Analysis of DAG Structure and HEFT Scheduling Efficiency Across Graph Sets

Abstract

Abstract

This study investigates the relationship between Directed Acyclic Graph (DAG) structural properties and scheduling efficiency under the Heterogeneous Earliest Finish Time (HEFT) algorithm in heterogeneous computing environments.Despite HEFT's widespread adoption as a benchmark scheduling heuristic, systematic characterization of how graph topology influences its performance across diverse workload regimes remains limited.Using a comprehensive benchmark of 300 DAG workflows spanning three complexity classes (9, 23, and 29 tasks), we employ multivariate statistical techniques including Principal Component Analysis, K-means clustering, hierarchical clustering, multiple regression, and Random Forest modeling to identify latent structural dimensions governing execution behavior.Results reveal three dominant variance components that explain 97.6% of the total variability: graph scale and computational complexity (PC1: 47.7%), communication intensity (PC2: 22.9%), and execution heterogeneity (PC3: 18.1%).Clustering analysis validates three distinct workload regimes with strong statistical separation (Silhouette score = 0.612).Critically, regression and feature importance analyses demonstrate that critical path length overwhelmingly dominates execution time (importance = 0.974), while total workload and graph size contribute secondarily.HEFT efficiency varies substantially across clusters, ranging from 0.771 (small graphs) to 0.408 (large graphs), with communication heavy and deep dependency structures exhibiting significant performance degradation.These findings support the development of Cluster Aware HEFT (CA-HEFT), an adaptive scheduling architecture that pre classifies incoming workflows and applies tailored prioritization and processor selection strategies.This research contributes an empirical taxonomy of DAG workloads, identifies critical path as the principal performance bottleneck, and provides a foundation for structure aware, adaptive scheduling in heterogeneous distributed systems.