Instruction scheduling is an important compiler technique for exploiting instruction-level parallelism (ILP) in modern, high-performance microprocessors. Among scheduling techniques, trace scheduling is an optimization technique that performes instruction scheduling across basic blocks. The trace scheduler selects a group of instructions from a sequence of basic blocks and schedules these instructions as if they were in a single basic block. So If operations are moved across basic block boundaries, the compensation copies are inserted into off-traces in order to preserve program's semantics. But insertion of compensation copies penalizes the off-trace code. The goal of this thesis is to reduce the penalty of off-traces and to overcome the risk from misprediction of branch target especially in control-intensive programs. It deals with the problem of compensation copy codes and presents optimization techniques to enhance the trace scheduling, related to the paths including off-traces. And the effectiveness is evaluated by using SPEC95 benchmark programs. The result shows the feasibility of improvement of trace scheduling with compensation code optimization techniques proposed in this paper.
현대 초고속 마이크로프로세서에서는 여러 개의 명령어를 한 clock cycle에 수행할 수 있다. 이러한 병렬 프로세서에 맞추기 위한 컴파일러에서는 명령어 스케줄링 작업이 명령어 수준에서의 병렬성을 높이기 위해 중요한 역할을 한다. 명령어 스케줄링 방법들 중에서 trace scheduling기법은 명령어들이 기본 블록들 사이를 넘나들수 있게 허용하는 글로벌 명령어 스케줄링 방법들 중 하나이다. 기본 블록내에서의 스케줄링은 병렬성을 찾기에 한계가 있기 때문에 여러 개의 기본 블록을 스케줄링의 범위로 하는 것이다. trace scheduling의 핵심 내용은 명령어들을 주어진 정보에 기반하여 기본 블록에 상관없이 선택한 후 trace를 형성하고, trace가 기본 블록인 것처럼 명령어 스케줄링을 한다. 이 때, trace내에서 기본 블럭의 경계를 넘어가는 명령어들이 있다면, 프로그램의 올바른 수행을 위해 보정작업이 필요하다. 보정작업이란, trace 내의 명령어들의 재배열로 off-trace의 영향을 미칠 경우, 필요한 명령어를 복사하여 off-trace에 삽입하는 것이다. 그러나 복사된 명령어의 삽입은 코드 크기를 늘리는 단점도 있고, off-trace에 불리한 결과를 초래할 수 있다. 특히, off-trace를 포함한 path에서 같은 명령어가 두 번씩 반복되는 경우도 있다. 즉, trace형성시 이용된 정보가 잘못되었다면 전체 실행시간에 영향을 줄 수 있다. 이 논문은 이러한 off-trace에 주어지는 부작용을 줄이고, 결국 trace선택시 사용된 정보가 정확하지 못했을 때 생길 수 있는 위험부담을 감소시키는 데에 목적을 둔다. 따라서 보정코드에 대한 문제점들을 중심으로 기존 연구들의 고찰을 통하여 off-trace에 주어지는 악영향을 줄이기 위한 몇 가지 효과적인 방법을 제안하였다.
첫 번째는 프로그램의 CFG에 적용할 수 있는 최적화 방법이다. 이는 프로그램의 CFG를 간소화함으로써 trace내의 명령어 수를 늘려 더 많은 병렬성의 기회를 제공할 수 있다. 두 번째는 보정코드에서 반복되는 코드를 찾아 없애는 방법이며 직접적으로 off-trace에 대한 부작용을 줄일 수 있는 방법이라 할 수 있다. 그리고 마지막으로, superblock scheduling에서 사용되는 tail duplication의 방법을 선택적으로 적용하여, 코드급증을 초래하지 않으면서 off-trace의 부담을 줄일 수 있는 기법을 설명하였다.
이렇게 제안한 몇 가지 최적화 방법을 trace scheduling 알고리즘에 적용하여 향상된 trace scheduler를 구현하였다. 그리고, SPEC95 프로그램들을 이용하여 제안한 코드 최적화 방법들이 적용되기 전과 적용된 후를 비교분석함으로써 보정코드 최적화 방법들이 어느 정도 榮향을 주었는지를 평가하였다. 비록 그 효과성이 크게 드러나지는 않았지만, 그에 대한 몇 가지 요인들이 있었다. 그리고 off-trace에 대한 악영향을 줄일 수 있었고, control이 복잡한 프로그램들에 유용하다는 데에서 그 가치를 찾을 수 있을 것이다.
