투기적 병렬 그래프 감축을 위한 대치과정이 지연된 람다 연산식 = Deferred Substitution Form of Lambda Expression for Speculative Parallel Graph Reduction

국문 초록 (Abstract)

병렬 그래프 감축 모델에 있어서, 투기적 연산(speculative evaluation) 모델은 병렬성을 증가 시키지만 불필요한 연산으로 인해 자원을 낭비할 수 있다. 투기적 태스크가 람다 연산식을 WHNF(Weak Head Normal Form)로 감축할 때, 대치과정은 그래프를 증가시킬 수 있고, 많은 복사과정을 요구할 수 있다. 이러한 투기적 태스크는 나중에 불필요한 연산이 될 수 있고, 이 경우 이러한 투기적 태스크에서 발생한 다른 모든 투기적 태스크들을 종료해야 하는 부담이 있다. 또한 불필요하게 된 복사과정으로 인한 기억 공간을 재사용이 가능한 상태로 만들어 주어야 한다.
본 논문은 WHNF 또는 HNF로 감축할 때 발생할 수 있는 불필요한 대치과정으로 인한 오버헤드를 줄이기 위해 대치과정이 지연된 람다 연산식 형태(DSF : Deferred Substitution Form)를 제안한다. 이 형태는 대치과정을 필수적 태스크(mandatory task)가 수행할 때까지 지연시키기 위한 람다 연산식 형태이다. 대치과정이 지연된 람다 연산식 형태로의 감축을 수행하는 투기적 태스크에서, 대치과정이 존재하지 않기 때문에 그래프의 크기가 증가하지 않고 또한 복사과정을 요구하지 않는다. 따라서 연산식에 대한 대치과정이 지연된 람다 연산식 형태로의 감축이 불필요하게 된 경우 부담이 줄어들게 된다. 아울러 병렬성을 증가시키기 위한 연산 모델을 제안한다.

다국어 초록 (Multilingual Abstract)

In a parallel graph reduction system, speculative evaluation can increase parallelism but waste the machine resources by evaluating expressions which may eventually be discarded. When a speculative task reduces a lambda expression to WHNF (Weak Head Normal Form), substitution can lead to unbounded growth of the graph size and requires many copy operations. This speculative task may be unnecessary. In that case the performance is affected by the overheads to terminate all tasks to be propagated from the speculative task and to refresh the memory cells to be allocated for copy operation.
We propose a lambda form called DSF(Deferred Substitution Form) in which substitution is deferred until a mandatory task will evaluate substitution. In the speculative task to DSF, since there is no substitution, it does not grow the graph and require copy operation. Therefore the overhead can be decreased when the expression reduced to DSF is eventually unnecessary. In addition, we propose an evaluation model for DSF to increase the parallelism.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 병렬 그래프 감축
• 3. 대치과정이 지연된 람다 연산식
• 4. 병렬 그래프 감축 모델
• 5. 구현 및 실험 결과
• 6. 결론
• 참고문헌
• 저자소개