데이타 캐시의 활용도를 높이는 동적 선인출 필터링 기법 = Dynamic Prefetch Filtering Schemes to enhance Utilization of Data Cache

다국어 초록 (Multilingual Abstract)

Memory reference instructions such as loads or stores are critical factors that limit the processing power of processor. The prefetching technique is an effective way to reduce the latency caused from memory access. However, excessively aggressive prefetch leads to cache pollution so as to cancel out the advantage of prefetch. In this study, four filtering schemes have been compared and evaluated which dynamically decide whether to begin prefetch after referring a filtering table to decrease cache pollution. First, A bi-states scheme has been shown to analyze the lock problem of the conventional scheme, this scheme such as conventional scheme used to be N:1 mapping, but it has the two state to 1bit value of each entries. A complete state scheme has been introduced to be used as a reference for the comparative study. A block address lookup scheme has been proposed as the main idea of this paper which exhibits the most exact filtering performance. This scheme has a length of the table the same as the bi-states scheme, the contents of each entry have the fields the same as the complete state scheme recently, never referenced data block address has been 1:1 mapping a entry of the filter table. Experimental results from commonly used general benchmarks and multimedia programs show that average cache miss ratio have been decreased by 10.5% for the block address lookup scheme(BAL) compare to conventional dynamic filter scheme(2-bitSC).

국문 초록 (Abstract)

Load/store와 같은 메모리 참조 명령어는 프로세서의 고속 수행을 방해하는 주요인이다. 캐시 선인출 기법은 메모리 참조에 따른 지연시간을 줄이는 효과적인 방법이다. 그러나 너무 적극적으로 선인출할 경우에 캐시 오염을 유발시켜 선인출에 의한 장점을 상쇄시킨다. 본 연구에서는 캐시의 오염을 줄이기 위해 동적으로 필터 테이블을 참조하여 선인출 명령을 수행할 지의 여부를 결정하는 네 가지 필터링 기법들을 비교 평가한다. 먼저 기존 연구에서의 문제점을 분석하기 위해 이진 상태 기법을 보였는데, 이 기법은 기존 연구와 같이 N:1 매핑을 사용하는 반면, 각 엔트리의 값을 1비트로 하여 두 가지 상태값을 갖도록 하였다. 비교 연구를 위해 완전 상태 기법을 제시하여 비교 기준으로 사용하였다. 마지막으로 본 논문의 주 아이디어인 정교한 필터링을 위한 블록주소 참조 기법을 제안하였다. 이 기법은 이진 상태 기법과 같은 테이블 길이를 가지며, 각 엔트리의 내용은 완전 상태 기법과 같은 항목을 가지도록 하여 최근에 미 사용된 데이타의 블록주소가 필터 테이블의 하나의 엔트리와 대응되도록 1:1 매핑을 하였다. 일반적으로 많이 사용되는 일반 벤치마크 프로그램과 멀티미디어 벤치마크 프로그램들에 대하여 실험한 결과, 제안한 블록주소 참조 기법(BAL)이 기존 연구인 동적 필터 기법(2-bitSC)과 비교하여 캐시 미스율이 10.5%감소하였다.

참고문헌 (Reference)

• 1 Media benchmark program, "http://cares.icsl.ucla.edu/ appications.html"
• 2 "SpecInt 2000 benchmark program"
• 3 D. Joseph, "Prefetching Using Markov Predictors" 48 (48): 1999
• 4 D. Joshep, "Prefetching Using Markov Predictors" 252-263, 1997
• 5 N. P. Jouppi, "Improving directed-mapped cache performance by the addition of a small fully- associative cache and prefetch buffers" 364-373, 1990
• 6 X. Zhuang, "Hardware-based Cache Pollution Filtering Mechanism for Xggressive Prefetches" 286-293, 2003
• 7 T-Fu Chen, "Effective Hardware- Based data prefetching for High-Performance Processors" 44 (44): 609-623, 1995
• 8 M. D. Hill, "Dinero Ⅲ Cache Simulator" Department Computer Science 1990
• 9 G. Hariprakash, "DSTRIDE : Data-cache miss-address-based stride prefetching scheme for multimedia processors" 62-70, 2001
• 10 Y. Solihin, "Correlation Prefetching with a User-Level Memory Thread" 14 (14): 2003
• 11 A. J. Smith, "Cache Memories" ACM Computing Surveys 473-530, 1982
• 12 J. L. Baer, "An effective on-chip preloading scheme to reduce data access penalty" 176-186, 1991
• 13 J. H. Lee, "An Intelligent Cache System with Hardware Prefetching for High Performance" 52 (52): 2003
• 14 A. Srivastava, "ATOM : A System for Building Customized Program Analysis Tools" 196-205, 1994
• 15 V. Srinivasan, "A Prefetch Taxonomy" 53 (53): 126-140, 2004
• 16 J. Kim, "A Framework for Data Prefetching using Off-line Training of Markovian Predictors" 340-347, 2002