Many modern computer architectures are equipped with hardware components to reduce various costs such as code size and energy and improve the performance of the system such as execution time and memory usage. Conventional code generation techniques, however, often generates inefficient code, failing to fully utilize those hardware components and leaving much room for optimizations.
In my thesis, I propose code generation techniques to better exploit strong features of three modern architectures by refining the layouts of data in storage such as memory and register file.
First, I address the offset assignment problem in code generation for digital signal processor (DSP). I aim to minimize the code size and improve the performance by reducing the number of instructions solely for calculating addresses of variables. By tightly combining the offset assignment problem with code scheduling, I improve existing solutions.
I also propose the reassignment of registers to minimize the costs of transferring data between the register file and the memory for the architectures equipped with register stacks. Register stack provides a virtually infinite-sized register file to processor through overflowing the register values to the memory whenever the total height of the register stack reach a certain threshold and also filling the registers back whenever they are needed, without processor intervention. To mitigate these costs of overflowing/underflowing registers, I attempt to minimize the register stack height by reassigning register names in the code emission phase, the last phase of code generation.
Finally, I propose a technique for variable assignment to mitigate the delay of memory access which is known as one of the major bottlenecks in embedded systems' performance. I study DRAM memory layout for storing the non-array variables in code to achieve a maximum utilization of page and/or burst modes to increase memory bandwidth. I formulate relevant optimization problems and reveal that they are NP-hard. In addition, I propose efficient heuristic algorithms.
The above studies show that elaborate layouts of data during compile-time considering underlying features within register files and virtual/physical memory address space can substantially improve the performance of overall system such as code size, execution time, and energy consumption.
오늘날 많은 컴퓨터 아키텍처들에는 코드 사이즈와 에너지와 같은 비용을 줄이고, 프로그램의 수행시간과 메모리 사용량 등의 성능을 개선시키기 위한 전용의 하드웨어들이 장착되어있다. 그러나, 기존의 코드 생성 기법들에 의해 생성된 코드는 이러한 하드웨어들을 최대한 활용하기에는 종종 비효율적이며, 아직도 많은 최적화의 여지를 남겨놓고 있다. 본 논문에서는, 코드 생성 시에 메모리나 레지스터 파일 내에 데이터의 배치를 최적화함으로써 아키텍쳐의 장점을 최대한 높이는데 도움을 줄 수 있음을 보여주었다. 세 가지 컴퓨터 아키텍처를 위해서, 각각 최적화 기법을 개발하였다.
첫째, 주소 생성을 위한 전용 하드웨어인 AGU가 장착된 디지털 신호 처리 프로세서용 코드를 생성 시에, 변수의 주소를 할당하는 문제 (offset assignment problem) 에 대해서 다루었다. 연구의 목적은, 변수의 주소를 계산하는 용도로만 쓰이는 인스트럭션의 개수를 줄임으로써, 전체적인 코드의 크기를 줄이고, 실행 성능을 개선하는 것이다. 각각이 NP-hard한 문제인 변수의 주소 할당과 코드 스케줄링 (scheduling)을 효과적으로 결합함으로써, 적당한 시간 이내에 만족스러운 결과를 내는 알고리즘을 개발하였다.
또한, 레지스터 스택을(register stack) 가지는 아키텍처에서 레지스터와 메모리 간의 데이터 전송에 소요되는 비용을 최소화하기 위한 레지스터 재할당 (register reassignment) 기법을 개발하였다.
구체적으로는 컴파일러 코드 생성시의 레지스터 할당 이후에, 레지스터의 liveness를 분석해서 레지스터 스택의 높이를 줄이는데 도움이 되는 방향으로 레지스터들을 재할당 해주는 기법이다. 최적의 레지스터 재할당을 정의하고, 그래프 상에서 패스를 찾음으로써 재할당을 하는 기법을 개발하였다.
마지막으로, DRAM의 페이지(page) 모드 접근과 벌스트(burst) 모드 접근을 최대한 이용하도록 하는 프로그램 변수의 메모리 주소 상의 배치 기법을 개발하였다. 각각의 접근에 대해서, 최적의 배치를 구하는 것은 NP-hard함을 밝히고, graph 상에서 패스를 찾는 방법에 기반한 효율적인 고성능의 휴리스틱 알고리즘을 개발하였다. 제안된 기법은 캐시(cache)메모리가 존재하지 않는 소형 컴퓨팅 시스템에서 메모리 접근 시간과 에너지를 줄이는 데 효과적으로 이용될 수 있다.
본 논문은 위의 세 가지 연구들을 통해서, 레지스터 파일이나 논리적/물리적 메모리 주소 영역 및 제공되는 접근 모드의 특징을 고려하여, 그 안에 데이터들의 위치를 컴파일 시에 잘 배치함으로써 생성된 코드의 사이즈, 수행 시간, 에너지 소모와 같은 전체적인 시스템의 성능을 상당부분 개선시킬 수 있음을 보여주었다.
