分层立方体网络在NoC线性阵列中的最优嵌入

随着大数据时代的到来,大规模计算的需求使得人们对芯片性能的要求日益提高,片上网络(Network-on-Chip,NoC)作为芯片内部以网络通信为中心的互连结构,在通信的各个方面实现了良好的平衡。NoC组件的物理布局及互连方式对芯片的总体性能(如信号延迟、电路成本等)有着很大的影响,因芯片面积有限,最小化连接组件的导线总长度,即最小化线长,被作为芯片设计的重点。分层立方体网络(Hierarchical Cubic Network,HCN)具有通信延迟低、可靠性和扩展性高等优点,而线性阵列是NoC常用的拓扑结构之一,将分层立方体网络移植到线性阵列上,就可以在线性阵列上模拟分层立方体网络的结构和算法。图嵌入是实现网络移植的关键技术。在图嵌入中,最小化导线总长度的目标可以通过求解具有最小线长的最优嵌入来达成。文中主要研究了分层立方体网络在线性阵列中的最优嵌入问题。首先,通过研究分层立方体网络的最优集,提出了分层立方体网络在线性阵列中的一种嵌入方案hel,并证明在嵌入方案hel下的线长相比其他嵌入方案下的线长是最小的,即hel为最优嵌入;然后给出了嵌入hel下线长的精确值以及一个时间复杂度为O(N)的嵌入算法,其中N为n维分层立方体网络的顶点数且N=22n;其次,还给出了分层立方体网络在NoC上的线性物理布局算法;最后,通过对比实验评估了嵌入hel的性能。

BC互连网络及其性质

提出一种称为一一对应连接 (BC)图的互连网络族 ,使其包含超立方体、交叉立方体和M bius立方体作为其真子集 ,同时又使其具有与超立方体、交叉立方体和M bius立方体相同的对数级的直径和顶点度数、最高连通 (容错 )度和相同的可诊断性等性质 ,从而使对超立方体及与其结构相似的大量互连网络的某些性质的研究合而为一 ;

Mbius立方体互连网络上的圈嵌入算法

图嵌入技术是研究多处理器互连网络模拟其它网络的能力的重要技术．文中讨论了近年提出的一类互连网络——Ｍｏｂｉｕｓ立方体上的圈嵌入性质．Ｍｏｂｉｕｓ立方体是超立方体的变型，它们具有一些比超立方体更优越的性质，如ｎ维Ｍｏｂｉｕｓ立方体Ｍｎ的直径大约是ｎ维超立方体的一半，其期望距离大约是ｎ维超立方体的２３等．文中证明了Ｍｏｂｉｕｓ立方体另一个比超方体优越的性质，即任一长度为ｌ（４≤ｌ≤２ｎ）的圈能以扩张ｌ嵌入ｎ维Ｍｏｂｉｕｓ立方体Ｍｎ（ｎ≥２），并给出了构造过程，从而也证明Ｍｎ对环网络的模拟能力比超立方体的高（超立方体不含奇长圈）．

交叉立方体互连网络的Hamilton连通性

交叉立方体互连网络是超立方体的一个变型，它有一些比超立方体更好的性质．本文证明了ｎ维交叉立方体ＣＱｎ的又一个超立方体所不具备的性质，即当ｎ≥１，ｎ≠２时，ＣＱｎ是Ｈａｍｉｌｔｏｎ连通的，并给出了当ｎ≥４时ＣＱｎ中任意两个顶点间Ｈａｍｉｌｔｏｎ路条数的一个下界４（２ｎ－１－２）∏ｎ－２ｉ＝３（２ｉ－２）２．

超级Mbius立方体──一类最优容错的小直径互连网络

文中将具有２ｎ个顶点的Ｍｏｂｉｕｓ立方体的拓扑结构加以改变，得到了包含任意个顶点的互连网络——超级Ｍｏｂｉｕｓ立方体，并证明它保持了Ｍｏｂｉｕｓ立方体的高连通度、对数级的直径和顶点度数等优良性质，并且当顶点个数Ｎ＝２ｎ＋２ｎ－１时，０－型超级Ｍｏｂｉｕｓ立方体是一个（ｎ＋１）－正则图；更进一步地，由于它包含任意个顶点，所以其升级只需增加任意个顶点，从而克服了Ｍｏｂｉｕｓ立方体的升级必须成倍增加其顶点个数的缺点．

交叉立方体在两种策略下的可诊断性

互连网络可诊断性度的高低是衡量这种网络性能优劣的重要标志二交叉立方体是近年提出的一类互连网络，它有一些比超立方体更好的性质．本文用PMC模型证明了n维交叉立方体Dn在精确策略和悲观策略下分别是n-可诊断的和（2n－2）／（2n－2）一可诊断的，从而证明民在这两种策略下的可诊断性度与n维超立体的相同．另外，本文在证明Dn是n-可诊断的同时，还得到了Dn中任何两顶点之间的n条互不相交的路径，它们可作为容错远路的依据．

超级交叉立方体互连网络及其拓扑性质

交叉立方体是近年提出的超立方体的一个变种．由于它的许多优越性质（如直径、嵌入性等），在并行处理领域越来越受到人们的重视．然而，像超立方体一样，它也有一个缺点，即要使交叉立方体升级，就必须成倍地增加其顶点个数．为了解决这一问题，本文将顶点个数为２的次幂的交叉立方体推广到具有任意个顶点的互连网络，提出了超级交叉立方体的定义，并证明它保持了交叉立方体在高连通度、对数级的直径和顶点度数等方面的优良性质。

将圈嵌入交叉立方体及其算法

图嵌入技术是研究处理器互连网络的计算性能和任务分配的重要技术，是近年来并行处理领域研究的热点之一．本文研究了交叉立方体互连网络上的圈嵌入问题，证明了任何长度为ｌ（３＜ｌ≤２ｎ）的圈均能以扩张１嵌入交叉立方体ＣＱｎ，并证明了ＣＱｎ包含２ｎ－ｋ个互不相交的长为２ｋ（１≤ｋ≤ｎ）的圈，最后给出了一个Ｏ（ｌｏｇｌ）级的圈嵌入算法．

多处理器互连网络诊断性和容错性的细胞图自动机算法

本文将细胞图自动机概念引入多处理器互连网络，并用细胞图自动机设计了多处理器互连网络上的多项式纹诊断和容错算法，从而给出了研究互连网络诊断性和容错性的另一种有效方法．

超级交叉立方体互连网络上的圈嵌入

作为超立方体的变型 ,交叉立方体同时具有一些比超立方体优越的性质 ,但类似于超立方体 ,它的升级也伴随着顶点个数的增加而成倍增加 .为了解决这一问题 ,一种称为超级交叉立方体 (SCC)的互连网络被提了出来 .有关文献已证明 ,SCC很好地保持了交叉立方体在顶点度数 ,直径和连通度方面的优越性质 ,而且其升级可以增加任意多个顶点 .用图嵌入技术讨论了 SCC模拟环网络的能力 ,证明了长度为 4到 N的任一圈都能以扩张 1嵌入具有 N个顶点的 SCC,从而证明了 SCC模拟环网络的能力与交叉立方体完全相同 .

关于加强超立方体互连网络的可诊断性的另一种证明方法

ｎ维加强超立方体是具有２ｎ个顶点，（ｎ＋１）２ｎ－１条边的（ｎ＋１）－正则图，它是通过对ｎ维超立方体增加２ｎ－１条边得到的．在［１］中证明了基于ＰＭＣ模型的ｎ维加强超立方体在精确诊断策略下是（ｎ＋１）－可诊断的，在悲观诊断策略下是（２ｎ）／（２ｎ）－可诊断的，但其证明很繁琐．本文利用［１０，３］中的结果，给出了加强超立方体可诊断性的另一个更为简洁的证明。

在细胞图自动机上寻找图的基本回路

将细胞自动结构推广到任意图结构，并用它解决图论中的问题，是细胞自动机理论在图论领域中的一个应用．

交叉立方体圈嵌入的一个新算法(英文)

交叉立方体互联网络有不少独特的性质。已经证明当3n时n维交叉立方体nD是Hamilton连通的,一个将长度)24(,nll的圈以扩张1嵌入nD的)log(llO算法。本文利用交叉立方体的Hamilton连通性给出了一个将长度nll24,的圈以扩张1嵌入nD的新的算法也被给出,其时间复杂度为)(lO。

互连网络诊断性与容错性的细胞图自动机算法的串行模拟

本文对作者以前提出的细胞图自动机算法，给出了串行模拟结果，特别地给出了这些串行模拟程序对几种重要的互连网络如超立方体，交叉立体和Ｍｏｂｉｕｓ立方体模拟的一些具体结果及效率分析．

细胞有向图自动机及算法

本文提出了细胞(d_1,d_2)-有向图自动机的定义,研究了怎样用它求得(d_1,d_2)-有向图的广度优先混合方向支撑树,单向树及强连通分量等问题并给出了相应的并行算法和时间复杂度分析.

最小T－2倍树的构造算法

本文提出了对任意一棵树的顶点赋权使其满足一定约束条件的最小Ｔ－２倍树的定义。

细胞（d1，d2）－有向图语言类在集合论运算下的封闭性

本文给出了细胞（ｄ１，ｄ２）－有向图自动机类的定义及其接受的语言（判断）类的定义，并讨论了该语言（判断）类在并、交。

基于ZigBee无线传感器网络的智能交通系统设计

针对交通系统中移动的流量监测和查询应用,提出了一种基于ZigBee标准的无线传感器网络智能交通系统设计,以提供一个弹性和高效的无线参考解决方案。给出的体系结构考虑节点的异构性,将系统中的节点分为MS、VS和SN 3种不同角色。设计中给出了包括初始化过程的详细路由算法。为了加快信息的响应速度,设计了一种基于预测的路由转发机制。VS节点接收来自SN的数据,基于MS的移动性信息计算MS位置并确定路由。此外,VS缓存请求数据机制进一步优化了结果。实验表明与现存同类方法相比,所提方案能有效加快数据获取速度,在延迟方面具有显著提升。

基于Voronoi图的无线传感器网络K覆盖算法

针对无线传感器网络(WSN)在随机高密度部署节点情况下的多重覆盖问题,提出一个基于Voronoi图的K覆盖算法。该算法利用邻居节点信息计算Voronoi覆盖邻居节点集,构建有向Voronoi覆盖关系图,通过调整关系图中的节点状态实现K覆盖。仿真结果表明,该算法能正确判断网络覆盖率,连通K覆盖的近似最小活动节点集数目少于CCP算法。

基于融合树的事件区域检测容错算法

针对无线传感器网络的事件区域检测问题,提出了一种基于融合树的事件区域检测容错算法。该算法首先构建分布式融合树,每个节点报告自己的感知数据到最邻近的树节点,树节点执行多元线性回归,对单个或多个同时发生的事件进行检测,获得事件区域检测的估计值,同时融合冗余信息,降低数据传输量。仿真结果表明,该算法具有较高的检测精度,可改善发生在事件区域边界节点的检测质量。