（通信与信息系统专业论文）基于格型拓扑结构的片上网络路由算法研究.pdf

摘要 随着半导体工艺技术的发展 电路设计的集成度不断提升 芯片的规模越来 越大 工作频率也越来越高 片上网络作为一种全新的集成电路体系结构可以解 决基于总线设计的片上系统带来的诸多问题 其中路由算法作为n o c 的一项关键 技术受到了各研究机构的广泛关注以及深入研究 由于路由算法在很大程度上决 定了分组的端到端时延以及整个网络的吞吐 这也直接影响到了n o c 的整体性能 所以如何基于简单的格型拓扑设计出具有优良时延和吞吐性能的路由算法是本文 的研究重点 本文首先对n o c 的产生背景 体系结构 关键技术做了简要的介绍 并针对 国内外的研究现状进行了总结 详细介绍了路由算法的分类 死锁 活锁及饥饿 的概念 并列举了典型的路由算法 接下来依照不同标准对路由算法的实现进行 了分类 结合算法的硬件实现 描述了几种分类各自的优缺点 并对常用于格型 m e s h 的x y 维序路由算法的不同实现方式进行分类对其路由计算模块进行设计 通过i s e 软件验证了输出端口的计算功能 进行了资源消耗的评估 在此基础之 上 本文借鉴了p a r t i a li n t e r c o n n e c t i o no f m e s hn e t w o r k s 格型拓扑结构的优势 结 合虚拟网络的概念 设计了一种对角虚拟网络d v n 路由算法 最后利用o p n e t 仿真软件对分组的路由过程进行仿真 对d v n 路由算法和c r o s s r o u t i n g 路由算法 以及用于m e s h 的x y 维序路由算法在不同流量模式下进行了仿真对比 针对端到 端时延和吞吐性能进行了评估 结果表明d v n 路由算法可以降低端到端的时延并 且提高吞吐 从而提升网络的整体性能 关键词 片上网络路由算法对角虚拟网络d v n a b s t 队c t w i t ht h ed e v e l o p m e n to fs e m i c o n d u c t o rt e c h n o l o g ya n dt h er i s i n go fc i r c u i t i n t e g r a t i o nl e v e l t h es c a l eo fc h i ph a sb e c o m el a r g e ra n dt h ew o r k i n gf r e q u e n c yi s i n c r e a s i n g n e t w o r k o n c h i p n o c w h i c hs e r v e sa san e wi n t e g r a t e dc i r c u i ts y s t e m s t r u c t u r e c a ns o l v et h ep r o b l e m sb r o u g h tb yt h eb u s b a s e ds y s t e m o n c h i p a sak e y t e c h n o l o g yo fn o cr e s e a r c h r o u t i n ga l g o r i t h mh a sb e e nr e s e a r c h e dw i d e l ya n dd e e p l y i nn u m e r o u sr e s e a r c hi n s t i t u t i o m i tp l a y sac r i t i c a lr o l ei nd e t e r m i n i n gt h ep e r f o r m a n c e o fn o ci nt e r m so fe n d t o e n dl a t e n c ya n dt h r o u g h p u t t h e r e b yi n d u c i n gd i r e c ti m p a c t s o nt h ep e r f o r m a n c eo ft h ew h o l es y s t e m t h e r e f o r et h ek e yo ft h i sd i s s e r t a t i o ni st o d e s i g nt h er o u t i n ga l g o r i t h mf o rs i m p l eg r i d b a s e dt o p o l o g y 衍t i lg o o dp e r f o r m a n c eo f l a t e n c ya n dt h r o u g h p u t f i r s t l y t h i sd i s s e r t a t i o nb r i e f l yi n t r o d u c e st h eb a c k g r o u n d t h es t r u c t u r ea n dt h e k e yt e c h n o l o g i e so fn o c a n ds u m m a r i z e st h er e s e a r c hs t a t u so fb o t i ld o m e s t i ca n d a b r o a d t h e nd e t a i l so ft h ec l a s s i f i c a t i o no f r o u t i n ga l g o r i t h m s e v e r a lc l a s s i c a lr o u t i n g a l g o r i t h ma n di m p o r t a n tc o n c e p t s s u c h a sd e a d l o c k l i v e l o c ka n ds t a r v a t i o na r e i l l u s t r a t e d i na d d i t i o n t h ei m p l e m e n t a t i o nm e t h o d so fr o u t i n ga l g o r i t h m sa r ec l a s s i f i e d a c c o r d i n gt od i f f e r e n tc r i t e r i a m o r e o v e r t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e s e c l a s s i f i c a t i o n sa r ea n a l y z e do nt h eb a s i so fh a r d w a r ei m p l e m e n t a t i o n a n dt h e nt h e p o p u l a rx yr o u t i n ga l g o r i t h mi su s e di nm e s hr e a l i z e dt h r o u g hv a r i o u sw a y s t h e r o u t i n gc o m p u t a t i o nm o d u l ei sd e s i g n e da n dt h ec o m p u t a t i o nf u n c t i o no fo u t p u tp o r ti s v e r i f i e db yi s et 0 0 1 m e a n w h i l e t h er e s o u r c ec o n s u m p t i o nc o s t sa r ea l s oe v a l u a t e d o n t h i sb a s i s w ed r a wo nt h ea d v a n t a g eo fp a r t i a li n t e r c o n n e c t i o no fm e s hn e t w o r k s 西d b a s e dt o p o l o g ya n dt h ec o n c e p to fv i r t u a ln e t w o r kt od e s i g nd v nr o u t i n g a l g o r i t h m f i n a l l yw eu s eo p n e ts i m u l a t o rt oe m u l a t et h er o u t i n gp r o c e s so fp a c k e t s c o m p a r i n gt h e s i m u l a t i o nf o re t ed e l a ya n dt h r o u g h p u tp e r f o r m a n c eo fd v n c r o s s r o u t i n ga n dx yr o u t i n ga l g o r i t h mu n d e rd i f f e r e n tt r a f f i cp a t t e r n s t h er e s u l t s h o w st h a td v nr o u t i n ga l g o r i t h mc a nr e d u c ee t ed e l a ya n di m p r o v et h r o u g h p u t a c c o r d i n g l ya n de n h a n c et h eo v e r a l ln e t w o r kp e r f o r m a n c e k e y w o r d n e t w o r ko nc h i p r o u t i n ga l g o r i t h md i a g o n a l l y l i n k e dv i r t u a l n e t w o r kd v n 第一章绪论 第一章绪论 片上网络产生背景 1 9 5 2 年英国雷达研究所的gw a 达默首先提出集成电路的构想 集成电路的 设想就此问世 近几十年来半导体技术遵循摩尔定律不断革新飞速向前发展 集 成电路的发展依次经历了小规模集成电路 s s i 中规模集成电路 m s i 大规 模集成电路 l s i 现今处于特大规模集成电路 v l s i 与超大规模集成电路 u l s i 阶段 从长远看来随着集成度的不断提升集成电路设计势必会进入超特 大规模集成电路 g s i 这一阶段 2 0 世纪9 0 年代中期 半导体工艺技术迅猛发展 超深亚微米级集成电路工艺 技术也日趋成熟 随着2 l 世纪后6 5 纳米 4 5 纳米工艺的相继投产 集成电路设 计已步入纳米时代 这使得集成电路的设计者能够把越来越多复杂的功能集成到 单一芯片上 在单个芯片上实现一个复杂的系统 片上系统 s y s t e mo nc h i p s o c l 应运而生 s o c 可定义为在单个芯片上实现的数字计算机系统 包括一个c p u 及 其总线的硬件部分 以及由操作系统组成的软件部分 s o c 可理解为一个简化的 p c i 2 1 集成度升高 元器件尺寸减小 然而芯片的功能更加完善 性能需求更高 芯片的规模越来越大 工作频率也越来越高 如表1 1 所示 据i t r s 预测 半导 体元器件的特征尺寸在2 0 1 5 年左右将达到2 5 纳米1 3 1 时钟频率将达到l o g i i z 以 上 集成的晶体管数目也将达1 0 亿数量级 当集成在单个芯片上的晶体管数目达 1 0 亿时s o c 不再适用1 4 j 此时v l s i 设计者需要考虑的设计因素有 功能性 可 测试性 线间延迟 功耗管理 嵌入式软件 信号完整性 射频 r f 混合芯片 组包以及物理限制管理 这些设计因素都增加了设计的复杂度 况且集成电路的 制造工艺以每年5 8 的增长率持续发展 而其设计制造的增长率仅为每年2 1 5 这使得芯片的设计产业面临严峻的挑战 其次 现今的s o c 包含一个或多个处理器 存储器 模拟电路 数模混合电 路以及片上可编程逻辑等i p i n t e l l e c t u a lp r o p e r t y 核 6 总线结构的设想是基于 单个c p u 的 随着系统的规模越来越大 当i p 核的数目增加到成千上万时现有的 总线结构存在以下问题 1 可扩展性差 基于总线的连接方式限制了连接资源的数目 总线的地址资 源不能随着计算单元的增加而无限扩展 而且由于各个资源共享连接的介质 虽 然总线可由多个用户共享 但是一条总线无法支持一对以上的用户同时通信 也 2 基于格型拓扑结构的片上网络路由算法研究 就是说这种串行的访问机制会导致通信的瓶颈 故其扩展性受限 2 通信效率低下 当系统由多个内核组成时 此时需要很长的连线 这限制 了总线连接的速度 功耗控制也相当困难 3 单一时钟同步问题 集成电路设计工艺技术的进步使得工艺特征尺寸进入 纳米级 器件的工作频率迅速上升 时钟频率在达到1 0 g h z 后 由连线带来的时 延问题愈发严重 这也将给电路的设计带来巨大的影响 信号在全局连线上的传 播可能需要好几个时钟周期 对于时钟偏移 c l o c ks k e w 将不能进行精确地控制 而且时钟树的功耗在整个芯片功耗中比重较大 使用单一系统的时钟来同步整个 芯片是极其困难的 表1 1i t r s2 0 1 0 技术预测 3 l y e a r 订p r o d u c t i o n 2 0 l l 2 0 1 22 0 1 3 2 0 1 4 2 们52 0 1 62 0 1 72 0 1 0 n 幽1 2p i t c h n m x u n c o n t e c t e dp o y l 2 8 2 5 2 32 0 1 8l s 9i 2l z d r a m1 2p s t e b n m c o u t e c t e d l o弘3 22 82 5 2 2 s 2 n 冉 1 7 i v l p l i i a s i cm e t a l1 m d l 2p s t c b n m 3 8n2 72 42 1l 量 i l s 膏 m p up r i n t e dg a t el e u g t b g l p r x n n 3 s3 12 82 52 21 9 j1 7 7l m p un 删g a t e 嘲b l o x i m 2 42 22 81 81 7l s ji 一1 2 j a s i c l o wo p e r a t i n gp o w e rp r i n t e dg o t el e n g t l r i m 4 1弱3 l2 5越l j1 7 71 支7 a s i c f i l o wo p e r u t i n gp o w e rp h y s i c a lg a t e 一m a m 2 72 42 21 81 7i l ol u a s i c l o ws t e n d b yp o w e rp b y s h lg a t el e n g t h u r n 2 92 7龆1 01 7l l l u m p ue t c hr a t i og l p r g l p b n n i 4 螂1 4 7l j 51 3 懿l1 3 s1 挣1 71 2 0 71 2 3 0 4 为解决以上基于总线设计的s o c 存在的问题 近年来提出了一种全新的集成 电路体系结构一片上网络 n e t w o r k0 1 1c h i p n o c 1 2 片上网络体系结构概述及其特点 1 2 1n o c 体系结构概述 新出现的n o c 体系结构相比于s o c 可看作是更大规模 更高层次的片上系统 是集成于片上的网络系统 2 0 0 0 年1 1 月瑞典皇家技术学院 k t h 等单位提出了 n e t w o r ko hac h i p 的概念 这标志着片上网络的诞生 n o c 是一个由计算资源 处理器核与现场可编程逻辑块 分布式存储资源以及可编程f o 资源组成 所 有i p 核通过路由节点进行互连的网络 允许任意i p 核之间进行通信 5 j n o c 结构通过提供不同的组件级结构并使用具体的互连网络拓扑结构和路由 第一章绪论3 技术进行通信 这种体系结构被期望用于改善当前存在的基于总线通信系统的性 能 t 焉由可亘曩绩一 图1 14 x 42 d m c s h 结构组成 7 l n o c 主要由以下基本单元组成 负责计算的i p 核 r e s o u r c e 负责通信任务 的路由节点 s w i t c h e s 资源网络接口 r e s o u r c en e t w o r ki n t e r f a c e r n i 以及 通信链路 c h a n n e l 四部分组成 上图1 1 a 所示的是一个4 x 4 的2 dm e s h 其中i p 核负责完成广义的计算任务 这些节点既可以是s o c 也可以是某种 单一功能的i p 核 比方说它们可以是一个处理器核 一个存储器 一个f p g a 或者是一个定制的硬件核或是任何其它i p 核 图1 1 b 中的各参数分别为 处 理器核 p p r o c e s s o rc o r e 数字信号处理器核 d s pc o r e 高速缓冲存储器 c c a c h e 随机存储器 m m e m o r y 以及可重配置模块 r e r e c o n f i g u r a b l e b l o c k 图1 1 c 所示的是路由节点的微结构 它由选择逻辑 缓冲队列 多路复 用器 交叉开关 以及输入输出链路构成 路由节点为m 核间信息的交互确定路 径并分配缓冲队列 将信息通过交叉开关从它的输入端口传输至其中的一个或是 多个输出端口 路由节点之间或是一个i p 核和路由节点之间都是由两条单向的链 路连接而成的 资源网络接口 i i 资源网络接口指的是i p 核与路由节点之间的接口 只 4 基于格型拓扑结构的片上网络路由算法研究 有配置了资源网络接口的i p 核才可以与网络中的其它m 核进行通信 通信链路指的是口核和路由节点 路由节点与路由节点之间的链路 1 2 2n o c 特点 n o c 与s o c 有两点本质的区别 分别是处理器数量的不同和通信机制的不同 前者是多处理器系统而后者是单一处理器系统 从体系结构的角度来看 n o c 借 鉴了计算机网络的特点使用网络进行通信 而后者使用总线进行通信 所以相比于s o c n o c 具有如下的优势 2 5 7 8 j 并行通信 n o c 体系架构支持并行通信 解决了串行访问机制带来的通信瓶颈 提高数据吞吐率及整体性能进而提高通信效率 其最大的并发量与所采用的网 络拓扑结构有关 拓扑结构规则 灵活 规则的拓扑结构 使用较短的连线代替使用长的全局连 线在整个芯片上有利于减少信号耦合 以便于实现信号的完整性 当系统规模 增大时 链路可扩展 n o c 为其拓扑提供了可扩展性 重用性 n o c 可以实现已经设计好的处理单元以及互连单元的重用 因此可以 缩短设计周期 减小开发成本 上市更快更具竞争力 全局异步局部同步 g l o b a la s y n c h r o n o u sl o c a ls y n c h r o n o u s g a l s n o c 使 用全局异步局部同步的时钟策略 每个i p 核都工作在自己的时钟域 不同的 i p 核之间使用片内通信方式 这样一来便可以解决总线结构的单一时钟同步问 题 继而解决时钟树带来的功耗和面积开销的问题 1 3n o c 国内外研究现状 n o c 作为一门新兴的集成电路体系结构设计技术起步于2 0 0 0 年 由瑞典皇家 技术学院等单位率先提出了 n e t w o r ko n ac h i p 的概念 虽然此次对于n o c 的定 义还不是很完善 但是n o c 的概念与其优良的设计理念已对各国科研工作者产生 了深远的影响 n o c 技术发展至今已过去十年 由于n o c 良好的性能和巨大的市 场潜力 在这十年里得到了国内外学术界的广泛关注 目前已有多所大学和科研 单位加入到了n o c 的研究中 其中影响较大的有瑞典皇家技术学院 芬兰v 订大 学 卡梅隆大学 荷兰p h i l i p s 研究实验室等 参与研究的国家还有 法国 意大 利 希腊 以色列 巴西 印度 中国 韩国等 1 3 1 国外研究现状 随着2 0 0 0 年n o c 的诞生 n o c 注定成为活跃在学术前沿的新兴技术 2 0 0 1 第一章绪论 年 瑞典皇家技术学院和芬兰v t t 大学联合启动 n e t w o r k o n c h i pa r c h i t e c t u r e n o c a r c 计划 8 j 着手研究n o c 的基础架构 2 0 0 1 年6 月斯坦福大学的w j d a l l y 等人发表论文 9 1 提出使用片上互连网络通过传输分组的方式替代各式各样连线的 构想 将研究重点转移到n o c 上来 2 0 0 2 年 荷兰p h i l i p s 研究实验室的k g o o s s e n s 等人开始研究 n e t w o r ko ns i l i c o n 重点是片上互连网络的服务质量 1o l i 2 0 0 3 和2 0 0 4 年 各国加大科研力度 进行基础研究 于是出现了n o c 的相关专著 这 也给后续n o c 的研究做了很好的铺垫 同时这也标志着n o c 成果的正式出现 2 0 0 5 年 n o c 开始快速发展 各种n o c 技术和科研成果不断涌现 研究方向更加细化 研究内容更加广泛 2 0 0 6 年3 月f u t u r ei n t e r c o n n e c t sa n dn e t w o r ko nc h i p 年会召开 主要讨论了未来n o c 的连接以及通信问题 2 0 0 7 年5 月第一届i e e ei n t e r n a t i o n a l s y m p o s i u mo nn e t w o r k s o n c h i p 召开 此会议聚集了包括学术 工业领域的研究 人员也包括相关产业的开发商 他们以基于各个层次的片上网络系统为主要讨论 内容 近年来每年都会举办一届 在2 0 1 2 年5 月即将举办的第六届i e e e i n t e m a t i o n a ls y m p o s i u mo nn e t w o r k s o n c h i p 上将会主要探讨片上网络的体系架 构 设计方法学 功耗问题 时序同步问题以及面向具体应用的片上网络等方面 的具体内容 现在一些学术科研机构已经开发完成了具体的n o c 系统 p h i l i p s 实验室研究 的 e t h e r e a l 1 2 jn o c 提供了保证服务 g u a r a n t e e ds e r v i c e g s 以及最大努力 b e s t e f f o r t s b e 服务 从通信角度来看 该片上网络支持点对点 点对多点的 双向传输以及点对多点的单向广播模式 由瑞典皇家技术学院开发研制的 n o r s t l l 朋1 1 0 j 技术主要聚焦于从物理层到应用层的通信问题 其主要特点是 使用 了规则的2 dm e s h 拓扑结构 每个m 核与一个特定的路由节点相连 口核间通过 路由节点发送分组进行通信 交换网络使用的是一个伪同步时钟域 由法国p i e r r e e tm a d ec u r i e 大学研发的s p i n j s c a l a b l ep r o g r a m m a b l ei n t e r c o n n e c t i o nn e t w o r k 结构依靠分组交换以及路由节点间点对点的双向链路实现微网络 它使用虫孔交 换技术 自适应的路由策略 以及基于信用的流控方式 在片上实现了一个胖树 f a t t r e e 拓扑结构的网络 英国m a n c h e s t e r 大学研发的c h a i n t l 3 c h i pa r e a i n t e r c o n n e c t 是一个自定时的n o c 结构 它使用了细粒度的流水线窄链路 路由 节点具有较小的开销 建立在异步系统设计的基础上 d e n m a r k 大学的m a n g o i l 4 m e s s a g e p a s s i n ga s y n c h r o n o u sn e t w o r k o n c h i pp r o v i d i n gg u a r a n t e e ds e r v i c eo v e r o c pi n t e r f a c e 是一种无时钟的n o c 应用目标是针对粗粒度的全局异步局部同步 类型的s o c 提供无连接的b e 路由方式以及有连接的g s 服务 其中路由节点采 取了虚信道以及异步时延保证技术来保证g s 服务 近年来也陆续出现了商用的n o c i n t e l 公司在i s s c c 2 0 0 7 推出了t e r a f l o p r e s e a r c hc h i p 它是基于n o c 的8 0 核处理器芯片 特点是 这款芯片采用6 5 纳 6 基于格型拓扑结构的片上网络路由算法研究 米工艺 每个核都包含一个5 端口的路由节点 核与核间依照2 dm e s h 的拓扑结 构相互连接并进行通信 因此保证了良好的可扩展性 此产品每万亿次的计算仅 需要消耗6 2 w 这可以与台式机处理器的功耗相媲美 t i l e r a 公司于2 0 11 年8 月 份推出了g f g 5 0 0 g b 以太网视频处理器 其核心部件为t i l e r at i l e p r 0 6 4 它由相 同的6 4 个核组成 使用i m e s h 片上网络创新技术形成一个高速并且无阻塞的m e s h 网络 s o n i c s 作为全球领先的片上通信i p 厂商已于2 0 1 1 年9 月份发布了业界的首 款g h z 片上网络产品s o n i c s g n 这款产品具有最佳的同步化特性以及无缝互通性 和兼容性 可以针对智能手机 移动视频以及平板电脑提供高性能的同步应用程 序处理 1 3 2 国内研究现状 国内相对于国外片上网络的研究开展较晚 但是由于已经觉察出n o c 的发展 契机 现在国内许多高校以及科研机构正在开展n o c 方面的研究 其中包括清华 大学 西北工业大学 合肥工业大学 电子科技大学 西安邮电学院等 并且许 多单位已经获得了国家自然基金的资助 其中西北工业大学与合肥工业大学已进 入n o c 系统芯片级研究i l 孓 j 从近年来国内的博士学位授予情况及研究成果中可以看出 n o c 的基础研究 已经比较成熟 正在深入对于n o c 体系结构低功耗设计 高性能评估及其路由算 法等通信技术的研究 1 3 3n o c 发展趋势 现如今随着理论体系的不断完善 n o c 作为一个新兴的学术领域已经迅速地 成长起来 成果也日渐丰硕 至今已出版了许多专著 国内的研究进程也会紧追 国外研究的前沿进入新的阶段 在接下来的研究中 将会针对具体的实际应用 比如 无线通信 图像处理和多媒体应用等 这些面向具体应用的n o c 必须具备 可升级 可靠性等特点 由于片上网络涉及到其体系结构的组成 互连的物理实 现 操作系统的支持 及其应用的各个层面等 所以在以后的研究中将会对片上 网络的各个层面进行具体的研究 1 4 1 课题来源 1 4 课题来源及文章结构安排 本论文课题来源于以下两个项目t 第一章绪论 7 1 国家自然科学基金项目 n o 6 0 8 0 3 0 3 8 2 中兴通讯产学研合作项目 1 4 2 文章结构安排 本论文主要分为五大部分 第一章介绍了片上网络的产生背景 对片上网络的体系结构及特点进行了概 述 之后分别从科研学术和商业角度介绍了片上网络的国内外研究现状 最后进 行了发展趋势的展望 第二章列举了片上网络拓扑结构 交换机制 路由算法的相关概念并对其关 键技术做了简要的介绍 第三章对路由算法的实现方式进行了分类 针对不同实现引入了实例并分析 研究了各自所带来的优缺点 最后针对应用于格型m e s h 拓扑结构中的x y 维序路 由算法的路由计算模块的四种实现方式进行了设计并对其路由计算功能进行了验 证 第四章针对基于p a r t i a li n t e r c o n n e c t i o no fm e s hn e t w o r k s 格型拓扑结构的 c r o s s r o u t i n g 路由算法进行改进 提出了一种具有一定自适应性的对角虚拟网络 d v n 路由算法 使用实验室已有的仿真平台将d v n 算法与c r o s s r o u t i n g 算法以及j x y 维序路由算法在不同流量模式下进行仿真对比 最后对仿真结果进行分析研 究 第五章对全文所做的工作进行总结 8基于格型拓扑结构的片上网络路由算法研究 第二章片上网络相关概念及其关键技术9 第二章片上网络相关概念及其关键技术 2 1 拓扑结构 n o c 的拓扑结构可定义为网络内部路由节点与链路的互连及其布局方式 它 对于网络的时延 吞吐率 面积开销 功耗等各项性能都存在着重要的影响 它 还进一步影响了路由策略的选取 n o c 拓扑结构的研究具有重要的现实意义 2 1 1 主要参数 n o c 的拓扑结构在很大程度上借鉴了通用并行计算机互连网络的结构 在介 绍具体的常见拓扑前 先对影响拓扑结构的几个参数进行定义 1 5 1 6 1 网络规模 网络中路由节点的数目 它反映出了网络的大小 这将直接影响到 网络的成本 直径 网络中任意两个节点之间的最短路径的长度最大值 它将影响通信的时 效性 所以我们追求的设计目标是 为减小网络时延网络直径应尽可能小 节点度 一个节点与其相邻节点间连通的链路数目 可分为入度与出度 规则性 如果网络中各个节点的节点度都相同 则网络是规则的 对称性 如果从网络中的任意一个节点看过去 网络的拓扑结构都相同 则该 网络是对称的 可扩展性 指网络模块化并且可扩展新节点的能力 直接网络 网络内任一路由节点都与i p 核直接相连 间接网络 网络内一部分路由节点只与其它路由节点相连 2 1 2 常见拓扑结构 n o c 的拓扑结构可以分为规则与非规则两大类 1 规则的拓扑结构 其中规则拓扑又可分为直接网络和间接网络 直接网络里常见的有二维网格 2 dm e s h 二维环绕 2 dt o m s 三维立方 3 dc u b e 以及环网 r i n g 间 接网络里常见的有树 蝶网 b e n e s 网 c l o s 网等 1 二维网格 2 dm e s h 4 1 s k u m a r 等人提出此结构 它是一个最为简单的拓扑结构 在此结构中每个路 由节点与一个具体的i p 核相连 其路由节点与i p 核数目相同 如图2 1 a 每个非 1 0 基于格型拓扑结构的片上网络路由算法研究 边缘的路由节点有五个端口 其中四个与相邻路由节点相连 一个与碑核相连 因此该结构具有较小的尺寸 结构简单易于实现较高的物理链路容量 以及良好 的可扩展性 是一种典型的格型拓扑结构 路由节点 囹 i p 棱 一 严 隧jf 霸 吲 f 豸 曩 瓣j i 一 鬻j 圈 羁f 溺 1 j 1 眵囊i 圈f两 f蓦j j d i 1 j t i n r 1 7 一 l 一 一 一 图2 14 x 42 d m e s h 和4 x 4 2 d t o m s 2 二维环绕 2 dt o r u s w j d a l l y 等人提出了2 dt o m s 结构如图2 1 b 此结构通过在行尾路由节点 上添加长的环形链路以此来缩短节点之间的平均距离 这种结构大大减小了网络 的直径 可以减小能耗 但是这种方式由于环形链路较长可能会带来额外的时延 3 三维立方 3 dc u b e 一个n c u b e 由 2 个节点组成 如图2 2 它是n 3 时的特例 在该结构中 每个路由节点同样只与一个i p 核相连 路由节点数目与礤核相同 此结构的优势 在于减小了网络直径和节点度 但是由于要进行立体布线 不易于实现 所以使 用较少 一 路由节点 囡 i p 核 图2 23 d c u b e 4 树形 t r e e 拓扑结构 树形结构的特点是树的父节点是路由节点 子节点是i p 核 网络的时延取决 第二章片上网络相关概念及其关键技术 于树的深度 也就是节点数目的对数 每个父节点在树的每层都被复制四次 通 过增加冗余度 降低时延 增加吞吐 实现可扩展性 图2 3 为s p i n 树形结构 图2 4 为b f t 树形结构 从图中可以看出虽然两者都是树形结构但是它们路由节 点以及链路的数目都不相同 相比于s p i n 结构b f t 的优势在于它减少了路由节 点以及链路的数目 以此降低面积开销 图2 3s p i n 圈 路由节点 i p 核 圈 路由节角 i p 核 图2 4b f t 5 蝶形 b u t t e r f l y 拓扑结构 类似于树形结构 蝶形拓扑也是一种对数型网络 如图2 5 对给定的2 2 交叉 开关 线对中各引出一根线简单的交叉就可得到蝶形网络的构造模块 n 维蝶形网 络包括n 2 个i p 核和n 2 1 个度数为2 的路由节点 路由节点组织成n 层 每 层有n 2 个路由节点 2 非规则的拓扑结构 图2 5 蝶网 圜 路由节点 i p 核 1 2基于格型拓扑结构的片上网络路由算法研究 与规则拓扑不同 非规则拓扑主要针对的是特定的应用需求 面向应用适用 于不同的领域之中 它可以分为以下四类 1 5 图 a 图 c 路由节点 团 i p 核 一 路由特点 囹 i p 核 f z q 喇络接口 总线 图 b 图 d 图2 6 非规则拓扑结构 1 专用网络拓扑 专用网络是指网络的拓扑完全根据具体的应用需求进行设定 没有依循其它 的规则 如图2 6 a 2 基于规则拓扑结构 这种拓扑结构指的是在规则的网络拓扑结构的基础上对一些节点或是链路进 行局部的添加或是删除 使得所需面向具体应用的拓扑结构失去规则性 如图 2 6 b 3 分层网络 在分层网络中 网络的拓扑是一种层次化的结构它具有两层或是多层 一般 包括全局网和局部网两个层次 根据需求可以对规则拓扑与非规则拓扑进行选择 如图2 6 e 4 网络 总线混合拓扑结构 这种结构也相当于一种层次化的拓扑结构 全局网络采用规则或是非规则的 拓扑 局部网络采用总线 这种混合型的拓扑结构结合了共享媒介总线以及网络 互连的优点 相比于总线结构增加了带宽 相比于网络结构又可以缩短节点之间 的距离 如图2 6 d 第二章片上网络相关概念及其关键技术 2 2 交换机制 交换机制 l7 l 可定义为分组在片上网络中的传输方式 同时它规定了分组从输 出端口转发出去的时机 其中也包括了对所传输分组的格式要求 n o c 借鉴了i n t e m e t 以及并行计算机互连网络的主要技术 但是n o c 具有低 时延 高吞吐 能耗与芯片面积受限等特点 交换机制是影响上述性能参数的一 个重要因素 在片上网络中使用的交换机制主要包括 面向连接和无连接两类 面向连接的主要是电路交换 无连接的主要是分组交换 分组交换又可以分为 1 8 存储转发交换 虚切通交换 虫孔交换 以下对几种交换方式进行介绍 2 2 1 电路交换 c i r c u i ts w i t c h i n g 电路交换这种方法使用电路或是专用路径 先通过一个信息头部中包含的路 由信息进行选路 在发送数据分组前建立传输路径 在建立阶段进行资源分配 预定所经过路径的链路资源 目的端在成功接收到这个信息头后沿路返回一个应 答 源端在接收到这个应答后便开始传输数据分组 分组在网络中传输时独占此 路径中各段链路的整个带宽 并且不需要再做路由选择 通信结束后 源端向目 的端发出终止通信的要求 沿路拆链释放各段链路 以备其它通信需求 电路交换的缺点是它在建立路径 等待应答和数据传输的过程中都要占用物 理链路 致使其它资源得不到利用 带宽的预留降低了整体的吞吐以及片上资源 通信的平均时延 电路交换的优点是其路由节点不需要添加缓存资源 这样一来 可以减小芯片的面积开销 并且在多媒体业务中 数据分组数量较少 但是数据 分组较长 所以采用电路交换方式较有优势 2 2 2 存储转发交换 s t o r ea n d f o r w a r ds w i t c h i n g 存储转发交换对消息进行分割 划分为若干较小的分组 其数据分组包含分 组头中的路由控制信息 及后续有效载荷 这种交换方式不用像电路交换那样预 先建立传输路径 它将消息划分为固定长度的分组 每个分组在整个的传输过程 中独立路由 在分组转发至下一个节点之前 它将被完全缓存在每个节点之中 如果下一节点有足够的缓存空间存放此分组 就将此分组转发至下一节点 存储转发交换的优点是动态分配链路带宽 这样可以提高链路带宽的利用率 它的缺点是由于在每个路由节点中需要提供至少一个分组大小的缓存资源 所以 会增加芯片面积开销 同时由于每个分组独立路由 不同分组在网络之中的传输 可能经过不同的路径 因此会发生乱序 而且各分组到达时间无法预测 会产生 1 4 基于格型拓扑结构的片上网络路由算法研究 抖动 故只能提供b e 服务 2 2 3 虚切通交换 v i r t u a lc u tt h r o u g hs w i t c h i n g 由于存储转发交换方式的一个分组在转发前必须全部缓存在路由节点中 此 时不能接收下一个分组 这样会使得链路在繁忙时产生较大的时延 虚切通交换 进一步将分组划分为更小的微片 f l i t 并将所有微片顺序排列 第一个微片称为 头微片 包含路由信息 后续微片为数据微片 虚切通交换的优点是由于路由信息只包含于头微片中 只要接收到头微片就 可以立即进行路由转发而不需要等待整个分组接收完毕 当网络状况并不繁忙时 采用虚切通交换方式的网络其平均时延大幅降低 2 2 4 虫孔交换 w o r m h o l es w i t c h i n g 对于虫孔交换 微片的类型分为 头微片 体微片和尾微片 并且允许一个 分组只由一个微片组成 虫孔交换与虚切通交换方式的思想基本相同 头微片包 含路由信息 负责选路 体 尾微片不具备选路功能 头微片确定好分组的传输 路径后 后续微片简单跟随头微片进行传输 虫孔交换的优点是 它只需要较小的缓存资源 时延性能优良 具有足够大 的吞吐量 虫孔交换方式的缺点是 它是一种无连接的交换机制 不能用在长消 息的多媒体应用中 一旦发生阻塞 它的各个微片将会就地阻塞 这样会使得阻 塞的状况扩散到多个相邻的节点 于是增大了其它分组阻塞的概率 2 3 1 路由算法概述 2 3 路由算法 路由算法是确定一个分组从源节点传输至目的节点所走路径的机制 由于路 由算法在很大程度上决定了分组的端到端时延以及整个网络的吞吐 高效的路由 算法能够使片上网络获得优良的时延和吞吐性能 所以在设计路由算法时 应考 虑以下众多因素1 1 9 j 连通性 将分组从任意源节点路由到任意目的节点的能力 自适应性 存在竞争和故障节点时 通过其它可选路径路由分组的能力 死锁和活锁 确保分组不会永远阻塞或者在网络中不停游荡而到达不了目的节 点的能力 容错性 在网络存在故障节点时对分组进行路由的能力 如何在网络中存在故 第二章片上网络相关概念及其关键技术 障节点的情况下 将分组有效地送到目的节点是容错路由设计的首要目标 为 达到有效传送目的 应该尽量采用最短路径同时避免死锁的产生 均衡性 网络中业务的不均衡性要求路由算法要能够具有均衡负载的能力 负 载均衡算法可以使网络中的各种资源 包括缓存资源与链路资源 能够得到充 分利用 避免网络之中某些部分资源充足 而其它部分资源紧张的现象 负载 均衡算法可以通过提高资源的利用率来增加系统的吞吐率 降低分组端到端的 时延 服务质量保证 由于网络中存在很多业务 实时性业务 多媒体数据等 对服 务质量 q o s 有要求 因此路由算法设计中除了传统的参数外还要考虑一些 q o s 参数 如链路剩余带宽 丢失率 时延抖动等 网络中q o s 路由算法需 要考虑的问题有 参数的选择 状态信息的选择和路由策略 2 3 2 路由算法分类 路由算法可以根据不同的标准进行分类 主要包括以下几种 按照目的地的数量 分为单播路由和多播路由 单播路由的目的地只有一个 而多播路由的目的地有多个 按照路由决策地点 分为集中式路由 分布式路由 源路由和多阶段路由 集中式路由是由路由控制中心周期性地收集各链路的状态 经过路由计算后再周 期性地为网络中的各个节点提供路由表 由信息 独立地计算到达各节点的路由 分布式路由是网络中各节点通过交换路 源路由是指源节点决定该消息或分组的 所有路径 并在发送之前将此路由信息存于分组头中 将以上各种路由算法的特 点混合后可以得到多阶段路由 在多阶段路由中 源节点计算一些目的节点 它 们之间的路径以一种分布式的方式建立 按照路由是否具有自适应性 即路由算法是否能够适应网络状态的变化 分 为无关路由和自适应路由 无关路由又可以分为确定性路由和随机路由 无关路 由算法在选择路径时不考虑任何网络当前状态信息 确定性路由是在给定源和目 的节点地址后以网络拓扑为依据 按照某一固定的原则进行路由 其优点是算法 简单 实现容易 但是 由于确定性路由算法忽略了路径多样性 因此它不能充 分利用片上网络提供的链路资源 随机路由是随机选择分组的路由路径 自适应 路由算法能够根据网络当前所处的状态 对分组的传输路径进行优化 它有效地 利用了片上网络的链路资源 根据自适应度的不同又可分为部分自适应路由和完 全自适应路由 自适应路由算法的设计思想是在路由计算时根据网络当前所处的 状态 在源节点和目的节点之间的所有可达路径中 选择一条最优的路径 自适 应路由算法的优点在于能够获得更低的分组传输时延和更高的网络吞吐性能 但 1 6 基于格型拓扑结构的片上网络路由算法研究 是由于需要保证网络无死锁 相应的算法实现复杂度也就增加了 按照选择路径是否最短 分为最短路由和绕道路由 最短路由算法只选择将 分组送到离目的地更近的节点 又称为最小路由 绕道路由则可以提供远离目的 地的节点路由