Efficient Response Time Bound for Typed DAG Tasks

Heterogeneous multi-core platforms have been used in many fields to meet the increasing requirement of computation. In this paper, we study the response time bound of typed DAG (directed acyclic graph) tasks on heterogeneous multi-core platforms. The existing bound has exponential time complexity. In this paper, we propose a new bound that can be computed with complexity
$O(\vert V\vert +\vert E\vert)$
and is only slightly larger than the state-of-the-art. Experiments demonstrate that the computation of our bound is significantly more efficient than the existing bound and our bound has almost the same tightness as the existing bound.