PARAdeg-processor scheduling for acyclic SWITCH-less program nets. (English) Zbl 0978.90053
Summary: This paper deals with multiprocessor scheduling for acyclic SWITCH-less program nets that is a graph representation of a data-flow program. A task graph is a special case of acyclic SWITCH-less not PN and the important difference is that a program net allows nodes to fire more than once while a task graph asks its each node to fire exactly once. Hence scheduling problem for program nets is NP-hard in a stronger sense. In this paper, we first extend CP (critical path) method by taking firing numbers of nodes into account to propose extended critical path (ECP) method. Based on this we further propose ORF/ECP (OR-node First/ECP), and LTF/ECP (Larger node firing Time First/ECP) methods, by taking notice of firings of OR-nodes and node firing times, respectively. Then using priority lists as populations, we propose two genetic algorithms \(n\)-GA and 1-GA, by, respectively, requiring all and only initial populations satisfying precedence relation of nodes. Our experiments show that: (i) precedence relation of nodes is no more important for scheduling of program nets; (ii) 1-GA gives the best results, and LTF/ECP is next to 1-GA and is effective when node firing numbers are not large.
MSC:
| 90B36 | Stochastic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90B10 | Deterministic network models in operations research |
Keywords:
data-flow program; program net; multiprocessor scheduling; list scheduling; GA scheduling; evaluationSoftware:
SWITCHReferences:
| [1] | J.B. Dennis, First version of data flow procedure language. Lecture Notes in Computer Science, vol. 19G, Springer, New York, 1974.; J.B. Dennis, First version of data flow procedure language. Lecture Notes in Computer Science, vol. 19G, Springer, New York, 1974. · Zbl 0315.68007 |
| [2] | J.B. Dennis, The MIT data flow engineering model, Proceedings of IFIP Congress 83, 1983, pp. 553-560.; J.B. Dennis, The MIT data flow engineering model, Proceedings of IFIP Congress 83, 1983, pp. 553-560. |
| [3] | Rumbaugh, J., A data flow multiprocessor, IEEE Trans. Comput., c-26, 2, 138-146 (1977) · Zbl 0348.68040 |
| [4] | Veen, A. H., Dataflow machine architecture, ACM Comput. Survey, 18, 4, 365-396 (1986) |
| [5] | Ge, Q. W.; Watanabe, T.; Onaga, K., Topological analysis of firing activities of data-flow program pets, IEICE Trans. Fund., E73, 7, 1215-1224 (1990) |
| [6] | Ge, Q. W.; Watanabe, T.; Onaga, K., Execution termination and computation determinacy of data-flow program nets, J. Franklin Institute, 328, 1, 123-141 (1991) · Zbl 0717.68012 |
| [7] | Yuba, T., Dataflow parallel computers, J. System Control Inform. Japan, 33, 5, 220-229 (1989) |
| [8] | Ge, Q. W.; Watanabe, T.; Onaga, K., Analysis of parallelism in autonomous execution of data-flow program nets, IEICE Trans. Fund., E74, 10, 3008-3017 (1991) |
| [9] | M.R. Garey, D.S. Johson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979.; M.R. Garey, D.S. Johson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979. · Zbl 0411.68039 |
| [10] | E.G. Coffman, Computer and Job-Shop Scheduling Theory, Wiley, New York, 1976.; E.G. Coffman, Computer and Job-Shop Scheduling Theory, Wiley, New York, 1976. · Zbl 0359.90031 |
| [11] | Lenstra, J. K.; Kan, A. H.G. R., Complexity of scheduling under precedence constraints, Oper. Res., 26, 22-35 (1978) · Zbl 0371.90060 |
| [12] | Hu, T. C., Parallel sequencing and assembly line problems, Oper. Res., 9, 841-848 (1961) |
| [13] | Coffman, E. G.; Graham, R. L., Optimal scheduling for two-processors systems, Acta. Informatica, 1, 200-213 (1972) · Zbl 0248.68023 |
| [14] | T.E. Morton, D.W. Pentico, Heuristic Scheduling Systems, Wiley, New York, 1993.; T.E. Morton, D.W. Pentico, Heuristic Scheduling Systems, Wiley, New York, 1993. |
| [15] | T.L. Adam, K.M. Chandy, J.R. Dickson, A comparison of list scheduling for parallel processing systems, Commun. ACM 17 (12) (1974).; T.L. Adam, K.M. Chandy, J.R. Dickson, A comparison of list scheduling for parallel processing systems, Commun. ACM 17 (12) (1974). · Zbl 0293.68047 |
| [16] | H. Kasahara, S. Narita, Practical multiprocessor scheduling algorithms for efficient parallel processing, IEEE Trans. Comput. c-33 (11) (1984).; H. Kasahara, S. Narita, Practical multiprocessor scheduling algorithms for efficient parallel processing, IEEE Trans. Comput. c-33 (11) (1984). |
| [17] | Onaga, K.; Silva, Manuel; Watanabe, T., Qualitative analysis of periodic schedules for deterministically timed petri net systems, IEICE Trans. Fund., E76-A, 4, 580-592 (1993) |
| [18] | Tanida, T.; Watanabe, T.; Yamauchi, M.; Onaga, K., Priority-list scheduling in timed petri nets, ICIEC Trans. Fund., E75-A, 10, 1394-1406 (1992) |
| [19] | Tamaki, H., Combinatorial optimization by genetic algorithms, J. SICE, 34, 5, 347-352 (1995) |
| [20] | Hou, S. H.; Ansari, N.; Ren, H., A genetic algorithm for multiprocessor scheduling, IEEE Trans. Parallel Distrib. Systems, 5, 2, 113-120 (1994) |
| [21] | Ge, Q. W.; Yanagida, H., A method of computing minimum firing time for self-cleaning SWITCH-less program nets, J. Franklin Institute, 335B, 5, 877-895 (1998) · Zbl 0973.68180 |
| [22] | J. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975.; J. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975. · Zbl 0317.68006 |
| [23] | L. Davis, Handbook of Genetic Algorithms, Van Nostrand, 1990.; L. Davis, Handbook of Genetic Algorithms, Van Nostrand, 1990. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
