Scheduling in Parallel Computing Systems

by Salleh Shaharuddin; Zomaya, Albert Y.

• ISBN13: 9780792385332
• ISBN10: 0792385330
• Format: Hardcover
• Copyright: 1999-04-01
• Publisher: Kluwer Academic Pub

Summary

Scheduling in Parallel Computing Systems: Fuzzy and Annealing Techniques advocates the viability of using fuzzy and annealing methods in solving scheduling problems for parallel computing systems. The book proposes new techniques for both static and dynamic scheduling, using emerging paradigms that are inspired by natural phenomena such as fuzzy logic, mean-field annealing, and simulated annealing. Systems that are designed using such techniques are often referred to in the literature as 'intelligent' because of their capability to adapt to sudden changes in their environments. Moreover, most of these changes cannot be anticipated in advance or included in the original design of the system. Scheduling in Parallel Computing Systems: Fuzzy and Annealing Techniques provides results that prove such approaches can become viable alternatives to orthodox solutions to the scheduling problem, which are mostly based on heuristics. Although heuristics are robust and reliable when solving certain instances of the scheduling problem, they do not perform well when one needs to obtain solutions to general forms of the scheduling problem. On the other hand, techniques inspired by natural phenomena have been successfully applied for solving a wide range of combinatorial optimization problems (e.g. traveling salesman, graph partitioning). The success of these methods motivated their use in this book to solve scheduling problems that are known to be formidable combinatorial problems. Scheduling in Parallel Computing Systems: Fuzzy and Annealing Techniques is an excellent reference and may be used for advanced courses on the topic.

Table of Contents

Preface	xi
Scheduling: Setting the Seen	1	(20)
Introduction	1	(4)
Problem Overview	5	(3)
Definitions	8	(4)
Task Precedence Relationships	12	(5)
Objective Function	15	(2)
NP-Completeness and Scheduling	17	(1)
Scope of this Work	18	(3)
Parallel Computing: Experimental Platform	21	(16)
Introduction	22	(1)
Parallel Computers	23	(3)
Transputer-Based Systems	26	(5)
Software Tools for the Transputer	31	(3)
Occam	31	(1)
Parallel C	32	(2)
FAMTS	34	(2)
Summary	36	(1)
Task Scheduling: Highlights and Framework	37	(20)
List Scheduling Heuritics	37	(2)
Heuristic Clustering Algorithms	39	(1)
Graph Theoretic Approaches	40	(1)
Queuing Theory	41	(1)
A Framework for Experiments	42	(4)
Case Study	46	(2)
Parallel Implementation	48	(6)
Summary	54	(3)
Static Scheduling: Mean-Field Annealing	57	(36)
Neural Networks	57	(4)
An Overview of Mean-Field Annealing	61	(7)
The Graph Partitioning Problem	68	(1)
Minimum Interprocessor Communication	69	(2)
MFA Model for Minimum Interprocessor Communication	71	(4)
Implementation Strategy	75	(3)
Case Study: A Fully-Connected Network	78	(3)
Different Network Topologies	81	(9)
Mesh and Hypercube Networks	83	(3)
MFA and Machine-Dependent Factors	86	(2)
Simulating TS_MFA-2	88	(2)
Summary	90	(3)
Dynamic Scheduling: A Fuzzy Logic Approach	93	(34)
Fuzzy Logic	93	(2)
Dynamic Scheduling	95	(1)
A Fuzzy Model for Dynamic Task Allocation	96	(16)
Computing Platform	97	(1)
Fuzzy Scheduling	98	(8)
Simulation Results	106	(6)
Fuzzy Dynamic Scheduling	112	(9)
Simulation Results	116	(5)
Implementation	121	(4)
Summary	125	(2)
Single-Row Routing: Another Computationally-Intractable Problem	127	(20)
Introduction	127	(4)
Solving the SRR Problem	131	(6)
Necessary and Sufficient Conditions	134	(3)
Existing Methods	137	(3)
Method by Tarng et al. (1984)	137	(2)
Method by Du and Liu (1987)	139	(1)
Simulated Annealing	140	(5)
Energy Formulation	141	(1)
SSA Implementation	142	(3)
Comparisons	145	(1)
Summary	146	(1)
Epilogue	147	(4)
Summary of Findings	147	(3)
Open Issues	150	(1)
Appendix A: Graph Multipartitioning Using Mean-Field Annealing	151	(2)
Appendix B: General List Heuristic (GL)	153	(2)
Appendix C: Single Row Routing (Tarng et al. 1984)	155	(2)
Appendix D: Single Row Routing (Du and Liu 1984)	157	(2)
References	159	(8)
Index	167