《基于高斯网络的可重构NoC设计方法研究.doc》由会员分享，可在线阅读，更多相关《基于高斯网络的可重构NoC设计方法研究.doc（6页珍藏版）》请在三一办公上搜索。
1、基于高斯网络的可重构NoC设计方法研究摘要 单击此处键入中文摘要. 应反映出论文的主要观点, 概括其结果或结论. 摘要的撰写要精心构思, 随意从文章中摘出几句或只是重复一遍结论的做法是不可取的. 摘要中不能出现文献序号.关键词 高斯网络， Hamilton环，可重构，NoCPACS: 21.10.Jx, 46.90.+s, 46.15.-xShashi Kumar等人提出片上网络NoC1以来，这种有效的片上系统处理器间的通信架构2-4得到了众多学者的认可，但通信网络在片上系统中的能耗是不能忽视的2，需要对NoC进行优化和重构设计，以达到重新配置空闲资源，节约功耗的目的。目前有报道的基于网络通信
2、状态的重构设计：文献3提出了一种根据路由的使用情况重新分配端口缓冲大小方法；文献4提到根据网络流量分布动态改变链接的数据流向的方法；文献5-9提到对应特定应用重新映射分配网络链接的方法，这往往无法满足复杂应用的需求；文献10,11提出一种针对满足一定约束的复杂应用集的重映射方法，针对上述重构方法的缺点，文献12提出了一种在路由连接间添加轻量级可配置，结合网络的通信任务图，动态调整开关通路来实现重构网络的方法；以及文献13提出的ReNoC，一种通过在物理路由外层包裹多个拓扑开关，配置路由的联通的方式实现可重构的网络架构及在它之上发展的重构方法12-14；还有文献15对应同质处理器核NoC提出的，
3、核心可替换的重构方法。但是上述工作都需要很好的掌握网络的通信情况，并通过较复杂的算法完成重构分配，且重构后的网络没有一般的规则，缺乏有效的自动构造机制以及相应的数学理论的支持。近年来，随着SoC多层布线技术的发展，可以实现三维环状网络连接，就有学者将更优秀的网络拓扑结构和对应路由算法 16-18应用到NoC架构上，以优化网络的吞吐量和延迟。文献19,20提到立方体网络拓扑应用到NoC网络中；文献21,27提到Torus的网络拓扑和对应路由算法，并和Mesh结构进行对比；文献22-25提到循环图的拓扑结构；近年来有研究人员提出将高斯网络的理论应用到NoC架构中26-29，高斯网络是针对高斯整数定
4、义的拓扑结构，对应不同的高斯整数给出不同的网络。上面提到的Torus和环形网络结构都可以由特殊条件下的高斯网络表示，文献29还提出了基于高斯距离的最短路径路由算法可以在合理的功耗花销下进行快速的路由路径计算比基于网络流量监控的动态算法更适用于路由设计，并可证明路由算法具有无死锁，无活锁的特性。但已有文献仅在高斯网络在网络拓扑特性和路由算法的优势进行了描述，基于高斯网络的重构设计却没有提及。在本文中，将通过对高斯网络特性的研究，分析其应用在NoC的优势，拟将高斯网络特性和网络重构方法结合，在保证重构前后网络特性一致的情况下，提出基于高斯网络的可重构思想，并设计出重构的方案。同时将给出重构的约束条
5、件和可重构思想理论证明。1 高斯网络及其在NoC应用上的优势1.1 高斯网络（连贯）高斯网络是由高斯图33描述的网络，网络节点唯一对应图中顶点，网络连接由图中无向边表示。针对任意一个高斯整数28，文献29给出了如下网络描述： (1)从上面描述可知，基于的高斯网络中的每个节点唯一对应中一个高斯整数, 表示的余集28，具有个节点，每个顶点有且仅有四个连接，分别连接到相邻的其它四个顶点，所有连接是无向的，且对于连接的顶点是对称，无差别的。图1给出了的网络结构。图1 3+4i的高斯网络拓扑1.2高斯网络在NoC中的应用优势分析图1给出的网络结构，整体网络由一个mesh网络和一个mesh网络连接而成，外
6、加边缘节点根据网络定义的特有连接，保证每个节点拥有4条连接，在NoC设计中使用高斯网络与mesh结构的NoC对比，整个网络有更多的可用连接，连通性更强，网络出现拥塞的几率更小；图2 高斯网络G5和mesh网络同时由图2可以观察到mesh结构对顶角间的距离是8，而G5中仅为2，同时通过分析高斯网络的距离分布29，给出两种结构距离分布的对比图。图3 G5和mesh网络距离分布对比图从图中可以看出高斯网络不仅在网络直径上有明显优势，而且短路径也比mesh网络要多。这从NoC的数据传输角度表现为高斯网络相对于mesh结构在传输延迟上有明显的优势。将高斯网络运用到NoC中，根据网络特性，只要通过简单的线
7、性运算和数值对比，在线性时间O（n）内就能得到网络中两节点间最短路径，并进行路由选择，称为最短路径路由算法29。由于NoC节点的功耗和面积的限制，基于网络流量分析的动态路由12需要复杂的运算并不适用于NoC路由设计，而基于最短路径的静态路由算法可以在合理的功耗/面积花销下进行快速的路由路径计算,因此更适合路由设计; 同时，由于前面提到的距离分布的优势，该算法对于mesh结构上同样是通过距离选择的XY路由21有明显优势。1.3可分解出Hamilton环的高斯网络（融合到前面的路由里面去）对于高斯整数和高斯网络，当且仅当时，存在环形网络使得,证明见26，表明满足条件的高斯网络按给定单位可以循环遍历
8、所有网络节点。同时根据高斯网络的定义，每个点对应的高斯整数是唯一的，且增加一个单位量仅会出现一个可能的值，保证了按给定单位遍历网络的路径上不会出现公用的边，上述条件满足了边不相交的Hamilton环的定义30，于是可证明满足时可分解出两个边不相交的Hamilton环31。文献32中表明可分解出边不相交的Hamilton环的网络可以保证单位时间内最大的信息传输。同时,文献21证明了网络可分解出边不相交Hamilton环，对于上面提到的最短路径路由算法可以同时保证无死锁和无活锁。2 可重构的高斯网络2.1 高斯网络的可重构依据本小节将从网络硬件结构和高斯网络性质两方面讨论高斯网络的可重构特性。从硬
9、件方面，如图4所示，采用ReNoC13的网络节点结构,只要配置路由外围的交叉通道电路，就能动态地实现NoC的可重构变化。图4 高斯网络重构路由连接示意图图4右下角网络节点处在正常状态下运行，路由器和外界保持正常连接保证网络节点正常工作；图中右上角的网络节点处于低功耗运行模式，路由和处理核心停止工作，且不和外界联通，仅外围交叉通道保证特定方向的电路联通。这样的设计在保证重构后网络连通需求的同时，又充分减少了网络剩余节点在系统中的功耗。从高斯网络性质方面，对高斯网络定义进行分析发现，高斯网络除边缘节点内部采用固定的网格互联方式，所有高斯网络内部连接模式相同，网络重构后连接可以直接使用无需修改；基于
10、文献29给出的高斯网络边缘节点连接公式，结合对不同参数网络的大量观察分析发现，网络外围节点连接路径方向有规律，只要保证重构前后网络定位可靠，仅需要原始网络提供小范围内的连通支持，就能在不会影响其他路径连通的情况下完成重构连接，同时能保证不出现横穿整个网络的重构连接，阻碍重构的顺利实现。综合本节的讨论，在硬件技术和网络自身性质上保证高斯网络具有可重构性。2.2 高斯网络的可重构条件及证明但也不是所有的情况都能实现网络的重构，如图5给出例子。图4 到的重构需要的连接由图4可见，在中建立的从到的连接，图中粗实线表示，将会占用的所有连接通路，导致的重构连接无法完成。所以需要对重构前后的网络添加约束条件
11、进行限制。首先，重构后网络规格上要求比原网络小；其次重构后网络要具备原网络相同的特性，路由算法可正常使用；最后，重构后网络边不能重叠，保证重构后连接无须路由，仅通过静态连接通路就可完成。对于在中的重构，下面给出约束的数学表达：对上述约束条件的证明：首先，在下面证明中，规定中b节点重构后位于中b节点位置，其它节点依次排布，这将在后面给出证明。其次，为了保证重构的可完成性，重构后网络在尺寸上应该小于原网络，必须满足条件；最后，通过重构路径的构造过程和高斯网络的定义，对于原网络和重构后网络，在实轴上坐标小于b的点在重构中的延伸节点将会出现在的最上边沿，对应的另一个延伸节点将会出现在处，如图5所示。类
12、似的路径有b条，根据最短路径算法，完成连接还需要原网络提供条实轴上的连接，在右上方区域内，原网络可提供的连接有条，只有当时原网络提供的连接才能满足重构的需要，其它区域证明类似。图5 在中的重构过程示意图对于定位点选择的证明：首先，从高斯网络边的定义上看：对于任意高斯网络中b-1点对应-i的相邻点为，其位于网络右上角；b点对应-i的相邻点为，其位于网络左上角。根据上面描述的连接位置关系可以推断出：在重构前后网络的对应b点不重合的情况下，将会存在一或多个从原网络左端到右端的长距离连接，这样的连接会占用大量连接，根据的前面对条件的证明，可知需要满足条件的网络才可能完成重构，其中x0表示上述长连接的个
13、数，显然满足这个条件的可重构网络要比满足原条件的少，所以选择重构前后网络的对应b点重合，可以保证重构网络选择的最大灵活性。3 可重构高斯网络的设计与实现3.1重构算法描述本节描述如何构造重构后网络的算法，设原网络和重构后网络。第一步 定位重构后网络节点位置首先，定位中b-1节点到中b-1节点位置，然后其它点根据高斯网络定义，按照其于b-1点的相对位置分布，依次在中找到对应点，并记录对应中的坐标，如图4示意，图中空心点代表中节点排布，实心点代表中节点排布。图6 在中的重构节点分布第二步 确定重构后网络的边在原网络中的路径在确定了节点的位置后，根据的边的定义在中确定连接关系，当的边相连的节点对映射
14、在中也是相邻关系时，直接采用原有边加入当的边的节点对映射在中没有直接相邻关系时，需要进一步选择原有连接的组合来完成边的路径。第三步 确定重构后的新连接路径，完成网络重构首先对一些简称进行描述，为后续描述做准备：1高斯网络边（连接）对于某个端点的下一跳方向，由下面计算获得：设中一条边连接的两个点分别表示为和，对于点的方向为： (4)2边缘连接，在一条长度大于1的路径中，包含一个路径端点的连接；3延伸节点，路径端点通过边缘连接延伸出的节点。连接算法设计思路如下：首先，新的连接必须保证在原有网络上正常运行的路由算法依然可以正常运行，这就要求在中关于的边新产生的路径，必须包含对于路径端点和有相同下一跳
15、方向的两个边缘连接；其次，为保证的边不重叠，必须保证在完成路径连接的过程中不能重复使用已被占用的连接。最后，为保证连接占用率最低和路径的长度最小，然后采用最短路径算法计算原网络中两延伸节点间的高斯距离，同时在保证边不重复的情况下，逐个添加连接，直到完成需要的重构路径。3.2 算法时间复杂度分析首先定有n个点，的直径为d， 在对中所有节点进行定位和连接准备过程中仅存在简单数值计算和判断步骤，所有复杂度为O(n)。在建立单个完整连接的过程中，最短路径算法复杂度29为O(1)，在寻找连接的过程上，因为约束条件保证了连接存在性，根据高斯网络距离的性质复杂度为O(d)。综上所述整个重构过程复杂度为O(n
16、d)，这在与中直接建立n条连接路径的复杂度一致。表明了我们的算法在时间复杂度上是最优的。3.3重构的结果展示图1如图所示。图1 单个重构连接示意图5 结论本文介绍了高斯整数和高斯网络及其性质。提出并证明了可重构的条件，提出了重构的方法，最后给出了重构的效果展示。另外重构的连接中含有若干将会影响数据传输的速率，这将在后面研究中继续完成。参考文献 1 Wang Q H, Lindon O, Hardle W. Semiparamet-ric regression analysis with missing response at random. J Am Stat Assoc, 2004, 99:
17、 3343452 Rordam M, Larsen F, Lausten N. An introduction to K-theory for C*-algebras. Cambridge: Cam-bridge University Press, 2000. 30353 Qin H R. The subgroups of a finite order in K(Q). In: Bass H, Kuku A O, Pedrini C, eds. Algebraic K-theory and Its Application. Singapore: World Scientific, 1999.
18、6006074 Minor H E. Spillways for high velocities. In: Zu-rich V E, Minor H E, Hager W H, eds. Proceed-ings of International Workshop on Hydraulics of Stepped Spillways, Rotterdam, the Netherlands, 2000. 3105 Liu G X. Classification of finite dimensional basic Hopf algebras and related topics. Disert
19、ation for the Doctoral Degree. Hangzhou: Hangzhou University, 2005. 24286 Phillips N A. The Nested Grid Model. NOAA Tech-nical Report NWS22. 19797 苏晓龙, 贾晓军, 谢常德, 等. 用正交压缩态光场产生连续变量类GHZ和类Cluster四组分纠缠态. 中国科学G辑: 物理学 力学 天文学, 2007, 37(6): 6896998 Zhang W P. Experiment Apparatus of Diffraction Imaging. Chi
20、na Patent, 02290557.X, 2003-12-039 Wang D L, Zhu J, Li Z K, et al. User Manual for QTKMapper Version 1.6, 199910 Hemodynamics III: The ups and downs of hemodynamics. Version 2.2. Orlando (FL): Computerized Educational Systems. 199311 Christine M. Plant physiology: Plant biology in the Genome Era OL.
21、 Science, 2003, 281: 331332 2003-09-23. http:/www.sciencemag.org/ anatmorp.htm12 傅景礼, 陈立群, 陈本永. 非规范格子离散机电耦合动力系统的Noether理论. 中国科学: 物理学 力学 天文学, 2010, 40(2): 13314512 He C J, Zhou H B, Hang Y H. A numerical study on Rayleigh-Taylor instability of aluminum plates driven by detonation. Sci China Phys Mech
22、 Astron, 2010, 53(2): 19519830, D. Witte, J. Gallian, A survey: Hamiltonian cycles in Cayley graphs, Discrete Math. 51(1984), 293-304.TitleAuthor 11,2*, Author 22 & Author 331 Address 1;2 Address 2;A precise dynamical model to describe the relative motion of a lunar probe in a rotating coordinate sy
23、stem is presented. Real celestial mechanics background of the sun, the earth and the moon is considered. An accurate and simple formula of the absolute angular velocity of the rotating coordinate system Including solar gravitational perturbation is derived. The model would be the one for elliptical
24、restricted three-body problem if the solar gravitation was neglected, and the one for circular restricted three-body problem if the lunar orbit eccentricity was zero. An iterative method to calculate accurate collinear and triangular Lagrange points, which are relevant to the Julian date and time period concerned, was established. The model can be used to design transfer orbit to the moon passing through the Lagrange points.lunar probe, relative orbital dynamics, Lagrange point, four-body problem, solar gravitational perurbationPACS: 05.45.-a, 45.50.Jf, 45.50.Pk, 95.55.Pe, 96.12.De
