（计算机软件与理论专业论文）高效的片上网络体系结构：核内路由.pdf

浙江大学硕士学位论文 摘要 近年来随着生产工艺的不断改进，单芯片多处理器( c h i pm u l t i p r o c e s s o r ， c m p ) 成为了提升计算机性能的主要途径。核心数量的不断增多，核问通信 量的不断增大，使得越来越多的研究者从片上网络( n e t w o r ko nc h i p ，n o c ) 出发研究核间通讯。目前n o c 上的研究大部分集中在对路由器各个部件的性 能优化方面，这些研究都是以路由器位于处理核心外部为基础，未能充分利 用n o c 各处理核心所具有的存储、带宽等资源。 本文通过对路由器内部存储的研究，针对处理器核具有一定的片内存储、 丰富的片内线宽资源的特点，将路由器集成到处理核心内部。这样可通过对 缓冲区的加速、对数据包传输过程的优化，形成高效节能的核内路由。 本文首先分析了片上网络与现实中的宏网络( m a c r on e t w o r k ) 的差异性， 然后对路由器的内部缓存进行了分类和研究，提出了一种将片上网络路由器 集成到处理器核心内部，以提升片上网络性能的解决方案。同时本文实现了 片上网络核内路由器设计，将该路由器集成到每一个单独的核中，并利用处 理核心片内存储，以及路由在核内执行的特点，对缓冲区的使用与数据包的 传输提出了四种优化策略( 发送b u f f e r 优化策略、退出b u f f e r 优化策略、提 前发送h e a df l i t 策略和消除t a i lf l i t 策略) ，以降低网络的平均延迟和能耗。 模拟实验表明，发送b u f f e r 优化和提前发送h e a df l i t 优化策略在b u f f e r 深度较高时可以有效地提升网络的性能，最好可以降低2 4 3 的平均延迟和9 的网络能耗。在b u f f e r 深度较低的情况下，混合使用退出b u f f e r 优化、消除 t a i lf l i t 优化的改进方案，最终可降低3 0 5 的平均延迟和3 7 8 的网络能耗。 据测算，本文提出的核内路由体系结构，可以比传统片上网络节省9 3 的芯 片面积。 综上所述，本文提出的片上网络核内路由解决方案将路由器集成到 处理器核内，以及相应的四种优化措施是可行、高效的，不但节省了芯片面 积，而且有效地降低了网络的平均延迟和能耗。 关键词：多核处理器，片上网络，低延迟，低能耗，片上网络模拟器 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，i m p r o v e m e n to fm a n u f a c t u r eh a sm a d ec h i pm u l t i p r o c e s s o r ( c m p ) t h e 砸m a r yw a yf o rp r o c e s s o rp e r f o r m a n c ei m p r o v e m e n t w i t ht h eg r o w i n g n u m b e ro fc o r ea n df r e q u e n tc o m m u n i c a t i o no nc h i p ，r e s e a r c h e r sh a v ep a i dm o l ea n d m o r ea t t e n t i o nt on e t w o r ko nc h i p ( n o c ) a tp r e s e n tm o s to fr e s e a r c h e sa b o u tn o c f o c u s e do nt h ev a r i o u so p t i m i z a t i o n so fm u t e rc o m p o n e n t s ，w h i c ha s s u m e st h a tr o u t e r i so u t s i d et h ec o r ea n df a i l e dt om a k eu s eo fl o c a lr e s o u r c eo fc o r es u c ha sm e m o r y a n db a n d w i d t h b yr e s e a r c h i n gi n t oi n t e r n a ls t o r a g eo fr o u t e r , t h i sp a p e ri n t e g r a t e sr o u t e ri n t o c o r r e s p o n d i n gc o r eo fw h i c hb a s e do nc h a r a c t e r i s t i c ss u c ha sl o c a lm e m o r ya n d r e s o u r c e f u lb a n d w i d t h t m sc a nl e a dt oa ne f f i c i e n ta n dp o w e r - s a v i n gr o u t e rb yb u f f e r e l i m i n a t i o n ，b u f f e ri m p r o v e m e n ta n dp a c k e tt r a n s m i s s i o no p t i m i z a t i o n t h i sp a p e rf i r s tc o m p a r e sn e t w o r ko nc h i pw i t hm a c r on e t w o r k , c l a s s i f i e s i n t e r n a ls t o r a g eo fm u t e r ，a n dr a i s e da ne f f i c i e n tn o ca r c h i t e c t u r e ：r o u t e ri n s i d et h e c o r e t h e n , f o u ro p t i m i z a t i o n s ( s e n db u f f e ro p t i m i z a t i o n ，e x i tb u f f e ro p t i m i z a t i o n , s e n d i n gh e a df l i ta h e a d ，t a i lf l i te l i m i n a t i o n ) a l ep r o p o s e db a s e do na n a l y s i so f r o u t e r si n t e r n a lb u f f e ru t i l i z a t i o na n dp a c k e tt r a n s m i s s i o np r o c e s st or e d u c ea v e r a g e p a c k e tl a t e n c ya n dp o w e r o fn e t w o r k s i m u l a t i o ne x p e r i m e n t ss h o wt h a ts e n db u f f e ro p t i m i z a t i o na n ds e n dh e a df l i t a h e a do p t i m i z a t i o nc a ne f f e c t i v e l yr e d u c ea v e r a g el a t e n c yb y2 4 3 a n dp o w e rb y 9 w h e nb u f f e rh a sl a r g e rd e p t h b ym i x i n ge x i tb u f f e ro p t i m i z ea n dt a i lf l i t e l i m i n a t i o n ，i tw i l le v e n t u a l l yr e d u c ea v e r a g el a t e n c yb y3 0 5 a n do fp o w e rb y 3 7 8 t h o u g hb u f f e ri so fs m a l ls i z e b e s i d e s ，a c c o r d i n gt oc a l c u l a t i o n ，i n t e g r a t i n g r o u t e ri n t oc o r ec a ns a v e9 3 c h i pa r e a t os u mu p ，r o u t e r - i n s i d e - t h e - c o r ea r c h i t e c t u r ea n df o u ro p t i m i z a t i o n 8p r o p o s e d i nt h i sp a p e ra r ee f f i c i e n ta n df e a s i b l e i tc a l ls a v ec h i pa r e a , r e d u c ea v e r a g el a t e n c y a n dp o w e rc o n s u m p t i o ne f f e c t i v e l y k e y w o r d ：m u l t i - c o r e , n e t w o r ko nc h i p ，l o wl a t e n c y l o we n e r g y , s i m u l a t o r 浙江大学硕士学位论文图目录 图目录 图1 1 常用网络拓扑3 图2 1 路由器功能简图一9 图2 4 虚线路虫洞路由器数据通路1 2 图3 1 通用n o c 体系结构1 7 图3 2 虫洞路由中的数据包结构1 8 图3 3 核内路由体系结构框架2 0 图3 4 核内路由详细结构2 0 图4 1 核内路由芯片面积2 2 图4 2 路由器b u f f e r 的分类2 3 图4 3 砌n g 拓扑下本地发送数据包与转发数据包的比例2 4 图4 4r i n g 拓扑下不同结点与发送b u f f e r 比重的关系2 4 图4 5 发送b u f f e r 优化2 5 图4 6 退出b u f f e r 优化。2 6 图4 7 改进退出b u f f e r 优化2 8 图4 8 路由延迟与端口数和虚线路数的关系3 0 图4 9 网络注入延迟的减少；。3 0 图4 1 0r i n g 拓扑下退出b u f f e r 优化对数据包平均传输时间的改进3 1 图4 1 1 一个数据包的产生和发送过程3 2 图4 1 2 控制包传输的时间代价。3 3 图4 1 3 提前发送h e a df l i t 3 4 图4 1 4 消除1 越lf l i t 3 4 图5 1n o x i m 的基本模块图3 6 图5 2g e n e r a t e 方法的流程图3 7 图5 3r x p r o e e s s 方法流程图3 8 图5 4 提前发送h e a df l i t 的t x p r o g e g s 流程图，3 9 图5 5 改进的n e x t f l i t 函数流程。4 0 图6 1 消除发送b u f f e r 的平均延迟4 4 图6 2 消除发送b u f f e r 的能耗4 5 图6 3 使用退出b u f f e r 优化的平均延迟。4 6 图6 4 使用退出b u f f e r 优化的能耗4 6 图6 5 提前发送h e a df l i t 的平均延迟4 8 图6 6 提前发送h e a df l i t 的能耗。4 8 图6 7 消除t a i lf l i t 的平均延迟4 9 图6 8 消除t a i lf l i t 的能耗4 9 图6 9 集成退出b u f f e r 和消除t a i lf l i t 优化方法的平均延迟5 0 图6 1 0 集成退出b u f f e r 和消除t a i lf l i t 优化方法的能耗。5 0 图a 1 前三个周期的网络状况。5 9 图a 2 偶数结点情况下各个路由器的负载情况。6 0 浙江大学硕士学位论文表目录 表目录 表2 1 各种流控制策略比较【2 】9 表2 2 路由b u f f e r 策略的比较一1 0 表4 1 第一种退出b u f f e r 优化的优缺点2 7 表6 1 典型的片上网络配置 4 4 1 4 2 表6 2 片上网络各组件的面积4 2 表6 3 路由器各组件的面积4 3 表6 4 实验参数4 3 表6 5 能耗参数【3 1 1 。4 4 表a 1 全负载流模式下路由器的负载情况。6 0 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝婆盘堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：豸长l 嘲 签字日期：驴召年名月7 日 学位论文版权使用授权书 本学位论文作者完全了解堑江盘堂有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者躲蜘 签字日期沙8 年6 月7 日 导师签名： 签字日期： 浙江大学硕士学位论文第l 章绪论 1 1 多核处理器 第1 章绪论 随着互联网和计算机的全球化，企业以及个人消费者都对计算机的性能 提出了极高的要求。由于c p u 主频的提升已经接近极限，为了实现对计算资 源的高效节能的利用，多核处理器开始进入人们的视野。最近几年层出不穷 的多核技术代表了计算技术领域的最新的成果。 所谓多核处理器是在单个芯片上中集成两个或多个执行核心，被称为 c m p ( c h i pm u l t i p r o c e s s o r ) 。这些核心能够同步运行多个进程或线程，实 现真正的并行处理。但它不同于已有的多处理器的思想。在多处理器的环境 中，每个处理单元享有独立的一级和二级缓存。而在多核心处理器的环境下， 为了进一步提高多进程之间的通信效率，将在多个单元之间共享二级或三级 缓存。类似的是操作系统同样将每个执行核心视为独立的处理器。 根据处理核心的功能相同与否可以将多核分为同构多核和异构多核。同 构多核中的每个计算单元拥有相同的体系结构，对所运行的任务没有特别的 要求，市面上流行的i n t e l 和a m d 的多核处理器就是这样的产品。而异构多 核架构中的不同核心具有不同的体系结构，某些特殊的核心往往被用于进行 特定的计算和处理。i b m 的c e l l 就是异构多核架构。 在多核平台上，由于每个独立的处理器并行完成不同功能，因此可以提 高任务运行的效率。理论上n 核心处理器的工作效率可以达到单核心处理器 的n 倍，但是实际工作中的效果往往达不到理想的情况，这是由于在程序运 行的过程中，存在着数据依赖。据此我们把并行分为两类，完全独立的并行 和有数据依赖的并行。 完全独立的并行是指两个或多个任务的运行不受对方运行状态的干 扰，同时自己的运行状态也无法影响对方的运行情况。这种情况在实 际运行中相对比较少见，例如图像的并行处理。 有数据依赖的并行是指两个或多个任务的运行依赖于其他任务的状 态，结果，输出等变量，同时也可能由于自身的变化对其他任务产生 影响。在实际应用中，这是非常常见的，比如循环的并行计算等。 1 2 片上网络概念 在传统的计算机内部，无论是处理器与北桥芯片之间，内存控制器与主存 l 浙江大学硕士学位论文第1 章绪论 之间，或者是高性能计算中所使用的多处理器之间，还是最近几年比较流行 的单芯片多核心之间，都是由不同的共享总线来连接和传送数据的。 随着处理器频率的不断提升，处理器对内存的存取速度已经极大地受到 了总线瓶颈的阻碍。而且单芯片多核心技术的出现使共享总线连接的方式更 加无法适应芯片内部低延迟，高通信量的要求。这是因为，在已有的编程模 型中，并行处理是利用进程和线程完成的。而在实际应用中，有数据依赖的 并行占了绝大多数的部分。进程线程之间的频繁交互对通信速度提出了很高 的要求。可以看到，近些年来总线频率也在不断提升，但是，由于总线是独 占性的资源，因此任何一对核间开始通信意味着其他的通讯请求必须等待。 同时随着制造工艺的不断完善，核的数量将继续增长，核内通信量特会越来 越大，传统的共享总线连接方式将极大地限制通信速度，造成不必要的延迟。 很自然地，用网络进行通信的方式被引入到片内连接中。在网络连接方 式下，任何两个核心之间的通信都可以独立的完成，并且只要采取合适的路 由策略和流控制策略，就能够以较低的延迟代价实现大数据量的并行通讯。 这同主机之间的网络连接相似。一般将这种传统的主机之间的网络连接 称为宏网络( m a c r on e t w o r k ) ，而称新的连接方式为片上网络( n e t w o r k0 1 1 c h i p ) ，英文简称为n o c 。类似的，片上连接的网络也是由结点，路由器， 网络接口所组成的。其中结点可以是不同的计算单元，存储单元，是数据包 的来源。网络接口用来将原始数据封装成适合网络传输的数据包，同时将收 到的数据包转化成原始数据。路由器决定了数据包转发的方式，是决定网络 性能的主要因素。对于追求高吞吐，低延迟的核间网络来说，路由器的微体 系结构最直接地影响了整个网络的性能。 同芯片间的网络连接和主机之间的网络连接不同的是，片内的网络有相当 多的“线”资源可以利用，比如可以在每个结点外引出更多的引脚。而芯片间 的引脚资源却被限制。根据【1 】，这种资源的比例是2 4 ：l 。也就是说，核间网 络有潜在的巨大的带宽可以利用。但是大的带宽带来的是高能耗，因此在网 络的选择和设计上，要考虑多方面的因素。 1 3 片上网络性能分析 一个网络往往具有以下几个主要特征，而这几个特征又影响了网络的性 能。比如拓扑结构，交换模式，流控制策略等。 1 3 1 拓扑结构 常用的拓扑结构包括m e s h ，r i n g ，t o r u s 等。 2 浙江大学硕士学位论文 第1 章绪论 0 囝强v 喇喇 图1 1 常用网络拓扑 如图1 1 所示砒n g 结构下，只有单一的通路，路由器的功能非常简单。 但是，这种结构下，正因为可选择的通路少，数据拥塞、死锁等情况将非常 严重。m e s h 结构类似矩阵，每个计算单元或存储单元位于其中的一个交点上。 t o r u s 结构可以认为是m e s h 结构的一个变种，它把矩阵行或列上的首位结点 联结起来，这种方式充分利用了上面所提到的核内的大量的引脚资源，一方 面减少了路由h o p 的次数，另一方面增加了带宽。另外用到的拓扑还有f a t t r e e 等。 1 3 2 交换模式 交换模式包括电路交换和包交换两种模式。 电路交换( c i r c u i ts w i t c h i n g ) 是指在数据传送前，首先由源结点发出请 求到目的结点，然后再接收来自目的结点的确认信号，由此来预先建立起固 定的数据通路的网络模式。这个通路建立的过程被称为“连接”阶段。以后的 数据传输都是根据这样的通路来进行，无论是否有其他可以传输的路径。在 数据传送完成后，连接的解除也是类似建立的过程。 电路交换模式下，由于路径确定，消除了路由选择的代价，网络将不会 出现拥塞状况。另外由于任何两对结点之间的通信不互相干扰，死锁的情况 也不会出现，因此通信的质量可以得到保证。但是由于线路被提前预定，该 网络无法适应实际变化的网络情况，可能会造成网络利用率低下的问题。 包交换模式将数据封装成包( p a c k e t ) ，根据包头的信息，通过路由选择 策略，一级一级地将数据包转发到目的地。因此逻辑上属于同一连接的数据 包物理上可能通过不同的路径来传送，这就使得对网络连接的利用更加公平， 提高了网络的利用率。同时，包交换模式使得属于同一个连接的数据可以“并 行”传播，提高了传播的速度。但是，这样的网络模式可能会由于路由策略的 选择不当造成拥塞和死锁。目前已经提出了很多在此模式下解决片内网络拥 塞和死锁的办法。 3 浙江大学硕士学位论文第l 章绪论 1 3 3 流控制策略 在包交换的网络模式下，为了解决片内网络的拥塞的死锁，可以考虑一 些已在现有的大规模网络中应用的流控制策略。这些策略主要包括存储转发 ( s t o r e a n d f o r w a r d ) ，虚切入交换( v i r t u a lc u tt h r o u g h ) 和虫洞路由( w o r m r o u t i n g ) 1 2 j 。首先现在来分析一下各种流控制策略的特点，以确定它们是否适 合应用在高速的片内的网络连接上。 如果使用存储转发的方式，则路由器将存储每一个接收到的数据包，并 且只有在置个数据包已经完整地被接收到之后，才会转发出去。这样一来， 在等待剩余数据包的时间里，网络连接将一直空闲，网络利用率会比较低。 而且这样的存储方式要求路由器中的b u f f e r 至少等于一个包的大小，对于要 缓存多个包并进行转发的路由设计，将导致大的b u f f e r 容量，同时也意味着 将占用较多的芯片面积，而在片内网络的设计中，这是不允许的。 虚切入交换的方式不等待完整的包被接收到，相反，它把数据包分解成 为更小的片( f l i t ) ，尽可能地利用了网络连接的空闲。只要下一个接收的 目的路由拥有接收一个数据包( p a c k e t ) 大小的空闲b u f f e r ，并且线路未被占 用，就立刻发送即使未完整到达的数据包。这种办法降低了通讯延迟，提高 了网络连接的利用率，但它仍然需要为每个包保留一个包大小的b u f f e r 。为 了减少b u f f e r 的大小，需要改变缓存整个包的策略。 虫洞路由就采取了这样的方式。它同样把数据包分解成为更小的片 ( f l i t ) ，每个f l i t 像极小的“蠕虫”一样逐个通过路由，所不同的是只要当接 受端路由器拥有可容纳一个f l i t 大小空闲b u f f e r 的时候，该f l i t 就被上一个 路由器所发送。因此可以降低网络延迟，提高网络利用率，也可以节省b u f f e r 的空间。另外一旦某个该路由器的发送端被属于同一个数据包的f l i t 所标识 并占据，且其中的f l i t 被阻塞，则由于每个数据包对物理路径的独占性，这 样的方式可能会引起死锁【2 】的出现，相反降低网络的利用率。 1 4 研究难点 根据上面几节的叙述，核间高通讯量，低延迟的需要对片内的连接提出 了新的要求。相对于共享总线的连接，将各个处理核心作为结点，通过网络 连接起来的方式更好地分散了通信线路的压力，因为网络可以并行地处理多 个通信结点对的通信。 尽管解决了由于共享总线而带来的通信资源竞争问题，网络中的通信效 率问题同时呈现在我们面前。网络中的通信延迟包括通信线路延迟，路由器 4 浙江大学硕士学位论文第l 章绪论 的数据包存储延迟，路由仲裁延迟，数据包转发延迟来决定。通信线路延迟 受到技术工艺的限制，相对比较固定。而其他的延迟却可以通过采用不同的 策略来减少。已经有很多研究通过预先配置合适的路径，消除仲裁的延迟， 将每个路由的延迟降低到1 个时钟周期【3 】【4 】【5 1 。更进一步的，有人利用三态门 作为路径的选择开关，将该延迟降低到了0 7 个时钟周期【6 】。但这些方法需要 应用在一些关键的路径上。所谓关键路径即是指数据包频繁通过的路径。对 于另外一些非关键路径，路由仲裁的延迟依然无法有效改进。 1 5 本文工作 本文通过对片上网络与宏网络( m a c r on e t w o r k ) 的比较分析以及对路由 器内部存储的分类研究，提出了一种将片上网络路由器集成到处理器核心内 部，提升片上网络性能的解决方案。同时本文实现了片上网络路由器设计， 并以此为基础提出了四种降低路由器的平均延迟和能耗的策略。 本文的具体研究工作包括： 1 提出全负载流模式并进行分析。 2 在全负载流模式下，对路由器b u f f e r 的分类研究。 3 提出核内路由的体系结构，为降低片上网络的能耗和延迟开辟了新的 研究空间。 4 在核内路由的基础上，提出了下面四种改进方案。 a ) 发送b u f f e r 优化 b ) 退出b u f f e r 优化 c ) 提前发送h e a df l i t 优化 d ) 消除t a i lf l i t 优化 5 基于传统片上网络模拟器的核内路由模拟器的设计。 1 6 论文结构 下一章主要介绍了从n o c 概念提出以来各个方面的研究，包括流控制策 略，路由器微体系结构，n o c 能耗，n o c 模拟平台。第三章详细说明了本文 提出的核内路由的体系结构并与传统的通用n o c 体系结构进行了比较。第四 章对核内路由的设计与优化进行了详细的描述，并对改进后的性能进行了初 步分析。为了对本文的想法进行论证，我们在已有n o c 模拟器的基础上进行 了修改并进行了实验。第五章讲解了核内路由模拟器的修改和实现过程。第 六章列出了实验结果并进行了分析。第六章是对本文的总结和对片上网络核 内路由未来研究的展望。 s 浙江大学硕士学位论文第1 章绪论 1 7 本章小结 本章首先介绍了课题研究的背景多核处理器发展的概况，然后分析了 在共享总线连接方式的不足。针对这种不足，本章介绍了近几年来新提出的 片上网络连接方式( n e t w o r ko nc h i p ) 以及决定网络连接性能的三点因素： 拓扑结构，交换模式和流控制策略。同时我们认为片上网络研究的难点主要 集中在如何降低网络延迟特别是路由器的延迟上。最后，本章列出了本文工 作的要点以及论文结构。 6 浙江大学硕士学位论文第2 章片上网络研究 第2 章片上网络研究 2 1n o c 概念的提出 2 0 0 1 年，s t a n f o r d 大学计算机系统实验室的w i l l i a mj d a l l y 和b r i a n t o w l e s 提出芯片内部的通讯数据应通过转发的方式，即网络的方式来实现， 而不是用导线直连的方式【1 】。网络上的每个结点被称为一令t i l e ，即网络客户 端。客户端可以为处理器，d s p ，存储，外围控制器或者与其他芯片网络的 接口。相比与共用总线的连接方式，网络提供了结构化，高性能和模块化的 优点。同时网络拥有高的带宽，且支持多个同步的通信，而且网络的方式提 供了一个简单可靠的底层数据报服务，不同的客户端可以在这样的基础上实 现不同的协议，比如内存读写，流控制数据服务等，因此网络为不同的单元 提供了统一的底层访问接口。 但是由于片内网络与片间网络甚至是板间网络的不同特点，n o c 体系的 设计面临许多新的挑战。比如片内网络具有大量的导线和引脚资源可以利用， 但b u f f e r 空间却十分受限。这些不同导致新的网络拓扑，流控制方法和其他 技术需要研究和改进。 拓扑结构涉及到数据包所进行的平均跳转次数和平均传输距离，而这些 变量直接关系到能耗的大小。数据包在m e s h 结构下就比t o r u s 结构有更多的 平均跳转次数，而t o r u s 结构的能耗更易受平均传输距离的影响。所以，如果 导线传输能耗占据了主要的因素，则m e s h 结构比t o r u s 结构更高效【1 】。 流控制方面，b u f f e r 的大小对路由体系结构的设计非常关键。大的b u f f e r 可以减少竞争和拥塞，但无法满足芯片面积的限制。采用小的b u f f e r ，可以 节省空间，但是必须采用其他一些丢弃包或者重新转发的策略，这样增加了 导线的负载，也增加了能耗。 其他技术比如，电路的技术革新，也可以提高网络的性能。如果单个导 线在每个时钟周期可以发送多个b i t 的话，就可以提高整个网络的带宽，同时 减少对b u f f e r 的压力。在o 1 斗m 技术下，单个导线可以达到4 g b s 的传输速 度。但是这需要电路技术的革新，达到相同的频率以驱动这样的传输。同时 随着n o c 技术的发展，不同的网络客户端可能会要求运行在不同的频率上， 所以将需要电路提供高频率连接与低频率连接之间的接口。 电路的改进也可以把b u f f e r 集成到驱动器，接收器和中继器里以取代在 本来输入输出控制器里大面积的b u f f e r 。 7 浙江大学硕士学位论文 第2 章片上网络研究 n o c 提供的是一种普遍的服务媒介。同专用的导线和共享总线相比， n o c 的使用会带来一些额外的代价。比如大概会有6 6 的芯片面积被花费在 路由器上，且数据传输的过程中引入了控制信息的代价。可是相比之下，n o c 的使用，无论在硬件设计和可预测的性能参数方面的优点都要更加突出，这 包括： 可预测、结构化的导线布局【lj 。专用导线提供了高性能，但由于物理限制， 往往跨越了很大的距离，因此对相邻的导线造成了寄生电容和干扰，并且 这些交叉影响难以在设计时期进行预测。而n o c 将导线的布局结构化， 结点之间的路径在设计时候就已经被定义，减少了后期设计的修改过程。 统一的接口设计【1 1 。通过网络这样一个统一的接口，所有的系统组件可以 进行重用，否则就要为不同的控制器设计一个接口。 网络本身具有可重用性【l 】。网络本身作为一个整体，允许设计者加入其他 的资源，以进行不同的设计和验证。 提高导线的利用率【1 1 。根据估计，尽管芯片中的专用导线或者总线在传输 时总是全速地运行，但大部分时间却是处于空闲状态，这个空闲的时间超 过9 0 。n o c 通过在信号之间共享导线资源，提高了导线的利用率。 信息的并行处理。多对客户端的通信存在是物理路径，所以通信可以完全 并行地进行。另外同一对客户端的通信可以存在多个物理路径，数据将以 流水线的方式同时发送。 由此可以看出，n o c 作为一种新的片上连接方式，其结构非常类似已经 研究多年的宏网络。但是，许多的新特点也给研究人员提出了新的挑战。下 面几节将介绍近些年来n o c 相关的一些研究。 2 2n o c 上的流控制 n o c 上的流控制应该满足低b u f f e r ，低延迟，高吞吐的要求。根据1 3 3 节的叙述，存储转发和虚切入交换的方式需要存储整个包的大小，此外，存 储转发的方式由于需要等待整个包的到达浪费了带宽，使得转发的延迟增加。 虫洞路由的方式采用部分发送的思想，只要线路允许，将到达的包立刻发送 出，降低了不必要的延迟。不同于虚切入交换的是，它只需要下一个目的路 由拥有一个f l i t 大小的b u f f e r 即可。因此，尽管在宏观网络中存储转发的方 式得到了很好的利用，但在n o c 中，根据相关的特点，虫洞路由的方式却得 到的普遍的认可。 表2 1 比较了各种流策略的优缺点，容易看出虫洞路由对b u f f e r 的需求 最低且延时最少，因此成为了目前研究的主流。 8 浙江大学硕士学位论文 第2 章片上网络研究 表2 1 各种流控制策略比较f 2 】 麓瓣燃獭嬲锱僦擎缓g 熬鬈霸黼黼 嬲燃颧戮凝燃灞攥鳓瓣 存储转发大( 一个包)大( 一个包)范围小，只涉及相邻通讯结点之间 虚切入交换大( 一个包)小( 一个片)范围小，只涉及本地结点 虫洞小( 一个片)小( 一个片)范围大，数据包跨越的各结点之间 但虫洞路由有其本身的缺点易造成大量的延迟。这是由于单一数据 包物理路径的独占性，如果某个数据包中具有较多的f l i t ，则可能会大量占用 物理资源，造成其他依赖于该通路的连接阻塞。如果这样的依赖形成环，则 网络死锁的情况将会出现。目前针对死锁的研究有 虚路径。这种方式定义了多个逻辑路径，他们相互独立，数据传送不 互相影响。通过选择合适的路由策略，可以消除资源依赖图中环的出 现【6 1 。 有方向性的路由策略。合适的路由策略应避免数据包在网络中循环运 动。比如x y 路由策略，在以x y 坐标安排网络结点时，它优先将数 据沿x 轴发送，直到到达目的路由所在的y 轴，再沿y 方向发送。 这样的要求也可以被减弱，比如只要要求数据包每次发送的方向都保 证与目的路由的距离在减少就可以，因为这样在数据包的传播路径 上，最多形成矩形的两条边，而无法形成三条以上的边1 6 】。 另外从使用模型上看，可以把数据流传输分成面向连接的和非面向连接 的流。它们分别提供了g u a r a n t e e ds e r v i c e 和b e s te f f o r ts e r v i c e 。g u a r a n t e e d s e r v i c e 提供了带宽保证，但是路径的建立阶段需要花费时间。而且充分利用 g u a r a n t e e ds e r v i c e 的基础是在某个固定的时间段内某个连接线上只存在一个 活动连接。b e s te f f o r ts e r v i c e 提供了高的吞吐量，但是无法在最坏的网络状 况下保证带宽1 2 】【引。 2 3n o c 上的路由器 数据包广 广_ 1 广 广1 叫存储卜- 叫路由选择卜- 刊仲裁，通路硬件资源分配卜叫c r o s s b a rl l - - 。一l 一l ，j l ，一 图2 1 路由器功能简图 图2 1 给出了n o c 上路由器的功能简图，这适用于虫洞路由和非虫洞路由。 本文以虫洞路由为研究基础。由于虫洞路由器本身容易造成死锁的缺点，早在 1 9 9 2 年w j d a l l y 就提出了虚线路( v i r t u a lc h a n n e l ) 的思想，主要方法是把 物理上唯一的通路分成逻辑上不同的线路，在数据包传递中无需考虑对物理 资源的竞争问题，代价是在路由器中加入了b u f f e r 和仲裁器t 9 1 。因此大量关 9 浙江大学硕士学位论文第2 章片上网络研究 于路由器的研究以虚线路和虫洞路由相结合为基础，方向涉及硬件性能比如 延迟和能耗，以及路由控制比如b u f f e r 动态分配。总而言之，针对路由器的 研究主要集中在这四个部分：存储( b u f f e r ) ，路由选择，仲裁和通路硬件资源非 配以及c r o s s b a r 。 2 3 1b u f f e r 对图2 1 中的研究涉及如何合理放置b u f f e r 以解决路径资源冲突并提 高网络利用率的问题，有三个主要的方式，o u t p u tq u e u e ，i n p u tq u e u e 和 v i r t u a lo u t p u tq u e u e ，各自的特征如表2 2 所示。 表2 2 路由b u f f e r 策略的比较 隧凝鬣黼糕鬻阚熏霸飘 o u t p u tq u e u e 8 l 【1 0 】 位于输出端口，需要n 2 个队列n 大时，需要连线 依赖多路选择多 器 i n p u tq u e u e 8 】【1 o 】 位于输入端口，需要n 个队列h e a d - o f - l i n e 【1 1 】 依赖调度单元 b l o c k i n g 影响，网 络利用率低 v i r t u a l 位于输入端口，需要n 2 个队列 n 大时，连线数并 o u t p u tq u e u e 8 】 依赖c r o s s b a r不大量增加，网络 【1 2 1 3 】 利用率高 另外， 1 4 1 5 儿1 6 】的研究表明，路由器使用的b u f f e r 占据芯片上b u f f e r 总量 的6 0 ，同时也消耗了整个芯片6 0 的泄露能耗。因此如何提高b u f f e r 的利 用率，合理分配并尽量减少使用成为了图2 1 中研究的焦点。【1 7 】完全避免 了b u f f e r 空闲的可能。另外为了使得b u f f e r 分配更加合理，1 1 8 儿1 9 】提出了动态 分配的方法，随着某条线路的流量增加，需要的b u f f e r 队列长度也会增加。 另外，【2 0 】在分析了各种b u f f e r 分配的基础上，认为芯片内部高速串行线的延 迟和单个虚线路带宽的增加，直接导致了对b u f f e r 的高需求，同时指出在这 种趋势下，采用虚切入交换的方式将更适合。i s 】使用专门的硬件f i f o 队列， 有效减少了b u f f e r 的面积。 2 3 2 路由算法 对图2 1 中的研究主要是指路由算法方面，路由算法的任务是确定数据 包的下一个目的结点以及需要通过的线路，然后在图2 1 中对该线路资源 进行申请。路由算法可以分成确定性和非确定性两类。如果使用确定性的路 l o 浙江大学硕士学位论文 第2 章片上网络研究 由算法，那么源结点和目的结点之间通信发送的所有数据包在网络中的遍历 路径是确定的。比较流行的确定性算法有s o u r c er o u t i n g 和x - yr o u t i n g ( 使用 在2 维的m e s h 拓扑结构中) 。s o u r c er o u t i n g 中，由数据包发出时就已经确 定好了要走的路径。x yr o u t i n g 中包首先沿着x 方向前进，然后再沿着y 方 向到达目的结点。适应性的路由算法以每个路由器为单元动态地选择路由方 向，比如根据当时的网络拥塞状况来判断。这要求更加复杂的路由器实现， 但是可以保证网络的负载均衡。 死锁的出现是指某个数据流在申请别人占有的线路的同时，也占有了别人 正在申请的线路资源。这样的关系形成环的话，就出现了死锁。在2 dm e s h 拓扑中使用x yr o u t i n g 时，由于不可能在网络中形成环路，因此可以避免死 锁的出现。在n * n ( n 3 的时候，当出现图2 2 的 情况时候，死锁就出现了。图中的箭头表明资源请求关系，比如虚线箭头表 示结点l 占有到达结点2 的线路资源并申请到达结点3 的资源，而加粗的箭 头表示结点4 占有到达结点5 的线路资源并申请到达结点1 资源。这样就形 成了占有并等待的资源依赖关系环。 图2 2 死锁出现图2 3 死锁避免 对于n = 4 的情况，死锁是可能出现的，但只要规定数据发送的方向是一 定的，则可以避免死锁。针对于n 4 的情况，【z l j 提出了c y c l e b r e a k i n g 的路 由算法。如图2 3 所示，他通过选择一个结点，规定以其为目的地的数据流 不使用t o m s 中连接两端的长连接线，而其他的数据流依然以最短路径为路 由原则，并且可以使用长连接线。这种方式打破了资源申请关系环的出现， 因此可以有效地避免死锁。 图2 3 中的阴影结点代表了其中一种选择策略，其中打破了环形关系的关 键是结点5 对结点2 的申请方式，如该图中粗箭头所表示。 l l 浙江大学硕士学位论文第2 章片上网络研究 2 3 3 通路资源仲裁 对图2 1 中的研究是目前研究的焦点，它涉及到是否能够以低的控制和 延迟代价来接通物理通路，是否能够解决竞争的请求。这是造成路由器平均 延迟的主要部分。 采用虚线路的虫洞路由功能组件和数据通路如图2 4 表示。 图2