基于子集最优分配办法的片上系统优化*

张婉桥，陈　鑫，夏　欢（南京航空航天大学 电子信息工程学院，江苏 南京 210016）

基于子集最优分配办法的片上系统优化*

张婉桥，陈鑫，夏欢
（南京航空航天大学 电子信息工程学院，江苏 南京 210016）

在片上系统高速发展的今天，寻求高性能低功耗的设计架构是目前的最大需求。为了满足对架构愈发严格的要求，提出一套简单有效的片上系统优化方法。该方法通过优化算法将关联性强的设备放置在同一条总线上来降低转接桥的通信量，进而减小整个系统的延迟，得到高性能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数据量。

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，X⊂A，Y⊂B且|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）所示。

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

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

2.2系统算法优化

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

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

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

（4）重复步骤（2），直到所有的元素都被提取出来，最后会得到一系列的（′，′），（′，′），（′，′），…，（′），分别对应g1，g2，g3，…，gn。很明显注意到有一部分gi＜0。则将X和Y两个子集交换后整个系统外部通信量降低了。于是在这里需要确定k值来确保为最大值。注意到，当 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）所示。

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

图1　系统架构化优实例

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

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

4　结论

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

图2　算法时间复杂度探究

［1］PINTO A，CARLONI L P，SANGIOVANNI-VINCENTELLI A L.A methodology for constraint-driven synthesis of onchip 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.

图7　满载时输入电压和电流波形

4　结论

本文对UCC3818A工作原理进行了简要的分析；阐述了外围电路中关键元器件的参数的设计方法。结合UCC3818A的内部特性，对电路中电压环、电流环、乘法器等主要功能电路进行了理论设计。制作了600 W的APFC模块并对其理论设计进行了验证。结果表明，该模块特性可以满足PF要求在0.9以上的电动观光车充电器的要求。如果采用更高耐压的器件，将辅助电源的输入置于APFC的输出，可以避免本模块中因辅助电源引起PF值丢失，从而可以得到更高的PF值。

参考文献

［1］万辉，张捍东，黄丹.有源功率因数校正控制技术现状与发展［J］.电工电气，2013（3）：1.

［2］贲洪奇，张继红，刘桂花，等.开关电源中的有源功率因数校正技术［M］.北京：机械工业出版社，2010.

［3］UCC3817A/18A Bicmos PFC［EB/OL］.（2009-3-26）［2014-10-02］.http：//www.ti.com.cn/cn/lit/ds/symlink/ucc3818a.pdf.

［4］王建飞，付纯菲.基于UCC3818大功率APFC电源设计［J］.变频器世界，2013（8）：52.

［5］王居德，赵恒飞，刘颖力，等.铁硅铝磁芯升压电感的设计［J］.磁性材料及器件，2011（8）：53-54.

（收稿日期：2014-10-21）

作者简介：

张兴（1987-），通信作者，男，硕士研究生，主要研究方向：LED驱动、大功率铅酸电池充电器。E-mail：alexpowera@163.com。

秦会斌（1961-），男，博士，教授，博士生导师，主要研究方向：新型电子材料与器件、抗 EMI技术。

郭石磊（1984-），男，硕士研究生，主要研究方向：大功率逆变电源。

An optimal allocation of subsets methodology for system-on-chip architectures

Zhang Wanqiao，Chen Xin，Xia Huan
（School of Electronic and Information Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，China）

Nowadays，with the fast developing system-on-chip（SoC）technology，the essential requirements for structure design lie in high performance and low power consumption.In order to meet these increasingly urgent requirements，this paper proposed a simple system optimization method for SoC.By placing the highly relevance devices on the same bus to decrease the communication traffic between the transfer bridges.Therefore，the communication delay of the overall system is reduced，and achieve the high performance.For the sake of the practicability of the proposed method，this paper established a proposed SoC system.By comparing the improved system and the traditional one，the communication delay has been reduced obviously.

System-on-Chip（SoC）；system optimization；an optimal allocation of subsets；communication architectures

TN47

A

1674-7720（2015）06-0026-03

2014-10-24）

张婉桥（1989-），女，硕士研究生，主要研究方向：数字集成电路设计。

陈鑫（1982-），男，博士，副教授，主要研究方向：数模混合电路。

夏欢（1989-），男，硕士研究生，主要研究方向：数字集成电路设计。

国家自然科学基金（ 61106029 ）