Journal of The Korea Society of Computer and Information Vol. 22 No. 3, pp. 9-16, March

Size: px

Start display at page:

Download "Journal of The Korea Society of Computer and Information Vol. 22 No. 3, pp. 9-16, March"

원주 구
3 years ago
Views:

1 Journal of The Korea Society of Computer and Information Vol. 22 No. 3, pp. 9-16, March In recent computing systems, LRU replacement policy has been widely used because it can be simply implemented and applicable to most programs. However, if the working set size of the program is bigger than the actual cache size, LRU replacement policy may occur thrashing problem. Thrashing problem means that cache blocks are consistently replaced without re-referencing in the cache. This paper proposes a new cache management scheme to solve the thrashing problem in the second-level cache. The proposed scheme measures per set reuse frequency using EAF structure to find thrashing sets. When the cache miss occurs, it tests whether the address of the missed block is stored or not. If the address of the missed block is stored, it means that the recently evicted block is re-requested, so the reuse frequency is predicted high. In this case, the corresponding counter of the set is increased. When the counter value is bigger than the threshold value, we assume that the corresponding set shows high reuse frequency. The proposed scheme assigns the set with high reuse frequency to the additional small size cache to keep the blocks in the cache for a long time. Our experimental results show that the proposed scheme improves the IPC by 3.81% on average. 최신컴퓨팅환경에서캐쉬메모리는시스템성능에매우큰영향을미친다. 캐쉬메모리의구조를결정하는설계요소는크기, 연관방식, 교체정책등이있는데, 그중에서도교체정책은캐쉬에어떤블록들을더오래보관할지를결정하는방법으로써, 캐쉬를효율적으로사용하기위해서는효과적인교체정책이필수적으로요구된다. 교체정책은크게두가지방식으로구성된다. 첫번째는블록을캐쉬에삽입할때어떤위치로저장할것인지를결정하는삽입방식과두번째는새로운블록이삽일될때어떠한블록을교체시킬것인가를결정하는교체방식이다. 임베디드프로세서에서는구현이간단하고대부분의프로그램에적용가능한 LRU(Least Recently Used) 교체정책이널리사용되었다. LRU 교체정책은세트에있는여러블록들중에서가장오랫동안접근되지않은블록을교체시키는정책이다. LRU는시간적지역성이높아서최근에사용되었던블록들이다시사용되는빈도가높은경우에매우효과적이다. 하지만프로그램이데이터를다시사용하기까지시간이오래걸리거나프로그램에서데이터를순환적으로사용하는데그범위가캐쉬의크기보다큰경우에는 LRU가성능에좋지않은영향을미치게된다. LRU 교체기법이캐쉬의성능을저하시키는경우들중에서가장문제가되

10 Journal of The Korea Society of Computer and Information 는경우는프로그램의데이터접근범위인작업그룹의크기가캐쉬의크기보다크게되어재사용되는데이터들이 MRU 위치에서 LRU 위치까지이동한후지속적으로교체되기만할뿐적중이발생하지않아캐쉬의활용률이크게떨어지게되는경우인데, 이러한경우를캐쉬쓰래싱 (Thrashing) 이라고한다.

일반적으로캐쉬에서 LRU가효율적으로사용되는경우는재사용빈도가높은블록의수가캐쉬의크기보다적어서 A, B, C, D에대한요청이반복적으로발생하는경우재사용빈도가높은블록들이캐쉬에지속적으로보관되어대부분의요청에적중이발생하는경우이다.

2 10 Journal of The Korea Society of Computer and Information 는경우는프로그램의데이터접근범위인작업그룹의크기가캐쉬의크기보다크게되어재사용되는데이터들이 MRU 위치에서 LRU 위치까지이동한후지속적으로교체되기만할뿐적중이발생하지않아캐쉬의활용률이크게떨어지게되는경우인데, 이러한경우를캐쉬쓰래싱 (Thrashing) 이라고한다. Fig. 1. Cache Thrashing 그림 1은 LRU 교체정책을사용했을때효과적인경우와쓰래싱이발생하여 LRU가캐쉬의성능을저하시키는경우를나타낸다. 일반적으로캐쉬에서 LRU가효율적으로사용되는경우는재사용빈도가높은블록의수가캐쉬의크기보다적어서 A, B, C, D에대한요청이반복적으로발생하는경우재사용빈도가높은블록들이캐쉬에지속적으로보관되어대부분의요청에적중이발생하는경우이다. 이에반해, 쓰래싱이발생하는경우에는 A부터 I까지의블록들이반복적으로요청되면서모든블록들의재사용빈도가높지만 MRU 위치에서 LRU 위치까지이동한후차례대로교체되기만할뿐캐쉬에서적중은전혀발생시키지못하게됨으로써캐쉬활용률을심각하게저하시킨다. 캐쉬쓰래싱문제를해결하기위해서교체정책에관한많은연구가수행되었다. 쓰래싱이발생하게되면캐쉬에대한접근이대부분적중실패하게되어캐쉬의효율성이크게떨어지게되는데, 이런경우에는 LRU 교체정책처럼캐쉬에최근요청된데이터를가장오래보관하는것이아니라, 데이터중일부는오래보관하고나머지들은보관기간을짧게해주면오래보관되는데이터들중에서는적중이발생할수있어서캐쉬의효율성을향상시킬수있다. 이를위해서기존연구들에서는주소값을바탕으로블록들의재사용특성을예측하거나각블록별로재사용특성을예측하여재사용빈도가높게예측되는블록들은캐쉬에오랫동안보관될수있도록하고나머지블록들은캐쉬에서보관하지않도록하거나잠시동안만보관되도록함으로써캐쉬의효율성을향상시켰다 [1, 2]. 이처럼지금까지의연구들은대부분캐쉬에블록을삽입하는방식을바꾸어캐쉬에일부의블록만을남김으로써쓰래싱문제를해결하려고하였다. 하지만이들은 LRU 교체정책에적합한프로그램들에대해서는성능저하를발생시킬가능성이있어문제가된다. 또한이전의연구들에서캐쉬에대한접근이전체세트에대해균등하게발생하지않는다는사실을확인할수있다 [3, 4-7]. 이는대부분의프로그램에서빈번히발생하는데캐쉬에 대한접근이각세트에대해균등하게분포되지않아세트별로접근되는수가매우상이하게나타나는현상이다. 이경우전체작업그룹의크기는캐쉬의크기보다작더라도특정세트에만접근하게되어캐쉬에공간적여유가있더라도해당세트에서는지속적으로쓰래싱이발생하게된다. 그림 2는이러한현상이매우두드러지게나타나는 ammp 벤치마크의세트별충돌적중실패의 (conflict miss) 수를나타낸다. 가로축이세트의번호를나타내고세로축은적중실패수를나타내는데, 세트에따라그수가매우상이한것을확인할수있다. 본논문에서는이에착안하여 2차레벨캐쉬의쓰래싱을완화시키기위해작은크기의캐쉬를 2차레벨에추가하고쓰래싱이많이발생하는세트들을탐지하여이세트들을추가시킨캐쉬에할당함으로써쓰래싱이많이발생하고있는세트들에서재사용가능성이있는블록들이 2차레벨캐쉬에오래머무르게하는기법을제안하고자한다. Fig. 2. Number of conflict misses (Per-Set) 본논문의구성은다음과같다. 2장에서는쓰레싱문제를해결하기위해제안된기존연구들을소개한다. 3장에서는본논문에서제안하는세트별재사용빈도정보기반쓰래싱저항캐쉬관리기법을기술하고, 4장에서는모의실험결과를분석하고성능을평가한다. 마지막으로 5장에서는본논문의결론과향후연구계획에대해서기술한다. 캐쉬쓰래싱문제를해결하기위한교체정책들에대해많은연구가이루어졌다. 기존연구들은주로캐쉬블록들의특성을파악해분류한뒤분류된그룹별로재사용특성을예측하여그특성에맞게블록을삽입하는방식을바꾸는방법으로제안되었다. DIP(Dynamic Insertion Policy)[8] 는쓰래싱문제를해결

3 Reuse Information based Thrashing Resistant Cache Management Scheme 11 하기위해작업그룹중에일부만캐쉬에보관될수있도록블록삽입방식을바꾸어보관된부분에서라도적중을발생시킬수있는기법을제안하였다. 기존의 LRU는작업그룹이캐쉬크기보다크게되면블록이 MRU 위치에서 LRU 위치까지이동하면서한번도적중되지못하고교체된후다시요청되기를반복하여캐쉬의활용률이크게떨어지는데이것을방지하기위하여블록이삽입될때의위치를 LRU 위치로바꾸어대부분의블록들은 LRU위치에서곧바로캐쉬에서교체되도록하고블록이재참조되는경우에만 MRU 위치로이동시켜일부의블록들만캐쉬에보관시킬수있는 LIP(LRU Insertion Policy)[8] 또한제안되었다. 이기법에서캐쉬블록들은 LRU 위치로삽입되고재참조될때 MRU 위치로이동하게된다. 따라서새로삽입된블록이재참조되어 MRU 위치로이동하지않는한한번 MRU 위치로이동한블록들은그대로계속유지되게되므로미래에참조될가능성이없는블록들도그대로 MRU 위치에서계속유지되는문제가발생한다. 이를막기위해 BIP(Bimodal Insertion Policy)[8] 를제안하여모든블록들을 LRU 위치에삽입하지않고일정비율의블록은 MRU 위치에삽입하도록하여 MRU 위치의블록들이계속유지되지않도록할수있는방법도제안되었다. LIP와 DIP는 LRU 교체정책이적합한프로그램에서는성능을크게저하시킬수있다. 이를방지하기위하여세트샘플링기법을사용하여선택된몇개의세트를샘플링하여현재프로그램이 LRU 교체정책에잘맞는지 BIP 교체정책에잘맞는지를측정하고, 이를바탕으로캐쉬의교체정책을결정한다. 하지만이경우세트별로적중실패의비율이다르게되면전체시스템의성능이감소할가능성이있다. 시스템의모든블록에대해재사용빈도관련정보를저장하는것은너무큰메모리공간을요구하게되어사실상불가능하다. EAF에서는모든블록들을저장하지않으면서블록단위의재사용빈도예측을수행한다. 블록의재사용빈도가높다는것은블록이교체되고얼마지나지않아다시사용될확률이높다는것을나타내고재사용빈도가낮다는것은블록이교체된후다시사용되지않는다는것을나타낸다. 이를바탕으로 EAF 에서는최근캐쉬에서교체된블록들의주소들을저장하여블록들의재사용빈도를예측하는구조를제안하였다. 그림 3은 EAF의구조를나타낸다. 프로세서에서블록의요청이 D, E, F, A, B, C, D, Z의순서로발생하였다고가정한다. D블록이캐쉬에재요청되었을때해당블록은이미캐쉬에서교체된상태이기때문에적중실패가발생하게되고재사용빈도예측을위해 EAF를검사한다. D블록의경우현재 EAF에저장되어있으므로재사용빈도가높게예측된다. 이와반대로, 캐쉬에서적중실패한주소가 EAF에서존재하지않는다면, 그블록은오랫동안요청되지않다가요청된것이므로재사용빈도가낮은것으로예측된다. 이렇게블록단위로재사용빈도를예측한후, 재사용빈도가높게예측되는블록들은 MRU 위치로삽입하고그렇지않은블록들은 BIP를사용하여캐쉬에삽입한다. 하지만이와같은방법도결국교체된블록의주소를따로저장해야하므로큰크기의작업그룹을측정하기위해서는캐쉬의크기와유사한크기의저장공간을필요로하는데, 이는시스템전체블록의정보를저장하는것보다는작지만역시상당한크기의메모리공간을요구한다. EAF에서는측정가능한작업그룹의크기는줄이지않으면서필요한공간의크기를감소시키기위하여블룸필터 [10] 를사용한다. 블룸필터는특정값 (EAF에서는주소값 ) 자체를저장하는것이아니라그값의현재저장상태만을확인할수있도록하는확률적인구조이다. EAF에서는블록의주소값자체가필요한것이아니라적중실패가발생한블록이최근에교체되었는지를확인하기위해 EAF에존재하는지확인만하면되므로블룸필터를적용시켜저장공간을크게감소시킬수있다. Fig. 3. Evicted Address Filter EAF(Evicted-Address Filter)[9] 는캐쉬블록단위로재사용빈도를예측하여블록의삽입위치를결정한다. 기존의연구들은 PC(Program Counter) 값을바탕으로블록들의그룹을나누어각기다른삽입방식을선택하였다. 이경우에는각각의블록들이속해있는그룹의특성과다른특성을가지게되는경우캐쉬성능이크게저하될수있다. 이를해결하기위해서는모든블록들의재사용빈도를예측하여야하는데이를위해 본장에서는세트별재사용정보기반쓰래싱저항캐쉬관리기법을기술한다. 본논문에서는세트단위로쓰래싱을예측하고쓰래싱이높게발생되는것으로예측되는세트들에 2차레벨에추가시킨작은크기의캐쉬를할당해준다. 이를위해서는쓰래싱이발생한세트예측이필요한데, 본논문에서는 EAF[9] 에서전체캐쉬의블록단위재사용빈도예측을위해사용되었던구조를수정하여사용한다.

4 12 Journal of The Korea Society of Computer and Information EAF에서는 2차레벨캐쉬에교체된주소를저장시키기위해블룸필터를활용하였다. 즉, 캐쉬전체단위로교체된블록들의주소를모두저장하여블록들의재사용빈도를예측하였다. 본논문에서는이와같은구조를세트단위로적용한다. 블록이교체된주소를블룸필터를통해서세트단위로할당되어있는비트배열에각각저장한후각세트에서적중실패가발생한경우해당블록이세트별비트배열에저장되어있는지를검사한다. 해당세트와연관된비트배열에블록이존재한다면, 그블록은최근에교체되었지만곧바로요청되어적중실패가발생한것으로서재사용빈도가높다고예측할수있다. 이와같은방법으로세트단위의블록재사용빈도를예측하여재사용빈도가높게예측되는블록들이위치하는세트들을추가시킨작은크기의캐쉬에할당한다. 본논문에서는쓰래싱을완화시키기위하여 2차레벨에작은크기의캐쉬를추가한다. 추가된작은크기의캐쉬를효율적으로사용하기위해서는쓰래싱이가장심각하게발생하는세트들을할당하여야한다. 이를위해서 EAF에서전체캐쉬단위의교체된블록들을효율적으로저장하기위해사용되던블룸필터의구조를수정한다. 면동작이완료된다. 4-(b) 는검사동작을나타낸다. 검사는적중실패가발생한주소의재사용빈도를검사하기위하여실시되는데검사와똑같은방식으로 2개의해시함수를사용하여적중실패가발생한주소를색인으로변환시켜비트배열을접근한다. 여기서중요한점은 2개의해시함수를사용해접근한비트배열의값 2개가전부 1 이여야해당주소가블룸필터에존재한다는것이다. 따라서 (1) 의접근은블룸필터에해당주소가존재하는것이고, (2) 의접근은해당주소가존재하지않는경우이다. 마지막은초기화동작이다. 블룸필터는비트배열을사용하여데이터를저장하는데이러한비트배열을초기화해주지않으면어떤값을검사해도해당값이존재한다는결과가나오기때문이다. 본논문에서는 2가지의해시함수를사용하므로하나의데이터를저장하는데필요한비트배열의값은 2개이다. 따라서비트배열이저장할수있는주소의수는비트배열의수를 2로나눈수이며, 이수만큼의주소가저장된후에는비트배열의값을다시초기화해주어야한다. 본논문에서는이를위해블룸필터에저장된주소의숫자를세기위한카운터를사용한다. 데이터를저장하는비트배열의길이는세트별로저장할수있는교체된블록의수를나타내는것으로볼수있으며비트배열이길수록더많은블록들을저장할수있다. 본논문에서는실험에 8웨이의 2차레벨캐쉬를사용하였는데비트배열은웨이수와동일하게 8개의블록을저장할수있도록한다. 따라서저장된주소의숫자를세기위한카운터는 3비트를사용한다. Fig. 4. Bloom filter operation 이에앞서블룸필터의구조를간략하게설명하도록한다. 블룸필터는동작은 3가지로이루어진다. 그림 4는삽입과검사의 2가지블룸필터동작을나타낸다. 4-(a) 는삽입동작을나타내는데, 교체된블록의주소가결정되면이주소를 2개의해시함수를사용하여비트배열의색인으로변환시킨다. 이 2 개의색인을사용해서각비트배열의값들을 1 로세트시켜주 그림 5는 EAF와블룸필터를포함하는제안기법의전체적인동작방식을나타낸다. 세트별로불균형하게발생하는쓰래싱을해결하기위해쓰래싱이발생하는세트들을추가시킨쓰래싱완화캐쉬에할당한다. EAF 구조를사용하여측정된세트별쓰래싱발생빈도를쓰래싱카운터에저장시키고그값을기준으로쓰래싱완화캐쉬에할당시킬세트들을결정한다. 2차레벨캐쉬에서블록이교체된경우교체되는블록의주소를 EAF 구조에저장시킨다. 교체된블록의주소로 2개의해시함수를사용하여인덱스를생성시켜비트배열의해당하는위치에접근하여해당비트의값을 1 로바꿔주고블룸필터초기화를위해사용될블룸카운터값을 1증가시킨다. 그후 2차레벨캐쉬에대한요청이적중실패가되면해당주소로 2개의해시함수를사용하여 EAF 구조에접근시킬인덱스를생성시켜해당위치에접근한다. 비트배열의두값이모두 1 인경우, 해당블록이최근에교체되어블룸필터에저장되어있는것으로재사용빈도가높은블록이교체된것으로볼수있다. 따라서쓰래싱카운터에접근하여값을 1증가시켜준다. 만약쓰래싱카운터값이실험적으로도출된최적의임계값인 5를넘는경우에는해당세트를추가시킨쓰래싱완화캐쉬에할당하여쓰래싱완화캐쉬로도블록이적재될수있도록하여쓰래싱을완

5 Reuse Information based Thrashing Resistant Cache Management Scheme 13 Fig. 5. Thrashing resistant cache management scheme 화시킬수있도록한다. 쓰래싱카운터값은오래된정보를가지고있지않도록 10만사이클마다그값을 1씩감소시켜준다. 그림 6은메모리에서 2차레벨로의블록전송방식을보여주고있다. 2차레벨캐쉬세트의상태는쓰래싱이발생한세트와그렇지않은세트로나뉜다. 세트별상태를구분하기위해본논문에서는블룸필터를사용하여측정한블록별재사용빈도예측값과쓰래싱카운터를사용한다. 쓰래싱완화캐쉬는작은크기의캐쉬이므로쓰래싱이발생한세트의블록들을전부쓰래싱완화캐쉬로만적재시킨다면블록들을오래보관하지못하고계속해서교체되게될것이다. 따라서블록을 2차레벨캐쉬와쓰래싱완화캐쉬를번갈아적재시킨다. 2차레벨캐쉬에서적중실패가발생할경우블록을하나교체시키게되는데이블록은블룸필터에삽입되게되므로블룸필터의카운터값은증가하게된다. 이카운터값은블록을적재시킬때마다변하게되므로이값의최하위비트를사용하여 0인경우에는 2차레벨캐쉬로적재하고 1인경우에는쓰래싱완화캐쉬로적재하도록한다. Table 1. System Parameters System Parameter Instruction L1 Cache Instruction L1 Cache Latency Data L1 Cache Data L1 Cache Latency Unified L2 Cache Unified L2 Cache Latency 본장에서는제안된세트별재사용정보기반쓰래싱저항 캐쉬관리기법의효과를분석한다. 변경된메모리구조의성능 을평가하기위해서 SimpleScalar[11] 시뮬레이터를사용한 다. 입력벤치마크프로그램으로는 SPEC CPU2000[12] 에서 10 개의벤치마크를선정하여사용한다. 실험을위해사용한시 스템의구성변수들은표 1 과같다. Value 16K Bytes, 256 Sets, 32B Line, 2Way 1 Cycle 16K Bytes, 256 Sets, 32B Line, 2Way 1 Cycle 256K Bytes, 1024 Sets, 32B Line, 8Way 16 Cycles Fig. 6. Block transfer method 앞서기술한바와같이제안하는기법은 2차레벨에작은크기의캐쉬를추가하여 2차레벨에서의적중실패를감소시킴으로써전체적인평균메모리접근시간을줄임으로써성능을향상시키는것을목적으로한다. 따라서시스템의성능이캐쉬에영향을거의받지않는벤치마크들은제안하는기법을적용하여도성능을향상시키기가어렵다. 그러므로제안하는기법이효과적으로성능을향상시키는지확인하기위해서우선성능이캐쉬의크기에민감한벤치마크와그렇지않은벤치마크로구

14 Journal of The Korea Society of Computer and Information 분한다. 본논문에서는캐쉬의크기에민감한벤치마크와그렇지않은벤치마크들을구분짓기위하여하나의통합된캐쉬만을사용한경우에천개의명령어당적중실패 (MPKI, Misses Per Kilo Instructions) 가얼마나발생하는지를측정한다.

크게되어지속적으로적중실패가발생하다가 512KB 이상의캐쉬를사용하게되면작업그룹이캐쉬의크기보다작게되어적중실패가급격하게감소한것으로볼수있다. 나머지벤치마크들은 32KB에서캐쉬의크기를증가시킴에따라지속적으로 MPKI가감소되는것을볼수있다.

6 14 Journal of The Korea Society of Computer and Information 분한다. 본논문에서는캐쉬의크기에민감한벤치마크와그렇지않은벤치마크들을구분짓기위하여하나의통합된캐쉬만을사용한경우에천개의명령어당적중실패 (MPKI, Misses Per Kilo Instructions) 가얼마나발생하는지를측정한다. 10개의벤치마크에대해측정한결과값을 MPKI의변화율을기준으로하여캐쉬에민감한벤치마크 (CS, Cache Sensitive) 와캐쉬에민감하지않은벤치마크 (CI, Cache Insensitive) 두가지로분류한다. 그림 7과그림 8은두종류벤치마크의 MPKI를나타내고있다. 크게되어지속적으로적중실패가발생하다가 512KB 이상의캐쉬를사용하게되면작업그룹이캐쉬의크기보다작게되어적중실패가급격하게감소한것으로볼수있다. 나머지벤치마크들은 32KB에서캐쉬의크기를증가시킴에따라지속적으로 MPKI가감소되는것을볼수있다. crafty, vortex 벤치마크의경우 64KB, gcc 벤치마크의경우 128KB 이전까지급격하게감소하다가이후에는거의일정한비율로감소하는것을볼수있다. 이들은 LRU 교체정책에맞는벤치마크들로 32KB부터적중이발생하였으며캐쉬가특정크기이상이되면전체작업그룹을수용할수있어서 MPKI가일정하게유지되는것임을알수있다. 그림 8의벤치마크들은캐쉬크기가증가하는것과는관계없이 MPKI값이일정한것을볼수있는데이러한벤치마크들은캐쉬에상관없이성능이일정할것임을예측할수있다. 해당벤치마크들에는캐쉬관리기법을바꾸어도성능에미치는영향이적을것이라는것을알수있다. 실험결과를분석하기에앞서기존시스템에서 2차레벨캐쉬의크기에따른성능향상의정도를측정하여본실험의결과가기존의시스템에비해캐쉬를얼마나효율적으로사용할수있는지를비교할수있도록한다. Fig. 7. MPKI of cache sensitive benchmarks Fig. 9. Performance of cache sensitive benchmarks according to cache size Fig. 8. MPKI of cache insensitive benchmarks 그림 7은캐쉬의크기에따라성능이크게차이나는캐쉬크기에민감한벤치마크들이다. 그래프를살펴보면캐쉬크기가 32KB에서 1MB까지증가함에따라전체적으로 MPKI가감소하는추세를보이는것을볼수있다. 이중에서도특히 ammp, applu 벤치마크를살펴보면특정부분에서그래프가급격하게꺾이는것을볼수있다. 두벤치마크의경우 256KB 이전까지는 MPKI가거의일정하다가 512KB 이상의캐쉬를사용한경우에 MPKI가급격하게떨어진다. 이는 512KB보다작은크기의캐쉬를사용한경우, 작업그룹의크기가캐쉬의크기보다 Fig. 10. Performance of cache insensitive benchmarks according to cache size

7 Reuse Information based Thrashing Resistant Cache Management Scheme 15 Fig. 11. Performance of thrashing resistant cache management scheme according to thrashing relieve cache size 그림 9와그림 10은기존시스템에서 2차레벨캐쉬의크기에따른 IPC(Instruction Per Cycles) 를나타낸다. 그림 9는캐쉬크기에민감한벤치마크들의캐쉬크기에따른성능을보여주고있는데이러한벤치마크들은캐쉬의크기가증가함에따라서성능이비례하여증가하고있는것을볼수있다. 그림 10 은캐쉬크기에민감하지않은벤치마크들을보여주는데이벤치마크들은캐쉬의크기가증가하여도성능에는거의영향을받지못하는것을볼수있다. 성능이캐쉬의크기에영향을받지않는벤치마크들은캐쉬를효율적으로사용하는기법을적용한다하더라도성능향상이크지않을것이라는것을예측할수있다. 본논문에서수행하는실험에서모든벤치마크들에대해 2 차레벨캐쉬의크기는 256KB로고정하고쓰래싱완화캐쉬의크기를 4KB, 8KB, 16KB, 32KB로사용하는경우에대해성능을측정한다. 그림 11은제안된구조를사용하여성능을측정한결과를나타낸다. 좌측 5개의벤치마크는 2차레벨캐쉬의크기에민감한벤치마크들이고우측 5개의벤치마크는 2차레벨캐쉬의크기에민감하지않은벤치마크들이다. 각벤치마크별그래프에서가장좌측값은쓰래싱완화캐쉬를추가하지않고기존의 256KB의캐쉬만사용하였을때의 IPC를나타낸다. 본논문에서는쓰래싱완화캐쉬를 2차레벨에추가하여전체작업그룹중일부를 2차레벨에남겨두어적중을추가로발생시켜캐쉬의효율을증가시켜성능을향상시킨다. 캐쉬의크기에민감한벤치마크들중에서 ammp, applu 벤치마크의경우 16KB의쓰래싱완화캐쉬를사용하였을때, IPC가각각 %, 7.21% 증가함을알수있다. 이는그림 7에서볼수있듯이, 작업그룹의크기가커서지속적으로적중실패만발생하던것을작은크기의쓰래싱완화캐쉬를사용하여일부를 2 차레벨에오랫동안머무를수있게함으로써성능이향상된 것으로볼수있다. 특히, ammp 벤치마크는그림 2에서와같이세트별적중실패의수가매우상이하여크게성능이향상된것으로보인다. 16KB의쓰래싱완화캐쉬를사용할때, ammp, applu 벤치마크는기존의시스템에서거의 1MB의캐쉬를사용한것과유사한성능을나타낸다. 나머지 crafty, gcc, vortex 벤치마크들은 16KB의쓰래싱완화캐쉬를사용할때 IPC가각각 4.56%, 2.73%, 0.73% 증가한다. 그림 7에서볼수있듯이, 이벤치마크들은 LRU 교체정책에적합한벤치마크들이었는데교체정책을바꾸지않고작은크기의쓰래싱완화캐쉬를추가함으로써성능을감소시키지않고오히려추가캐쉬의공간을활용하여성능을증가시킬수있다. 나머지오른쪽의 5개의벤치마크들은캐쉬의크기에민감하지않은벤치마크들로서예상대로모든벤치마크들에서쓰래싱완화캐쉬에따른성능의변화가없음을확인할수있다. 본논문에서는 2차레벨캐쉬에서발생하는쓰래싱문제를해결하기위해 2차레벨에쓰래싱을완화시키기위한작은크기를캐쉬를추가하였으며이를포함한캐쉬관리기법을제안하였다. 제안하는기법은블룸필터를사용하여세트별로교체되는블록이재사용되는수를측정하여그값이임계값을넘기는경우에만해당세트를쓰래싱완화캐쉬로할당하여쓰래싱이가장문제가되는세트들에서작업그룹의일부만이라도남길수있도록하여쓰래싱을완화한다. 실험을통해확인한결과, 캐쉬크기에민감한쓰래싱이많이발생하는벤치마크들에서는 16KB의쓰래싱완화캐쉬를사용한경우평균 3.81% 의

16 Journal of The Korea Society of Computer and Information IPC를향상시키는것을확인하였다. 제안하는기법을쓰래싱이많이발생하는캐쉬크기에민감한프로그램들에적용하는경우에는성능을크게향상시킬수있을것으로예상된다.

Emer, SHiP: Signature-Based Hit Predictor for High Performance Caching, In Proceedings of the International Symposium on Microarchitecture (MICRO), pp. 430-441, 2011. [2] G. S. Tyson, M. K.

8 16 Journal of The Korea Society of Computer and Information IPC를향상시키는것을확인하였다. 제안하는기법을쓰래싱이많이발생하는캐쉬크기에민감한프로그램들에적용하는경우에는성능을크게향상시킬수있을것으로예상된다. 향후에는캐쉬크기에민감하지않은벤치마크들까지포함하여모든프로그램에대해적용하여성능을향상시킬수있는캐쉬관리기법을연구하고자한다. [1] C. J. Wu, A. Jaleel, W. Hasenplaugh, M. Martonosi, S. C. Steely, Jr., and J. Emer, SHiP: Signature-Based Hit Predictor for High Performance Caching, In Proceedings of the International Symposium on Microarchitecture (MICRO), pp , [2] G. S. Tyson, M. K. Farrens, J. Matthews, and A. R. Pleszkun, A Modified approach to data cache management, In Proceedings of the International Symposium on Microarchitecture (MICRO), pp , [3] D. Rolán, B. B. Fraguela, and R. Doallo, Adaptive Line Placement with the Set Balancing Cache, In Proceedings of the International Symposium on Microarchitecture (MICRO), pp , [4] J. Peir, Y. Lee, and W. W. Hsu, Capturing Dynamic Memory Reference Behavior with Adaptive Cache Topology, In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp , [5] M. K. Qureshi, D. Thompson, and Y. N. Patt, The V-Way Cache: Demand Based Associativity via Global Replacement, In Proceedings of International Symposium on Computer Architecture (ISCA), pp , [6] J. M. Kim and S. W. Chung, Group-Based Replacement Algorithm to Reduce Cache Miss in Last Level Cache, Journal of The Korea Society of Computer and Information, Vol. 6, No. 5, pp , Oct [7] D. O. Son, H. J. Choi, J. M. Kim., and C. H. Kim, Core-aware Cache Replacement Policy for Reconfigurable Last Level Cache, Journal of The Korea Society of Computer and Information, Vol. 18, No. 11, pp. 1-12, Nov [8] M. K. Qureshi, A. Jaleel, Y. N. Patt, S. C. Steely, Jr., and J. Emer, Adaptive Insertion Policies for High Performance Caching, In Proceedings of International Symposium on Computer Architecture (ISCA), pp , [9] V. Seshadri, O. Mutlu, M. A. Kozuch, and T. C. Mowry, The Evicted-Address Filter: A Unified Mechanism to Address Both Cache Pollution and Thrashing, In Proceedings of International Conference on Parallel Architectures and Compilation Techniques (PACT), pp , [10] B. H. Bloom, Space/time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM, pp , [11] T. Austin, E. Larson, and D. Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, Vol.35, No.2, pp , [12] SPEC CPU2000 Benchmarks, Authors Gyu Yeon Sim received the B.S degree and M.S in electronics and computer engineering from Chonnam National University, Gwangju, Korea in 2015 and 2017 respectively. His research interests include computer architecture, multiprocessors and embedded systems. Cheol Hong Kim received the B.S. degree in Computer Engineering from Seoul National University, Seoul, Korea in 1998 and M.S. degree in He received the Ph.D. in Electrical and Computer Engineering from Seoul National University in He worked as a senior engineer for SoC Laboratory in Samsung Electronics, Korea from Dec to Jan Now is working as an Associate Professor at School of Electronics and Computer Engineering, Chonnam National University, Korea. His research interests include embedded systems, mobile systems, computer architecture, SoC design, low power systems, and multiprocessors.

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA 논문 10-35-03-03 한국통신학회논문지 '10-03 Vol. 35 No. 3 원활한 채널 변경을 지원하는 효율적인 IPTV 채널 관리 알고리즘 준회원 주 현 철*, 정회원 송 황 준* Effective IPTV Channel Control Algorithm Supporting Smooth Channel Zapping HyunChul Joo* Associate