SOC软硬件协同设计中多任务性能评估算法

摘　要：在分析现有的性能评估方法之上，提出了用MTLS算法对软硬件划分结果进行性能评估，验证系统软硬件划分的优劣。并且针对单任务图描述多CPU系统结构的不足，提出采用多任务图来描述的方法。首先搭建了软硬件协同设计的平台并描述了软硬件协同设计的流程，其次对目标系统进行形式化的描述，最后重点阐述了多任务图的MTLS性能评估算法，并与MD，HNF，HLHET三种算法进行了比较。实验结果表明，提出的MTLS算法比其他三种算法优越。

关键词：调度；分配；性能评估；软硬件划分；多任务图

引 言

　　随着微电子技术的发展，芯片的集成度越来越高，片上系统( SOC)的发展已经是必然趋势。SOC系统是将原来由许多芯片完成的功能，集中到一块芯片中完成。但SOC不是各个芯片功能的简单叠加，而是从整个系统的功能和性能出发，用软硬协同设计和验证方法，利用IP复用及深亚微米技术，在一个芯片上实现复杂的功能。软硬件协同设计是一个从高层抽象建模到低层硬件建模的过程。在从无时间概念的功能模型转换为总线周期精确的功能模型过程中，软硬件划分和性能评估是软硬件协同设计的难点和关键。

传统的芯片设计中工程师一般都是凭经验进行软硬件划分，随着系统结构复杂度的增加，凭经验已经难以给出适当的划分结果，而且系统的软硬件划分结果直接影响到后续的软硬件协同设计和最终的硬件实现，因此软硬件自动划分技术成为当前研究的热点。为了实现软硬件自动划分，并且评估软硬件划分的优劣，评估因子的选择以及性能评估算法的实现相当重要，调度和分配一直是贯穿在软硬件划分性能评估的始末。目前，软硬件划分技术可以分为两大类：①首先对系统初始化，然后在调度中分析系统特征并优化分配。如YuaNXie 和WanyWolf提出的方法是将系统模块初始化为硬件，然后根据时间约束条件改变分配方式将部分硬件由软件替换减小系统
耗费。②在固定分配方式下进行调度，采用遗传算法、模拟退火算法等进行寻优。如Dick首先初始化多种分配方案构成种群，每个个体采用MD算法进行调度，然后采用遗传算法对种群进行演化，直到搜索到最优解。

本文研究的软硬件划分技术是基于第二类方法，即是在固定的分配方式下进行调度。当系统结构中存在多个处理器时，系统的工作流程由多个并发的进程构成，单任务图有时无法描述多个任务的并发性，本文采用多任务图对系统抽象。针对MD (Mobility Directed)，HNF (Heavy Node First)，HLFET(HighLeveLFirsTwithEstimated Time)算法的缺陷，提出了MTLS(MultiTask LisTScheduling)性能评估方法。MTLS算法考虑了系统的关键路径、任务的权重大小以及系统的时间约束，从全局把握。实验证明，MTLS算法比上述三种算法能够更好地评估划分性能。

SOC软硬件协同设计

SOC软硬件划分平台
软硬件划分是软硬件协同设计首要问题，只有在系统各个模块确定了实现方式之后才能保证软件和硬件的设计可以同时进行。系统实现的软硬件划分平台如图1所示，由六个模块组成，分别为图形用户编辑接口、系统模型、分配模块、IP特征库、性能评估模块、结果分析。

图形用户编辑接口是用户输入/输出的接口。系统模型主要是对系统进行形式化的定义，对系统进行建模。IP特征数据库中收集了很多现有IP核的性能参数，如IP核的尺寸、最大工作频率、工作时的功耗、空闲时的功耗等。它是IP核复用技术的基础。分配模块主要是分析输入的系统模型以及该系统模型与特征数据库之间的关系，从IP库中提取特征参数，完成对数据流图的分配。性能评估模块是核心，主要是对分配完成后的数据流图进行调度，评估出系统的运行时间和功耗。结果分析模块主要是分析可行的划分解，比较得出较优的划分结果。

SOC软硬件划分流程
本文采用速度、功耗和价格作为衡量的标准，这几个参数也是生产者和消费者共同关注的问题。要使划分的结果最优，实际上是一个多目标优化的过程，遗传算法可以很好地进行多目标寻优。图2是软硬件划分的流程图，整个流程在外框架是一个多目标寻优的演化过程，而在每次的演化过程中采用MTLS算法对分配后的模型进行调度和评估。

首先，在图形接口输入系统形式化定义后的数据流图，从IP特征库选择合适的IP进行初始化的分配。同时初始化种群，界定优化算法的搜索空间，为多目标优化模块指定相应的优化目标。其次，调度种群中的个体，给出优化目标的评估结果，并将不满足时间约束条件的解直接删除。采用小生境技术选择较优的解构成前沿，经过演化，该前沿会逐渐靠近空间的最优前沿。最后，判断逐步演化的前沿是否为最优前沿，如果是最优前沿，演化过程结束，并输出一组非劣的划分结果和相应的目标值。

性能评估

形式化定义
系统结构是异步多处理器结构，由多个RISC和多个ASIC组成，多个CPU共享一个存储器。同一个CPU上可以执行不同任务，而同一个ASIC只能执行一种任务。为了较好地描述这样的系统结构，采用DAG (Directed Acyclic Graph)来对系统进行抽象。DAG称为有向无环图，如图4所示，DAG由节点和弧线构成，N1→N2表示N2的执行必须在N1完成之后。首先要把系统分解为若干个并行的流程。对于每个流程，按照一定的粒度对硬件描述代码和软件代码进行分析，分解为若干个任务。然后确定每个流程中任务间(包括硬件和软件)的依赖关系。任务映射为DAG中的节点，任务之间的数据依赖映射为DAG中的弧线，因此系统的调度问题也就转换成为对多任
务图的调度。

对系统做如下定义：DAG = {D1，D2，. . . ，Di}，Di表示任务图，Di= {N，E}，N= {N1，N2，. . . ，Ni}，Ni代表任务图中的节点，NCi表示Ni的子节点，NPi表示Ni的父节点；E = { EN1→N2，EN1→N3 ，.，ENi→Nj}，ENi→Nj表示Ni到Nj的弧线。如果Ni和Nj都由硬件或者软件实现，ENi→Nj代价为零，否则映射为总线。

定义1　indegree表示流入任务节点弧线数，outdegree表示流出任务节点弧线的个数。src代表入度为零的任务节点，sink代表出度为零的任务节点。每个sink任务节点都会赋有截止时间deadline，表示对sink任务的时间约束。EXT表示任务的执行时间。data定义为总线上传输的数据。ST表示系统调度所需的时间。

定义2　EFT( EarliesTFinishTime)表示任务节点最早完成任务的时间，可以通过从src节点向下遍历获得。假设Ni有p个父节点，如果ENPik →Ni的代价为零，w= 0，如果ENPik →Nt由总线实现，w= 1(以后的w表示相同的含义)。EFT由如下的公式确定：


定义3　LFT(LatesTFinishTime)表示任务节点最晚完成任务的时间，可以通过从树的根节点向上遍历获得。假设Ni有p个子节点，LFT由如下公式确定：


如果Ni为sink节点，NLFTi= deadline。

定义4　mobility表示任务节点N和总线E执行时间的灵活度。任务节点的mobility值定义为LFT和EFT的差值：mobility =LFT-EFT任务节点N和总线E的mobility的属性有如下关系：
　　



定义5　CP(CriticaLPath)定义为关键路径，表示从src节点到sink节点执行时间最长的路径。Critical是一个布尔量，表示任务节点N和总线E是否位于关键路径上。

定义6　BD (BottomDistance)表士任务节点到sink节点的最长的执行路径，由如下公式确定：


k如果Ni为sink节点，NBDi= NEXTi。

MTLS算法的思想与实现
优先级确定
优先级的比较分为同一任务图中节点之间的比较和不同任务图中节点之间的比较。对于同一任务图，关键路径上的任务执行时间最长，要使任务尽早完成，即要尽量使关键路径上的任务尽早执行，因此关键路径上的任务优先级最大。关键路径上任务的父辈任务越早执行使得关键路径上的任务越早就绪，因此它们的优先级次高。不属于前两类的任务节点通过BD来比较它们的优先级。对于不同的任务图，首先根据任务是否在关键路径上来比较它们的优先级，在关键路径上的任务优先调度。如果两者都在关键路径上或者都不在关键路径上，就比较它们的mobility大小。mobility体现了任务图的时间约束，约束条件紧迫的流程应当优先考虑。

速度和功耗的评估
算法实现的流程图如图3所示。输入为配置好的多任务图，根据上述定义计算出CP，以及每个任务节点和弧线的mo2bility和BD参数。根据优先级确定计算出每个任务节点和弧线的优先级大小，搜索就绪的任务节点和弧线，选择并行执行的节点，包括优先级最高的硬件、优先级最高的总线和优先级最高的软件。如果有多个CPU，则要根据CPU的个数确定多个软件并行执行的情况，并且在多CPU上进行调度，保证CPU资源的充分利用。选择每次调度中最小的执行时间，判断调度是否完成，如果没有则继续循环调度，如果结束就计算调度的累加时间。

假设Ni的实现IP为PE，Eij实现IP为B us，IPi= { PE1，PE2，. . . ，PEN，B us}，PE = PEh∪PEs，PEh代表软件IP，PEs代表硬件IP。由IPi建立链表IPList，每个IPi需要执行j个任务，用Tij表示，j个任务Tij建立链表TaskList，每个Tij对应一个
任务节点Ni。

Tij= {Ni1，Ni2，. . . ，Nij}，IPi∈PE

Tij= { Ei1，Ei2，. . . ，Eij}，IPi为B us

调度前为每个任务图建立链表Task Ready List和Task Compare List，Task Ready List用来比较同一任务图中任务的优先级，Task Compare List用来比较不同任务图中任务之间的优先级。实现MTLS性能评估算法的伪码如下：



调度完成后，ST就是系统执行的时间，也是系统速度的衡量标准。价格的评估比较简单，只需要简单的累加。在已知调度时间ST，每个任务执行时间NEXT、单位时间的功耗Npow，总线的执行时间EEXTij、总线工作功耗B uspow、总线空闲功耗B usidle下，系统功耗的评估由如下公式确定：




实验结果与分析
MD算法的基本思想是根据任务执行的灵活度来确定优先级；HNF算法的基本思想是根据任务的权重大小来确定优先级；HLFET算法的基本思想是根据任务执行的路径大小来确定优先级。这三种算法都存在它们的不足，它们没有从全局上考虑系统的整体信息，而是通过系统的局部信息来调度。MTLS算法考虑了系统的关键路径、任务的权重大小以及系统的时间约束，是从全局上进行把握的。

为了验证算法的有效性，采用包含两个DAG的系统作为例子，如图4所示，第一个DAG由七个任务节点组成，第二个DAG由10个任务节点组成。任务的执行时间已经在图中注明，黑色节点代表任务由软件实现，白色节点代表任务由硬件实现，每个sink节点的时间约束都为1400。采用MTLS算法，计算出了CP(CP为1表示节点在关键路径上)，以及每个任务节点的参数mobility，BD，并得到了每个任务在相应IP完成时间，如表1所示(mb表示mobility)。

可见最后执行的任务是DAG1中的N7，在1310时刻完成任务，因此采用MTLS算法需要1310个时间单位。同样用MD，HNF，HLFET算法调度后，得到结果如下：MD算法需要1440个时间单位，HNF算法需要1390个时间单位，用HLFET算法需要1470个时间单位。采用MTLS算法执行的时间最短。实验数据如表1所示。


　　为了更好地比较四种算法的优劣，采用个数不同的任务图来验证。分别输入个数为2，4，6，8的任务图，如图5所示，可以发现随着DAG个数的增多，四种算法的差距越大，MTLS算法比其他三种算法性能优越。实验结果说明，MTLS算法适于并行进程比较多的系统，它能够很好地减少并行进程的调度时间。MD算法虽然考虑到了关键路径上任务，但没有考虑到非关键路径上的任务对调度的影响，而且会导致约束条件严格的任务一直保持高优先级，使得其他任务无法抢占。HNF算法没有考虑关键路径，也没有考虑时间约束，这种算法使用的任务特征太局部化。在两个任务图的关键路径的长度相差比较大的情况下，HLFET算法容易延迟路径短的任务图，虽然缩短了调度时间，却无法满足约束条件。MTLS算法既考虑了关键路径，又考虑到了非关键路径，同时也满足了时间约束条件，从全局把握。同一任务图中的就绪任务和不同任务图中的就绪任务采用不同的策略调度，使得对软硬件划分的性能评估最优。

结论

硬件集成度的飞速发展导致SOC产品的开发面临着巨大的挑战，SOC的设计方法学的研究还是任重而道远的。多任务图比单任务图能够更好地描述包含多个处理器的系统结构，因此提出用多任务图建模。本文的软硬件划分平台是在系统级进行建模，提高了设计的层次，在高层对系统的速度、功耗、价格进行评估，避免了底层设计带来的不必要的损失。MTLS算法是本文提出的适合评估软硬件划分性能的评估算法，通过实验比较比其他三种算法优越。在下一步的改进方面，可以在目标值的优化方面改进为优化更多的目标或是根据用户的需求动态选择优化目标，以满足不同用户对产品的需求。