淡江大學機構典藏:Item 987654321/95804
English  |  正體中文  |  简体中文  |  Items with full text/Total items : 64180/96952 (66%)
Visitors : 11307150      Online Users : 8368
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version


    Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/95804


    Title: 平行式程式設計、實作與效能分析：以找尋派翠網路上的永不變特性為實例 Parallel Programming Design, Implementation and Analysis： A Case Study on Finding Invariants for Petri Nets
    Authors: 陳伯榮;靳傑中;王萬福;李永裕
    Contributors: 淡江大學資訊工程學系
    Keywords: 平行程式設計;派翠網路;反應式系統;不變性;設計;效能分析;Parallel Programming;Petri Net;Reactive System;Invariant;Design;Performance Analysis
    Date: 1997-05
    Issue Date: 2014-02-13
    Abstract: 本文的主要目的即研究[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.
    Relation: 1997分散式系統技術及應用研討會論文集=Proceedings of 1997 Workshop on Distributed System Technologies & Applications，頁513-521
    Appears in Collections:[Graduate Institute & Department of Computer Science and Information Engineering] Proceeding

    Files in This Item:

    File Description SizeFormat
    平行式程式設計、實作與效能分析：以找尋派翠網路上的永不變特性為實例 _中文摘要.docx摘要20KbMicrosoft Word275View/Open
    平行式程式設計、實作與效能分析：以找尋派翠網路上的永不變特性為實例 _英文摘要.docx摘要20KbMicrosoft Word160View/Open

    All items in 機構典藏 are protected by copyright, with all rights reserved.

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - Feedback