《计算局域性可知的片上多核系统互联拓扑结构--计算机工程》由会员分享，可在线阅读，更多相关《计算局域性可知的片上多核系统互联拓扑结构--计算机工程（6页珍藏版）》请在金锄头文库上搜索。
1、基金项目：基金项目：国家教育部博士点基金（ 20070007070）作者简介：作者简介：刘彩霞，女（1973-） ，博士生，主要研究方向： 计算机体系结构。石峰，博士生导师，教授。乔宝军， 博士，讲师。M.Haroon，博士。宋红，博士，副教授 E-mail：计算局域性可知的基三片上多核互联拓扑计算局域性可知的基三片上多核互联拓扑刘彩霞，石峰，乔宝军，刘彩霞，石峰，乔宝军，M. Haroon， 宋红宋红（北京理工大学计算机科学技术学院，北京，100081）摘摘 要：要：文中提出一种基于计算局域性原理的互联网络评价标准：底层全互联，并利用该标准对新型基三多核体系（Triplet Based Ar
2、chitecture ，TriBA）的直接互联网络（Direct Interconnection Network，DIN）在计算速度、物理布局以及成本三个方面进行了性能评价。 结果表明，TriBA 互联体系具有层次性、可扩展性和递归性，其底层全互联的结构特性确 保了高效的通信局域性。是一种可以有效开发处理节点间组局域性的计算有效的互联策略。 所提出的 TriBA 基于 VLSI 实现的布局方案是切实可行的。 关键词：关键词：片上多核系统，局域性，互联网络，VLSI 布局Computationally Efficient Locality-Aware Interconnection Topolo
3、gy 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)【Abstract】 A new criterion in performance evaluation that is based on the concept of localit
4、y 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 point
5、s, 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 interconn
6、ection strategy that exploits group locality in processing nodes, the proposed VLSI layout is flexible. 【Keywords】 Multiprocessor, locality, interconnection network, VLSI layout 1 1 引言引言 片上多核系统（CMP）由于其具有的低设 计复杂度、高主频和高吞吐率的特性而成为未 来处理器体系发展的主流方向。CMP 是将各类 同构或异构的 IP (Intellectual Property)核 通过一定结构的互联网络集成到
7、同一块芯片上 的处理器设计技术，因而互连网络是构建 CMP 体系的关键因素。在过去的三十年中，已经提出了很多面向 CMP 的互连结构，如 2D Mesh， 二叉树以及超立方体等，关于这些网络的分析 评价可以参见文献。任何一种互联网络在投入使用之前都要经过分析评估，使用到的最重要 也是最经典的定量拓扑原理就是网络的局域性1。TriBA 体系中的处理节点与其邻近的三个节点在底层采用全互联结构，因而 TriBA 拓扑 结构优于 2D 拓扑（如 mesh、二叉树和超立方 体）的一点就在于它能够充分而有效的开发复 杂科学计算中的局域特性。 文中我们分析评估了面向CMP的基三 （TriBA）互联网络拓扑结
8、构的性能。首先我 们基于局域性原理提出一种互联网络评价标准： 底层全互联。然后利用该评价标准将TriBA2 体系与已被广泛接受的2D mesh和二叉树拓扑 进行了比较和评价。采用的计算模型与 Thompson 3为VLSI实现而设计的网格模型类似。 其次，我们提出了TriBA VLSI实现的物理布局 方案，并从面积和功耗角度对该布局方案进行 了可行性分析。最后，我们的评价结果表明， TriBA是一种可行的能够开发处理节点间组局 域性的计算有效的互联策略，具有层次性、对 称性、可扩展性以及拓扑结构简单、节点度数 低等特性。 文章的其它部分组织如下：文章的第二部 分给出了TriBA体系结构模型并定
9、义了底层全 互联评价标准，利用该标准进行了TriBA互联 体系的性能分析比较。文章的第三部分给出了 TriBA体系的VLSI布局布线方案及可行性分析。 文章的最后总结了我们的研究工作。 2 2TriBATriBA 互联体系结构互联体系结构.k=0k=1k=2k=3 k 层层迭迭代代后后总总节节点点数数 N=3k图图1.1. 基三网络互联体系基三网络互联体系TriBATriBATriBATriBA是一种新型CMP计算机体系，适用于 复杂嵌入式应用环境。TriBA中每一个处理核 节点都与和它邻近的三个节点底层全互联2。 TriBA网络是一种具有层次性的可扩展互连拓 扑结构，该结构的第0层是单个节点
10、，通过3条 通信链路将3个节点彼此互连形成一个三角形， 从而构成该结构的第1层，如图。1层网络是构 造TriBA的基本构件，利用该基本构件，通过 迭代函数族(IFS)可以构造出任意层次的 TriBA。假设该结构的迭代函数族为，将1层TriBA看作是1次迭代后321,FFFIFS的网络N N(1)，N N(k)表示k次迭代后得到的k层网 络，则TriBA的构造过程可以表述为：（1）U311)(lkkNN其递归构造过程为：在基本构件的基础上， 将每个节点用一个低层网络替代，从而得到更 高层的一个三角形网络结构。重复这一过程， 我们可以构造出满足应用需求的任意层次的 TriBA。图1给出的是一个经过
11、3次迭代，含有 27个节点的三层TriBA。 2.12.1 分形递归互联结构分形递归互联结构TriBA 基三互连是一种自相似嵌套结构(也 称递归结构)，节点内和节点间不同层次子网 与整个网络结构自相似，各层次互连结构完全 统一。这将为路由、软件任务调度等带来方便。TriBA 的递归结构使得它具有很强的可扩 展性5。按照 TriBA 的构造规律，可以将节点 连接构成规模更大，性能更高的 TriBA，其中 的节点可以是单个的处理节点，也可以是几个 节点连接而成的低层网络（即超节点），其递 归扩展方式如图 2(a)。这对于现有计算机系统 性能升级和大型软件开发(尤其是实时系统开 发)十分重要，如软件
12、设计出来后性能不能满 足应用需求时，则理论上可按上述方式升级系 统，通过硬件性能的提高弥补软件性能的不足， 而没有必要购置更高档次机器或重新开发软件；2D Mesh 虽然也可用作处理器内部核间、处理 器间、主板间等不同层次互连，但不同层次网 络连接在一起一般不会形成更大规模的 2D Mesh 结构，图 2(b)给出了 2D Mesh 结构的现 有扩展方案。如果将 2D Mesh 结构进行递归扩 展，其扩展方式如图 2(c)所示，这样也实现了 底层全互连、高层次互连随层次增高递减，但 显然硬件实现代价较高。因此 AMD 的 Barcelona 四核内没有采用这种结构。无论节点层次如何，其出度恒为
13、3，而且 带有子网的节点构成的大网络仍然是 TriBA互连结构，9核TriBA处理器3节点TriBA 处理器主板每个层次子网 出口均为2不同层次网络 出口均为3不同层次网络出 口均为3图图2(a)2(a) TriBATriBA体系递归扩展结构体系递归扩展结构16核2D Mesh 处理器所有内核构成的大网络结构不再是2D Mesh， 除除非非每每个个多多核核处处理理器器的的输输出出端端口口数数为为 然而当内核数较大时这在技术上存在困难内核数整个网络不再是 统一的2D Mesh结构4节点2D Mesh 处理器主板图图2(b)2DMesh2(b)2DMesh现有扩展结构现有扩展结构图图 2 2(c)
14、(c) 2D2D MeshMesh 递归扩展结构递归扩展结构2.22.2 低延迟、低成本底层全互联结构低延迟、低成本底层全互联结构定义 1：如果一个集合或子集合中的每一 个节点都通过一条独立的通信路径彼此互相联 接，则称这个集合或子集中的节点全互联。为了恒量一类网络拓扑结构其底层全互联 的程度，我们定义了层次化网络底层全互联率 CCR这样一个性能指标，根据底层全互联的定义， 则：（2）CCR =网网络络系系统统可可用用连连接接数数全全互互联联需需要要的的总总的的链链路路数数表 1 给出了利用表达式（2）计算得到的 TriBA 和其他几类网络拓扑结构的底层全互联 率及其底层全互联结构。其中实线代
15、表网络拓 扑连结中的路径，虚线表示为了达到全互联特 性而需要添加的路径。表表1 1 底层全互联程度及底层全互联结构底层全互联程度及底层全互联结构拓扑结构底层节 点数CCR底层全互联结构TriBA31（3/3）2D Mesh40.667（4/6）二叉树30.667（2/3）超立方 体（度 为 3）31（3/3）最底层节点采用全互连结构，较高层次网 络之间的连接链路相对较少，降低了网络复杂 度，减少网络本身对片上资源的占用，在通讯 效率和网络复杂度之间进行了较好的平衡。此 外底层全互联可以降低节点间通信延迟，避免资源竞争（因为任意两个节点间有独立的联结 路径）。文献研究表明， 2D Mesh 的平
16、均信息延迟为（N为节点数），以H-树形式)( N连接得二叉树的信息延迟也为，超立)( N方体网络拓扑的平均信息延迟时间为 ，那么相同的计算评估方法可以NN log/得出 TriBA 的平均信息延迟时间为，)( N 不劣于其它网络拓扑结构。图 3 中给出的各个 网络的吞吐率可以表明由于底层全互联结构， TriBA 的通信性能要好于 2D Mesh 结构和二叉 树结构。而且随着网络规模的增加，TriBA 的 通信性能增长较快，更适合于大规模片上系统。图图3 3 网络规模与吞吐率网络规模与吞吐率 为了恒量底层全互联成本，我们定义全互 联代价CCO： （3）CCO =全全互互联联通通道道数数底底层层节节点点数数根据定义可知，全互联代价CCO表示网络扩 展时底层全互联结构的成本需求，表示网络中 每增加一个节点，底层全互连结构对连接通道 数的增加需求。表 2 给出了根
