According as scientific, technique as well as business users need to a high-performance computing power and parallel computers are emerging to satisfy their demands, a development of an efficient parallel programming environment is required. Today, programming parallelism is still very difficult for most programmers due to the fact that existing languages were originally developed for sequential computers. Programmers are often forced to program hardware-dependent features instead of programming parallelism using high-level abstraction.
In this thesis, a new parallel programming language, COIS(concurrent iterative statements) is developed. It is a high-level, implicitly parallel language. It makes the abstract and architecture-independent parallel programming possible. The COIS is based on UNITY theory, which is proposed by Chandy and Misra. UNITY is a computational model based on unbounded iterative nondeterministic transition. Nondeterministic transition systems are natural method for specifying parallel systems. A UNITY program has one global state and transitions operating on it, possibly concurrently, it does not have an explicit notion of a process; it terminate implicitly, by reaching a fixed point state. In UNITY, statements are constructs to represent transitions. They should be executed atomically. COIS is designed with a computational model of UNITY with some modifications; addition of new sections (macro and terminate), introduction of explicit termination scheme, definition of declarations and expressions, and some changes for programming notations.
We implement a COIS-to-C translator in order to execute a COIS program on a hypercube multicomputer. The translator generates host and node programs with SPMD (single program and multiple data) style. The translator consists of two modules of front-end and back-end. The front-end module includes lexical analyzer, parser, and semantic processor. It transfers AST (abstract syntax tree) and DAL (data access list) to the back-end module. The back-end module consists of scheduler, mapping processor, and code generator. The scheduler implements atomic operation between tasks, by providing a solution for the distributed multiple resource accessing problem. Then, it generates a TIG (task interaction graph) modeling a communication pattern of tasks. This TIG is used by the mapping processor in order to assign tasks to processors of a hypercube multicomputer efficiently. An algorithm detecting a distributed termination is derived using token passing strategy.
We develop some COIS program solving the main numerical problems such as dense matrix algorithms, and spare systems of linear equations derived from partial differential equations. We verify the effectiveness of COIS by executing these programs on a hypercube multicomputer.
Consequently, we design and implement the high-level parallel programming language COIS, such that a programmer need not consider explicit partitioning or mapping in programming parallelism. It will be a useful tool for practical as well as experimental parallel programming.
과학 기술 분야 및 상업 분야에서 고속의 계산 능력을 갖는 컴퓨터에 대한 필요성이 증가하고, 이에 부응해서 병렬 컴퓨터의 이용이 증가함에 따라 효율적인 병렬 플로그래밍 환경의 개발이 요구되고 있다. 현재, 병렬 컴퓨터를 프로그래밍하는 것은 아직 대부분의 프로그래머들에게는 어려운 작업으로 남아 있는데 이는 기존의 프로그래밍 언어들이 대개 순차 컴퓨터에 적합하도록 개발되었기 때문이다. 특히 프로그래머들은 고급의 추상화 개념을 사용해서 병렬 프로그래밍을 하기 보다는 하드웨어 의존적인 프로그램을 하도록 강요받는다.
본 논문에서는 이러한 문제점을 해결하기 위하여 새로운 병렬 프로그래밍 언어인 COIS(concurrent iterative statements)를 개발한다. 이 언어는 묵시적 병렬성을 기술할 수 있는 고급 언어로서, 추상화되고 하드웨어 독립적인 병렬 프로그래밍을 가능하게 한다. 이 언어는 Chandy와 Misra에 의해 제안된 UNITY이론에 기초를 두고 있다. UNITY란 말은 무제한적이고 반복적인 비결정적 전이에 바탕을 둔 계산 모델을 의미한다. 비결정적 전이 시스템은 병렬성을 표현하기 위한 자연스러운 방법이 될 수 있다. UNITY 프로그램은 하나의 전역 상태를 갖게 되며, 그에 대해 동시에 실행할 수 있는 여러개의 전이들로 이루어진다. 그래서 여기에는 프로세스의 명확한 개념이 없게 되며, 정점 상태에 도달되었을때 묵시적으로 프로그램이 종료되는 규칙이 적용된다. UNITY에서 전이를 표현하는 수단은 프로그램 문장들이며, 이러한 문장들은 원자성을 갖고 실행되어야 한다. COIS는 몇가지 수정을 통하여 UNITY의 계산 모델에 바탕을 두고 설계되었다: macro 및 terminate 섹션의 새로운 도입, 명시적 종료 방법의 도입, 선언 및 수식 구문의 정의, 프로그래밍 기호에 대한 변경 등.
이러한 COIS-to-C 번역기가 구현된다. 이 번역기는 SPMD(single program, multiple data) 형식의 호스트와 노드 프로그램을 생성한다. 번역기의 구성은 크게 전위와 후위 모듈로 나누어 진다. 전위 모듈은 어휘 분석기와 파서 그리고 의미 분석기로 이루어 지며, AST(abstract syntax tree)와 DAL(data access list)를 생성한다. 후위 모듈은 스케쥴러와 매핑 프로세서, 코드 생성기로 구성된다. 스케쥴러는 태스크들 사이의 원자 연산을 구현하며 이를 위해 분산 환경에서의 다중 자원 접근 문제에 대안 해결책을 제공한다. 이를 통해 태스스크들 사이의 통신 형태를 모델링하는 TIG(task interaction graph)가 생성되며, 이 TIG는 하이퍼큐브 다중컴퓨터의 프로세서들에 대한 태스크들의 할당 문제를 풀기 위하여 매핑 프로세서를 전달된다. 최종적으로 분산 종료를 검출하기 위한 알고리즘은 토큰 전달 방식에 기초를 두고 구현된다.
이렇게 구현된 COIS는 편 미분방정식으로부터 유도되는 연립 선형 방정식과 행렬 계산과 같은 수치 문제들을 프로그래밍하는데 적용된다. 이 프로그램들은 실제 하이퍼큐브 다중 컴퓨터상에서 실행되며, 이를 통하여 COIS의 유용성을 검증하였다.
결론적으로, 본 논문을 통하여 새로운 고급 병렬 프로그래밍 언어인 COIS가 설계되고 구현되었다. 이를 사용하므로써 프로그래머들은 병렬 프로그래밍을 하는데 있어 명시적인 분할이나 매핑 같은 문제들을 고려할 필요가 없게 되었다. 이러한 병렬 언어는 병렬 프로그래밍을 위한 실험적인 도구로서뿐만 아니라 실제적인 유용한 도구로서 사용될 수 있다.
