（微电子学与固体电子学专业论文）noc通信节点设计技术研究.pdf

摘要 摘要 n o c 通信节点由路由器、网络接口和互连组成。本文基于二维网格拓扑、x y 路由算法、虫洞交换技术和轮循仲裁算法设计了一种含虚拟通道的高效路由器， 可正确选择数据的传输方向，仲裁传输请求，并有效解决网络拥塞问题。在此基 础上，设计了一种低延迟、高吞吐率的网络接口以实现网络与处理单元之间的数 据协议转换。其引入的延迟为4 时钟周期，随机传输下的平均吞吐率达0 7 6 f l i t s c y c l e 。另外由于互连串扰已经成为影响信号完整性及数据带宽的关键问题， 文中也介绍了一种抑制信号抖动的自适应长互连变驱动方法，使信号相对抖动降 为4 5 ，线上传输频率达1g h z 。 经过综合、仿真，证明本文的设计具有正确性、可配置性和高效性，满足片 上网络中的通信需求，并且通过p 复用，可快速、简易地组成具有一定规模的片 上网络架构。 关键词：片上网络路由器网络接口互连 a b s t r a c t a b s t r a c t n o c ，sc o m m u n i c a t i o nn o d ei n c l u d e sr o u t e r ，n e t w o r ki n t e r f a c ea n dl i n k b a s e do n 2 d m e s ht o p o l o g y ，x yr o u t ea l g o r i t h m ，w o r m h o l es w i t c ht e c h n i q u ea n dr o u n d r o b i n a r b i t r a t i o n ，t h i sp a p e rp r e s e n t san e w r o u t e rs t r u c t u r ew h i c hc a l ls e l e c td a t at r a n s m i s s i o n d i r e c t i o n , a r b i t r a t et r a n s r n i s s i o nr e q u e s tc o r r e c t l ya n dd e a lw i t hn e t w o r kc o n g e s t i o n e f f e c t i v e l y f u r t h e r m o r e ，al o w - l a t e n c y ，h i 曲一t h r o u g h p u tn e t w o r k i n t e r f a c ei sd e s i g n e d t op e r f o r md a t ap r o t o c o lc o n v e r s i o nb e t w e e nn e t w o r ka n dp e t h ea v e r a g e1 a t e n c y i n t r o d u c e db yi ti s4c l o c k c y c l e s ，a n dt h et h r o u g h p u ta c h i e v e su pt o0 7 6 f l i t s c y c l ef o ra r a n d o mt r a n s a c t i o n s i n c ee r o s s t a l kb e t w e e nl i n k sh a sb e e no n eo fk e yi s s u e s i n f l u e n c m gs i g n a li n t e g r a l i t ya n dt r a n s m i s s i o nb a n d w i d t h , a l la d a p t i v ed r i v ea p p r o a c h a i m i n gs u p p r e s ss i g n a lj i t t e ro fl o n gl i n k si sa l s op r o p o s e d a sar e s u l t ，r e l a t i v ej i t t e rc a n r e d u c e st o4 5 a n dt r a n s m i s s i o nf r e q u e n c yo nl i n k sr e a c h1g h z s i m u l a t i o na n ds y n t h e s i sr e s u l ts h o wt h a tt h o s ep r o p o s e dm e t h o d sa tes oa v a i l a b l e ， c o n f i g u r a b l e ，e f f e c t i v et h a tt h e yc a ns a t i s f yo n c h i pc o m m u n i c a t i o nr e q u i r e m e n t a n o ca r c h i t e c t u r ec o u l db ef o r m e dr a p i d l ya n ds i m p l yt h r o u g hi pr e u s e k e y w o r d s ：n e t w o r k - o n c h i p r o u t e rn e t w o r k - i n t e r f a c e l i n k 西安电子科技大学 学位论文创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：豸蚴旦日期呈2 主： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 日期旦丕主：笪 銎 名 名 签 签 人 师 本 导 第一章绪论 1 1 1s o c 架构设计遇到的困难 第一章绪论 1 1 研究背景 片上系统( s o c ) 是目前较为成熟的集成电路设计方法，其设计思路是从整个系 统性能出发，在单个芯片上完成整个系统的功能。在人类不断追求更快、更多、更 小的愿景和努力下，伴随着科技水平的飞速发展以及芯片的不断小型化、复杂化， s o c 已经成为具有上亿门电路、几个c m 2 量级面积、几十个g b i t s s 数据通量规模 u 】的电路系统。伴随着工艺技术的进步、特征尺寸的减小、设计技术的提高，片上 系统规模进一步增大。这种趋势导致片上p 数量的迅速增加，需要更高的数据带 宽来满足系统要求，而金属线宽和间距的减小，不仅带来线上寄生电阻的增加， 同时导致线间耦合电容的增大，严重限制了总线带宽，并带来功耗的急剧增加， 基于总线的s o c 架构的主要问题表现在： 1 全局同步问题 当工艺特征尺寸在o 1 8 p a n 以下、工作频率达到几个g h z 时，时钟信号的布 线成为最为棘手的问题【2 】。首先，不断翻转的时钟信号会影响周围信号的传输，其 本身也会由于这种串扰产生信号延迟和时钟的不确定性，进而造成时钟偏差( c l o c k s k e w ) 和时钟抖动( c l o c kj i t t e r ) ，并由此限制时钟频率的提升。虽然采用时钟树 ( c l o c kt r e e ) 优化的方法可以改善这一影响，但同步时钟网络所产生的动态功耗始 终难以接受，甚至可占据芯片总功耗的4 0 以上【3 】。因此，设计由单一系统时钟控 制的全局同步电路变得困难重重。 2 传统的总线结构问题 随着电路规模增大、数据处理量增长，传统总线结构可扩展性差的问题日益 突出，同时连接几十上百个功能模块( 或嵌入式处理器) 根本无法实现，而且其 一般采用分时复用策略，因此连线资源利用率低，并行处理能力弱【4 1 。 深亚微米集成电路中，互连线寄生电容成为主要的负载形式，制约着集成电 路在功耗、工作频率及信号完整性等多方面的表现【5 】。随着特征尺寸的进一步减小 和集成电路规模的进一步增大，互连线宽度及间距相应减小，线间耦合电容则相 应增大，并在数字信号间产生动态串扰，影响信号完整性及传输正确性，导致额 外的延迟。随着工作频率的提高，这种影响会更加严重，极易导致电路发生时序 违背现象。如果传播时钟信号，同步通信就会变得不可行，于是回到第一个挑战。 2 一 n o c 通信节点设计技术研究 1 1 2n o c 架构的特点和优势 面对s o c 架构出现的上述设计障碍，人们借鉴计算机网络通信的思想，提出 片上网络( n e t w o r ko nc h i p ) 的概念来满足日益增长的数据带宽需求。主要地，n o c 使用基于包( p a c k e t ) 传输的网络通信代替s o c 中的传统总线通信，通过网络协议与 计算协议的转换组成具有计算、通信功能的完整系统。其次，n o c 同样可方便地 使用口复用技术完成系统的扩展和高效的设计，最后，使用全局异步局部同步 ( g l o b a l l ya s y n c h r o n o u sl o c a l l ys y n c h r o n o u s g a l s ) 技术，既能保证p 间的高速通 信，又不失设计的一般性、复用性。 相应s o c 面临的困难，n o c 具有如下优势【6 】： 1 具有良好的地址空间可扩展性，理论上可集成的p 数目不受限制；而s o c 受地址总线位宽的限制，具有最大通信带宽； 2 提供良好的并行通信能力，从而提高数据吞吐率及整体性能：而s o c 过低 的总线使用率成为其性能提升的障碍； 3 使用全局异步局部同步( g a l s ) 通信机制，每一个p 节点都工作在自己的时 钟域，而不同的节点之间则通过网络进行异步通信，很好地解决了总线结构的单 一时钟同步问题，从而彻底解决了庞大的时钟树所带来的功耗和面积问题。 1 2 国内外n o c 研究状况和发展趋势 1 - 2 1 国外研究状况 由于n o c 具有的独特优势以及巨大潜力，自从1 9 9 9 年左右几个研究小组提出 这种架构后，越来越多的研究机构和公司企业投入到这个领域的研究中。推动着 这项新技术发展的重要国外单位有美国斯坦福大学、普林斯顿大学、k t h 以及法 国p i e r r ee tm a r i ec u r i e 大学等等。专门的国际年会有：自2 0 0 1 年开始，每年一度 的“i n t e m a t i o n a lf o r u mo na p p l i c a t i o n - s p e c i f i cm u l t i p r o c e s s o rs o c ”以及0 7 年开 始的”i n t e r n a t i o n ms y m p o s i u mo nn e t w o r k s o n c h i p ”。生产出产品样片的有：m m 、 东芝、索尼三家公司联合开发的“c e l lp r o c e s s o r ”( 包含1 个6 4 位控制处理器和8 个通用处理器) ，s a n d b r i d g e 公司的“s b 3 0 0 0 ( 包含1 个a r m 核和4 个d s p 核) 等。以下是一些所选取具有代表性的近几年国外研究动态： _ 0 3 年法国的a r t e r i s 公司推出业界第一款用于构建n o c 系统的一整套 库及相应设计仿真的e d a 工具，并且开始商业运作，随后被众多i c 设计 公司( 比如t i ，p i x e l w o r k 等) 所使用【7 1 。 0 4 年美国的n i l a n j a nb a i l 鲥e e 等人对n o c 架构进行分析，并对功耗、性 第一章绪论 能建模1 8 】； 一0 5 年加拿大p a r t h ap r a t i mp a n d e 等人研究n o c 各项性能评定指标( 如吞 吐量、延迟、功耗和面积) 的权衡性设计，进行仿真验证的横向对比【9 1 ； 一0 6 年韩国k a n g m i nl e e 等人提出众多行之有效的n o c 低功耗、g a l s 技 术，并成功地把采用这些技术的n o c 设计进行流片【1 0 】； 一0 7 年n o c 进入6 5 n m 时代】；印度s a n t a n uk u n d u 等人详细论述了n o c 中用以异步通信的g a l s 技术1 2 】：美国u m i ty 等人提出时钟隔离岛的概 念来进行异步设计【”】； - 0 8 年i n t e l 公司成功研制出使用n o c 技术的集成有8 0 核的芯片，成为第 一块性能超过1 0t e r af l o p s 的芯片【1 4 】。 1 2 2 国内研究状况 相对于国外研究的快速发展，毫不掩饰地说，国内在这个领域的研究力度以 及研究成果明显逊色。目前国内的研究单位主要有合肥工业大学、哈尔滨工业大 学、西北工业大学、西安电子科技大学等。其中合肥工业大学开展较早，有多位 在读博士、硕士致力于此领域的研究，并发表了多篇高质量论文。 从上节可见，国外在此领域已发展至整体架构的设计、优化，并且有成熟芯 片面世；而国内研究的特点大多还停留在片面技术的研究，以下为所选取的一些 研究成果与研究热点： 0 6 年合肥工业大学高明伦等首先发表n o c 论文 6 1 ：( n o c ：下一代集成电 路主流设计技术。西北工业大学周国昌等通过横向对比几种n o c 中时钟 树结构【l5 1 ，提出了一种有效解决n o c 中时钟问题的技术方案； 0 7 年中国科学院王军等提出一种n o c 中b u f f e r 的读写电路以减少数据读 写功耗【1 6 1 ；西安电子科技大学张恒龙等人归纳总结n o c 所采用的拓扑结 构【1 7 1 ，为选择最合适的拓扑结构提供了理论依据；武汉大学朱小虎【1 8 】等 人提出一种多级拥塞控制的路由算法，更好地折中了网络延迟与吞吐量； 0 8 年清华大学林世俊等人f 1 9 】设计了一种g a l s 通信的网路接口，具有高 速、低延迟的特点；西安电子科技大学何世超等【2 0 】提出测试交换结构间互 连线串扰的b i s t 的方法，电子科技大学武畅等【2 1 】提出一种l o t t e r y 的仲 裁算法，可提高路由节点的处理能力。 小结：n o c 是一个新兴研究领域，并且正处于高速发展阶段。我国在这各领域 的研究已经落后大概有3 5 年的时间，现在正是一个刻不容缓的时刻。但是只要科 技决策层敏锐地觉察出这是一个跟上国际发展水平的难得机遇，果断地支持n o c 相关技术的理论研究工作，一定能够追赶上国际研究的前沿。从这个层面看，n o c 4 一 n o c 通信节点设计技术研究 的出现无疑为中国集成电路设计方法学的继续发展又提供了一次很好的机遇。我 国若能够全面开展n o c 学术领域的前沿工作，将会出现大量的创新成果。 1 3 本文工作的目标与内容 1 3 1 本文工作的目标与内容 从上述发展趋势来看，n o c 势必成为下一代集成电路的主流技术。为适应国 际i c 设计技术的潮流，在此领域寻求创新点，本人为项目主要实施人参与了课题 组立项的n o c 研究与实现。为了搭建起整个n o c 架构并对其进行整体性研究， 本文的研究目标是n o c 主要组件二一通信节点的研究与设计，组成完整的通信框 架，并解决一系列相关问题，为后续工作的深入开展打下基础。 本文的主要工作是在阅读大量相关国内外文献的基础上，了解n o c 的结构、 功能，掌握其中拓扑结构、网络协议、q 嗵s 技术、仲裁器、存储器、性能评价等 技术要点，并对通信节点的各关键子模块( 路由器、网络接口和互连) 进行创新 性设计，使用相关e d a 工具仿真、验证其正确性、有效性，最后撰写论文。 首先，研究路由器功能结构，并设计一种使用异步f i f o 的异步通信方法，结 合仲裁器、交叉网络、路由控制器等模块组成一个具有完整功能的路由器；其次， 为实现网络与p 间穿越网络的的数据通信，成功设计一种具有低延迟、高吞吐率 特点的网络接口模块；最后，针对n o c 中长互连线，本文提出一种自适应驱动能 力的方法，减小相邻线间的耦合串扰，以减小传输信号抖动，提升线上传输频率。 上述三个部件的复用加上处理单元可以组成一定规模的片上网络架构。 1 3 2 章节安排 第一章分析本文的研究背景和意义。讨论在n o c 的技术背景、国内外研究现 状、本文的研究方向、n o c 技术的必要性；最后是本文研究的意义和章节安排。 第二章主要是n o c 系统架构的综述。阐述了n o c 的定义、协议、组成结构 和关键技术等。 第三至五章主要是分别对路由器、网络接口和互连的设计与验证工作。详细 阐述了工作的理论依据、创新性和实现策略，并给出必要的仿真验证结果。 第六章对本文的总结和展望。 第二章n o c 技术要点 第二章n o c 技术要点 2 1n o c 体系结构概述 n o c 是在一块芯片上构建的网络系统。它集成多个具有特定功能的s o c 或p 模块，以及从物理底层到应用顶层的完整通信网络。也可以定义为在单一芯片上 实现的基于网络通信的多处理器系统。 n o c 包括资源和通信两类节点：资源节点完成广义的计算任务，典型的资源 节点可以是带缓存的嵌入式微处理器和d s p 核、专用硬件资源、可重构硬件资源， 或者是上述各种硬件的组合以及一些特定的总线架构，本文中统称为处理单元 ( p e ) ；通信节点( 又称交换开关，s w i t c h ) 负责资源节点之间的数据通信，主要包 括路由器( r o u t e r ) 、网络接口( n e t w o r ki n t e r f a c e ) 和互连( l i n k ) 。通信节点借鉴了分布 式计算机系统的通信方式，用路由和分组交换技术替代传统的总线技术完成通信 任务。典型的二维网格型n o c 结构如图2 1 所示： 核 络接口 图2 1 二维网格型n o c 结构示意图 网络接口和路由器是片上网络的两个关键组件，网络中一切通信事务皆由它 们实现。片上网络中数据传输的过程可大致分为5 个阶段： ( 1 ) 源节点中的d 核通过局部总线以同步方式将需要发送的消息数据写入网 络接口： ( 2 ) 源节点的网络接1 ：3 将待发送的消息数据组成数据包( p a c k e t ) ，再将数据 包分解为微片( f l i t ) 以异步方式送入片上网络； ( 3 ) 片上网络路由器将数据包转发到目标节点； ( 4 ) 目标节点中网络接口从接收到的数据包中提取有效数据，进行消息重组； 6 一 n o c 通信节点设计技术研究 ( 5 ) 目标节点中的p 核通过局部总线读取接收到的消息数据。 在以上数据传输过程，我们采用了基于数据包的交换方式和g a l s 系统架构， 并且引入了计算机网络所采用的虚拟通道技术和路由算法以优化片上网络模型的 性能。 下文将首先简要介绍片上网络相关技术要点和组成，在此基础上介绍基于数 据包的交换方式、路由算法和g a l s 系统架构，最后叙述片上网络中关键模块的 设计实现方法。 2 2 拓扑结构 拓扑结构【1 7 】体现了n o c 中的通信节点是如何在芯片中分布和连接的。n o c 拓扑 结构的选择对系统性能和芯片面积具有明显的影响，拓扑结构的衡量标准通常是 以理论上影响路由成本和性能为基础的。良好的拓扑结构必须考虑以下因素： ( 1 ) 资源节点与通信节点之间或者通信节点之间的通信带有明显的“本地相 邻”特征： ( 2 ) n o c 中资源节点的物理尺寸与通信节点的物理尺寸相互影响； ( 3 ) n o c 中使用物理连线作为通信信道，因此节点之间的连接不能太复杂，且 要具有可扩展性。 2 2 1 几种常见的拓扑结构 ( 1 ) 二维网格( 2 d m e s h ) 结构： 2 0 0 2 年，s k u m a r 等人提出此结构。如图2 2 所示，该结构中每个非边缘通信 节点有五个端口，其中，四个连接相邻通信节点，一个连接资源节点。每个边缘 通信节点有三个端口，其中两个连接相邻通信节点，一个连接资源节点。因此， 这个拓扑结构中的通信节点和资源节点在数量上相同。该结构简单，易于实施， 可扩展性好，是目前较为广泛采用的拓扑结构之一。但是该结构网络直径和平均 距离较大，因此当网络规模扩展后，功耗较大。 第二章n o c 技术要点 图2 2 二维网格结构 ( 2 ) 二维环状( 2 d t o m s ) 结构： 2 0 0 1 年，w j d a l l y 和b t o w l e s 在网格结构的基础上，提出增加行和列首尾通 信节点的环形链路的环形结构。如图2 3 ，该结构缩短了节点间的平均距离，大大 减小了网络直径，从理论上降低了功耗。然而，这种结构中过长的环形链路可能 会产生额外的延迟。 日 月 卢 ，_ u l 嘧 - -_ 飘一 尸 ，尸月 i f 曩 尸， - 户 l ilul - ， 卢，户 l l 图2 3 二维环状结构 ( 3 ) 八角形( o c t a g o n ) 结构： 为了解决s o c 系统中总线结构存在可扩展性差的缺陷，2 0 0 2 年，k a r i m 等提 出o c t a g o n 结构，如图所示。结构中每个结点又可以扩展成一个基本的o c t a g o n 结 构并且可无限扩展。但该结构很明显会增加布线的复杂性，而且随着结构的不断 扩展，连接两个o c t a g o n 结构的交换结点很容易变成通信的瓶颈。 欠l i v v i k 永 x 。 v 塔v 够 图2 4o c t a g o n 结构及其扩展结构 ( 4 ) s p i n 结构： 2 0 0 0 年，p g u e r r i e r 和a g r e i n e r 提出了一种可扩展的胖树结构s p i n 结构，如 图所示，它用来把每个p 核互连在一起。该结构中树的叶子结点放置p 核，非叶子 结点均是交换结点，每个父结点在树的每层都被复制四次，这样虽然增加了冗余度， 但是提高了整体性能，实现了可扩展性。但该结构较复杂，在芯片上布线复杂度 大，增加了芯片的面积。 n o c 通信节点设计技术研究 口 图25s p i n 结构 ( 5 ) s p i d e m e t 结构： 2 0 0 8 年，温东新等人【2 2 1 提出了介于m 髂h 和1 研u s 的一种中间结构s p i d e m e t 。 如图26 ，其是以一个正1 1 边形为中心向外扩展的结构，相邻多边形上的对应点成网 状互连，如图。这种结构有很好的扩展性，并且在平均最短路径和可平面化方面 具有优势。 凹凹日。口1 l 研可d 口i l l 可可百 口i l 叫盯叮叫 囝26 四节点的s p i d e m e t 拓扑结构厦物理布局 ( 6 ) s t o r u s 结构： 2 0 0 8 年，朱晓静瞄i 提出了一种类似楼梯( s t a i r s ) 的、和t o r u s 拓扑相似的结构一 s t o m s ，如下所示。该结构和同等规模的t o r u s 相比二者互连数相同，但对于各 种负载模式，s t o r u s 的平均延时比t o n t s 约d 、2 0 - 1 5 0 ，当使用热点负载作为测试 数据时，s t o r u s 的饱和吞吐量约为t o r u s 结构的12 - 15 倍。 图27s t o m s 结构 7 ) 三维拓扑： 2 0 0 7 年日：苯h i m k im a t s u t a n i 等人【“惺出三维拓扑的架构。充分利用芯片间 第二章n o ( 3 技术要点 ( i n t e r - w a f e r ) 互连的低延迟、高密度，使用特殊的交叉网络连接不同层间的处理单 元，并提出相应的3 d 路由算法。如图这种架构在性能、面积、功耗上都超出二维 结构，但很明显地，设计复杂度增加，而且需要扩展、完善路由算法。 2 2 2 拓扑结构的比较 图2 8 三维拓扑结构 根据上述的各种拓扑结构，表2 1 列出了其各种性能参数，首先给出以下定义， 各种拓扑结构间的比较从以下着手f 1 7 】瞄】。 定义1 ：节点度( n o d e & g l e e ) 一路由器节点与其他路由器节点相连接的所有 边的度数。每一条边都为双向边，包含输入和输出，节点度为2 。节点度大的节点 有更多的选择路径的机会。但同时增加了片上的面积开销，网络复杂度随之增加。 定义2 ：连通度( c o n n e c t i v i t y ) ：使网络不连通所需要去掉的最少路由器节点数 目。网络的连通度越大，网络结构越复杂，网络的容错能力越强。 定义3 ：两节点之间最小距离：网络中实现两节点之间通信的最短路径所需的 跳数。 定义4 ：网络直径( n e t w o r kd i a m e t e r ) = 任意两p 核节点之间最小距离的最大值。 网络直径与网络的通信延迟成线性正比关系。 定义5 ：平均最短路径( a v e r a g em o s ts h o r t - c i r c u i tp a t h ) ：网络中任意两p 核节点 之间的最小距离和与其所包含的路径数之比。平均最短路径能反映片上网络互连 的特征。 定义6 ：平均布线长度( a v e r a g ew i r el 髓g t h ) ：网络拓扑结构映射到片上网格后 的实际平均最短路径布线长度，单位为l ，即每一格的边长度为l 。 表2 1 给出了各拓扑结构的性能参数。 1 0 n o c 通信节点设计技术研究 表2 1 节点数为k 2 的拓扑结构属性( 3 d 拓扑为k 3 ) 节点度连通度 网络直径平均最短路径 平均最小布线长度 m e s h 822 k 2 2 ( k 2 1 )2 ( k 2 1 ) 3 k 3 k 8 4kk t o m sk 1 2 84kk s t o r mk 1 2 k 2 8 o c t a g o n 61 。| |1 4 2 s p 矾k 2 k 2k 2 1k | 28 坚一1 7 k1 s p i d e r n e t 83 5 k 2 3 k 一2 21 23 6 6 k 2 ( k 2 1 )2 ( k 2 1 ) 3 d 1 23 2 k 2 3 k3 k ， 2 2 3 定制拓扑 上述的几个拓扑例子都属于规则拓扑，它们具有规则的网络参数和可复用性， 降低了设计时间和成本，适用于通用的对称同构系统，适合连接同类处理单元。 与规则拓扑不同，定制拓扑一般是不规则的结构，可以面向不同的领域，根据特 定的应用需求定制。拓扑的选择取决于系统功能的要求，还有整合模块的尺寸和 布局要求。一般地，s o c 整合技术都潜在地包含不同的技术和专用部件( 设计者 需要优化系统的功耗问题等) ，这些部件有各自的功能、尺寸和通信需求。这就 需要一个用户自定义的、面向专用的不规则拓扑。 以一个m p e g 4 解码器的执行过程为例i z 5 1 。首先，嵌入式存储单元( s d r a m ) 比其他核大的多，也是通信的瓶颈。模块的尺寸高度的不统一，平面布局也不像 m e s h 中的处理单元那样有规律性；第二，整个嵌入式s d r a m 的带宽比其他核间的 大得多：第三，很多相邻模块不需要通信。即使能在同构结构上运行m p e g 4 ，也 需要冒很大的风险，因为这可能使得许多的单元和连接不能被利用到，或者是另 一个极限局部的阻塞而导致了性能的降低。这些因素促进了片上专用网络的 应用。 意大利博洛尼亚大学和美国斯坦福大学联合推出n o c 组件库p i p e s 【2 6 1 ，其 第二章n o c 技术要点 包括参数化的n i ，r o u t e r , l i n k 的等基本组件，可借助x p i p e s c o m p i l e r 等工具方面进 行非规则拓扑、定匍 n o c 设计，达到性能的最优化。清华大学马立伟【2 7 】等人在确 定n o c 设计流程的基础上，根据其通信特征，选择了合适的离散平面结构，对n o c 的运算及控制等模块进行布局、对模块间的通信依赖关系进行布线，发展出f r o d 算法，以自动生成片上网络的拓扑结构，可在面积、延迟、功耗方面有较大的优 化效果。 可见，n o c 拓扑分为规则拓扑和非规则拓扑两大阵营，两者各有优缺点。规则 拓扑可以借鉴并行计算机领域的研究成果，具有良好的可复用性、可扩展性，可 以降低设计时间和成本，但是只适用于通用和同构的体系结构。由于规则拓扑具 有良好的网络参数，在n o c 领域已经取得了广泛的应用。现有的大量研究都是围绕 规则拓扑开展的，特别是适合二维平面布局的网格类拓扑。非规则拓扑可以为具 体的应用定制，节省了芯片的功耗和面积，但是设计效率较低。由于嵌入式系统 资源受限，具有专用性，多处理器s o c 中含有通用c p u 、协处理器、d s p 等多种类 的异构处理单元，非规则拓扑更适合作为其互连网络拓扑，将会是未来n o c 拓扑的 研究重点。随着s o c 中处理器数目的不断增加，层次结构拓扑也将是下一步的研究 热点。分层网络可以兼顾规则拓扑和非规则拓扑的优点，是大规模n o c 拓扑的必然 发展方向。 2 3 片上网络中的数据结构 一般地，把处理单元产生的数据叫做信息( m e s s a g e ) ，而在n o c 系统中，数据包 ( p a c k e t ) 是处理单元间相互通信的基本元素，其大小根据需求来设置，可以设为几个 字节，也可设定为一块内存区域所包含的信息。n o c 通信时，一个时钟周期内所交换 的信息单元称为数据微片( f l i t ) ，由于其操作的原子性，就定义了网络中两个处理节点 之间的最大带宽。通常，一个数据包由多个数据微片组成，当进行一个完整的信息交 换时，从处理器层来看，是简单的传送接受一个数据包，从原子操作角度看，网络节点 间进行了多次的数据微片交换。它们之间的关系如图2 9 所示。 一个包主要由包头( h e a d e r ) 和包负载( p a y l o a d ) 组成。包头包含必要的路由信 息和网络控制信息，在x y 路由中，一个包头一般包含如图所示的路由信息1 2 8 】。 其中操作地址指读写数据所访问的地址( 一般为存储器读写地址) ；源地址、目的 地址分别指起始、目的处理单元在网络中的位置坐标；操作类型指示读写操作的 种类；包尺寸表示一个完整信息被分成的包的数目；标志位包括像一些表示信息 结束的位等等。数据部分组成负载，接在包头之后，组成完整的包。包负载为所 要传输的数据或者控制信息，其中f l i t 的数目由其大小决定。 1 2 n o c 通信节点设计技术研究 图2 9 网络中传输的数据结构 2 4 基于包的交换技术 在任何系统中，信息从源地址到目的地址的传输都需要一系列的规则和方法， 这些规则和方法就称为协议。当直接相连的两个单元之间通信时，通过请求和应 答实现硬件握手就是一种简单的通信协议。通信协议决定了资源如何被连接到网 络中去，并且还决定了资源的通信方式。每一个资源都有唯一的地址，可以通过 开关连接到网络中，它们通过( 网络接口) 与开关进行通信。 包交换技术关注的是数据包是怎样从输入通道交换到输出通道的。采用的包 交换技术不同，所产生的延迟就不同，网络的延迟与包交换技术直接相关。交换 技术主要有三种：存储转发( 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 ) 和虫洞【2 9 】( w o r m h o l e ) 路由。存储转发模式是当节点将一个数据包完整接收之后， 再将这个数据包进行转发。可以看出，存储转发模式造成的数据传输延迟比较大， 并且需要大量的缓存开销。虚拟直通路由是当节点可以保证能够在数据包接收完 整时，立即将该数据包进行转发。因此虚拟直通路由的数据传输延迟要小于保存 转发模式。 虫洞路由实际上是虚拟直通路由的一种优化改进。它将数据包分为若干个基 本单位微片- - f l i t ( 流控制单元) ，头微片包含路由寻址信息。节点接收到数据 包的头微片后译码，然后开始对该数据包进行路由，而头微片后面的有效负载微 片遵循头微片的传输通道进行数据传送。这就使节点需要的缓存开销大为降低， 并且大大提高了数据的传输效率，从而降低了数据的传输延迟。从上面的描述可 以看出，虚拟直通方式和虫洞路由方式是很相似的。事实上，在没有阻塞的情况 下，虚拟直通和虫洞路由是完全样的。它们两者的差别在于发生阻塞时对被阻 第二章n o c 技术要点 塞的数据包的处理：虚拟直通将整个的数据包储存在发生阻塞的路由器中；而虫 洞路由是将各个片段分散到各个节点中。 由上面的分析可见虫洞路由的优点： 敏感。数据包的传输延迟由两部分组成， ( 1 ) 相对的使网络延迟对路径长度不那么 部分是发送数据包的时间，另一部分 是在各个节点寻径时间的总和。在实际应用中，一般数据包的长度比较大，远远 大于各个节点寻径时间的总和，所以延迟主要由前一部分决定。这个优点很好的 适应了n o c 可升级性( s c a l a b l e ) 的要求。( 2 ) 虫洞路由只需要很少的路由器缓存。 这一点也很好地迎合了n o c 的特点。 但同时虫洞路由也有其不可避免的弊病：( 1 ) 只要一条通道开始传送包的第一 个片段，它就被这条数据包所占用了，必须等到传完所有片段才能被释放，继而 被其它消息使用。也就是说，一个包发生阻塞时，可能会同时阻塞其他多个数据 包，进一步的造成网络拥塞。( 2 ) 当死锁发生时，很难将发送来的消息集合在缓存 中以晚点再传送。因为，虫洞路由的消息长度没有限制，而且缓存通常很小。 2 5 路由算法 n o c 的拓扑结构必须保证每个节点可以发送数据包到其他任意节点。当从源 节点到目的节点的路径有很多条时，需要路由算法决定其中一条路径( 可能这条 路径不是最优的) 。有效的路由算法对n o c 网络性能的好坏是至关重要的。路由算 法要考虑网络的连通性、自适应性、死锁和活锁的可能性以及容错等问题。 与传统的计算机网络相比，片上网络受芯片面积和功耗的限制，不能使用太 多缓存，同时片上网络中的路由节点较少，所以一些传统的路由方法并不适用于 片上网络。对于片上网络路由算法的研究是片上网络研究领域中的一个重要分支， 主要方法是通过评估现有用于并行计算机集群的路由算法，加以优化、裁减。评 估和优化的过程中除了考虑路由算法的连通性、自适应性、死锁和活锁发生率、 容错能力等基本性能外，更加关注路由算法在时间开销、硬件实现的复杂度以及 资源开销方面的情况。在我们给出的片上网络模型中，将直接采用一种确定性路 由算法，作为片上网络路由单元的设计基础。在设计方案中路由算法的实现只与 路由计算单元相关，且该单元被封装成一个独立的模块，可以根据需要进行路由 算法的替换，不影响其它模块的现有结构。 所谓确定性路由算法是通过计算目的地址与源地址的差值建立路径，在任意 两个网络节点之间，每次路径选择是相同的( 确定的路径) 。我们将要在路由计算 单元中实现的是确定性路由算法中较为简单的一种，称为x y 路由算法【3 们。规则二 维网络拓扑结构可以被分解为两个正交的维x y ，通过比较两个坐标地址可以 得到当前节点和目标节点之间的距离。x y 路由算法，首先从x 轴开始计算路由方 1 4 n o c 通信节点设计技术研究 向，在每一个节点都比较当前、目的节点的坐标地址。在二者的x 坐标相等时，开 始沿y 轴传播：比较y 坐标，当y 坐标也相等时，说明数据包已经抵达目标节点， 路由过程结束。以下为路由算法的具体流程： 算法：规则二维网格拓扑结构中采用的x y 路由算法 输入：当前节点的坐标( x c u r r e n t ，y c u r r e n t ) 和目标节点坐标( x d e s t ，y d e s t ) 输出：选中的输出通道e h a n n e l 过程： i f ( x d e s t x e u r r e n t ) c h a n n e l = x + ； e l s ei f ( x d e s t y c u r r e n t ) c h a n n e l - - y + ； e l s ei f ( y d e s t 1 ) b i n ； 正确产生空满标志是整个f i f o 设计的最关键部分p 6 1 ，这部分的好坏直接影 响着整个f i f o 的性能。对满信号置位表示f i f o 已经处于满状态，不能再执行写 入操作；对满信号复位表示f i f o 非满，还可以执行写入操作；对空信号置位表示 f i f o 处于空状态，这时没有有效数据可以读出；对空信号复位说明f i f o 非空， 这时可以进行读操作。当读指针和写指针相等时，f i f o 可能处于满状态或空状态。 可以用不同的方法判断f i f o 究竟处于什么样的状态，也就是说究竟是写指针 从后面追上了读指针还是读指针从后面追上了写指针。本文所采用的方法是分别 将读写地址寄存器扩展一位，将最高位设置为状态位，其余低位作为地址位，指 针由状态位和地址位组成。首先把读、写状态位全部复位，然后利用状态位和地 n o c 通信节点设计技术研究 址位的结合实现对空、满标志的控制。当读写指针的状态位和地址位全部吻合的 时候，读写指针经历了相同次数的循环移动，也就是说，f i f o 处于空状态；如果 读写指针的地址位相同而状态位相反，写指针比读指针多循环一次，表明f i f o 处 于满状态。在二进制编码的情形下，可以使用下面的方式来判断空满状态： e m p t y = ( w r _ p t r a d d r _ w i d t h ：o = 刊- p t r a a a r _ w i d t h ：o ) f u l l = ( w r _ _ p t r a d d r _ w i d t h 一1 ：o 】司p t r a d d r _ w i d t h - 1 ：o 】 & & w r _ p t r i a d d r _ w i d t h 刮p t r a d d r _ w i d t h ) 必须注意的是，r dp 仃和、) l ，rp 仃是在两个不同的时钟域产生的信号，所以在进 行比较之前必须进行同步以避免亚稳态的出现。本文的设计就采用下图表示的两 级同步电路，电路形式简单，且技术非常成熟，采用它解决亚稳态问题时，同步 错误发生的概率是可计算的，即亚稳态发生概率已知。以写指针同步到读时钟域 为例，见图2 1 3 ： 图2 1 3 读指针同步化电路示例 由于对异步f i f o 的研究，我的师兄已经做出了较深入的工作，这里不再详述 1 3 7 】。其他文献中还提及了一些q 地s 实现方案，比如无时钟方法( c l o c k l e s s ) 【3 8 】，半 同步方法( m e s o c h r o n o u s ) 3 9 1 ，源同步方法( s o u r c e s y n c h r o n o u s ) 4 0 】等等。这些方法具 有可行性，但在设计的通用性、难易程度和移植性上不太理想，这里略叙。 2 8 性能评价指标 为了对比、评价不同的n o c 架构，必须制定一系列的性能评价指标f 9 】。例如我 们可以看到这样的描述：l l t n o c 架构具有低延迟、高吞吐率、较低的功耗和面积开 销。在当今的功耗约束环境下，鉴别最高效节能的架构和量化性能与功耗间的折 中显得越来越重要了。一般来说，所添加的口核所占的面积开销应该尽可能的小。 下面详细介绍这些评价指标。 2 8 1 信息吞吐率 一般地，用带宽c o i t s s e c ) 来衡量一个数字通信网络的性能。但是在n o c 体系中 我们更加关心的是网络中信息交换的比率。因此吞吐率是更合适的评价指标。不 第二章n o c 技术要点 1 9 同的实现方式，吞吐率的表示方法也不同。这里使用公式( 2 1 ) 定义： t h r o u g h p frate=(totalm e s s a g e scompleted)x(messagel e n g t h ) ( 2 1 ) 一(numbero fb l o c k s ) ( t o t a lt i m e ) 、 其中t o t a lm e s s a g e sc o m p l e t e d 表示成功达到目的处理单元的整个信息的数量； m e s s a g sl e n g t h 表示其中数据微片的数目；n u m b e ro f b l o c k s 表示通信中所涉及的p 块的数目；t o t a lt i m e 是在第一个信息产生到最后一个信息被接收之间的时间( 时 钟周期数) 。因此，信息吞吐率就被表示为网络中可以实际处理的最大负载的分数 形式。如果吞吐率等于1 ，则对应着每个时钟周期、每个节点都收到一个f l i t 。因此， 吞吐率的单位为：f l i t s c y c l e i p 吞吐率意味着可接受通信量的最大值，并且和系统 可承受的峰值数据传输量有关。 2 8 2 传输延迟 传输延迟定义为从源节点一个包头注入