서지주요정보
Memory reuse analysis and transformation for ML-like programs = ML같은 프로그램에서 메모리 재사용을 위한 프로그램 분석과 변환
서명 / 저자 Memory reuse analysis and transformation for ML-like programs = ML같은 프로그램에서 메모리 재사용을 위한 프로그램 분석과 변환 / Ouk-Seh Lee.
저자명 Lee, Ouk-Seh ; 이욱세
발행사항 [대전 : 한국과학기술원, 2003].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8014775

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 03028

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Automatic memory management can be more than the garbage collection. Using the static analysis technologies, we can automatically find memory reuse opportunities in user programs, hence reducing the frequency of garbage collections. In this thesis, we present a static analysis that estimates reusable memory cells and a source-level transformation that inserts explicit memory-reuse commands into the programs that support algebraic data types. For benchmark programs in ML, our analysis and transformation achieves the memory reuse ratio from 5.2% to 91.3%. The small-ratio cases are for programs that have too much sharings among memory cells. For other cases, our experimental results are encouraging in terms of accuracy and cost. Major features of our analysis are: (1) use of multiset formulas in expressing the sharings and partitionings of heap cells; (2) poly-variant analysis of functions by parameterization for the argument heap cells; (3) deallocations conditioned by dynamic flags that are passed as extra arguments to functions. Our method is better than existing reported works in terms of its analysis accuracy and effectiveness. Our analysis and transformation is fully automatic and proven correct. Our experiment results are promising enough to conclude that garbage collection combined with the static analysis techniques can comprise more efficient, automatic memory management than garbage collection alone does.

ML같은 상위의 언어에서 메모리 재활용 방법 (garbage collection) 이상의 효율로 메모리를 자동관리할 수 있다. 프로그램 분석 기술을 사용하여 메모리 수거를 거치지 않고 바로 재사용하도록 변환함으로써 메모리 수거의 회수를 줄이거나 필요 메모리 크기를 줄일 수 있다. 본 논문에서는 재사용 가능한 메모리를 추정하는 프로그램 분석과 이를 기반으로 메모리 재사용 명령어를 삽입하는 프로그램 변환 알고리즘을 제시한다. 고안한 기술을 구현해서 다양한 ML 프로그램들에 적용해 본 결과, 총 할당된 메모리 중 5.2%에서 91.3%를 재사용하였고, 재사용에 의해 프로그램이 필요로 하는 메모리 공간을 최대 71.9% 까지 줄일 수 있었다. 향상된 정도가 작은 경우는 프로그램이 원천적으로 재사용 가능성이 낮은 경우들이었다. 제안한 분석과 변환 알고리즘의 핵심 기술은 다음과 같다. (1) 분석의 정확도를 높이기 위해 메모리 셀들의 집합을 분석 도중 나누는 두 가지 방법을 사용한다. (2) 나누어진 조각들이 서로 겹치지 않는지를 메모리 셀들간의 공유정보를 통하여 분석한다. (3) 함수의 분석 결과가 인자에 대한 식으로 얻어지므로 매번 함수 호출시 분석하지 않아도 싸게 정확한 결과를 얻을 수 있다. (4) 실행 시간에 전달되는 논리값 정보를 통해 조건적으로 메모리를 재사용하도록 변환한다. 제안된 알고리즘은 지금까지 알려진 방법과 비교하여 정확하고 효과적이다. 또한 프로그램 작성자의 아무런 도움도 받지 않고 자동으로 프로그램을 변환하며, 변환된 코드는 언제나 안전하다는 것이 증명되었다. 실험 결과를 통하여 프로그램 분석과 결합된 메모리 재활용 방법이 프로그램 분석 없이 홀로 메모리를 관리하는 것보다 더 효과적일 수 있음을 규명하였다.

서지기타정보

서지기타정보
청구기호 {DCS 03028
형태사항 iv, 105 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 이욱세
지도교수의 영문표기 : Kwang-Keun Yi
지도교수의 한글표기 : 이광근
수록잡지명 : "Inserting safe memory reuse commands into ML-like programs". Lecture notes in computer science, no.2694, pp. 171-188 (2003)
수록잡지명 : "A proof method for the correctness of modularized 0CFA". Information processing letters, v.81 no.4, pp. 179-185 (2002)
학위논문 학위논문(박사) - 한국과학기술원 : 전산학전공,
서지주기 Reference : p. 101-105
주제 program analysis
memory analysis
garbage collection
type
functional language
프로그램 분석
메모리 분석
메모리 재활용
타입
함수형 언어
QR CODE qr code