Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems.

*(English)*Zbl 1086.90021Summary: Scheduling program tasks on processors is at the core of the efficient use of multiprocessor systems. Most task-scheduling problems are known to be NP-Hard and, thus, heuristics are the method of choice in all but the simplest cases. The utilization of acknowledged sets of benchmark-problem instances is essential for the correct comparison and analysis of heuristics. Yet, such sets are not available for several important classes of scheduling problems, including multiprocessor scheduling problem with communication delays (MSPCD) where one is interested in scheduling dependent tasks onto homogeneous multiprocessor systems, with processors connected in an arbitrary way, while explicitly accounting for the time required to transfer data between tasks allocated to different processors. We propose test-problem instances for the MSPCD that are representative in terms of number of processors, type of multiprocessor architecture, number of tasks to be scheduled, and task graph characteristics (task execution times, communication costs, and density of dependencies between tasks). Moreover, we define our task-graph generators in a way appropriate to ensure that the corresponding problem instances obey the theoretical principles recently proposed in the literature.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |

PDF
BibTeX
XML
Cite

\textit{T. Davidović} and \textit{T. G. Crainic}, Comput. Oper. Res. 33, No. 8, 2155--2177 (2006; Zbl 1086.90021)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Hu, T.C., Parallel sequencing and assembly line problems, Operations research, 9, 6, 841-848, (1961) |

[2] | Garey, M.R.; Johnson, D.S., Computers and intractabilitya guide to the theory of NP-completness, (1979), W. H. Freeman and Company San Francisco |

[3] | Ullman, J.D., NP-complete scheduling problems, Journal of computer and system science, 10, 3, 384-393, (1975) · Zbl 0313.68054 |

[4] | Coffman, E.G.; Graham, R.L., Optimal scheduling for two processor systems, Acta informatica, 1, 200-213, (1972) · Zbl 0248.68023 |

[5] | Krishnamoorthy, V.; Efe, K., Task scheduling with and without communication delaysa unified approach, European journal of operational research, 89, 366-379, (1996) · Zbl 0913.90173 |

[6] | Varvarigou, T.A.; Roychowdhury, V.P.; Kailath, T.; Lawler, E., Scheduling in and out forests in the presence of communication delays, IEEE transactions parallel and distributed systems, 7, 10, 1065-1074, (1996) |

[7] | Djordjević, G.; Tošić, M., A compile-time scheduling heuristic for multiprocessor architectures, The computer journal, 39, 8, 663-674, (1996) |

[8] | Kwok, Y.-K.; Ahmad, I., Dynamic critical path schedulingan effective technique for allocating task graphs to multiprocessors, IEEE transactions on parallel and distributed systems, 7, 5, 506-521, (1996) |

[9] | Manoharan, S.; Thanisch, P., Assigning dependency graphs onto processor networks, Parallel computing, 17, 63-73, (1991) · Zbl 0723.68021 |

[10] | Sarje, A.K.; Sagar, G., Heuristic model for task allocation in distributed computer systems, IEE Proceedings-E, 138, 5, 313-318, (1991) |

[11] | Sih, G.C.; Lee, E.A., A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures, IEEE transactions on parallel and distributed systems, 4, 2, 175-187, (1993) |

[12] | Blazewicz, J.; Drozdowski, M.; Ecker, K., Management of resources in parallel systems, (), 263-341 |

[13] | Pinedo, M., Scheduling theory, algorithms and systems, (2002), Prentice-Hall Englewood Cliffs, NJ · Zbl 1145.90394 |

[14] | Coll PE, Ribeiro CC, de Sousa CC. Test instances for scheduling unrelated processors under precedence constraints. http://www-di.inf.puc-rio.br/\(\sim\)celso/grupo/readme.ps; 2002. |

[15] | Kwok, Y.-K.; Ahmad, I., Benchmarking and comparison of the task graph scheduling algorithms, Journal of parallel and distributed computing, 59, 3, 381-422, (1999) · Zbl 0958.68020 |

[16] | Tobita, T.; Kasahara, H., A standard task graph set for fair evaluation of multi-processor scheduling algorithms, Journal of scheduling, 5, 5, 379-394, (2002) · Zbl 1014.90044 |

[17] | Hall, N.G.; Posner, M.E., Generating experimental data for computational testing with machine scheduling applications, Operations research, 49, 854-865, (2001) · Zbl 1163.90490 |

[18] | Davidović, T., Exhaustive List-scheduling heuristic for dense task graphs, Yujor, 10, 1, 123-136, (2000) · Zbl 0948.68226 |

[19] | Kwok, Y.-K.; Ahmad, I., Bubble schedulinga quasi-dynamic algorithm for static allocation of tasks to parallel architectures, (), 36-43 |

[20] | Kwok, Y.-K.; Ahmad, I., Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm, Journal of parallel and distributed computing, 47, 58-77, (1997) |

[21] | Davidović, T.; Maculan, N.; Mladenović, N., Mathematical programming formulation for the multiprocessor scheduling problem with communication delays, (), 331-334 · Zbl 1049.68026 |

[22] | Khan, A.A.; McCreary, C.L.; Jones, M.S., A comparison of multiprocessor scheduling heuristics, (), 243-250 |

[23] | Chen, B., A note on lpt scheduling, Operations research letters, 14, 139-142, (1993) · Zbl 0803.90075 |

[24] | Malloy, B.A.; Lloyd, E.L.; Soffa, M.L., Scheduling DAG’s for asynchronous multiprocessor execution, IEEE transactions parallel and distributed systems, 5, 5, 498-508, (1994) |

[25] | Ahmad I, Kwok Y-K. Optimal and near-optimal allocation of precedence-constrained tasks to parallel processors: defying the high complexity using effective search technique. In: Proceedings of the 1998 international conference on parallel processing, 1998. p. 424-31. |

[26] | Davidović, T.; Hansen, P.; Mladenović, N., Scheduling by vnsexperimental analysis, (), 319-322 · Zbl 1081.90608 |

[27] | Davidović, T.; Hansen, P.; Mladenović, N., Variable neighborhood search for multiprocessor scheduling problem with communication delays, (), 737-741 |

[28] | Davidović T, Crainic TG. New benchmarks for static task scheduling on homogeneous multiprocessor systems with communication delays. Publication CRT-2003-04, Centre de Recherche sur les Transports, Université de Montréal, 2003. |

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.