2020. 7. 22. 15:46ㆍComputer Architecture/Cache security
Authors: Moinuddin K. Qureshi Yale N. Patt Department of Electrical and Computer Engineering The University of Texas at Austin {moin, patt}@hps.utexas.edu
[Abstract]
This paper investigates the problem of partitioning a shared cache between multiple concurrently executing applications.
This paper proposes utility-based cache partitioning (UCP), a low-overhead, runtime mechanism that partitions a shared cache between multiple applications depending on the reduction in cache misses that each application is likely to obtain for a given amount of cache resources.
<모르는 부분>
- Application's utility가 무엇인가?
[1.Introduction]
최근 processor들은 multiple applications (or threads)를 수행하기 위해 single chip 안에 multiple core를 가지고 있다.
이러한 multicore architecture의 성능을 높이기 위한 방법 중 하나는 largest level on-chip cache를 효율적으로 관리하는 것이다.
largest level on-chip cache를 효율적으로 관리하여 off-chip accesses를 줄이는 것이다.
해당 논문은 multiple competing applications 사이에서 shared largest-level on-chip cahce를 partitioning하는 것의 문제점에 대해 조사한다.
원래 on-chip cache는 LRU(or an approximation of LRU)를 replacement decision의 policy로 사용한다.
이 LRU는 competing applications 사이의 shared cache의 partitioning에도 관여하는데, demand basis로써, demand에 비례하여 cache resource가 각 application에 배정된다.
하지만, 이렇게 배정받은 cache resource로 application이 갖는 benefit은 demand for cache resource와 직접적인 연관이 없을 수 있다.
* 여기서 benefit: miss수 감소 혹은 성능 개선의 효과
즉, 이렇게 배정받은 cache resource가 benefit의 향상으로 이어지지 않을 수 있다.
한 예로, streaming application을 든다.
streaming application은 large number of unique cache blocks을 접근하지만, 이러한 cache block들의 재사용률은 만약 application의 working set의 크기가 cache size보다 크다면 높지 않게된다. (working set은 cache size보다 훨씬 더 넓은 지역에서 작동하기 때문)
이러한 경우, application은 high demand를 가져 더 많은 cache resource를 가지게 되지만, 성능향상으로는 직접적으로 이어지지 않는다.
따라서, 논문에서는 다음과 같이 표현한다.
"Thus, it makes sense to partition the cache based on how much the application is likely to benefit from the cache rather than the application's demand for the cache."
cache resource가 필요한 만큼 shared cache를 partitioning하지 않고 해당 application이 cache로 부터 얻을 수 있는 benefit에 따라 partitioning하는 것이 더 효율적이라는 것이다.
<Problem with LRU-based partitioning>
Figure 1-(a).
궁극적으로 증가하는 cache size에 따른 Miss수를 살펴봄.
x축: # of ways --> set을 고정하고 ways 수를 늘려가며 cache size를 증가시킴.
y축: MPKI
baseline L2 cache: 16-way, 1MB, 1024sets.
빨간색의 vpr(SPEC benchmark)의 경우, cache size가 증가함에 따라 miss rate가 단조롭게 감소한다.
하지만 파란색의 equake의 경우, 3-ways를 초과하는 순간 더이상 cache resource로 부터 miss rate 감소라는 beneift을 얻지 못한다.
vpr과 equake를 baseline 1MB 16-way cache를 공유하고 LRU policy를 가지는 dual-core system에서 돌린다면, 평균적으로 vpr은 9-ways를 갖고, equake는 7-ways를 갖는다고 한다. (vpr은 equake보다 더 많은 cache resource를 확보하였으므로 성능향상이 있긴 있겠지만 equake의 경우 3-ways이상부터는 n-ways에 비례하여 어떠한 benefit효과도 얻을 수 없다.)
만약 cache partitioning이 utility of cache resource based(UTIL)로 이루어졌다면, equake는 3-ways만 갖고, vpr은 13-ways를 가질 수 있을 것이다.
이 방식으로는 equake는 전혀 손해볼 일이 없다. 자신은 3-way이든 7-way든 miss rate가 변하지 않으므로, 자신의 ways수를 vpr에 양보함으로써 vpr은 더 큰 성능향상의 이득을 얻는다. (즉, 패자가 없으므로 서로 win-win이다.)
Figure 1-(b).
cache를 utility information을 base로 partitioning하면 CPI가 줄어듦을 보여준다.
* CPI가 감소할수록 성능은 향상.
vpr의 경우 equake의 CPI에 영향을 주지 않으면서 CPI가 2-->1.5로.
결국, equake는 성능에 아무런 영향을 받지않고, vpr의 성능이 좋아져서 UTIL의 방법으로는 dure-core system에서 전체적인 성능향상의 효과를 얻을 수 있음을 알 수 있다.
application's utility for the cache resource를 base로 cache를 partitioning하기 위해 논문에서는 UCP(Utility-Based Cache Partitioning)을 제안한다.
UCP의 핵심은, UCP는 runtime에 모든 competing application에서 utility of cache resource 정보를 얻을 수 있다는 것이다. (by monitoring circuits)
UMON(utility monitoring) circuits는 UCP의 효율을 위해 not hardware-intensive하거나 power-hungry하다.
UMON circuit이 모은 정보는 partitioning algorithm이 얼마만큼 cache를 partitioning 해줄지를 결정하는 것에 사용된다.
UCP는 LRU-based cache partitioning보다 더 높은 성능을 보인다. dual-core system에서는 23%까지 평균적으로는 11%의 성능향상을 보인다.
Section 6에서는 Lookahead Algorithm을 이용하여 application의 수가 많아 지면서 partitioning해야하는 부분이 많아짐에 따라 효과적인 partitioning decisions을 추가로 제안한다.
[2. Motivation and Background]
cache size가 달라짐에 따라 utility of cache resources for application은 직접적으로 miss수의 변화와 관련되기에 메인 메모리의 접근 횟수와 관련되어 application의 성능향상으로 이어질 수 있다.
위의 그림은 SPEC benchmark별 miss와 CPI를 나타내는 그래프다.
application마다 utility of cache resource는 다르다.
위의 그래프에 나타난 benchmark(application) 15개를 세개의 카테고리로 나누었다.(1층, 2층, 3층)
카테고리를 나눈 기준은 way수를 1~16으로 증가함(cache size가 증가함)에 따라 얻는 이득이다.
1층은 Do not benefit significantly as the cache size is incread from 1 way to 16 ways 이다. --> low utility
1층의 원인:
1. data set이 cache size보다 크다. (e.g., mcf)
2. large number of complusory misses (e.g., gap)
2층은 continue to benefit이다. --> high utility
3층은 benefit significantly as the cache size is increased from 1way to 8 ways.
3층의 원인: have a small working set that fits in a small size cache. 따라서, 8 way 이상에서는 성능의 향상이 일어나지 않는다.
--> saturating utility
만약, 1층의 application 중 2개의 application을 동시에 실행하면, 그들 각각의 성능은 cache resource에 영향을 받지 않는다.
만약, 3층의 application 중 2개의 application을 동시에 실행하면, cache resource는 그들의 성능에 영향을 미칠 것이다.
만약 saturating utility application + low utility application 을 동시에 실행하면, cache resource가 saturating utility application을 support할 만큼 배정되지 않을 수 있다.
또한 Figure 2는 대부분의 경우, miss의 감소는 CPI의 감소와 연관있음을 알 수 있다.
따라서, miss 수 감소를 cache partitioning decision을 결정하는 것에 이용할 수 있다. (cache miss가 CPI, 성능과 연관)
본 논문에서는 Utility of increasing the number of ways from a to b를 다음과 같이 정의한다.
a,b : # of ways
[3. Utility-Based Cache Partitioning]
[3.1 Framework]
UMON: utility monitoring(UMON) circuit
partitioning algorithm은 UMON이 모은 정보(자신의 core의 application의 utility information for all the ways in the cache)를 추합하여 each core에 배정할 way의 수를 결정한다.
[3.2 Utility Monitors(UMON)]
UMON은 application이 요구하는 mechanism을 monitoring하여 모든 가능한 way 수에 따른 miss수를 조사한다.
baseline 16-way cache라면, way를 1개, 2개, ~, 16개씩 배정하면서 miss수를 조사한다.
이러한 Stack algorithm을 아래의 그림으로 설명한다.
간단히 4-way에 관한 example이다. 각 CTR POS 가 way이다.
CTR: Counter
POS: Position
Position 0은 MRU position이고, POS 3은 LUR position이다.
오른쪽 (b)의 Value는 해당 position에서의 hit number이며, (b)의 표에는 전체 misses의 수가 나와있으며, 4-way에서는 miss수가 25개인 것을 알 수 있다.
만약 여기서 way수를 하나줄여서 3-way로 만든다면 MISSES + CTR POS 3 = 35의 miss수가 나오며,
2-way 의 경우, MISSES + CTR POS 3 + CTR POS 2 = 50 이 나온다.
즉, 먼저 큰 number의 way를 가졌을 때의 position에서의 hit value를 알면, 그 보다 더 작은 way를 가졌을 때의 전체 miss 수를 알 수 있는 것이다.
ATD: Auxiliary Tag Directory
UMON은 utility of each way를 tracking하기 위해 ATD와 hit counters를 사용한다.
첫 번째 그림은 UMON-local이다.
하지만 이 모델은 각 set 마다, line마다 hit counter와 tag entry가 필요하므로 overhead가 크다.
이를 보완하기 위해 두 번째 UMON-global이 있다.
set마다 hit counter를 group화 시켰다.
하지만 tag entry는 그룹화 하지 않고 UMON-local과 똑같다.
[3.3 Reducing Storage Overhead Using DSS]
UMON-global도 여전히 overhead가 남아 있기 때문에, DSS(Dynamic Set Sampling)을 사용한다.
DSS의 핵심은 전체 cache의 behavior을 few set으로 sampling한다는 것이다.
--> UMON-global의 hit counter information을 sampling few sets으로 appoximate한다.
Figure 5의 세 번째 그림이다.
UMON-DSS 모델이다.
그렇다면 과연 몇개의 sampling이 필요한지는 5.4에서 다루며, UMON-DSS와 UMON-global의 성능을 먼저 다음에서 비교한다.
[3.4 Analytical Model for Dynamic Set Sampling]
application A, B competing for a cache containing S sets.
a(i): A의 # of ways, given set i
application A에 UMON-global에 의해 배정된 ways 수를 다음과 같이 정할 수 있는데, 즉, UMON-global은 모든 set에 동일한 중요도를 주고 그저 a(i)의 평균을 Ug로 배정한다고 아래와 같이 정한다.
n: UMON-DSS에 의해 random하게 선택된 set의 수
u_s: UMON-DSS로 A에 배정된 way의 수
qnstksdms a(i) across all the sets이다.
다음의 식은 Chebyshev's inequality이다.
위 Chevyshev's inequality식으로 인해,sample되는 set의 lower bound 개수를 알 수 있다. (최소)
위 그래프 결과로 32 sets를 UMON-DSS의 sample된 set의 개수로 정한다.
앞으로 UMON=UMON-DSS이다.
[3.5 Partitioing Algorithm]
Partitioing Algorithm은 각각의 application(core)에서 UMON-circuit(UMON-DSS)에서 hit counter를 읽는다.
partitioing Algorithm은 전체 miss 수를 줄이려고 한다.
가장 큰 miss 수를 줄이면 결국 combined utility를 maximizing하는 것과 같다.
UA, UB를 각 application의 utility function이라 한다.
Utot(a): combined utility (U_tot)는 다음과 같다.
결국 U_tot 를 max하는 partition을 구하는 것이다.
[3.6 Changes to Replacement Policy]
way partitioning을 구현하기 위해 각 block에는 tag-store entry가 저장
cache miss가 발생했을 시, replacement engine은 miss가 일어난 application의 cache block 수를 기록한다.
[4. Experimental Methodology]
[4.1 Configuration]
baseline으로 L2 cache는 모든 processor core에 공유되며 LRu replacement를 사용한다. 따라서, L2 cache는 demand basis에 따라 competing cores에 prtitioned 된다.
더 자세한 baseline은 아래와 같다.
[4.2 Metrics]
IPC_i: 동시에 돌아가는 application 중 i번째 application의 IPC
Single IPC_i: i번째 application이 홀로 돌아갈때의 IPC
N개의 thread가 동시에 실행되고 있다면 세개의 emtrics는 위와 같다.
Weighted Speedup: 실행 시간의 감소를 나타낸다. --> multicore configruation에서의 performance를 나타내는 수치로 간주한다.
IPC_sum: 시스템의 처리량을 나타낸다. but it can be unfair to a low IPC application.
IPC_norm_hmean: 공정성과 성능사이의 균형에 관한 metric이다.
[4.3 Benchmarks]
SPEC CPU2000의 benchmark들을 사용하였으며 각 벤치마크들은 250M instruction을 수행한다.
표에 보이듯이 2개의 benchmakr들을 묶어서 dual-core system에 돌렸으며, 이를 통해 one multiprogrammed workload를 수행하여 이들을 5개의 카테고리로 나누었다. 나눈 기준은 Weighted Speedup을 기준으로 Type A,B,C,D,E로 나누었다.
[5 Results and Analysis]
[5.1 Performance on Weighted Speedup Metric]
