Job Scheduling Strategies for Parallel Processing: 12th International Workshop, JSSPP 2006, Saint-Malo, France, June 26, 2006, Revised Selected Papers (Lecture Notes in Computer Science (4376))

This book constitutes the thoroughly refereed post-proceedings of the 12th International Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2006, held in Saint-Malo, France in June 2006 in conjunction with the Joint International Conference on Measurement and Modeling of Computer Systems SIGMETRICS/Performance 2006. The 12 revised full research papers cover all current issues of job scheduling strategies for parallel processing. Title Preface Table of Contents Provably Efficient Two-Level Adaptive Scheduling Introduction Models and Objective Functions The AGDEQ Algorithm Makespan of AGDEQ Mean Response Time of AGDEQ for Batched Jobs ASDEQ Algorithm and Performance Competitiveness of Mean Response Time for Nonbatched Jobs Related Work Conclusion Scheduling Dynamically Spawned Processes in MPI-2 Introduction Dynamic Creation of Processes in MPI MPI-2 On-Line Scheduling of Parallel Processes A Scheduler for MPI-2 Programs The Scheduler The Overloaded Primitives The Task Graph Structure of the Scheduler Scheduling Heuristics Programming with MPI-2: The Fibonacci Example Experimental Evaluation of the Scheduler The Fibonacci Test-Case with MPI-2 Computing Prime Numbers in an Interval Conclusion and Future Work Advance Reservation Policies for Workflows Introduction Background Towards a Solution of the Problem Input and Notation Outline of the Solution Recursive Spare Time Allocation The Critical Path Based Allocation An Example Experimental Results The Setting Performance Results Conclusion On Advantages of Scheduling Using Genetic Fuzzy Systems Introduction Background Scheduling Concepts Evolution Strategies Fuzzy Systems Scheduling Objectives and Features Scheduling Objectives Feature Definitions Rule Based Scheduling Systems Probability Driven Rule Base Development Scheduling Strategies Based on Genetic Fuzzy Systems Evaluation Estimation of Computational Effort to Establish the Rule Based Scheduling System Conclusion Moldable Parallel Job Scheduling Using Job Efficiency: An Iterative Approach Introduction Related Work Simulation Setup Workload Generation The Downey Model Fair-Share Allocation and Overbooking Fair-Share Based Allocation Perfect Scalability Non-ideal Job Scalability Efficiency Considerations Incorporating Efficiency into Fairshare Experimental Results An Iterative Approach for Moldable Scheduling The Iterative Algorithm Results Conclusions Adaptive Job Scheduling Via Predictive Job Resource Allocation Introduction Related Work The Cirne-Berman Scheduler The SCOJO-P Space Sharing Scheduler The Original SCOJO Scheduler The New SCOJO-P Scheduler Adaptive Target-Size Determination Trying to Schedule the Job with Adaptive Target Size and Adaptive Backfilling Discussion of Expected Behavior and Benefits The Speedup Model Used Experimental Evaluation Test Environment and Measured Metrics Workload Model Approaches Tested Experimental Results Summary and Conclusion A Data Locality Aware Online Scheduling Approach for I/O-Intensive Jobs with File Sharing Introduction Problem Definition and Use-Case Applications Related Work Dynamic Job Scheduling Hypergraph Partitioning Runtime Hypergraph-Based Mapping of the System State Job Ordering in a Compute Node and Scheduling of Remote File Transfers File Eviction Policy Existing Job Mapping Techniques Experimental Results Application Workloads Modeling the Load Modeling the Arrival Process Performance Evaluation on a Cluster Conclusions Volunteer Computing on Clusters Introduction Utilization of Clusters Fine Grain Cycle Stealing on Clusters Experimental Setup Slowdown on Linux Impact on Cluster Throughput Parallel Guest Applications Scalability Discussion Guidelines for Volunteer Computing on Clusters Case for Zero Priority Processes Conclusions Load Balancing: Toward the Infinite Network and Beyond Introduction ProActive IFL: A Randomised Load-Balancing of Active-Objects on P2P Networks Definitions Original Version of the IFL Algorithm New Version of the IFL Algorithm Experimental Verification Scaling Tests Using Simulation Fine-Tuning Scaling Conclusions Symbiotic Space-Sharing on SDSC’s DataStar System Introduction Hardware Environment The Effects of Sharing Resources Memory Sharing I/O Sharing Mixing Jobs Symbiotic Space-Sharing and Parallel Codes Towards a Symbiotic Scheduler Identifying Symbiosis Prototype Symbiotic Scheduler Related Work Conclusions and Future Work Multithreading Paging Time-Sharing SMP Memory Bus Contention Other Related Work Modeling Job Arrivals in a Data-Intensive Grid Introduction Statistical Analysis Workload Description Job Arrival Analysis Self-similarity Methodology Markov Modulated Poisson Processes Hyperexponetial Renewal Processes Transportation Distance of Time Series Bootstrapping Modeling Grid Level Virtual Organization Level Region Level Stochastic vs. Deterministic Related Work Conclusions and Future Work On Grid Performance Evaluation Using Synthetic Workloads Introduction System Scenarios Performance Metrics Time-, Resource- and System-Related Metrics Workload Completion and Failure Metrics Metrics Selection General Aspects for Workload Modeling User Group Model Submission Patterns Grid-Specific Workload Modeling Types of Applications Computation Management Data Management Network Management Locality/Origin Management Failure Modeling Economic Models GrenchMark: A Framework for Grid Performance Evaluation Conclusion Current Features Extension Points Grid vs. Parallel Production Environments Author Index This book constitutes the thoroughly refereed postproceedings of the 12th International Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2006, held in Saint-Malo, France, in June 2006 in conjunction with the Joint International Conference on Measurement and Modeling of Computer Systems SIGMETRICS/Performance 2006. The 12 revised full research papers presented went through two rounds of reviewing and improvement. The papers cover all current issues of job scheduling strategies for parallel processing such as workflow problems, scheduling performance, job migration issues, performance degradation by resource sharing, and job modeling issues in grid computing