DBEFT: A Dependency-Ratio Bundling Earliest Finish Time Algorithm for Heterogeneous Computing

Tao Li, Dingyuan Cao, Ye Lu, Tehui Huang, Chengjun Sun, Qiankun Dong, Xiaoli GongIEEE Access 2019 · OpenReview

Abstract

Performance effective task scheduling algorithms are essential for taking advantage of the heterogeneous multi-processor in heterogeneous computing environments. In this paper, we present a task scheduling algorithm named as Dependency-ratio Bundling Earliest Finish Time (DBEFT). DBEFT is a list-based scheduling algorithm combined with task duplication, which can achieve high performance and low time complexity simultaneously. DBEFT selects the task from the perspective of extending parallelism between tasks instead of giving priorities to tasks on the critical path. Also, DBEFT reduces communication cost by adopting a bundling scheduling strategy. The experiments were conducted on both random graph set and real-world applications, and the results show that DBEFT obtained significant performance improvement, outperforming CEFT by 15%, PEFT by 30% and HEFT 33% in terms of SLR respectively.

Introduction

In modern heterogeneous computing environments, applications are typically modeled as Directed Acyclic Graphs (DAGs), where nodes represent tasks and edges represent data dependencies. The primary objective of task scheduling is to map these tasks onto a set of heterogeneous processors to minimize the total execution time, or makespan. Traditional list-based scheduling algorithms, such as the Heterogeneous Earliest Finish Time (HEFT), often focus on the "critical path"—the longest sequence of dependent tasks. However, this approach can overlook opportunities to maximize parallelism and may fail to mitigate significant communication overheads between processors.

Methodology

The proposed DBEFT algorithm addresses these limitations through three core innovations:

1. Task Dependency Ratio (TDR)

Unlike traditional methods that prioritize tasks based on their distance to the exit node, DBEFT utilizes a Task Dependency Ratio (TDR). This metric identifies "bottleneck" tasks that, upon completion, enable the highest number of successor tasks to begin execution. By prioritizing these high-TDR tasks, the algorithm effectively increases the system's overall parallelism.

2. Bundling Strategy

Communication costs often dominate execution time in distributed systems. DBEFT identifies "ultra-long" communication edges—those with data transfer costs in the top 5% of the distribution. These task pairs are "bundled" and "frozen" together, ensuring they are scheduled on the same processor. This strategy eliminates the associated communication delay entirely.

3. Task Duplication

To further reduce processor idle time, DBEFT employs selective task duplication. If the time required to re-calculate a predecessor's result on a local processor is less than the time required to wait for that result to be transmitted over the network, the algorithm duplicates the predecessor task.

A sample DAG and its corresponding computation time matrix for three processors (P1, P2, P3).

Experimental Evaluation

The performance of DBEFT was evaluated using a massive dataset of over 750,000 synthetic random graphs generated via daggen, as well as real-world application graphs like Gaussian Elimination and Fast Fourier Transform (FFT).

Performance Metrics

The study introduced two new metrics alongside standard ones:

  • Scheduling Length Ratio (SLR): Measures the ratio of the actual makespan to the lower bound of execution time.
  • Average Idle Time (AIT): Quantifies the efficiency of processor utilization.
  • Redundant Computing Ratio (RCR): Tracks the overhead introduced by task duplication.

Results and Discussion

Experimental results demonstrate that DBEFT significantly outperforms state-of-the-art algorithms. In terms of SLR, DBEFT achieved improvements of 15% over CEFT, 30% over PEFT, and 33% over HEFT. Furthermore, as task complexity increased, DBEFT maintained an AIT of less than one-third of its competitors, indicating superior hardware utilization. While the RCR is higher due to duplication, the trade-off results in a substantially lower overall makespan.

Conclusion

DBEFT provides a robust solution for task scheduling in heterogeneous systems by shifting focus from critical path length to parallelism expansion and communication cost reduction. While currently a static scheduling model, its principles of task bundling and dependency-ratio prioritization offer a promising foundation for future dynamic or energy-aware scheduling frameworks.

Summary updated

Abstract

Performance effective task scheduling algorithms are essential for taking advantage of the heterogeneous multi-processor in heterogeneous computing environments. In this paper, we present a task scheduling algorithm named as Dependency-ratio Bundling Earliest Finish Time (DBEFT). DBEFT is a list based scheduling algorithm combined with task duplication, which can achieve high performance and low time complexity simultaneously. DBEFT selects the task from the perspective of extending parallelism between tasks instead of giving priorities to tasks on the critical path. Also, DBEFT reduces communication cost by adopting a bundling scheduling strategy. The experiments were conducted on both random graph set and real-world applications, and the results show that DBEFT obtained significant performance improvement, outperforming CEFT by 15%, PEFT by 30% and HEFT 33% in terms of SLR respectively.
BibTeX
@inproceedings{li2019dbeft,
  author = {Tao Li and Dingyuan Cao and Ye Lu and Tehui Huang and Chengjun Sun and Qiankun Dong and Xiaoli Gong},
  title = {{DBEFT: A Dependency-Ratio Bundling Earliest Finish Time Algorithm for Heterogeneous Computing}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=IzQZQ6Ntx},
}

Loading related content...

Figure