STG top > Introduction


Contents

STG top

Introduction

Minimum execution time multiprocessor scheduling problem

Standard Task Graph Set for evaluation of multiprocessor scheduling algorithms

How to make STG

STG format

Download STG

Optimal schedules

Links


Minimum Execution Time Multiprocessor Scheduling Problem

To efficiently execute programs in parallel on a multiprocessor system, a minimum execution time multiprocessor scheduling problem must be solved to determine the assignment of tasks to the processors and the execution order of the tasks so that the execution time is minimized [E.Coffman76] .

A task graph
Figure 1 : A task graph

The multiprocessor scheduling problem treated in this project is to determine a non-preemptive schedule that minimizes the execution time, or the schedule length, when a set of n computational tasks having arbitrary precedence constraints and arbitrary processing time are assigned to m processors of the same capability. These tasks are represented by a directed acyclic graph (DAG) called a "task graph", G = (N, E), where N is the set of nodes (|N| = n is the number of nodes) and E is the set of edges (|E| = e is the number of edges), as shown in Figure 1. However, this problem has been known as strong NP-hard intractable optimization problem when it assumes arbitrary number of processors, arbitrary task processing time, and arbitrary precedence constraints (as shown in Table 1).

Table 1 : Complexity of scheduling problems

Number of Processors(m)

Task Processing Time Ti

Precedence Constraints

Complexity

Arbitrary

Equal

Tree

O(n)

2

Equal

Arbitrary

O(n^2)

Arbitrary

Equal

Arbitrary

NP-hard

Fixed (m>=2)

Ti=1or2 for all i

Arbitrary

NP-hard

Arbitrary

Arbitrary

Arbitrary

Strong NP-hard



Standard Task Graph Set for Evaluation of Multiprocessor Scheduling Algorithms

The performance of scheduling algorithms has been evaluated using randomly generated task graphs [C.Ramamoorthy72] [H.Kasahara84] [T.Adam74] [A.Gerasoulis92] [T.Yang94] [H.El-Rewini90] [T.Yang93] [B.Shirazi90] [V.Almeida92] [G.Manimaran98] or task graphs modeled from actual application programs [T.Adam74] [A.Gerasoulis93] [T.Yang94] [Y.Kwok96] [B.Shirazi90] [H.Kasahara85] [S,Darbha98] [J.Llosa98] [A.Hurson90]. However, these task graphs are not typically available to other researchers. Therefore, fair performance comparisons of the algorithms under the same conditions has been impossible. To allow researchers to evaluate their algorithms under the same conditions, we proposed a Standard Task Graph Set covering previous task graph generation methods [C.Ramamoorthy72] [H.Kasahara84] [T.Adam74] [T.Yang91] [T.Yang94] [T.Yang93] [V.Almeida92].

Now the proposed Standard Task Graph Set is available at

http://www.kasahara.elec.waseda.ac.jp/schedule/

To make the Standard Task Graph Set better, we welcome information or URL's about other task graphs.
Please contact to



References

  • [E.Coffman76] E. G. Coffman, "Computer and Job-shop Scheduling Theory", John Willey & Sons (1976).
  • [C.Ramamoorthy72] C. V. Ramamoorthy, K. M. Chandy and M. J. Gonzalez, "Optimal scheduling strategies in a multiprocessor system", IEEE Trans. Comput., Vol.C-21, No.2, pp. 137-146 (1972).
  • [H.Kasahara84] H. Kasahara and S. Narita, "Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing", IEEE Trans. Comput., Vol.C-33, No.11, pp. 1023-1029 (1984).
  • [T.Adam74] T. L. Adam, K. M. Chandy and J. R. Dickson, "A Comparison of List Schedules for Parallel Processing Systems", Communications of the ACM, Vol.17, No.12, pp. 685-690 (1974).
  • [A.Gerasoulis92] A. Gerasoulis and T. Yang, "A Comparison of Clustering heuristics for Scheduling Directed Acyclic graphs on Multiprocessors", J. of Parallel and Distributed Computing, Vol.16, pp. 276-291 (1992).
  • [T.Yang94] T. Yang and A. Gerasoulis, "DSC : Scheduling Parallel Tasks on an Unbounded Number of Processors", IEEE Trans. Parallel and Distributed Systems, Vol.5, No.9, pp. 951-967 (1994).
  • [H.El-Rewini90] H. El-Rewini and T. G. Lewis, "Scheduling Parallel Program Tasks onto Arbitrary Target Machines", J. Parallel and Distributed Computing, Vol.9, pp. 138-153 (1990).
  • [T.Yang93] T. Yang and A. Gerasoulis, "List Scheduling With and Without Communication Delays", Parallel Computing 19, Vol.12, pp. 1321-1344 (1993).
  • [B.Shirazi90] B. Shirazi, M. Wang and G. Pathak, "Analysis and Evaluation of Heuristic Methods for Static Task Scheduling", J. Parallel and Distributed Computing, Vol.10, pp. 222-232 (1990).
  • [V.Almeida92] V. A. F. Almeida, I. M. M. Vasconcelos, J. N. C. Árabe and D. A. Menascé, "Using Random Task Graphs to Investigate the Potential Benefits of Heterogeneity in Parallel Systems", Proc. Supercomputing '92, pp. 683-691 (1992).
  • [G.Manimaran98] G. Manimaran and C. Siva Ram Murthy, "An Efficient Dynamic Scheduling Algorithm for Multiprocessor Real-time Systems", IEEE Trans. Parallel and Distributed Systems, Vol.9, No.3 pp.312-319 (1998).
  • [A.Gerasoulis93] A. Gerasoulis and T. Yang, "On the Granularity and Clustering of Directed Acyclic Task Graphs", IEEE Trans. Parallel and Distributed Systems, Vol.4, No.6, pp. 686-701 (1993).
  • [Y.Kwok96] Y. Kwok and I. Ahmad, "Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors", IEEE Trans. Parallel and Distributed Systems, Vol.7, No.5, pp. 506-521 (1996).
  • [H.Kasahara85] H. Kasahara and S. Narita, "Parallel Processing of Robot-Arm Control Computation on a Multiprocessor System", IEEE J. Robotics and Automation, Vol.RA-1, No.2, pp. 104-113 (1985).
  • [S.Darbha98] D. Darbha and D. P. Agrawal, "Optimal Scheduling Algorithm for Distributed-Memory Machines", IEEE Trans. Parallel and Distributed Systems, Vol.9, No.1, pp. 87-95 (1998).
  • [J.Llosa98] J. Llosa, M. Valero, E. Ayguadé and A. González, "Modulo Scheduling with Reduced Register Pressure", IEEE Trans. Comput., Vol.47, No.6, pp. 625-638 (1998).
  • [A.Hurson90] A. R. Hurson, B. Lee, B. Shirazi and M. Wang, "A Program Allocation Scheme for Data Flow Computers", Proc. 1990 Int'l Conf. on Parallel Processing, pp. I-415-I-423 (1990).
  • [T.Yang91] T. Yang and A. Gerasoulis, "A Fast Static Scheduling Algorithm for DAGs on an Unbounded Number of Processors", Proc. Supercomputing '91, pp. 633-642 (1991).


page top previous page next page

Copyright (C) Kasahara Lab., Waseda Univ.. All rights reserved.

Standard Task Graph Set

Kasahara Laboratory
Dept. of Electrical, Electronics
and Computer Engineering,
Waseda University
E-Mail :