分层异构信号处理平台调度方法研究

李 娜，高 博，谢宗甫

(战略支援部队信息工程大学 信息系统工程学院,河南 郑州 450000)

随着无线通信技术的发展，愈加复杂的通信模式对信号处理平台实时性、准确性、高效性的要求越来越高。因此，研究一种具有开放性、可扩展、可移植的智能异构信号处理平台已成为未来信号处理平台的发展趋势。不同类型的信号处理平台使用的高性能处理器有所差异，软硬件资源的耦合程度较大，应用任务可移植性较差，导致信号处理平台研发周期长且通用性较差。软件无线电(Software Defined Radio，SDR)及认知无线电概念的提出和软件通信体系架构(Software Communication Architecture，SCA)的不断发展，使得在开放性通用平台上开发可升级、可复用、可重配置的软硬件体系架构逐渐成为研究热点。弗吉尼亚理工大学于2006年提出了基于SCA标准的OSSIE架构，该结构可以在异构平台上进行互操作，同时处理多个信号任务[1]。加泰罗尼亚大学基于PHAL开发的ALOE架构则具有良好的实时性[2]。认知软件无线电框架能够最大限度利用平台系统软硬件资源，其综合且开放的软硬件体系架构为分层异构信号处理(Layered Heterogeneous Signal Processing，LHSP)平台的高性能研究提供了参考。

分层异构信号处理平台复杂、庞大的软硬件资源使得针对软硬件体系架构的研究成为平台的关键部分，而复杂系统的资源管理和信号任务的动态到达又增加了问题的复杂性，因此任务调度策略是平台实现高性能的关键。异构计算环境下的任务调度计算复杂度较高，是一个NP(Non-Deterministic Polynomial Complete Problems)完全问题。目前任务调度多建立有向无环图(Directed Acyclic Graph，DAG)模型来表述，通过节点和有向边为任务调度算法提供简单直观的描述。大量有关DAG任务的调度方法已被提出。这些方法所采用的调度技术和应用场景各有不同，其中一些算法已经被成功应用到异构计算系统中，例如异构最早完成时间(Heterogeneous-Earliest-Finish-Time，HEFT)、动态优先级调度(Dynamic Level Scheduling，DLS)等。文献[3]提出的智能并行蚁群任务调度策略，通过改进蚁群搜索方式，有效提高了异构系统中大规模并行计算任务的执行效率。文献[4]提出基于优先队列划分的调度算法，动态的队列划分方法有效减少了异构系统任务的完成时间。随着人工智能技术的快速发展，机器学习算法、人工神经网络[5]等在异构系统中得到了广泛的应用。文献[6]提出的树形调度算法，以二叉树的形式对集群资源进行划分，平衡了硬件加速器负载并提高了资源利用率。基于人工神经网络、基于模型并行的多层感知机等方法，将机器学习应用在嵌入式异构系统中，提高了平台开发速度。单一的任务调度算法虽然在一定程度上改善了任务调度效率，但该算法本身存在的不足(例如蚁群算法前期收敛缓慢且后期易陷入局部最优，动态队列划分算法复杂度高等)。此外，单一的任务调度算法在提高平台任务处理效率时易产生瓶颈，无法满足用户对平台高性能的要求。因此本文提出了组合优化算法的概念，即将性能各异的调度算法以一定的方式结合，进行优劣互补以满足调度目标的需求。

1 LHSP平台调度策略

1.1 LHSP平台

多层异构信号处理平台涉及的软硬件资源庞大，通过构建硬件体系架构和软件体系架构对资源进行系统的管理，有利于描述和拓展。硬件资源架构由ATCA、VPX、CPCI等不同的总线标准和通信协议定义的平台构成，根据其异构性、差异性、多样性、层级性的特点，将其划分为系统域、域、平台、板卡、处理器[7]。多个不同的域互联形成系统域，每个域由多个平台构成，每个平台内包含多个板卡，板卡中嵌入具有不同处理速度、结构、功能的高性能处理器。在层与层之间通过相应管理模块的IP和MAC地址实现互联互通。软件体系架构如图1所示，其由硬件平台层、操作系统层、驱动抽象层、核心框架层、管理服务层和应用层构成。在硬件平台层采用了兼容性强且可扩展的硬件架构ATCA(包括CPU、GPU、DSP、FPGA等处理器)和VPX等高速串行总线。操作系统层和驱动抽象层为上层提供统一接口，达到屏蔽底层硬件之间差异的目的，也体现了层级划分的思想。在核心框架层，利用容器技术形成了统一、标准的任务调度模式，屏蔽不同处理器间的差异。应用层包含雷达、短波、卫星等多种应用，其以组件的形式进行调度。平台软硬件架构的层次型设计实现了平台软硬件解耦合，满足了组件的可移植、跨平台操作等需求[8]。

图1 分层异构信号处理平台软件体系架构

1.2 调度算法分类和归纳

任务调度的难点在于将节点分配到目标系统的处理器上。在满足系统资源约束条件的前提下，需要选择合适的调度算法将到达的任务队列进行合理地规划和映射，使该平台下的处理器系统拥有高效的计算性能，从而满足预期的调度目标。本文对已有的调度策略按照不同方式进行了分类，图2为各分类算法间的关系拓扑图，体现了不同分类算法间的关系。

图2 算法分类拓扑图

本文按照调度任务类型、调度系统目标、调度过程进行分类，具体如下：

(1)根据任务间是否关联或是否存在优先约束关系，将任务分为独立任务和非独立(关联)任务。虚拟专家(Virtual Savant，VS)[9]是一种基于机器学习，适用于解决独立任务调度问题的优化算法。在传统调度方法中，Min-min、Sufferage等在独立任务调度问题中应用较为广泛。关联任务间存在一定的内部或外部数据依赖关系，调度算法可以概括为Abjtnad等划分的BNP、UNC、APN等算法。关联任务[10]通常采用DAG图来描述任务间关联性及约束关系；

(2)任务调度可以根据任务在划分阶段是否离线被分为静态调度和动态调度[11]。静态调度也被定义为预调度，即在分配给硬件处理器资源前就已经确定了任务的划分，形成了基本的调度方案。而动态调度的任务划分是随调度环境和任务依赖关系的动态变化情况实时决策的，目的是平衡处理器间的工作负载。典型的动态调度算法包括最短时间优先算法、最小松弛度优先算法[12]等。但动态调度方法存在额外的任务计算开销，导致总的运行开销较大，且时间复杂度较高；

(3)根据搜索过程进行元启发式(准随机调度)和经典启发式调度的划分。元启发式在搜索最优解的过程中具有导向性，结合局部最优解迭代产生的新结果作为下次迭代的判决[13]。目前使用较为广泛的列表搜索算法(List Search，LS)、遗传算法(Genetic Algorithm，GA)、模拟退火(Simulated Annealing，SA)、蚁群算法(Ant Colony Optimization，ACO)等智能寻优算法都可以归为准随机调度。经典启发式调度算法可以根据调度被策略分为表调度、基于任务聚类、基于任务复制等算法；

(4)根据调度结果是否需要满足多个优化目标来区分单目标优化和多目标优化。任务调度算法的优化目标包括调度长度、负载均衡、吞吐量、能耗、通信计算比率等。单目标优化算法，例如先来先服务(Fist In Fist Out，FIFO)算法、短作业优先算法(Short Job First，SJF)等求解相对简单，通常存在唯一全局最优解。而多目标优化得到的是最优解的集合，求解过程相对复杂；

(5)根据任务调度过程中是否存在任务优先级动态抢占来划分抢占式调度和非抢占式调度。抢占式调度中任务的优先级类型被划分为静态优先级和动态优先级[14]。静态优先级是指在整个调度过程中任务的优先级程度保持不变，形成固定的任务队列。而动态优先级首先会按优先级高低排序，每执行一次任务，优先级下降，每等待一次则优先级上升，处于动态改变状态。在非抢占调度中，被调度任务的优先级是确定的，一旦任务开始执行就不能被其他具有任意优先级的任务打断。这种方式不存在因优先级切换而产生的额外开销，在实现方面比较简单，但其性能较差，也不灵活。抢占式调度虽然存在任务切换产生的额外开销，但能够满足多任务优先级的调度，更符合实际系统的调度需求；

(6)根据系统是否依赖反馈信息改变自身的调度策略进行自适应和非自适应的划分。自适应任务调度能根据系统反馈信息和当前的环境适应度，及时调整调度策略，而非自适应调度则不具备此优势，调度适应性较差。

基于研究方法的分类如下：

(1)最优化调度算法是基于最优化理论提出的。在给定一些假设的前提下设计一个调度方案，通过数学优化技术将复杂问题转化为数学规划模型。这类方法包括数学规划(动态规划、混合整数线性规划等)、分支定界法和消去法、排队论等算法。但随着调度任务规模的增大，此类算法不再适用于求解复杂的任务调度问题；

(2)智能搜索算法(Intelligent Search Algorithm，ISA)。智能搜索算法通过多次迭代获得反馈信息，选择能最快得到最优解的路径[15]，大多被应用于多目标优化和动态调度中。该类算法通常基于准随机搜索算法，通过设置某些特殊参数模仿自然界的某些行为或现象来对真实系统建模。智能搜索算法能够从不同的角度对局部搜索进行改进，避免寻优过程中出现收敛较慢或陷入局部最优的现象，能够得到满足目标函数的最优调度组合；

(3)基于仿真的方法。通过模拟实际的环境，设置不同的仿真参数构建仿真平台。根据仿真结果数据建立规则库或训练模型，常用于动态任务调度；

(4)混合调度方法。混合调度[16]方法以静动结合的方式对任务进行分配和映射。相比动态调度，静态调度方法能够更好地满足任务调度的实时要求。静态调度方法属于离线算法，任务分配是在编译时完成的，在执行过程中不会产生调度开销，能够弥补动态调度开销大的缺点。混合调度是建立在静态调度之上的，通过静态调度形成任务划分的初始方案，在此基础上根据系统环境的变化进行动态调整，此类调度过程可以称为重调度或在线调度；

(5)机器学习算法。机器学习算法[17]均属于自适应在线调度算法[18]，其中人工神经网络以多层网络构造调度决策模型，是一种处理复杂信息的信息处理系统，因此在功能上具有智能化的特点。该方法能够在线学习，实现动态调整资源的分配，适用于解决动态调度问题。强化学习算法中，Q-learning 算法通过非监督学习与外部环境交互，在处理任务调度问题上具有良好的效果。

2 任务调度模型及算法性能对比分析

2.1 任务调度模型

任务调度建模包括对调度任务建模和目标处理系统建模，需要考虑组件间、多个子任务之间的关联以及异构处理器之间的通信等因素，因此任务调度模型的构建与调度策略的选择是分层异构信号处理平台提高性能的关键[19]。异构信号处理平台下的组件任务调度关系采用有向无环图来描述，如图3(a)所示，节点代表应用组件，有向边代表通信链路。系统中待调度任务采用模型G={V,E,C,L}表示，其中V={v1,v2,v3,…,vn}代表信号处理任务含组件的集合，E={e12,e23,…,eij}是存在依赖关系的有向边的集合，eij=(vi,vj)表示vi和vj之间有直接通信链路，且vi是vj的前驱，C={c1,c2,…,cn}表示组件计算量的集合，L(vi,vj)表示组件间通信量。硬件资源可以采用无向图表示，抽象为P={N,H,W,T}，N为处理器集合，H为处理器特征，W为计算开销。

(1)

式(1)是任务组件在处理器间的通信开销，如果组件任务vi和vj被映射到同一节点上，通信开销Tij为0。假设异构平台上有4个异构处理器，如图3(b)所示抽象为具有一定拓扑结构的异构硬件处理器模型。

(a)

2.2 算法对比分析

任务的动态分配和调度的实时性是高性能分层异构信号处理平台发展的瓶颈，而单一的任务调度算法由于自身存在的缺点不能完全满足平台对高效率调度的要求。本文根据异构系统任务调度最新的研究进展提出了组合优化算法的概念，即通过不同算法的结合形成优劣互补来满足调度目标要求。组合优化算法的出现为解决任务调度出现的瓶颈问题提供了新思路。表1总结了经典启发式调度算法(D-Heuristic Algorithm，DHA)、ISA、机器学习算法(Machine Learning，ML)、组合优化算法(Combinatorial Algorithm，CA)的适用场景，并进行了优缺点对比。

表1 DHA、ISA、ML、CA算法性能分析

图4分析了经典启发式调度算法、智能搜索算法、机器学习算法、组合优化算法从十九世纪六十年代至今的算法使用比例。经典启发式算法适用于静态任务调度且灵活性差，不能按照系统可用处理器资源及时进行任务调配，因此应用比例逐渐降低。智能搜索算法和人工智能算法随计算机和人工智能技术的快速发展，使用比例显著增加。但智能搜索算法的可预测性差，机器学习算法存在训练时间较长且结果缺乏解释力的问题，因此任务调度结果差强人意。组合优化算法通过算法的相互结合能够较好地解决这类问题。组合优化算法主要包括经典启发式调度算法与智能搜索算法的结合(DH-ISA)、不同智能搜索算法间的结合(IS-ISA)、机器学习算法与经典启发式算法的结合(ML-DHA)及机器学习与智能搜索算法的结合(ML-ISA)。

图4 DHA、ISA、ML、CA算法应用比例

2.2.1 DH-ISA、IS-ISA改进方式及性能比较

在异构处理机系统中常用的经典启发式调度算法有HEFT算法、DLS算法等。ISA算法通常由一组随机数构成初始解开始迭代搜索直到算法收敛，获取满足系统优化目标的最优解。由于ISA算法具有与问题无关、结构开放的特性，研究人员通常在问题的描述、编码方法、算法构造等方面进行改进。

GA算法以改进编码的形式与HEFT结合，通过设计合适的适应度函数或根据个体实时适应度值动态调整交叉、变异概率调节计算式。如表2所示，文献[3]将HEFT算法与ACO结合，得到智能并行蚁群任务调度策略。HEFT任务排序改善了蚁群算法缺乏初始信息的问题。文献[13]在HLEFT中引入GA，从算法搜索效率和算法多样性两方面进行优化，即通过交叉、变异引入新的处理器排列方式，减少了寻找近似最优解的计算时间，增强了局部搜索的能力。蚁群算法在初期搜索时信息匮乏需要做大量的尝试以便确定目标点和最优路径[20]，因此初期搜索速度较慢，但在后期又由于信息素的积累容易陷入局部最优。文献[17]对MLSH、GA-MLSH、ACO、GAACO算法在调度长度和总平均利用率方面进行了对比，并将GA得到的次优解作为ACO的初始信息素，以便获取更优的收敛速度和性能。

表2 DH- ISA、IS-ISA性能改进

2.2.2 ML与ISA、DHA相结合

人工神经网络将已知的与目标函数相关的约束信息存储于神经网络的连接权矩阵中[21]，通过增加隐藏单位的数量来获得更好的训练结果，但所花费的时间也会随之增加。文献[4]和文献[6]通过ANN、SVM、自增强网络训练生成预测模型，分别与GA结合作为在线调度器迭代搜索映射空间，选取最优的映射决策方案。通过对比任务最少执行时间，得到ANN与GA结合为最优映射方案。文献[22]提出智能的两阶段任务分配方案，第一阶段使用SVM按照任务特征、处理器状态等进行预处理分类到异构处理器上，在第二阶段根据处理器状态参数及运行状态的改变，通过多次的任务队列调整进行任务分配[22]，有效降低了分配开销。

Q-Learning算法是一种经典的无监督、自适应算法[23]，其建立在马尔科夫决策过程(Markov Decision Process，MDP)[24]上，通过不断与外部环境进行交互获得反馈信息，并根据反馈信息和历史经验不断学习，在解决任务调度问题上具有较好的效果。文献[15]将分布式系统任务分配决策建模为MDP，通过Q-Learning使得调度长度(Makespan)最小化，并在此基础上结合ACO算法进一步提高系统的可用性。文献[18]将改进SVM与Q-Learning算法结合，将其应用于传感器节点任务调度中，并与BP-Q算法进行对比。BP-Q网络虽然在初始阶段的学习速度较快，但由于泛化能力较弱，易陷入局部最优[25]。而SVM泛化性能出众[26-27]，与Q-Learning算法结合能够提高模型的解释能力，在保证WNS网络寿命的同时获得更好的应用性能和更高的任务执行成功率。

表3 ML- DHA、ML- ISA性能改进

结合以上对组合优化算法的研究及表1对DHA、ISA、ML、CA算法的优缺点对比，发现组合优化算法可以取得更好的优化结果，具有广泛的适用场景。此外，组合优化算法通过对资源的动态管理和智能决策，满足了异构信号处理平台对任务调度实时性、准确性、高性能的要求。

3 发展方向

分层异构信号处理平台硬件资源种类繁多，其异构性、层级性的特点给任务规划增加了一定的难度，而良好的负载均衡要求也给任务调度带来了挑战。合理的任务调度算法可以将复杂多样的信号处理任务根据其特征分配到不同硬件资源上，满足平台的高性能需求。目前智能搜索算法和人工智能算法在不同场景下的任务调度中得到了广泛的研究及应用，其智能搜索的特点有效解决了传统算法灵活性差、资源利用率低的问题。但是，上述方法计算复杂，所需要的收敛时间较长，不能满足信号任务对异构信号处理平台高效率、高实时性的需求。组合优化算法通过算法间结合达到了优劣互补，其动态资源管理、智能决策、广泛的适用场景等特性为解决任务调度的瓶颈问题提供了新思路，能够满足异构信号处理平台对任务调度实时性、准确性、高性能的要求。因此，将组合优化算法应用到分层异构信号处理平台中，发挥平台的异构高性能特性，满足不同信号处理任务的变化需求已成为下一步的研究重点和热点。

4 结束语

目前多层异构信号处理平台的任务规划研究仍面临着挑战，本文对分层异构信号处理平台进行了研究，并将调度算法按照任务类型、调度环境、调度目标、研究方法进行了分类、归纳，总结了目前任务调度算法的研究现状，提出组合优化算法的概念并进行了对比分析。本文根据异构信号处理平台对实时性的要求以及目前单一任务调度算法存在的负载失衡、能耗大等问题，进一步阐述了组合优化算法的优点，并预测其将成为今后主要的研究方向。