（计算机应用技术专业论文）片上网络平台架构的研究.pdf

蹲京邮电大学硕士研究生学位论文摘要 摘要 随着集成电路设计和制造技术的不断进步，芯片的集成度和复杂度也以惊人的速度发展。 在2 0 世纪9 0 年代中期开发出s o c ( s y s t e m o nc h i p 片上系统) ，标志着集成电路开始向集成系 统转变。总线结构是s o c 的主要特征，总线由于可以提供高性能的互连而被广泛运用。但未来 的s o c 设计对系统的可扩展性和可靠性要求越来越高，而传统的总线结构将不再适应系统发展 的需要，因此2 0 0 0 年左右几个研究小组提出了一种全新的集成电路体系结构n o c ( n e t w o r k s o n c h i p 片上网络 ，其核心思想是将计算机网络技术移植到芯片设计当中，南于n o c 具有良好 的空阆可扩展性，提供了并行通信能力，以分组交换作为基本遥信技术，采用全局异步一局 部同步的通信方式，因而能从体系结构上彻底解决总线架构带来的问题。 n o c 作为一种新的体系结构，需要有新的设计方法学与之相适应，进行n o c 系统的设计。 本文在介绍了n o c 多种拓扑结构特点的前提下，对n o c 的设计方法和设计流程做了描述，并总 结了n o c 发展的一些关键技术；n o c 与计算机网络一样，也需要进行流量控制，才能避免网络 拥塞，提高系统性能，文中根据n o c 路由器的特点，建立了适f f n o c 的预测性流控模型；最震， 对n o c 的路由机制进行了深入分析，将“奇偶”转折模型应用予路径分配中，对已有的n o c 静态 路由提出了改进。 关键词：n o c 拓扑结构流量控制“奇偶”转折模型最短路径算法 麓京邮电大学竣士研究生学位论文a b s t r a c t a b s t r a c t w i t lt h ed e v e l o p m e n to fl cd e s i g n i n ga n dm a n u f a c t u r i n gt e c h n o l o g y ，t h ec h i p sd e n s i t ya n d c o m p l e x i t ya l s or i s e s 、柝mt h ea s t o n i s h e dr a t e 1 1 1 ea p p e a r a n c eo fs o cl a b e l st h et r a n s f o r m a t i o n f r o mi n t e g r a t e dc i r c u i t 稻i n t e g r a t e ds y s t e m 。b u s e sa n dp o i n tt op o i n tc o n n e c t i o n sw e r et h em a i n m e a n st oc o n n e c tt h ec o m p o n e n t s b u s e sa r ea t t r a c t i v eb e c a u s et h e yp r o v i d eh i 曲p e r f o r m a n c e i n t e r c o n n e c t i o n sw h i l et h e yc a ns t i l lb es h a r e db ys e v e r a lc o m m u n i c m i o np a r t n e r s h e n c et h e yc a n b eu s e dv e r yc o s te f f i c i e n t l y 、i l et h ef u t u r es o cd e s i g nr e q u i r e st h es y s t e mb em o r es c a l a b l ea n d r e l i a b l e ，s ot h et r a d i t i o n a lb u s e sa r c h i t e c t u r ec a n tm e e tt h er e q u i r e m e n to fs y s t e md e v e l o p m e n t n o ca r c h i t e c t u r e sa l eb e l i e v e dt ob et h ei d e a ls o l u t i o nt om a n yo ft o d a y ss o ci n t e r c o n n e c t i o n p r o b l e m s o n c h i pn e t w o r ka r c h i t e c t u r e sm a ya d o p td e s i g nc o n c e p t sa n dm e t h o d o l o g i e sf r o m c o m p u t e rn e t w o r k s ，n a m e l yf r o ms y s t e m a r e a - n e t w o r k sa n dp a r a l l e lc o m p u t e rc l u s t e r s 弧en e wa r c h i t e c t u r en e e d san e wm e t h o d o l o g yt os u p p o r tt h es y s t e md e s i g n ，习l i sp a p e r a n a l y s e ss o m ec o m m o nt o p o l o g i e s o fn o c ，t h e ni l l u m i n a t e st h ed e s i g nf l o wo fn o ca n d s u m m a r i z e st h ek e yt e c h n o l o g i e sf o rn o c a c c o r d i n gt ot h ec h a r a c t e r i s t i co fm u t e ri nn o c ，w e c o n s t r u c tam o d e lt oc o n t r o lf l o w a tl a s t ，w ea n a l y z et h em u t i n gs t r a t e g yi nd e t a i l s ，a n da p p l yt h e o d d e v e n t u mm o d e lt ot h es h o r t e s tp a t ha l g o r i t h m ，f o r man e wd e t e r m i n i s t i cm u t i n ga l g o r i t h m f o r n o c k e y w o r d s ：n o c ，t o p o l o g ya r c h i t e c t u r e ，f l o wc o n t r o l ， o d d - e v e n t u r nm o d e l ，s h o r t e s tp a t h a l g o r i t h m i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：；岛日期z 盟刖， 7 一r 一 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：扭导师签名：必叠日期邋：叫 南京邮电大学硕士研究生学位论文第一章绪论 1 1s o c 技术的发展 1 1 1 集成电路进入s o c 时代 第一章绪论 2 0 世纪9 0 年代中期，随着半导体工艺技术的发展，i c 设计者能够将越来越复杂的功能集 成到单硅片上，s o c 正是在集成电路向集成系统转变的大方向下产生的。由于s o c 可以充分利 用已有的设计积累，显著的提高a s i c 的设计能力，因此发展非常迅速。 s o c 通常指在单一芯片上实现的数字计算系统，一般包括两个基本部分：硬件部分和软件 部分。硬件部分包括p r o c e s s o r 、b u s 、r o m r a m 、f op o r t 等计算机系统的基本部件；软件 部分主要包括操作系统和重要的应用软件。1 9 9 4 年m o t o r o l a 公司发布的f l e xc o r e 雕系统 和1 9 9 5 年l s il o g i c 公司为s o n y 公司设计的s o c ，是基于i p 核完成s o c 设计的最早报道。当前无 论在国外还是圉内，在s o c 设计领域已经展开激烈的竞争。按指令集来划分，s o c 主要分x 8 6 系列、a r m 系列、m i p s 系列和类指令系统等几类，每一类都各有千秋。国内研制开发者主要 基于盾两者，如中科院计算所中科s o c ( 基于龙芯核，兼容m i p s i i i 指令集) 、北大众志( 定义 少许特殊指令) 、方舟2 号( 自定义指令集) 等。开发拥有自主知识产权的处理器核、核, l , i p 和片上总线，将使国内s o c 发展具有更强的竞争力，从而带动国内i c 产业的发展。 1 1 。2s o c 主要研究内容 片上总线技术 总线结构【4 0 】及互连技术，直接影n l 匈s o c 芯片总体性能的发挥。片上总线技术包括两个方面， 一是制定( 选用) 标准，二是设计实现。表1 1 总结了基前国际国内现有的片上总线。 总线机构 c o r e c o n n e c t 1 1 3 i m a d v a n c e dm i c r o c o n t r o l l e rb u sa r c h i t e c t u r ea r m w i s h b o n e o p e n c o r e s 南京邮电大学硕士研究生学位论文第一章绪论 s i l i c o n b a c k p l a n ei i i s o n i c s p i b u s ( p e r i p h e r a li n t e r c o n n e c tb u s )o p e nm i c r o p r o c e s s o rs y s t e m si n i t i a t i v e o c p ( o p e nc o r ep r o t o c 0 1 ) o p e nc o r ep r o t o c o li n t e r n a t i o n a l i pi n t e r f a c e m o t o r o l a i p bu s i n t e g r a t e dd e v i c et e c h n o l o g y ( i d t ) f i s p b u sm e n t o rg r a p h i c s c o r e f r a m e p a l m c h i pc o r p o r a t i o n c i e a r c o n n e c t c l e a r s p e e dt e c h n o l o g y c 木b u s 苏州园芯 表1 1 国际囡内现有片上总线总结 每一种片上总线都是在满足特定应用领域的条件下发展起来的，各有优势，但是也具有 共同的特点网： ( 1 ) 采用主从式结构，并且都支持多个主单元，由总线仲裁器根据优先权原则将总线控制权赋 予相应的主单元。特别是w i s h b o n e 总线的交叉开关互连方式，这是把透信领域的技术用于片 上总线的一个范例，也是片上总线较传统计算机总线的最大优点之一。 ( 2 ) 总线应尽可能简单，占用的逻辑资源少。首先总线的时序本身要简单，便予使用者学习和 接受，这样i p 核的设计者就可以把主要精力集中于i p 本身功能的设计；其次由于片上总线集成 于一块芯片内，因此它不能占用太多资源。 ( 3 ) 为了降低功耗，各种信号一般都尽可能保持不变，并且多采用单向信号线，这样也利于结 构的简化以及时钟的同步。基本上，这些总线都把输入数据线和输出数据线分开，并且都没 有信号线复用的现象。 ( 4 ) 在批量数据传输时一般都采用流水线方式，露当前的地址与上一次的数据交叠在一起，从 而实现一个时钟周期传送一次数据。这样就可以实现一个时钟周期完成一次数据传输。 ( 5 ) 支持可变宽度的地址和数据线。一般的片上总线都至少支持6 4 位的数据宽度( a m b a 最多 支持1 0 2 4 位数据宽度) ，并且这些地址和数据线的宽度都是可以改变的，这无疑增加了片上总 线的应用范围。传统的计算机总线给人的第一印象就是该总线是并行的还是串行的，如采是 并行的又是多少位的等等。片上总线改变了人们的思维方式它的数据宽度是可配置的。 i p 重用技术 在强大的商监压力下，设计公司想要大幅度提高s o c 的设计效率，就必须尽可能多地使用 南京邮电大学硕士研究生学位论文 第一章绪论 现有的电路模块，甚至从其他公司那里获得所需要的i p 核。然后再将这些合适的i p 核通过某 种方式“拼装成符合一定功能需求的s o c 。这就是i p 重用技术。 i p 是集成电路知识产权模块的简称。这里将其定义为：经过预先设计、预先验证、具有 相对独立的功能、可以重复使用在s o c 和复杂a s i c 中的电路模块。在工业界，其又常被称为s i p ( s i i i c o ni p ) 。 通常按照其在设计流程中的位置，i p 可以分为三种：软i p 核、固i p 核和硬i p 核。软i p 核 ( s o f ti p ) 是用可综合硬件描述语言( h a r d w a r ed e s c r i p t i o nl a n g u a g e ，h d l ) 描述的电路功能 块。硬i p 核( h a r di p ) 是经过布局布线并针对某一特定工艺库优化过的版图。通常是g d s i i - s t r e a m 的文件形式。固i p 核( f i r mi p ) 是已经基于工艺库进行了综合，通常以网表的形式提交 客户使用。固i p 核提供了介于软i p 核和硬i p 核之间的一个折中方案，比硬i p 核具有更好的灵 活性和可移植性，比软i p 核又在性能和面积上有更好的可预知性。 建立在i p 重用技术基础上的s o c 设计使设计方法从电路设计转向系统设计，设计重心将从 今天的逻辑综合、布局布线后模拟转向系统级模拟、软硬件联合验证，以及若干个i p 组合在 一起的物理设计。i p 重用技术迫使设计业向两极分化，一是转向系统，利用i p 设计高性能高 复杂度的专用系统。另一方面是设计深亚微米下的i p 核， 步入物理层设计，使i p 核的性能更 好并可预测。 软硬件协同设计技术 早期的软硬件协同设计技术3 2 3 9 1 是针对一个特定的硬件如何进行软件开发或根据一个已 有的软件实现具体的硬件结构。早期的这种技术缺少统一的软硬件表示方法，软硬件划分只 凭经验定义，不能够验证整个系统。通过h w s w 边界时很难发现不兼容问题，缺少成熟的设 计流程。在s o c 设计中，软硬件的划分要从系统的角度将软硬件完成的功能作均衡，以需要达 到的目标为设计标准，在系统的复杂度一定时，使软硬件结合达到更高的性能。软硬件划分 好以后，软件和硬件的设计一直是保持并行的，在设计过程中两者交织在一起，互相支持， 互相提供开发的平台。 面向s o c 的软硬件协同设计理论应该是从一个给定的系统任务描述着手，目前广泛采用的 硬件描述语言基本不具备系统描述功能，如何能有效的描述系统级功能就是一个非常重要的 课题。软硬件协同设计所涉及到的内容有：h w s w 协同设计流程、h w s w 划分、h w s w 并行综合、h w s w 并行验证。2 0 世纪9 0 年代中后期开始出现商业性的协同设计e d a 软件， 南京邮电大学硕士研究生学位论文 第一章绪论 软硬件协同设计也逐渐在业界获得越来越广泛的应用。软硬件协同设计软件主要有两大类， 一类是基于模型的，这类软件通常都有一个可扩充的模型库，里面有微处理器、总线、存储 器、各种编解码器以及软件驱动、实时操作系统的模型，用户也可以用h d l 语言、c 语言或者 专用的语言编写自定义的软硬件模块；另一类是面向综合的，这类软件试图把软硬件设计和 验证整合到一个统一的设计流程中。通过使用同一种语言来描述软件和硬件，用户可以构建 一个从系统设计、r t l 设计和门级设计的统一设计验证环境。 软硬件协同设计作为s o c 的支持技术，还在不断的发展和完善中，研究开发软硬件协同设 计平台，是这一技术逐渐走向成熟的标志。 s o c 验证技术 在s o c 的研发周期中，验证工作的重要性( 验证工作量约占整个设计工作量的7 0 9 6 ) 近年来 已经得到了广泛的论述。此外，最近的调查显示，在流片前仍未检测出的功能故障仍是造成 重新流片的主要原因。其问题在于，验证技术的发展未能跟上i p 重用设计技术的广泛使用， 以及设计规模和复杂程度不断增加的步伐，从而导致两者之间出现了明显的差距。 建立在单点工具( p o i n tt o o l s ) 上的验证方法是造成验证差距的主要原因。这些验证方 法都旨在解决某一个特定的验证问题，如验证平台自动化、断言和模型检验等。当用户追求 横跨验证流程最佳工具组合时，通常不得不自行尝试将这些工具整合起来建立一个完整的流 程，要达到这一要求必须投入相当多的时间和精力。然而，这种做法会导致验证方法之间的 严重脱节。芯片设计失误的统计数据表明，验证技术的发展的确未能跟上芯片规模和复杂度 的增长。另外，验证方法的落后也成为i p 核重用的障碍。解决这一问题的有效途径是采用统 一的验证方法，应用经过改进的工具平台和充分利用具有丰富语义的标准语言。 a r m 和s y n o p s y s 联手开发基于覆盖率分析的s o c 验证的统一方法，这种验证方法面向功能 验证的各方面，包括可用于形式分析和动态验证的可验证性设计技术( s y s t e mv e r i l o g a s s e r t i o n s ) ；使用有约束条件的随机激励生成技术( s t i m u l u sg e n e r a t i o nt e c h n i q u e s ) ；使用覆盖 率统计的分析方法来实现快速的验证收敛。这项方法还将帮助验证用i p ( 专用于验证的i p ) 供应 商采用一致的验证架构，从而便于最终用户将不同来源的验证用i p 有效地整合起来。 4 南京邮电大学硕士研究生学位论文 第一章绪论 1 2 从s o c 到n o c 的过渡 1 2 1n o c 技术的产生背景 ( 1 ) 现有设计方法学遇到了巨大的挑战 集成电路设计效率的增长率总是滞后于芯片集成度的增长率，造成了芯片集成度和设计 效率之间著名的“剪刀差 ，并且它们之间的差距还在继续增大，如图1 1 所示。重用设计方 法学是缩短“剪刀差”的有效途径，各个层次的电路功能模块的重用有效的弥补了设计效率的 差距。但是随着电路规模成指数增长，现有重用单元的电路规模依然不够大，缩短“剪刀差 仍然是个问题，集成电路设计方法学的发展史，就是一个不断扩大重用单元规模的过程，前 一个阶段的“产品”将成为下一个阶段的重用单元( 晶体管一门级电路一i p 模块专s o c 平台) 。 n o c 提供了支持高效率可重用设计方法学的体系结构：现有规模的s o c 完全可以作为n o c 的资 源节点参与重用设计，其重用效率无疑将大大提高。 图1 1 集成电路设计发展规律图 另一方面，现有的s o c 设计方法的核一t l , 内容是以嵌入式微处理器为核心，基于片上总线集 成i p 核，最终设计出目标芯片。这种以微处理器为核心的设计方法将随着微处理器数量的增 多而遇到困难。不难想象，当片上集成上百个处理器时，仅仅是众多微处理器之间的协同验 证就变得极其困难，而n o c 通过通信节点连接资源节点，每个资源节点只要符合片上通信协 议即可，就像因特网对p c 本身的要求十分宽松一样。在集成多个微处理器单元时，以通信协 议为核心的n o c 设计方法所特有的高设计效率将发挥巨大的优势，为缩短“剪刀差 提供了 s 南京邮电大学硕士研究生学位论文第一章绪论 一个解决方案。 ( 2 ) 现有芯片体系结构的瓶颈 单一时钟同步问题 随着工艺特征尺寸越来越小，工作频率迅速上升，达到1 0 g h z 以后，连线延时造成的影 响将严重到很难展开设计工作的程度。全局连线上信号的传播需要好几个时钟周期，时钟错 位( c l o c ks k e w ) 也变得很难精确控制，而且时钟网络的功耗将占据芯片总功耗的大部分。由单 一系统时钟同步全芯片的工作将极其困难。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 ) 的通信机制：每一个资源节点都工 作在自己的时钟域，而不同的资源节点之间则通过通信节点进行异步通信，从而很好的解决 了问题。 传统的总线结构问题 随着电路规模越来越大，片上集成的单元越来越多，数据处理量也越来越大，传统的总 线方式可扩展性差的问题就越来越突出，同时连接成百上千个功能模块( 或嵌入式处理器) 则完 全无法实现。而且传统总线结构资源利用率较低，不能提供很好的并行处理能力。尤其是在 纳米特征尺寸阶段，物理上的原因( 如多种噪声源的引入、功耗增大以及多种物理参数的不 可预知性等) 使全局连线( 即总线) 遇到了无法逾越的瓶颈。n o c 片上通信技术不仅具有良 好的可扩展性，还提供了很好的并行处理能力，能够分解深亚微米时代所产生的一系列问题， 势必将成为替代总线通信方式的一种理想的解决方案。 从上面的分析看，随着半导体工艺特征尺寸的不断减小，在电路规模不断扩大的渠道下 以及新的物理效应和设计剪刀差的压力下，芯片基础架构及其设计方法学的全新变革是必定 要发生的。另外，电子信息技术的高速发展要求未来的电子系统具备快速解决日益复杂的检 测、计算、通信以及讯号处理的能力：相应的，系统将要求未来的芯片提供并行计算和实时 处理多任务的能力，n o c 的基础架构正好具备了这种特点，符合电子设备发展的潮流。 因而，2 0 0 0 年左右几个研究小组提出的一种全新的集成电路体系结构n o c ( n e t w o r ko i l c h i p ) t 2 1 ，其核心思想就是将计算机网络技术移植到芯片设计当中，并借鉴并行计算技术的特 点，协调系统内不同组件协同工作，从体系结构上彻底解决总线架构带来的问题。s o c 的发展 使得未来系统的复杂性和集成度都越来越高，需要将数十个甚至上百个处理单元和存储单元 集成在一块硅片上，还需要支持组件复用以及“即插即用 【h 等特性，随着5 0 1 0 0 纳米技术的 发展，采用通信模块和网络协议的n o c 设计方法学就成了研究的重点。值得注意的是，n o c 6 南京邮电大学硕士研究生学位论文第一章绪论 技术虽然移植了计算机网络中的关键技术，但是，由于通信媒介存在着根本差异以及纳米级 工艺条件下芯片设计的特定需求，使得n o c 在以下几个方面与传统计算机网络之间存在着明 显的不刚3 4 j ： 连线资源远较计算机网络丰富 流量分布函数的差别( 传统计算机网络的流量服从泊松分布) 资源节点的异类性( n o c 中的计算节点的功能可以从单一功能的l p 到整个s o c ) 显著的低功耗需求( 纳米级工艺条件下任何芯片都无法回避的最重要的问题之一) 。 自s o c 诞生以来，集成电路设计技术进入到追随p c 的阶段( 如s o c 就相当于p c ，而i p 重用 设计方法学则借鉴了p c 插件板的“即插即用”概念) 。现在p c 正快速朝向基于网络的n c ( n e t w o r kc o m p u t e r ) 发展，可以预见，以分组转发机制和网络通信协议为核心的n o c 体系结 构必将成为未来v l s i 设计技术的主流。 1 2 2n o c 研究动态 n o c 是一个崭新的话题，在国际上才起步不久，随着技术的不断发展，越来越多的研究 机构意识至u n o c 的潜力，纷纷投入到其中并推动着它的发展，这使得n o c 成为一个非常活跃的 学术前沿领域。据初步统计，国际上共有3 0 多所大学、研究所及研究单位正在积极从事n o c 的研究工作【1 0 】。其中影响较大的有瑞典皇家技术学院、斯坦福大学和荷兰菲利普研究实验室 等。参与研究的国家还有法国、意大利、芬兰、希腊、以色列、巴西、印度等。2 0 0 0 年3 月， 法国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 c a l a b l e ，p r o g r a m m a b e l ，i n t e g r a t e dn e t w o r k ，s p i n t l 】) ，并将并行计算技术中分组交换的方法引 入芯片设计中，以实现数据交换【3 】。2 0 0 0 年1 1 月，瑞典皇家技术学院等单位提出 n e t w o r ko na c h i p ”概念，将n o c 定义为在一块芯片上实现的，通过交换开关相互连接的处理资源、存储资 源、i o 资源的总体。每个处理单元拥有各自地址，通过发送和接收带有地址信息的数据包来 和其他单元进行通信。2 0 0 1 年，瑞典皇家技术学院和芬兰v t t 大学联合启动 n e t w o r k o n c h i p a r c h i t e c t u r en o c a r c ”计划，研究n o c 的基础架构。2 0 0 1 年1 0 月，意大利博洛尼亚大学的l u c a b e n i n i 与斯坦福大学的g i o v a n n id em i c h e l i 开始研究5 0 纳米n10 0 纳米下的s o c s o c 互连技术， 他们提出“n o c 是s o c 的新范例”的论断，并论证了将计算机网络的层次化协议结构移植到芯 片中的可行性。2 0 0 1 年6 月，斯坦福大学的w j d a l l y 提出使用片上互连网络通过数据包通信的 7 南京邮电大学硕士研究生学位论文 第一章绪论 方式替代各式各样的连线结构的设想，将研究重点放在了对n o c 通信方式的研究上。下表总 结了目前国际上对于n o c 的研究状况。 时间事件主要内容 2 0 0 1 9 第2 7 届欧洲固体电路会 a j a n t s c h 做了n o c 概述”报告，l r z h e n g 议的研讨分会“s y s t e mo n做了“n o c 中的物理问题”报告，m f o r s e i l c h i p ，s y s t e mi np a c k a g e 做了 n o c ”体系结构的报告，j ps o i n i n e n 召开 做了“一种n o c 设计方法学”的报告 2 0 0 2 1 0 “n e t w o r k o n - c h i p ”国际讨论t n o c 的概念与范畴、设计方法学及 研讨会在日本京都召开设计空间探索等问题 2 0 0 2 1 l“e x s i t e ”学术研讨会在 汇报了n o c 通信平台体系结构的研究进展 芬兰首都赫尔辛基召开 2 0 0 3 2 n e t w o r k so r lc h i p ) ) 一书 内容包括n o c 的基本理论与设计方法学、 由k l u w e r 学术出版社出基础架构、软硬件接口等问题 版 2 0 0 3 5 瑞典皇家技术学院的研该年的专题以 n e t w o r k so nc h i p ) ) 一书的 究生课程 s o c 专题的内容为蓝本开设1 2 个子主题讲座 2 0 0 3 专题是 n e t w o r k so n c h i p 2 0 0 3 8 斯坦福大学与博洛尼亚研究n o c 的综合流程：拓扑结构映射、拓 大学的联合计划扑结构选择和拓扑结构生成 “n e t c h i p ”启动 2 0 0 4 2 e l s e v i e rs c i e n c e 的 内容包括i p 互连、n o c 数据打包与路由交 j o u r n a lo fs y s t e m s 换、n o c 通信协议的服务质量以及n o c 设计 a r c h i t e c t u r e ) ) 发表n o c ” 探索的结构建模等 专题 2 0 0 4 8( ( i n t e r c o n n e c t c e n t r i c内容包括总线结构作为n o c 的基本单元、 d e s i g nf o ra d v a n c e ds o c多处理器仿真系统的基于网络的建模等 a n dn o c ) ) 一书由k i u w e r 学术出版社出版 2 0 0 5 2 i e e et r a n s a c t i o n so n 包括设计方法学、拓扑结构、前沿技术、 p a r a l l e la n dd i s t r i b u t e d 相关算法、嵌入式系统、专用电路或i p 的 s y s t e m 将组织一个 n o c 、应用程序接口、电源功率、可靠性 “o n - c h i pn e t w o r k s ”专题 与可重构以及“o n - c h i pn e t w o r k s ”的电路 时序问题 1 2 3n o c 基础理论体系 表1 2 国际n o c 研究动态 经过了4 年多的发展，n o c 技术的领域框架已经基本成形。n o c 技术领域包括体系结构、纳 米设计技术、e d a 实现理论与工具等几个主要方面m 3 。 n o c 体系结构研究n o c 的基本软硬件结构，是当前n o c 领域的研究重点。其中“片上 互连结构”研究n o c 的基础通信架构( b a c k b o n e ) ；“拓扑结构研究n o c 通信系统的拓扑框 架：“通信协议”着眼于基础架构中的高效通信；“n o c 软件 侧重于操作系统：“n o c 基 8 南京邮电大学硕士研究生学位论文第一章绪论 础元件库 相当于s o c 时代的l p 库，库元件既包括s o c 、i p 等传统元件，也包括链接通道( 1 i n k ) 、 接口、路由器、电开关等n o c 时代的特有元件；“系统集成和验证技术”研究如何在上述基础 上设计n o c 芯片。 “纳米设计技术 涵盖了纳米工艺条件下芯片设计与实现的各种关键技术，如低功耗设计 技术、可制造性设计技术( d e s i g nf o rm a n u f a c t u r e ，d f m ) 、傣号完整性设计技术等。纳米设计 技术是所有纳米芯片的共同课题，不是n o c 领域所特有的。但是，由于n o c 技术的战略地位， 纳米设计技术的各种难题将集中体现在n o c 的所有设计环节中。 “e d a 实现理论与工具”指的是n o c 自动化设计过程中的各种工具及其算法研究，是产业 阶段所需要的研究工 擘，如通信建模工具( 并行通信模型建模、应用特征图建模等) 、综合工 具( 拓扑结构综合、资源映射优化等) 、仿真工具( 如系统级仿真) 等。 1 3 论文的主要研究内容 本文对新兴的片上网络做了探索性的分析和研究工作，论文的主要工作和取得的成果如 下： ( 1 ) 对n o c 的理论基础进行了研究，分析了n o c 的体系结构、拓扑结构、设计流程、设计方法 以及实现n o c 的关键技术等。 ( 2 ) 根据n o c 中的资源通信状况和路由器的结构特点，建立了具有预测性的n o c 流量控制的数 学模型。 ( 3 ) 分析并实现了基于“奇偶”转折模型的免死锁路由算法，通过对n o c 网络通信的分析，综合 “奇偶”转折模型和最短路径算法的优点，提擞了一种耨的混合算法，确保在免死锁的前 提下分配代价最小的路径，使系统的执行代价最小。 1 4 论文的组织结构 第一章：引言。主要介绍了论文的背景，研究该课题的意义，目前国际上的研究现状，论文 的主要研究内容和组织结构等。 第二章：n o c 的结构及设计。介绍并分析了n o c 的节点结构及常用的拓扑结构，阐述了n o c 的 网络层次模型，设计流程和实现l n o c 的关键技术。 第三章：n o c 的流量控制。根据资源通信状况和路由器结构，建立了资源通信状况模型和路 9 南京邮电大学硕士研究生学位论文第一章绪论 由器模型，在此基础上形成了具有可预测性的流量控制模型。 第四章：n o c 的路由机制。介绍了虫孔路由、免死锁等概念，分析了转折模型和“奇偶”转折模 型，并实现了基于“奇偶”转折模型的最小自适应路由算法。通过对n o c 网络通信的分 析，对文献1 3 5 】中提出的n o c 静态路径分配方法进行了改进，综合“奇偶”转折模型和 最短路径算法的优点，提出了一种新的混合算法，确保在免死锁的前提下分配代价 最小的路径，使系统的执行代价最小。 第五章：总结与未来工作。主要对全文进行了总结，并提出了未来的研究工作。 l o 第帝n o c * 构投设计 2 1n o c 结构 211n 0 0 节点结构 第二章n o c 结构及设计 n o c 竹点之间的通信可以通过消息传递( m e s s a g ep a s s i n g ) 和共享内存( m e m o r ys h a r i n g ) 两种方式来实现。在消息传递方式巾，节点之间传输数据需要显式响用a p i s ，例如s e n d ( ) 和 r e c e i v e ( ) 。这些a p i 命令的实现，需要相应的协议米支持，凶此产生了额外的传输消耗，可能 降低系统效率；相比较而吉，菸享内存万一j 需璺刘存储器进行存取操作，不需要额外的传 输消耗，闻此，煎享内存的通信方式被广泛应川于如今的高性能多处理器系统r 】。个典型 的n o c 结构h 1 如图2 】所示。它通过卟片e 互联网络米连接多个资源符点，每个节点有其 独立的c p u 和缓存结构，当从绒缓存l lz 【1 没有读耿到数j l l 时，会进入二级缓存l 2 ，如果 一级缓存中也没有所需数札，则会进行存储器的读操作，从存储器中读墩数据，当l 1 和l 2 进行数据更新时，两者都叫以采取写通或写l 叫的方式。 c n - c h i pi n t e r c o n n e c t n e t w o r k 图2 - ln o c 节点结构 每个节点之间通道共享内存相互联系在物理上所有节点统编址，并通过存储器目录可 对存储器进行访问。当从l 2 不能读取到所需数搬时，l 2 通过片上删络发送请求以表明要进 行存储器读操作，当存储所需数据的存储器接受到请求后，将发送应答给请求节点，应答中 南京邮电大学硕士研究生学位论文 第二章n o c 结构及设计 包含所请求的数据。当进行缓存的写通或写回操作时，需要更新的缓存内容将被封装在一个 数据包内，发送到相应的存储器所在的位置，完成更新。 在使用共享内存方式的n o c 中，保持缓存一致性是一个关键问题，因为一个数据可能有 多份拷贝在不同的节点缓存中，当存储器中的数据更新时，相应节点中的这些陈旧数据都需 要被更新，通常有两种方法解决这种一致性问题：1 ) 缓存更新法即当存储器内的数据更新 时，更新所有在缓存中的相应拷贝；2 ) 缓存无效法将缓存中相应的数据标记为无效，当下 一次读取这些数据时，将会产生一个读取存储器的请求，从而会从存储器中取到更新后的数 据。 2 1 2n o c 拓扑结构 由于不同的性能需求和成本要求，很多n o c 网络拓扑结构是为特别应用量身定做的。n o c 中的节点分为资源节点和通信节点，资源节点负责对数据的处理，通信节点负责对数据流的 仲裁和路由转发，通信节点既可以被集成在资源节点内部，也可以在外部实现，可以根据不 同需求进行不同的物理实现。 蜂窝结构 在蜂窝结构中，资源节点和通信节点的比例为3 ，一个资源节点与三个资源节点和三个通 信节点相连，一个通信节点与6 个资源节点和6 个通信节点相连，相比其他拓扑结构，其连 线资源比较紧张。 网格( m e s h ) 和花环( t o r u s ) 结构 在网格和花环的网络中，节点相互连接成一个k 行维的m e s h 型阵列( k a r yn - m e s h ) ， 或是k 行维的t o r u s 型阵列( k a r yn c u b e ) 。这种结构连接简单，也便于在数据传输时进行路 由选择，因此被广泛应用在并行处理系统中【引。m e s h 和t o r u s 结构具有高度的规则性，每两个 节点之间的连线长度都相一致，从而在任意两个邻接节点间进行数据传输时，所消耗的能量 基本一致，保证片上网络整体性能的均衡性。 1 2 自j ，：邮电火学rj = 究学位论上= 口n o c 镕构垃计 吲2 - 2 n e 曲和t e r u s 结构 c u b e - c o n n e c t e d c y c l e s 结构 相比较于l 叫格和花环结构，c u b e - c o n n e c t e d c y c l e s ( c c c ) 结构有效的减少了每个节点的 度数，即每个节点所莲接的边的数目。在c c c 结构中，何个节点的度数部是3 ，而在m e s h 或 l o r “s 结构中，每个节点的度数为2 ”( n 为维数) 。c c c 结构自鲜明的层次性，每个角的3 个 节点组成个局部环，每个环又。q 以与相邻的环连接，从而形成网络结构。 八角形结构 八角形结构足将八个节点组成一个局部纠、，并j 咀过3 条直径连接这八个节点，从环内的 仟一仃点出发最多经过两跳，即u r 到达环内任意节点。枷果将环中的个节点作为桥节点， 可将多个环相连接，构成网络结构。 ( a ) c u b e c o m l e c t k y e l e sc o ) o c t a g o n 圈2 - 3c c c 和八角形结构 蝶劂( b u t t e r f l y ) 结构 在蝶网结构吼p ，资源k 2 _ 1 通过外置的通信节点相连接，每两个资源节点问有一条固 定的路径n l 任意两节点问通信所产生的延时柏同，延时的k 短由转发节点的级数所决定。 凰一骊一蓊一 南京m 电 学顺l 。q f 宄生学位论土 钟一章n o c 结构且设h 碟m 结构有多种周构结构，例如b a n y a n 和b a t c h e r - b a n y a n 网络，b a n y a n 网络中有n - - 2 “个 入口和n = 2 ”个出口，n 就足l 哪络的维数。在总甚n 数结构中，其转垃节点数为三1 。g 。 由于结构类似，因而他们的物理如局也极其相似。 胖树型结构 与蝶网结构不同，在胖树型结构中，m 个资源节点川可有多条路径，它可以有多个根节 点，节点之间的通信延时取决于树的深度。 2 2n o c 层次模型 图2 - 4 蝴蝶和树，弘结构 在分组交换m 络中，通信协议定义了资源节点如何连接到网络上以及信息如何从源节点 传输到目的地。分组交换网络通信协议比总线协议更为复杂，通常为多个层次定义协议层 次的结构通常称为协| 义组。在刊算机喇络研究领域，通常使用7 层o s i 协议模型，而且将其作 为研究不同通信协议组时的参考。绝大多数n o c 研究者都提出了类似于o s i 协议模型的层次化 协议组，比如l b e n l n j 和g d m i c h e l i 等人提出的微网络协议组( m i c m - n e t w o r kp r o t o c o ls t a c k ) ， 如图2 5 所示，r 血将分别介绍微网络协议组的各层挑议。 霾一固 ，o，日i 到器器岛器 蓁 南京邮电大学硕士研究生学位论文 第二章n o c 结构及设计 图2 5 微网络协议组 ( 1 ) 物理层( p h y s i c a ll a y e r ) 定义连接资源节点和通信节点的连线数目和长度、电压级别、信号时序等。全局连线是 n o c 中信道( c o m m u n i c a t i o nc h a n n e l ) 的物理实现，物理层的设计应该在提供一个令人满意 的品质和为其他协议层提供一个清晰的、完整的信道属性的抽象之间达到平衡。 ( 2 ) 数据链路层( d a t a 1 i n kl a y e r ) 定义资源节点和通信节点以及两个通信节点之间的传输协议，保证物理连接之间可靠的 信息传输。数据链路层的功能就是将信息的每一个字准确的没有误差的从一个节点传输到相 邻的节点上。由于两个相邻的节点可能以异步传输模式工作，依次除了需要考虑数据的出错 检测与纠错之外，数据链路层还须注意硬件同步问题。此外，数据链路曾也实现数据编码和 为更好的控制功耗。 物理层和数据链路层均与工艺有关，也就是说，如果采用新工艺，必须重新定义这两个 c j 力譬o ( 3 ) 网络层( n e t w o r kl a y e r ) 定义一个数据