병렬 결합자 그래프 감축기계의 성능평가 모델 = A Performance Evaluation Model for Parallel Combinator Graph Reduction Machine

국문 초록 (Abstract)

SK 결합자 그래프를 보다 효과적으로 구하는 그것을 병렬 감축하기 위해 제안한 병렬 그래프 감축 시스템인 PARACOM(PARAllel COMbinator graph reduction system)은 순차 그래프 감축 모델을 개선한 병렬 함수언어 처리 시스템이다. 본 논문에서는 PARACOM을 구성하는데 필요한 처리기 소자의 수와 병렬 감축횟수 및 연산횟수를 추정하기 위한 성능평가 모델을 제시하고자 한다. 성능평가 모델의 특성은 SK 결합자 그래프의 특성 즉, 각 결합자가 취하는 인자의 수, 그리고 병렬 감축 방식 등과 밀접한 관계가 있다. 제안된 성능평가 모델은 휴리스틱한 방법에 의해 마련된 바, 시뮬레이션을 통해 그 정확성을 검증하였다. 시뮬레이션 결과에 의하면 순환 함수의 경우에만 추정된 처리기 소자의 수와 차이를 보일 뿐, 그 외의 경우는 추정값과 거의 비슷한 값이 나타난다. 그러므로 자원의 수나 감축 및 연산 속도의 추정에 제안된 성능평가 모델이 효용가치가 있다는 결론을 얻을 수 있다.

다국어 초록 (Multilingual Abstract)

A parallel graph reduction system, PARACOM(PARAllel COMbinator graph reduction system), is a new functional language computational model. It improves the sequential graph reduction machine. The PARACOM can get SK combinatory graphs more effectively and reduce them in parallel. In this paper, we develop the estimation method for the number of resources and processing speed by relying on the performance evaluation model. The property of the evaluation model is closely related to the property of the SK combinatory graph, that is, the number of arguments and the method of parallel reduction. To verify the accuracy of the performance evalutation model, the results of the simulation will be presented. The simulation results show that the number of reductions and evaluations is nearly equal to the estimation results, with the exception that the necessary number of processing elements for the recursive function is different from the estimation results. Therefore we can reach the conclusion that the proposed performance evaluation model is useful for estimating the number of resources and processing speed.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. 서론
• 2. 시스템의 개요
• 3. 성능평가 모델
• 4. 시뮬레이션을 통한 검증
• 5. 결론
• 참고문헌
• 저자소개