高级检索

    异构多核全局限制性可抢占并行任务可调度分析

    Schedulability Analysis of Parallel Tasks Under Global Limited Preemption on Heterogeneous Multi-Cores

    • 摘要: 异构多核平台可以利用不同类别体系结构的处理器来执行特定任务,从而达到提高性能和降低功耗的目的. 然而,向大规模异构平台迁移极其困难,且大规模的、必要的程序并行会导致软件调度的复杂度. 虽然,基于有向无环图(directed acyclic graph, DAG)并行任务模型已有相关的研究工作,但是基于DAG任务模型的限制性可抢占的调度策略研究仍存在不足. 鉴于此,主要讨论了DAG任务在异构平台上进行全局固定优先级限制性可抢占调度时的最差响应时间(worst case response time,WCRT)分析,对并行任务的每个结点可用的处理器资源进行了一定的限制,即只能执行在规定类型处理器上的任务. 基于最新的单分类并行任务的可调度性分析,提出了多个并行任务的可调度性分析. 进一步,提出了高优先级任务的干涉量与低优先级任务的阻塞量的计算方法;结合最新的分类并行任务的任务内干涉计算方法,最终提出了一种伪多项式的分析方法. 实验结果表明,提出的算法能够在合理的时间范围内得到任务集可调度性的分析结果,且任务集的接受率随各个参数的变化符合预期.

       

      Abstract: The heterogeneous multi-core architecture takes advantage of the strengths of different architectures to execute specific types of workloads and is typically more energy-efficient and faster. However, it is very difficult to migrate to large-scale heterogeneous platforms, and large-scale parallelism will lead to a high level of complexity in software scheduling. Although there have been related studies on the DAG task model, the research on the limited preemption scheduling strategy based on the DAG task model still has some shortcomings. In this paper, we present a worst-case response time (WCRT) analysis method for typed DAG tasks on heterogeneous multi-cores under global fixed priority limited preemption scheduling, in which each vertex of the DAG is allowed to execute on only one type of core. We present a method for analyzing the schedulability of multiple DAG tasks under global fixed-priority preemption scheduling based on the latest schedulability analysis of a single DAG task. First, a method to analyze the upper bound workload of higher priority tasks is proposed. Following that, a method for analyzing the upper bound workload of lower priority tasks is proposed. A pseudo-polynomial analysis method is proposed for analyzing the upper bound of WCRT of each typed DAG task based on the state-of-the-art method for single typed DAG task analysis. The results of our experiments with randomly generated workloads indicate that our proposed method is capable of analyzing a task set in a reasonable amount of time. In addition, the results of the scheduler meet all expectations.

       

    /

    返回文章
    返回