This paper presents a strategy for automatically decomposing functional programs into new combinators with an optimal grain and distributing them on distributed-memory multicomputers. The program transformation technique proposed here accepts a lambda expression and generates program-derived combinators which are fine-tuned to have a right granularity for a given multiprocessor architecture. The right granularity is decided by analyzing the weight for each program-derived combinator during translation. We call a program-derived combinator at just the right level of granularity the hybrid combinator, which is composed of a fixed set of combinators suitable for spawning the parallel elements and partitioning them. The hybrid combinator provides an alternative method to the representation and synchronization of processes. This paper shows the parallel graph reduction process, where the hybrid combinators act as the controlling mechanisms by directing when and which subgraph is to be distributed.
컴비네이터를 이용한 그래프 감축으로 함수 프로그램을 수행시킬 수 있다. 이 경우 함수 프로그램에서 변수를 제거하고 제거된 변수의 위치를 컴비네이터라 불리는 연산자로 지시한다. 변수가 없는 프로그램이기 때문에 수행 시 조회 환경을 유지할 필요가 없어지며 프로그램의 수행 메카니즘이 간단해 진다.
본 논문에서는 함수 프로그램에서 병렬 처리 요소를 찾아 분할하고, 그 요소를 특정 컴퓨터 시스템에 적절한 크기로 조정할 수 있는 하이브리드 컴비네이터를 이용한 함수 프로그램의 번역과 번역된 코드의 분산 그래프 감축 기법을 제안 하였다. 이때 하이브리드 컴비네이터는 병렬 처리의 한 단위가 되며 그 내부는 제안한 한정 컴비네이터(a fixed set of combinators) 코드로 구성되어 효율적이며 기계적인 감축 기법을 사용할 수 있다. 또 하이브리드 컴비네이터는 그래프 감축 시 언제, 어떤 서브 그래프가 분산 처리될 것인가를 지시하는 제어 메카니즘으로서의 역할도 한다.
