（微电子学与固体电子学专业论文）片上网络的拓扑结构设计与仿真.pdf

摘要 随着半导体技术的发展，未来s o c ( s y s t e m o n c h i p ) 将变得越来越复杂， s o c 将在一个芯片上集成更多的处理器和存储元件。传统的片上通信结构在目 前的设计中有很多局限性，片上网络将成为片上多处理器m p s o c ( m u l t i p r o c e s s o rs y s t e m o n c h i p ) 的合适的通信结构。 片上网络的拓扑结构对系统的性能有很大的影响。网络的延迟，路由算法， 容错性都和拓扑结构有关。常见的网络结构有m e s h 结构，t o r u s 结构等。本文 提出了基于d eb r u i j n 图结构的片上网络，并为其设计了两种路由算法。与其他 网络结构相比，d eb m i j n 图具有网络直径小，连通性高，路由简单等优点。 s y s t e m c 是由o s c i ( o p e ns y s t e m ci n i t i a t i v e ) 负责维护，发展的建立在c + + 基础上的系统级描述语言，由一系列用来进行系统描述的c + + 类构成，适合做 系统级仿真设计。本文使用s y s t e m c 建立了系统仿真模型，在该模型上能便于 片上网络仿真平台的搭建，体系结构的研究和网络协议的制定，能加速片上网 络路由单元的r t l 设计和实现，并进行功耗和延时等许多方面的研究。 关键词：片上网络：d eb r u i j n 可容错路由：虚拟通道：s y s t e m c a b s t r a c t w i l ht h ed e v e j o p m e n to fs e m i c o n d u c t o r t e c h n o l o g y , s o c ( s y s t e m - o n - c h i p ) w i l lb e c o m em o r ea n dm o r ec o m p l e xi nt h ef u t u r e s o c t e c h n o l o g yw i l li n t e g r a t e m o r ep r o c e s s o r sa n d m e m o r yc o m p o n e n t si nac h i p t h e r ea r em a n yl i m i t a t i o n si n t r a d l t l o n a io n h i pc o m m u n i c a t i o ns t r u c t u r ei nt h ec u r r e n td e s i g n n e t w o r k o n c h i d ( n o c ) w i l lb et h et h e a p p r o p r i a t ec o m m u n i c a t i o ns 缸c t u f ef o rm p s o c ( m u l t i - p r o c e s s o rs y s t e m o n c h i p ) n o c t o p o l o g yh a sag r e a ti n f l u e n c eo nt h ep e r f o r m a n c eo f t h es y s t e m n e t w o r k l a t e n c y ，r o m m ga l g o r i t h m ，f a u l tt o l e r a n c ea r er e l a t e dt ot h es t r u c t u r ea n dt o p o i o g y o o m m o ns t r u c t u r e so ft h en o ca r em e s ha n dt o m ss t r u c t u r e s i n t h i sp a p e r ，w e p r o p o s e dan e t w o r kt o p o l o g yf o rn o cb a s e do nd eb r u i j ng r a p ha n dd e s i g n e dt w o m u t i n ga i g o r i t h m sf o rt h en e t w o r k d eb r u i j ng r a p hh a ss m a l l e rd i a m e t e r ，h i g h e r c o 彻e c t l v l t ya n ds i m p l e rr o u t i n ga l g o r i t h mc o m p a r e dw i t ho t h e rn e t w 0 1 ks t n l c t u r e s s y s t e m c ，w h i c hi sm a i n t a i n e da n d d e v e l o p e db yo s c i ( o p e ns v s t e m c l n n l a t l v e ) ，1 sas y s t e m - l e v e ld e s c r i p t i o nl a n g u a g ef o rt h es y s t e m d e s c r i p t i o n i ti s b u i l to nas e r i e so fc + + c l a s ss t r u c t u r e a n ds u i t a b l ef o rs y s t e m 1 e v e ls i m u l a t i o n d e s l g n i nt h l sp a p e r , w eu s e ds y s t e m ct oe s t a b l i s ha s y s t e ms i m u l a t i o 舳【l o ( j e jw h i c h c a l lf a c i l i t a t et h en o cs i m u l a t i o n ，a r c h i t e c t u r e r e s e a r c ha n dn e t w o r kp r o t o c o l d e v e l o p m e n t t h i sm o d e lc a na l s oa c c e l e r a t et h ed e s i g na n dr e a l i z eo f 附，lb a s e d n o c r o u t i n ga n db eu s e df o rr e s e a r c ho fp o w e r c o n s u m p t i o na n dl a t e n c v k e yw o r d s ：n e t w o r k - o n c h i p ，d eb r u i j n ，r e l i a b l er o u t i n g ，v i m u a l c h a n n e i s y s t e m c ： 图目录 图1 1 总线结构连接示意图3 图1 2 片上网络结构连接示意图一4 图2 1 片上网络的理论体系结构6 图2 2 直接网络拓扑结构1 0 图2 3 间接网络拓扑结构1 0 图2 4 竞争前瞻的自适应路由1 3 图2 5 路由节点的缓存结构1 4 图2 6 发生阻塞时虚拟直通和虫孔路由的区别1 5 图3 1 拓扑结构的设计流程1 6 图3 24 x 4 m e s h 结构一1 7 图3 34 4 t o r u s 结构】9 图3 4d b ( 2 ，4 ) 结构2 1 图3 5d b ( 2 ，4 ) 的两个链路不相交的二进制生成树2 2 图3 6 数据包格式2 3 图3 7 路由器接口2 4 图3 8 三种拓扑结构网络直径的比较2 5 图3 9d eb r u i j n 结构分成均等两半的示意图2 6 图3 1 0 理论得到的三种结构传输延迟比较2 7 图3 1 1d eb r u i j n 结构中的节点回路2 9 图4 1 几种硬件描述语言适用的范围；3 3 图4 ，2s y s t e m c 语言的结构一3 4 图4 3s y s t e m c 描述的f i f o 3 6 图4 5 使用虚拟通道的路由节点模块4 1 图4 6 包头译码模块4 1 图4 7 数据流控制的有限状态机4 2 图4 8x y 路由的转折方式4 3 图4 9d eb r u i j n 结构的转折方式4 3 图4 1o 数据包注入网络的示意图4 5 图4 1 1 仿真运行界面4 6 图4 1 2 基于d b ( 2 ，4 ) 的片上网络波形图4 6 图4 1 3 使用虚拟通道和虚拟输出队列的性能比较4 7 图4 1 4 不同虚拟通道数对网络性能的影响4 8 图4 1 5f i f o 深度对网络性能的影响4 8 图4 1 6 不使用虚拟通道时三种拓扑结构的性能比较4 9 图4 17 使用虚拟通道后三种拓扑结构性能比较5 0 图4 1 8 使用可容错算法对网络性能的优化5 1 表目录 表1 1 片上总线结构与片上网络网络的比较4 表2 1 片上网络通信协议7 表4 1 热点通信模式下不同热点位置网络的性能4 9 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：毛纽1 厶彩b 作者签名：巡：! ：尘1 9 签字日期：鲨生16 ：垄 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中 国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 日公开口保密( 年) 作者签名：逊：! ：坠鱼 导师签名： 签字日期：i 鲨! 竺：垒：三签字日期： 第一章绪论 第一章绪论 1 1 系统芯片s o c 2 0 世纪9 0 年代以来，集成电路产业的发展速度越来越快，集成度越来越高。 随着集成电路制造工艺、封装测试技术和设计方法学的进步，晶体管的尺寸越来 越小，单个芯片上集成的晶体管数目越来越多，目前量产芯片的特征尺寸已降到 4 5 n m 。1 9 5 8 年，世界上第一块集成电路在美国德州仪器公司( t i ) 诞生，当时这 块集成电路上只集成了4 个晶体管。而现在单个芯片上已经可以集成上百万门。 在集成电路设计发展初期，电路设计是从器件的物理版图入手，以晶体管级为基 础，这种原始的设计方法使得芯片的集成度和复杂度难以提高，开发周期也特别 长。后来随着e d a 工具技术的出现，集成电路的设计开始以标准单元库 ( c e l l 1 i b r a r y ) 为基础，使用标准的逻辑符号库、功能参数库和版图库，使得集成 电路设计从器件级进入到逻辑级。随着大规模集成电路的发展和e d a 工具的进 一步发展，集成电路设计开始以r t l 级( r e g i s t e rt r a n s f e rl e v e l ，寄存器传输级) 为基础。r t l 级按电路的数据流进行设计，以寄存器( r e g i s t e r ) 为基本单位对数 据在寄存器之间的流动和传输使用代码描述。r t l 级设计使用v e r i l o g 和v h d l 等硬件描述语言，与工艺无关，移植性好，使集成电路的集成度进一步提高，产 品的研发周期更短。随着系统向更的集成度发展，对系统规模、性能、功耗、开 发时间提出了越来越高的要求；同时，由于e d a 工具技术的飞速发展和第三方 独立m 的出现，出现了系统芯片设计方法s o c 。 s o c 通常是指在单一芯片上实现的数字计算系统。系统一般包含两个部分： 硬件部分和软件部分。硬件部分将微处理器、模拟i p 核、数字i p 核和存储器集 成在一块芯片上，实现信号采集、转换、存储、处理和i o 等功能，软件部分包 括操作系统和重要的应用软件。s o c 实现了一个系统的功能，速度快，集成度 高，功耗低，使得成本和体积都大大降低，也加快了更新换代的速度。s o c 的 这些优点正好顺应了通信产品、微型计算机、消费类产品体积小、重量轻、低功 耗和更新换代快的发展趋势，在过去十年里得到了快速的发展。 i p ( i n t e l l e c t u a lp r o p e r t y ) 是知识产权，i p 核是具有知识产权的专用集成电 路。i p 核经过专业的设计和验证，可以独立的实现一些系统功能，并可以方便 在以后的设计中使用，或是提供给别的用户用来在s o c 系统中实现需要的功能。 对于i c 设计公司来说，由于每次都重新设计一个复杂的系统芯片需要很长的时 间，所以为了使产品尽快上市，就要提高s o c 的设计效率，就必须要尽可能采 用基于已有的i p 核的设计方法，使开发的周期缩短，这就是i p 核重用技术。i p 核可以分为三种：软i p 核、硬i p 核和固i p 核。 第一章绪论 软i p 核( s o f ti p ) ：是抽象层次上对硬件的描述，包括可综合的h d l 代码、 网表、和测试文档( t e s t b e n c h ) ，通常以h d l 文本的形式提交给用户，需要用户 进行综合和布局布线后才能使用。软核经过r t l 级的功能验证，但其中不含有 版图和物理信息，软核可能不能通过后端验证。在设计中由于不涉及版图的物理 实现，所以使用软核有很大的灵活性和适应性。 硬i p 核( h a r di p ) ：已经完成了全部的前后端的设计，电路结构掩膜、布局、 工艺都已经确定，具有可靠的性能。硬核向用户提供的形式是电路物理结构掩模 版图和全套设计的参数如芯片面积、功耗、时序、布局等，使用者在自己的设计 中给硬i p 核留出足够的面积空间，并保证接口合适即可。但是对于不同的工艺， 硬i p 核的形式是不同的，参数和连线方式均有变化，所以移植性较差。 固p 核( f i r mi p ) ：是可综合并带有一定的版图布局规划的i p 核，介于软硬 核之间，是在完成r t l 设计之后将r t l 描述综合成门级电路网表，并完成了时 序仿真。固i p 核一般以门级网表的形式提供给使用者，使用者需要根据提供的 门级仿真结果将自己的设计中的时序关系与固i p 核对应。固i p 核的灵活性介于 软m 核和硬i p 核之间，有折中的可移植性和设计可靠性。 i p 核重用技术使s o c 的设计得到了很大的发展，从原来的以实现每个模块 的功能为基础开始做设计发展到直接采用各种d 核做系统设计，设计中的关键 难点从综合和仿真转变为软硬件的协调，系统级模拟，不同d 模块的功能、接 口、时序和电气特性的结合等问题。i p 核重用技术要求设计的口核具有更好的 可测性、适应性以及可扩展性，同时还希望i p 核有较好的加密技术来保护设计 者的版权。 在一个s o c 系统中一般包括一个嵌入式微处理器，用于做计算时单个嵌入 式微处理器的功能不够强，需要采用多个处理器核来提高s o c 系统的性能。在 多核系统中不是使用几个核性能就可以提高几倍，核与核之间的通信效率才是决 定系统性能高低的关键。在集成电路发展的过程中各个模块之间的通信连接变得 越来越复杂。在早期的芯片设计中，由于芯片规模较小功能较少，只需要划分为 几个功能模块，设计好他们的连接和时序就可以实现需要的功能，这时连接各个 模块之间的方式是点对点的连接，不需要引入复杂的仲裁机制。在现在的s o c 系统的通信结构中普遍使用的是总线互连结构，如图1 1 所示。 2 第一章绪论 图1 1 总线结构连接不意图 总线结构为系统提供了一整套的通信协议，实现系统中多个单元模块的数据 传输。总线结构中的多个单元共享一条总线，单元模块根据使用总线的方式分为 主设备和从设备，分别启动和响应总线的操作。s o c 中的片上总线最大的特点就 是有统一的接口标准，每个i p 核在连接到总线上之前先设计一个符合标准的总 线接口。这样可以方便各种i p 核的复用，大大的缩短设计需要的时间。虚拟插 座接口联盟( v i r t u a ls o c k e ti n t e r f a c ea l l i a n c e ) 提出了统一的规范性的总线接口， 即虚拟元件接口v c i ( v i r t u a lc o m p o n e n ti n t e r f a c e ) ，用于将不同的i p 模块进行 包装后加人总线接口。使用基于v c i 的总线封装增加了d 核应用到s o c 中的可 重用程度，使得移植变的更加容易，而且减少了输入输出引脚，简化了系统设计 与连接布线。 1 2 片上网络的提出 由于在总线结构中每个单元模块共用一条系统总线，总线的带宽就由系统中 所有的模块共同占用，每个模块平均占用的带宽不高，而且总线中在同一时间里 只允许有一条通信信息，所以当节点数量变大时每个节点分得的带宽将会很少， 系统的性能也会降低。片上总线在全局时钟域上的时钟同步问题，以及由于窜扰、 电磁干扰、电磁辐射等产生的传输数据错误，使得片上总线结构在数据传输的可 靠性不能满足未来高频率的片上系统芯片的通信要求。 以前由于芯片设计技术的限制在一个芯片上只能集成几个或十几个资源节 点( 如处理器核和应用i p 核) ，如果使用一个以包交换来传输数据的网络不能 充分的利用网络通信的优势。而随着集成电路的发展在一个芯片内可以集成的资 源数越来越多，使用片上网络( n e t w o r k o n c h i p ) 来代替片上总线结构成为未来 s o c 通信结构设计的理想选择( d a l l ya n dt o w l e s ，2 0 0 1 ) 。片上网络的体系结构 笫一帝绪论 的基本组成是由一个路由节点连接着一个资源节点和相邻的节点，如图1 2 所示 图1 2 片上嘲络结构连接示意图 片上网络的特点是采用包交换的通信方式，网络中可以使用不同的节点拓扑 结构和路由协议。在可扩展的s o c 系统中使用包交换的片上网络可以极大的提 高性能，降低功耗。片上网络与片上总线相比在很多方面更适合作为未来多核芯 片中的通信结构，如表1 1 所示( n ia n dm c k i n l e y1 9 9 3 ) 。 表1 1 片上总线结构与片上网络嘲络的比较 片上总线结构片上网络结构 每个节点单元都连接到总线上，电气性 每个节点单元连接至0 对应的路由节点 能随着单元的增加而变差上，当网络规模变天时资源节点与本地 路由节点的连蔹不受影响 总线的频率越来越高，时序安排和时钟片上网络由于连接都是点对点连接，可 同步越柬越困难以采用流水线改进性能 总线的仲裁成为瓶颈，随着主设备数量一般由分布在网络申的片上路由器共 的增加仲裁延迟越来越高同实现路径选择，延时可以估计 不同的总线结构，总线中连接的设备不路由算法相同圳0 路由嚣结构也相同，与 同，总线仲裁器各不相同网络大小无关 所有的节点单元共用总线，带宽资源有带宽资源随着网络包含的单元数量的 限 增加而增大 本论文的主要研究片上网络结构和路由器的通信性能，使用s ) ，s t e m c 建立了 片4 上网络的系统仿真平台，该仿真平台能方便片上网络体系结构的研究和网络协 议的制定，能加速片上网络路由单元的r t l 设计和实现，并进行功耗和延时等 许多方面的研究。在平台上实现了m e s h 结构、t o m s 结构和基于d eb r u i j n 图结 第一章绪论 构的网络模型，并用可容错路由和虚通道改善网络性能，给出了一些仿真结果 并做出对比。 1 3 论文结构及内容安排 文章共分五个章节，组织如下： 第一章绪论。介绍了集成电路s o c 的发展，片上网络产生的技术背景，片 上网络和片上总线的比较，采用片上网络的优势以及片上网络的研究动态。 第二章片上网络技术基础。首先介绍片上网络的通信协议，然后介绍了片 上网络的拓扑结构，片上网络使用的交换技术和路由算法等相关的概念。 第三章拓扑结构设计。介绍了常见的两个拓扑结构，并主要介绍了基于d e b r u i j n 图结构的网络模型。 第四章仿真实验。介绍了s y s t e m c 系统级描述语言，详细介绍了仿真模型 各个单元的设计，实现的功能。通过在仿真平台上的实验仿真，对m e s h 结构、 t o r u s 结构和基于d eb r u i j n 图结构的网络模型的性能进行比较。 第五章总结与展望。总结了本文的工作，并提出了对进一步工作的展望。 第二章片上网络的技术基础 第二章片上网络的技术基础 。，r 7 通讯结点羌件“霉 嚣厂，基础元件库，f l 一计算结点元件i f - 。彳n i_ ?彩 l ，l 抖确m 儿1 7 一篥j ，。荸譬集成与验证墨i - 荔1 1 通讯协议 ? i系 ：。：，。 。，】m 附议 li 霜卜。曼，卿二。h 一一。| 拓扑鲔构、7 喜i ；构i ，茹砒一m 旎磁l 拓扑鲔构委 l l ，n o c 软件；一 。 引丽离赫蛩。7 徽霎。誊 ；考f ；檠k ? 可测性设计孽气* 一熙矽莓尊筹纛，- i _ | | | | 卞萋隹：蔷舞函蕊 ! 。置| ：、煮幺l f 。，i ，可制造性设计篓，j ，。 l一，、。广。，通疆仿真。二 l 晤r 一。劣真王具：一i 一系统仿真善 l | 耋卜i 獬具、i 一辽、誓豢曩 理i 一1 77 一一“l 资源映射：+ ：挈卜，一系统建模工具f 。，。字用特征建模 l ”_ 流程及方法学誓 。“ 6 第二章片上网络的技术基础 2 2 片上网络通信协议 片上网络的通信参考了计算机网络的设计概念。计算机网络可以在多个资源 间有效的传输数据，所以包含多个资源节点的片上网络采用了计算机网络的以包 交换为基础的多节点系统通信方式。 在网络系统中为了将信息从一个资源传输给另一个资源需要建立一套协议。 如在两个通过数据连线相连的单元之间通信可以通过带有请求和确认的硬件握 手信号，这就是一个简单控制信号协议。在系统级芯片的设计中所用的i p 核越 来越多，各种不同的i p 核之间的通信越来越复杂，通信协议已经严重影响系统 的性能和可扩展性，所以在片上网络中的通信需要通用性更高、数据传输效率更 高的技术。包含多个资源节点的片上网络系统与计算机网络系统类似，在片上网 络中采用的通信协议也受到了计算机网络的通信协议的启发。在片上网络中采用 和计算机网络相似的通信协议是使用路由器来传递网络数据，以包为单元来进行 数据传输，再结合芯片电路的设计的特点来进行片上网络系统的设计。 计算机网络通信是由一组通信协议组成的。协议中的每一层在各自的层面上 实现相对独立的功能，而一组完整的通信协议被称为协议栈。在片上的包交换网 络中的通信协议决定了资源节点与网络相连的接口，还决定了信息是怎样从源节 点发送向目的节点，以及路由节点的缓存大小、仲裁机制等。片上网络的通信协 议比总线协议复杂的多，所以片上网络的通信和计算机网络一样采用分层协议的 设计，划分为七个层次如表2 1 所示。每一层的协议实现不同的功能，组成片上 网络的协议栈。 表2 1 片上网络通信协议 软件应用层 系统层 传输层 网络应用和控制 网络层 数据链路层 物理 物理层 在片上网络的分层协议中，通信所需的各种功能根据其的划分在各个不同的 层上，这样的好处是提供了针对不同需求可以从不同层次优化来能够满足不同的 传输要求。片上网络的通信涉及到从最基础的物理层到最高的应用层的软件和操 作系统，如果在整体系统对数据传输统一进行处理会给设计和调试带来很大的困 难。例如，在一个集成了不同处理器核和i p 核的s o c 中，两个不同种类的资源 之间进行的消息通信可以在协议栈某个较高的层次来调试，如在网络层中调试， 则不需要关心两个资源节点如何将消息拆分成包，如何在物理层的电路连接中进 7 第二章片上网络的技术基础 行传输，以及具体的物理电路的实现，只需要考虑数据包传输中经过哪些路径， 会不会发生阻塞就行了，这样就简化了系统设计的难度。 目前片上网络的数据包交换通信中的研究主要集中在网络中的拓扑结构、路 由节点设计、路由算法以及接口等，主要对应于o s i 参考模型中较低的三个层次： 物理层，数据链路层和网络层，分别描述如下： 1 物理层 物理层主要涉及路由节点和资源之间以及两个路由节点之间的电路连接，电 路的物理特性如串扰、电感等。物理层解决网络中的数据通道的物理实现问题， 定义了连接资源节点和通讯节点连线的数目，电压高低，走线长度和宽度，信号 时序，两个单元间的连线数量等。物理层的设计目标是使得整个片上网络建立在 一个性能良好的通信信道的基础上，并为其他协议层提供一个良好的接口和便于 仿真的模型。 2 数据链路层 数据链路层定义了网络中数据包传输的协议，为信息在物理链路上的传输提 供定程度的可靠性保证，处理数据传输时发生的错误，并向网络层提供一个良 好的接口。 在数据链路层上为了将信息从一个节点无误地传输到与其相邻的节点，通常 是在源节点对传输数据进行打包，分成一组微片流水的在网络层中传输。而在目 的节点上解包还原出原始数据。打包过程将原始的传输数据分成为包头，数据信 息，包尾三种，并给每一部分加上消息标识，每种数据包的长度相同。包头中包 含有整个数据包的信息，如包的大小、目的节点地址、包的顺序号等。包尾作为 数据包的一组微片的结束标识，一个发送完整的数据包必须包含包头和包尾。路 由单元在接受到数据包后就能够根据包头的信息决定对数据包做什么操作。 在物理层中，数据信号可能在传输中会由于串扰等因素发生错误。如果在物 理层不育i , 1 日i k 好的解决，就需要在数据链路层中在帧的前后加上检错和纠错信息， 然后在目的节点处对发送中出错的数据信息进行恢复。 数据链路层还需要对链路上的数据流量情况进行监控，网络层根据监控的拥 堵情况改善整个片上网络的数据传输。如在路由节点处检测可用的输出缓冲 f i f o 以及每个相邻节点的输入缓冲f i f o ，记录路由节点可使用的虚拟通道的数 量。可使用的虚拟通道数的初始值为路由结构中的输入输出虚拟通道数，例如当 一个输出端口发送数据包时，该端口的可用输出虚拟通道数量减一，当整个数据 包向目的节点发送成功后可用的输出虚拟通道数量加一，同样可用对输入端的虚 拟通道计数。路由节点的可用输入输出虚拟通道不为零时连接是畅通的，可以继 续发送新的数据包，否则端口被阻塞。 8 第二章片上网络的技术基础 3 1 网络层 片上网络的网络层的功能是在交换网络中将数据包从一个资源传输到另一 个资源，提高传输的效率和质量。网络层中使用的交换技术包括包交换、虚拟直 通、虫孔路由等，决定了网络中节点间数据交换和连接的方式。网络层中的路由 算法对不同的拓扑结构是不同，好的路由算法可以将数据包完整快速的从源资源 块通过交换网络传递到目的资源块。路由算法决定了包头微片在路由节点上的路 由决策，比如在自适应路由算法的数据传输中由于网络中的拥堵情况不同，在同 一对节点间发送的不同数据包可能经过不同的路由来绕过发生堵塞的路由节点。 在网络层中需要提供合适的数据交换技术来适应路由算法，如在使用自适应路由 算法中允许数据包退回并释放开始申请的通道。 片上网络上的通信需要根据不同的需要采用不同的通信协议和网络的拓扑 结构。由于片上网络采用了通信协议堆栈的描述方式，可以对不同协议层次的性 能进行分别的研究，比如在物理层对同步接口和电气性能做改善，在网络层对路 由算法做改善等，有利于对于不同协议层次的通信结构进行优化，从而提高片上 系统的通信性能。 2 3 片上网络拓扑结构 片上网络的拓扑结构定义了网络中的资源节点和路由节点的连接方式，片上 网络系统采用的拓扑结构对系统的延时、吞吐率、面积、功耗等性能有重要的影 响，还决定了片上网络的路由算法，可扩展性，服务质量等。 2 3 1 直接网络拓扑 在直接网络拓扑结构中，每个处理单元和其专用的存储单元组成的资源节点 与路由节点一起组成一个瓦片( t i l e ) ，构成了网络的基本组成单元。每个瓦片 具有不同的功能，但是具有相同的通信协议，按照一定的拓扑结构被规则的布置 在网络中。直接网络拓扑中一般采用包交换技术通信，每个瓦片均能独立地对数 据包做出路由，使数据包在瓦片之间传递。 口 口! 口，口i 口| 口；口! 口； 口 口i 口；口i 口口口口 ( a ) 9 l j i 】i 口；口口 f 上 ： 】| ；口 口口 ”口；口：i 口 灌j 遵干剁i # ( b ) 第二章片上网络的技术基础 口7 _卜口 入i l 山 v 、7 口、卜弋 ( c ) 口口 厂1 ： 1 一 启 口l 晒匹 _和塌i l i d 百 ( d ) 口资源节点 豳路由节点 图2 2 直接网络拓扑结构 在图2 4 中，( a ) 是最常见的二维网格结构，也就是m e s h 结构，其特点是 结构和路由算法简单，易于实现。( b ) 是t o r u s 结构，在m e s h 结构的基础了增 加了边缘节点处的连接，所有的通信节点形成了回路，使最短路径延迟减小。( c ) 是o c t a g o n 结构，特点是任意两节点之间的连接都只需要经过两个两个路由节 点。( d ) 是非规则的直接网络结构。 2 3 2 间接网络拓扑 在间接网络拓扑中处理单元与路由单元不是一一对应的，处理单元通过网络 资源接口和开关节点相连，网络中的路由交换由专门的交换开关实现。与直接网 络的瓦片结构相比较，间接网络拓扑结构中网络主要由开关节点构成，处理单元 和路由单元分开执行各自的功能的。 在图2 5 中，( a ) 是树形结构，资源节点连接到网络中树的叶子上，在根 节点处的路由节点连接的路径和处理的数据包最多，需要较高的吞吐量。 ( b ) 是b u t t e r f l y 结构，网络中任意两个不是连接到同一交换节点的处理单元的延迟均 相同。 ( a ) 口资源节点囱路由节点 图2 3 间接网络拓扑结构 l o ( b ) 第二章片上网络的技术基础 2 4 片上网络路由算法 2 4 1 路由算法的分类 片上网络中的路由算法决定路由器接收到的数据包的发送方向。路由算法根 据数据包的包含的路由信息做出仲裁，将数据包发送到对应的路径上。路由算法 需要避免网络中出现死锁和活锁，尽量减少网络的拥堵和延时，提高网络的性能。 不同的拓扑结构需要使用不同的路由算法，一起影响片上网络的网络性能。与计 算机网络相对应，片上网络也已经提出了很多的路由算法，可以按照不同的标准 分为不同的类别： 1 路由算法可以按目的地的数量分为单播路由和多播路由 单播路由数据包只有一个目的地，也就是一对一的通信模式，网络中的路由 器对数据包只转发不复制；多播路由是数据包可以有多个目的地，也就是一对一 组的通信模式。 2 路由算法可以根据做出路由决策的地点分为源路由和分布式路由 源路由是由源节点在数据包注入网络之前决定数据包发送后在网络中的传 输路径，一般将决定的路由信息保存在数据包的包头中，在路由节点处只需要根 据路由信息转发不用判断，路由节点的设计比较简单但是传输的数据包内容增 多；分布式路由是在路由节点接收到数据包后自己判断传输的方向，这样数据包 包含的内容较少，但是路由节点的设计复杂，延迟和功耗较大。也可以在不同的 阶段分别使用源路由和分布式路由，这样的混合路由方式也称为多阶段路由。 3 路由算法可以根据路由方向是否确定分为确定性路由和自适应路由 确定性路由算法的传输路径完全由源节点和目的节点决定，在给定的源节点 和目的节点对之间提供相同的路径，当网络中出现堵塞时数据包只能在堵塞处等 待堵塞缓解；自适应路由算法则是对给定的源节点和目的节点根据网络状态、可 用通道数等信息来决定路由方向，可以使数据包尽量避开拥堵的连接或是网络中 的故障连接，提高网络的性能。 4 在自适应路由算法中又根据采用的绕道方向可以分为前进型和回溯型。 前进型路算法是每次路由节点将数据包的包头向前移动的同时在前方的路 由处预留一个新通道；回溯型算法是在包头发送受阻时将包头退回到原先的路由 节点，重新选择路径发送并释放掉先前预留的通道。 5 路由算法根据它们选择路径的是否最短分为最短路由和绕道路由。 最短路由是路由节点对数据包路由时只选择满足从源节点到目的节点的路 径最短的通道，也称为最小路由算法；绕道路由则可以根据网络的状况提供将据 包送到远离目的地的通道，也称为非最小路由，使用绕道路由必须小心出现活锁 第二章片上网络的技术基础 现象，即数据包在网络中被转发后总是不能被发送到目的节点。 6 路由算法还可以根据实现方法的不同分为查表路由和状态机路由。 查表路由是路由节点处保存有一个路由表，路由时根据源节点和目的节点的 地址在路由表中查找对应的传输路径；状态机路由是在路由节点处用硬件实现的 根据路由信息和有限状态机的状态来得到数据包传输路径的路由算法。 2 4 2 确定性路由 确定性路的传输路径完全由源节点和目的节点决定，在给定的源节点和目的 节点对之间提供相同的路径。它的路由路径只与源节点和目的节点有关，与当前 网络的状态无关，在给定源节点和目的节点后路由路径就确定了。确定性路由特 点是路由算法简单，实现需要的逻辑资源较少，在片上网络中的资源节点向网络 中注入数据的注入率不高的情况下拥堵发生的情况很少，而且设计者可以根据特 点的系统中通信的特点，对收发数据较多的相关节点提供专门的低延迟路径，还 可以平衡网络中的数据流量，可以最大限度的避免通信拥堵，获得较低延迟。但 是在注入率较高时网络中出现大量的拥堵，某些路径可能长期不通畅的情况下确 定性路由的性能会迅速降低。在确定性路由算法中使用的最多的是维序路由。维 序路由算法在发送数据包时首先根据当前节点和目的节点之间在各个维上的偏 移量计算出当前节点与目的节点的位置关系，然后选择其中的某一个维严格按增 加或减少的次序进行路由，每发送一次后当前节点和目的节点在该维上的偏移量 减一，直到在当前维上的偏移量减为o ，也就是在这个维上到达了合适的坐标后 再转入下一维进行路由。数据包在通道内路由时是按照从低维到高维的顺序，所 以维序路由算法不会出现死锁。维序路由有着非常简单、易实现的路由逻辑，需 要的延时和功耗较小。m e s h 结构中的x y 路由和t o m s 结构中的t x y 路由都是 维序路由。 2 4 3 自适应路由 自适应路由是对给定的源节点和目的节点根据网络状态、相邻节点的可用缓 存数等信息来决定路由方向通过增加适当的复杂度来获得灵活性。例如，从一个 节点向另一个节点传输数据包，由于网络状态不同，在传输中可能遇到拥堵，传 输数据包的路由路径可能不同。自适应路由的优点是传输数据的路径可以调整， 减少网络拥塞发生的概率，使片上网络通信的网络带宽更高。但是自适应路由的 路由逻辑与确定性路由相比较为复杂，在延时功耗等方面开销较大，而在网络数 据包注入率较低的情况下性能与确定性路由相比差不多，并且在改变数据传输路 径后可能会发生死锁问题，所以避免出现死锁是在研究自适应路由算法时必须考 虑的问题。如图2 2 为根据相邻节点的可用缓存数来选择路由路径的竞争前瞻的 1 2 第二章片上网络的技术基础 自适应路由。 一 vv -一 i 缓存信息 i 、 ，一、 一 、 一 c ，、二rn n 厂、 ， kk 一 i - * 4 。 )， 厂、 k - ，r ， ) 二 luf 一r 一一1 、 、l 头片f、 一 图2 4 竞争前瞻的自适应路由 一般常用的无死锁路由的方法主要有三种： 1 是在设计路由算法时限制路由向某些方向发送数据，使得网络中的节点发 送数据时不会形成环路来避免死锁。 2 是使用虚通道技术来避免出现死锁。 3 是检测可能出现的死锁，在对包头微片做路由时避免向可能出现死锁的方 向路由。 使用虚通道可以很好的避免出现死锁，但是需要增加路由上的缓存资源。采 用带有一定自适应性的维序路由算法可以在不增加网络资源的条件下，从算法上 提高自适应度和避免死锁的出现。在一般的维序路由中数据包沿着一个维上传 输，直到到达适当的坐标后再转向另一维。在带有自适应行的维序路由中数据包 可以在中间转向，如沿着某一维传输的过程中传输路径上发生了拥堵，路由就向 另一维连接到目的节点方向的路由发出申请传输的请求，如果在另一维上可以接 收数据则数据包就转向该方向传输数据，然后再按照原先的路由方式在第一维上 继续传输，如果另一维也发生拥堵才在原路由处等待。这样的路由算法在网络中 没有形成环路，所以可以避免出现死锁。 2 5 片上网络交换技术 片上网络采用包交换技术实现数据在节点直接交换，主要使用的包交换技术 包括：存储转发( s t o r e a n d - f o r w a r d ) 、虚拟直通( v i r t u a lc u t t h r o u g h ) 和虫孔路由 ( w o r m h o l er o u t i n g ) ，在片上网络中有不同的性能和资源需求。 2 5 1 存储转发技术 存储转发又叫报文转发，是将数据包划分为固定长度的报文，每个报文都包 含有路由信息。在每个路由节点处对经过的报文进行检查判断发送的方向，在从 一个路由器发送到下一个路由器，报文被完整的存储在路由节点的缓存中，所以 第二章片上网络的技术基础 缓存的大小要足够大可以放下整个报文，所以路由节点上需要很多的存储资源。 存储转发技术中数据包在网络中的传输延迟的计算公式如下： t = ( l b w + r ) h 其中，l 为数据包的长度，b w 为网络的带宽，r 为路由节点上的路由交换 延迟，h 为数据包从源节点到目的节点经过的路由节点的个数。 图2 5 路由节点的缓存结构 2 5 2 虚拟直通技术 虚拟直通技术将数据包分成一组组的微片，在头微片中包含有路由信息，在 路由节点处决定发送的方向就直接转发头微片，后面的微片跟着头微片以流水的 方式通过路由器，可以节省路由时间。但是当发生阻塞时整个数据包都要存储在 当前路由节点的缓存中，所以也需要很大的缓存资源。虚拟直通技术中数据包在 网络中的传输延迟的计算公式如下： t = l b w + r h 2 5 3 虫子l 路由 虫孔路由与虚拟直通方式很相似，也是将数据包分成一组组的微片，在头微 片中包含路由信息。头微片到达路由节点判断路由方向后将发送端口保留给后面 的微片，整个数据包就以流水的方式从保留的端口被发送出，直到发送出包尾后 释放发送端口。当发生阻塞时虫孔路由不需要在当前路由节点处存储整个数据 包，而是各个微片存储在阻塞发生时所在的路由节点里面。所以虫孔路由不但有 较小的路由转发延迟，而且每个路由节点处只需要很少的缓存空间。虫孔路由和 虚拟直通路由的传输延迟计算公式相同： t = i r w + r h 1 4 第二章片上网络的技术基础 数据包 _ _ _ 一阻塞 ill 一 o ；二：一一【二 源节点 虚拟直通 ，目的节点 虚拟直通 阻塞处理 _ 广_ _ _ 1 - 广一 l 卜乙_ _ m 阻塞； 二二二二 源节点目的节点 虫孑l 路由 阻塞处理 图2 6 发生阻塞时虚拟直通和虫孔路由的区别 虫孔路由的缺点在于只要一个数据包占用了一个端口开始发送后就独占了 这条通道，必须等到该数据包的所有微片被发送完后才会释放该端口，在这个过 程中其它数据包不能使用该端口。所以当数据包在某个路由节点发生阻塞时可能 会