In highly parallel ILP(Instruction-Level Parallel) processors, one of the performance bottlenecks is insufficient instruction fetch bandwidth. The fetch bandwidth is determined by a number of factors, such as instruction cache hit ratio, branch prediction accuracy, basic block size, and percentage of taken branches in the instruction stream.
In a conventional fetch unit, which can fetch one basic block per cycle, the number of instructions fetched per cycle is about five, which is the average basic block size of general-purpose application program. As the fetch unit cannot fully feed the highly parallel execution unit, it becomes necessary to fetch multiple basic blocks per cycle. Fetching instructions from conventional cache memory hinders this effort due to the problem of noncontiguous instruction fetching caused by taken branches as branch instructions and their targets are typically located in different cache lines.
Cache miss also limits instruction fetch bandwidth by introducing clock cycle overhead for the cache miss service. To reduce the clock cycle overhead and improve the efficiency of an instruction fetch unit, prefetching is used to bring instructions as needed by the processor into the cache in advance.
In this thesis, we propose hardware schemes to improve instruction fetch bandwidth; multiple basic block fetching and instruction prefetching. In the proposed multiple basic block fetching scheme, called path-classified trace cache, paths are classified to improve the trace cache hit ratio and basic blocks are joined to reduce the hardware cost needed to implement the trace cache. The proposed instruction prefetching scheme, called look-ahead prefetching, reduces the miss penalty of the first-level instruction cache by accurately predicting the target lines to be prefetched using a branch predictor.
In order to investigate the performance of the proposed schemes, we constructed trace-driven simulation models for the proposed schemes which were simulated using SPEC95 benchmark programs. We compared the proposed multiple basic block fetching to the trace cache [34], and the proposed instruction prefetching to the stream buffering [22]. The proposed multiple basic block fetching scheme excels the trace cache scheme in the trace cache hit ratio and EFS(Effective Fetch Size) by 33% and 9%, respectively. And, the proposed instruction prefetching scheme excels the stream buffering in miss penalty reduction and bus occupation by 26% and 42%, respectively. When both hardware schemes are combined and equipped with an instruction fetch unit, they improve IPC(Instruction completed Per Cycle) by 61% over the conventional cache-based instruction fetch unit.
고병렬 수퍼스칼라 프로세서에 있어서 명령어 팻치 유닛의 효율은 그 프로세서의 성능을 좌우하는 중요한 요인 중 하나이다. 사이클당 팻치되는 명령어의 수는 명령어 캐쉬의 히트율(hit ratio), 분기 명령어 예측의 정확도, 기본 블록(basic block)의 크기, 그리고 명령어 흐름내의 분기 동작의 발생 등에 의해 결정된다.
현재 사용되고 있는 명령어 팻치 유닛은 한 사이클에 하나의 기본 블록만을 팻치하고 있어서 사이클 당 팻치 가능한 명령어의 수는 약 5개 정도이다. 이는 일반적인 어플리케이션들의 기본 블록의 크기가 약 5개의 명령어임에 기인한다. 이와 같은 명령어 팻치 유닛은 실행 유닛의 병렬성을 충분히 활용하지 못함으로써 프로세서의 성능을 제한하게 된다. 따라서, 한 사이클에 복수개의 기본 블록을 팻치 하는 것이 필요하다. 하지만, 단순히 명령어 캐쉬로부터 한 사이클에 복수개의 기본 블록을 팻치하는 일은 분기 작용을 발생시키는 분기 명령어로 인해 방해를 받는다. 그 이유는 일반적으로 분기 명령어와 그 분기 명령어의 목표 명령어가 서로 다른 캐쉬 라인에 존재하기 때문이다.
명령어 캐쉬의 미스(cache miss) 또한 그 미스를 처리하기 위한 많은 사이클을 소모하게 함으로써 명령어 팻치 유닛의 효율을 떨어뜨리는 중요한 요인 중 하나이다. 명령어 캐쉬의 미스에 의한 성능 저하를 최소화 하기 위해 명령어를 메모리로부터 사용되기 전에 미리 캐쉬로 가지고 오는 프리팻치(prefetch) 기법이 일반적으로 많이 사용되고 있다.
이 논문에서는 명령어 팻치 유닛의 성능을 높이기 위한 하드웨어 기법들을 제안한다. 제안된 하드웨어 기법은 한 사이클에 복수개의 기본 블록을 팻치하는 기법과 명령어 프리팻치 기법이다. 먼저 사이클당 복수개의 명령어를 팻치하기 위한 기법으로는 기존의 트레이스 캐쉬(trace cache [34]) 기법을 보완하여 트레이스 캐쉬의 히트율을 높이고 하드웨어 비용을 절감한다. 그리고, 제안된 프리팻치 기법은 분기 예측기(branch predictor)를 사용하여 프리팻치될 목표 명령어에 대한 예측율을 높임으로서 명령어 캐쉬의 효율을 높인다.
제안된 하드웨어 기법들의 성능을 측정하기 위해 트레이스 기반(trace-driven)의 시뮬레이션 기법과 SPEC95 벤치마크 프로그램들을 사용하였다. 또한 제안된 기법들은 관련된 최신의 연구 결과들과의 성능 비교를 통하여 그 우수성을 검증 하였다. 먼저 제안된 복수개의 명령어 팻치 기법은 기존의 트레이스 캐쉬 기법에 비하여 트레이스 캐쉬의 히트율을 33% 높였고 그 결과 사이클당 명령어 팻치 수(EFS: Effective Fetch Size)를 9% 높였다. 또한 제안된 명령어 프리팻치 기법은 기존의 스트림 버퍼링(stream buffering [22]) 방식에 비하여 26% 만큼의 캐쉬 미스 패널티를 더 줄일수 있었다. 두 가지의 하드웨어 기법을 채용한 명령어 팻치 유닛은 기존의 명령어 팻치 유닛에 비하여 사이클당 약 61%의 명령어를 더 수행할 수 있게 함을 보였다.
