摘  要： 在片上系统高速发展的今天，寻求高性能低功耗的设计架构是目前的最大需求。为了满足对架构愈发严格的要求，提出一套简单有效的片上系统优化方法。该方法通过优化算法将关联性强的设备放置在同一条总线上来降低转接桥的通信量，进而减小整个系统的延迟，得到高性能SoC架构。为验证该方法的可行性，最后建立一个SoC系统进行验证。该SoC系统经过优化后，系统事件传输的延迟时间明显减少。

　　关键词： 片上系统；系统优化；子集最优；通信模型

0 引言

　　随着片上系统System-on-Chip（SoC）的发展，业界开始追求在性能、功耗、成本三者之间的最佳平衡点。高性能SoC已成为IC界的焦点。

　　针对该问题，PINTO A等人对设备的接口和相应总线布局布线进行重新设计，使得系统的通信不同于之前的点对点通信方式[1]。PANDEY S等人则致力于找到相对高效的总线位宽与总线数目[2-3]，其方法是在综合时对总线上设备接口的缓冲宽度与深度进行权衡，进而提出一种时间离散的马尔科夫链。

　　在集成电路设计的系统架构研究主要从软件调度和硬件拓扑两个方面进行。其中，软件调度主要是通过对处理器指令调度的重新规划来提升各个处理器之间的通信流程。如Wang Yi重新安排事件调度[4]。参考文献[5]选用的是多层总线的模式。这个方向的研究还有在网格环境下[6]与群组架构下的[7]。

　　本文针对目前硬件拓扑方法实现复杂的问题，提出一套简单有效的优化办法，将侧重点放在系统总线之间设备的关联性上，通过优化算法将关联性强的设备放置在同一条总线上来降低转接桥的通信量，进而减小整个系统延迟。

1 系统建模

　　在系统模型中，每个设备作为一个顶点，设备之间的任务量用对应的权重值表示。该权重值代表两个设备之间的通信量。若任意两个设备Ci和Cj之间存在通信则通过相应的有向线段来表示，如（Ci，Cj）对应的权重值Weight（见式（1）），表示在事件传输过程中由设备Ci向Cj设备总共发送大小为Weight数据量。

　　Weight=Avg.size×trans.num（1）

　　2 系统优化

　　2.1 系统通信量定义

　　首先，假设设备总数为偶数。即设备集合S总共有2n个元素，则设备之间的通信矩阵为C=｛cij｝，i，j=1，…，2n且cii为0。i和j在这里分别代表着系统中任意两个设备。cij表示（Ci，Cj）和（Cj，Ci）的权重和，且cij为非负值，于是可以看出矩阵C为对称矩阵。

　　从而降低T的值，也就降低转接桥需要承载的通信量。假设存在子集X和Y，XA，YB且|X|=|Y|≤n/2，所以该算法重点是从A和B集合中分别确定要交换的X和Y的子集。

　　假设a∈A，则a与A集合的通信量定义为内部通信量Ia，a与B集合的通信量定义为外部通信量Ea，则：

　　同样地，假设存在b∈B，则外部通信量与内部通信量之差Dz=Ez-Iz，其中z∈S。并且假设t为整个集合S中除去与a和b有关的外部通信量总和，则整个系统的外部通信量如式（5）所示。

　　T=t+Ea+Eb-Cab（5）

　　当a和b互换之后，整个系统的外部通信量为T′，如式（6）所示。

　　T′=t+Ia+Ib+Cab（6）

　　于是a和b互换之后系统的外部通信量的下降为：

　　decline=T-T′=Da+Db-2Cab（7）

　　2.2 系统算法优化

　　通过下面的步骤对系统进行优化。

　　（1）先计算S集合中的每个元素的D值；

　　（2）选取ai∈A，bj∈B，使得相应的g1为最大值；

　　（3）假设在步骤（2）得到一对最大值对应为a1′和b1′，接下来计算除去这两个元素剩下元素的D值，即范围分别变为A-{a1′}和B-{b1′}。此时的D值可以通过下面的两式来计算：

注意到有一部分gi<0。则将X和Y两个子集交换后整个系统外部通信量降低了gi=G。于是在这里需要确定k值来确保gi=G为最大值。注意到，当gk+1≤0时便找到G的最大值所对应的k值，若满足k>0就表示交换X和Y两个子集就会使得外部通信量降为最低，同时也表明该转接桥的通信量已经达到局部最大优化值。

　　以X和Y两个子集交换之后重新组合的A′或B′集合为准，在其内部进行子集划分，继续从步骤（1）开始新的循环，直到优化完系统的每个转接桥。

　　特殊情况可以适当地补充空元素z，即z元素的Iz=0且Ez=0。补充完之后继续使用前面算法对元素的分布进行优化。

3 实验实例

　　为证明算法的可行性，以图1所示系统为例。如图1（a）所示，有a、b、c、d、e总共5个设备，参考第1节的建模。其系统对应的通信矩阵如式（11）所示。

　　C= 0 10 5 20 3510 0 5 0 0 5 5 0 0 2520 0 0 0 535 0 25 5 0（11）

　　设备优化前的排布如图1（a）所示，最优排列如图1（b）所示。

　　在第二节中提到过，转接桥传递的事件权重越小，则代表通过转接桥的数据总量就越小，相应地整个系统的事件传输的延迟时间也就越少。

　　但是当设备的个数增加时，穷举算法的时间复杂度呈指数方式增长，所以穷举算法不可取。然而采用该算法的时间复杂度为n2logn，并且随着设备数的增长，算法的运行时间如图2所示。由此可见该算法具有灵活高效性。

4 结论

　　越来越多的实践和研究表明，SoC系统级设计在整个SoC设计中占有非常重要的地位。本文在着力于解决SoC架构的优化问题，通过对系统问题规范的模型化，提出一种架构优化的方法。该方法通过动态分析可以优化SoC的系统设计，并且方法灵活，不拘于软件，实施起来相对简单。为验证算法的可行性，本文设置了5个模块组成的总线系统，实验结果证实该算法可以快速有效地减小系统通信的延迟周期，得到高性能SoC架构。

参考文献

　　[1] PINTO A， CARLONI L P， SANGIOVANNI-VINCENTELLI A L. A methodology for constraint-driven synthesis of on-chip communications[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2009， 28（3）：364 -377.

　　[2] PANDEY S， GLESNER M， MUHLHAUSER M. On-chip communication topology synthesis for shared multi-bus based architecture[C]. 2005 International Conference on Field Programmable Logic and Applications， IEEE， 2005：374-379.

　　[3] PANDEY S， ZIMMER H， GLESNER M， et al. High level hardware/software communication estimation in shared memory architecture[C]. IEEE International Symposium on Circuits and Systems， ISCAS 2005， IEEE，2005，1：37-40.

　　[4] Wang Yi， Liu Duo， Qin Zhiwei， et al. Optimally removing intercore communication overhead for streaming applications on MPSoCs[J]. IEEE Transactions on Computers， 2013， 62（2）：336-350.

　　[5] HSIU P， HSIEH C， LEE D， et al. Multilayer bus optimization for real-time embedded systems[J]. IEEE Transactions on Computers， 2012，61（11）：1638-1650.

　　[6] Zhu Qian， AGRAWAL G. Resource allocation for distributed streaming applications[C]. ICPP ′08. 37th International Conference on Parallel Processing， IEEE， 2008：414-421.

　　[7] Qun Xu C， Xue C J， Hu B C， et al. Computation and data transfer co-scheduling for interconnection bus minimization[C]. Design Automation Conference， ASP-DAC 2009. Asia and South Pacific， IEEE， 2009：311-316.