Job Scheduling Strategies for Parallel Processing: IPPS/SPDP’99Workshop, JSSPP’99 San Juan, Puerto Rico, April 16, 1999 Proceedings

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