directed acyclic task graph scheduling for heterogeneous computing systems by dynamic critical path duplication algorithm

directed acyclic task graph scheduling for heterogeneous computing systems by dynamic critical path duplication algorithm

;Yin Fei;Du Xiaoli;Jiang Changjun;Deng Rong
journal of algorithms & computational technology 2009 Vol. 3 pp. -
104
fei2009journaldirected

Abstract

This paper addresses the static scheduling of a directed acyclic task graph (DAG) on a heterogeneous, bounded set of distributed processors to minimize the makespan. We first derive the lower and upper bounds on the makespan of assigning a given directed acyclic task graph on heterogeneous processors by deferent scheduling strategies. Based on the analysis, we present a new heuristic, known as Heterogeneous Dynamic Critical Path Duplication (HDCPD), for scheduling DAG on a set of heterogeneous processors. HDCPD assigns the tasks on the dynamic critical path to the suitable processors which minimize the earliest finish time for them, combining insertion-based scheduling and task duplication techniques. The comparison study by simulation on Simgrid, based on randomly generated DAG, shows that HDCPD surpasses previous approaches in terms of both quality and cost of schedules, which are mainly presented with schedule length, frequency of best result, and scheduling time metrics.

Citation

ID: 130735
Ref Key: fei2009journaldirected
Use this key to autocite in SciMatic or Thesis Manager

References

Blockchain Verification

Account:
NFT Contract Address:
0x95644003c57E6F55A65596E3D9Eac6813e3566dA
Article ID:
130735
Unique Identifier:
10.1260/174830109787914001
Network:
Scimatic Chain (ID: 481)
Loading...
Blockchain Readiness Checklist
Authors
Abstract
Journal Name
Year
Title
5/5
Creates 1,000,000 NFT tokens for this article
Token Features:
  • ERC-1155 Standard NFT
  • 1 Million Supply per Article
  • Transferable via MetaMask
  • Permanent Blockchain Record
Blockchain QR Code
Scan with Saymatik Web3.0 Wallet

Saymatik Web3.0 Wallet