.png){kind=icon}
返回
A Novel Task-Duplication Based Clustering Algorithm for Heterogeneous Computing Environments
.png){kind=icon}
PRE
AI
DOI：10.1109/TPDS.2018.2851221.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
As a crucial task in heterogeneous distributed systems, DAG-scheduling models a scheduling application with a set of distributed tasks by a Direct Acyclic Graph (DAG). The goal is to assign tasks to different processors so that the whole application can finish as soon as possible. Task Duplication-Based (TDB) scheme is an important technique addressing this problem. The main idea is to duplicate tasks on multiple machines so that the results of the duplicated tasks are available on multiple machines to trade computation time for communication time. Existing TDB algorithms enumerate and test all possible duplication candidates, and only keep the candidates that can improve the overall scheduling. We observe that while a duplication candidate is ineffective at the moment, after other duplications have been applied, this ineffective duplication candidate can become effective, which in turn can cause other ineffective duplications to become effective. We call this phenomenon the chain reaction of task duplication. We propose a novel Task Duplication based Clustering Algorithm (TDCA) to improve the schedule performance by utilizing duplication task more thoroughly. TDCA improves parameter calculation, task duplication, and task merging. The analysis and experiments are based on randomly generated graphs with various characteristics, including DAG depth and width, communication-computing cost ration, and variant computation power of processors. Our results demonstrate that the TDCA algorithm is very competitive. It improves the schedule makespan of task duplication-based algorithms for heterogeneous systems for various communication-computing cost ratios.
Keyword:
Task duplication
clustering and merging
optimal scheduling
heterogeneous environment
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
5.2K
被引数:
1.1W
机构
暂无机构信息
引用论文
.png){kind=icon}
Tin(IV)oxide supported noble metal catalysts for the carbon monoxide oxidation at low temperatures
PREAI
分享收藏分享收藏
查看更多内容