（计算机科学与技术专业论文）高阶路由器交换结构设计与分析.pdf

国防科学技术大学研究生院工学硕士学位论文 摘要 随着微电子技术和信号发射技术的发展，串行链路成为有效的信号传输方式。 高速串行链路的使用可以大幅度减少路由器芯片的引脚数目，导致高阶路由器的 实现成为可能。此外，从具有代表性的高性能计算机统计数据来看，路由器的端 口数朝着越来越大的方向发展，使用高阶路由器是互连网络的发展趋势。由高阶 路由器构成的互连网络只需要几个跳步( h o p ) 就可以连接成千上万个处理节点， 获得更低的延迟和更低的成本。 本文首先对各种路由器交换结构进行了分析，总结了各种交换结构的优势与 存在的不足。深入研究了6 4 端v i 的高阶路由器y a r c 的交换原理、组成结构、仲 裁流程，总结在高阶路由器设计上使用t i l e 的优势。 本文着重研究了胖树网络最优路由策略对路由器内部流量关系的影响。在此 基础上，对3 2 阶路由交换芯片的各种端口分配方案进行了比较分析，提出了行列 均匀离散分配方案和优化的行列均匀离散分配方案，使流量在片内均衡分布，提 高交换结构的性能。 本文设计实现了一个3 2 端口的高阶交换芯片$ 3 2 ，提出了一种适用于3 2 端口 交换芯片的双端口瓦片2 p o r t t i l e ，设计了一种基于逻辑端1 ：3 的路由变换机制。对 $ 3 2 的交换结构，流水线设置，路由变换策略，8 8 c r o s s b a r 实现等方面进行了详 细阐述。构建了网络仿真模型，仿真结果表明，在通信局部性条件下，行列均匀 离散分配方案和优化的行列均匀离散分配方案能够有效降低报文延迟，提高网络 吞吐率。 主题词：高阶路由器，t i l e 交换结构，端口分配，胖树网络 第i 页 国防科学技术大学研究生院工学硕士学位论文 a b s t r a c t a d v a n c e si nm i c r o e l e c t r o n i c sa n ds i g n a l i n gt e c h n o l o g yh a v ee n a b l e ds e r i a l i z e d t r a n s m i s s i o na sa ne f f i c i e n t l yt r a n s m i s s i o nm o d e u s i n gh i g h - s p e e ds e r i a l i z e d l i n kw i l l l a r g e l yd e c r e a s er o u t e r sp i nn u m b e r ，a n dm a k et h ei m p l e m e n t a t i o no fah i g h - r a d i x r o u t e rp o s s i b l e f u r t h e r m o r e ，s t a t i s t i c so ft y p i c a lh i g hp e r f o r m a n c ec o m p u t e r ss h o w s t h a tt h en e t w o r kr a d i xi n c r e a s es i g n i f i c a n t l yo v e rt i m ea n du s i n gh i g h - r a d i xr o u t e ri st h e t r e n do fi n t e r c o n n e c t i o nn e t w o r k s i n t e r c o n n e c t i o nn e t w o r k sb a s e do nh i g h - r a d i xr o u t e r o n l yn e e ds e v e r a lh o p st oj o i n tt h o u s a n d su p o nt h o u s a n d sp r o c e s s o rn o d e s ，t h u s r e d u c i n gp a c k e td e l a y sa sw e l la st h eo v e r a l lc o s to f an e t w o r k i nt h i sp a p e r , w ef i r s ta n a l y s i st h ev a r i o u se x i s t i n gs w i t c h i n gf a b r i c s ，s u m m a r i z i n g t h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s w et h e ni n - d e p t hs t u d ya6 4 一p o r th i # r a d i xr o u t e r n a m e dy a r c t h es w i t c h i n gt h e o r y ，c o n s t i t u t i o nf a b r i ca n da r b i t r a t i o np r o c e d u r eo f y a r ca l ea l ld i s c u s s e d w ep o i n to u tt h a ti ti sa p p r o p r i a t et ou s et i l ei nt h ed e s i g no f a l l i g h - r a d i xr o u t e r 1 1 1 er o u t e r si n t e r n a lt r a f f i cu n d e ro p t i m a lr o u t i n gi n f a t - t r e en e t w o r ki sa l s o r e s e a r c h e d b a s e do ni n t e m a lt r a f f i c ，w et h e nm a k eac o m p a r i s o no ns o m ep o r t a l l o c a t i o np o l i c i e so fa3 2 p o r ts w i t c hc h i p w ep r o p o s e dt w oi m p r o v e ds w i t c h i n g f a b r i c ，b o t ho fw h i c hc a nm a k er o w sa n dc o l u m n su n i f o r m l yd i s t r i b u t e d ，m a k i n g i n t e r n a l 仃a f f i cb a l a n c e da n di m p r o v i n gs w i t c h i n gp e r f o r m a n c e ah i g h r a d i xs w i t c h i n gc h i pn a m e d $ 3 2i si m p l e m e n t e d d u r i n gt h ed e s i g no f $ 3 2 ， ad u a l 。p o r tt i l ef a b r i ca n dal o g i c p o r tb a s e dr o u t i n gt r a n s f c r mm e c h a n i s ma r ep r o p o s e d w ed e s c r i b et h es w i t c h i n gf a b r i c ，p i p e l i n ed e s i g n , r o u t i n gt r a n s f o r mm e c h a n i s m ， c r o s s b a ri m p l e m e n t a t i o na r t ss oo nd e t a i l e d l y w ec o n s t r u c ta ni n t e r c o n n e c t i o nn e t w o r k b a s e do n $ 3 2s w i t c h i n gf a b r i c 1 1 1 es i m u l a t i o nr e s u l td e m o n s t r a t e st h a to u rt w o p r o p o s e dp o l i c i e sc a na c h i e v eb e t t e rp e r f o r m a n c e ，e s p e c i a l l yu n d e rc o m m u n i c a i t o n l o c a l i t yc o n d i t i o n k e yw o r d s ：h i g h r a d i xm u t e r ，t i l es w i t c h i n gf a b r i c ，p o r ta l l o c a t i o n ，f a t - t r e e n e t w o r k 一_ 一一 第i i 页 国防科学技术大学研究生院工学硕士学位论文 表目录 表4 1t i l e 交换结构的行列配置3 4 表4 23 2 阶路由交换芯片实际流量对照表3 8 表4 33 2 阶路由交换芯片端口连续分组定义表3 9 表4 46 4 阶y a r c 端口分组定义表4 l 表4 53 2 阶路由交换芯片端口类y a r c 分组定义表4 1 表4 63 2 阶路由交换芯片端口行列均匀离散分配表4 3 表4 73 2 阶路由交换芯片端口优化的行列均匀离散分配表4 4 表5 1 物理端口与逻辑端口映射表5 4 第1 v 页 国防科学技术大学研究生院工学硕士学位论文 图目录 图1 1 分布式存储多处理机体系结构示意图1 图2 1 带输入缓冲的c r o s s b a r 1 0 图2 2 带输出缓冲的c r o s s b a r 。10 图2 3 组合输入一输出缓冲c r o s s b a r 1 1 图2 4v o q b c s 交换结构1 2 图2 5c i x o b 交换结构1 4 图2 6y a r c 芯片8 x 8 瓦片阵列【12 1 1 5 图2 7 单个t i l e 的结构16 图2 8 行总线组织结构1 7 图2 9 列通道组织结构18 图2 1 0 输入端口第一级仲裁1 9 图2 1 1 第二级仲裁行列交换2 0 图2 1 2 输出端口选择2 0 图3 1 二叉树和二叉胖树拓扑结构2 1 图3 2 与图3 1 ( b ) 近似的结构2 l 图3 34 - p o r t3 - t r e e ( f t ( 4 ，3 ) ) 结构【3 1 】2 2 图3 4s u b f t ( m ，1 ) 和s u b f t ( m ，) 结构【3 1j 。2 3 图3 5f t ( m ，n ) 的结构【3 1 】2 4 图3 6f t ( 8 ，2 ) 拓扑结构2 7 图3 7f t ( m ，2 ) 的一个最优路由算法【3 1 】2 8 图3 8f t ( 8 ，3 ) 拓扑结构3 0 图3 9 刀沏，3 ) 的最优路由算法【3 1 1 3 1 图4 1 基于t i l e 的3 2 x 3 2 交换结构3 2 图4 2t i l e 交换结构另一种实现方式3 5 图4 3 完全x b a r 流量关系3 6 图4 4 非根交换节点中的实际流量关系3 7 图4 5 最优路由策略下非根交换节点中的实际流量关系3 7 图4 63 2 阶t i l e 交换结构端口分配图一3 9 图4 7x b a r 内部流量关系一。3 9 图4 8x b a r 内部流量关系二4 0 图4 9x b a r 内部流量关系三4 0 第v 页 国防科学技术大学研究生院工学硕士学位论文 图4 1 0x b a r 内部流量关系四4 0 图4 1 13 2 阶t i l e 交换结构端口分配图二4 2 图4 1 2 a r 内流量关系4 2 图4 1 3x b a r 内流量关系4 2 图4 1 4t i l e 交换结构端口分配图三4 3 图4 1 5x b a r 内流量关系六4 4 图4 1 6t i l e 交换结构端口分配图四4 5 图4 1 7x b a r 内流量关系七4 5 图5 13 2 端口交换芯片基本视图4 7 图5 2 $ 3 2 端口逻辑框架4 8 图5 3s 3 2 交换结构框架。4 9 图5 4 双端口瓦片2 p o r t t i l e 结构5 0 图5 5 $ 3 2 交换结构流水线示意图。5 1 图5 6c r o s s b a r 逻辑端口编号示意图5 3 图5 7 基于物理端口的源路由场5 5 图5 8 基于逻辑端口的源路由场5 5 图5 98 x 8 c r o s s b a r 基本框架5 5 图5 1 00 m n e t + + 模型结构。5 8 图5 1 1t i l e 输入端口模块结构5 9 图5 1 2t i l e 的输出端口模块5 9 图5 13s u b s w i t c h 模块结构。6 0 图5 1 4s u b s w i t c h 端口模块结构。6 0 图5 1 5 目标节点局部性分布条件下的通信性能6 3 图5 1 6 目标节点均匀分布条件下的通信性能6 3 第v l 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：直险整由墨銮逸结抱遮让生金盘 学位论文作者签名： 蔓塾耸 日期： 2 呷年f 月f 乡日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 直睑整由墨塞搀丝捡遮让皇金堑 学位论文作者签名： 童望釜 日期： 2 a d 7 年f 月眵日 作者指导教师签名：二3 迕 匿日期：汐c ，7 年f 月哆日 国防科学技术大学研究生院工学硕士学位论文 第一章绪论 1 1 课题研究背景 现代科学的发展依靠理论研究、科学实验与计算技术三种重要手段，其中计 算技术的发展带来了理论研究的深入、科学实验速度的加快和实验成本的降低， 成为人类科学研究必不可少的方法之一。 随着微电子技术的不断发展，微处理器的运算速度3 0 多年来提高了6 个数量 级。但是，单机的性能仍然满足不了来自科学、工程、商业等应用领域对计算能 力的需求。使用多个处理器的大规模并行处理技术为高性能计算机( h i g h p e r f o r m a n c ec o m p u t e r ，简称h p c ) 的实现提供了解决方案。高性能计算机技术是 整个信息技术的制高点，一直以强大的辐射力带动着信息技术的发展。继“加速 战略计算创新( a s c i ) 计划【l 】之后，美国国防部高级研究计划局( d a p p a ) 在 科学论证、严密组织下，又提出一项高性能计算机研究计划“高产出率计算 系统( h p c s ) 2 1 ，h p c s 旨在填补起始于8 0 年代的h p c 技术与未来的新概念计 算之间的空隙，以取得新结构、新技术、新器件、新工艺的突破性进展，将高性 能计算机技术的研究推向新的高潮。 图1 1 分布式存储多处理机体系结构示意图 高性能计算机由一组处理节点组成，处理节点之间通过互连网络进行通信与 协作。高性能计算机硬件系统的发展也主要体现为处理节点和互连网络的性能提 高。一种典型的高性能计算机体系结构( 分布式存储多处理机) 如图1 1 所示。 1 1 1 互连网络成为h p c 的性能瓶颈 从上世纪8 0 年代以来，随着大规模集成电路技术的快速发展，微处理器( c p u ) 的性能提高基本上遵循了著名的摩尔定律每18 个月翻一番，这主要来源于三 个因素：电路速度、流水线深度和指令级并行。从现在的情况看，流水线设计已 第1 页 国防科学技术大学研究生院工学硕士学位论文 接近每一站8 1 6 个f 0 4 ( f a n o u t o f - f o u r ) 反相器延迟的最低下限【jj ，流水线级数 的增加即将终止。随着集成电路制造工艺进入深亚微米阶段，受功耗和制造成本 的限制，电路速度的增长也已经放缓。 为了保证性能的持续增长，目前的微处理器技术已经开始向单芯片多核( 如 i b mp o w e r 4 ) 、单芯片多线程( 如i n t e lp e n t i u m 4 ) 以及片上系统等方向发展。i n t e l 在其微处理器发展蓝图中指出，今后应用于不同领域的c p u 都将采用多核结构。 2 0 0 6 年推出的基于c o r e 构架的c o n r o e ( 酷睿2 ) ，处理器核基于p e m i u mm ，i n t e l 的数据表明c o n r o e 比上一代处理器在性能上提高了4 0 ，而功耗降低了4 0 。在 2 0 0 5 年国际固态电路会议( i s s c c ) 上，i b m 、s o n y 和t o s h i b a 首次公开介绍了被 称为片上超级计算机( s u p e r c o m p u t e r o n a - c h i p ) 的高性能处理芯片e l l l 4 】。 c e l l 可以在4 g h z 的频率下工作，峰值浮点运算速度为2 5 6 g f l o p s ，支持完全符合 i e e e7 5 4 标准的双精度浮点运算，其速度约是单精度的十分之一，为2 5 3 0 g f l o p s 。 即使这个速度，也达到了当前主流高性能微处理器的5 1 0 倍。由于这些新技术的 不断采用，在未来十几年之内，微处理器的性能提高还会按这种规律持续下型5 。 互连网络是高性能计算机系统中连接处理器、存储器、i o 设备的重要组成部 分，承担不同处理节点间的同步和通信。互连网络是影响整个高性能计算机系统 的性能和扩展性的重要因素。根据a s c i 计划对硬件系统的量化指标，要实现百万 亿次以上的计算能力，互连网络的延迟和带宽是必须首先解决的关键问题( 临近 节点访存延迟为3 0 0 5 0 0 个c p u 周期、带宽1 - 8 b f l o p ；远程节点的访存延迟为1 0 0 0 个c p u 周期左右、带宽1 b f l o p 左右) 。 微处理器技术的发展使得处理节点的计算能力迅速提高，也对互连网络的性 能提出了更高的要求。然而实际上，互连网络带宽的增长与微处理器性能的增长 有超过3 0 的差距，互连网络带宽每年以大约2 6 的速度增长，远低于处理器性 能每年5 9 的增长速度。预计到2 0 1 0 年，远程节点的访存延迟将达到9 0 0 0 个c p u 周期、带宽只能达到o 0 2 4 b f l o p ，而到2 0 2 0 年，远程节点的访存延迟将达到惊人 的6 7 0 ，0 0 0 个c p u 周期、带宽只能达到0 0 0 2 4 b f l o p l 5 1 。因此互连网络的延迟和带 宽已成为制约高性能计算机性能提高的瓶颈之一。 1 1 2 高速串行传输技术 分析最近几年t o p 5 0 0 高性能计算机互连网络技术可以看到，高性能互连网络 技术中最大的变化在于串行传输技术的成熟和大量使用。基于串行传输技术设计 的互连网络协议和产品大量出现，如1 0 g 以太网、i n f m i b a n d 、p c i e x p r e s s l 6 1 等， 目前高速串行传输已成为互连传输技术的主流。 传统的并行互连具有技术相对成熟、接口实现容易、传输带宽高、延迟小、 第2 页 国防科学技术大学研究生院工学硕士学位论文 成本相对较低等优点【7 】。但电信号传输在互连密度、时钟歪斜、功耗、抗干扰性、 传输距离等方面受限【8 】，进一步提高电信号的传输带宽面临“电子 瓶颈，难以满 足高性能计算对更高传输带宽、更长传输距离等方面的要求。相比并行互连，串 行传输方式通过将时钟编码在数据中传输，没有时钟歪斜问题，具有带宽高、传 输距离长、互连密度高、抗干扰能力强等优点。 在串行传输技术广泛使用之前，互连链路带宽的增长依赖两种手段：提高并 行链路的工作频率；增加并行链路的位宽。两种手段之间存在一定的矛盾，并行 链路位宽越高，链路间的s k e w 越大，要提高链路工作频率就非常困难。因而依赖 并行电链路在提高链路带宽方面已面临瓶颈，目前基于并行传输技术的互连链路 频率一般不超过8 0 0 m h z 。 串行传输技术的发展，使得网络带宽的增长能适应处理器接口带宽及存储器 带宽的增长，并且可以以可预见的方式不断提高互连链路带宽。基于串行传输技 术，提高互连链路带宽更为容易，方式更为多样，提高串行互连链路带宽的方式 包括： 1 、单路串行传输带宽不断提高，从最初2 5 g b p s ，逐渐发展到目前的6 g b p s ， 甚至1 0 g b p s 。 2 、在单条串行链路上使用d d r ( 单拍传输2 位数据) 或q d r ( 单拍传输4 位数据) 技术进一步提高单链路带宽，目前基于d d r 和q d r 技术的i n f i n i b a n d 技术均已开始产品化。 3 、多条串行链路并行使用：目前i n f i n i b a n d 支持4 x ，8 x ，1 2 x 的串行链路， p c i e x p r e s s 支持4 x ，8 x ，1 6 x 的串行链路，通过多路并行，能快速提高链路的 带宽，未来可能出现二维并行的多条串行链路，如2 x 2 4 路等。 4 、串行链路向更高带宽发展，还可以使用基于稀疏波分复用( c w d m ) 及密 集波分复用( d w d m ) 技术来进一步提高带宽。 我们认为串行传输技术的发展，在多个方面丰富了高性能互连网络的设计资 源，克服了高性能互连网络的设计瓶颈，为高性能互连网络技术的发展提供了新 的驱动力，表现在以下几个方面： l 、带宽资源：串行传输技术能提供更高、更易于扩展的网络带宽资源，克服 互连网络设计中的带宽瓶颈，实现互连网络带宽与处理器带宽及存储器带宽间的 均衡发展。 2 、p i n 资源：在互连芯片设计中，使用串行传输技术的端口在同等带宽下， 相比使用并行传输技术的端口需要很少的芯片引脚【9 1 ，而随着芯片设计制造工艺水 平的不断提高，p i n 资源已成为芯片设计中最为重要的资源和限制因素之一。 3 、网络端口资源：互连交换芯片的网络端口数量是制约互连网络拓扑结构设 第3 页 国防科学技术大学研究生院工学硕士学位论文 计的一个重要因素，由于串行传输技术需要的p i n 较少，因而互连交换芯片设计 中可以集成更多的互连端口，为互连网络设计提供丰富的网络端口资源。 4 、传输距离瓶颈：串行传输技术既可以采用电链路实现，也可以采用光链路 实现。当使用光链路实现时，在满足带宽要求的前提下，传输距离可以很长( 超 过5 0 m ) ，能够满足构建大规模互连网络系统的距离要求，而并行电链路在链路 高带宽和长距离之间也存在矛盾，难以适应构建大规模互连网络的需求。 5 、功耗瓶颈：使用基于光链路的串行传输技术，相对于并行电链路传输，能 极大地降低互连链路的功耗要求。 6 、可靠性和可维护性：基于串行传输技术技术设计的互连网络，需要更少的 互连线、更少的互连交换芯片，更小的互连网络直径，因而能显著提高互连网络 的可靠性和可维护性。 1 1 3 高阶互连交换芯片 根据w i l l i 锄j d a l l y 和j o h nk i m 1 0 】的推导，要想获得更低的网络延迟，网络的 最佳阶数k ，路由器总带宽b ，路由器转发延迟f ，节点数n ，报文长度l ，有如下 关系： 挑办= 等笋 随着高性能计算机的发展，尽管路由器转发延迟，不断减小，但总体上 b t rl o g n 呈不断增大的趋势，使得网络阶数k 向高阶( h i g h r a d i x ) 的方向发展。 三 受限于一些技术因素的限制，现有的路由交换芯片通常使用较小的端口密度， 如8 个端口【】。随着串行传输技术的成熟及a s i c 设计工艺水平的提升，设计高端 口密度或者说是高阶路由交换芯片的时机已趋于成熟，表现在以下几个方面： 1 、串行传输技术要求设计高阶路由交换芯片来降低互连系统延迟。串行传输 技术的一个较大的缺点就是串行传输技术的端口延迟较大。在同等互连规模的条 件下，需要使用高阶路由器来减小系统互连直径，通过减小互连跳步数来减小系 统互连延迟。 2 、串行传输技术的使用，只需要较少的互连交换芯片引脚，使得互连交换芯 片可以集成更多的互连端口。在使用并行互连链路的技术条件下，设计高带宽的 互连链路需要更多的j 枣片引脚，如设计3 2 位宽4 0 0 m h zd d r 链路，双向带宽为 6 4 g b s ，需要的引脚数为：3 3 位( 3 2 位数据+ l 位时钟) 2 ( l v d s ) x 2 ( 双 工) = 1 3 2 位。在此要求下，设计8 个双向端口即需要1 0 5 6 条引脚，进一步扩展 端口数量面临引脚瓶颈。而要实现相同近似的带宽，使用6 2 5 g b p s 8 l a n e s 的串 第4 页 国防科学技术大学研究生院工学硕士学位论文 行链路传输技术，需要的引脚数约为4 0 。在相同引脚规模下，使刷串行传输技术 设计的端口数超过2 4 。 3 、单引脚带宽的提升，使得使用较少的芯片引脚即可实现较高的端1 3 带宽。 理论上使用传统的并行电链路，也可以设计高阶的路由交换芯片，如使用1 6 位数 据位取代3 2 位数据位，可降低每端口的引脚需求，进而支持设计高阶路由交换芯 片，付出的代价是降低每个端口的位宽，由此带来的是端口带宽的下降，难以与 处理器带宽及访存带宽相匹配。而随着单引脚带宽的提升，使用串行传输技术， 较少的芯片引脚即可实现很高的端口带宽。 4 、a s i c 设计生产工艺水平的提升，如a s i c 工艺水平从1 3 u r n 提高到目前的 6 5 n m 水平，并正在向4 5 n m 工艺迈进。单个a s i c 芯片内可以集成的逻辑单元密 度飞速提高。理论上随着端口数的提高，a s i c 芯片的逻辑单元数量成线性增长或 成平方增长，a s i c 工艺水平的提升，使得芯片内逻辑资源不至于成为高阶路由交 换芯片设计的限制因素。 在串行传输技术的驱动下，高阶路由交换芯片成为最近几年高性能互连网路 发展的一个主流，c r a y 公司设计了6 4 端口3 链路的y a r c 芯片【1 2 】，m y r i n e t 公司 设计了3 2 端口x 4 链路的交换芯片【1 3 】，m a l l a n o x 公司设计了2 4 端口x 4 链路的 i n f m i b a n d 交换芯片1 1 4 】，s g i 公司正在设计1 6 端口x1 2 链路的交换芯片【1 5 】。 高阶路由交换芯片的优势有以下几点： 1 、通过提高单芯片的端口数量，能降低系统互连的直径，减小节点间通信的 步长，从而减小节点间通信延迟。 2 、通过提高芯片端口密度，减少互连系统中的互连节点数量，从而提高系统 的可靠性。 3 、高阶路由交换芯片提供更为丰富的互连端口资源，为互连拓扑结构设计提 供了更多的灵活性，可以设计更多冗余的链路，支持自适应路由，从而提高系统 的可靠性和可用性。 1 1 4 胖树拓扑结构 高性能计算机中互连网络的结构设计已较为成熟，比较常用的网络结构包括： m e s h i l6 1 、t o r u s 1 7 】、3 d t o r u s l l 引、f a t t r e e l l 9 1 、c l o s l 2 0 等。互连网络的结构设计主 要受到以下因素的约束： 1 、互连传输距离。在电并行链路情况下，互连传输距离受限，由此可能导致 互连网络结构设计受到较大的约束。而在串行链路传输条件，如果使用光传输技 术，则可以突破传输距离的限制。 2 、交换芯片的端口密度。端口密度较小带来两个方面的不利影响：( 1 ) 拓 第5 页 国防科学技术大学研究生院工学硕士学位论文 扑结构的设计灵活度较小；( 2 ) 网络直径较大，由此将导致网络延迟较大。 3 、网络直径。指的是互连网络中距离最远的两个节点间的跳步数。网络直径 越大，通常意味着系统的互连延迟越大。互连网络设计的目标之一就是减小网络 直径。 4 、等分带宽。指的是将互连网络分为等分的2 部分需要切断的互连链路数量。 等分带宽越高意味系统中任意2 点间的通信带宽越高，网络中存在的带宽瓶颈较 小。 5 、可扩展性。互连结构应具有良好的可扩展性。 串行传输技术可以较为容易地突破互连距离和带宽的限制，并且便于设计高 阶路由交换芯片，极大地丰富了互连的链路资源、带宽资源和端口资源，为互连 网络结构的设计提供了更高的灵活性。 在串行传输结合高阶路由交换芯片的前提下，设计胖树互连网络是一种较为 普遍而直接的选择，如m y r i n e t 公司基于3 2 端1 2 1 交换芯片设计实现了5 1 2 端口交 换机，其内部实现即为一个2 级胖树结构；m a l l a n o x 公司基于2 4 端口交换芯片设 计实现了2 8 8 端口的i n f i n i b a n d 交换机。c r a y 的b l a c k w i d o w 系统也支持胖树互连 结构。高阶路由交换芯片可以提供丰富的端口资源，相比低阶路由交换芯片，设 计出来的胖树网络可以足够胖、足够矮，具有以下优势。 1 、互连网络的直径较小。 2 、二分带宽高：在全胖树网络中，二分带宽等于端节点的互连带宽，互连网 络中完全不存在网络瓶颈。 3 、胖树网络提供了两节点之间的丰富的冗余路径，便于通过自适应路由技术 提高网络结构的可靠性和灵活性及实用带宽。 1 2 本文研究内容、意义和主要贡献 高性能互连网络是高性能计算机的重要组成部分。随着高性能计算机逐渐迈 向p f l o p s 量级，研究与之相匹配的高性能互连通信网络具有非常重要和现实的 意义。 我们将基于高阶互连交换芯片构建的互连网络称为高阶互连网络( h i g h r a d i x n e t w o r k ) 。高阶互连网络是目前高性能互连通信网络研究领域的重点和热点，其 关键技术包括： 1 、片内互连结构设计：在低阶互连交换芯片设计中，由于端口数较少，端口 之间可以通过c r o s s b a r 进行全互连，互连结构较为简单，实现难度较小。而在高 阶路由交换芯片中，如果使用c r o s s b a r 连接所有端e l ，将面临多方面的问题，第 一，c r o s s b a r 上的竞争和仲裁压力成倍增加，由于多输入端口竞争同一个输出端口 第6 页 国防科学技术大学研究生院工学硕士学位论文 导致的c r o s s b a r 吞吐率下降问题将更为严重。第二，c r o s s b a r 结构的可扩展性很差， c r o s s b a r 所消耗的交换资源随端口数的平方增长，当交换芯片内集成的端口数很多 时，将很快面临资源瓶颈。为此，必须研究适应高阶路由交换芯片的高效、简捷、 易扩展的片内交换结构，在逻辑复杂度、芯片交换延迟和性能之间取得较好的平 衡，是高阶路由交换芯片设计中的难点和重点。 2 、片内传输可靠性：随着互连端口数和片内互连规模的增大，在片内传输数 据的长度和带宽要求都进一步提高，高频片内数据传输的可靠性问题开始显现， 需要对高频数据的长线传输进行可靠性控制，这是片内交换带宽提高后出现的新 问题，需要进一步的研究。 3 、高阶互连网络中的路由策略研究。 4 、高阶互连网络性能评价。 本文的研究工作主要集中在以下几个方面： 1 、对路由器互连交换结构进行了深入、全面的分析和总结，对比分析各种交 换结构的优势与存在的不足，为设计新型互连交换结构打下基础。 2 、深入研究了6 4 端口的y a r c 路由器的交换原理、组成结构、仲裁流程， 总结y a r c 在高阶路由器设计上使用t i l e 的优势。 3 、研究适应高阶胖树网络的路由策略，分析在确定性最优路由策略条件下， 胖树网络的数据流向和连接关系，作为t i l e 交换结构优化的依据。 4 、创造性地将胖树路由策略对路由器中实际发生的流量关系分析引入到交换 结构效率分析中，深入分析了胖树结构及胖树路由策略对网络路由器片内流量的 影响，并根据实际流量分布，对3 2 阶t i l e 交换芯片的内部交换结构进行了比较分 析，提出了行列均匀离散分配方案和优化的行列均匀离散分配方案。 5 、实现了一个3 2 端1 ：3 的高阶交换芯片$ 3 2 ，提出了一种双端口瓦片2 p o r t t i l e ， 设计了一种基于逻辑端口的路由变换机制。对$ 3 2 的交换结构，流水线设置，路 由变换策略，8x8 c r o s s b a r 实现等方面进行了详细阐述。采用o m n e t + + 离散事件 模拟平台，建立仿真模型，实验结果表明，本文提出的行列均匀离散分配和优化 的行列均匀离散分配具有较大的性能提高，尤其是在通信具有局部性的时候。 1 3 论文组织结构 全文共分六章，各章节内容组织如下： 第一章绪论。指出了课题的研究背景和意义、介绍了本文的主要研究内容。 第二章路由器互连交换结构分析。对路由器互连交换结构进行了分析和总 结，介绍了各种内部无缓冲的交换结构和内部有缓冲的交换结构的基本原理、性 能和实现代价：重点分析了当前非常有代表性的高阶片内交换结构一y a r c 的基 第7 页 国防科学技术大学研究生院工学硕士学位论文 于t i l e 的交换结构。 第三章胖树网络最优路由策略。介绍了二级胖树网络和三级胖树网络最优路 由策略，以及它们的数据流向和连接关系，作为t i l e 交换结构优化的依据。 第四章t i l e 高阶交换结构优化设计。本章详细分析了t i l e 交换结构在胖树网 络中的实际数据流向和连接关系，以此为指导，对y a r c 的t i l e 交换结构进行了 改进，提出了行列均匀离散分配方案和优化的行列均匀离散分配方案。通过改进， 能够使负载得到有效平衡，提高交换结构的性能。 第五章高阶交换结构设计与性能评测。对3 2 端口的高阶交换芯片$ 3 2 的设 计实现过程进行了详细说明，重点描述了$ 3 2 的交换结构，双端口瓦片2 p o r t t i l e ， 基于逻辑端口的路由变换，8 8 c r o s s b a r 实现等。用o m n e t + + 仿真环境构建了网 络仿真模型，仿真结果表明，在通信局部性条件下，行列均匀离散分配方案和优 化的行列均匀离散分配方案能够有效降低报文延迟，提高网络吞吐率。 第六章结束语。对本文的研究工作进行了总结，并展望了进一步的研究方向。 第8 页 国防科学技术大学研究生院工学硕士学位论文 第二章路由器互连交换结构分析 本章我们对路由器互连交换结构进行较为全面的分析和总结。在低阶路由器 中，通常采用c r o s s b a r 交换结构，本章对c r o s s b a r 结构的多种实现方式进行了介 绍和分析。在高阶路由器中，比较典型的是基于t i l e 的交换结构，本章对y a r c 的t i l e 交换结构进行了深入的研究和分析。 2 1c r o s s b a r 交换结构 c r o s s b a r 是一种非常经典的交换结构，本文对其基本原理不做详细介绍，在下 文中将结合不同的c r o s s b a r 类型进行简单说明。根据c r o s s b a r 中是否有缓冲区及 缓冲区所处的位置，我们对c r o s s b a r 进行了分类，并对其中应用较为广泛的几种 类型进行了简单介绍。 按c r o s s b a r 内部是否有缓冲区可以将c r o s s b a r 分为2 大类，即内部无缓冲的 c r o s s b a r 和内部有缓冲的c r o s s b a r 。前者又可以分为( 1 ) 带输入缓冲的c r o s s b a r ； ( 2 ) 带输出缓冲的c r o s s b a r ；( 3 ) 组合输入一输出缓冲的c r o s s b a r 。内部有缓 冲区的c r o s s b a r 可分类为：( 1 ) v o q b c s 交换结构( 2 ) c i x o b 交换结构。 2 1 1 带输入缓冲的c r o s s b a r 带输入缓冲的c r o s s b a r 在其输入端有缓冲队列，交换结构没有内部加速，每个 输入端一次至多只能发送一个报文，每个输出端口一次最多只能接收一个报文， 如图2 1 所示。如果输入缓冲队列采用f i f o 策略处理报文，则每个时钟周期只有队 列头部的报文参与输出端口的竞争。当队列头部的报文竞争输出端口失败时，该 队列后边的报文都将被阻塞，即使此时它们的目的端口是空闲的，这些报文也不 能跳过头部报文参与交换，这种现象被成为h o l ( h e a do f l i n e ) 现象。h o l 现象 造成带输入缓冲的c r o s s b a r 数据吞吐率下降，性能饱和点为5 8 6 【2 1 1 。 使用虚拟输出队列o q ) 能够消除h o l 阻塞，每个输入缓冲器被划分为n 个 队列，每个队列对应一个输出端口。一个报文到达输入端之后，根据其目的端口 把该报文放到相应的v o q 队列中。调度器根据所有v o q 的队头报文进行调度选 择，将报文交换出去。由于不存在报文被去往不同目的端口的报文阻塞的情况， 消除了h o l 阻塞。v o q 机制的引入，使得带输入缓冲交换结构的性能主要依赖 于调度算法，选择适当的算法，数据吞吐率能够从5 8 6 提高到1 0 0 。但是当n 逐渐增大时，调度匹配算法将占用仲裁的绝大部分时间，且连线复杂度、延迟都 将变得不具有实用性，因此，带输入缓冲的c r o s s b a r 不适用于高阶路由器的设计。 第9 页 国防科学技术大学研究生院工学硕士学位论文 输入0 输入l 输入n 1 1 j 1r 1 rr 输出0 输出1 输出n 1 图2 1 带输入缓冲的c r o s s b a r 2 1 2 带输出缓冲的c r o s s b a r 带输出缓冲的c r o s s b a r 在每个输出端设置缓冲队列，某个时间槽内到达输入 端的报文，在下一个时间槽到来之前，都被交换到输出端。例如，加速比为n 的 c r o s