星形图上无死锁的路径算法

星形图具有许多良好的拓扑性质，是一种有可能替代传统的超立方体的并行计算互联网络的模型。在本文中，作者针对在星形图这样一种高度规则的网络中，可能产生死锁的问题，对星形图上无死锁的路径算法进行了研究。首先利用星形图中匹配基的性质，给出了从Ｓｎ（Ｂ）到Ｓｋ的正规映射的定义，然后提出了星形图上的两个无死锁受限条件，最后证明了一个满足无死锁受限条件的路径算法。作者还提出了星形图上路径算法的最小无死锁受限条件     

超立方体上基于缓冲机制的无死锁路径算法

本文研究了超立方体上基于单缓冲和双缓冲技术的无死锁受限条件，提出了相应的无死锁路径算法．性能分析表明，路径算法的效率和算法的自适应能力及算法的复杂性相关．     

超立方体上路径算法的无死锁性

本文对超立方体上路径算法的无死锁性问题进行了研究，提出了超立方体上的两类最小无死锁受限条件，证明了路径算法的无死锁和对称性两者之间关系。     

离散事件系统的无死锁模块化状态反馈控制

本文讨论离散事件系统的无死锁模块化状态反馈问题。首先我们定义自动机的交与并运算，然后通过引入自动机对的Ｄ－不变关系，我们证明当控制目标是两个谓词的交时，模块化状态反馈控制器是无死锁的充要条件是各子控制器是无死锁的且相应的控制器满足Ｄ－不变关系。我们证明了一个给定的自动机对于另一自动机的Ｄ－不变子自动机类有最大元存大，并由此给出一个综合算法。     

柔性制造系统的改进粒子群无死锁调度算法

基于柔性制造系统的Petri网模型,以制造期最小为优化目标,将死锁避免策略嵌入粒子群算法中,提出一种无死锁改进粒子群调度算法.该算法将粒子与工件的工序序列相对应,以位置数值的大小表示对应工件工序在执行顺序中的优先级.采用一步向前看的死锁避免策略方法对序列的可行性进行验证,提出一种跳出局部极值的策略.实例仿真结果表明了粒子群调度算法的可行性和有效性,以及改进粒子群调度算法的优越性.     

OpenMP Fortran程序中死锁的静态检测

与BARRIER相关的死锁是导致OpenMP程序失效的重要隐患之一.对该类隐患的静态检测有助于在OpenMP程序运行之前提高其正确性.为了便于检测,将这种死锁分为两类.借助搜索与数据流分析分别按照存在性规则和非一致性规则检测第1类和第2类死锁.扩展了传统的控制流图以表示OpenMP程序.对于每个检测到的死锁,通过回溯记录控制流图中相关的路径,并利用静态分支预测量化其严重程度.基于上述思想,实现了一个OpenMP Fortran程序中死锁的静态检测工具C-Checker.实验表明,该工具能有效地检测OpenMP程序中与BARRIER相关的死锁.     

基于资源等待图的死锁检测算法

死锁是操作系统、数据库系统以及通信网络中经常出现的现象.分析了使用资源分配图和进程等待图完成死锁检测的不足,提出了资源等待图的概念,并给出了基于资源等待图进行死锁检测的方法,该算法能够完成当资源类含有多个实例时的死锁检测.     

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

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

基于Petri网的柔性制造系统无死锁遗传调度算法

对以最小化加工时间为目标的柔性制造系统无死锁调度问题, 提出了一种遗传调度算法. 算法考虑到同类工件具有预先确定的相同加工路径, 而各工序的处理时间与工件有关. 用Petri网对工序和资源分配进行逻辑建模,利用遗传算法, 采用工序自然编码方式, 基于系统的最佳避免死锁Petri网控制器, 检测染色体的可行性, 修复不可行染色体使其对应的调度满足资源约束和无死锁控制约束, 从而保证算法所利用的所有染色体都对应系统的可行调度. 仿真结果表明了算法的可行性和有效性.     

基于动态滑模的无死锁时间管理算法

基于新一代仿真体系结构HLA的IEEE1516新标准中的最大有效逻辑时间关键值,讨论最大有效逻辑时间在HLA时间管理中的重要意义,分析其在常规时间推进算法中的实现及死锁的产生,研究并证明HLA时间推进中的4个产生死锁的充分条件,即互斥条件、请求保持条件、不剥夺条件和环路等待条件,提出动态滑模的概念,设计了基于动态滑模的无死锁时间管理算法,对Lookahead的合理设置进行了分析。     

Deadlock-free adaptive routing in multicomputer networks usingvirtual channels

The use of adaptive routing in a multicomputer interconnection network improves network performance by using all available paths and provides fault tolerance by allowing messages to be routed around failed channels and nodes. Two deadlock-free adaptive routing algorithms are described. Both algorithms allocate virtual channels using a count of the number of dimension reversals a packet has performed to eliminate cycles in resource dependency graphs. The static algorithm eliminates cycles in the network channel dependency graph. The dynamic algorithm improves virtual channel utilization by permitting dependency cycles and instead eliminating cycles in the packet wait-for graph. It is proved that these algorithms are deadlock-free. Experimental measurements of their performance are presented     

Optimal Fully Adaptive Minimal Wormhole Routing for Meshes

A deadlock-free fully adaptive minimal routing algorithm for meshes that is optimal in the number of virtual channels required and in the number of restrictions placed on the use of these virtual channels is presented. It is also proved that, ignoring symmetry, this routing algorithm is the only fully adaptive routing algorithm with uniform routers that achieves both of these goals. This new algorithm requires only 4n-2 virtual channels for an n-dimensional mesh. In addition, if more than the minimum number of virtual channels is available, the routing algorithm can use these additional channels with the fewest possible number of restrictions. The proofs are first presented for the 2D mesh and then generalized to n-dimensional meshes.     

蜂窝网络上的路由算法*

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

考虑缓冲区的自动生产单元的无死锁调度策略

在制造系统中,必须防止死锁的发生.本文提出了一种在制造系统(带有有限缓冲区)中搜索最优的无死锁调度的算法.为此首先介绍了死锁问题及其图论表示方法,然后在遗传算法的基础上,运用图论算法来保证无死锁的调度结果.为了保证遗传算法生成的调度策略能够满足所要求的约束,运用图论方法选择无死锁个体,或添加缓冲区,从而在基本保证了系统的主要性能指标的同时,得到系统可行的无死锁调度结果.最后给出了一个运用此方法解决死锁问题的实例.     

Deadlock-free multicast wormhole routing in 2-D mesh multicomputers

Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms     

Mesh网络耐故障虫孔路由

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

Deadlock-free message routing in multicomputer networks

The execution of a concurrent computation by a network of processors requires a routing algorithm that is deadlock free. Many routing algorithms proposed for processor networks have the potential of deadlock due to the cyclic topology of the network. In this paper we first formalize the concept of message routing. Next, we show a method by which a deadlock-free routing algorithm can be constructed out of a given routing algorithm. Finally the method is illustrated by constructing deadlock-free routing algorithms for cartesian product processor networks. Peter A.J. Hilbers received the B.S. and M.S. degrees in mathematics, and the Ph.D. degree in computer science from Groningen University, Groningen, The Netherlands, in 1979, 1983, and 1989, respectively. From 1988 to 1989 he was an Assistant Professor with the Department of Computing Science at Groningen University. Currently he is a research engineer in the Department of Mathematics and Systems Engineering at the Koninklijke/Shell-Laboratorium, Amsterdam (Shell Research B.V.). His research intersts are program derivation and correctness, concurrency, and processor networks. Johan J. Lukkien received the B.S. and M.S. degrees in mathematics from Groningen University, Groningen, The Netherlands in 1982 and 1986 respectively. Currently he is a Ph.D. student at the Department of Computing Science, Groningen University. His research area is the construction and verification of concurrent programs.     

Multipath-Based Multicasting Strategies for Wormhole-Routed Star Graph Interconnection Networks

The star graph interconnection network has been recognized as an attractive alternative to the popular hypercube network. In this paper, we present a multipath-based multicast routing model for wormholerouted star graph networks, propose two efficient multipath routing schemes, and contrast the performance of the proposed schemes with the performance of the scheme presented in our previous work. Both of the two proposed schemes have been proven to be deadlock-free. The first scheme, simple multipath routing, uses multiple independent paths for concurrent multicasting. The second scheme, two-phase multipath routing, includes two phases: source-to-relay and relay-to-destination. For each phase, multicasting is carried out using simple multipath routing. Experimental results show that, for short and medium messages with small message startup latencies, the proposed schemes reduce multicast latency more efficiently than other schemes.