（通信与信息系统专业论文）片上网络分层交换结构设计及性能研究.pdf

南京邮l 乜人学硕l ：研究生学位论文 摘要 摘要 片上网络是近年来众核片上系统中的研究热点之一，它将通信网络技术引入到芯片设 计之中，以突破传统总线连接方式所导致的核问通信的约束。目前，针对片上网络的面积 与功耗、布线复杂度、可扩展性等设计需求，人们通常采用m e s h 拓扑和单层交换方式来 构建片上网络的基础结构。然而，随着芯片工艺水平的不断提升，片内核的数量持续增长， 这种单层m e s h 结构在通信性能上表现出一定劣势，因此，探索新的路由或交换体系结构 成为片上网络的一项重要研究内容。 本文借鉴了计算机通信的分层组网技术，结合片上网络的特点，引入三层交换模型， 提出了一种三层片上网络结构，以降低芯片布线冗余度，并提高通信性能。它将片上网络 内交换节点分为接入级、汇聚级、核心级三个级别。资源节点分布在网络边缘，通过与接 入级交换节点相连接入到网络；接入级交换节点彼此相连并连接到上层的汇聚级交换节 点；汇聚级交换节点彼此相连并连接到核心级交换节点。这种结构可减少芯片中通信部分 的而积占比，减少核问的通信跳数，同时具有较低的布线复杂度。 本文选取了n s 2 作为仿真平台，设计了仿真方案，对三层片上网络结构的性能进行了 分析。研究表明，在同等网络规模下，相比于采用m e s h 拓扑的c l i c h i 羔结构，三层片上 网络结构的平均包时延降低了约1 6 个百分点，吞吐率提升了约3 个百分点，丢包率降低 了约9 个百分点。在高负荷下，三层片上网络结构的吞吐性能提升更为明显。此外，三层 片上网络结构具有更高的最大零丢包运行速率。研究还发现，单纯提高交换节点的缓存容 量，并不能有效改善三层片上网络结构的丢包率，反而会导致时延性能下降。 关键词：片上网络，三层交换结构，结构设计，仿真，性能分析 南京邮i 乜人学硕i ：研究生学位论文 a b s t r a c t a b s t r a c t n e t w o r ko nc h i p ( n o c ) i so n eo ft h ea c t i v er e s e a r c ha r e ao fm u l t i c o r es y s t e mo nc h i p ( s o c ) i nr e c e n ty e a r s i tu t i l i z e st h ec o m m u n i c a t i o nn e t w o r kt e c h n o l o g yf o rt h ed e s i g no ft h e c h i pt ob r e a kt h r o u g ht h eb o t t l e n e c kw h i c hc a u s e db yt h eb u sc o n n e c t i o n c o n s i d e r i n gt h e r e q u i r e m e n t s i nc o m m u n i c a t i o na r e ai n c h i p ，p o w e rc o n s u m p t i o n ，i m p l e m e n t a t i o nc o s t ， s c a l a b i l i t ya n do t h e rf a c t o r s ，m e s ht o p o l o g ya n ds i n g l e - l a y e rs w i t c h i n gm o d ea r eo f t e nu s e dt o b u i l du pt h ei n t r a - c h i pc o m m u n i c a t i o ni n i l a s t r u c t u r ei nn o c h o w e v e r , w i t ht h eg r o w t ho ft h e i n t e g r a t e dc o r e so n as i n g l ec h i p ，t h es i n g l e l a y e rm e t h o d o l o g ys h o w ss o m e k i n do fd i s a d v a n t a g e o nc o m m u n i c a t i o np e r f o r m a n c e ，s oh o wt of i n dan e wr o u t i n go rs w i t c h i n ga r c h i t e c t u r eh a s b e c o m ea l li m p o r t a n tr e s e a r c ha r e ai nn o c d e s i g n b yr e f e r r i n gt h ec o n c e p to ft h eh i e r a r c h i c a ls w i t c h i n gm o d e lo ft h ec o m p u t e rn e t w o r k ，a 3 1 a y e rn o ca r c h i t e c t u r ei sp r o p o s e d a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fn o c ，t or e d u c et h e r e d u n d a n c yo fw i r i n ga n di m p r o v et h ec o m m u n i c a t i o np e r f o r m a n c e t h ea r c h i t e c t u r ec o n s i s t so f t h es w i t c hn o d e sc l a s s i f i e di n t ot h r e el e v e l s ：a c c e s sl e v e l c o n v e r g e n c el e v e la n dc o r el e v e l t h e r e s o u r c en o d e sd i s t i l b u t ea tt h ee d g ec o n n e c t i n gb ya c c e s sn o d e st ot h en e t w o r k ，t h es w i t c h n o d e sw i t h i nt h ea c c e s sl e v e la r ec o n n e c t e de a c ho t h e ra n du p l i n k e dt oc o n v e r g e n c es w i t c h e s ， a n dc o n v e r g e n c es w i t c h e sa r ec o n n e c t e de a c ho t h e ra l s oa n du p l i n k e dt oc o r es w i t c h e s t h e p r o p o s e da r c h i t e c t u r ec a nr e d u c et h ec h i pa r e ar e q u i r e db yt h es w i t c hn o d e s ，t h eh o p sb e t w e e n t h ee n d s ，a n dt h ew i r i n gc o m p l e x i t y n s 2w a ss e l e c t e da so u rs i m u l a t i o np l a t f o m l w ed e s i g n e dt h es i m u l a t i o np r o g r a ma n d a n a l y z e dn u m e r i c a l l yt h ep e r f o r m a n c eo ft h e3 1 a y e rn o ca r c h i t e c t u r ec o m p a r e dt ot h ec l i c h e w h i c hb a s e do nt h em e s ht o p o l o g y t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ea v e r a g ep a c k e td e l a yi n t h e3 1 a y e rn o ca r c h i t e c t u r ed e c r e a s e sa b o u t16 。t h et h r o u g h p u tr a t ei n c r e a s e sa b o u t3 ，a n d t h ep a c k e td r o pr a t i od e c r e a s e sa b o u t9 f o rt h es a m en e t w o r ks c a l e t h et h r o u g h p u t p e r f o r m a n c eo ft h e3 - l a y e rn o ca r c h i t e c t u r ei m p r o v e sm o r eo b v i o u s l yt h a nt h ec l i c h eu n d e r h e a v yt r a 衔cl o a d e d i na d d i t i o n t h em a x i m a lp a c k e tr a t ew i t hz e r od r o p p e di sh i g h e rf o rt h e p r o p o s e da r c h i t e c t u r e t h er e s u l t sa l s os h o wt h a tt h eb u f f e rs i z ei n c r e a s i n gi ns w i t c h e sl c a d st o n os i g n i f i c a n ti m p r o v e m e n ti nt h ep a c k e td r o pr a t i oo ft h e3 - l a y e rn o ca r c h i t e c t u r e b u ti n c r e a s e i nt h ed e l a y k e y w o r d s ：n e t w o r ko nc h i p ( n o c ) ，3 - l a y e rs w i t c h i n ga r c h i t e c t u r e ，s y s t e md e s i g n ，s i m u l a t i o n ， p e r f o r m a n c ee v a l u a t i o n 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均己在论文中作了明确的说明并表示了谢意。 研究生签名：毒啦r 期：三竺笠垒上 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊迸) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究牛部办理。 研究生签名：嗵导师签名：j 卑日期：互竺蝉 南京邮电人学硕i ：研究生学位论文第l 章绪论 第1 章绪论 1 1 片上网络的技术发展过程 进入到超大规模集成电路时代以来，芯片的工艺水平依然在不断的提升，摩尔定律仍 旧发挥着它的作用。随着工艺水平的4 i 断提升，集成电路现己进入纳米阶段，如今，4 5 n m 工艺制程的：签片已经量产，3 2 n m l 艺处理器也即将投入生产，集成芯片的尺寸越来越小， 单个芯片集成的晶体管数量也越来越多。由于信息市场的需求和微电子自身的发展，引发 了以微细加工为主要特征的多种工艺集成技术和面向应用的系统级芯片的发展，在单一集 成电路芯片上就可以实现一个复杂的电子系统。这对集成芯片设计方法的研究提出了挑 战。 现阶段一种十分常用的芯片设计方法被称为片上系统( s o c ，s y s t e mo nc h i p ) ，在片 上系统中集成了数量众多的i p ( i n t e l l e c t u a lp r o p e r t y ) 核，包括处理模块，存储器模块， d s p 模块等，它们采用同步时钟，总线( b u s ) 连接方式进行内部通信。片上系统设计方法 的出现和发展，解决了通信、计算、消费电子( 3 c ) 等领域的众多挑战性难题。然而随着 芯片规模的不断增长，内部i p 核的数量不断增加，传统的基于同步时钟的总线连接方式遇 到了瓶颈：( 1 ) 由于s o c 内各i p 核间的通信必须通过总线，而随着芯片频率的不断提升， 其通信速率已经极大地受到了总线速率的阻碍，而且随着i p 核数量的不断增长，共享总线 连接的方式更加无法适应芯片内部低时延，高通信量的要求。( 2 ) 由于总线是独占性的资 源，因此任何一对核间开始通信意味着其他的通讯请求必须等待，i p 核的利用率很低，这 极大的浪费了片内资源。 计算机网络能够有效解决大量资源之i 、日j 通信的问题，这也为芯片系统的设计提供了一 种新的思路。将传统计算机网络的设计思想引入到芯片设计中来，这就是片上网络( n o c ， n e t w o r ko nc h i p ) 。片上网络概念的提出最1 1 见于国外学者发表的一些论文中：2 0 0 0 年5 月，法国p i e r r ee tm a r i ec u r i e 大学的p i e r r eg u e r r i e r 等人提出可升级、可编程的集成网络 ( s p i n ) 【l 】，将并行计算中分组交换( p a c k e t s w i t c h e d ) 的方法引入系统芯片。2 0 0 0 年1 1 月，瑞典皇家技术学院等单位提出“n e t w o r ko nac h i p ”概念，把n o c 定义为一块芯片上 实现的，由交换开关网络互连的计算资源、存储资源以及i o 资源的片上网络。2 0 0 1 年6 月，斯坦福大学的w j d a l l y 等人发表沦文【2 1 ，提出使用片上互连网络通过数据包通讯的 方式替代各式各样的连线结构的构想。 南京邮电 学硕十研究学位论立 第】绪论 【a ) u s p i c b 7 ， ( b 1n o t w o r k 幽1 一i 芯片内翻5 通信结构示意图 在刚络连接方式下，任何两个核心之间的通信都可以独立的完成，并且只要采取合适 的路 | = i 策晰和流控制策略，就能够以较低的时延代价实现大数据萤的并行通讯，这吲主机 之间的刚络连接相似。类似的，片上连接的1 嘲络也是由结点，路由器，网络接所组成的。 其中结点c 玎以是不同的计算单几，存储单儿等i p 核，是数据包的柬源。网络接口用来将原 始数据封装成适合网络传输的数摒包，同刊将收到的数据包转化成原始数据。路山器决定 了数据包转发的方式，是决定网络性能的主蜚凼索。对于追求高吞吐，低时延的核问网络 来说，路山器的微体系结构最直接地影响了整个网络的性能。 片上嘲络的研究初衷是探索s o c 通信部分的系统缴设计方法，但是研究工作很快涉及 到从物理层设计到体系结构、操作系统以及应用等各个层面。日前的n o c 概念很宽泛，包 括硬件通信结构、中间件、操作系统通信服务以及设计方法和工具等。从系统结构角度来 看，n o c 研究的重点是其拓扑结构、协议、服务质量和低功耗等。 1 2 片上网络的技术特点 21 芯片设计 全局连线上的信号时延次定了系统的时钟一周期，为了保持甚至提高系统时钟频率，只 能对全局连线进行分m 流水，或者采片j 区域可步全局异步的时钟模式，片上网络就是一种 全局异步局部同步( g a l s ，g i o b e a 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 ) 的设计方沾。此外， 相比总线连接方式，网络连接方式提供了结构化，高性能和模块化的优点。同时网络拥有 高带宽，且_ 吏持多个同步的通信，而且网络的方式提供了一个简单可靠的底层数据撤服务， 不同的客户端町以在这样的基础卜实现不同的梆议，比如内存读写，流控制数据服务等， 因此网络为不同的单兀提供丁统一的底层访问接口。与此同时，n o c 的使用会带来一些额 南京邮电入学硕i ：研究生学位论文第l 章绪论 外的代价。比如大概会有一部分芯片面积被仡费在路由器上，且数据传输的过程中引入了 控制信息的代价。可是相比之下，n o c 的使用，无论在硬件设计和可预测的性能参数方面 的优点都要更加突出，这包括： 高吞吐量：总线是一种共享介质的互连结构，某一时刻只允许一个i p 核使用总线。仲 裁逻辑允许高优先级的i p 核获得总线的使用权，在总线被占用期间，所有其他的请求被阻 塞，直到总线空闲。如果数十个i p 核争用一条总线，很难想象结果会是怎样。这还没考虑 由于太多的组件连接到总线上而导致的总线频率降低等因素。而片上网络结构通过交换 网络将各i p 核连接在一起，各个i p 核之白j 可以独立进行通信，不需要等待总线资源的释 放，其通信具有并发性，这就决定了片上网络具有较高的吞吐性能。 统一的接口设计：通过网络这样一个统一的接口，所有的系统组件可以进行重用，否 则就要为不同的控制器设计一个接口。 较高的资源利用率：根据估计，尽管芯片中的专用导线或者总线在传输时总是全速地 运行，但大部分i p 核资源却是处于空闲状态，对于高集成度的芯片，这个空闲的时问超过 9 0 。n o c 通过并发通信，提高了资源的利用率。 可预测、结构化的导线布局：专用导线提供了高性能，但由于物理限制，往往跨越了 很大的距离，因此对相邻的导线造成了寄生电容和干扰，并且这些交叉影响难以在设计时 期进行预测。而n o c 将导线的布局结构化，结点之| 、日j 的路径在设计时候就已经被定义，减 少了后期设计的修改过程。 可重用性：在片上系统设计中，可重用性是一个重要的设计原则。可重用性设计可以 节省设计成本，提高设计的可靠性，缩短产品的上市周期。在基于总线的片上系统设计中， 各个i p 组件是重用的，但通信结构却无法再用。每个设计都需要重新设计通信结构。在片 上网络中，除了各个组件是可重用的，片上通信结构以及片上的通信服务也是可重用的。 设计新的系统时，在原有的系统上添加路由器和新的功能部件就可以了，以前的设计得到 了重用，大大加快了设计的进度。 低功耗：总线结构中，采用广播方式进行通信，使得系统的功耗浪费在无效的通信上。 在片上网络中，由于采用全局异步、局部同步设计，端到端的通信方式，只有参与通信的 组件是激活的，因此大大降低了系统的功耗。 1 2 2 网络结构设计 ( 1 ) 信号传播时延 雨京邮电入学坝f ? 研究生学位论文第l 章绪论 众所周知，传统计算机网络的链路长度一般较大，通常在几千米到数百千米，甚至于 数千千米。而片上网络的链路长度是以毫米为单位，整个芯片的宽度也就l 到2 个厘米。 我们计算传输时延的时候，通过介质中的光速计算出的时间是5 微秒千米，那么不难算出 传统计算机网络的时延通常在几微秒到几毫秒之问；而片上网络则在几皮秒到几十皮秒之 间，可见其巨大的差别。 ( 2 ) 环境干扰与系统可靠性 计算机网络由于链路长度较大，所以所受到的干扰比较大，信噪比低，所以传输时延 高，误码率较高。如果网络中有环节受损，那么可以很方便的整修或者替换。 片上网络位于芯片之内，受到的干扰主要为内部串扰，信噪比较高，误码率较低。而 且一般芯片的寿命一般在几年甚至几十年之问，网络结构稳定，可靠性较高。 ( 3 ) 链路传输带宽 传统计算机网的传输带宽一般以m b i t 为单位，我们所熟悉的以太网传输带宽有 1 0 m b i t ，1 0 0 m b i t ，1 0 0 0 m b i t 。而片上网络中，单线带宽往往能够达到几个g b i t ，甚至更高。 ( 4 ) 传输控制与管理 在片上网络的路由决策时，可以提供服务质量，对关键部件的网络带宽或者时延进行 保证，没有被保证的通信采用尽力而为的传输策略，片上网络通过流控机制来保证服务质 量。但是，与计算机网络不同是，片上网络没有专门的协议处理机，协议必须由硬件处理， 这就要求片上网络协议不能太复杂。 1 3 研究现状 片上网络的概念自提出以来，已经吸引了各国的学者以及研究机构的重视，不同的研 究机构对片上网络的研究重点不同，其中一些著名机构的研究成果代表了目前片上网络的 研究水平，下面就将对一些具有代表性的工作做一些简要的介绍【3 】。 ( 1 ) n o s t r u m 工程 n o s t r u m 是瑞典k t h 研发的一种n o c 体系结构，它主要研究从物理层到应用层的通 信问题，n o s t r u m 是通过将每个路由节点连接到另外四个路由节点而形成一个规则的二维 m e s h 拓扑结构，一个i p 核连接到一个路由节点。交换网络采用了同频不同相的伪同步时 钟，每个i p 核使用不同甚至任意的时钟实现。n o s t r u m 网络采用了自适应反射路由策略和 很小的缓冲避免了拥塞并具有自适应容错能力，采用保留通信资源来提供保证时延的流量 并提供尽最大努力流量。该研究组正在研究n o c 的协议、映射技术、时钟策略。他们研究 4 南京邮电人学坝l ：研究生学位论文第l 章绪论 网络处理器和多媒体应用的n o c 平台。用n o s t r u m 仿真环境n n s e 来配置n o s t r u m 网络 的节点数量、拓扑结构、路由策略、流量模式等进行仿真，仿真结果可以采用不同的图形 方式显示。 ( 2 ) x p i p e s 工程 x p i p e s 是由意大利b o l o g n a 大学和美国s t a n f o r d 大学联合研发的一个可综合的、商性 能的n o c ，通过对路由节点、通信链路和网络接口的配置可以得到任意的拓扑结构，采用 了蠕动交换技术和确定性源路由的静态路由算法。网络接口采用o c p 2 0 ( o p e nc o r e p r o t o c o l2 o ) 协议，支持网络和i p 核不同的时钟。链路可以分级产生流水线。s u n m a p 工具是根据应用需求自动选择最佳拓扑结构，并根据约束条件和i p 核之间的流量模型映射 i p 核到选定的拓扑结构并选路由策略，进行配置x p i p e s c o m p i l e r 工具。x p i p e s c o m p i l e r 工 具自动根据元件库中的元件和输入的拓扑结构、路由策略等实现个定制的n o c ，输出一 个s y s t e m c 的n o c 设计。他们对m e s h 结构的m p e g 4 解码器和定制结构的m p e g 4 解码 器面积和功耗进行了分析比较。 ( 3 ) a s et h e r e a l 工程 a s et h e r e a l 是由荷兰p h i l i p s 公司研发的具有保证服务并提供尽最大努力服务的 n o c 。保证服务满足关键性的流量，尽最大努力服务提供非关键性的通信。a s et h e r e a l 网络使用无竞争的路由策略和流水线时分复用电路交换技术来实现保证服务。尽最大努力 服务使用源路由方式，避免了死锁。使用了由g s 路由器和b e 路由器并行组成的g s b e 路由器，路由节点的交换是可配置的。b e 路由器有较低的优先级，它使用g s 路由器没有 使用的链路或带宽。g s b e 路由器可以采用分布式和集中编程方式进行时隙分配。它用b e 包建立和撤除g s 连接。两种编程模式撤销时隙分配是相同的，仅仅是编程模式不同。a s e t h e r e a l 路由器具有3 2 位6 个双向端口，每端口2 4 字深的输入b e 队列。该n o c 的设 计和验证使用了形式化方法。 ( 4 ) s p i n 工程 s p i n ( s c a l a b l ep r o g r a m m a b l ei n t e g r a t e dn e t w o r k ) 是由法国p i e r r ee tm a r i ec u r i e 大学 研发的通用可扩展s o c 互连微网络。它使用蠕虫交换技术、自适应路由策略、基于信用的 流控机制和胖树拓扑结构。这种拓扑结构产生无阻塞网络交换并且性能不随系统的变化而 变化。通信链路由流控信号、奇偶校验位、错误诊断位和3 2 位数据位组成3 6 位的数据宽 度。他们开发了基于周期精确的c a s s ( c y c l e a c c u r a t es y s t e ms i m u l a t o r ) 模拟器来评估 和比较通信结构。在c a s s 中，用例化元件和定义互连网络的结构化v h d l 文件指定系 统结构。c a s s 模拟模型是通过可综合的v h d l 模型而得到的，因此，模拟模型是周期精 南京邮电人学硕f ：研究生学位论文第l 章绪论 确和位精确的。 ( 5 ) s o c b u s 工程 s o c b u s 是由瑞典l i n k o p i n g s 大学研发的n o c 网络结构，是一个用于硬实时系统的片 内通信网络。典型的应用是无线通信的基带处理和通信基础设施。s o c b u s 采用包连接的 电路( p a c k e tc o n n e c t e dc i r c u i t ) 交换方式。实际上就是利用包交换的方式，让一个数据包 寻找路由，如果成功，则保持所走过的路径，作为电路交换的路径设置。如果不成功，则 可以重发。这个交换方式的优点是没有死锁、不要缓冲器，缺点是数据包的重发会导致时 延和不确定性。s o c b u s 采用二维m e s h 拓扑结构，可以根据应用来增加或删除路由器和 链路来优化网络拓扑结构。用c + + 实现了一个基于事件的高速n o c 模拟器。模拟器的输入 是用x m l 表示的流量和网络模型。 1 4 本文工作 本文借鉴了计算机网络分层交换的设计思想，结合片上网络的特点提出了一种三层片 上网络结构。采用n s 2 作为仿真平台并设计了仿真方案，对其性能进行了分析。分析结果 表明，在同等网络规模下，相比于采用m e s h 拓扑的c l i c h i ! 结构，三层片上网络结构的 平均包时延降低了约1 6 个百分点，吞吐率提升了约3 个百分点，丢包率降低了约9 个百 分点。在高负荷下，三层片上网络结构的吞吐性能提升更为明显。 本文内容安排如下： 第l 章介绍了片上网络的技术发展过程和特点，包括片上网络的提出、片上网络与传 统芯片设计方法以及计算机网络的异同点、片上网络的研究现状等。 第2 章研究了片上网络的关键技术，包括拓扑结构设计、协议设计、流控策略、服务 质量、面积与功耗、片上网络的分层模型。 第3 章首先介绍了一种典型的片上网络单层交换体系结构c l i c h i ! ，然后在分析传统 计算机网络分层交换设计思想的基础之上提h 了一种三层片上网络结构。 第4 章研究了现有的片上网络仿真工具，选择了n s 2 作为本文的仿真平台，并对n s 2 做了简要的介绍，最后介绍了三层片上网络结构以及c l i c h i ! 结构在n s 2 中的建模实现。 第5 章对仿真实验参数做了研究选取，并对三层片上网络结构的性能进行了仿真分析， 研究结果表明，三层片上网络结构的性能特别是时延性能要优于c l i c h i i 结构。 第6 章对本文的主要工作进行了总结，并对该课题的进一步研究方向提出了个人见解。 6 南京邮电人学硕i ：研究生学位论文第2 章片1 ：网络关键技术 第2 章片上网络关键技术 片上网络借鉴了计算机网络的设计思想，将计算机网络技术移植到芯片设计中来，在 单个芯片上构建一个微网络。片上网络与计算机网络相比有很多相同点：都支持包交换、 类似的转发策略、流量控制协议等。但同时，两者也有很多不同的地方：( 1 ) 片上网络多 为二维平面网络，拓扑结构中不允许有交叉连线且规模相对较小；( 2 ) 片上网络是集成芯 片上的网络，其规模要比计算机网络低多个数量级，模块i 、日j 连线短，模块占用面积小，因 此不能部署太大的缓存，同时由于模块间连线短，时延小，所以可以选择较大的分包；( 3 ) 片上网络单个节点的处理能力要比独立计算机弱，没有专门的协议处理机，不适合太复杂 的处理逻辑，对片上网络协议层的简化显得尤为必要；( 4 ) 片上网络对功耗的要求十分严 格，对于性能与功耗的权衡显得十分重要。 片上网络研究涉及到系统级、网络适配级、网络级、链路级1 4 1 等诸多方面。从网络级 角度看，片上网络研究的重点在于拓扑结构、协议设计、流量控制、服务质量等。下面就 将对其中的一些关键技术做一些简要的介绍。 2 1 拓扑结构设计 片上网络的拓扑结构定义了网络内节点与链路的布局和互连方式，拓扑结构的选择对 系统性能和芯片面积具有明显的影响。现有的常见拓扑结构包括s p i n ，m e s h ，2 dt o r u s ， f o l d e dt o r u s ，o c t a g o n ，s p i d e r g o n ，b u t t e r f l yf a t t r e e ( b f t ) - 等【5 】( 如图2 一1 ) 。 r1 二 工，1 | ，试。 _ 醛 l 0一 i - f ? ：| 芦i + ： ：i 手 中 if u 上 手 ”“l 卜t 岜r盈- 扛 越殄 叨蕊 l a lm e s h l b l2 dt o r u s( c lf o l d e dt o r u s e d 】s p i d e r g o n kx k爿 一磁瓤 l e lo c t a g o nm s p i n f g lb i t 图2 i 常见的片上网络拓扑结构 7 南京邮i 乜人学硕j ：研究生学位论文第2 章甩i ：网络关键技术 m e s h 结构简单，布线复杂度低，可扩展性好，链路利用率高，是日自订较为广泛采用的 拓扑结构之一，但是其网络直径和平均距离较大，因此当网络规模扩展后，该结构的功耗 较大。 为了改进m e s h 中的不足，w j d a l l y 和b t o w l e s 提出2 dt o r u s l 2 】结构，该结构通过增 加行和列首尾交换节点的环形链路，缩短了节点l 、b j 的平均距离，大大减小了网络直径，理 论上降低了功耗。但是，这种结构中过长的环形链路可能会产生额外的时延。 为了解决2 dt o r u s 中由于过长环形信道而产生额外时延的问题，w j d a l l y 和c l s e i t z 提出了f o l d e d t o r u s 6 l 结构，该结构通过改变交换节点的连接方式，解决了由于过长的 环形信道产生额外的时延，提高了系统的整体性能。 为了解决总线结构存在可扩展性差的缺陷，k a f i m 等提出o c t a g o n l 7 】结构，该结构中每 个节点有三个邻居节点相连。最大的特点是平均距离短，网络中任何两个节点的通信最多 只需要两跳即可完成。结构中每个节点又可以扩展成一个基本的o c t a g o n 结构并且可以无 限扩大，然而随着结构的不断扩展，连接两个o c t a g o n 结构的交换节点很容易变成通信的 瓶颈，当扩展节点失效时，整个拓扑结构将被分割为失去联系的两部分。 为了降低设计的复杂性和布线的难度，m a r c e l l oc o p p o l a 等提出s p i d e r g o n f s l 结构，该 结构是基于一个双向环形对称的结构，增加了每个节点与其对角邻点的交叉连接。每个交 换节点有四个端口，一个连接i p 核，三个连接邻居交换节点。交换节点i 的邻居节点可以 表示为：( 1 ) 顺时针方向：( i + 1 ) m o dn ；( 2 ) 逆时针方向：( i 1 ) m o dn ；( 3 ) 对角线方 向：( i + n ) m o dn 。该结构的优点是：网络直径较小，链路数量较少，任何两个节点间通 信跳数较少，物理设计复杂度低。 p g u e r r i e r 和a g r e i n e r 提出了一种可扩展的胖树结构s p i n 结构，该结构中树的叶子 节点放置i p 核，非叶子节点均是交换节点。i p 核通信是首先要在父交换节点中查找，如 果父节点查找自己的子节点中没有目的节点，就要向上层查询，增强了系统的本地特性。 但该结构冗余度较高，在芯片上布线复杂度大，需要占用更多的芯片面积。 同s p i n 结构相似，在b f t t 9 l 结构中，i p 核被放置在叶子节点上，而交换节点被放置 在拓扑结构中的非叶子节点上，但在陔结构中交换节点数量和链路数量都大大减少了，从 而减小了芯片的面积，降低了物理设汁的复杂度。 2 2 协议设计 协议设计关心的是片上网络中传送数据的策略，交换方式、转发策略以及路由算法的 8 南京邮电人学硕i ：研究生学位论文第2 章片i ：网络关键技术 选择都是片上网络研究的重点。 ( 1 ) 交换方式 片上网络交换方式主要包括电路交换和包交换两种。 电路交换需要连接的建立与释放，数据沿着相同的路径传输。电路交换模式下，由于 路径确定，消除了路由选择的代价，网络将不会出现拥塞状况。另外由于任何两对结点之 间的通信不互相干扰，也不会出现死锁，因此通信的质量较高。但是电路交换不能适应突 发性流量，链路利用率低。 包交换将数据封装成包，包头中包含了只的地址和顺序信息，根据包头的信息，通过 路由选择策略，逐级将数据包转发到f 1 的地。在每一个中间节点，路由算法指出下一步要 使用的通道，该通道可以从多个可能的通道中选择。如果所有候选通道都忙，包就被阻塞， 不能再前进。有效的路由对互连网络的性能十分关键。路由算法要考虑网络的连通性、自 适应性、死锁和活锁的可能性以及容错等问题。数据包可以通过不同的路径同时传送，提 高了网络的利用率与传输的速度。但是，由于需要数据的封装与重组，增加了网络的开销； 同时，包交换可能会造成拥塞和死锁。目前已经提出了一些在此模式下解决片内网络拥塞 和死锁的办法，将在下文中提到。 在片上网络中，包大小的选择也是很重要的。如果一个消息分成太多的包，在目的节 点进行包重组，会带来很大的处理负担。相反，如果包太大，则需要路由器设置更大的缓 存以容纳待转发的包，同时更长的包长度意味着发送包的时延变得更大，对于一些有着实 时需求的应用会产生不利的影响。 k u e i - c h u n gc h a n g 等人的研究表明：在片上网络系统中，包交换具有灵活，可伸缩， 高吞吐的特点，但其端到端时延较大，能耗水平较高。而电路交换能耗较低，时延也比包 交换方式小，在小规模片上系统中，电路交换方式比起包交换方式更具吸引力1 0 】。 ( 2 ) 转发策略 在片上系统中，比较常用的转发策略有存储转发，虚直通交换和虫洞路由。 存储转发( s t o r e a n d f o r w a r d ) ：节点将存储每一个接收到的数据包，并且只有在一个数 据包己经完整地被接收到之后，才会转发出去。这种方式的网络利用率较低且需要较大的 缓存。c l i c h i 三 11 】采用了存储转发。 虚直通交换( v i r t u a lc u t - t h r o u g h ) 不等待完整的包被接收到，而把数据包分解成为更小 的片( f l i t ) 。只要下一个接收的目的路由拥有接收一个数据包( p a c k e t ) 大小的空闲缓存，并且 线路未被占用，就立刻发送即使未完整到达的数据包。这种办法降低了通讯时延，提高了 网络连接的利用率，但仍然需要为每个包保留一个包大小的缓存。 9 雨尿哪【乜人学颂l ：研究生学位论文第2 章， i ：嘲络关键技术 虫洞路由( w o r m h o l er o u t i n g ) ：它f j 样把数据包分解成为更小的片( f l i t ) ，每个f l i t 像极 小的“蠕虫 一样逐个通过路由，所不同的足只要当接受端路由器拥有可容纳一个f l i t 大 小空闲缓存的时候，该f l i t 就被上一个路由器所发送。因此可以降低网络时延，节省缓存 空问。但是，一旦某个该路由器的发送端被属于同一个数据包的f l i t 所标识并占据，且其 中的f l i t 被阻塞，则由于每个数据包对物理路径的独占性，这样的方式可能会引起死锁的 出现。 ( 3 ) 路由算法 常用的路由算法可以分成确定性和非确定性两种。如果使用确定性的路由算法，那么 源结点和目的结点之间通信发送的所有数据包在网络中的遍历路径足确定的。比较经典的 确定性算法有源路由和x y 路由算法。源路由中，由数据包发出时就已经确定好了要走的 路径。x y 路由中包首先沿着x 方向前进，然后再沿着y 方向到达目的结点。自适应路由 算法采用每跳决定，动态选路机制，可以根据网络的拥塞情况自主选择合理的传输路径， 大大提高了转发效率，但同时其复杂的路由算法需要更为复杂的路由节点来实现。 2 3 流量控制策略 流量控制应包括拥塞避免与死锁避免两个方面。 采用特定的自适应路由算法可以有效避免网络拥塞，这增加了节点执行的复杂性，但 是却带来了动态负载平衡的好处。 当两个包彼此等待路由转发时，由于保留了部分资源并等待对方释放资源，因此产生 死锁。目自订解决死锁的办法有：( 1 ) 虚路径：通过设立多个独立缓存队列的逻辑通道来共 享物理通道，逻辑路径之间相互独立，数据传送不互相影响。通过选择合适的路由策略， 可以消除资源依赖图中环的出现。( 2 ) 有方向性的路由策略：合适的路由策略应避免数据 包在网络中循环运动。比如x y 路由策略，在以x y 坐标安排网络结点时，它优先将数据 沿x 轴发送，直到到达目的路由所在的y 轴，再沿y 方向发送。这样的要求也可以被减 弱，比如只要要求数据包每次发送的方向都保证与目的路由的距离在减少就可以，因为这 样在数据包的传播路径上，最多形成矩形的两条边，而无法形成三条以上的边【1 2 】。 2 4 服务质量 片上网络服务应该具有高吞吐量，低时延，低功耗等特点。服务质量分为：尽最大努 力服务( b e ) 和保证服务( g s ) ，它们提供不同层次的许诺服务，并且对通信行为有潜在的影 1 0 南京邮电人学硕j 二研究生学位论文 第2 章片上网络关键技术 响。保证服务具有可预测性，用于期望服务质量高的业务，例如实时系统。尽最大努力服 务则能提高平均资源利用率。在片上网络的路由决策时，可以提供服务质量，对关键部件 的网络带宽或者时延进行保证，没有被保证的通信采用尽力而为的路由策略。另外，在深 亚微米工艺下，串扰和电压降等问题使得部件之间的连线是不可靠的，可能会造成数据传 输的错误或丢失。为了保证可靠的数据传输，当遇到数据错误时，需要进行重传。片上网 络通过流控机制来保证服务质量。 2 5 面积与功耗 片上网络芯片的面积取决于网络布线以及i p 核的大小，网络布线更多的取决于拓扑结 构而i p 核的大d , n 主要取决于处理核心的复杂度以及缓存的大小。缓存是路由节点的组成 部分，在目前大多数片上网络体系中，缓存占据了路由节点的主要区域，所以在给定性能 需求下怎样降低缓存的大小就成了控制芯片面积不得不关心的问题。y i r a ns u n 等人的研 究表明，单纯提高缓存容量并不能解决拥塞， 吐量并没有改变，相对于功耗和面积的增长， 利用缓存是片上网络研究的关键问题之一。 它最多只是时延了拥塞的发生时间，因为吞 性能的提升是缓慢的f 1 3 1 。所以怎样合理设计 功耗也是片上网络设计关心的重点问题，除了工艺水平的影响外，处理逻辑的复杂程 度、网络拓扑结构规划的合理性、网络负载的平衡性等都会影响到片上网络的功耗水平。 2 6 片上网络的分层模型 传统o s l 分层模型将计算机网络分为七层：应用层、表示层、会话层、传输层、网络 层、数据链路层、物理层。这种分层模型对于计算机网络的实施有着诸多的好处：它使得 人们容易探讨和理解协议的许多细节；提供层问标准化接口，允许不同的产品只提供部分 层次的功能，或是只提供协议功能的一部分；创建更容易集成的环境，提高网络结构的可 重用性；上层无需知道的下层的具体结构，只须利用下层提供的服务，从而减少了网络的 复杂性。然而片上网络不同于传统计算机网络，它是芯片上的网络，网络直径小，各处理 核心的运算能力有限，且受限于面积与功耗，因此不能支持过于复杂的网络协议。 考虑到以上因素，可以将片上网络划分为如图2 2 所示的五层网络模型： 南京邮电大学颀l ：研究生学位论文 第2 章片i ：网络关键技术 o s i7 - l a y e rm o d e l 岁 ；a p p l i c a t i o nl a y e r ip r e s e n t a t i o nl a y e r i i s e s s i o nl a y e r i it r a n s p o r tl a y e r n e t w o r kl a y e r j d a t al i n kl a y e r ；7 p h y s i c a ll a y e r 一， 。t n o c5 - l a y e rm o d e l a p p l i c a t i o nl a y e r t r a n s p o r tl a y e r