The performance of processor has increased dramatically over the past decade and has outperformed that of main memory. As a result, the main memory access latency becomes an obstacle to achieve high performance computing. In large-scale multiprocessors with a general interconnection network, the program execution time significantly depends on the shared-memory access latency which consists of the memory access latency and the network latency. The shared-memory access latency reaches to tens to hundreds of processor cycles with the advent of very fast uniprocessors and massively parallel systems. The most part of this latency comes from the large network latency associated with the traversal of the processor-memory interconnect.
Caches are quite effective to reduce and hide the main memory access latency in uniprocessor systems and the shared-memory access latency in shared-memory multiprocessors. However, the remained cache miss penalty is still a serious bottleneck to achieve high performance computing.
Prefetching is an attractive scheme to reduce the cache miss penalty by exploiting the overlap of processor computations with data accesses. Especially for multiprocessors, cache miss penalty can be decreased significantly by overlapping the network latency of fetched block with those of prefetched blocks. Many prefetching schemes based on software or hardware have been proposed. Software prefetching schemes perform static program analysis and insert explicitly prefetch instructions into the program code, which increases the program size. In contrast, hardware prefetching schemes control the prefetch activities according to the program execution by only hardware. Several hardware prefetching schemes prefetch blocks if a regular access pattern is detected. These schemes require complex hardware to detect a regular access pattern. Prefetch on misses [29] is a simple hardware scheme, but needs a miss to prefetch one block. Thus this scheme reduces the miss rate maximally to half.
Sequential prefetching [28. 10]is an extension of prefetch on misses. This scheme prefetches d consecutive blocks following the missed block in the caches on each miss. The miss rate could be reduced maximally to one (1+d)th by this scheme. But this scheme increases the possibility of prefetching useless blocks. Because the traffic and the number of memory accesses are increased by prefetching useless blocks, the memory access time is increased, and the performance is degraded. Also, useless blocks increase the cache pollution. Thus, the performance of sequential prefetching depends on the prefetching degree, i.e., the number of blocks to prefetch on each miss, and the average length of sequential memory access.
We analyze the relationship between the average length of sequential streams of application programs and the effectiveness of sequential prefetching on various memory and network latency and propose a new adaptive sequential prefetching scheme. Simply adding a small table to the sequential prefetching scheme, this scheme prefetches many blocks on cache misses in long sequential streams and a few blocks on misses in short sequential streams by adjusting the prefetching degree according to the length of sequential streams. Therefore, the proposed scheme prefetches a large number of blocks for application programs with high average length of sequential streams and reduces the miss rates significantly, and prefetches a small number of blocks for application programs with low average length of sequential streams and avoids loading useless blocks.
과거 수십년동안 프로세서의 성능은 비약적으로 증가하여 주기억장치의 성능과의 차이가 상당히 크게 되었다. 결과적으로, 주기억장치 접근 지연시간은 컴퓨터상에서 고성능 컴퓨팅을 이루는데 장애가 되었다. 또한 범용 상호 연결망으로 연결된 대규모 다중 처리기에서도, 프로그램 수행 시간은 공유기억장치의 접근 지연시간에 의해 큰 영향을 받는다. 공유기억장치의 접근 지연시간은 기억장치 접근 지연시간과 망 지연시간으로 구성된다. 아주 빠른 프로세서의 출연과 다중처리기의 대규모화에 의해, 공유기억장치의 접근 지연시간은 프로세서 주기의 수십에서 수백배에 이르게 되었으며, 이 지연시간은 주로 프로세서와 기억장치사이의 망을 통과하는데 소요되는 망 지연시간에 기인한다.
캐쉬는 단일처리기로 구성된 시스템의 주기억장치 접근 지연시간이나, 범용 상호 연결망으로 연결된 대규모 다중 처리기에서의 공유기억장치의 접근 지연시간을 줄이는데 아주 효과적이다. 하지만, 남아 있는 캐쉬 미스는 고성능 컴퓨팅을 이루는데 여전히 커다란 장애가 된다.
선인출은 프로세서의 연산과 주기억 장치 접근을 중첩시켜 캐쉬 미스에 의해 발생하는 부담을 줄이는 효과적인 방법이다. 특히, 다중처리기에서는 인출되는 자료의 망 지연시간과 선인출되는 자료의 망 지연시간을 중첩시켜 캐쉬 미스에 의해 발생하는 부담을 보다 많이 줄일 수 있다. 소프트웨어 및 하드웨어에 기반을 둔 여러가지 선인출 기법이 제안되었다. 소프트웨어 선인출 기법은 프로그램을 정적으로 분석하여, 프로그램 코드사이에 선인출 명령을 추가한다. 이 기법은 결과적으로 프로그램 크기를 증가시킨다. 반면에, 하드웨어 선인출 기법은 프로그램이 수행되는 상태에 따라 선인출에 관련된 기능들을 하드웨어로 조정한다. 기억 장치 접근 패턴에 규칙이 있으면, 이에 따라 자료를 선인출하는 기법이 여러 가지 제안되었지만, 이 기법은 기억 장치 접근 패턴의 규칙을 찾기 위해 복잡한 하드웨어를 필요로 한다. 캐쉬 미스시, 미스가 일어난 블럭의 다음 블럭을 선인출하는 기법은 아주 간단한 하드웨어 방식이지만, 하나의 미스시 하나의 블럭만을 선인출하므로, 미스율을 최대 반으로 밖에 줄일 수 없다.
순차적 선인출 기법은 위의 기법을 보완한 것이다. 이 기법은 미스시 d 개의 연속된 블럭을 선인출한다. 결과적으로 이 기법은 미스율을 $\frac1d$ 까지 줄일 수 있다. 하지만 이 기법은 불필요한 블럭을 선인출할 확률을 증가시킨다. 불필요한 블럭을 선인출하므로서, 전송량 및 기억장치 접근 횟수를 증가시키고, 결과적으로 주기억장치 접근 지연시간을 증가시키고 컴퓨팅 성능을 저하시킨다. 즉 순차적 선인출 기법은 미스시 선인출할 블럭의 수와 순차적 주기억 장치 접근의 평균 길이에 영향을 받는다.
이 논문에서는 순차적 주기억 장치 접근의 평균 길이와 순차적 선인출 기법의 성능과의 관계를 여러 기억장치 및 망 지연시간에 있어서 분석하고, 선인출 양을 조절하는 새로운 순차적 선인출 기법을 제안한다. 선인출 기법에 작은 테이블을 추가하여, 순차적 주기억 장치 접근이 긴 경우는 많은 블럭을 선인출하고, 순차적 주기억 장치 접근이 짧은 경우는 적은 블럭을 선인출한다. 즉 순차적 주기억 장치 접근의 길이에 따라 선인출하는 블럭의 수를 조절한다. 이 기법을 사용하므로서, 순차적 주기억 장치 접근의 평균 길이가 긴 프로그램의 수행시는 많은 블럭을 선인출하여 미스율을 크게 감소시키고, 순차적 주기억 장치 접근의 평균 길이가 짧은 프로그램의 수행시는 적은 수의 블럭을 선인출하여 불필요한 블럭이 선인출되는 것을 방지하였다.