Low Cost Working Set Size Tracking

Low Cost Working Set Size Tracking

Weiming Zhao1, Xinxin Jin2, Zhenlin Wang1, Xiaolin Wang2, Yingwei Luo2, and Xiaoming Li2

1Dept. of Computer Science, Michigan Technological University

2Dept. of Computer Science and Technology, Peking University

Abstract

메모리자원을 효율적으로 관리 하기 위해서는 실행시간에 에플리케이션 or 시스템의 메모리 수요를 알아야 한다.

널리 사용되는 접근 방법중 LRU 구조 기반의 miss ratio curve(MRC)가 있다. 이것은 현제WSS(working set size)뿐만아니라 타겟 에 할당된 메모리와 성능 과의 관계도 나타낸다.

하지만 LRU MRC monitoring cost는 꽤 있다. 기존의 오버해드를 줄일수 있는 방법으로 AVL tree based LRU structure and dynamic hot set sizing있지만 여전히 평균 16%의 높은 오버해드가 존재 한다.

대부분의 프로그램의 WSS가 안정적인 순간이 대부분의 시간을 차지 한다는 통찰을 이용하여 이들은 intermittent tracking scheme 를 고안 하였다. 이것은 stable상태를 예측하여 일시적으 메모리 수요 tracking끈다. 이것은  hardware performance counters을 사용하여 중대한 메모리의수요가 변화 기 예상될 때 memory tracking다시 동작 한다.

실험 결과 memory tracking을 끌수 있는 구간이 전체 실행 시간중의 82%에 달 하였다. 그리고 정확도의 손실은 4%에 그쳤다. 가장 중요한것은 이 intermittent tracking scheme 는 기존의 최적화 방법인 AVL-tree based LRU structure and dynamic hot set sizing과 같이 사용이 가능하다. tree 방법을 같이 사용할 경우 2% 오버헤드 만이 발생하였다. 결국 이들은 가상머신의 성능을 1.85향상 시키는데 성공하였다. 

1 Introduction

메모리 할당량과 성능의 상관관계는 메모리 메니지 먼트의 필수적인 사항이다.

그중 가장 널리 사용되는 방법에 MRC가 있다 이건 단순히 WSS만 알 수 있는 것이아니라 메모리 할당에 따른 성능에 대하여 알 수 있다. 

하지만 이점을 뒤 덮을만한 오버헤드가 존재 한다 씨피티 바운드의 특정 상황에서는 실행 시간이 1.78배 늘어 나게 된다. 

이 노문은 low cost working set size tracking approach를 제안한다. We have implemented an AVL-based LRU structure and dynamic hot set sizing (DHS)to lower the tracking overhead.However, our experiments show that it is still as high as 16% on average. However, our experiments show that it is still as high as 16% on average.
프로그램의 phase behavior 를 활용하여 이들은 더 나은 디자인 intermittent memory tracking(IMT)를 제안 하였다. 이것은 상당히 오버헤드를 떨어 뜨렸으며 그러면서 적확성도 조금 떨어졌다. 

이 아이디어는 프로그램을 실행 단계에 따라 나눌 수 있다는 사실에 근거 한다. 

이는 각각의 단계의 메모리 수요가 상대적으로 안정적이라는 사실이다 (참조 논문에 근거한 이야기이다.)

따라서 시스템이나 프로세서의 phase의 상태를 예측하여 일시적은로 tracking off하여 tracking를 오버헤드를 줄일 수 있다. 나중에 단계의 변화가 예상이 되면 다시 tracking을 하게 된다. 

The key challenge is to predict phase changes when memory tracking is off.

이들은 메모리 수요의 안정성과 밀접한 영향이 있는 하드웨어 이벤트인 data TLB misses, and L1 and L2 cache misses. 관찰한다. 

이러한 하드웨어 이벤트들을 통하여 phase의 변화를 예측하여 tracking off를 하였다. 

 DTLB and cache-level events show much higher fluctuations (noise) than memory demands 이것은 phase 예측의 정확성의 도전이 된다. 이 문제를 이들은 quick self adaptive mechanism을 만들어서 해결 합니다. 이것은 threshold 값을 정하는 것입니다. 

실험 결과 총 실행 시간중 82%동안 tracking off 할 수 있었고 정확도는 3.9%떨어 지게 되었다. 

2 Background and Related Work

2.1 Working Set and Miss Ratio Curve

이전의 메모리 예측 방법중 MRC가 최고다 이유는 WSS예측 뿐만 아니라 성능에 대한 평가도 가능하기 때문이다. 

수많은 기존의 연구가 있어지만 아직도 오버헤드에 대한 문제가 잔존 하고 있다 . //이전 연구를 다 공격하는 자신감

2.2 Phase Prediction

대부분의 프로그램들은 단계적인 실행 흐름을 보인다. IPC, 분기예측 , 메모리 버근 패턴 등등 이것은 단계는 대부분 안정적이지만 단계간의 변화에 보통 파격적인 변화가 발생하게 된다. 

P. J. Denning. Working sets past and present. IEEE Transactions on Software Engineering, SE-6(1), 1980.

X. Shen, Y. Zhong, and C. Ding. Locality phase prediction. In ASPLOS’04, 2004.

이러한 단계 변경 단계를 찾는 방법으로 L2캐시의 미스율를 잡는 방법이 있다. 

3 Intermittent Memory Tracking

Most programs show typical phasing behavior in terms of memory demands. 단계 안에서는 WSS이 거의 일정하게 유지가 된다. 

This inspired us to temporarily disable memory tracking when the monitored program enters a stable phase and re-enable it when a new phase is encountered.Through this approach, the overhead can be substantially lowered. However, when memory tracking is off, the memory tracking mechanism itself is unable to detect phase transitions anymore. 그러므로 an alternative

method is required to wake up memory tracking when it predicts a phase change.

이들은 단계의 변화가 WSS가 급격한 변화가 생길 때 하드웨어 이벤트인 TLB misses, L2 misses와 관련 있다는 것을 찾았다. 또한 WSS가 안정기에 들어 갈 때또한 이러한 하드웨어 이벤트도 안전한 상태를 가진다. 

이러한 이벤트들은 can be monitored by special registers (Performance Monitor Counters, PMCs) 최신의 프로세서에는 왠만하면 있다.그리고 오버해드 또한 무시할만한 수준이다.  // 스팍에도 있는지 확인하기 

그러면 이제 문제는 임의의 변동 phase change를 구별하는 것입니다.

First, a moving average filter is applied for signal de-noising.

Let vi denote the sampled value (WSS or the number of occurrences of some hard ware event) during ith time interval. We pick f(i) =(vi + vi−1 + . . . + vi−k+1)/k as the filtering function to smooth the sampled values, in which k is the filtering parameter, an empirical value. 충분한 데이터가 쌓이면 // 논문에 공식 참고 

err_r는 현재 샘플링 값과 그리고 원도우안의 history data 값 간의 상대적인 차이이다. 

err_a는 핸재 샘플링 값과 그리고 원도우안의 history data 값 간의 절대적인 차이이다. 

만약 err_r ∈ [1−T,1+T] 있으면 안정적인 단계라고 판단한다. 만약 아니라면 새로운 단계로 진입한다고 생각한다. 진입하는 경우 이전의 데이터들은 초기화 된다. 

T는 threshhold 값이다. 

Fixed-Threshold Phase Detection

T is the key parameter in phase detection.We first propose a scheme that uses a fixed T.One phase detector, based on past WSS, checks if the memory demands reach a stable state so the WSS tracking can be turned off. The other detector uses PMC values to check if a new phase is seen sothe WSS tracking should be woken up.

// 하나의 디텍터는 이전WSS에 메모리 수요가 얼마나 안정적인지 판단하여 turn off 하는 것이고 

// 하나는 PCM을 일어서 새로운 단계의 진입을 감지하여 turn on 하는 것이다. 

T값이 작을 수 록 정확도 손실이 줄어든다. (이들의 시험은 0.05로 하였다.)

err_a또한 메모리 tracking의 가이드로 사용할 수 있다. For example, if memory tracking is at a MB granularity, then as long as 

err_a < 1MB, WSS can still be assumed in a stable state even when err_r > T.

너무 엄격한 검사는 성능에 안좋을 수 있다. T가 커지면 허용 범위가 작아진다. 

Adaptive-Threshold Phase Detection

To improve upon fixed-threshold phase detection, we propose a self adaptive scheme which adjusts T dynamically to achieve better performance. The key is to feed the current stability of WSS back to the hardware performance phase detector to construct a closed-loop control system 그림 1과 같은 구조이다.   

Initially, the PMC-based phase detector can use the same threshold as used in fixed-threshold phase detection. When memory tracking is on, its current stability is computed and compared with the PMC-based phase detector’s decision. 만약 결과가 일치하는 경우 아무것도 변경 되지 않는다. 만약 현재 메모리 수요가 안정적인 경우 PCM 바탕의 검출기가 반대의 결정을 할경우 (err_r >  T) 이것은 현재 threshold 가 너무 타이트 하다는 것이다. As a result, its T is relaxed to its current err_r.

Next time, with increased T, the PMC-based detector will most likely find that the system enters a “stable” state and thus turn off memory tracking. On the contrary, if the current memory demands are unstable, while the PMC-based phase detector assumes stable PMC values, i.e. errr < T, it implies an over-relaxed threshold.  

4 Implementation and Evaluation

we use the Xen 3.4 [14] hypervisor, an open source virtual machine monitor, as the base of our implementation.When a para-virtualized guest OS that runs in user mode attempts to modify its page tables, it has to make a hypercall to explicitly notify the hypervisor to do the actual update. In our modified hypervisor, once such requests are received, our code will first perform the requested update as usual and then revoke the access permission by setting the corresponding bit on the page table entry.

4.1 Performance of IMT

IMT의 성능은 두 가지 지표에 의해 평가된다

(1) the time it saves by turning off memory tracking, reflected by up ratio

(2) 메모리 추적을 일시적으로 비활성화로 인해 정확도 손실, 평균 상대 오차로 표시.