（计算机应用技术专业论文）片上网络通信调度仿真系统的研究与实现.pdf

at h e s i si nc o m p u t e r a p p l i c a t i o nt e c h o n o l o g y ft ! l s ! l ! i ip f r f l l l l r r l liu i l l i j i r l ! l l l l f 丫18 4 0 7 0 3 s t u d ya n di m p l e m e n t a t i o no fa s i m u l a t i o n s y s t e m f o rc o m m u n i c a t i o n s c h e d u l i n go n n e t w o r k so nc h i p s b y y u a nl i n g s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rd e n gq i n g x u n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 p 、 1l l ， ， 独创性声明 -本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 - 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 i ；6 二 恧。 学位论文作者签名：玺岭 e l期：妒移7 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半口两年口 学位论文作者签名：衰玲 签字日期：徊7 7 s 导师签名：瓦卞泵瑶 签字日期：纠吕、- 7 j r j 东北大学硕士学位论文摘要 片上网络通信调度仿真系统的研究与实现 摘要 当前，运行在片上系统( s o c ) 的应用越来越需要大量并行的处理能力，因此集成在 s o c 上的处理器核的数量、存储容量、面向应用的信号处理器核的数量快速增长，在这 种新的多处理器s o c ，也就是所谓的片上多处理系统( m p s o c s ) 中，考虑到整体执行 效率的一个最重要的部分就是片上互联。片上网络( n o c ) 是解决大规模片上多处理器 系统中片上通信问题的有效途径。与基于总线的方式相比，片上网络通过使用网络互连 的方式进行通信，有效的降低了通信功耗、缓解了带宽争夺、提高了通信的可靠性、简 化了硬件体系结构，具有良好的可伸缩性。虫洞交换网络是片上网络系统中最常见的通 信机制。与存储转发网络相比，虫洞交换网络对缓存的需求量非常小，因此它非常适合 受成本、功耗、面积等方面严格限制的片上网络系统。本课题主要研究了基于虫洞交换 的片上网络系统实时通信调度的问题。 本论文研究了片上网络通信实时调度的相关的多个调度算法，设计与实现了一个基 于虫洞交换的片上网络系统实时通信调度仿真系统。该仿真系统可以对各类任务集( 周 期性任务集，非周期性任务集等) 在各种调度算法( r m 、e d f 、l l f 等) 下的实时性能进 行仿真调度和评估，从而为片上网络系统实时通信调度问题的研究提供支持。 该仿真系统的设计与实现主要分为两大部分，一部分是在片上网络中r m 、e d f 、 l l f 三种调度算法的设计与实现，即系统的实时通信调度仿真模块的设计与实现，另一 部分是该仿真系统中一些可视化界面的设计与实现，这其中包括了可视化手动生成任务 系统模块的设计与实现、随机自动生成任务系统模块的设计与实现、仿真结果显示与分 析模块的设计与实现和可视化仿真调度过程回放模块的设计与实现。 论文详细介绍了三种调度算法和该仿真系统所包括的五个功能模块的具体设计与 实现过程，同时本文也通过该仿真系统对这三种调度算法的性能进行了分析和比较。 关键词：片上多处理器；片上网络；虫洞交换；实时通信；仿真系统：调度算法 东北大学硕士学位论文 摘要 t 口 0 东北大学硕士学位论文a b s t r a c t d e s i g na n di m p l e m e n t a t i o no fa s i m u l a t i o ns y s t e mf o r c o m m u n i c a t i o n s c h e d u l i n go nn e t w o r k so nc h i p s a b s t r a c t c u r r e n ts y s t e m s o n - c h i p ( s o c ) e x e c u t ea p p l i c a t i o n st h a td e m a n de x t e n s i v ep a r a l l d p r o c e s s i n g ；t h u s ，t h ea m o u n to fp r o c e s s o r s ，m e r n o f i o sa n da p p l i c a t i o n - s p e c i f i cs i g n a lp r o - c e s s i n gc o r e si sr a p i d l yi n c r e a s i n g i nt h e s en o wm u l t i - p r o c e s s o rs o c s ，( m p s o c s ) o n eo ft h e m o s tc r i t i c a le l e m e n t sr e g a r d i n go v e r a l le f f i c i e n c yi so n - c h i pi n t e r c o n n e c t i o n s n e t w o r k - o n - c h i p0 q o c ) i sa l le f f i c i e n ts o l u t i o nf o rt h ec o m m u n i c a t i o no nl a r g e s c a l e 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 c o m p a r e d 、访n lb u s b a s e dc o m m u n i c a t i o n , n o c - b a s e d c o m m u n i c a t i o n 璐鹤n e t w o r ki n t o r c o n n e c t i o n s ，a n de f f e c t i v e l yr e d u c e sp o w e rc o n s u m p t i o n s ， m i t i g a t e sb a n d w i d t hc o n t e n t i o n s ，i m p r o v e st h er e l i a b i l i t y , s i m p l i f i e st h eh a r d w a r ea r c h i t e c t u r e a n dh a sg o o ds c a l a b i l i t y w o r m h o l es w i t c h i n gi sap o p u l a rc o m m u n i c a t i o nm e c h a n i s mf o r n o c c o m p a r e dw i t ht h es t o r e - a n d f o r w a r dm e c h a n i s m , w o r m h o l es w i t c h i n gh a sl e s sc a c h e r e q u i r e m e n t s ；t h e r e f o r ei ti sv e r ys u i t a b l ef o rn o c ，w h i c hi ss t r i c t l yl i m i t e db yt h ec o s t , p o w e r c o n s u m p t i o n ，s i z ea n do t h e ra s p e c t s t h ew o r ki nt h i st h e s i sm a i n l yf o c u s e so nt h er e a lt i m e c o m m u n i c a t i o n s c h e d u l i n g o nw o r m h o l es w i t c h i n gn o c s as i m u l a t o rf o rr e a l t i m e c o m m u n i c a t i o ns c h e d u l i n go nw o r m h o l es w i t c h i n gn o c si sd e s i g n e dt os u p p o r tt h er e s e a r c h o fc o m m u n i c a t i o ns c h e d u l i n g s o m ea l g o r i t h m sa b o u tt h er e a l - t i m ec o m m u n i c a t i o ns c h e d u l i n go nn o cw e r es t u d i e di n o u rw o r k , a n das i m u l a t o ra b o u tt h er e a l - t i m ec o m m u n i c a t i o ns c h e d u l i n go nn o ci sd e s i g n e d f o rf a c i l i t yt h er e s e a r c h t h es i m u l a t o rc a nh e l pt h er e s e a r c h e rt oe v a l u a t et h e r e a l - t i m e p e r f o r m a n c eo f v a r i o u st a s ks e t s ( e g p e r i o d i ct a s ks e t , n o n - p e r i o d i ct a s ks e t , e t c ) s i m u l a t e d b yi tw i t hd i f f e r e n ts c h e d u l i n ga l g o r i t h m s ( e g r m ，e d f , l l f , e t c ) t h er e s e a r c hi n c l u d e st w od i f f e r e n tp a r t s ：t h ef i r s tp a r ti sa b o u tt h es c h e d u l i n ga l g o r i t h m s a p p l i e dt on o c - b a s e dc o m m u n i c a t i o n , a n dt h r e es c h e d u l i n ga l g o r i t h m sa r ea n a l y z e di nd e t a i l ； t h es e c o n dp a r ti sa b o u tt h ed e s i g na n di m p l e m e n t a t i o no ft h eu s e ri n t e r f a c e so ft h es i m u l a t o r t h i st h e s i sd e t a i l e dt h ed e s i g na n di m p l e m e n t a t i o no ft h r e es c h e d u l i n ga l g o r i t h m sf o r n o ca n dt h ef u n c t i o n a lm o d u l e sr e q u i r e db yt h e s i m u l a t o r b yu s i n gt h i ss i m u l a t o r ， p e r f o r m a n c eo f t h r e es c h e d u l i n ga l g o r i t h mw a sa n a l y z e d k e yw o r d s ：m p s o c ；n o c ；w o r m h o l es w i t c h i n g ；r e a lt i m ec o m m u n i c a t i o n ；s i m u l a t o r ；, s c h e d u l i n ga l g o r i t h m - i i i 东北大学硕士学位论文 a b s t r a c t i 、 p l 蠢 ， t 东北学硕士学位论文目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第l 章绪论1 1 1 课题的提出、目的与意义1 1 2 国内外现状2 1 3 论文研究主要内容4 第2 章相关理论背景5 2 1 片上总线与片上网络概述5 2 1 1 片上互连方法5 2 1 2 片上总线及其优缺点5 2 1 3 片上网络6 2 2 片上互连网络路由分析7 2 2 1 片上互连网络路由算法设计特点7 2 2 2 片上互连网络路由机制8 2 2 3 片上互连网络的交换技术9 2 3 实时系统相关理论1 0 2 3 1 实时系统的三个性能指标1 l 2 3 2 实时系统的分类1 1 2 4 本章小结12 第3 章片上网络通信调度算法的设计1 3 3 1 系统模型中的三种调度算法+ 13 3 1 1 固定优先级调度算法1 3 3 1 2 抢占式的e d f 算法1 3 3 1 3l l f 调度算法1 4 3 2n o c 实时通信中的三种调度算法14 3 2 1n o c 实时通信调度中的r m 算法1 5 3 2 2 在n o c 实时通信调度中的e d f 和l l f 算法18 3 3n o c 通信调度中的性能优化方法19 3 3 1 影响n o c 通信调度性能的原因分析1 9 v 东北学硕士学位论文 目录 3 3 2 最优通信路由路径的定义2 0 3 3 3 最优通信路由路径的路由节点计算方法2 l 3 4 虫洞交换技术在n o c 中的应用研究2 2 3 4 1 死锁问题2 2 3 4 2 活锁问题2 3 3 5 本章小结2 4 第4 章片上网络通信仿真系统设计与实现2 5 4 1 系统总体设计2 5 4 1 1 系统各功能模块设计2 5 4 1 2 系统各功能模块间的关系2 6 4 2 仿真系统开发工具和环境2 6 4 3 系统中各功能模块的实现2 7 4 3 1 实时通信调度仿真模块的实现2 7 4 3 2 可视化手动生成任务系统模块的实现3 2 4 3 3 随机自动生成任务系统模块的实现3 6 4 3 4 可视化片上网络路由拓扑结构生成模块的实现3 9 4 3 5 调度结果显示与分析模块的实现4 0 4 3 6 可视化仿真调度过程回放模块的实现4 0 4 4 最优路由路径实现4 3 4 4 1 判断最优通信路由路径函数的设计与实现4 3 4 4 2 随机自动生成最优通信路由路径函数的设计与实现4 6 4 5 本章小结4 7 第5 章测试与性能分析4 9 5 1 测试数据的生成4 9 5 2 测试结果呈现5 1 5 3 测试结果分析5 3 第6 章结论5 9 6 1 论文主要的工作5 9 6 2 未来工作和展望6 0 参考文献6 3 致谢6 7 v i _ 查北学硕士学位论文目录 。- 一一- - - ： 研究生期间科研情况6 8 v i i 东北学硕士学位论文 目录 东北大学硕士学位论文第l 章绪论 第1 章绪论 1 1 课题的提出、目的与意义 片上多处理器系统( 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 ) 【1 】是指将多个处理 器或功能模块集成在同一片芯片上构成的特殊多处理器系统。随着现代计算机芯片技术 的发展，靠单纯提高频率来提高计算性能的途径已经不是主流，片上多处理器系统凭借 其在计算能力、功耗、可靠性、性价比等方面的巨大优势，已成为未来计算机系统发展 的必然趋势。与此同时，嵌入式系统也已经步入片上多处理器系统时代，例如t i 的o m a p 芯片上同时集成一个a r m 内核与一个d s p 内核，i b m 与s o n y 共同研制的c e l l 芯片上拥 有一个通用处理内核以及8 个专用处理器内核，而p i c o c h i p 近期推出的p c 2 0 5 芯片上 含有2 4 8 个d s p 内核和一个a r m 内核。 m p s o c 在对性能、功耗和造价具有严格要求的应用领域有巨大的市场。例如，通信、 多媒体和网络是符合该种需求的市场。这些通过标准定义的应用领域带动了巨大的相互 兼容的产品市场。这些标准不仅仅需要巨大的计算能力，并且需要简单电路所不能提供 的复杂算法【2 1 。 m p s o c 对汽车电子、航天电子，工业设备等诸多关键领域实时嵌入式系统领域也有 着非常广泛的应用前景。该类嵌入式系统除了具有高可靠性、强实时性的特点之外，该 类系统还具有很高的并行性，因为这类系统需要频繁的与外部环境通过传感器和执行器 进行联系，而外部环境信息是并行的1 3 】( 持续监控系统运行的各种状态以及发出控制指 令。系统往往需要进行多通道数据的并行采集和处理) ，该类复杂的嵌入式应用系统往 往需要异构的多处理系统来进行并行实时的海量数据采集和处理，同时需要实时进行复 杂的控制指令操作。在m p s o c 出现之前，由于这类应用对系统性能要求很高，因此多处 理器实时系统在很多关键领域得到应用，如航空电子控制系统、核反应堆控制系统等等 【4 】【5 】。而m p s o c 为这类复杂的嵌入式应用系统提供了一种集成的异构多处理器解决方案， 其单个芯片上可以集成的芯片数目可以更多，并且采用片上网络实现核与核之间通信， 因此同传统的多处理器系统相比，其处理能力和可靠性更高【6 】，可以很好的满足这类嵌 入式系统对多种性能指标的综合需求，例如同时具备高速的数据处理能力和高实时的控 制流程处理能力，未来将在汽车电子、航天电子、核反应堆控制系统、工业控制等关键 嵌入式实时系统领域得到广泛应用【7 】。 东北大学硕士学位论文第1 章绪论 m p s o c 将在通信、多媒体、网络和航天电子、工业控制和汽车电子等复杂嵌入式应 用领域发挥重大作用，已经引起大批研究人员和工业界的广泛关注，从2 0 0 1 年开始， 由i e e e 、e d a a 支持每年举办的专用r p s o c 论坛汇聚了研究领域的p r i n c e t o n 、m i t 、 b e r k e l e y 等众多知名高校的研究人员和a r m 、i n t e l 、i b m 、x i l i n x 、a c t e l 等芯片领域 的几乎所有知名公司【8 1 。从产业界看，国际上己有多家知名芯片厂商建立了m p s o c 平台， 分别有i b m 的c e l l ，a r m 的m p c o r e ，p h i l i p 的n e x p e r i a ，t i 的o m a p 以及x i l i n x 的v i r t e x 4 和v i r t e x 5 等。与其他m p s o c 平台不同的是，x i l i n x 公司通过重构的方式来实现定制的 m p s o c ，其v i r t e x 4 和v i r t e x 5 都支持各种软核的重构方案，为各类具有专门需求的应 用提供专用功能的m p s o c 或搭建各种m p s o c 试验平台提供了手段。 随着芯片集成度的不断提高，传统的基于总线片内通信机制在通信带宽，功耗，可 靠性等诸多方面已经远远无法满足需求。片上网络( n o c ) t l 】成为了未来片上多处理系 统必然的选择。目前已经有许多m p s o c 采用n o c 作为基础通信机$ 1 1 1 2 1 1 3 1 ，它们已 经初步显示出了这种方式的优越性。片上网络( n o c ) 【2 】是解决大规模m p s o c 片上通信问 题的有效途径。与基于总线的方式相比，片上网络通过使用网络互连的方式进行通信， 有效地降低了通信功耗，缓解了带宽争夺，提高了通信的可靠性，简化了硬件体系结构， 具有良好的可伸缩性。 由于网络通信方式的非确定性很强，基于片上网络( n o t ) 的任务系统与传统的单处 理器或者基于总线结构的多处理器的任务系统相比，其任务运行的时间属性更加难以预 测。因此将m p s o c 和n o c 应用于实时嵌入式系统，对系统设计者将带来巨大的挑战。 虫洞交换网络( w o r m h o l es w i t c h i n g ) i 3 1 ，是片上网络系统上最常见的通信机制。与存 储转发网络相比，w o r m h o l es w i t c h i n g 对缓存的需求量非常小，因此它非常适合受成本、 功耗、面积等方面严格限制的片上网络系统。本课题的研究将主要针对基于w o r m h o l e s w i t c h i n g 的片上网络系统的实时通信调度问题。 随着m p s o c 规模的不断扩大和制造工艺尺度的不断缩小，通信已经成为基于 m p s o c 和n o c 的系统实时性能的瓶颈，即系统时间属性受到通信的严重影响，因此通 信调度是这些实时系统中非常重要的问题。到目前为止，基于w o r m h o l es w i t c h i n g 网络 的实时通信调度问题方面的研究还非常有限。本课题将设计与实现一个基于虫洞交换的 片上网络系统实时通信调度的仿真系统。该仿真系统可以对各类任务集( 周期性任务集、 非周期性任务集、基于帧的任务集等) 在各种调度算法( r m 、e d f 、l l f 等等) 下的实时 性能进行仿真和评估，从而为片上网络系统实时通信调度问题的研究提供支持。 1 2 国内外现状 自从2 0 0 1 年片上网络系统被首次提出，过去的几年里，对于片上网络体系结构， 东北大学硕士学位论文第1 章绪论 网络协议，编程方法等方面的研究得到了飞速的发展【4 1 。片上网络的通信，首先取决于 其体系结构。例如p l e i a d e s s 】体系结构一个相对细粒度的异构片上网络系统，其应用实 例m a i a 处理器将a l u 、存储器、f p g a 等等各种运算资源通过网络的方式进行互联， 此网络是异构分层的，因而能够提供足够的通信灵活性和较低的功耗。片上网络系统和 传统网络一样，通常采用分层的网络协议结构【4 】，因此提供了网络各层次功能间的较好 分离。与传统网络相比，片上网络对能量、面积、网络拓扑、容错等方面的要求更加严 格，而同时，片上网络中不存在传统网络中诸如动态网络拓扑，向下兼容性等问题。 由于片上网络的特殊性和复杂性，它已经成为目前学术界越来越重视的问题之一。 但是片上网络系统的研究，目前还尚处于非常不成熟的阶段【们。尤其是对片上系统实时 性问题的研究非常有限。 z l ua j a n t s c h 和1 s a n d o r 7 】第一次对w o r m h o l es w i t c h i n g 片上网络中静态通信任 务集的可调度性问题进行了研究，文中假设系统调度的最坏情况为所有通信任务同时释 放的情况。z h e n gs h i 和a l a nb u m s 在他们的一篇文章【8 】中却指出该假设是错误的，即 w o r m h o l es w i t c h i n g 片上网络中通信某个任务被阻塞的最坏情况，并不一定发生在所有 的任务都同时释放的情况下。随后，该文又证明了一个更一般性的结论，即决定该问题 的最坏情况是n p h a r d 的。与此同时，该文中采用固定优先级的方式进行实时通信的调 度：在路由器中提供根据优先级的传输仲裁，并在路由器中提供与系统优先级数目相同 的虚拟通道( v i r t u a lc h a n n e l ) ，这样可以避免低优先级任务在被阻塞时继续占用传输资 源。该文章中研究了其可调度性判定问题，给出了一种充分而非必要的响应时间分析判 定条件。 这篇文章的研究表明，与处理器上的任务调度相比，w o r m h o l es w i t c h i n g 片上网络 中通信调度的问题模型更加复杂，具有很大的研究价值。由于基于优先级的网络通信中， 允许n i t 层次或p a c k e t 层次的抢占，而与处理器上的任务抢占不同，通信的抢占带来的 开销是非常小的，因此许多在处理器系统上因抢占开销限制而不适用的调度方式( 比如 最小松弛时间优先调度算法和基于公平的调度算法) ，适用于解决片上网络中的通信调 度。作为进行这个问题深入研究的第一步，编写一个相应的仿真系统来对各类任务系统， 各类调度算法在该问题中的性能表现进行仿真分析，是非常必要的。 目前，学术界和工业界有许多网络系统仿真系统。例如n s 2 【9 】是最著名网络系统仿 真系统，通过它可以对包括移动a d h o c 网络( m a n e t s ) 和无线传感器网络( w s n ) 在内的 动态网络系统或分布式系统进行仿真。o p n e t ( o p t i m i z o dn e t w o r ke n g i n e e r i n gt o o l s ) t l o l 是o p n e tt e c h n o l o g i e s 公司开发的一个商业工具，用于对通信网络，设备和协议进行建 模和仿真。o p n e t 主要是用于企业进行网络系统的诊断与重组。g l o m o s i m ( g l o b a l m o b i l ei n f o r m a t i o ns y s t e m ss i m u l a t i o nl i b r a r y ) 】是美国加州大学洛杉矶分校计算实验 东北大学硕士学位论文第1 章绪论 室开发的一个可扩展的仿真程序库，其主要用于对超大规模无线网络模型的研究。 g l o m o s i m 使用基于c 语言的并行离散时间仿真语言p a r s e c ( p a r a l l e ls i m u l a t i o n e n v i r o n m e n tf o rc o m p l e xs y s t e m s ) 1 2 1 。p a r s e c 最重要的一个特点是它能在不同的并行 体系结构上使用异步并行协议来执行离散事件仿真模型。但是，g l o m o s i m 的文档资料， 工具标准，用例支持等等资源非常少，不利于其它用户扩展和使用。q u a l n e t 1 3 是一个 基于g l o m o s i m 的商业工具，旨在改善g l o m o s i m 的上述问题，但同时，使用者不得不 为其提供的文档技术支持支付昂贵的费用。 但是，这些仿真工具都不具备对系统时间行为进行描述的能力【1 4 1 ，因此不能被直接 应用于我们的问题。对现有网络仿真系统进行修改和扩展，虽然可以应用于我们的问题， 但是由于这些现有工具有其特定的设计目的，而非针对实时系统，因而缺乏针对实时系 统进行仿真的优化，这将导致比较低的仿真性能。 r t s i m t l 5 】是一个用于进行多处理器嵌入式系统建模和仿真的c 卜+ 库。r t s i m 最重要 的特点是它汇聚了目前处理器调度和有限延迟资源共享方面最前沿的理论成果。但是， 由于r t s i m 最初就不是为网络而设计的，因此无法直接应用于对片上网络系统的仿真。 综上所述，目前现有的各类网络仿真系统和实时系统仿真系统，都无法满足对片上 网络系统中实时通信任务调度仿真的要求。因此，设计并实现一个仿真和分析工具，对 片上网络系统实时性问题的研究有非常重要的意义。 1 3 论文研究主要内容 本课题研究的主要目的是研究和实现一个片上网络系统实时通信调度仿真系统，以 便为n o c 上的各种调度算法性能进行评估。该仿真系统可以为用户提供所见即所得的任 务系统和片上网络路由拓扑结构的生成，以及一定参数范围内的随机自动生成的任务系 统。该仿真系统能够对生成的任务系统进行不同调度方式的实时调度仿真，从而得到任 务系统的可调度性，响应时间等实时性能，并会对仿真结果进行显示和分析。在实时仿 真调度过程中，该仿真系统还可以对仿真过程中的事件进行记录，因此该仿真系统还可 以提供任务系统可视化的仿真调度过程的回放。 论文主要研究工作包括：( 1 ) 片上网络相关理论分析和研究；( 2 ) 片上网络通信实 时调度研究的系统模型建立；( 3 ) 片上网络通信调度仿真器的设计与实现；( 4 ) 基于该 仿真器的各种片上网络通信调度算法的实时性评估和分析。 4 东北大学硕士学位论文 第2 章相关理论背景 第2 章相关理论背景 本章主要介绍片上互联的各种方法及其优缺点，主要介绍了片上总线和片上网络两 种片上互联方法、互连原理；介绍了片上网络互联路由相关理论和实时系统相关理论。 2 1 片上总线与片上网络概述 2 1 1 片上互连方法 基于m 核的s o c 设计应该是面向互连的。未来s o c 的片上通信结构的可靠性、低 功耗、高性能设计将面临前所未有的挑战，互连技术将成为达到复用操作目的的限制因 素。图2 1 中展示了s o c 中三种基本的互连通信结构。 ( a ) 总线互连( b ) 点对点的互连 ( c ) 片上网络互连 图2 i 三种基本的互连通信结构 f i g 2 1t h r e eb a s i cc o n n e c t i o na r c h i t e c t u r e 2 1 2 片上总线及其优缺点 2 1 2 1 片上总线 s o c 的设计过程中，最具特色的是m 复用技术，即选择所需功能的m 核集成到一 个芯片中。由于p 核的设计千差万别，口核的连接就成为构造s o c 的关键。片上总线 ( o n - c h i pb u s ，o c b ) 是实现s o c 中m 核连接最常见的技术手段，它以总线方式实现m 核之间数据通信。一个片上总线规范一般需要定义各个模块之间初始化、仲裁、请求传 输、响应、发送接收等过程中驱动、时序、策略等关系。 2 1 2 2 片上总线的缺点 基于总线的通讯方式，即使采用的分层思想【2 0 】，如通过桥接的方式将片上总线分成 高速处理器总线、系统总线、低速外围总线，可以在一定程度上提高s o c 性能，但仍不 能满足未来s o c 设计的需要。传统的片上总线体系结构正在成为未来大规模s o c 多i p 核通信的瓶颈，主要表现在以下几个方面： ( 1 ) 结构带宽限制：传统的片上总线结构不能随着片内i p 核的增多而自由伸缩，并 且总线是一种共享介质的互连结构，某一时刻只允许一个设备使用总线。仲裁逻辑允许 高优先级的设备获得总线的使用权，在总线被占用期间，所有其他的请求将被阻塞，直 - 5 东北大学硕士学位论文第2 章相关理论背景 到总线空闲。这就导致了系统并发通信能力低和吞吐率低，而且上百个p 核都连接在 总线上时，总线频率将降低，总线速度也会受到影响。 ( 2 ) 信号集成度( 可靠性) ：未来s o c 将会有更低的电压、更小的线宽，这使得整个 v l s i 系统对电流中的噪声更加敏感。而共享介质上的多功能部件会进一步加重噪声。 ( 3 ) 信号延时：随着芯片特征尺寸的下降，芯片内部的连线延迟超过门延迟成为了 影响信号延时的主要因素。实际上，互连线延迟已经成为当今v l s i 系统设计的一大挑 战，在整个设计流程的早期，由芯片内部各个通信部件分布距离决定的延迟很难确定， 所以在未来的s o c 设计中，开发一种新的在设计流程早期就可以估计延迟的通信互连架 构很重要。 ( 4 ) 全局同步：全局连线上的信号延迟决定了系统的时钟周期，并且全局时钟会带 来时钟歪斜的问题，驱动遍布整个芯片的全局时钟信号线需要消耗很多的能量，为了保 持甚至提高系统的时钟频率，解决时钟歪斜问题，和解决庞大时钟树所带来的功耗问题， 未来大规模多核的s o c 设计必须使用全局异步局部同步( g l o b a la s y n c h r o n o u sl o c a l s y n c h r o n o u s 。g a l s ) 机制，每一个代理模块工作在自己的时钟域，而不同的资源节点之 间则通过片上互连网络进行异步通讯。 由于总线的串行访问特征，使得共享总线架构并不适合较大规模的多处理器系统或 通讯要求很高的应用。 2 1 3 片上网络 片上总线概念从板级而来，为了面对高频率，较大规模的s o c 片上通信结构的要求， 片上总线采用了流水线技术，采用了桥接分级总线结构，如a m b a 等，来缓解一下片 上总线结构面临的压力，但这样的结构只是能胜任大约只有2 0 个左右口核的小规模s o c 的片内通信，片上总线结构没有本质上的变化。但是，集成电路制造技术仍然按着摩尔 定律在发展，根据i t r s 的预测，到2 0 1 1 年，集成电路的特征尺寸将达到5 0 n m ，工作 频率也在1 0 g h z 左右，单芯片系统中将可容纳更多的m ，多达上百个。面对如此大规 模的系统芯片，无论从集成电路系统芯片的设计方法学角度出发，还是从系统芯片本身 的系统结构出发，都需要发展一种新的片上通讯架构来适应未来大规模，多核的系统芯 片的设计与开发。这种新的片上通讯架构与片上总线相比，具有更高的灵活性，更强的 可扩展性，能够在深亚微米工艺下，避免过长互连线的出现而不带来信号的衰减，而且 能够从本质上带来系统的并行性，提高系统的吞吐率，这种新颖的片上通信架构就是片 上网络，也就是基于网络构建系统芯片的片内通信架构，同时也以它为中心展开一系列 相关的系统芯片设计方法学的研究。片上网络概念是在上个世纪末本世纪初提出来的， 学术界和工业围绕片上网络进行了相关研究。 片上网络( n o c ) 指的是在单个芯片上实现的基于网络通讯的超级系统，其核心思想 每 东北大学硕士学位论文 第2 章相关理论背景 是将计算机网络技术移植到芯片设计中来，从体系结构上彻底解决片上通讯的瓶颈问题。 它采用网络的通讯方式代替传统总线通讯方式，提供异步通讯机制，解决了传统总线采用 单一时钟同步的通讯瓶颈问题。此外，片上网络还具备数据处理量大、多任务并行计算、 架构易扩展、灵活性强等特点。该技术以其支持同时访问、可靠性高、可重用性高等特 点被认为是更加理想的大规模c m p 互连技术。片上网络克服了总线结构可扩展性差的 缺点，为l o 亿晶体管时代提供了一种可行的片上系统通信机制。片上网络除了可以连 接更多的m 组件，与总线结构相比，还有高可重用性等特点。它是基于片上网络的互 连结构，即m 核之间通过网络结构来实现数据的传输。 2 1 3 1 片上网络的路由方式 在n o c 系统内进行数据传输时，有三种路由方式可供选择，即“存储转发”( s t o r e a n df o r w a r d ) 、w o r m h o l e 和“偏置路由一( d e f l e c t i o n m u t i n g ，以h o tp o t a t o 为代表) 。 存储转发路由方式，即当一个转发器接收完整个数据包后，再将数据包发送至另一 个转发器。虽然该方式保证传递过程中数据完整，但完成一跳的时延过长，且每个转发 器需要有足够的缓存来存放一个数据包，不太适合n o c 的需求。 w o r m h o l e 路由方式当初是为了研究计算机并行计算而设计出来的，它可以减小传 输时延和缓存空间。传输数据时，每个数据包被分为多个数据分片，当传送头分片( h e a d f l i t ) 时，转发器选择一条最优路径，记录下数据包类型，并保持该路径通畅，直到数据 包的所有数据分片通过为止。这种方式需要比较复杂的控制逻辑，需要记录数据类型以 及头分片的路由信息，当数据过长时，也可能产生阻塞，同时，还需要一个确认机制以 防止数据丢失或重发，这也增加了系统的负载。 偏置路由( d f ) 采用了一个比较成熟的转发机制，即对数据包中的每一个分片，都选 择了一条当前系统中的最优路由，而不是固定路由，这样不需要为一个特定数据包保持 一条通路，一个数据包中的不同分片可以同时传输，提高了系统利用率。当接收数据时， 分片到达顺序可能不同于发送顺序，这就需要为每个分片编号，再接收端重新组装。此 方式的网络接口设计较为复杂，同时需要一个良好的拥塞控制方式来避免数据的丢失和 重传。 2 2 片上互连网络路由分析 2 2 1 片上互连网络路由算法设计特点 片上互连网络的研究和设计可以借助传统计算机网络和并行计算及系统研究中的 特点和设计方法；同时由于片上互连网络自身的特点，可以利用单芯片上丰富的互连线 资源，但又受芯片面积和功耗的限制，不能使用太多缓存，这与传统的网络又有所不同。 所以在片上路由算法设计方面需要采用新的方法，特别是在如下两个方面： 东北大学硕士学位论文 第2 章相关理论背景 ( 1 ) 片上互连网络结构：片上互联网络结构可以利用芯片上丰富的互连线资源。控 制信号不需要被传入数据中一起传送，而可以使用专用的控制信号线，同时为了减小芯 片面积和功耗，片上缓存区的使用数量将被限制。 ( 2 ) 路由算法：片上网络路由算法要求尽量少的使用片上缓存区，同时网络的状态 ( 包括拥塞信息) 也能够通过专用的信号控制线来传送，这样就有可能实现相邻节点状态 信息的及时传递，提前预判竞争，减少线路竞争的发生，减小阻塞发生的可能性，降低 数据传输延时，提高片上互连的性能。 2 2 2 片上互连网络路由机制 网络的路由算法决定了使用源到目的地所有可能路径中哪一条作为路由，也决定了 各个特定数据包如何遵循该路由。路由器的基本操作是监视其输入到达的数据包，对每 个输入数据包，选择一个将其送出的输出端口。所以路由算法是函数r - n * n - - 屺，它 在各个节点将目的节点i l d 映射到路由上的下一个通道。高速路由器基本上使用三种机制 从数据包头的信息来决定输出通道：算数运算的、基于源的端口选择和查表。片上互连 网络中，路