Skeleton-based parallel programming is recently attracting much attention as a framework for expressing data-parallelism in functional languages. It allows efficient and portable parallel programming by encouraging programmers to build programs using ready-made parallel skeletons for which efficient implementations are known to exist. In spite of these good points, parallel programming is still difficult. In functional languages, iterative computations on data collections are usually expressed using recursive functions on recursive data structures. Extracting computations that have appropriate data-parallelism from such specifications and integrating them into efficient parallel programs are not strainghtforward. In this thesis, we present an analytical method to transform recursive functions on general recursive data structures into data-parallel programs based on parallel skeletons.
Firstly, we present a formal classification of computations in recursive functions on general recursive data structures on the basis of their data-parallelism. For the definition and analysisi of the classification, we define the static slice of using abstract interpretation. Then, we present a method to automatically generate data-parallel programs from the classified computations of input programs.
Compared with the previous parallelization methods based on program calculation, our approach is more practical in the following aspects. Because our method is based on a data-flow analysis, it can deal with recursive functions with complex data-flow which commonly occurs from let bindings and assignments to tuple patterns in practical functional programs. In addition, our method can effectively parallelize recursive functions on general recursive data structures such as trees. By adapting parallel skeletons which do not require the associativity of argument functions, our parallelization method does not deal with the associativity of computations; this makes our method easier to implement than the calculational methods.
We have implemented a parallelizing translator which can transform call-by-value functional programs into data-parallel programs based on parallel skeletons. Our parallelizing translator can parallelize functions of practical programs such as the in-order numbering program and the parallelizing translator itseld.
자료 병렬 수행 구조(data-parallel skeleton)를 사용한 병렬 프로그래밍은 함수형 언어에서 자료 병렬성으 ㄹ표현하기 위한 대표적인 방법이다. 자료 병렬 수행 구조란 병렬 프로세서에 분산되는 자료형들에 대하여 적용되는 일반적인 병렬 계산들의 공통적인 형태들을 고차 함수의 형태로 정의해 놓은 것을 말한다. 이에 기반한 병렬 함수혀여 언어들은, 다양한 병렬 컴퓨터에 효과적인 구현이 가능한 병렬 수행 구조를 프로그래머들에게 제공하므로써, 효율적이고 이식성이 좋은 병렬 프로그램이 생성되도록 하는 장점을 가진다.
함수형 언어에서 자료 집합에 대한 반복적인 계산은 일반적으로 재귀적인 구조를 가지는 자료 구조에 대한 재귀함수에 의하여 표현된다. 따라서 순차적인 정의로부터 자료 병렬 프로그램을 작성하기 위해서는, 재귀 함수에서 병렬 수행 구조로 수행이 가능한 부분들을 파악하고 이를 적절한 자료 병렬 수행 구조들이 조합으로 표현하는 쉽지 않은 작업을 수행하여야만 한다. 이에 대하여, 본 연구에서는 재귀적 자료 집합에 대한 재귀 함수로부터 자료 병렬 수행 구조를 사용하는 병렬 프로그램을 자동으로 생성하는 방법을 제시하였다.
먼저, 일반적인 재귀적 자료 구조에 대한 재귀 함수로부터 자료 병렬성을 추출하는 방법을 제시한다. 즉, 재귀 함수 내의 모든 계산들을 자료 병렬 수행을 위한 조건들에 의하여 분류하는 방법을 정의하였으며, 이러한 분류에 필요한 자료 흐름의 분석을 위하여, 입력 언어의 정적 분할을 정형적으로 정의하고 추상 해석 방법론에 기반한 정적 분할의 분석 방법을 제시하였다. 그리고, 병렬 수행의 조건에 의하여 분류된 재귀 함수내의 계산들을 적절한 자료 병렬 수행 구조를 위한 인자 함수로 변환하므로써 병렬 프로그램을 생성하는 방법을 제시하였다.
본 연구에서 제시된 병렬화 방법은 기존의 프로그램 변환 규칙(program calculation)에 기반한 병렬화 방법과 비교하여 다음과 같은 장점을 갖는다. 자료 흐름의 분석에 기반한 병렬화 방법은 let문이나 튜플 패턴(tuple pattern)에 대한 지정문에 의하여 발생하는 복잡한 자료 흐름을 가지는 실제적인 함수들에 효과적으로 적용될 수 있다. 그리고, 목적 프로그램의 병렬 수행 구조를 재귀적 자료형의 구조에 대응하여 적절하게 동작하도록 다형적으로 정의하고, 병렬성의 분석과 병렬 프로그램 생성을 일반적인 재귀적 자료형에 대하여 동작하도록 정의하므로써, 일반적인 재귀적 자료 구조에 대한 재귀 함수의 병렬화가 가능하도록 하였다. 또한, 프로그램 변환 규칙에 대한 병렬화 방법들은 변환 규칙을 적용하기 위해 결합 법칙을 만족하는(associative) 적절한 인자 함수를 찾는 어려운 작업을 수행해야 하는데 비해, 본 연구의 방법은 이러한 작업을 필요로 하지 않으므로 구현이 용이하다.
본 연구에서는, 제시된 병렬화 방법에 기반하여 일차 함수형 언어에 대한 병렬화 변환기를 구현하였으며, 구현된 변화기가 실제적인 프로그램들에 대하여 적용 가능함을 보였다.