정보과학회 논문지 B : 소프트웨어 및 응용
Current Result Document : 7 / 7
| 한글제목(Korean Title) |
그래프 축약 기계에서 수행 시간을 고려한 루트 최적화 방법 |
| 영문제목(English Title) |
Root Optimization with Less Execution-Time Overhead in Graph Reduction Machine |
| 저자(Author) |
최광훈
한태숙
Kwanghoon Choi
Taisook Han
|
| 원문수록처(Citation) |
VOL 25 NO. 05 PP. 0841 ~ 0853 (1998. 05) |
한글내용
(Korean Abstract) |
지연 계산 기반 함수형 언어에서 동일한 값을 갖는 매개변수를 가지고 재귀호출이 일어날 때 일부 동일한 내용을 갖는 썽크를 반복해서 만드는 부담이 있다. M,P.Jones는 G-machine에 공유할 썽크를 찾는 명령어를 도입하여 이 부담을 줄이는 루트 최적화 방법을 제안했다. 이 방법으로 썽크 공유를 통해 수행 공간을 절약할 수 있었지만 공유할 썽크의 위치를 찾는데 시간 부담이 크다. 그리고 임의의 썽크를 블럭형태로 표현할 수 없고 테일 호출을 함께 적용할 수 없는 단점이 있다. 이러한 이유로 인해 이 방법을 실제적인 컴파일러에 적용하기가 쉽지 않았다. 본 논문에서는, 안전하게 씽크를 공유할 수 있는 함수로 변환하고 새로운 타입의 노드와 이 노드에 대한 런타임 시스템 루틴을 추가해 기존의 방법이 지닌 단점을 해결하였다. 그리고 본 논문에서 제안한 방법을 Chalmers Haskell 컴파일러에 구현해 실현 가능성을 보였고, 벤치마킹 실험 결과를 통해 적은 수행 시간 부담으로 수행 공간을 줄일 수 있음을 확인하였다.
|
영문내용
(English Abstract) |
In functional languages based on lazy evaluation, recursive calls with same-valued parameters can create thunks containing invariants repeatedly. M.P.jones introduced a new G-machine instruction to find sharable invariants in thunks so that those overhead could be reduced. It is called root optimization. Although root optimization can reduce runtime space, it results time overhead to search sharable positions of thunks. Also, it prevents from thunks representations with blocks and tail call optimizations. These cause difficulties in employing root optimization for practical compilers. We solved the problems by transforming a function into one which can share invariants of thunks safely and introducing new types of node and runtime system routines for each type. We implemented the idea on Chalmers Haskell compiler to show its realizability. We convinced that root optimization can be implemented with less execution-time overhead by experiment results. |
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
