MPSoC软硬件划分的自动波竞争神经网络算法

常政威，谢晓娜，桑 楠，熊光泽

(1. 四川电力试验研究院 成都 610072; 2. 电子科技大学计算机科学与工程学院 成都 610054; 3. 郑州大学体育学院 郑州 450044)

片上系统(system-on-chip，SoC)已广泛应用于网络通信、信号处理、多媒体等嵌入式电子产品中，单处理器SoC无法满足片上系统日益增长的功能和性能需求，多处理器SoC (multi-processor SoC，MPSoC)[1-2]成为高性能嵌入式系统发展的必然趋势。目前，国际上已有多家公司建立了MPSoC平台[2]，如Philips的Nexperia、TI的OMAP以及Xilinix的Vertex-II Pro。

为提高设计和生产效率，MPSoC基于设计重用的思想，普遍采用经过预先验证、测试的可交易组件，如软件采用商业成品(commercial-off-the-shelf，COTS)构件，硬件采用知识产权(intellectual property，IP)核。对于系统中的每个功能模块，不同的提供商可能有不同的软硬件组件解决方案以及不同的性能参数，如功耗、面积、成本、运行时间等。在设计过程中如何兼顾系统的功能需求和性能约束，确定各模块的实现方式，使MPSoC的性能指标最优，即软硬件划分问题。

针对嵌入式系统软硬件划分问题，研究人员已提出了许多算法[3-6]，大都把软硬件划分看作二路划分问题，将系统中的计算模块划分为软件和硬件两个子集。早期的嵌入式系统主要考虑“CPU+ASIC”的单一架构，分配到CPU上的模块用软件方式执行，否则为硬件。但是在MPSoC平台中，系统结构呈多元化，迫切需要面向MPSoC高效、自动化的划分工具和算法。

脉冲耦合神经网络(pulse coupled neural networks，PCNN)是一种具有生物学背景的全新神经网络模型，已在图像处理、模式识别和优化等领域得到了广泛的应用[7]。文献[8]借鉴PCNN中自动波产生与传播的机理，进一步提出了用于求解最短路径问题的自动波竞争神经网络(autowave competition neural networks，ACNN)。

本文针对基于可重用组件(软件构件和IP核)的MPSoC平台，定义了系统成本和实时性约束的低功耗软硬件划分问题，将其转化为一个有向图中的多约束最短路径问题，并提出了一种新的ACNN算法用于获得问题的优化解。最后，通过一个MPSoC实例验证了算法的有效性和求解效率。

1 MPSoC软硬件划分问题

1.1 系统模型

如图1所示，MPSoC平台由一个或多个可编程的CPU、存储器以及若干硬件单元即IP核组成。软件保存在存储器中，由CPU执行。假设平台中CPU与存储器的数量已经固定，可以满足嵌入式应用的计算和存储能力需求，但单纯用软件方式无法满足系统的性能需求，需要选择若干IP核完成一些计算功能。本文对MPSoC的通信平台不作考虑，计算节点间可采用总线、点对点或片上网络等各种通信方式。

图1 MPSoC平台系统结构

MPSoC应用的设计需求用一个任务流图表示，如图2所示。任务流图中的每个节点表示一个计算任务模块，节点间的有向边表示任务模块之间的控制依赖关系。任务流图中有一个入度为0的开始节点和一个出度为0的终止节点。从开始节点到终止节点之间的一条通路称为系统的一次处理过程。

图2 MPSoC应用的任务流图

对MPSoC软硬件划分问题作如下假设：

(1) MPSoC平台有一个可供选择的组件库，每个组件是一个软件构件或IP核。

(2) 对于任意一个任务模块，组件库中包含多个可以实现对应功能的组件。不同的组件执行该任务有不同的性能参数，包括成本、运行时间和功耗。

(3) MPSoC的总功耗(成本)定义为所有任务模块的功耗(成本)之和，即成本和功耗具有累加性。

(4) 一次处理过程的运行时间定义为其中所有任务的运行时间之和。MPSoC的运行时间定义为所有处理过程运行时间中的最大值。

(5) 给定任务流图和组件库，MPSoC低功耗软硬件划分问题就是在MPSoC总成本和实时性约束下，确定每个任务模块采用具体的软件(构件)或硬件(IP核)组件实现，使得MPSoC的功耗最优。

1.2 问题定义

本文给出以上低功耗MPSoC软硬件划分问题(简称MPSoC划分)的形式化描述。

1.3 转化为多约束最短路径问题

根据MPSoC划分的定义，可以构造出一个赋权有向图，将MPSoC划分问题转化为一个多约束最短路径(multi- constrained shortest path，MCSP)问题，如图3所示。

构造赋权有向图的具体规则如下。

(1) 每个组件Coreij对应图中的一个顶点，Corei中所有组件对应的顶点排成一列。Coreij与下一列每个顶点Corei+1,k之间有一条有向边连接，边的权重为Pi+1,k，即Corei+1,k的功耗。

(2) 除此之外，增加起始顶点Start和目标顶点End两个虚拟顶点，顶点Start到Core1j(1≤j≤|Core1|)之间有一条有向边，权重为P1i。Corenj(1≤j≤|Coren|)到顶点End之间有一条有向边，权重为PEnd= 0。

图3 由MPSoC划分构造的赋权有向图

2 基于ACNN的MPSoC划分算法

ACNN的相关概念如神经元的激活势U、阈值θ、输出Y和自动波强度A以及自动波传播机制参见文献[8]，本文限于篇幅不再赘述。

(1) 每个神经元只点火一次；

(2) 每个神经元的阈值仅更新一次，从∞变为一个具体的数值后，不再改变；

(3) 除Start外，每列神经元均由上一列中的同一个神经元点火。

为求解图3中的MCSP问题，在自动波向目标顶点End前进的过程中，必须考虑对应路径的约束条件。因此，在ACNN的每次迭代中，只有满足约束的自动波才能继续前进。不满足约束的自动波要及时被剔除，才能确保网络中强度较大或约束条件较轻的自动波有继续竞争前进的机会。

为了提供对MCSP问题中各约束条件的支持，下面对ACNN进行重新设计。

(1) 一个神经元在点火以后，可以再次“熄火”，即神经元的阈值从一个具体的数值重置为∞。熄火后的神经元可以再次点火，即一个神经元可以多次点火和熄火。

(4) 当End点火以后，获得了一条满足约束条件的路径，但不一定是最优的受约束路径。为此，首先将End熄火，然后将上一列神经元传播来的相应自动波强度也设置为∞，以便其他的自动波能够继续竞争前进。

当神经元I点火以后，由式(4)得到它向下一列各神经元传播的自动波强度。但是，若下一列的某神经元不符合约束条件，则对应的强度将置为∞。另外，当下一列的神经元被某自动波点火又熄火以后，也将对应的自动波强度置为∞。若I产生的所有自动波强度都为∞，则该自动波已无法再前进，因此将I熄火。

下面给出采用ACNN求解MSCP问题的步骤。

//t：网络的迭代时刻。

由以上算法可以遍历所有从Start到End满足约束条件的路径，从而获得最优的MCSP，对应地得到最优的MPSoC划分方案。为了减少ACNN的求解时间，也可以限定算法的最大迭代次数或Power的更新次数，获得满足约束的次优解。

3 应用实例

MPSoC平台的组件库以及由本实例所构造的赋权有向图参见文献[10]。给定不同的系统成本和实时性约束，分别用ACNN求解从顶点Start到终点End的最短路径，得到的优化结果如表1所示。

表1 不同约束下的优化结果

当Cmax=1 500 元和Tmax=200 ms时，获得的功耗最优MPSoC划分解为SP=(Core12, Core23, Core33,Core44, Core54, Core63)，对应的功耗为1.53 W，除τ1外的任务模块均采用硬件实现。

当改变约束为Cmax=1 000 元和Tmax=700 ms时，ACNN获得了另一个不同的MPSoC划分结果，功耗为1.73 W。与上次的选择不同，τ2和τ3用硬件实现，其他的4个模块采用软件实现。

以第2组约束为例，在ACNN首次获得受约束路径时，各神经元的点火与熄火过程如表2所示。

表2 ACNN神经元点火与熄火过程

文献[10]提出一个采用PCNN的SoC划分算法，同样是基于自动波的传播机制。用PCNN[10]求解表1中不同约束下的MPSoC划分，获得的结果与ACNN算法相同，但是要耗费数十倍的迭代时间，如表3所示。表中的求解时间以获得受约束最优路径的网络迭代次数表示。分析其原因，是因为PCNN中自动波在两个神经元间的传播时间与神经元间的连接强度成正比，求解效率较低。ACNN中，自动波在相连接神经元间的传播只需要一次迭代，与神经元间的连接强度(对应构造图中有向边的权值)无关，所以求解速度很快。

表3 ACNN与PCNN求解时间对比

4 结 论

针对基于可重用组件的MPSoC平台中成本和实时性约束的低功耗软硬件划分问题，本文提出了一种新的ACNN求解算法。

该文算法具有高度的并行性，ACNN无需训练和设置参数，可以获得问题的全局最优解。ACNN的网络和神经元结构简单，易于用VLSI硬件实现，可推广到大规模的MPSoC系统设计中。如国外的研究人员已经用电子阵列芯片实现了32×32的PCNN[7]。与PCNN相比，ACNN的神经元结构更简单，更容易实现，可以显著降低运行时间，具有较高的求解效率，是一个很有前景的优化手段。

另外，本文虽然将功耗作为优化目标，将成本和时间作为约束条件，但也可将成本作为优化目标，功耗作为约束条件，由于MPSoC的总成本仍然具有累加性，则本文的算法仍然适用；将功耗、成本等特性分配相应的权重，每个组件得到一个总的特性值，只要MPSoC的系统优化目标仍然是累加的，本文的算法同样可用于此类多目标的最优软硬件划分。

[1] WOLF W, JERRAYA A A, MARTIN G. Multiprocessor system-on-chip (MPSoC) technology[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(10): 1701-1713.

[2] JERRAYA A A, WOLF W. Multiprocessor systems on chips[M]. San Francisco: Elsevier Morgan Kaufmann, 2005.

[3] ARATO P, MANN Z, ORBAN A. Algorithmic aspects of hardware/software partitioning[J]. ACM Transactions on Design Automation of Electronic Systems, 2005, 10(1):136-156.

[4] ELES P, PENG Z, KUCHCINSKI K, et al. System level hardware/software partitioning based on simulated annealing and tabu search[J]. Design Automation for Embedded Systems, 1997, 2(1): 5-32.

[5] ZHANG Y, LUO W, ZHANG Z, et al. A hardware/software partitioning algorithm based on artificial immune principles[J]. Applied Soft Computing, 2008, 8(1): 383-391.

[6] GUO B, WANG D, SHEN Y, et al. Hardware-software partitioning of real-time operating systems using hopfield neural networks[J]. Neurocomputing, 2006, 69(16-18):2379-2384.

[7] JOHNSON J L, PADGETT M L, MICOM U S, et al. PCNN models and applications[J]. IEEE Transactions on Neural Networks, 1999, 10(3): 480-498.

[8] 董继扬, 张军英, 陈 忠. 自动波竞争神经网络及其在单源最短路问题中的应用[J]. 物理学报, 2007, 56(9): 5013-5020.DONG Ji-yang, ZHANG Jun-ying, CHEN Zhong.Autowave-competition neural network and its application to the single-source shortest-paths problem[J]. Acta Physica Sinica, 2007, 56(9): 5013-5020.

[9] ZHAN J, XIONG G. Optimal hardware/software co-synthesis for core-based soc designs[J]. Journal of Systems Engineering and Electronics, 2006, 17(2): 402-409.

[10] CHANG Z, XIONG G. Hardware/software partitioning of core-based systems using pulse coupled neural networks[C]//Advances in Neural Networks, ISNN 2007. [S.l.]:[s.n.], 2007: 1015-1023.