DEADLOCK-FREE SCHEDULING METHOD BASED ON PETRI NET AND GA

An efficient algorithm for finding an optimal deadlock-free schedule in amanufacturing system with very limited buffer is presented. This algorithm is based on the effectivegenetic algorithm (GA) search method, and a formal Petri net structure is introduced to detect thetoken player assuring deadlock-free. In order to make the scheduling strategy generated by GA meetthe required constraint of deadlock-free, Petri net is involved to make the implementation of thejob scheduling in an FMS deadlock-free. The effectiveness and efficiency of the proposed approach isillustrated by using an example.

面向对象范型体系结构中构件行为相容性研究

软件体系结构(SA)为基于构件的软件开发提供了一种高层次的抽象.如何有效描述体系结构中构件的对外交互行为、验证组装构件间的行为相容及保证整个体系结构行为无死锁是其中较为重要的研究内容.在基于面向对象范型这类重要的软件体系结构中,构件组装通常是通过接口方法调用加以实现.针对这样一类基于软件体系结构的构件组装问题,形式描述与定义了构件及其对外交互协议,分析了服务请求构件与服务提供构件所能展示的不同行为,给出了组装交互的构件在请求/提供接口上协议级行为相容的一组验证规则及相关定理.最后,通过一个电子商务应用实例来说明所提出途径的可用性和针对性.

一种基于局部扭曲立方体的无死锁路由算法

局部扭曲立方体是一种新提出来用于并行计算的互连网络.经研究发现,局部扭曲立方体中已有最小路由算法存在着死锁.针对原有算法的特点,提出了一种新的无死锁路由算法并给出了无死锁证明.利用将物理通道分成2条虚拟通道进而形成2个不相交的虚拟网络,将不同的点对之间的路由限定在某一个虚拟网络中,从而有效地避免了死锁的产生.同时,利用一个局部扭曲立方体可由2个低维子立方体和2-扭曲立方体构成这一性质,在局部的低维子立方体和2-扭曲立方体中均采用自适应路由,从而提高了算法的自适应性.

2D-Mesh结构片上网络无虚通道容错路由算法

为了解决单故障节点情况下片上网络的无虚通道容错通信问题,提出一种新的片上网络容错路由算法.该算法在已有算法绕行思想的基础上,首先利用内建自测试机制获取故障节点的位置信息,再通过辅助节点来优化数据的绕行策略,达到了均衡故障节点周围链路负载并减少部分数据的绕行距离的目的.针对8×8 2D-Mesh网络的仿真结果表明,与Zhangs算法和Chens算法相比,采用本文算法后网络的饱和注入率分别提高了3.13%和21.77%,在注入率为0.09时网络的通信功耗分别降低了3.40%和5.57%.

基于路径的无死锁NoC多播路由器的设计

针对NoC中并行处理事务的增多,将计算机网络中的多播传输模式引入到NoC路由器的设计中来,提出了一种新颖的基于路径的多播路由器设计模式.采用数据包中带有多个目的地址及数据子包的模式,实现了数据包到多个目的节点的高效传输,同时,通过引入Hamiltonian路径的无死锁处理模式,避免了数据包传输过程中死锁的发生.采用Verilog HDL实现了该模型的RTL级设计,并用Synopsys EDA软件完成功能仿真、时序验证及综合.

基于PRDT的16节点NoC路由算法

网络结构对于片上网络系统的性能和功耗发挥着重要作用,PRDT(2,1)有着较低的网络直径和平均距离、常数的节点度以及良好的可扩展性,这些特点使其非常适于NoC。为了提高小规模PRDT的路由性能,该文提出了一种binary路由算法,当网络规模不大于16时,该算法无须使用虚拟通道即可实现无死锁路由,通过增加少量虚拟通道,可改进为完全自适应路由算法。对所提出的路由算法与原有的向量路由算法进行仿真比较,结果显示binary算法在硬件成本较低的同时,性能更为优异,完全可以应用于基于PRDT的小规模NoC网络。

Mesh网络耐故障虫孔路由

耐故障是互连网络设计中的一个重要问题。本文提出了一种新的耐故障路由算法,并将其应用于使用虫孔交换技术的Mesh网络。由于使用了较低的路由限制,这一算法具有很强的自适应性,可以在各种不同故障域的Mesh网络中保持路由的连通性和无死锁性;由于使用了最小限度的虚拟通道,这一算法所需的缓冲器资源很少,非常适宜构建低成本的耐故障互连网络;由于根据本地故障信息进行绕行故障节点的决策,这一算法的路由决策速度较快并且易于在互连网络中实现。最后网络仿真试验显示,这一算法具有良好的平滑降级使用的性能。

共享竞争择一资源Petri网的形式化设计方法

自动制造系统中有许多共享资源,例如,机器人、数控加工中心、无人导引自动小车等,竞争择一是其共享方式之一,以往,自动制造系统的Petri网控制器设计几乎都是试凑,而且一些性质不能得到满足,如无死锁,这主要是对共享资源的不适当设计造成的,对于多个子系统,为了使之能很好地工作,必须研究一种设计有界、无死锁的Petri网控制器的方法,本文在以往工作的基础上,提出了有界、无死锁、安全Petri网控制器设计的形式化方法,它也适用于Petri网的自动建模。

光刻设备TRACK系统的无死锁调度算法

为使半导体生产线光刻设备的TRACK系统正常运行,有效地避免死锁,提高设备利用率,提出了一种无死锁调度算法,在不会引发死锁的条件下为需要调度的工件确定加工组件,同时考虑到组件发生故障的情况,及时排除故障的影响,并通过仿真证明了算法的有效性。

一种高效全自适应路由算法的构造框架

路由算法在大规模并行处理机 (MPP)系统中对互连网络通信性能和系统性能的发挥起着关键作用 .深入分析消息在网络中寻径特性 ,提出“最佳寻径网 (BNR)”概念 ,根据 BNR构造全自适应路由算法设计框架 ,并给出一类 Mesh网络基于 BNR的全自适应路由算法 BBFAM的设计 .性能分析表明 ,BBFAM是一类高效全自适应路由算法 ,从而证明 BNR构造框架对网络设计人员确能提供有效的路由算法设计指导 .

一种运用图论进行FMS无死锁调度的方法

在制造系统中 ,必须防止死锁的发生。本文提出一种在制造系统 (带有限缓冲区 )中搜索最优的无死锁调度算法。此算法建立在遗传算法的基础上 ,运用图论算法来保证无死锁调度结果。为了保证遗传算法生成的调度策略能够满足所要求的约束 ,运用图论方法选择无死锁个体 ,添加缓冲区 ,从而在保证了系统的主要性能指标的同时 ,得到系统可行的无死锁的调度结果。本文的主要创新之处在于提出了一种考虑系统缓冲区的无死锁调度方法。

Torus网络自适应容错路由算法

在应用于大规模并行计算机的互连网络的设计中,容错问题是其中的一个关键问题和难点问题。提出了一种基于Torus虫孔交换网络的容错路由算法,这一算法使用了矩形故障模型,无论故障区域大小多少和如何分布,算法始终是无死锁的,而且具有足够的自适应性,只要故障节点没有断开网络的连接,算法就能够通过选路使消息绕过故障区域,保持路由的连通性。同时,算法仅需要使用3个额外的虚拟通道。最后算法在不同故障率的Torus网络中进行了仿真实验,结果显示这一算法具有良好的平滑降级使用的特性。

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

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

带有部分可观察的无死锁模监控

讨论了带有部分可观察的无死锁模监控的综合问题.通过用可辨识语言来代替可观察语言引入无死锁的,可控闭语言中,利用一对监控器间的d 不变关系,得到带有部分可观察的无死锁模监控的充分必要条件是两个子监控器满足d 不变关系.最后,又给出了带有部分可观察无死锁模监控的综合过程.

基于不规则Mesh的NoC无死锁路由

网络拓扑的选择是NoC设计中的一个重要问题,目前典型的特定应用NoC系统通常集成多个不同功能、不同尺寸、不同通讯需求的组件,而规则的网络拓扑结构并不适于在这种类型的NoC中应用,因此不规则Mesh网络被提出并被应用于不规则结构的NoC系统.为解决规则Mesh路由算法在不规则Mesh中无法保证路由连通性的问题,本文提出一种不规则Mesh无死锁路由算法,无论NoC系统集成组件的版图如何变化,这一算法始终是连通的,即算法与不规则Mesh的规模和结构是无关的,同时算法仅使用较低的虚拟通道.

一种新型缓冲结构——支持无死锁的完全自适应路由

介绍了一种适用于虫孔切换网络的多请求输入缓冲区组织的新型缓冲区结构.该结构支持Duato方法在报文穿插存储情况下实现无死锁的完全自适应路由.同时,基于BookSim模拟平台,对多请求输入缓冲区结构的性能进行评价.结果表明,新型多请求输入缓冲区结构的性能优于先进先出(FIFO)缓冲结构,其在uniform通信模式下的报文延迟降幅近68%.

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

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

针对片上网络组播通信模型的设计与仿真

文章提出了一种针对片上网络的组播通信模型,能够为片上网络提供无死锁的通信。该模型能显著减少总通信量,增加通道利用率;在测试模式下,能有效节省测试时间。将该模型仿真应用到二维带环网格拓扑结构的片上网络中,试验结果表明,该模型较单播通信具有更小的平均传输延迟和更高的吞吐量。

基于FPGA的2D-Torus片上网络无死锁路由算法

片上网络的拓扑结构和路由算法直接影响片上网络的传输延迟和传输效率.基于2D-Torus拓扑结构,提出了一种新的片上网络无死锁路由算法.通过改变数据包在片上网络路由过程中受限制转弯的位置,保证片上网络的自适应路由条件,从而有效降低片上网络的延迟.在FPGA硬件平台上,设计并实现了基于该路由算法的2D-Torus片上网络,并对其进行测试.实验结果表明,基于该路由算法的片上网络,可以满足片上网络多方向数据通信及多路数据并行通信等性能要求.

在半适应多孔网状网络系统中解除死锁的多址发送机制

描述在多孔网状网络上解除多址发送中死锁问题的一种方法．这种方法将多址发送的目标组织成一棵分配树，树的分枝由一些消息链接而成，这些消息能够按照半适应回转路由选择策略沿着不会造成死锁的路线传送．树的每一分枝不是同时创建的，并且独立地进行多孔路由选择．这种技术具有较少的处理开销和较短的通信延迟时间，且在使用信道资源方面更加有效．与以前采用的多址发送机制相比，它提高了信道的使用效率且减少了信道的竞争概率．这种技术也适用于带有修改消息链策略的其它路由选择方案．