基于异构多核的多类型DAG任务的响应时间分析

Response Time Analysis of Typed DAG Tasks on Heterogeneous Multi-Cores

由于异构多核并行架构能够利用不同体系结构的优势来提供更高的性能,近年来受到了广泛的关注.本文是对异构多核平台上多类型DAG(Directed Acyclic Graph)任务的最坏响应时间进行分析.多类型DAG是一种任务内并行模型,其中包含不同类型的节点,每个节点必须在其指定类型的处理器内核上执行.传统的研究在分析多类型DAG任务的最坏响应时间时高估了节点受到的阻塞,导致得到的响应时间上界过于悲观.为此,我们首先提出了一种新的多类型DAG任务转化算法,该算法通过将节点拆分成单位节点,并在不破坏原有依赖关系的基础上按照单位节点分配策略在单位节点之间增加新的边,构成一个新的多类型DAG任务,从而减少每个节点可能并行执行的节点个数,降低被阻塞时间.在该转化算法的基础上,我们提出了一个新的最坏响应时间分析方法,用来验证支持异构并行计算的多类型DAG任务的可调度性.通过对随机生成的多类型DAG任务进行的实验表明,我们提出的最坏响应时间上界比现有方法的精确度提高20%以上.

Heterogeneous multi-cores and parallel architectures have recently gained much attention owing to utilize the strength of different architectures for offering higher performance.This paper analyzes the worst-case response time of typed DAG tasks on heterogeneous multi-core platforms,i.e.,a typed DAG task contains different types of vertices,and the workload of each vertex must execute on its particular type of cores.Binding code snippets of a program to a specific type of cores is a common operation in heterogeneous multi-cores scheduling and can be easily implemented in mainstream parallel programming frameworks and operating systems.In recent years,scholars domestic and overseas have made great progress in the research of heterogeneous parallel task scheduling with real-time constraints.However,there are still many problems with the existing research results.The traditional research overestimated the interference of the vertices in the DAG when analyzing the worst-case response time of typed DAG tasks,leading to the upper bound of pessimistic response time.For this reason,we propose a typed DAG transformation algorithm,which can obtain a new DAG task by adding extra edges on the basis of retaining the dependency between the original vertices,so as to reduce the number of vertices that can be executed in parallel for each vertex and reduce the possibility of each vertex being blocked.The main idea of the algorithm is to divide vertices into multiple unit-nodes and assign unit-nodes to different sets of parallel unit-nodes according to the principle of minimizing the increment of blocking time.When all unit-nodes in the DAG are allocated,the conversion of DAG tasks can be realized by connecting adjacent sets of parallel unit-nodes with edges.Based on this transformation algorithm,we propose a new worst-case response time analysis method to verify the schedulability of typed DAG tasks that support heterogeneous computing.A comparison of randomly generated DAG tasks shows that the accuracy of our new worst-case response time is more than 20%higher than the existing bounds.Based on the actual heterogeneous hardware device platform,we carried out experiments on the actual typed DAG task to evaluate the correctness of the new worst-case response time upper bound DTA proposed by us in the practical application.The experimental results show that the theoretical time obtained by our worst-case response time analysis method is always greater than the actual running time,so the new response time upper bound DTA proposed by us is safe and reliable.The research in this paper has a positive significance to improve the ability to compute the worst-case response time of the typed DAG task in heterogeneous multicores platform.Our future work will focus on extending the existing response time analysis methods to analyze the response time upper bound of multiple typed DAG tasks.At the same time,we will study a more efficient typed DAG task transformation algorithm,which can realize DAG task transformation in a shorter time,and the result is approximate to the upper bound of response time proposed by us.