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)

✍ Scribed by Eitan Frachtenberg (editor), Uwe Schwiegelshohn (editor)

• Publisher: Springer
• Year: 2007
• Tongue: English
• Leaves: 263
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

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