Deterministic scheduling in systems with interprocessor communication times
Jing‐Jang Hwang, Yuan-Chieh Chow · 1987
This dissertation is devoted to developing a new scheduling theory for computer networks and modern MIMD architectures. We take interprocessor communication overhead, system architecture, and task precedence relationships into account in the formulation of a new class of scheduling problems. The objective is to minimize the total schedule length, which is equivalent to maximizing the multiprocessing speedup. As concrete results, three scheduling methods--ELS, ETF, and JLP--are designed and analyzed. The first method, ELS, extended from the classical list scheduling, is unsatisfactory since it is shown that all intertask communication requirements may turn out, in worst cases, to cause real communications and to lengthen the total schedule. The second method, ETF, abbreviated from Earliest Task First, is a highly intelligent heuristic which maintains the same strength of list scheduling when dealing with the scheduling of concurrent tasks in a precedence graph. In addition, ETF effectively shortens communication delays and significantly outperforms ELS according to worst-case analysis. The establishment of a worst-case bound for ETF is a major contribution of this work. The bound provides a nice performance guarantee for systems with any number of processors. The third method, JLP, abbreviated from Join with the Latest Predecessor, is an O(n) algorithm which guarantees generating an optimal schedule for a particular problem. The problem represents a solvable case in the problem space where interprocessor communication overhead is included in the system and program models. Finally, a unified model is developed for analyzing the system speedup in terms of several major factors: communication overhead, application algorithms, and scheduling methods. The speedup model presented brings together in a useful way a number of algorithm and system characteristics which can be used analytically or empirically to determine the speedup achieved. With the model, the impact on overall system performance of interprocessor communication overhead, in the presence of a non-optimal scheduling method, can be quantitatively assessed. To demonstrate the application of the model as well as to emphasize the role of scheduling in overall system performance, the results obtained for ELS and ETF are translated into expressions of speedup degradation.