Program optimization exploiting cross-invocation value reuse

국문 초록 (Abstract)

반도체 공정 기술의 발전으로 메모리 집적도가 지속적으로 높아짐에따라, 컴퓨터
시스템의 메모리 용량도 지속적으로 증가하고 있다. 그러나, 현재 메인 메모리로 널 리 사용되고 있는 DRAM 은 비트를 저장하는 커패시터(capacitor)의 스케일링으로 인해, 전하 유지 시간(retention time)이 점차 짧아지고 있으며, 이는 리프레쉬 (refresh) 비용의 증가로 이어지고 있다. 이러한 문제를 해결하기 위해, DRAM을 대체하거나 보완할 새로운 메모리 디바이스 기술이 활발히 연구되고 있다. 이 중 비휘발성의 특성을 가지며, DRAM 처럼 byte-addressable 한 메모리 디바이스들 을 흔히 Storage Class Memory(SCM)이라 부르는데, SCM은 데이터 유지를 위한 Refresh가 필요없고, 집적도가 높아 비트당 가격이 저렴한 장점이 있다. 또한, PRAM, STT-RAM등의 SCM 디바이스는, DRAM과 비슷한 수준의 엑세스 시간을 갖는다. 따라서, SCM과 DRAM을 혼용하여, 메인 메모리 시스템을 구성하려는 방법 들이 제안되었는데, 이를 Unified Memory System(UMS)이라 부른다. UMS는 기 존의 DRAM 메인 메모리에 비해, 같은 가격과 전력 소모 제한 하에서 더 많은 용 량의 메모리를 제공해 준다. 본 논문에서는 UMS가 제공하는 풍부한 메모리 자원 을 이용하여, 프로그램의 성능을 향상시키는 기법으로 Terminate-and-Stay-Resident (TSR) Object를 제안한다. TSR Object 는 프로그램 종료 후에도 데이터 가 메모리 영역에 상주하여, 다음번 프로그램 실행시 재활용 될 수 있는 메모리 오 브젝트이다. TSR Object 를 재활용 하여, 프로그램 수행시 오브젝트에 대한 초기화 시간을 줄이며 값의 재사용을 바탕으로 프로그램의 성능을 높일 수 있다. 또한, 본 고에서는 TSR Object 를 활용가능한 4개의 프로그램 패턴(Iterative Convergence, Branch-and-Bound, Inspector-and-Executor, Code Cache)을 제시한다. 이 4 가지 패턴에서 TSR Object를 활용하여, 루프의 반복 횟수를 줄이거나, 프로그램 초기 구동 시간을 절약하거나, 예측적 병렬화를 적용하는 등 다양한 방법으로 프로 그램의 성능을 개선할 수 있음을 보였다.

다국어 초록 (Multilingual Abstract)

Computer memory size continues to increase as memory densities have increased with the progress of semiconductor process technology. However, currently charge-retention time is gradually shortened due to the scaling of the DRAM cell capacitor and it can causes frequent refreshes. So as to solve this problem, the memory device technology replacing or supplementing the DRAM has been actively researched. Storage Class Memory (SCM) is the memory device which has characteristic of nonvolatile semiconductor memory and is byte-accessible and it doesn’t need to refresh device cells and has a low price per bit due to the high density of cells. In addition, the specific devices (PRAM, STT-RAM, etc.) have an average access time similar to the DRAM. In this paper, the techinique of improving the performance of the program, cross- invocation value reuse, using an abundant memory space like SCM is proposed. Terminate-and-Stay-Resident (TSR) object that is not terminated after end of the program can be recycled when the program is executed in the next time. This allows to reduce the object creation time at the beginning of the program, and it causes a performance improvement. In addition, this paper presents four patterns available to use TSR object (Iterative Convergence, Branch-and-Bound, Inspector-and-Executor and Code Cache). In these patterns, the performance is improved significantly that can be done in a variety of ways, reduction of the number of loop iterations, using the previous result value and speculative parallelization by using TSR object.

목차 (Table of Contents)

• 제1장 서론 3
• 제2장 연구 배경 6
• 2-1 메모리 디바이스의 스케일링 추세. 6
• 2-2 TSR Object 9
• 제3장 TSR Object 를 지원하기 위한 API 10
• 3-1 Function Design 10
• 3-1-1 tsrmalloc 11
• 3-1-2 tsrflag 11
• 3-1-3 tsrrealloc 11
• 3-1-4 tsrfree . 12
• 3-2 API 사용 예 . 12
• 제4장 TSR Object 사용 패턴. 14
• 4-1 Iterative Convergence. 15
• 4-2 Branch and bound. 16
• 4-3 Inspector-executor. 18
• 4-4 TSR Object 지원을 위한 API 설계 시 고려사항 20 제5장 프로토타입 구현. 22
• 5-1 Ramfs 를 이용한 TSR Object 에뮬레이션. 23
• 5-2 TSR Object Memory Layout. 23
• 5-2-1 TSR Object 관리를 위한 전체 Heap 구조 . 23
• 5-2-2 Metadata 구조 23 5-2-3 Allocated Block 구조. 23
• 5-2-4 De-allocated Block 구조 26
• 5-2 TSR object allocated region management. 27
• 5-2-1 Object group victim 선택 27
• 5-2-2 TSR object runtime handler. 27
• 제6장 성능 평가. 29
• 6-1 실험 환경. 29
• 6-2 성능. 29
• 6-2-1 Iterative convergence. 29
• 6-2-2 branch and bound 33
• 6-2-3 Inspector and Executor 35
• 6-3 Programming effort. 37
• 제7장 관련 논문 39
• 제8장 결론 42