A DUPLICATION HEURISTIC FOR STATIC SCHEDULING OF TASKS ON DISTRIBUTED MEMORY MULTIPROCESSORS

摘要

A task duplication heuristic, DSH, was proposed in [11]. The underlying concept of the task duplication heuristic is duplicating some tasks on processors such that the earliest start time of tasks on processors can be reduced, that is, tasks on processors can be executed sooner. This leads to a better scheduling length. In this paper, we propose a more general task duplication heuristic,bottom-up top-down duplication heuristic (BTDH), for static scheduling of directed-acyclic graphs (DAGs) on distributed memory multiprocessors. The key difference between BTDH and DSH is the method used for dupli-cating tasks. BTDH allows tasks to be duplicated on processors even though the duplication of tasks will temporarily increase the earliest start time of some tasks. DSH only allows those duplications which will reduce the earliest start time of tasks. Simulation results show that, for coarse-grain DAGs, the scheduling length of BTDH is almost the same as the scheduling length of DSH. However, for me-dium-grain and fine-grain DAGs, BTDH produces better scheduling length than DSH.