기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
태그 옮기기에 의한 G-machine 그래프의 압축
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 태그 옮기기에 의한 G-machine 그래프의 압축
  • Compressing the Graphis in G-machine by Tag-Forwarding
저자명
우균,한태숙
간행물명
정보과학회논문지. Journal of KISS (b):software and applications. B
권/호정보
1999년|26권 5호|pp.702-712 (11 pages)
발행정보
한국정보과학회
파일정보
정기간행물|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

지연 함수형 언어를 효율적으로 구현하기 위한 한 방법으로 G-machine이 제안되었다. G-machine은 그래프 축약을 빠르게 수행하지만, 축약 과정의 그래프를 저장하기 위해 많은 기억장소를 필요로 한다. 이는 그래프 축약 방법자체의 문제점으로 생각된다. 이 논문에서는 그래프 노드의 태그를 옮김으로써 기억장소의 그래프 구조를 압축할수 있는 방법을 제안한다. 노드의 태그는 그 노드를 가리키는 포인터 자리로 옮겨지는데, 포인터 정보의 유지하기 위해 상대주소와 합쳐져 함께 옮겨진다. 태그 옮기기는 그래프 구성 노드를 힙에 동시에 할당할수 있을 때 가능하다. 그러나, 일반적으로 그래프의 일부가 전체 그래프가 생성되기 이전에 생성될 수 있으므로, 이러한 태그 옮기기가 항상 가능한 것은 아니다. 그렇지만, 태그 옮기기에 의해서 어느 정도의 힙 사용량을 줄일 수있다. 태그 옮기기에 의해 그래프를 압축했을 때 압축된 그래프를 해석하기위한 수행시간의 부담이 생기게 되는데, 이 부담정도를 알아보기 위해 몇몇 작은 프로그램에 대해서 실험결과를 보였다. 실험결과에 따르면, 태그 옮기기를 수행한 결과, 총 힙 사용량은 평균 약 305 감소하였고, 이로 인한 수행시간은 원래의 G-machine과 비슷한 수준인 것으로 나타났다.