快速可重构信号处理异构平台下任务调度方法和系统

摘要

本发明属于信号处理技术领域，公开了一种快速可重构信号处理异构平台下任务调度方法和系统，在任务选择阶段完成使用统计学标准筛选出任务以优先级标准选择任务；在处理资源选择阶段选择处理资源要使得该任务或者绑定任务的最早执行完成时间最小。任务调度模块包括：任务选择模块；处理资源选择模块。本发明使用大量异构硬件资源来帮助信号处理应用的加速，同时配合上层的综合开发软件来实现信号处理应用部署的快速可重构和快速迭代。本发明算法是对HEFT和CEFT算法进行了改进，通过使用任务复制结合任务绑定的方法，充分利用处理资源的空闲时间，以一定量的计算开销来抵消更大的通信开销，达到优化整体任务的时间性能和系统资源利用率。

说明书

技术领域

本发明属于信号处理技术领域，尤其涉及一种快速可重构信号处理异构平台下任务调度方法、系统。

背景技术

目前：快速可重构信号处理异构平台利用CPU、DSP、GPU和FPGA等异构处理资源组成大量信号处理的板卡，并将各个板卡集成在机箱中，利用机箱背板上的总线和机箱的交换板进行处理资源之间的数据交互，借助存储器将处理过程中所需的数据和文件进行存储。该平台的综合软件开发环境是平台的软件部分，包括了可视化开发界面，任务调度模块、资源监控模块、配置控制模块、封装模块及通信控制模块等功能模块。任务调度算法是任务调度模块的核心，决定了信号处理应用的性能以及效率。一个信号处理应用通常由多个任务协作完成，任务之间通常包含复杂的依赖关系，通常用DAG(有向无环图)表示。在有向无环图中，节点代表着任务，有向的边代表任务之间的数据依赖关系。任务调度算法就是根据指定优化目标将任务图中的任务分派到合适的计算资源上，并且在保证任务之间的通讯依赖关系的前提下，决定在计算资源上的执行顺序。在我们的场景中，任务调度算法的主要优化目标就是信号处理任务的总体的执行时间，即最早开始执行的任务与最晚完成执行的任务之间的时间差。根据任务的特征(包括任务之间的依赖关系、任务在处理器上的计算开销和任务之间的通信开销)是否提前给定，可将任务调度问题分为静态任务调度和动态任务调度。在我们的平台下，采用静态调度的方法，由于硬件资源通常是固定不变的，同时各种信号处理任务也是由任务组件库提供的，所有我们会基于统计的方法给定这些特征估计值，提供给调度算法使用。针对异构系统中的静态调度问题，主要可划分为基于表的调度、基于聚类的调度、基于任务复制的调度和引导随机搜索调度，较为常见的调度算法有HEFT、CPOP、Lookahead、CEFT等启发式算法被广泛运用到实际的应用中。

通常这种任务调度分为两个阶段，分别为任务选择阶段和处理资源选择阶段。HEFT算法是基于任务的通信开销和计算开销从退出任务节点开始计算所有任务节点的RankU值，以此作为优先级排序的标准，对RankU值进行降序排列，依次调度每个任务到使得该任务最早执行完成时间(EFT)最小的处理资源上。CPOP算法是将关键路径上的任务调度到特定的处理资源上，其余的调度过程和HEFT类似。Lookahead法与HEFT相比的不同之处在于，在处理资源选择阶段使用任务的直接后继任务的最早执行完成时间为标准。CEFT算法是结合了表调度和任务复制的一种调度方法。

由于各个任务之间存在着数据依赖，后继任务必须在它的所有直接前驱任务都执行结束后才能够执行，也就是说它的所有直接前驱任务在执行完毕后，需要将其所依赖的数据传输到该任务所在处理资源中。在传输数据量大、通信带宽较窄、通信开销大的场景下，会使得后继任务有较长时间的等待时延，同时也造成处理资源的一定量的空闲时间，资源利用率较低，如HEFT算法在这方面的缺陷就较为突出。为了充分利用处理资源的空闲时间，利用处理资源的空闲时间来执行部分前驱任务，使用计算开销来抵消更大的通信开销，已达到降低整体任务应用的执行时间，这就是任务复制的方法。但是单纯使用任务复制的方法在存在高通信开销的任务的场景下，性能有待提高。所有本发明针对这些不足，提出了高通信开销任务绑定，并结合任务复制，来提高快速可重构信号处理异构平台下信号处理应用的时间应用。所谓的任务复制就是后继任务为了节省某些前驱任务到该任务的通信开销，拷贝这些前驱任务到该任务所在的硬件处理资源上执行。而高通信开销的任务绑定是将这个任务对捆绑在一起，在这两个任务的前驱任务的数据准备好了后，将该绑定任务对按照某一规则分配同一硬件处理资源上，以此来消除这两个任务直接的高通信开销。

为了满足越来越多的场景中信号处理的实时性需求，同时为了使得开发者能够对部署的信号处理任务进行快速迭代和快速重构，结合了异构硬件加速器(大量的多类型异构计算资源，如CPU、GPU、DSP和FPGA等)和可视化开发、资源虚拟化管理、实时任务调度的综合开发环境的快速可重构信号处理异构平台可以满足上述需求。开发者在可视化软件中部署信号处理应用，通常应用由具有一定数据依赖的多个任务组成，表现为一种DAG(有向无环图)的形式。为了加快信号处理过程以满足实时性需求，如何根据应用的本身的特点和平台中硬件的特性为各个任务分配合适的硬件计算资源的调度算法至关重要。和其他场景不同的是，在该异构平台下硬件资源是充足的，因此调度算法的主要关注的是时间性能。

通过上述分析，现有技术存在的问题及缺陷为：现有技术存在传输数据量大、通信带宽较窄、通信开销大的场景下，会使得后继任务有较长时间的等待时延，同时也造成处理资源的一定量的空闲时间，资源利用率较低。

解决以上问题及缺陷的难度为：为了实现信号处理应用的快速重构和快速部署就需要可视化软件和异构硬件相结合，因为同时涉及软件和硬件。所以如何搭建这样一个快速可重构信号处理平台成为了一个难点。同时面对传输数据量大、通信带宽较窄、通信开销大的场景，如何进行任务调度能尽可能提高信号处理应用的实时性。

解决以上问题及缺陷的意义为：能够加快信号处理应用的快速迭代和快速重构，缩短了应用部署的时间周期。使用本发明提出的任务调度算法能够进一步的加速信号处理应用的整体运行时间，提高应用的实时性。同时也使得我们所使用的异构平台下的硬件资源利用率得到了提高。

发明内容

针对现有技术存在的问题，本发明提供了一种快速可重构信号处理异构平台下任务调度方法和系统。

本发明是这样实现的，一种快速可重构信号处理异构平台下任务调度方法，所述快速可重构信号处理异构平台下在任务选择阶段完成使用统计学标准筛选并绑定高通信开销任务以及优先级标准选择调度任务；在处理资源选择阶段选择处理资源要使得该任务或者绑定任务的最早执行完成时间最小。

使用w

进一步，在任务选择阶段使用的优先级标准是

进一步，在处理资源选择阶段的标准是选择的处理资源要使得该任务的最早执行完成时间EFT最小，EFT可由如下公式进行计算EFT(j)＝w

进一步，所述快速可重构信号处理异构平台下任务调度方法调度前准备，具体包括：基于平台所提供的硬件处理资源和系统任务库所提供的信号处理任务，使用统计方法和经验方法，预估出每个任务在不同硬件处理资源上的计算开销值，w

进一步，所述快速可重构异构平台下任务调度方法执行调度，具体包括：

(1)解析DAG应用图，寻找入口任务EntryTask和出口任务ExitTask，并将EntryTask赋值给就绪队列ReadyQueue；

(2)统计信号处理应用的任务之间的通信开销，计算均值μ，和标准差σ，使用高斯分布模型的“3σ原则”筛选出通信开销落在2σ之外的上区间的任务对，即筛选出满足c

(3)计算所有任务的RankU值，以此作为任务选择时的优先级标准，RankU值越大优先级越高；

(4)当就绪队列ReadyQueue非空时，执行步骤(5)和(6)；当就绪队列ReadyQueue为空时执行步骤(7)；

(5)判断绑定列表List中的任务对是否存在于就绪队列ReadyQueue中，如果存在对该任务进行调度，将该任务分配到使得任务对中的后继任务最早执行完成时间EFT最小的处理资源上，从就绪队列ReadyQueue中和绑定列表List删除该任务对，并将新的就绪任务加入就绪队列ReadyQueue中，并返回步骤(4)；如果绑定列表List中的任务对不存在某一对在就绪队列ReadyQueue中，则执行步(6)；

(6)选择就绪队列ReadyQueue中最大的RankU对应的任务进行调度，分别考虑不复制前驱任务和复制前驱任务两种情况，选择两种情况中使得该任务最早执行完成时间EFT最小的处理资源执行该任务，将该任务从就绪队列ReadyQueue删除，并将新的就绪任务加入就绪队列ReadyQueue中，并返回步骤(4)；

(7)得到完整的任务调度方案，结束调度。

本发明的另一目的在于提供一种快速可重构信号处理异构平台系统，所述快速可重构信号处理异构平台系统用于实现所述的快速可重构异构平台下任务调度方法。快速可重构信号处理异构平台系统利用CPU、DSP、GPU和FPGA等异构处理资源组成大量信号处理的板卡，并将各个板卡集成在机箱中，利用机箱背板上的总线和机箱的交换板进行处理资源之间的数据交互，借助存储器将处理过程中所需的数据和文件进行存储。该平台的综合软件开发环境是平台的软件部分，包括了可视化开发界面，任务调度模块、资源监控模块、配置控制模块、封装模块及通信控制模块等功能模块。

结合上述的所有技术方案，本发明所具备的优点及积极效果为：本发明结合任务复制和任务绑定的方法，充分利用处理资源的空闲开销，以一定量的计算开销来抵消更大通信开销，加快整体任务的执行过程，可以很好的满足实时性需求。相比于常见的同类型调度算法，本发明所提出的算法具有更好的时间性能。

本发明中的系统使用大量异构硬件资源来信号处理应用的加速，同时配合上层的综合软件来实现应用部署的快速可重构和快速迭代。本发明算法是对HEFT和CEFT算法的进行了改进，通过使用任务复制加任务绑定的方法，充分利用处理资源的空闲时间，以一定量的计算开销来抵消更大的通信开销，达到优化整体任务的时间性能和系统资源利用率。

附图说明

为了更清楚地说明本申请实施例的技术方案，下面将对本申请实施例中所需要使用的附图做简单的介绍，显而易见地，下面所描述的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下还可以根据这些附图获得其他的附图。

图1是本发明任务调度模块的组成部分，1、任务选择模块；2、处理资源选择模块。

图2是本发明实施例提供的快速可重构信号处理异构平台系统的结构示意图；

图3是本发明实施例提供的快速可重构信号处理异构平台下任务调度方法流程图。

图4是本发明实施例提供的仿真结果示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

针对现有技术存在的问题，本发明提供了一种快速可重构异构平台下任务调度方法、系统、计算机设备，下面结合附图对本发明作详细的描述。

本发明提供的快速可重构异构平台下任务调度方法业内的普通技术人员还可以采用其他的步骤实施。

如图1所示，本发明提供的快速可重构异构平台下任务调度模块包括：

任务选择模块1，用于在任务选择阶段使用的优先级标准选择任务或者绑定任务；

处理资源选择模块2，用于在处理资源选择阶段选择处理资源要使得该任务或绑定任务的最早执行完成时间最小。

如图2所示，本发明提供的快速可重构异构信号处理平台的系统架构如图，是由软件部分和硬件部分组成，硬件部分由FPGA、DSP、GPU和CPU等异构硬件组成，软件部分将底层的硬件虚拟化为统一的逻辑资源，上层软件包含有实时调度模块、配置控制模块、资源管理模块、状态监控模块以及可视化的开发界面和显控界面。开发者可以以图形化的方式快速对信号处理应用进行部署和重构。

下面结合附图3对本发明的技术方案作进一步的描述。

本发明中的任务调度算法是针对快速可重构异构信号处理平台，加速有向无环图类信号处理应用的一种调度算法。调度的过程可以分为任务选择阶段和处理资源选择阶段。使用w

在任务选择阶段使用的优先级标准是

在处理资源选择阶段的标准是选择的处理资源要使得该任务的最早执行完成时间EFT最小，EFT可由如下公式进行计算EFT(j)＝w

本发明的调度算法具体步骤如下：

第一步，调度前准备，具体包括：基于平台所提供的硬件处理资源和系统任务库所提供的信号处理任务，使用统计方法和经验方法，预估出每个任务在不同硬件处理资源上的计算开销值，w

第二步，执行调度，具体包括：

(1)解析DAG应用图，寻找入口任务EntryTast和出口任务ExitTask，并将ETtryTask赋值给就绪队列ReadyQueue。

(2)统计信号处理应用的任务之间的通信开销，计算均值μ，和标准差σ，使用高斯分布模型的“3σ原则”筛选出通信开销落在2σ之外的上区间的任务对，即筛选出满足c

(3)计算所有任务的RankU值，以此作为任务选择时的优先级标准，RankU值越大优先级越高；

(4)当就绪队列ReadyQueue非空时，执行步骤(5)和(6)；当就绪队列ReadyQueue为空时执行步骤(7)。

(5)判断绑定列表List中的任务对是否存在于就绪队列ReadyQueue中，如果存在对该任务进行调度，将该任务分配到使得任务对中的后继任务最早执行完成时间EFT最小的处理资源上，从就绪队列ReadyQueue中和绑定列表List删除该任务对，并将新的就绪任务加入就绪队列ReadyQueue中，并返回步骤(4)；如果绑定列表List中的任务对不存在某一对在就绪队列ReadyQueue中，则执行步(6)。

(6)选择就绪队列ReadyQueue中最大的RankU对应的任务进行调度，分别考虑不复制前驱任务和复制前驱任务两种情况，选择两种情况中使得该任务最早执行完成时间EFT最小的处理资源执行该任务，将该任务从就绪队列ReadyQueue删除，并将新的就绪任务加入就绪队列ReadyQueue中，并返回步骤(4)。

(7)得到完整的任务调度方案，结束调度。

下面结合仿真对本发明的技术效果作详细的描述。

为了评估本发明的任务调度算法相比一些常见的算法的性能差异，对其进行仿真，本仿真中主要对比了经典的HEFT算法以及基于任务复制的CEFT算法。仿真中，整体任务的执行时间，性能参数为makespan，其定义为：

makespan＝max{AFT(ExitTask)}

调度长度比SLR，其定义为：

在我们的仿真中，使用平均调度长度比作为对比三种调度算法的性能指标。从仿真结果图可以看出，在任务个数相同的情况下，本发明所提算法具有较好的平均调度长度比性能。具体的相比于经典的HEFT算法，所提算法的性能有显著的优化，这得益于任务复制和任务绑定的共同作用，大幅度降低了任务间的通信开销。相比于具有任务复制的CEFT算法，所提算法的性能也得到了一定提高，这得益于所提算法对高通信开销任务对的绑定，消除了这类任务对之间的通信开销。

应当注意，本发明的实施方式可以通过硬件、软件或者软件和硬件的结合来实现。硬件部分可以利用专用逻辑来实现；软件部分可以存储在存储器中，由适当的指令执行系统，例如微处理器或者专用设计硬件来执行。本领域的普通技术人员可以理解上述的设备和方法可以使用计算机可执行指令和/或包含在处理器控制代码中来实现，例如在诸如磁盘、CD或DVD-ROM的载体介质、诸如只读存储器(固件)的可编程的存储器或者诸如光学或电子信号载体的数据载体上提供了这样的代码。本发明的设备及其模块可以由诸如超大规模集成电路或门阵列、诸如逻辑芯片、晶体管等的半导体、或者诸如现场可编程门阵列、可编程逻辑设备等的可编程硬件设备的硬件电路实现，也可以用由各种类型的处理器执行的软件实现，也可以由上述硬件电路和软件的结合例如固件来实现。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，都应涵盖在本发明的保护范围之内。