| 摘要: | 本文的主要目的即研究[Foster 95]中的平行式程式設計方法, 它包括了分割(Partition)、通訊(Communication)、聚合(Agglomeration)以及映射(Mapping)四個階段, 並實際應用到派翠網路(Petri nets)中探討獲得P-永不變特性(P-invariants)的平行式演算法。 派翠網路是經常被用來驗證和分析反應式系統(Reactive systems)的模式。因反應式系統多為高複雜度的系統, 其相對應的派翠網路也擁有極高的複雜度, 也因此在透過派翠網路分析反應式系統的特性時, 迫切需要善用所有系統資源才能有效率的得到驗證與分析的結果。在派翠網路中常利用p-永不變特性來驗證安全性(Safety)及存活性(Liveness)等行為特性(Behavior property)。 已知的平行式獲得P-永不變特性演算法[Dan 91]仍無法突破一主要循序瓶頸。而我們克服了看似無法平行化的循序部份, 且設計完成後的平行式運算模式符合擴散式計算模式(Diffusing computation),因此可依據[Dijkstra 80]所提出的演算法來作結束測知(Termination detection), 是極好的平行式程式設計的實例。 在設計完成後, 我們除了以最快的循序演算法[Martinez 81]為比較基礎探討傳統的效率(Efficiency)及提昇(Speedup)評估外, 也作了延展性分析(Scalability analysis)以做為是否需要修正設計的參考。
[Foster 95] presents a four-step parallel program design methodology, namely partition, communication, agglomeration and mapping. The main goal of this paper is to study this design approach and apply it to obtain P- invariants in Petri Nets (PN). PN is one of the best-known model for reactive systems. But the complexity of many reactive systems are often too hard to validate and analysis. Therefore, we focus on both the theoretical and experimental studies of the new parallel program design technique to build the parallel program to speedup the validation and analysis processed. P-invariants is one of the main structural properties in PN used to analyze and validate system behavior properties such as safety and liveness. Moreover, the speedup of the best known parallel algorithm for obtaining invariants [Dan 91] is limited by a sequential component. We overcome the sequential component in the algorithm and find that the resulting parallel algorithm is a diffusing computation as [Dijkstra 80] defined. Hence, the termination detection algorithm in [Dijkstra 80] can be applied. After design phase, we analyze the efficiency and speedup using the best known sequential algorithm [Martinez 81] as the base line. Also we evaluate the scalability of the resulting parallel algorithm and find the isoefficiency function to see if we need to refine the design. |
