一种新的软硬件协同综合及其处理器分配方法

王永博，杨明，赵冬媛

(辽宁大学信息学院，辽宁沈阳110036)

现代多媒体、数字信号处理器和数据传输都有非常密集的数据处理要求。使用单一处理器并不能满足总的数据处理能力要求，而使用多处理器又会受到多方面的限制，如系统面积、能耗大小、系统上市时间等。数据处理能力需求与系统限制之间的平衡要求，促进了自动化式系统设计的产生和发展。自动化式系统设计主要是指软硬件协同设计，主要包括3个部分：第一，选择系统使用的处理器元件(ASIC或者通用CPU);第二，分配所有任务到具体的处理器件，并建立处理器件间的通讯连接结构;第三，安排所有任务的开始和结束时间，即时间调度。由于处理分配和调度安排是熟悉的NP-Compelete[1-2]结构，因此本文在多处理器任务的分配和调度中使用启发式算法。

若提高处理能力需要系统进行流水式的快速执行，而仅仅在必备的执行环节使用硬件，则不能满足增长的处理能力要求，因此处理器件需要被安排到并行的执行平台[3]。很多算法被引入到含有选择处理器件和映射任务的软硬件协同设计当中，但是它们往往受限于单CPU和共用总线结构[4]。本文提供了一种用于处理器件分配和流水化式处理的算法。该算法基于任务的优先级，交替进行器件选择和任务映射，把流水化平台建立在分配处理过程当中，避免了冗余平台的残留。

1 已有算法简介

Wolf提出了一种结构协同算法[5]。其算法以不规则的拓扑分布为目标，能够处理多CPU和多硬件协同问题。首先，所有的任务映射到最快的处理器件上;然后，重新分配任务，目标设为减少数据传输量;最后，数据传输通道被分配到处理器件间的通讯上。该算法很好地区分了选择和分配过程。但是增加硬件有可能降低效率，因为硬件经常是满负荷工作，而且很可能永远不能从系统中移除出去。任务未进行流水化的处理，因此不能满足高数据量处理能力的要求。

Bakshi和Gajski提出的协同算法是首先将任务分配到硬件上，不考虑其他任何参数，然后软件处理器被尽可能地搜索。当任务不能被安排在当前流水平台时，该算法会创建新的流水平台。该算法的问题在于，对于给定的任务不能使任务安排器件在软件和硬件间交换。算法没有考虑增加一个CPU的硬件成本，不同任务的数据传输时间有时会超过任务执行时间。该算法还忽略了任务的传输时间。

另一种协同算法是由Chatha和Vemuri[4]提出。该算法以数据流应用为目标，分支和边界的划分是算法的中心。启发式的方法用于初始系统划分，然后用分支和边界算法探测软硬件选择。该算法为流水式，通过启发的方式选择数据相关性，之后创建流水平台，这样能够减少流水式缓冲需要的内存。然而任务的分配和流水化没有考虑相互的作用，流水化没有考虑目标时间，因此该算法执行后有可能产生冗余的流水平台。另外，该算法只考虑系统中一个软件处理器，并受到分支和边界划分法采用的指数时间限制。

2 处理器件选择、任务分配以及流水化

本文提出的算法，把任务划分为软件或硬件执行，其过程包括处理器件的选择(软件或者硬件)和任务的分配，而且建立了流水平台，以满足较高的数据处理能力约束。

2.1 处理器件选择

处理器件选择是本文算法的第一步。根据软件和硬件对系统的性能影响和面积消耗，选择软件或者硬件添加到系统中。选择过程对所有可能选项计算选择系数，选择系数包含2个因子：性能提高因子和面积消耗因子。为了描述这两个因子，首先要定义若干个变量。TSW表示当前系统中没有专用硬件资源的任务数，PESW和PEHW分别表示软件和硬件处理器件。SYSPESW和SYSPEHW分别表示系统内当前的软件和硬件资源数。基于这些变量，定义累加的软件和硬件执行时间分别为：

硬件提高因子是对特定任务添加某一硬件资源使系统获得的性能提高：

其中Ti表示能够在PENEW上执行的任务。

使用这些变量，定义之前和之后的系统执行时间为：

面积成本因子(PEAREA_FACTOR)表示特定处理器件的面积消耗。面积消耗按照MAX_AREA进行正态划分，MAX_AREA是所有可行器件的最大面积消耗。面积成本因子的计算公式为：

通过性能提高因子和面积消耗因子，将得到选择系数，它是性能提高因子和面积因子的加权和。

所有的处理器件都要计算PESELECT。而具有最大选择系数的器件将被添加到系统中。

2.2 任务分配与流水化

将任务分配到已添加到系统中的处理器件上，流水处理与任务分配即可同时进行。首先给每一个任务分配优先级，优先级分配可以采用多种方法，本文从执行的角度出发，对每一节点从任务图尾部开始累计它最小的执行时间之和，并对相应路径的后续节点设置最高优先级。这种优先级测量方法非常普遍，在文献[4]中被广泛使用。除了使用最小执行时间，还有其他统计学指标也可以被使用，比如平均或者中位执行时间。但是，最小执行时间测量方法能给出更好的结果。

流水化分配是寻找每一个处理器上分配任务的开始和结束时间。每一个任务开始时间被定义为EarliestStartTime，具体定义如下：

EarliestStartTime(Ti)=MAX(FinishTime(PRED(Ti)))，其中PRED(Ti)是Ti的前序任务

PEIdleTime(PEj)=FinishTime(Last_task_on_PEj)

算法定义了任务Ti被分配到处理器件PEj上时的数据通讯时间，这个时间是把所有需要的数据传送给PEj的时间。该时间定义如下：

通过EarliestStartTime、PEIdleTime和CommTime，可以定义任务起始时间和结束时间(Ti分配到上PEj)：

StartTime(Ti，PEj)=MAX(EarliestStartTime(Ti)，PEIdleTime(PEj)

FinishTime(Ti，PEj)=StartTime(Ti，PEj)+CommTime(Ti，PEj)+ExecTime(Ti，PEj)通过这些公式可以计算已经准备好且具有最高优先级的任务的完成时间，准备好的任务是指前序任务都已经分配完的任务。当前任务分配在有最早完成时间的PE上。如果最早完成时间超过了流水时间限制，那么将会生成新的流水平台。任务的最早开始时间EarliestStartTime将被置零，所有PE将会重新计算完成时间FinishTime。如果最早完成时间在新流水平台再次超过流水时间限制，那么该条件下的流水分配失败，需要返回并为系统添加处理器件。算法流程如图1所示。

3 实验结果

某个应用的任务数据流描述如图2所示。每一节点表示应用的一个任务，边界表示数据依赖，边界上的数字表示传输到其他任务的数据量。本文算法假定在可用资源上任务的执行时间是可知的。对硬件资源的执行时间信息能够人为或者使用文献[6]中的算法获得。对软件资源的执行时间信息能够通过模拟获取。因此。该应用的任务执行时间信息与面积信息如表1所示。

图1 算法流程

图2 任务数据流

本文算法在一定的时间和面积约束下执行，每次测试的结果被记录下来。本文算法输出的结果包括任务分配给器件的具体开始时间和结束时间的分配和流水平台。

图3显示了在面积和执行时间约束下算法获得的实际结果。约束条件按照面积、执行时间成组显示。图3中使用的约束是：(3 200，30)，(3 100，40)，(2 400，55)，(2 250，65)和(1 200，75)。结果显示算法能够满足所有的约束。基于执行时间的要求，执行被划分成若干个流水平台。流水平台数量从3(最初)变到1(最后)。

第一个测试的具体结果如表2所示。执行时间和面积要求是30个时间单位和3 200个面积单位。本文算法能够找到一个流水平台时长27个时间单位系统调度。算法选择了4个处理器件(3次使用3号件，1次2号件)，系统面积3 015个单位。执行被划分为流水平台。任务B在第二平台被执行，任务E在第三平台执行。

4 结论

本文提出了一种处理器件选择、任务分配和流水化的新算法。新算法区分了资源选择和任务分配。为了满足增长的数据处理量的要求，对任务执行进行了流水化处理。同时，避免了冗余流水平台的生成。本文算法根据面积信息和执行时间，提出了反复选择处理器件的启发式方法。与其他算法不同的是，本文算法将数据通讯时间纳入了考虑，同样的算法能够处理多硬件和多软件资源。

表1 处理器件任务时间与面积信息

表2 试验结果(执行时间30，面积3 200)

图3 测试结果

[1] Garey M R，Johnson D S.Computers and Interactability：A Guide to the Theory of NP-Completeness[M].San Francisco：Freeman，1979.

[2] Kwok Y K，Ahmad I.Dynamic critical-path scheduling：An effective technique for allocating task graphs to multiprocessors[J].IEEE Transactions on Parallel Distributed Systems，1996，7(5)：506-521.

[3] Bakshi S，Gajaski D D.Partitioning and pielining for performance constrained hardware/software systems[J].IEEE Transactions on Very Large Scale Integration Systems，1999，7(4)：419-432.

[4] Chatha K S，Vemuri R.Hardware-Software Partitioning and Pipelined Scheduling of Trans formative Applications[J].IEEE Transactions on Very Large Scale Integration Systems，2002，10(3)：193-208.

[5] Wolf W.An architectural co-synthesis algorithm for distributed，embedded computing systems[J].IEEE Transactions on VLSI Systems，1997，5(6)：218-229.

[6] Henkel J，Ernst R.A Path-Based Estimation Technique for Estimating Hardware Runtime in HW/SW Co-synthesis[C]//IEEE ACM Proc of 8th Intl Symposium on System Synthesis，2005.