Bounding the execution time of parallel applications on unrelated multiprocessors

Heterogeneous multiprocessors, that consist of processor types with different execution capabilities, are critical today, and in future, to offer high performance and high energy efficiency. In order to use them in hard real-time systems to support parallel processing, a tight estimation of the upper bound on the completion time (WCET) of parallel applications is needed. This paper presents, for the first time, a closed-form solution for the calculation of the WCET for task-based parallel applications modeled as directed acyclic-graphs (DAG) using the general unrelated multiprocessor model that is capable of modeling a wide range of heterogeneous multiprocessor platforms. The paper contributes with a polynomial time algorithm to calculate the WCET (i.e., makespan) for the unrelated model. In addition, it presents simulation results that are based on modeling a set of representative OpenMP task-based parallel applications from the BOTS benchmark suite