| 한글제목(Korean Title) |
재귀적 자료구조에 대한 재귀 함수의 병렬화 |
| 영문제목(English Title) |
Parallelization of Recursive Functions for Recursive Data Structures |
| 저자(Author) |
안준선
한태숙
Joonseon Ahn
Taisook Han
|
| 원문수록처(Citation) |
VOL 26 NO. 12 PP. 1542 ~ 1552 (1999. 12) |
한글내용
(Korean Abstract) |
자료 병렬성이란 자료 집합의 원소들에 대하여 동일한 작업을 동시에 수행하므로써 얻어지는 병렬서을 말한다. 함수형 언어에서 자료 집합에 대한 반복 수행은 재귀적 자료형에 대한 재귀 함수에 의하여 표현된다. 함수형 언어에서 자료 집합에 대한 반복 수행은 재귀적 자료형에 대한 재귀 함수에 의하여 표현된다. 본 논문에서는 이러한 재귀 함수를 자료 병렬 프로그램으로 변환하기 위한 병렬화 방법을 제시한다. 생성되는 병렬 프로그램의 병렬 수행 구조로는 일반적인 형태의 재귀적 자료형에 대하여 정의되는 다형적인 자료 병렬 연산을 사용하여 트리, 리스트 등과 같은 일반적인 재귀적 자료 집합에 대한 자료 병렬 수행이 가능하도록 하엿다. 재귀 함수의 병렬화를 위해서는, 함수를 이루는 각각의 계산들의 병렬성을 재귀 호출에 의해 존재하는 의존성에 기반하여 분류하고, 이에 기반하여 각각의 계산들에 대한 적절한 자료 병렬 연산을 사요하는 병렬 프로그램을 생성하였다.
|
영문내용
(English Abstract) |
Data parallelism is obtained by applying the same operations to each element of a data collection In functional languages, iterative computations on data collections are expressed by recursions on recursive data structures. We propose a parallelization method for data-parallel implementation of such recursive functions. We employ polytypic data-parallel primitives to represent the parallel execution structure of the object programs, which enables data parallel execution with general recursive data structures, such as trees and lists. To transform sequential programs to their parallelized versions, we propose a method to classify the types of parallelism in subexpressions, based on the dependencies of the recursive cal1s, and generate the data-parallel programs using data-parallel primitives appropriately.
|
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
