Job Scheduling Strategies for Parallel Processing: IPPS/SPDP'99 Workshop, JSSPP'99, San Juan, Puerto Rico, April 16, 1999, Proceedings (Lecture Notes in Computer Science, 1659)

✍ Scribed by Dror G. Feitelson (editor), Larry Rudolph (editor)

• Publisher: Springer
• Year: 1999
• Tongue: English
• Leaves: 243
• Category: Library

✦ Synopsis

This volume contains the papers presented at the f th workshop on Job SchedulingStrategiesforParallelProcessing, whichwasheldinconjunctionwith the IPPS/SPDP'99conference in San Juan, Puerto Rico, on April 16, 1999.The papers have been through a complete refereeing process, with the full version beingreadandevaluatedbyv etosevenmembersoftheprogramcommittee.We would like to take this opportunity to thank the program committee, Andrea Arpaci-Dusseau, Stephen Booth, Allen Downey, Allan Gottlieb, Atsushi Hori, PhilKrueger, RichardLagerstrom, MironLivny, VirginiaLo, ReaganMoore, Bill Nitzberg, UweSchwiegelshohn, KenSevcik, MarkSquillante, andJohnZahorjan, for an excellent job. Thanks are also due to the authors for their submissions, presentations, and nal revisionsfor this volume. Finally, we wouldlike to thank the MIT Laboratory for Computer Science and the Computer Science Institute at the Hebrew Universityfor the use of their facilities in the preparationof these proceedings. Thiswasthe fth annualworkshopinthis series, whichre?ectsthe continued interest in this eld. The previous four were held in conjunction with IPPS'95 through IPPS/SPDP'98. Their proceedings are available from Springer-Verlag as volumes 949, 1162, 1291, and 1459 of the Lecture Notes in Computer Science series. Sinceour rstworkshop, parallelprocessinghas evolvedtothe pointwhereit is no longer synonymous with scienti c computing on massively parallel sup- computers. In fact, enterprise computing on one hand and metasystems on the other hand often overshadow the original uses of parallel processing. This shift has underscored the importance of job scheduling in multi-user parallelsystems. Correspondingly, we had a session in the workshop devoted to job scheduling on standalonesystems, emphasizing gang scheduling, and another on scheduling for meta-systems. A third session continued the trend from previous workshops of discussing evaluation methodology and workloads. Aninnovationthisyearwasapaneldiscussiononthepossiblestandardization ofaworkloadbenchmarkthatwillservefortheevaluationofdi erentschedulers.

✦ Table of Contents

Job Scheduling Strategies for Parallel Processing
Preface
Table of Contents
Scheduling for Parallel Supercomputing: A Historical Perspective of Achievable Utilization
Introduction
The NAS Parallel Supercomputing Workload
Supercomputer Resource Sharing
Analysis of NAS Parallel Supercomputer Utilization
Intel iPSC/860 (Jan. 1990 to Sept. 1994)
TMC CM-5 (Jan. 1993 to Mar. 1995)
Intel Paragon XP/S-15 (Feb. 1993 to July 1995)
IBM SP-2 (July 1994 to Sept. 1997)
Cray Origin2000 (Jan. 1997 - )
Caveats and Conclusions
Future Work
References
On the Design and Evaluation of Job Scheduling Algorithms
Introduction
Scheduling Systems
Scheduling Policy
Objective Function
Scheduling Algorithm
Dependences
Comparison
Evaluation Example
Determination of the Objective Function
Description of the Algorithms
FCFS
Backfilling
List Scheduling (Garey and Graham)
SMART
PSRS
Workload
Workload Trace
Workload with Probability Distribution
Randomized Workload
Evaluation Results
Conclusions
Comparing Logs and Models of Parallel Workloads Using the Co-plot Method
1. Introduction
2. Co-Plot
3. The Data Set
4. Production Workloads: Variables
5. Production Workloads: Observations
6. Production Workloads Over Time
7. Synthetic Workloads
8. Implications for Modeling
9. Self-Similarity
10. Conclusions and Future Research
11. Acknowledgements
References
Appendix: Theory of Self-Similarity
Benchmarks and Standards for the Evaluation of Parallel Job S
Introduction
Motivation
Scope
Workload Benchmarks for Parallel Systems
State of the Art
Future Work
A Standard Workload Format
Workload Benchmarks for Metacomputing
Scheduling in a Metacomputing Environment
Components of a Benchmark Suite
Logging Scheduling Events in a Metacomputer
Evaluating Matacomputing Scheduling
Convergence
A Comparison
Integration of Parallel Systems and Metacomputing
An Evaluation Environment
Conclusions
The Effect of Correlating Quantum Allocation and Job Size for Gang Scheduling
Introduction
Scheduling Algorithm Description
Matrix
LRS
DHC
Simulation Methodology, Workload Models, and Metric
Definitions and Metrics
Workload Models
Results
Geometric-Bounded N2 Workload
Geometric-Bounded N1.5 Workload
Geometric-Bounded N Workload
Feitelson96 Workload
Response Times
Relative Performance of Algorithms
Conclusions
Scheduling on AP/Linux for Fine and Coarse Grain Parallel Processes
Introduction
Outline of AP/Linux
Parallel Process Scheduling of AP/Linux
Creation of Parallel Processes
Layout of Parallel Processes
Synchronization
Performance Evaluation
Comparison with CellOS
Processing of Several Parallel Processes
Performance of Synchronization
Related Research
Conclusions
Job Re-packing for Enhancing the Performance of Gang Scheduling
Introduction
Motivation
Job Re-packing
Resource Allocation Based on Job Re-packing
Conclusions
Process Tracking for Parallel Job Control
Introduction
Existing UNIX Mechanisms
Implementing Process Tracking
Experimental Results
System Integration
Conclusions and Future Work
The Legion Resource Management System
Introduction
Legion
Legion Core Objects
Resource Management Infrastructure (RMI)
Host and Vault Objects
The Collection
The Scheduler and Schedules
The Enactor
Application Monitoring
Examples of Use
Random Scheduling
Improved Random Scheduling (IRS)
Specialized Policies
Related Work
Conclusions and Future Work
Scheduling a Metacomputer with Uncooperative Sub-schedulers
Introduction
Background
Infrastructure
Job Scheduling for Metacomputing
Modeling the Metacomputer Infrastructure
Workload Model and Evaluation Criteria
Job Arrivals
Job Sizes
Internal Job Structure
Evaluation Criteria
The Algorithms
Scheduling with Full Control -- The Idealized Scenario
Scheduling with No Control - The Reference Case
Scheduling with Minimum Control - The Compromise
Results
Conclusion
Using Run-Time Predictions to Estimate Queue Wait Times and Improve Scheduler Performance
Introduction
Predicting Application Run Times
Our Run-Time Prediction Technique
Related Work
Predicting Queue Wait Times
Improving Scheduler Performance
Conclusions
Deterministic Batch Scheduling without Static Partitioning
Introduction
Related Work
Miser
Resource Accounting
Job Scheduling
Kernel - Miser Interaction
Kernel Support
The Scheduler
Virtual Memory Subsystem
Empirical Evidence
Experiments
Future Work
Conclusions
Author Index