蜂窝网络上的路由算法*

主要研究蜂窝网络上的无死锁单播路由算法和一对全的广播路由算法。基于蜂窝网络的砖形画法,利用二维网络维序路由的基本思想和两个虚拟网络实现了无死锁的最短单播路由算法,并证明了算法的无死锁性。然后基于这个单播路由算法和线列上的广播算法,用软件实现了蜂窝网络上一对全的广播路由算法,经过简单比较得出该广播算法比以往的算法在通信效率上有了极大的提高。     

Experience with Applying Formal Methods to Protocol Specification and System Architecture

In the last three years or so we at Enterprise Platforms Group at Intel Corporation have been applying formal methods to various problems that arose during the process of defining platform architectures for Intel's processor families. In this paper we give an overview of some of the problems we have worked on, the results we have obtained, and the lessons we have learned. The last topic is addressed mainly from the perspective of platform architects.     

PRDT（2，1）架构的NoC系统容错路由算法

链路和节点的故障会导致网络中许多节点无法相互通讯,因此容错性是NoC系统设计中的一个重要问题。基于一种新的NoC网络拓扑结构PRDT（2,1）,提出一种PRDT（2,1）容错路由算法以及相应的节点失效算法。节点失效算法通过使较少数量的无故障节点失效来构造矩形故障区域,PRDT（2,1）容错路由算法仅使用了最小数量的虚拟通道并提供足够的自适应性以实现无死锁容错路由。只要故障区域没有断开网络,这一算法能够保证路由的连通性。算法在不同故障率的PRDT（2,1）网络中仿真,结果显示这一算法具有良好的平滑降级使用特性。     

一个2D-Mesh上的完全自适应路由器设计

路由器在大规模并行处理机系统(MPP)中,对互连网络通信性能和系统性能发挥起着关键作用.本文根据所提出的完全自适应路由思想——基于通道方向的完全自适应路由,设计了一个2D-Mesh上完全自适应路由算法.进一步,采用了一种新的高速网络互连技术——源同步技术,最终设计、实现了一个高效、简洁的完全自适应路由器,并在Xilinx XACT的CAD工具上进行了模拟验证.     

井下调度运输的自动调度策略研究

为了提高煤矿井下机车调度效率和实现井下调度系统自动化,基于Petri网理论知识结合实际井下矿场路况建立机车调度Petri网模型,然后对Petri网模型添加限制库所和变迁使其调度过程无死锁,并通过理论证明了该调度模型是无死锁和冲突的,可以指导机车井下运输调度.然后在机车调度规则下针对不同的井下机车调度相关参数,提出了3种不同情况下的机车最优调度策略,并通过验证实际矿场参数后的分析证明了该调度策略下机车的调度是不触发死锁情况下的最优调度.最后通过仿真实验以及实际应用证明了该调度策略的正确性和完备性,为井下运输的自动调度提供了理论基础.     

蜂窝网格的单播路由算法

六角形蜂窝网格是一种具有良好网络拓扑性质的并行多处理机互连网络.蜂窝网格在某些特性上优于二维网格.不过,这种网络不存在单信道最短路径无死锁路由算法.文中针对该网络设计了两个部分自适应无死锁虫孔路由算法.一个是基于转弯模型单信道非最短路径路由算法,另一个则是采用了虚拟双信道的最短路径路由算法.对第二个算法,还进一步使用转弯模型对其改进.通过仿真实验,结果显示这两个路由算法都具有较好的性能.     

一种完全自适应片上路由器的设计

针对片上网络的死锁问题,文中根据所提出的完全自适应路由思想—基于虚拟网络的自适应路由算法,设计了一个完全自适应片上路由器.重点介绍了路由算法及路由器的系统结构,最终设计实现了一个高效、低代价的完全自适应路由器,并在2D Mesh拓扑结构下对其性能进行了模拟验证.实验得出该路由器实现了无死锁的自适应路由,并降低了平均网络延迟,提高了网络吞吐量.     

一种自适应动态缓存策略准入控制算法

针对片上网络的死锁问题,基于虚拟网络的自适应路由算法,设计了一个完全自适应片上路由器.重点介绍了路由算法及路由器的系统结构,设计实现了一个低代价、高效的完全自适应路由器,并在2DMesh拓扑结构下对其性能进行了模拟验证.实验结果表明,该路由器实现了无死锁的自适应路由,并提高了网络吞吐量,降低了平均网络延迟.     

一个高效完全自适应路由器的设计

路由器在大规模并行处理机（MPP）系统中对互连网络通信性能和系统性能的发挥起着关键作用。根据全自适应路由算法BNP设计框架,给出Mesh上一类基于BNP的全自适应路由算法BBFAM（thBNR-based fully adaptive algorithms on mesh);同时提出并采用动态优先级流控,“自由度”通道选择策略,设计了一个基于BNR,简洁,低代价的高效完全自适应路由器BFR（the BNR-based fully adaptive router),并采用Aletera CPLD器件构造了原型系统。     

事件反馈与状态反馈的混合模监控

在监控理论中 ,处理状态膨胀的标准方法之一是基于语言或谓词的模监控 .但文献中没有涉及同时基于语言与谓词的混合模监控 .本文研究混合模监控综合及其性质 .通过提出状态反馈与某一事件反馈的等价关系 ,给出了两者相连接的定义 ,进而得到了混合模监控器等价于子监控器与子控制器的连接 .并讨论了混合模监控器具有非阻塞性与无死锁性所满足的条件 ,即基于语言的闭环系统行为的封闭性与谓词的Σu-不变性 ,而其是无死锁的充要条件是子监控器与子控制器必须均是无死锁的并满足d-不变关系