Branch-and-bound task allocation with task clustering-based pruning

檔案

日期

2004-11-01

類型

期刊名稱

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING

卷期與頁次

第 64 卷第 11 期,頁 1223–1240

ISSN

0743-7315

語言

英文

摘要

We propose a task allocation algorithm that aims at finding an optimal task assignment for any parallel programs on a given machine configuration. The theme of the approach is to traverse a state-space tree that enumerates all possible task assignments. The efficiency of the task allocation algorithm comes from that we apply a pruning rule on each traversed state to check whether traversal of a given sub-tree is required by taking advantage of dominance relation and task clustering heuristics. The pruning rules try to eliminate partial assignments that violate the clustering of tasks, but still keeping some optimal assignments in the future search space. In contrast to previous state-space searching methods for task allocation, the proposed pruning rules significantly reduce the time and space required to obtain an optimal assignment and lead the traversal to a near optimal assignment in a small number of states. Experimental evaluation shows that the pruning rules make the state-space searching approach feasible for practical use. (C) 2004 Published by Elsevier Inc.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Ma, Y., Chen, T., & Chung, C. (2004). Branch-and-bound task allocation with task clustering-based pruning. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 64(11), 1223–1240. https://doi.org/10.1016/j.jpdc.2004.08.002

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/25668