Scheduling DAGs with random parallel tasks on binarily partitionable systems

摘要

We investigate the problem of scheduling dags with parallel tasks on binarily partitionable systems by analyzing α_n(LL), the average-case performance ratio of the level-by-level (LL) scheduling algorithm, where n is the number of tasks. It is shown that for arbitrary probability distributions of task parallelisms and task execution times, the asymptotic average-case performance ratio of algorithm LL in scheduling parallel computations with wide dags is α_∞ (LL) = 1. In particular, for exponential distributions of task execution times, the average-case performance ratio of LL in scheduling iterative computations, complete trees, partitioning algorithms and diamond dags is α_n(LL) = 1 + O(log n), 1 + O((log n)~2), 1 + O((log n)~2) and 1 + O((log n)~2 / n~(1/2)), respectively.