Reducing cache misses without increasing cache associativity is critical for reducing the power consumption and cache access time. This paper has focused on the stack of a program which often occupies more than half of total memory accesses[1]. This paper, as a result, proposes so-called dynamic stack allocation where the stack pointer is shifted at run time to a memory location which is expected to cause least number of cache misses. We implemented the proposed scheme using so-called Dynamic Stack Allocator(DSA) which consists of Cache Miss Predictor(CMP) to compute cache miss probability based on Least Recently Used(LRU) policy and Stack Pointer Manger(SPM) to manage multiple stack locations. We also verified the proposed scheme with both FPGA and ASIC by using iNCITE[2] and Dong-Bu electronics 0.18um process[3], respectively. Experimental results show that dynamic stack allocation significantly reduces cache misses from 1% to 42% in various benchmarks with relatively small power consumption and no extra delay.
캐쉬의 성능은 캐쉬 미스 비율에 의해 크게 결정된다. 일반적으로 캐쉬 미스 비율을 줄이기 위해 high associativity를 가지는 캐쉬를 사용한다. 하지만, associativity를 늘리면 전력 소모 및 캐쉬에 접근하는 데 걸리는 시간 또한 늘어나 고속 및 저전력 시스템 구현이 어렵다.
본 논문에서는 프로그램 실행 시에 메모리 영역 중 스택의 참조 빈도가 가장 큰 스택에 주목하고, 캐쉬 미스 비율을 줄이기 위해 "캐쉬 미스를 고려한 동적 스택 할당"을 제안하였다. 이 제안의 핵심은 스택 할당 시에 캐쉬 미스가 가장 적게 발생할 것이라고 예측되는 영역을 프로그램에 할당하는 것이다. 이것을 위해 프로그램 실행 중에 각 캐쉬 행에서의 미스 발생 빈도를 일정 주기마다 실시간으로 계산하는 것이 필요하다.
우리는 제안의 구현을 위해 Dynamic Stack Allocator(DSA)를 설계하였다.DSA는 실행 중에 캐쉬를 관찰하며 캐쉬 각 행에서의 미스 발생 확률을 실시간으로 계산하는 Cache Miss Predictor(CMP)와 스택 할당 시에 미스 발생 확률이 가장 적은 영역을 할당하기 위해 스택 포인터를 조정하는 Stack Pointer Manager(SPM)으로 구성되어 있다. SPM이 가장 좋은 영역을 찾기 위해 스택 전체를 탐색하는 것은 상당한 시간을 요구한다. 이를 줄이기 위해 우리는 다수의 스택을 사용하였다. 각 스택의 할당 방법은 기존의 LIFO와 같다. 그러므로 스택 할당 시에 SPM은 각 스택의 미스 발생 확률을 계산하고 비교하여 가장 낮은 확률을 가지는 스택을 프로그램에 할당한다. 이는 단지 스택 개수만큼의 계산을 필요로 한다.
DSA는 상위레벨 모델링, FPGA 에뮬레이션, ASIC 구현(with OpenRISC 1200 microprocessor)의 단계를 거치며 검증되었다. 검증 결과 DSA를 적용한 direct-mapped 캐쉬가 2-way set associative 캐쉬보다 전력 소모 및 캐쉬 접근 시간이 더 적으면서 캐쉬 미스 비율 또한 더 줄일 수 있었다. 또한 DSA는 associativity에 상관 없이 적용되어 캐쉬 미스 비율을 감소시킨다. ASIC 구현 결과 DSA는 전체 칩 면적에서 약 1%의 면적으로 구현되었다.
