Cache Miss-Aware Dynamic Stack Allocation

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 (Calder, et. al., 1998). 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 manager (SPM) to manage multiple stack locations. We also verified the proposed scheme with both FPGA and ASIC by using iNCITE and Dong-Bu electronics 0.18mum process, respectively. Experimental results show that dynamic stack allocation significantly reduces cache misses from 4% to 42% in various benchmarks with relatively small power consumption and no extra delay.