Parallel computers offer a great opportunity for developing high-performance systems and solving large problems in many application areas. However, programming on parallel computers is more comples than sequential programming for the following reasons: 1) programmers must divide input problems. This is inevitable for achieving speedups using the parallel programming languages provided by target systems. 2) they sche dule the sub-programs into available processors to ensure that their total execution time should be minimized. 3) they make those sub-programs to execute in correct order using the communication facilities provided by target parallel systems. Due to these difficulties, many parallel programming environments have been proposed to reduce such burdens of programmers. In general, they provide high-level and user-friendly parallel languages in which parallelism is expressed in either explicitly or implicitly. However, they may have two problems. First, since most of them are based on popular sequential programming languages such as C/C++ to represent parallelism, they suffer semantic disorder in expressing parallelism in sequential semantics. Second, programmers much are aware of the architecture of a target platform to achieve good performance.
In this thesis, we propose a dual specification approach in developing parallel software. SDEVS(Software DEVS) formalism, which is proposed in this thesis and originated from the DEVS (Discrete Event System Specification) formalism, is utilized to represent the structure of software and the parallelism among software modules. The real activity of software can be specified independent of SDEVS by using one kinds of sequential imperative languages. By doing this, we can get several advantages in the sense of both programmability and reusability. First, we can specify the structure of parallel software in a hierarchical, modular manner thanks to the DEVS formalism. The hierarchical, modular structure of program enhances top down development teams, concurrent design workthroughs and programming. The modularity of the DEVS formalism is analogous to the object orientation concept, although they provides weaker modularity for the introduction of inheritance. Second, the parallelism is separated from real activity. This helps to programmers to specify parallelism of problems first not even thinking detailed activities of problems. This also make compilers more easy to analyze and automatically extract parallelism from SDEVS without much cost. Moreover, both SDEVS specification and activity functions are more likely to be reused since they independently specified.
To specify the SDEVS formalism, we proposed an experimental language notations named PSSL(Parallel Software Specification Language)> PSSL provides near one-to-one correspondent syntax as SDEVS. Once a problem has been specified with PSSL, the SDEVS translator analyzes the specification and generates various results used for input of scheduling and code generation. Total three kinds of scheduling algorithms have been proposed in this thesis. The two of them employ genetic algorithms, which is stochastic search methods, to find better solutions than traditional heuristic algorithms. The one of them is based on a naive genetic algorithm with parallelization operator. Using the new operator the search space of the genetic algorithm is considerably reduced and find 2-5% and 10-20% better scheduling result than previous heuristic algorithms and GAs. The other one is based on parallel genetic algorithm, where a global population is divided into several subpopulations (demes) and each demes evolves independently. The algorithm named OGA orders demes from the highest to the lowest deme and migrates both the best and the worst individuals at the same time. The OGA adaptively assigns different mutation probabilities to each deme to improve search capability. By doing this, 13.4% better results than other scheduling algorithms. The third scheduling algorithm named RDS (Runtime distributed scheduling) utilizes the virtual bus network that provides a global bus operation in point-to-point networks only when requests bus operations. Using the virtual bus, global information of scheduling is kept at replicated queues located on each node and maintained through a broadcasting capability on mesh. The RDS scheduling algorithm show hear equal or slightly better results than traditional heuristic static scheduling algorithms for task graphs from real examples and random task graphs.
The code generation is performed in three kinds of parallel execution environments. Firstly, PDEVSim++, which is a parallel DEVS simulation package, is used to execute SDEVS models. Activity functions are executed on the top of the package according to the state transition of the simulator. The second one is a runtime kernel execution environment. Its code generator flattens SDEVS models with zero hierarchy and attaches a very small size of simulation code to every atomic models. Generated codes are executed in small sized runtime kernel that is a small part of DEVS abstract simulation algorithm. We can also execute SDEVS models on the RDS environment. To satisfy the input requirement of the RDS, the SDEVS translator generates the state transition trajectory for SDEVS atomic models and task graph based on the trajectory information. To show the expressive power and correctness of SDEVS, some set of numerical problems are described and executed.
본 논문에서는 병렬 프로그램 기술 및 수행을 위하여 SDEVS 포말리즘을 제안하였다. 이 SDEVS 포말리즘은 DEVS (Discrete Event System Specification)에 기초하였고, 소프트웨어 구조와 병렬성을 기술하기 위하여 확장된 형태이다. 병렬 프로그램의 행위는 SDEVS와는 독립적으로 행위함수에 의해 기술된다. 이와같이 함으로써, 프로그래밍과 기존 프로그램의 재사용 측면에서 많은 이점을 얻을 수 있다. 첫재, 병렬 프로그램밍과 기존 프로그램의 재사용 측면에서 많은 이점을 얻을 수 있다. 첫째, 병렬 프로그램을 DEVS 포말리즘의 성격에 힘입어 계층적이고, 독립적으로 기술할 수 있다는 점이다. 이렇게 함으로써 하나의 프로그램을 톱다운 방식으로 나누어서 기술할 수 있고, 동시에 개발이 가능해진다. 독립적인 프로그래밍 구조는 기존의 객체지향의 방식과 많이 닮아 있고 프로그램 모듈의 재사용 기회를 늘여준다. 둘째, 병렬 프로그램의 행위와 병렬성을 분리하였다. 이렇게 함으로써 세부적인 행위를 고려하기 이전에 병렬성을 먼저 구현하고 검증할 수 있는 장점이 있다. 그리고 컴파일러 구현에 있어서도, 기존의 컴파일러는 행위와 병렬성이 결합된 상태에서 병렬성을 찾기 위해 복잡하고, 컴파일 시간이 긴 단점이 있었지만, 제안된 방식에서는 이미 분리된 병렬성을 그대로 코드 생성을 하면 되기 때문에 아주 간단하게 구현할 수 있다. 또한, 병렬성과 행위를 분리함으로써 각각 독립적으로 재 사용이 가능하다라는 장점이 있다.
이 SDEVS 포말리즘을 언어도 기술하기 위해서 PSSL (Parallel Software Description Language)이라는 언어를 제안하였고, SDEVS 포말리즘과 거의 일대일 대응된다. 병렬성과 소프트웨어 구조가 PSSL 언어로 구현되고 나면, SDEVS 트랜스레이터에 의해 스케줄링과 코드 생성에 필요한 여러가지 정보를 출력한다. 스케줄링은 모두 3가지 방식을 제안하였다. 그 중 두가지는 유전자 알고리즘에 바탕을 두고 있다. 유전자 알고리즘은 기존의 휴리스틱 알고리즘에 비해 비교적 속도는 느리지만, 더 나은 해를 찾을 수 있는 검색 알고리즘이다. 유전자 알고리즘을 사용한 첫번째 알고리즘은 스케줄링에서 좀 더 유리한 조건에서 검색하도록 고안한 병렬 연산자를 도입하였다. 또 다른 하나의 유전자 알고리즘은 병렬 유전자 알고리즘에 기초하고 있으며 기존의 병렬 유전자 알고리즘이 좋은 해만 골라 이주시키는데 반해 본 논문에서 제안하는 OGA (Ordered-deme Genetic Algorithm)는 좋은 해와 나쁜 해를 동시에 맞 교환하는 방식으로 이주 시킴으로써 좋은 해를 좋은 해끼리 더 나은 해를 찾고, 나쁜 해는 나쁜 해대로 더 광범위한 영역을 탐색할 수 있다. 마지막 방식으로서는 수행 시 분산 스케줄링 방식 RDS (Runtime Distributed Scheduling)이 있다. 이 방식은 기본적인 가정으로 하부 통신 구조에서 방송기능을 탑재하고 있다고 가정했다. 이 방송기능을 사용함으로써 각 프로세서 끼리 수행시간에 서로 정보를 공유하고, 작업을 분산 스케줄링 함으로서 컴파일러의 도움을 최소화하면서 성능은 거의 정적 스케줄링에 필적하는 성능을 보여줄 수 있다.
코드 생성도 세가지의 방식의 수행 환경에 따라 각각 실행된다. 먼저 PDEVSim++ 패키지 상에서의 수행을 위한 코드를 생성한다. 이 패키지는 DEVS 모델들을 분산 환경에서 수행하기 때문에, 시뮬레이션과 동시에 코드를 수행하는 형태로 병렬 수행된다. 따라서 비교적 수행시 부담이 있지만, 가장 유연한 형태의 기술방식을 제공한다. 둘째, 아주 작은 수행 커널을 위한 코드 생성이다. 이 방식에서는 DEVS 시뮬레이션 알고리즘을 축약한 형태의 커널을 바탕으로 PDEVSim++ 보다는 수행시간 부담을 줄이면서도 유연한 프로그래밍 환경을 제공한다. 세째 방식은 RDS 커널 상에서 병렬 수행을 위한 코드 생성으로써 PSSL에서 부터 SDEVS모델들의 상태 전환에 대한 정보를 추출한 후 이를 바탕으로 태스크 그래프를 작성하고 이를 RDS 커널의 입력으로 보냄으로써 병렬 수행하는 방식이다.
전체 병렬 프로그래밍환경의 성능을 측정하기 위하여 임의 태스크 그래프, Gaussian Elimination, Finite Differemce Equation 등의 예제에 대해 태스크 그래프를 생성하고 각각의 스케줄링 알고리즘의 성능을 분석하였다. 그 결과 모든 알고리즘들에 대해 기존의 스케줄링 알고리즘들 보다는 좋은 해를 구할 수 있었고, 이를 사용한 병렬 프로그래밍 환경은 보다 높은 차원에서 병렬성을 기술할 수 있으면서, 성능은 기존 환경보다 뛰어난 병렬 프로그래밍 환경을 구축할 수 있다.
