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

基金项目 基金项目 国家教育部博士点基金 20070007070 作者简介 作者简介 刘彩霞 女 1973 博士生 主要研究方向 计算机体系结构 石峰 博士生导师 教授 乔宝军 博士 讲师 M Haroon 博士 宋红 博士 副教授 E mail lcx 计算局域性可知的基三片上多核互联拓扑计算局域性可知的基三片上多核互联拓扑 刘彩霞 石峰 乔宝军 刘彩霞 石峰 乔宝军 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 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 2 TriBATriBA 互联体系结构互联体系结构 k 0 k 1 k 2 k 3 k 层层迭迭代代后后总总节节点点数数 N 3k 图图1 1 基三网络互联体系基三网络互联体系TriBATriBA TriBATriBA是一种新型CMP计算机体系 适用于 复杂嵌入式应用环境 TriBA中每一个处理核 节点都与和它邻近的三个节点底层全互联 2 TriBA网络是一种具有层次性的可扩展互连拓 扑结构 该结构的第0层是单个节点 通过3条 通信链路将3个节点彼此互连形成一个三角形 从而构成该结构的第1层 如图 1层网络是构 造TriBA的基本构件 利用该基本构件 通过 迭代函数族 IFS 可以构造出任意层次的 TriBA 假设该结构的迭代函数族为 将1层TriBA看作是1次迭代后 321 FFFIFS 的网络N N 1 N N k 表示k次迭代后得到的k层网 络 则TriBA的构造过程可以表述为 1 3 1 1 l kk NN 其递归构造过程为 在基本构件的基础上 将每个节点用一个低层网络替代 从而得到更 高层的一个三角形网络结构 重复这一过程 我们可以构造出满足应用需求的任意层次的 TriBA 图1给出的是一个经过3次迭代 含有 27个节点的三层TriBA 2 12 1 分形递归互联结构分形递归互联结构 TriBA 基三互连是一种自相似嵌套结构 也 称递归结构 节点内和节点间不同层次子网 与整个网络结构自相似 各层次互连结构完全 统一 这将为路由 软件任务调度等带来方便 TriBA 的递归结构使得它具有很强的可扩 展性 5 按照 TriBA 的构造规律 可以将节点 连接构成规模更大 性能更高的 TriBA 其中 的节点可以是单个的处理节点 也可以是几个 节点连接而成的低层网络 即超节点 其递 归扩展方式如图 2 a 这对于现有计算机系统 性能升级和大型软件开发 尤其是实时系统开 发 十分重要 如软件设计出来后性能不能满 足应用需求时 则理论上可按上述方式升级系 统 通过硬件性能的提高弥补软件性能的不足 而没有必要购置更高档次机器或重新开发软件 2D Mesh 虽然也可用作处理器内部核间 处理 器间 主板间等不同层次互连 但不同层次网 络连接在一起一般不会形成更大规模的 2D Mesh 结构 图 2 b 给出了 2D Mesh 结构的现 有扩展方案 如果将 2D Mesh 结构进行递归扩 展 其扩展方式如图 2 c 所示 这样也实现了 底层全互连 高层次互连随层次增高递减 但 显然硬件实现代价较高 因此 AMD 的 Barcelona 四核内没有采用这种结构 无论节点层次如何 其出度恒为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 c 2D2D MeshMesh 递归扩展结构递归扩展结构 2 22 2 低延迟 低成本底层全互联结构低延迟 低成本底层全互联结构 定义 1 如果一个集合或子集合中的每一 个节点都通过一条独立的通信路径彼此互相联 接 则称这个集合或子集中的节点全互联 为了恒量一类网络拓扑结构其底层全互联 的程度 我们定义了层次化网络底层全互联率 CCR这样一个性能指标 根据底层全互联的定义 则 2 CCR 网网络络系系统统可可用用连连接接数数 全全互互联联需需要要的的总总的的链链路路数数 表 1 给出了利用表达式 2 计算得到的 TriBA 和其他几类网络拓扑结构的底层全互联 率及其底层全互联结构 其中实线代表网络拓 扑连结中的路径 虚线表示为了达到全互联特 性而需要添加的路径 表表1 1 底层全互联程度及底层全互联结构底层全互联程度及底层全互联结构 拓扑 结构 底层节 点数 CCR 底层全互 联结构 TriBA3 1 3 3 2D Mesh4 0 667 4 6 二叉树 3 0 667 2 3 超立方 体 度 为 3 3 1 3 3 最底层节点采用全互连结构 较高层次网 络之间的连接链路相对较少 降低了网络复杂 度 减少网络本身对片上资源的占用 在通讯 效率和网络复杂度之间进行了较好的平衡 此 外底层全互联可以降低节点间通信延迟 避免 资源竞争 因为任意两个节点间有独立的联结 路径 文献研究表明 2D Mesh 的平均信息 延迟为 N为节点数 以H 树形式 N 连接得二叉树的信息延迟也为 超立 N 方体网络拓扑的平均信息延迟时间为 那么相同的计算评估方法可以 NN log 得出 TriBA 的平均信息延迟时间为 N 不劣于其它网络拓扑结构 图 3 中给出的各个 网络的吞吐率可以表明由于底层全互联结构 TriBA 的通信性能要好于 2D Mesh 结构和二叉 树结构 而且随着网络规模的增加 TriBA 的 通信性能增长较快 更适合于大规模片上系统 图图3 3 网络规模与吞吐率网络规模与吞吐率 为了恒量底层全互联成本 我们定义全互 联代价CCO 3 CCO 全全互互联联通通道道数数 底底层层节节点点数数 根据定义可知 全互联代价CCO表示网络扩 展时底层全互联结构的成本需求 表示网络中 每增加一个节点 底层全互连结构对连接通道 数的增加需求 表 2 给出了根据表达式 3 计算 得到的几种网络拓扑结构的底层全互联代价 表表2 2 底层全互连代价底层全互连代价 拓扑结构 TriBA2DMesh 二叉树立方体线性 底层节点数 34232 CCO 通道 节点 11 51 510 5 显然 TriBA 互连网络是除 2 节点线形连接 结构外全互联代价最低的 这在互连的硬件实 现时具有十分重要的意义 因为通道数与用于 实现通道硬件成本间呈指数关系 每增加一通 道 全互连需要增加这个通道与所有其它通道 的连接通讯 2 42 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 所示 源到目的节点的通信端口号 目的节点编码b1b0 源节点编码b1b0 mod 3 对于每个节点 编码为0的通信端口 0b1b0作为构造更高层TriBA的连接点 4 假设N k 1 的节点编码和通信端口连接已 经完成 N k 1 的节点集记为Vk 1 5 1 3 1 1 k j jk tV 其中 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 1 0101 10 1010 01 1 1111 10 1010 11 1 1111 01 0101 11 1 1 1 k k k k k k 则得到k层 TriBA 的节点集Vk 7 3 1 3 1 1 jm mjk k tsV 其中 是N k 中 1 Vsj 1 km Vt mj ts 的节点的编码 图 4 给出了按照上述节点编码方案和通信 端口连接关系构造的含有 9 节点的 2 层 TriBA 的编码方案 11 0110 011 00 211111 010 110 210 201 001 101 11 0110 011 11 11 211 11111 11 11 0110 01 001 01 11 0110 10 010 10 00 节点编码 11 10 节点编码 10 11 K 1 K 2 图图4 4 TriBATriBA递归结构的节点编码递归结构的节点编码 这种编码方案结构清晰 编码本身涵盖了 网络的层次特性 能够大大简化路由过程中的 运算 此外 根据 TriBA 互连的自相似嵌套特 点 可以简单地对每个 Cell 编码得到其标识 ID 所有 Cell 的 ID 恰好形成了一张分布式存 储的路由表 这些编码可以十分简单地表示点 到点 以及分组路由 硬件实现十分简单 3 3 TriBATriBA体系体系VLSIVLSI实现的布局方案及可行实现的布局方案及可行 性分析性分析 片上互联网络的物理性能的评价应该包括 两方面 芯片面积和功耗 因为一个8核片上 系统 其互联网络的功耗等于一个核的功耗 而其面积开销是三个核面积开销的总和 连线 的几何参数也影响功耗和功率密度 3 13 1 连线模型连线模型 在Thompson的VLSI模型中 一个网络可以 表示成一个图 节点对应处理元素 PE 边 代表互联结构中的连线 这个图被嵌入到一个 2D Mesh网格中 我们的模型使用了同样的理 论 但有以下不同 处理单元没有按固定间隔放置在网格中而 是布置成一个正三角形 如图5 这和2D Mesh占据一样的方形区域 不同的是L2 Cache的放置 图图5 5 方形几何物理布局方形几何物理布局 节点间的连接线可以水平走向或垂直走向 或者与网格线成60度角或120度角走向 因此 在节点布局完善的情况下 TriBA 至少需要三个布局层 否则需要四个 图图6 6 连接层 连接层 0 0 6060或或120120度角度角 我们在图7中针对TriBA体系给出了一种全 新的节点布局方案 最近的研究已经表明对角 线连线可以用于VLSI布局 4 5 实验表明与曼 哈顿体系相比较而言 Y 体系可以在一个四方 形的芯片上得到30 7 的吞吐率提高 利用对 角线布线法 网路长度减少36 同时每个网路 路径延迟平均减少14ps 这一技术适用于10层 金属布局 芯片的几何尺寸不仅和连接模式有 关 也和VLSI技术有关 在很多技术中 芯片 尺寸是片上连线占用的面积总和 连线占用的 面积可以利用连线模型评估 图图7 a 7 a 2 2层层TriBATriBA正交布局正交布局 b b 角连接角连接 L2 L2L2 图图7 B 7 B 2 2层层TriBATriBA角连接布局角连接布局 图7中的连线有两个明显的特性 首先 所有的连线长度相同 因而临近节点的路径延 迟相同 其次 PEs对称放置 因而可以很好 的布局在一个方形区域内 正交连接布局方案 可以在现有布局技术下实现TriBA 而更简洁 的角连接布局方案在未来对角线连接技术应用 于VLSI布局中时可以成为实现TriBA的更好的 选择 3 23 2 布局方案的面积功耗分析布局方案的面积功耗分析 对TriBA的布局方案的面积和功耗的确定方 法采用类似于文献 6 中提到的 对TriBA的面 积的估算利用类Power4乱序核作为处理单元 PE 根据文献 一个Power4在65nm技术下所占 面积为10mm2 总线所占面积由联结的线数决定 连接线所占的片上面积和总线宽度 线间有效 间距以及线长有关 其中线间距是一个随布局 层不同而变化的因子 变化范围在0 2um 1 6um 之间 为使我们的分析简单化 我们在 评估面积时基于以下假设 总线宽度为常数 64 线间距是一个恒定的值0 7 对于角连接 布局方案 其中对角线长是水平或垂直线长的 1 154倍 实验核的功耗为10W 包括漏电流 表3给出了TriBA布局方案的面积 功耗性能以 及与2D Mesh的比较 表表3 3 面积面积 功耗估算功耗估算 网络规 模 N 链路数PE所占面 积 mm2 PE功耗 W 连线功耗 mW 功耗节 省比例 Mesh 1 2 NN TriBA 1 0 3 l i i N MeshTriBA 3 3121290901531760 9 9144120810810184317723 85 27 271404109272907290179711593411 33 81 81129609840656106561017868814358520 表3中可以看出 TriBA在VLSI实现时采用 上述的布局方案其链路数少于2D Mesh结构 因而功耗性能优于2D Mesh结构 平均功耗性 能加速比为11 其功耗优势在大规模系统中 更明显 81 81规模的系统中功耗性能改善20 因而比2D Mesh结构更适合于作为大规模片上 系统的互连结构 4 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 SH