Timed Petri net (TPN) has been widly used for the performance evaluation of a concurrent system. An approximate but highly accurate method for systematically converting a complicated TPN Into a simple net with a smaller state space is proposed in this thesis. It is based on reducible subnet and reduced reachability graph of it.
A reducible subnet (RSN) is defined as a well formed place module in the complicated TPN. Even if the TPN has cycles, the RSN may have no cycles and no coupling with others outside it. The reachability graph of a RSN is constructed and it is reduced to a simple form of a reachability graph defined as a reduced reachability graph (RRG). And from the RRG, a simple form of a TPN is deduced and defined as a reduced timed Petri net (RTN). The RSN is replaced by this resulting RTN and the same way is carried out on another RSN and so on, in the sequel, the complicated TPN can be converted into a simple TPN with a smaller state space. After this reduction, the remaining PTN with a smaller state space is used for the performance evaluation of the modeled system by a conventional technique.
The validity of the proposed method is shown by applying it to some example tasks to be run on hypercube multiprocessors, and it is used for the performance estimation of a hypercube multiprocessor designed in our laboratory.
시간 사양 Petri net(TPN)은 병렬 처리 system의 성능 추정을 위하여 널리 이용되어 왔다. 본 논문에서는 복잡한 TPN을 reducible subnet(RSN) 과 reduced reachability graph(RRG)를 이용하여 간단화하는 체계적인 방법이 제안되었다. RSN의 reachability graph를 구한후 이를 RRG로 변환하고 그에 상응하는 RTN을 원래의 TPN에 치환하는 방법을 연속하여 사용하므로써 감축된 시간 사양 Petri net를 얻는다. 이렇게 얻어진 RTN을 통상적인 TPN의 분석 방법에 의하여 system의 성능을 추정하게 된다.
본 논문에 제안된 방법의 타당성을 입증하기 위하여 hypercube 병렬 처리 계산기에서 수행되는 FFT의 성능을 추정하고 그 결과를 Caltech의 측정 결과와 비교하였다.
