Scheduling and Load Balancing in Parallel and Distributed Systems

by Shirazi, Behrooz A.; Hurson, Ali R.; Kavi, Krishna M.

• ISBN13: 9780818665875
• ISBN10: 0818665874
• Edition: 1st
• Format: Paperback
• Copyright: 1995-05-14
• Publisher: Wiley-IEEE Computer Society Pr

Summary

Advances in hardware and software technologies have led to an increased interest in the use of large-scale parallel and distributed systems for database, real-time, defense, and large-scale commercial applications. One of the biggest system issues is developing effective techniques for the distribution of multiple program processes on multiple processors. This book discusses how to schedule the processes among processing elements to achieve the expected performance goals, such as minimizing execution time, minimizing communication delays, or maximizing resource utilization. This book focuses on the future directions of the static scheduling and dynamic load balancing methods in parallel and distributed systems. It provides an overview and a detailed discussion on a wide range of topics from theoretical background to practical, state-of-the-art scheduling and load balancing techniques. The book will be a useful guide to industry professionals, academic professors, and students who are interested in these important aspects of parallel and distributed systems. Also, it will be helpful to those working on research and development in parallel processing applications, compilers and operating systems, system design, and software tools for parallel program development.

Author Biography

Behrooz A. Shirazi and Ali R. Hurson are the authors of Scheduling and Load Balancing in Parallel and Distributed Systems, published by Wiley.

Table of Contents

Preface	p. ix
Acknowledgments	p. xi
Introduction to Scheduling and Load Balancing	p. 1
A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems (IEEE Transactions on Software Engineering, February 1988, pages 141-154)	p. 7
Multiprocessor Scheduling with the Aid of Network Flow Algorithms (IEEE Transactions on Software Engineering, January 1977, pages 85-93)	p. 21
Load Distributing for Locally Distributed Systems (Computer, December 1992, pages 33-44)	p. 30
Static Scheduling	p. 43
Analysis and Evaluation of Heuristic Methods for Static Task Scheduling (Journal of Parallel and Distributed Computing, Volume 10, 1990, pages 222-232)	p. 50
Compile-time Partitioning and Scheduling of Parallel Programs (Proceedings of the SIGPLAN '88 Symposium on Compiler Construction, 1986, pages 17-26)	p. 61
Guided Self-Scheduling: A Practical Scheduling Scheme for Parallel Supercomputers (IEEE Transactions on Computers, December 1987, pages 1425-1439)	p. 71
Multiprocessor Scheduling with Communication Delays (Parallel Computing, Volume 16, 1990, pages 173-182)	p. 86
Heuristic Algorithms for Task Assignment in Distributed Systems (IEEE Transactions on Computers, November 1988, pages 1384-1397)	p. 96
Allocating Modules to Processors in a Distributed System (IEEE Transactions on Software Engineering, November 1989, pages 1427-1436)	p. 110
Compile-Time Scheduling and Assignment of Data-Flow Program Graphs with Data-Dependent Iteration (IEEE Transactions on Computers, November 1991, pages 1225-1238)	p. 120
A Program Allocation Scheme for Data Flow Computers (Proceedings 1990 International Conference on Parallel Processing, pages I-415-I-423)	p. 134
Task Granularity and Partitioning	p. 143
On the Granularity and Clustering of Directed Acyclic Task Graphs (IEEE Transactions on Parallel and Distributed Systems, June, 1993, pages 686-701)	p. 148
The Effects of Problem Partitioning, Allocation, and Granularity on the Performance of Multiple-Processor Systems (IEEE Transactions on Computers, April 1987, pages 421-432)	p. 164
Grain Size Determination for Parallel Processing (IEEE Software, January 1988, pages 23-32)	p. 176
Lazy Task Creation: A Technique for Increasing the Granularity of Parallel Programs (IEEE Transactions on Parallel and Distributed Systems, July 1991, pages 264-280)	p. 186
Scheduling Tools	p. 203
PARSA: A Parallel Program Software Development Tool (Proceedings 1994 Symposium on Assessment of Quality Software Development Tools, 1994, pages 96-111)	p. 207
The TOPSYS Architecture (Proceedings of CONPAR '90 VAPP IV: LNCS, Volume 457, 1990)	p. 223
Parallax: A Tool for Parallel Program Scheduling (IEEE Parallel & Distributed Technology, May 1993, pages 62-72)	p. 235
Parafrase-2: An Environment for Parallelizing, Partitioning, Synchronizing, and Scheduling Programs on Multiprocessors (Proceedings 1989 International Conference on Parallel Processing, Volume II, 1989, pages II-39-II-48.)	p. 246
Mapping Function-Parallel Programs with the Prep.-P Automatic Mapping Preprocessed (Technical Report Number CS 94-397, December 1994, pages 1-28)	p. 256
OREGAMI: Tools for Mapping Parallel Computations to Parallel Architectures (International Journal of Parallel Programming, 1991, pages 237-270)	p. 284
Load Balancing	p. 309
Load Sharing in Distributed Systems (IEEE Transactions on Computers, March 1985, pages 204-217)	p. 314
The Probability of Load Balancing Success in a Homogeneous Network (IEEE Transactions on Software Engineering, September 1991, pages 922-933	p. 328
Adaptive Load Sharing in Homogeneous Distributed Systems (IEEE Transactions on Software Engineering, May 1986, pages 662-675)	p. 340
Imbedding Gradient Estimators in Load Balancing Algorithms (Proceedings IEEE 8th International Conference on Distributed Computing Systems, 1988, pages 482-490)	p. 354
The Diverse Objectives of Distributed Scheduling Policies (Proceedings IEEE 7th International Conference on Distributed Computing Systems, 1987, pages 242-249)	p. 363
Effects of Response and Stability on Scheduling in Distributed Computing Systems (IEEE Transactions on Software Engineering, November 1988, pages 1578-1588)	p. 371
Condor-A Hunter of Idle Workstations (Proceedings IEEE 8th International Conference on Distributed Computing Systems, 1988, pages 104-111)	p. 382
GAMMON: A Load Balancing Strategy for Local Computer Systems with Multiaccess Networks (IEEE Transactions on Computers, August 1989, pages 1098-1109)	p. 390
The Stealth Distributed Scheduler (Proceedings IEEE 11th International Conference on Distributed Computing Systems, 1991, pages 336-343)	p. 402
Mechanisms for Process Migration	p. 411
Design Issues of Process Migration Facilities in Distributed Systems (IEEE Technical Committee on Operating Systems Newsletter, Winter 1989, pages 3-13)	p. 414
Heterogeneous Process Migration by Recompilation (Proceedings IEEE 11th International Conference on Distributed Computing Systems, 1991, pages 18-25)	p. 425
Attacking the Process Migration Bottleneck (Proceedings of the 11th ACM Symposium on Operating Systems Principles, 1987, pages 13-24)	p. 433
Designing a Process Migration Facility (Computer, September 1989, pages 47-56)	p. 445
Process Migration in DEMOS/MP (Proceedings of the 9th ACM Symposium on Operating Systems Principles, 1983, pages 110-119)	p. 455
Preemptable Remote Execution Facilities for the V-System (Proceedings of the 10th ACM Symposium on Operating Systems Principles, 1985, pages 2-12)	p. 465
Load Indices	p. 477
Predictability of Process Resource Usage: A Measurement-Based Study on UNIX (IEEE Transactions on Software Engineering, December 1989, pages 1579-1586)	p. 479
An Empirical Investigation of Load Indices for Load Balancing Applications (Proceedings Performance '87, The 12th Annual International Symposium on Computer Performance Modeling, Measurement and Evaluation, 1987, pages 515-528)	p. 487
The Influence of Different Workload Descriptions on a Heuristic Load Balancing Scheme (IEEE Transactions on Software Engineering, July 1991, pages 725-730)	p. 497
About the Authors	p. 503
Table of Contents provided by Ingram. All Rights Reserved.