Unless the speed gap between CPU and memory disappears, efficient memory usage remains as a decisive factor for performance. As the hardware storage capacity and computing power grow, the amount of data used by programs also increase; we focus on the compiler optimizations - pool allocation and field layout reconstruction - that optimize data usage of programs according to the memory hierarchy. Most of the previous work relied on profiling, since it is difficult to foresee run-time behaviors of programs at compile-time. On the contrary, our goal is to develop a fully automatic stand-alone compiler that transforms input codes to use memory more efficiently. We notice that regular expressions, which present repetition explicitly, are suitable for memory access patterns. In this paper, we describe how to extract memory access patterns as regular expressions in detail. Based on static patterns, we apply pool allocation to repeatedly accessed structures, and then exploit field layout reconstruction according to field affinity relations of chosen structures. In order to make a scalable framework, we devise and apply new abstraction techniques while finding properties for entire programs. We implement our analyses and layout transformations with the CIL compiler. To verify the effect and scalability of our framework, we examine various benchmarks including SPECINT 2000. Our experiments demonstrate that the layout transformations for dynamic memory dramatically improve cache locality by 16% and performance by 14% on average.
하드웨어 저장 공간과 CPU의 발전이 꾸준함에 따라, 프로그램의 복잡도와 데이터 사용량 또한 증가하는 추세이다. 메모리와 CPU 사이의 속도 차이가 줄어들지 않는 이상, 효율적인 메모리 사용은 여전히 성능 향상에 중요한 요소로 남아있다. 메모리 사용의 효율성을 높이는 여러 가지 방법 중, 이 논문은 컴파일러를 통한 코드 변환 방법 - 풀 할당과 필드 재구성 - 을 다루고 있다. 풀 할당은 자주 사용되는 인접한 동적 오브젝트들을 힙메모리의 특정 영역에 배치하는 방법이고, 필드 재구성은 데이터 구조 내의 자주 사용되는 필드들을 힙메모리 상에서 인접해 있도록 재구성하는 방법이다.
대부분의 코드 변환 방법들은 데이터 로컬리티 향상을 통해 프로그램의 성능을 향상시킨다. 로컬리티 향상을 위해서는 프로그램이 어떤 방식으로 데이터를 사용하는지 알아야 한다. 프로그램의 실제 동작을 수행 전에 예측하는 것은 어려운 문제이기 때문에, 기존 연구들은 프로그램을 미리 한 번 동작시켜 보는 프로파일링 기법에 의존하였다. 그와 달리, 이 논문은 전체 최적화 과정을 자동으로 수행하는 컴파일러 제작을 목표로 하고 있다. 즉, 프로그램의 데이터 사용을 수행 시켜보지 않고 예측한 후, 예측된 패턴을 바탕으로 풀 할당에 적합한 데이터 구조체를 찾고, 해당 구조체 마다 적합한 필드 레이아웃을 찾아 필드 재구성을 하는 컴파일러를 제작하였다.
로컬리티는 반복적으로 수행되는 프로그램의 일부분에 의해서 대부분 결정된다. 프로그램의 반복성을 잘 나타낼 수 있는 수단으로는 정규식을 사용하였다. 오토마타와 정규식이 동치라는 점을 활용하여, 프로그램의 수행 흐름으로부터 오토마타를 추출한 뒤, 오토마타로부터 프로그램의 메모리 접근 패턴을 유추하였다. 특정 데이터 구조체에 대한 필드 접근 패턴에서 반복성을 찾는 방법으로 풀 할당을 위한 데이터 구조체를 찾고, 패턴 내에 나타나는 필드들의 연관성으로부터 적합한 필드 레이아웃을 계산하였다. 그 후, 코드 내에서 해당 구조체를 할당하는 부분과 필드를 접근하는 부분을 각각 커스텀 할당 함수와 바뀐 레이아웃에 따라 필드 주소를 계산하는 코드로 치환하였다. 보다 간단한 형태의 패턴을 추출하는 방법을 고안하고, 패턴 해석 부분의 비효율성을 없애서 SPECINT 2000과 같이 큰 규모의 벤치마크에 대해서도 실험할 수 있었다. 실험 결과, 평균 16%의 캐쉬 성능 향상을 얻을 수 있었고, 그에 따라 실제 프로그램의 성능도 평균 14% 향상되었다.
