Instruction pipelining is essential to enhance the processor performance in modern RISC microprocessors including superscalar processors. Deeper pipeline generally yields finer clock step and shorter CPU cycle time and, therefore, enhances the CPU performance significantly as long as the normal pipeline flow is maintained. However, as the pipeline depth is increased for higher throughput, the branch penalty is also increased, which can severely reduce the performance advantage due to the deeper pipeline.
There were several approaches to solve the long branch penalty problem in both static and dynamic approaches. When only static approaches such as delayed branch and squashed branch are used, the hardware cost can be reduced but only at the cost of long branch execution cycles. On the other hand, dynamic approaches reduce the branch execution cycles but requires significant hardware overhead, as exemplified by such hardware schemes as branch target buffer (BTB) and branch folding.
In this thesis, a new hardware scheme called dynamic rescheduling squashed branch(DRSB) to reduce the branch execution cycles is proposed. A conventional BTB scheme enables the processor to fetch newly-predicted branch target instructions during the branch delay cycles by employing a separate branch cache which stores the PCs of the executed branch instructions. The proposed DRSB scheme employs a rescheduling buffer in which newly-predicted target instructions are dynamically rescheduled, therefore, enables processors to fetch the target instruction sequentially during branch delay cycles.
Performance of the DRSB scheme was evaluated using a trace-driven branch simulator with the estimation of silicon area using 0.8㎛ CMOS standard cell library. DRSB scheme reduces the silicon area of branch unit into $\frac{1}{2.911}$ while reducing branch execution cycles by 0.4% as compared with conventional BTB scheme whose branch cache size is 1 k-bytes. The proposed DRSB scheme reduces the silicon area of the branch unit significantly while reducing branch execution cycles because all the instruction cache cells are utilized as branch cache cells through dynamic rescheduling of newly-predicted target instructions into corresponding branch delay slots within the rescheduling buffer.
슈퍼스칼라 구조를 포함한 최근의 RISC 형태의 마이크로 프로세서는 성능 향상을 위해서 명령어 파이프라인을 필수적으로 채택하고 있다. 파이프라인의 단계를 높이면 일반적으로는 마이크로 프로세서의 수행 주기가 짧아지므로 성능의 향상을 기할 수 있으나, 분기 명령어 수행시의 분기 지연 사이클 (branch delay cycle)로 인한 분기손실 (branch penalty)은 프로세서의 성능을 심각하게 감소시킨다.
분기손실을 줄이기 위하여 소프트웨어에 기인한 정적인 기법과 하드웨어에 기인한 동적인 기법들이 많이 제안되었다. 기존의 정적인 기법은 구현을 위한 하드웨어 비용이 작은 반면에 분기손실을 충분히 감소시키지 못하고, 하드웨어에 기인한 기존의 동적인 기법은 정적인 분기기법에 비해서 분기손실을 충분히 감소시키지만 구현을 위한 하드웨어 비용이 큰 단점이 있다.
본 논문에서는 기존의 동적인 분기기법보다 작은 하드웨어 비용을 사용하여 분기손실을 최소화 하는 DRSB (Dynamic Rescheduling Squashed Branch) 라고 명명된 효율적인 동적 분기기법을 제안한다. 인텔의 펜티움, P6등과 같은 기존의 많은 마이크로 프로세서에서 사용되고 있는 BTB (Branch Target Buffer) 기법의 경우, 분기지연 사이클 동안 예측된 분기목적 명령어 (predicted branch target instruction)을 페취 (fetch)함으로써 분기손실을 줄이며, 이를 위해서 수행된 분기명령어의 프로그램 카운터 (PC) 와 목적 명령어의 PC값을 저장하기 위한 독립적인 분기명령어 캐쉬 (cache)가 필요하게 된다.
본 논문에서 제안된 DRSB 기법은 분기지연구간 (branch delay slot)에 분기목적 명령어를 동적으로 재 배치함으로써 BTB 기법의 분기명령어 캐쉬를 사용하지 않고, 분기지연사이클 동안 분기목적 명령어의 페취를 가능하게 한다. 명령어의 순차적인 페취와 함께 동적인 분기목적 명령어의 재배치를 통해 DRSB 기법을 지원하는 재배치 버퍼 (rescheduling buffer) 구조를 제안하였다.
실험결과를 통해서 볼 때, 재배치 버퍼를 이용한 DRSB 기법은 분기명령어 캐쉬 크기가 1 KB인 BTB 기법에 비해서 분기명령어 수행 사이클을 추가로 0.4% 감소시킴과 함께 분기유닛의 실리콘 면적을 $\frac{1}{2.911}$로 감소시켰다.
