Partitioning a task into modules is a necessary prerequisite to the parallel processing of the task, and also a necessary work to be done prior to solve those problems of module allocation and scheduling in multiple processors of a distributed system. The two important factors to be considered for the task partition are the amount of parallelism and the communication overhead, influencing performance of the system.
In this thesis, with Petri net as a task model, three partition schemes are presented, based on Petri net execution models under the maximum firing rule(MFR). They are called as Lock-Step Synchronization (LSS), Partial-State Branching (PSB) and Extended PSB (XPSB). The schemes focus their attention on the following two subjects which are inevitable for executing the task in the multiprocessor system: 1) how the task can be executed with maximally possible parallelism and 2) how the modules of the task can be grouped in order to have lowest possible communication overhead with maintaining the parallelism. The maximal parallelism is exploited and maintained by applying MFR to the execution of Petri nets. However, due to the distinction of the module grouping strategies resulting from their execution models, the granularity of a module running on a processor is different from each other. Thus, the communication overhead for each partition is different. We compare the three partitions with respect to two partition overheads, defined as the synchronization overhead and the message traffic. A task partition is represented by an intermodule synchronization graph (ISG), and the partition overheads are obtained from the corresponding ISG. The overheads can be reduced by increasing the asynchronous activity or local processing activity during the task partition for parallel processing. Consequently, we show that among three partition schemes, XPSB execution model partitions a task in a manner that allows maximal parallelism with lowest partition overheads. Their parallel behavior including module precedence relation is represented by a labeled directed graph called in AND/OR reachability graph which is generated by using four branching rules.
In real-time environment if the response time of a task is constrained by a specified time, analyzing its response time is a necessary prerequisite to the execution of the task for minimizing the undesirable outcomes during the execution. This thesis presents another partition scheme which can be applied to the response time analysis for the task modeled in a timed Petri net. The conventional timed Petri net is extended to have a mechanism for decision making of specifing the next state probability. We show that a combination of the partition scheme and the reachability analysis simplifies an original (complex) timed Petri net and reduces the state space required for the analysis. By adding a selection function to the conventional definition of timed Petri net execution, the repsonse time analysis can also be carried out without obtaining the corresponding timed reachability graph (TRG). We use a simulation technique, known as Monte-Carlo, as the selection function.
일 분할(task partition)은 다중 프로세서상에서 그 일의 병렬처리(예를 들면 일의 할당 및 계획)를 위해서 반드시 실행되어야 할 선행과제이다. 일 분할시 고려되어야 할 중요한 2가지 요소들은 병렬일의 양(amount of parallelism)과 그들 사이의 통신 오버헤드(communication overhead)이다. 이것들은 시스템의 성능에 막대한 영향을 끼치는데 왜냐하면 일반적으로 고성능을 위해 최대의 병렬성(maximal parallelism)을 추구하지만 그에 따라 통신 오버헤드 또한 큰폭으로 증가하기 때문이다. 그러므로 이 두가지 요소들은 일 분할시 가장 효율적으로 다루어져야 한다. 그러나 기존의 접근 방식들에서는 일 흐름 그래프(task flow graph)를 사용하여 병렬일의 양은 고정된다고 가정하므로 통신 오버헤드만을 최소화시키는데 중점을 두어왔다.
본 논문에서는 패트리망(petri net)을 일의 모델로 하여 그 수행 모델에 기초를 둔 3가지 일 분할 방법들, Lock-Step Synchronization(LSS), Partial-State Branching(PSB)과 Extended PSB(XPSB)들을 제시하였다. 이들이 기존의 방식에 비해 우수한 점들은, 기존의 방식들이 병렬일의 양을도외시 하였으나, 제안된 방식들은 모두 패트리망을 최다 수행 규칙(Maximum Firing Rule)에 의해 수행시킴으로써 다중 프로세서상에서 최대의 병렬성을 가지도록 일을 분할한다는 것이고, 또한 패트리망 수행모델에 근거를 두고 있기 때문에 그 분할이 용이하여 다중프로세서상에서 쉽게 응용할 수 있으며 그리고 통신 오버헤드가 분석적으로 도출될 수 있다는 것이다. 본 논문에서는 통신 오버헤드를 동기 오버헤드(synchronization overhead)와 메시지 트래픽(message traffic)으로 구분하여 각 분할방법에 대해 분석 하였으며 그 결과 XPSB 수행 모델에 따라 일을 분할하는 것이 가장 오버헤드가 작게 됨을 보여 주었다. 그러나 각 분할 방법에 대한 전체 수행 시간의 분석은 그 응용에 따라 또 그 일을 구성하고 있는 일 단위(activity)의 수행시간에 따라 다르게 나타나므로 이론적으로 분석될 수 없기 때문에 일반적으로 각 응용에 따라 시뮬레이션에 의해 추정하고 있다. 그러므로 본 논문은 전체일의 수행 시간을 각 일 단위의 수행 시간이 두가지의 분포함수 즉 uniform distribution과 Gaussian distribution을 하고 있을 경우를 가정하여 Monte-Carlo 방법을 사용하여 추정하고 있다. 그 결과는 XPSB 수행 모델에 따른 일 분할 이 수행시간 측면에서 대체로 우수하다는 사실을 보여주고 있다. XPSB 방식이 다른 방식에 비해 통신 오버헤드 측면에서는 30%이상의 감소를 보여 주었으며, 수행시간 측면에서도 특별한 경우를 제외하고는 10%이상의 감소를 보여주었다.
주어진 일이 응답시간(response time)의 제한을 받는 real-time task인 경우 응답시간을 추정하는 것은 real-time task의 설계시 반드시 실행되어야 할 선행과제인데 왜냐하면 실제 응용에서 제한 시간내에 그 일의 응답이 출력될 수 있도록 설계되어야 하기 때문이다. 본 논문에서 응답시간 제한을 받는 일의 분할 방법이 시간 사양 패트리망(timed Petri net)을 사용하여 제시되었다. 도달 그래프(reachability graph) 분석 방법에 기초를 둔 계층적 분할 정복(hierarachical divide-and-conquer) 방법을 사용하는데 작은 state space를 가지는 subnet들을 분석함으로써 전체 시스템의 분석을 용이하게 하는 장점이 있다. 이를 위해 convertible subnet(CSN) 이라는 기본 net모듈이 정의되었는데 이는 real-time task의 병렬처리를 위해 중요한 기초가 된다. 그러나 CSN의 size 및 그 발견을 위한 효율적인 알고리즘의 설계가 더 연구되어야 할 것이다.
앞으로 더 연구되어야 할 과제로서 LSS, PSB 그리고 XPSB를 각 상태에서 효율적으로 선택 사용하므로써 정적 부하 균형(static load balancing)의 연구에 응용될 수 있으리라 생각되며, 이를 위한 선택 알고리즘이 설계 구성되어야 할 것이다. 또한 제안된 세가지의 수행 모델들을 시간 사양 패트리망으로 확장시킴으로써 real-time task의 병렬처리 및 응답시간 추정에 응용될 수 있으리라 생각된다.
