A duplication heuristic for static scheduling of tasks on distributed memory multiprocessors
作者:
Yeh‐Ching Chung,
Chia‐Cheng Liu,
Jen‐Shiuh Liu,
期刊:
Journal of the Chinese Institute of Engineers
(Taylor Available online 1995)
卷期:
Volume 18,
issue 6
页码: 845-855
ISSN:0253-3839
年代: 1995
DOI:10.1080/02533839.1995.9677752
出版商: Taylor & Francis Group
关键词: distributed memory multiprocessors;scheduling length;grain size;list scheduling algorithms;task duplication
数据来源: Taylor
摘要:
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 duplicating 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 medium‐grain and fine‐grain DAGs, BTDH produces better scheduling length than DSH.
点击下载:
PDF (853KB)
返 回