zbMATH — the first resource for mathematics

A standard task graph set for fair evaluation of multiprocessor scheduling algorithms. (English) Zbl 1014.90044
Summary: A ‘standard task graph set’ is proposed for fair evaluation of multiprocessor scheduling algorithms. Developers of multiprocessor scheduling algorithms usually evaluate them using randomly generated task graphs. This makes it difficult to compare the performance of algorithms developed in different research groups. To make it possible to evaluate algorithms under the same conditions so that their performances can be compared fairly, this paper proposes a standard task graph set covering many ot the proposed task graph generation methods. This paper also evaluates as examples two heuristic algorithms (CP and CP/MISF), a practical sequential optimization algorithm (DF/IHS), and a practical parallel optimization algorithm (PDF/IHS) using the proposed standard task graph set. This set is available at http://www.kasahara.elec.waseda.ac.jp/schedule/.

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI
[1] Computer and Job-shop Scheduling Theory. Wiley: New York, 1976.
[13] Clustering task graphs for message passing architectures. In Proceedings of the 4th ACM International Conference of Supercomputing 1990; 447-456.
[14] A fast static scheduling algorithm for dags on an unbounded number of processors. In Proceedings of Supercomputing ’91, 1991; 633-642.
[23] Using random task graphs to investigate the potential benefits of heterogeneity in parallel systems. In Proceedings of Supercomputing ’92 1992; 683-691.
[27] A program allocation scheme for data flow computers. In Proceedings of the 1990 International Conference on Parallel Processing, 1990; I 415-I 423.
[28] Data-localization for fortran macrodataflow computation using partial static task assignment. In Proceedings of the 10th ACM International Conference on Supercomputing 1996; 61-68.
[29] Parallel processing of near fine grain tasks using static scheduling on oscar. In Proceedings of the IEEE ACM Supercomputing ’90, November 1990.
[30] A multi-grain parallelizing compilation scheme for oscar (optimally scheduled advanced multiprocessor). In Proceedings of the 4th Workshop on Languages and Compilers for Parallel Computing, August 1991.
[34] A parallel processing scheme for the solution of sparse linear equations using static optimal-multiprocessor-scheduling algorithms. In Proceedings of the 2nd International Conference on Supercomputing, May 1987.
[35] An approach to supercomputing using multiprocessor scheduling algorithms. In Proceedings of the IEEE 1st International Conference on Supercomputing, December 1985; 139-148.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.