计算局域性可知的片上多核系统互联拓扑结构--计算机工程

计算局域性可知的基三片上多核互联拓扑刘彩霞，石峰，乔宝军，M. Haroon， 宋红（北京理工大学计算机科学技术学院，北京，100081）lcx@摘 要：文中提出一种基于计算局域性原理的互联网络评价标准：底层全互联，并利用该标准对新型基三多核体系（Triplet Based Architecture ，TriBA）的直接互联网络（Direct Interconnection Network，DIN）在计算速度、物理布局以及成本三个方面进行了性能评价结果表明，TriBA互联体系具有层次性、可扩展性和递归性，其底层全互联的结构特性确保了高效的通信局域性是一种可以有效开发处理节点间组局域性的计算有效的互联策略所提出的TriBA基于VLSI实现的布局方案是切实可行的关键词：片上多核系统，局域性，互联网络，VLSI布局Computationally Efficient Locality-Aware Interconnection Topology for Triplet-Based Multi-Processor System-on-Chip (MP-SoC) Liu caixia, Shi feng, Qiao baojun, M.Haroon, Song hong(School of computer science and technology, Beijing institute of technology, Beijing, 100081)lcx@【Abstract】 A new criterion in performance evaluation that is based on the concept of locality in an interconnection network, the “lower layer complete connect”， is proposed in this article. With this criterion, evaluations of the Direct Interconnection Network (DIN) of Triplet Based Architecture(TriBA) is presented. The comparison / evaluation is enumerated from three orthogonal view points, viz., computational speed, physical layout and cost. Our analysis concludes that TriBA has such characteristics as hierarchy, scalability and recursiveness， the complete connection characteristics assures its efficient communication locality. TriBA is a kind of computationally efficient interconnection strategy that exploits group locality in processing nodes, the proposed VLSI layout is flexible. 【Keywords】 Multiprocessor, locality, interconnection network, VLSI layout 1． 引言片上多核系统（CMP）由于其具有的低设计复杂度、高主频和高吞吐率的特性而成为未来处理器体系发展的主流方向。

CMP是将各类同构或异构的IP (Intellectual Property)核通过一定结构的互联网络集成到同一块芯片上的处理器设计技术，因而互连网络是构建CMP体系的关键因素在过去的三十年中，已经提出了很多面向CMP的互连结构，如2D Mesh，二叉树以及超立方体等，关于这些网络的分析评价可以参见文献任何一种互联网络在投入使用之前都要经过分析评估，使用到的最重要也是最经典的定量拓扑原理就是网络的局域性[1]TriBA体系中的处理节点与其邻近的三个节点在底层采用全互联结构，因而TriBA拓扑结构优于2D拓扑（如mesh、二叉树和超立方体）的一点就在于它能够充分而有效的开发复杂科学计算中的局域特性文中我们分析评估了面向CMP的基三（TriBA）互联网络拓扑结构的性能首先我们基于局域性原理提出一种互联网络评价标准：底层全互联然后利用该评价标准将TriBA[2]体系与已被广泛接受的2D mesh和二叉树拓扑进行了比较和评价采用的计算模型与Thompson [3]为VLSI实现而设计的网格模型类似其次，我们提出了TriBA VLSI实现的物理布局方案，并从面积和功耗角度对该布局方案进行了可行性分析。

最后，我们的评价结果表明，TriBA是一种可行的能够开发处理节点间组局域性的计算有效的互联策略，具有层次性、对称性、可扩展性以及拓扑结构简单、节点度数低等特性文章的其它部分组织如下：文章的第二部分给出了TriBA体系结构模型并定义了底层全互联评价标准，利用该标准进行了TriBA互联体系的性能分析比较文章的第三部分给出了TriBA体系的VLSI布局布线方案及可行性分析文章的最后总结了我们的研究工作 2．TriBA互联体系结构图1. 基三网络互联体系TriBATriBA是一种新型CMP计算机体系，适用于复杂嵌入式应用环境TriBA中每一个处理核节点都与和它邻近的三个节点底层全互联[2]TriBA网络是一种具有层次性的可扩展互连拓扑结构，该结构的第0层是单个节点，通过3条通信链路将3个节点彼此互连形成一个三角形，从而构成该结构的第1层，如图1层网络是构造TriBA的基本构件，利用该基本构件，通过迭代函数族(IFS)可以构造出任意层次的TriBA假设该结构的迭代函数族为，将1层TriBA看作是1次迭代后的网络N(1)，N(k)表示k次迭代后得到的k层网络，则TriBA的构造过程可以表述为： （1）其递归构造过程为：在基本构件的基础上，将每个节点用一个低层网络替代，从而得到更高层的一个三角形网络结构。

重复这一过程，我们可以构造出满足应用需求的任意层次的TriBA图1给出的是一个经过3次迭代，含有27个节点的三层TriBA2.1 分形递归互联结构TriBA基三互连是一种自相似嵌套结构(也称递归结构)，节点内和节点间不同层次子网与整个网络结构自相似，各层次互连结构完全统一这将为路由、软件任务调度等带来方便TriBA的递归结构使得它具有很强的可扩展性[5]按照TriBA的构造规律，可以将节点连接构成规模更大，性能更高的TriBA，其中的节点可以是单个的处理节点，也可以是几个节点连接而成的低层网络（即超节点），其递归扩展方式如图2(a)这对于现有计算机系统性能升级和大型软件开发(尤其是实时系统开发)十分重要，如软件设计出来后性能不能满足应用需求时，则理论上可按上述方式升级系统，通过硬件性能的提高弥补软件性能的不足，而没有必要购置更高档次机器或重新开发软件； 2D Mesh虽然也可用作处理器内部核间、处理器间、主板间等不同层次互连，但不同层次网络连接在一起一般不会形成更大规模的2D Mesh结构，图2(b)给出了2D Mesh结构的现有扩展方案如果将2D Mesh结构进行递归扩展，其扩展方式如图2(c)所示，这样也实现了底层全互连、高层次互连随层次增高递减，但显然硬件实现代价较高。

因此AMD的Barcelona四核内没有采用这种结构 图2(a) TriBA体系递归扩展结构 图2(b)2DMesh现有扩展结构 图2(c) 2D Mesh递归扩展结构2.2 低延迟、低成本底层全互联结构定义1：如果一个集合或子集合中的每一个节点都通过一条独立的通信路径彼此互相联接，则称这个集合或子集中的节点全互联为了恒量一类网络拓扑结构其底层全互联的程度，我们定义了层次化网络底层全互联率CCR这样一个性能指标，根据底层全互联的定义，则： （2）表1给出了利用表达式（2）计算得到的TriBA和其他几类网络拓扑结构的底层全互联率及其底层全互联结构其中实线代表网络拓扑连结中的路径，虚线表示为了达到全互联特性而需要添加的路径表1 底层全互联程度及底层全互联结构拓扑结构底层节点数CCR底层全互联结构TriBA31（3/3）2D Mesh40.667（4/6）二叉树30.667（2/3）超立方体（度为3）31（3/3）最底层节点采用全互连结构，较高层次网络之间的连接链路相对较少，降低了网络复杂度，减少网络本身对片上资源的占用，在通讯效率和网络复杂度之间进行了较好的平衡。

此外底层全互联可以降低节点间通信延迟，避免资源竞争（因为任意两个节点间有独立的联结路径）文献研究表明， 2D Mesh的平均信息延迟为（N为节点数），以H-树形式连接得二叉树的信息延迟也为，超立方体网络拓扑的平均信息延迟时间为，那么相同的计算评估方法可以得出TriBA的平均信息延迟时间为，不劣于其它网络拓扑结构图3中给出的各个网络的吞吐率可以表明由于底层全互联结构，TriBA的通信性能要好于2D Mesh结构和二叉树结构而且随着网络规模的增加，TriBA的通信性能增长较快，更适合于大规模片上系统图3 网络规模与吞吐率为了恒量底层全互联成本，我们定义全互联代价CCO： （3）根据定义可知，全互联代价CCO表示网络扩展时底层全互联结构的成本需求，表示网络中每增加一个节点，底层全互连结构对连接通道数的增加需求表2给出了根据表达式3计算得到的几种网络拓扑结构的底层全互联代价表2 底层全互连代价拓扑结构TriBA2DMesh二叉树立方体线性底层节点数34232CCO（通道/节点）11.51.510.5显然，TriBA互连网络是除2节点线形连接结构外全互联代价最低的，这在互连的硬件实现时具有十分重要的意义，因为通道数与用于实现通道硬件成本间呈指数关系，每增加一通道，全互连需要增加这个通道与所有其它通道的连接通讯。

2.4 结构清晰的递归编码方案TriBA体系具有明显的层次化递归特性，因而其节点编码也具有递归特性包含3k个节点的k层TriBA，根据其递归构造过程，其节点的编码方案描述如下：Ø k=0时，TriBA仅含一个节点，节点编码并不重要，可任意设定Ø k=1时，网络N(1)中有3个节点，每个节点的编码b1b0用二进制形式表示，分别为01、10和11，节点集V1={01,10,11}按照表达式(4)给出的链路连接规则将这3个节点的通信端口进行连接构成了1层TriBA的节点和链路编码，如图4所示 Ø 假设N(k-1)的节点编码和通信端口连接已经完成，N(k-1)的节点集记为Vk-1： （5）其中：tj为N(k-1)中的节点编码，标记为b2k-3b2k-4…b2i-1b2i-2…b1b0 （1≤i≤k-1） N(k-1)的3个外连端口为O01…01,010…10,O11…11将3个k-1层的TriBA网络按照第1节介绍的构造方法，遵从表达式（6）给出的链路连接规则可以构造出N(k) （6）则得到k层TriBA的节点集Vk： （7）其中：，，是N(k)中的节点的编码。

图4给出了按照上述节点编码方案和通信端口连接关系构造的含有9节点的2层TriBA的编码方案图4 TriBA递归结构的节点编码这种编码方案结构清晰，编码本身涵盖了网络的层次特性，能够大大简化路由过程中的运算此外，根据TriBA互连的自相似嵌套特点，可以简单地对每个Cell编码得到其标识ID，所有Cell的ID恰好形成了一张分布式存储的路由表这些编码可以十分简单地表示点到点，以及分组路由，硬件实现十分简单3 TriBA体系VLSI实现的布局方案及可行性分析片上互联网络的物理性能的评价应该包括两方面：芯片面积和功耗因为一个8核片上系统，其互联网络的功耗等于一个核的功耗，而其面积开销是三个核面积开销的总和连线的几何参数也影响功耗和功率密度3.1 连线模型在Thompson的VLSI模型中，一个网络可以表示成一个图节点对应处理元素（PE），边代表互联结构中的连线这个图被嵌入到一个2D Mesh网格中我们的模型使用了同样的理论，但有以下不同：Ø 处理单元没有按固定间隔放置在网格中而是布置成一个正三角形如图5，这和2D Mesh占据一样的方形区域，不同的是L2 Cache的放置图5 方形几何物理布局Ø 节点间的连接线可以水平走向或垂直走向，或者与网格线成60度角或120度角走向。

因此，在节点布局完善的情况下，TriBA至少需要三个布局层，否则需要四个图6 连接层：0，60或120度角我们在图7中针对TriBA体系给出了一种全新的节点布局方案最近的研究已经表明对角线连线可以用于VLSI布局[4][5]实验表明与曼哈顿体系相比较而言，Y-体系可以在一个四方形的芯片上得到30.7%的吞吐率提高，利用对角线布线法，网路长度减少36%同时每个网路路径延迟平均减少14ps这一技术适用于10层金属布局芯片的几何尺寸不仅和连接模式有关，也和VLSI技术有关在很多技术中，芯片尺寸是片上连线占用的面积总和，连线占用的面积可以利用连线模型评估图7(a) 2层TriBA正交布局(b)角连接图7(B) 2层TriBA角连接布局图7中的连线有两个明显的特性：首先，所有的连线长度相同，因而临近节点的路径延迟相同；其次，PEs对称放置，因而可以很好的布局在一个方形区域内正交连接布局方案可以在现有布局技术下实现TriBA，而更简洁的角连接布局方案在未来对角线连接技术应用于VLSI布局中时可以成为实现TriBA的更好的选择3.2 布局方案的面积功耗分析对TriBA的布局方案的面积和功耗的确定方法采用类似于文献[6]中提到的。

对TriBA的面积的估算利用类Power4乱序核作为处理单元PE，根据文献，一个Power4在65nm技术下所占面积为10mm2总线所占面积由联结的线数决定连接线所占的片上面积和总线宽度、线间有效间距以及线长有关其中线间距是一个随布局层不同而变化的因子，变化范围在0.2um-1.6um.之间为使我们的分析简单化，我们在评估面积时基于以下假设：总线宽度为常数64；线间距是一个恒定的值0.7对于角连接布局方案，其中对角线长是水平或垂直线长的1.154倍实验核的功耗为10W，包括漏电流表3给出了TriBA布局方案的面积-功耗性能以及与2D Mesh的比较表3 面积-功耗估算网络规模“N”链路数PE所占面积（mm2）PE功耗（W）连线功耗（mW）功耗节省比例MeshTriBAMeshTriBA3×31212909015317609×9144120810810184317723.8527×271404109272907290179711593411.3381×81129609840656106561017868814358520表3中可以看出，TriBA在VLSI实现时采用上述的布局方案其链路数少于2D Mesh结构，因而功耗性能优于2D Mesh结构，平均功耗性能加速比为11%。

其功耗优势在大规模系统中更明显（81×81规模的系统中功耗性能改善20%），因而比2D Mesh结构更适合于作为大规模片上系统的互连结构4．总结和未来的工作本文给出了基三片上多核系统互联体系及其性能分析比较结果表明，TriBA是一种层次化网络拓扑结构，其结构的递归特性使得系统扩展性很强；底层全互连结构确保了TriBA良好的计算性能和系统扩展的低成本，适于VLSI并行处理对角线布线方法的研究推进了TriBA的VLSI实现的可行性因此，TriBA可以作为未来多核系统的片上网络一种有效的互连结构，能满足高效的计算局域性、低成本互连以及低功耗片上布局参考文献：[1] Rakesh Kumar, Victor Zyuban_, Dean M. Tullsen, “Interconnections in Multi-core Architectures: Understanding Mechanisms, Overheads and Scaling”[P] // Proceedings of the 32nd International Symposium on Computer Architecture (ISCA’05), pp. 408-419, 2005. [2] Feng SHI, Weixing JI, Baojun QIAO et al., “A Triplet Based Computer Architecture Suporting Prarllel Object Computing” [P] // Proceedings of the Eighteenth IEEE International Conference on Application Specific Architectures and Processors ASAP, pp. 192-197, July 2007. [3] C. D. Thompson, "A complexity theory for VLSI" Ph.D. dissertation, Carnegie-Mellon Univ., Pittsburgh, PA, 1980.[4] Hongyu Chen, Bo Yao, Feng Zhou and Chung-Kuan Cheng, “The Y- Architecture: Yet Another On-Chip Interconnect Solution” [P] // Proceedings of the IEEE computer Aided Design of Integrated Circuits and Systems, Vol 24, Issue 4, Aril 2005, pages: 588-599. [5] Noriyuki Ito, Hideaki Katagiri, Ryoichi Yamashita, Hiroshi Ikeda etc., “Diagonal Routing in High Performance Microprocesor Design” [P] // Proceedings of the IEEE Emerging VLSI Technologies, 2006, pp. 624-629. [6] R. Kumar, K. I. Farkas, N. P. Jouppi et al., “Single-ISA Heterogeneous Multi-core Architectures: The Potential for Processor Power Reduction” [J] // In MICRO-36, Dec. 2003. 。