Dynamic Tracking of Page Miss Ratio Curve for Memory Management

Dynamic Tracking of Page Miss Ratio Curve for Memory Management

Pin Zhou, Vivek Pandey, Jagadeesan Sundaresan, Anand Raghuraman, Yuanyuan Zhou

and Sanjeev Kumar

abstract

런타임에 어플리케이션의 메모리 요구사항을 다이나믹하게 determined and analyzed할수 있다면 Memory는 효율적으로 사용 될 수 있다. The page miss ratio curve(MRC)다시 말하면 page miss rate vs. memory size curve성능을 나타낼수 있는 좋은 metric이다. 그러나 다이나믹 하게 런타임에 MRC를 트래킹하는것은 시스템의 가상 메모리에서 는 도전이다. 왜나면 모든 메모리 레퍼런스가 OS를 통과 하는 것이 아니기때문이다. ( not every memory reference passes through the operating system )

이논문은 제안한다. 다이나믹 하게 MRC를 트래킹 할 수 있는 두가지 방법을 

첫번째 방법은 하드웨어 MRC monitor를 사용하여 MRC를 트래킹하는것인데 at fine time granularity

( 이들의 실험 결과 모니터는 무시할정도의 성능과 에너지 오버헤드를가지는 것을 확인하였다. )

두번째 방법은 OS만의 구현을 총하여 MRC를 구하는 방법이다. at coarse time granularity.

(  Linux에서 구현 결과 7~10% overhead가 발생하였다. )

그리고 이들은 다이나믹 MRC를 멀티프로그래밍 시스템의 메모리 할당 그리고 메모리 에너지 메니지먼트에 사용하였다. 

그들은 실제 시스템인 리눅스 하파치 웹서버 에서 MRC-directed memory allocation이 동작시같은 5.86향상 하고 page fault의 비율을 63.1%줄이는 결과를 보여 주었다. SPEC2000 벤치 마크를 사용하였고 MRC-directed memory energy management can improve the Energy * Delay metric by 27-58% over previously proposed static and dynamic schemes.

1. Introduction

1.1 motivation

메모리의 동작은 processor and disk의 동작 속도의 차이때문에 중요하다. 메모리 사이즈가 커진다고 하더라도 large data sets의 컴퓨팅 환경에서는 희소한 자원이다. 

특히 (1) host centers where multiple applications or virtual machines run on one physical machine 상황이나. (2) mobile devices that have limited amount of memory due to thermal(열) and packaging considerations.상황 에서 중요하다. 또한 메모리 가격또한 특정 규격이상이 되면 exponentially하게 증가 하게 된다. 그리고 큰 메모리는 데이터 센터에서 심각하게 에너지를 소비한다. [37, 10] 따라서 메모리 메니지 먼트 연구는 중요하다. 

이논문에서는 효율적인 메모리 메니지먼트를 위하여 두가지 관점에 중점을 맞춘다. 

(1) Memory allocation : 멀티플 어플리케이션이 동작하는 시스템에서 메모리는 모든 어플리케이션이 최소한의 메모리를 사용하면서 전체 시스템의 성능을 최대화 하는 방식으로 배분 해야한다.

(2) Memory energy management : 프로세서에게 여분의 메모리를 제공하는 것으로 성능을 향상 시키는 것은 한계가 있다. 이것은 차라리 메모리 에너지를 보전 하는것이 낫다. 작은 베터리나 데이터 센터의 운영 비용을 줄이기 위해서 에너지를 최적화 하는것은 중요하다. 메모리는 에너지 효율 이슈에서 중요한 타겟이다.  [9, 32, 37, 53] 증명하는 논문들

To address this problem, many modern memory modules support multiple low-power operating modes to conserve energy[48] 위에 두가지 메모리 메니지 먼트 관점은 서로다른 두가지 이슈에 집중하지만 둘다 응용프로그램의 다이나믹 메모리가 필요하다.  

working set size(WSS)라고 불리우는 단위는 종종 application’s dynamic memory behavior를 capture하기 위해 사용될 것이다. The working set model was first proposed by Denning [19] 그리고 이것은 일정 기간 동안 참조된 페이지의 숫자이다. 기존 연구들은 page replacements를 가이드 하기 위하여 사용되어 왔다. 

그러나 이 working set model는 memory allocation or memory energy management하기 에 충분 하지 않다. 왜나면 working set는 직접적으로 어프리케이션의 성능과 관련이 없기 때문이다. 

대안으로 the page miss ratio curve ( MRC )를 사용하는것이 좋다 the miss ratio vs. memory size curve 다이나믹 하게 어플리케이션의 메모리 need를 알기 위해서 Previous studies [49, 55, 3, 33] have used MRC to configure the memory hierarchy for applications. 이러한 연구는 응용 프로그램에 여러 번, 서로 다른 크기의 메모리를 사용하여 각 시간을 실행하여 정적 MRC을 구한다. 이러한 방법은 매우 다양한 메모리 요구사항과 서로 다른 연산 phase나 서로 다른 유저 입력에 효과적이다. 그렇지만 멀티 프로세싱 환경에서 메모리 환경을 정적으로 예측하는 일은 힘들다. 그렇기 때문에 런타임에 동적으로 MRC를 추적하는것이 바람직하다. 

파일 시스템에서 이러한 동적 트래킹이 있어나봄 하지만 메모리는 다른점이 파일은 모든 접근을 트래킹 할 수 있지만 메모리는 모든 접속이 OS가 관리 하지 않는다는것이다. 오직 page miss 만을 OS가 핸들하게 된다. 모든 페이지는 OS를 거치지않고 직접 물리적 메모리에 hit하게 된다. 따라서 파일시스템에 사용하던 간단한 MRC추적 시스템을 virtual memory 에서는 사용할 수 없다 ( miss만 OS에서 처리 하고 다른 모든 접근은 MMU를 통하여 처리 되기 때문이다. ) 

1.2 Contributions

이 논문에서 이들은 두가 방법의 다이나믹하게 MRC를 추적하는 방법을 제안한다 그리고 MRC를 사용하여 메모리 할당과 메모리 에너지 메니지먼트를 가이드 할것이다. 우리가 가상 메모리 를 실시간으로 MRC를 트래킹하는게 처음으로 알고 있다. 

그리고 지들이 처음으로 MRC를 메모리 할당과 에너지 메니지 먼트로 사용했다 (레전드)

We have designed a hardware MRC monitor to dynamically track MRC for applications at run time. This MRC monitor is relatively simple and has low power requirement, as shown by our execution-driven simulation results.

//하드웨어 추적 짱짱 좋음

We have also proposed a software-only solution that can track MRC approximately at run time in the OS. Our implementation results on Linux with real applications show that this software only solution imposes only 7-10% overhead.

// hostOS수정을 통한 방법 오버해드가 있음 정확성도 떨어짐 대략이라는 표현 사용 

We have applied MRC to direct memory allocation to maximize memory utilization in multiprogramming systems. Our real system experiments on Linux with real applications, including Apache Web Server, show that this scheme can speed up applications’ execution/response time by up to a factor of 5.86 and reduce the number of page faults by up to 63.1%.

// 실제 시스테멩 적용했을때 짱짱 좋았음 속도도 좋아지고 특히 페이지 포트가 짱짱짱 짱 줄어 들었음 

We have also used MRC to direct memory energy management in order to reduce energy consumption while still providing acceptable performance. Our executiondriven simulation results with SPEC2000 benchmarks show that MRC-directed memory energy management can improve the Energy * Delay metric by 27-58% over previously proposed schemes. // 에너지 소모량 관리 에서도 짱짱짱 좋은 효과를 나타 냄 우리는 짱짱짱 래전더임 

2. Background

2.1 Miss Ratio Curve(MRC)

만약에 어플리케이션의 메모리 behavior 런타임에 동적으로 분석할 수 있다면 메모리를 효율적으로 사용할수 있다. 하나의 효율적인 응용프로그램의 메모리 need를 측정하는 방법으로  MRC (dynamic miss-ratio curve)를 말할 수 있다. 그 그래프는 어플리케이션의 일정량의 물리 메모리의 어플리케이션의 페이지 미스에 대한 변화량을 에 대한것이다. Please note, in our paper, MRC is for accesses filtered by caches

We see that MRC decreases initially but eventually starts to flatten out after a certain point This indicates that even if the system provides more than n memory pages to this application during that interval, it does not help in reducing its miss ratio signifi-cantly. //메모리 할당에 적정량이 라는게 있다는 말 이걸 MRC를 통해 알아 낼수 있다. 그러니까 적당량을 을 제공해야 한다. 

applications’ dynamic memory needs에 대하여 유용한 정보를 제공한다. 예를 들어 we can use MRC to dynamically allocate memory to multiple applications to maximize the overall system performance.MRC can also be used to direct memory energy management. If applications need only n pages to provide the best possible page miss ratio during a period, the system needs to keep only n pages active and can power down the rest of memory to conserve energy in that period. // 좋은말 아까 한 좋은 말 조큼더 구체적으로 서술

과거에 WSS를 capture applications’ memory needs하기 위해 사용해 왔다 For an application, the working set is defined as the set of pages that it has recently referenced.

존나 명언 하나 나왔다 WSS는 what pages should be replaced 할건지 에 좋고 MRC how many pages should be allocated할지 좋다 캬 ~ 

이들은 MRC도 측정하고 WS도 측정할 것이다. 그리고 아가 소개글에서 한말 또함 

2.2 Mattson's Stack Algorithm
런타임에 MRC를 동적으로 추적하기 위해서 Mattson’s stack algorithm를 사용(바탕으로 한다.) 이것은 70년대에 reduce

trace-driven processor cache simulation time하기 위해서 제안 되었다. 

trace file를통하여 특정 교체 알고리즘에 따라 프로세서의 캐시 크기에 대한 미스 비율을 결정하는데 사용할수 있다. 

이들은 stack을 accessed pages의 page number를 저장 하기 위해여 사용한다. 

스택의 앤트리는 시간을 바탕으로 한다 가장 마지막으로 사용한 가장 최근에 사용한 페이지가 스택의 탑으로 간다. 그런 다음에 Mattson’s stack algorithm은 구성된다 다음의 3가지 단계로 

Step 1

첨조된 페이지가 스택 안에 있는지 검색한다. 만약 첨조된 페이지가 탑으로 부터 i(스택의 깊이)있다면 distance는 i이며 만약에 stack에 없다면 distance는 ∞가 된다.

Step 2

stack distance에 해당하는 메모리 크기에 대한 hit counter를 업데이트합니다. 그림의 스택의 크기는 4인데 1 ~ 1-i 사이에 있으면 hit 했다고 하고 그 사이에 없다면 page miss라고 한다.  ( 위 그림 예제 에서는 1~3 사이에 없으면 미스 하고 하는 거다 )

Step 3

Update the stack to reflect the memory content based on the replacement algorithm. For example under the LRU

policy, the referenced page is moved to the top of the stack. ( 그냥 LRU가 적용하여 첨조된 페이지가 top으로 간다는 것이다.LRU가 아닌 여기에 다름 알고리즘을 적용해도된다.  ) 마지막으로 after processing the whole trace miss rate는 계산될수 있다 for hit counter에 따라 여러 메모리 사이즈를 

// 여기서 부터 hit counter 를 가지고 메모리 사이즈를 구하는 공식이다. 

The miss ratio for memory size m pages, MR(m) for a system with total memory of n pages is given by the following formula.

the reference sequence is “1311”. Using the above formula, we calculate the miss ratios for memory sizes of 1, 2, and 3 pages as 0.75, 0.5, and 0.5 respectively. 

이 Mattson’s stack algorithmdl cache를 시뮬레이션 하기 위해서 만들어 진 것 이지만 MRC를 추적 하기위해서도 쓸수 있다. 이전 연구 논문 [35,43]에서 사용이 되어 왔다. 

3. Run-time tracking of MRC 

MRC를 런타임에 찾을수 있는 방법의 베이스를 Mattson’s algorithm가 주었다. 이걸 이제 낮은 오버해드로 구현하는 것이 도전 과제이다. 파일시스템과 다르게 모든 memory access가 OS를 거치지 않는다. 그러므로 이것은 이전의 파일 시스템에서 사용하던 연구 방법을 사용하여 구현 하는것이 불가능하다. [35, 43] 

어플리케이션의 MRC를 동적으로 생성하기 위해서 시간은 epochs 라고 불리우는 일정한 간격으로 나누어져 있다. 각  epoch 동안 우리는 변종된 Mattson’s stack algorithm를 사용하여 accesses를 관찰하여 기록할것이다. 각각의 epoch 가 끝날 때면 끝난 epoch 에 대한 MRC가 계산이 된다. 

이 단락에서는 두가지 구현 방법에 대하여 설명할것이다. 하드웨어를 사용하는 모니터와 소프트웨어(OS-only) 만을 사용한 방법인데 하드웨어 모니터는 당연히 짱짱 좋고 소프트웨어만을 사용한 경우에에는 불안정한 모습을 보여준다. 

3.1 Method 1 : Hardware Approach 

이들은 동적으로 MRC를 추적하기 위해서 하드웨어 모니터 모듈 MRC monitor라는 것을 디자인 하였다. MRC monitors는 메모리 버그와 연결하고 그리고 bus를 snooping하여 메모리 접근을 관찰 할 수 있다. 이것은 또한 메모리 컨트롤러에 built in 할 수 도 있다. 장점으로는 MRC 계산이 짱짱 좋은것이고 단점은 special-purpose hardware가 필요하다는 것이다. 

MRC monitor는 3가지 버퍼로 구성되어있다. LRU stack LRUArray, a group header array GroupHdrs, and a hit counter array HitCtrs. 아래 그림은 MRC monitor의 구조를 나타 낸다. 

LRU array는 LRU stack을 유지하고 안에 있는 엔트리는 각각의 물리적인 페이지와 관련되어 있다. LRUArray인덱스는 바로 page number로 사용될 수 있다. 예를 들어 if the page size is 4 KB, then the 20 most significant bits in the physical address form the index. LRU는 더블 링크드 리스트 구조로 구현되어 있으며 LRUArraysms 3가지 필드를 가지게 된다. (GroupID, next, prev)토탈 8바이트를 가지게 된다. 하나당 그래서 표에보면 8 * 전체 페이지숫자인거다. GroupID는 2바이트를 가지게 되며 소속된 그룹을 표현하는데 (다음 단락에서 소속 그룹에 대하여 설명)next and prev포인트는 각각 3바이트를 사용하여 더블 링크드 리스트 구조를 유지하게 된다. 그룹을 사용하는 이유는 전체 스케닝을 피하기 위해서 이다 The idea is similar to the fast stack implementation by Kim and Hill to reduce the trace simulation time for hardware caches[36]// 이 논문의 아이디어와 유사하다. LRU stack Page는 여러 페이지 그룹으로 분류됩니다

GrpHdrs 항목은 포인트는 page group과 관련이 있다. For example GrpHdrs의 항목의 처번째 포인터는 LRU stack의 top을 가르키게 된다.(가장 최근에 접근한 페이지) 같은 페이지 그룹은 같은 stack distance를 가진다. The array HitCtrs (4 bytes per entry) keeps track of the number of hits for different memory sizes. Since the stack distance is only accurate at the granularity of page group, HitCtrs only needs to record the numbers of hits for memory sizes that are integral multiples of GrpSize In particular, counter j (1 ≤ j ≤ NumGroups) in HitCtrs records the number of accesses that would result in a hit with a memory of size j ∗ GrpSize pages, but a miss for any smaller memory size. The last two counters in HitCtrs record the total number of memory accesses and the total number of misses respectively. // 페이지 그룹 만큼의 카운터가 있고 카운터의 마지막 두개는 하나는 총 카운트량 하나는 총 미스 량을 측정하게 된다. 

미스가 날경우 OS의 page fault handler가 교체하기 위해 victim page 선태하고 MRC monitor에게 미스난 가상 메모리와 hold된 물리 메모리를 알려준다. LRUArray의 관련되 물리적 메모리는 무효? 유효?된다. 페이지 폴트가 핸들링 된이후 프로세서는 다시 가상주소에 접근하게 된다.  

MRC모니터는 접근을 관찰하고 유효하지 않은 엔트리를 공지한다. 

따라서이 접근에 대한 스택 거리가 무한하다 그리고 the last two entries in HitCtrs is incremented by one.메모리에 대한 모든 액세스는 MRC 모니터의 구조를 업데이트 할 필요가 없습니다. MRC 모니터는 시간적 지역성을 활용하는 몇 가지 최근의 액세스의 페이지를 기록 할 수 있습니다

하나의 epoch시간이 끝나게 되면  MRC는 HitCtrs의 정보를 가지고 방적식 1번을 사용하여 generate한다. 방정식 1의 Hit[i]는HitCtrs[i]와 연관이 되어 있고 i 는 개별적인 페이지라기 보다 페이지 그룹의 인덱스 이다. 그리고 토탈 넘버 가 마지막 두칸에 있다. Since the hardware MRC monitor can observe all memory accesses, it can generate MRC at a fine granularity.

이것은 필수적이다. 왜냐 하면 10,000 CPU cycles 주서의 짧은 epoch 길이는 MRC-directed memory energy management에 필요 하기 때문이다. (세션 5에서 설명) 

The MRC monitor described so far tracks the miss ratio curve for the entire system including operating system and all applications.For applications like memory energy management (Section 5), this is appropriate because it can be used to conserve the energy in the system as a whole.//측정이 정확할수 록 에너지 conserve 효과가 커지는거 같다. 

그러나 다중 실행 환경에서는 (like a virtualazstion)프로세서 마다 따로 MRC를 계산하는것이 좋다. 이를 위해서는 GrpHdrs and HitCtrs 가 실행중인 프로세서에 private되어야 한다. 

The LRUArray would be shared among all processes but inside the LRUArray, pages that belong to the same process

are linked together following the LRU order. At a context switch, the GrpHdrs and HitCtrs should also be swapped.

MRC Monitor는 병렬적인 처리를 하기 때문에 imposes little runtime overhead

일반적으로 대분분의 memory instructions는 프로세서의 캐시에 접근하게 된다.(지역성) 그리고 작은 부분의 메모리 명령만이 메모리에 접근하게 된다. 이는 메모리 관리를 위한 유일한 고나심이다 (메모리 보다 캐시에 있도록 관리 해주는것이 좋다. )존나 많이 메모리에 접근하는 어플리 케이션의 경우 MRC모니터의 queue overflows가 발생 하기도 했지만 그렇게 큰 왜곡은 아니였다. 그리고 아주 정확할 필요도 없단다 지들이 하는 에너지 관리와 메모리 메니지먼트에 

//여기 부터 진짜 중요 하드웨어적인 지원 없이 소프트웨어로만 해결한 경우 

3.2 Method 2: OS approach

MRC monitor는 효율적으로 어플리케이션의 MRC를 생성하지만 이것은 여분의 하드웨어가 필요하다. multiprogramming (like a virtualization)환경에서는 완벽한 MRC 가 꼭 필요한것은 아니다. 간단한 솔루션을 제공하기 위해서 이들은 OSonly method to dynamically track MRC at run time를 제안하였다. 이들은 리눅스에서 구현하였고 이환경을 기본으로 실험하였다.

하드웨어 지원없이 Mattson’s stack를 구현하기 위해서는 몇가지 도전이 있다.

(1) Accuracy

모든 메모리 접근은 OS를 지나지 않는다 오직 페이지 폴트만이 OS를 거치게 된다. 페이지가 hit되는것은 바로 하드웨어가 핸들 하게 된다. 하드웨어는 모든 첨조된 페이지들은 accessed bit를 set하게 된다. 따라서 OS는 오직 대략적인 of pages referenced during an interval by  accessed bits 가 재 설정될때  interval의 시작과 긑에서 알수 있다. 

(2) Time Over head.

모든 "accessed” bit 를 Scanning하는것은 받아드리기 힘든 오버헤드가 될수 있다. 또한 충분히 자주 스캔해서  accesses to the pages를 놓치면 안된다. 

(3) Space Overhead

어플리케이션의 가상화된 주소를 전부 stack으로 구현하는것은 매우 많은 공간을 요구하게 된다. 이거는 어쩌면 MRC-directed memory management의 이점을 상쇄 할 수 있다. 

이러한 도전을 다루기 위해서 Mattson’s stack algorithm를 바탕으로 3가지 key로 OS를 개량 구현하였다. 

(1) “accessed" bit 를 스캔하는 페이지의 수를 줄이기 위해서 page protection를 사용하였다. 그래서 작은 시간안에 스캔이 가능하다 ? 

(2) hardware MRC monitor와 비슷하게 페이지 대신 페이지 그룹을 사용한다. the basic memory unit size to reduce the time overhead.

(3) 공간 오버해드 문제를 해결하기 위해서 stack의 크기의 한계 값을 total physical pages로 정한다. (가상 메모리 로 스택을 만들지 않는 다는 말) 

공간적인 한계 재약 때문에 OS구현에 대하여 짧을 설명만 했는데 더 자세히 알기 위해서는 [45]논문을 바라 //꼭 본다 구글링으로 없다 ㅠㅠ

For each monitored process the OS maintains the following data structures:

(1) stack은 더블 링크드 구조로 만든다. 각각의 목록들은 가상 페이지의 숫자와 페이지 구룹 아이디를 유지한다. 

(2) hardware MRC monitor의 group header array와 유사하한것을 tracking the headers of page groups 하기 위해 사용한다. 

(3) hit counter array도 사용된다 서로 다른 메모리 사이즈의 hit숫자를 기록하기 위해서 page group단위의 추적만을 한다. 

(4) A pointer called “scan list pointer”, which points to one of the elements in the doubly linked list.All the elements in the stack which are above this pointer form the scan list, the significance of which will be explained shortly.

OS는 결정적으로 최근 accessed pages set이 필요하다 그래서 이것은 it can update the hit counters한다.(총 엑세스 타임 hit을 가지고 MRC추정)

To reduce the overhead of scanning the accessed bits, OS구현하였다 page를 나누었다, 물리적인 메모리를 두가지 구역으로 For the recently accessed pages (members of the scan list),the OS checks the accessed bits to determine if  they were accessed. To catch references to the 드물게 accessed pages,the OS uses the page protection mechanism. //물리 메모리를 두구역으로 나누어서 자주 사용되는 것은 스캔 리스트에 넣어 놓고 자주 사용되지않는 것은 page protection mechanism을 사용하여 스캔 하는 영역을 줄인다는 이야기 같임

The OS periodically scans the accessed bits for pages that are in the scan list.y scans the accessed bits for pages that

are in the scan list. If the accessed bit for such a page is set, the OS calculates the stack distance based on the group

ID associated with the corresponding stack entry. It then increases the corresponding hit counter by 1. If this page is not in group 0, it is “moved” to the top of the stack by manipulating the doubly linked list and its page group ID is set to be 0.// 아까 하드웨어 MRC 모니터에서 했던 행동 똑같이 한다. 

For detecting references to pages that are not in the scan list //스캔리스트에 없는 메모리 참조가 일어날 경우 

the OS switches off the read-write permission of these pages. //OS단계에서 protection을 풀어 버린다. 

An access to such a page causes a protection fault.

This is similar to the Shared Virtual Memory (SVM) systems [39] // 유사 시스템 꼭 읽기 

Then the OS calculates the stack distance, updates the hit counter array, grants the read-write permission to this page to avoid future faults, and moves the corresponding entry to the top of the stack, thus adding it to the scan list. The last page in the scan list is evicted from the list by switching off its read-write permission to detect its future accesses, and scan list pointer is adjusted to reflect that this page is no more in the scan list. // 권한 변경 말고는 하드웨어 모니터와 같은 동작 

page protection optimization은 약간의 오버해드를 발생시킨다. 그이유는 다음과 같다. 

(1) Since most programs 이 좋은 temporal locality를 가진다. 최근에 사용되지 않은 페이지는 접근될 확률이 비교적 낮다. 따라서 이러한 보호 오류는 적다. (보호오류를 디텍팅 해서 콜드 리스트에서 핫 리스트로 변환 하기 때문에 변명하는 이야기 근거 잇따.  )

(2)만약이 로컬리티가 존나 구린 경우에는 we can increase the scan list length and disable the page protection optimization.해서 해결한다. 이들은 일반적인 액세스 패턴에 대한 전체 목록을 검색하지 않고 MRC을 추적하는 그 기술을 통합 할 수 있습니다.We have implemented the above method in Linux by modifying the virtual memory system and adding around 1000 lines of code.In addition to the background scanning procedure for the NRU (not recently used) page replacement algorithm implemented by the original Linux systemwe have added another scanning procedure to scan the reference bits of the scan list. Due to optimizations described above, the time overhead of our procedure is very low. //리눅스의 가상메모리 코드를 1000줄 가량 수정하였고 NRU교체 알고리즘은 리눅스 그것을 그대로 사용하였으며 스케닝 절차를 추가한것이 OS수준의 스캐닝의 구현 이다. 

4. APPLICATION I : MRC-DIRECTED MEMORY ALLOCATION (MRC-MM)

이 장에서는 multiprogramming system에서 MRC-based memory allocation방식에 대하여 설명한다. 멀티 프로그래밍 환경에서 프로세서의 메모리 요구사항을 항상 필요한 만큼 일치 하지 않는다. 프로세서가 필요한것보다 적게 할당 받았을때 가각의 메모리 참조는 e process triggers a page miss(페이지 폴트를 발생)이것은 CPU cycles를 수만개 사용하게 된다. disk I/O발생 

thrash로 인하여 성능이 떨어지게 된다. 이러한 문제를 방지 하려면 메모리 관리가 중요하다. 데이터 센터에서 사용하면 throughput을 향상 시킬수 있다. The memory manager can use the methods described in Section 3 to determine the MRC, and use the MRC to guide memory allocation. The basic idea of the scheme described in this section is to allocate more memory to processes that exhibit a higher marginal performance gain.

4.1.1 Problem Formalization 문제의 공식화 

좋은 메모리 메니지먼트 알고리즘을 찾기 위해서 우리는 먼저 문제를 공식화한다. (resource utility problem)

컴퓨터 시스템에 n 프로세서가 동작한다고 가정한다. (Pi, 0 < i < n-1) Mtot 는 시스템의 총 메모리 공간이다. 

문제는 n processes에 메모리를 할당하는것이다 in order to maximize memory utilization.(메모리 사용률의 극대화)

우리는 각각의 process Pi 와 관련있는 utility function Ui가 필요하다.R → R where Ui(m)

process Pi 에 할당 되어있는 메모리량을 알기 위해서 hit  비율이아닌 miss 비율을 사용하여 극대화 문게를 적용한다. 이것은 또한 성능의 지표로도 활용할 수 있다. Let Mi represent the memory size allocated to process Pi

Process Pi에는 수긍할만한 성능을 위해서 최소한의 메모리가 할당되어야 하는데 이것을 Mmin 라고한다. 각각의 프로세서에는 weighted by wi가 정해지는데 이것은 이프로세서가 시스템에서 얼마나 중요한것인지를 나타 낸다. The total system utility U is the weighted sum of the utilities of individual processes.

Then the problem of memory allocation is to find Mi for 0 ≤ i ≤ n − 1 that maximize the total system utility given by

An allocation M = (M0, . . . , Mn−1) is said to be feasible if it satisfies the following two constraints.

(1) Finite Memory: 유한적인 메모리 모든 할당된 메모리의 총합은 토탈 시스템의 메모리의 량과 같아야 한다.

(2) Minimum Memory Mmin각은 경우에도 논문에 있는 공식이 위 유한적인 메모리 할당과 같이 적용이 되어야 한다

This is essentially a QoS-based resource allocation problem and has been addressed in great detail and higher complexity in previous work [46, 47] // 졸 중요 Qos바탕의 메모리 할당에 대하여 알수 있다. 

that deals with resources for real-time applications. As the optimal solution for this has shown to be NP-hard [46], we give a greedy algorithm to get a good solution for the problem. // 이들같은경우 할당에 있어서 greedy algorithm를 적용하였다. (탐욕 알고리즘)

4.1.2 A Greedy Algorithm

greedy algorithm의 메인 아이디어는 메모를작은 δ 단위로 나누고 점진적으로 프로세서에 δ양 만큼 할당하는것이다. 이것은 각 단계마다 메모리 최대 이익을 가질수 있다. 즉 프로세서가 현재 받은 δ memory는 최대 사용량에 대한 메모리 할당량인것이다.

일반적인 손실 없이 이들은 utility functions이 이미 n weighted by their priorities wi를 가지고 있다고 가정하였다. 

유사하게 수긍할만한 성능을 위한 미니멈 메미로 향도 이미 할당 받았다고 생각한다. 따라서 그 크기는 초기화 Mmin i = 0.를 가진다. 

greedy algorithm는 모든 시스템의 모든 메모리가 할당 되었거나 모든 프로세서가 할당에 대하여 만족할때 까지 다음과 같은 행동을 반복한다. 

1. Let Mi = 0,0 ≤ i ≤ n − 1

2. 지금 까지 이미 모든 process Pi들이 메모리를 할당 받아 왔다라고 가정한다. 사용량 곡선을 계산한다. U′i (Mi)를 통하여 m를 유도한다. 

3. 최되 경사도를 가진 process Pj를 선택한다. priority를 사용하여 관계를 부술수 있다. 

4. Allocate δ memory to process Pj.Increase Mj by δ and the decrease free memory Mfree by δ. Other Mi values remain unchanged.

For convex utility functions, the greedy algorithm has shown to be optimal in For non-convex utilities, the

algorithm can be applied to the convex hull of the utility function curve. We note that MRCs are usually convex,

and therefore the greedy solution we obtain is very close to the optimal solution.// 45번 논문에 있는 내용인데 convex utility 보일수 록 greedy algorithm이 적용이 가능하고 이것은 MRC가 convex한 모습을 보여 주기 때문에 딱이다 ! 

4.1.3 Implementation of MRC-MM in Linux

이들은 리눅스의 메모리 메니저를 수정하였다. memory reclamation와 memory allocation procedures를 greedy algorithm를 베이스로 통합하였다. 

memory reclamation procedure에서는 시스템의 free memory가 어떠한 임계값이하로 떨어질 경우 프로세서들이 최소한의 성능 손해를 받을 만큼만 메모리를 회수 하게 된다. For example, comparing two processes A and B, if taking δ memory from A would  not increase A’s miss ratio at all whereas taking the same amount of memory from B would cause more misses for B, then process A is chosen to give up δ memory.The memory manager iterates this until the system has enough free memory.

memory allocation procedure에서는 프로세서가 page fault가 발생할 경우 이때 메모리 메니저는 free메모리를 할당해야 할지 아니면 다른 프로세서에서 뺏어 와야 하는지 체크한다. 이때 결정의 바탕은 성능이다 더 메모리를 줄때의 성능향상 정도 만약에 성능 향상이 짱짱 좋아 질거 라고 판단할 경우 메모를 준다 아니면 그냥 프로세서의 페이지하나를 교체 한다. 

4.2 Real System Experiments

3.2절에서 이들은 OS 방법으로 tracking MRC dynamically했다 리눅스 운영체제에서 그리고 이들은 메모리 메니지 먼트를 수정하여 MRC-directed memory allocation scheme를 구현하고 설명하였다(4.1.3) 실제 실험은 하드웨어 방식을 사용하지 않았다 그 이유는 OS가 시뮬레이션을 지원하지 않았기 때문이다. 또한 거친 OS구현의 tracks the MRC가 메모리 할당에 충분하다는 것을 이번 단락에서 설명한다. 

4.2.1 Methodology

We conduct our experiments on a system with a single 1.8 GHz CPU, Pentium 4 machine running Linux-2.4.20, with 128MB memory and 512MB swap space. The page size is 4KB. We use 128MB of memory because our applications’ data set sizes are relatively small. // 실험 스팩 

메모리를 작게 하고 실험하는데 이들은 메모리의 크기와 데이터 셋의 크기를 늘려도 비슷한 결과가 나올것이라 예상한다고 했다. 그리고 이들은 64페이지를 하나의 그룹으로 설정 하였고 epoch length는 10ms로 하였다. 

이들은 3가지 실 에플리케이션으로 수정된 시스템을 평가한다. (Apache Web Server [1], gcc, and gzip)그리고 두가지 synthetic benchmark를 사용한다. For the Apache Web server, we use the flood [2] to generate requests, and Apache’s logging facilities to find out the response time to serve each request.//flood라는것을 활용하여 요청을 보네고 서버의 아파치 로깅 시간을 이용하여 각각의 요청에 대한 응답 시간을 측정하였다. 

inputs for gcc and gzip are 166.i and input.graphic respectively, which have been taken from the SPEC2000 benchmark suite.

The two synthetic benchmarks are:

(1) LINEAR,

which emulates an application having a loop access pattern. The program consists of a loop that touches pages in a sequential fashion. // 이 에플리 케이션은 루프 엑세스 패턴을 가지고 있는데 순차적으로 페이지를 생성 한다. 

(2) INTR, which emulates an interactive

application consisting of periods of activity followed by inactivity (we use sleep() to emulate this).

// 대화형 에플리케이션인데 주시적은로 activity와 inactivity상태를 왔다 갔다 한다. 루프 형식으로 되어서 zipf distribution를 베이스로 temporal locality를 시뮬레이션 한다. 

이들 벤치 마크는 루프 반복에서 페이지를 터치하는 시간을 측정하여 응답시간을 측정한다. 

이들은 자신들이 만든 MRC-MM과 리눅스 메모리 메니지먼트와 original 리눅스 메모리 메니지 먼트와 비교 하였다. The original Linux MM uses the global page replacement(the LRU-like CLOCK algorithm)to manage the entire physical memory space without considering which process a page belongs to. It is simple but suffers from thrashing.

4.2.2 Overall Results

Table 2 shows the execution/response time and number of page faults for each application in MRC-MM and the original system for six multiprogramming settings:

(1) Apache with gzip, 

(2) Apache with gcc, 

(3) Apache with LINEAR,

(4) INTR with LINEAR, 

(5) INTR with gzip, and 

(6) INTR with gcc

interactive applications이 응답시간에 더 sensitive하다 Apache / INTR의 성능은 다른 세 가지 응용 프로그램의 실행 시간에 비해 더 중요한 고려 사항이다. 제시되는 모든 시간에는 tracking MRC overhead 부가 된다. 

interactive applications인 Apache / INTR에서 MRC-MM를 적용할 경우 응답시간을 줄일 수 있다. 2.29 to 5.86% 

예를 들어 욕망 알고리즘을 활용하여 최적화된 메모리를 할달하기 때문에 결과적으로 페이지 폴트가 줄어 들면서 성능이 향상되게 된다. 프로세스 스케줄링 및 요청 대기 지연의 개입으로 인해, 일부 설정의 평균 응답 시간의 비율 감소는 페이지 누락의 수의 비율을 감소보다 크다. 

대화식 프로그램에서는 강한 모습이지만 비대화식 프로그램에 대하여 작은 5~8%의 성능 저하도 보였다. worst case에서 그리고 어떤 상황에서는 성능 향상도 존재 하였다. // 대화형 프로그램에서는 좋은 모습을 보일수 있지만 비 대화형에서는 오버해드가 될수 있다. 그냥 오버해드 MRC측정 

그주된이유는 MRC-MM은 성능에 심각한 저하가 발생항 경우에만 추가적인 메모리를 에플리케이션에게 할당 하기 때문이다.(그러면 할당도 안되면서 MRC tracking을 하기 때문에 이득은 없고 측정에 대한 오버 헤드 만이 발생하게 된다. )

어떤경우에는 성능이 향상되게 되는데 그이유는 적은 페이지 교체 작업이 스왑아웃을 줄였기 때문이다. (이반적인 리눅스의 교체 정책의 회수 정책이 없기 때문이다. ) 

상세한 분석 그림 4 

A detailed analysis of Apache+gcc case is presented inFigure 4. In the experiment, Apache begins first and gcc

begins after 140s. Figure 4(a) shows the response time ofApache in the Apache+gcc setting on the original and the

MRC-MM system. // Apache+gcc case인데 아파치가 먼저 시작되고 gcc는 140초후 동작하게 된다. 

GCC가 처음으로 메모리에 배포 되었을때, GCC는 140S 후 시작하면, 원래 시스템에서 아파치의 응답 시간은 250MS의 최대 극적으로 증가하고, 300 초 정도까지 높게 유지 된다. gcc가 두번째 동작할때 다기 한번 응답시간이 증가하게 된다.

MRC-MM의 경우에도 gcc가 시작이 되면 응답시간이 증가 하게된다. 그렇지만 MRC-MM finds that giving Apache more memory at the cost of gcc is beneficial for the overall system performance and the performance of gcc is not greatly degraded by giving it less memory. // 더 좋은 성능을 발휘하고 적은 메모리를 할당한다고 성능이 떨어지지 않는다. 더적은 메모리로 더 좋은 성능을 나타 낸다. 

따라서 아파치의 재시작 응답시간도 빠르고 오리지널 시스템보다 더 빠르다. 비슷한 설명은 GCC의 두 번째 단계에 보유하고 있습니다.

그림 4의 (b)와 (c)는 보여준다 아파치의 오니지널과 MRC-MM의 resident set sizes (RSS) gcc가 시작되면 아파치는 20000페이지에서 8000페이지 정도로 떨어지고 gcc에는 20000페이지가 할당이 된다. 
데이터 센터 의 가상화같은 멀티프로그래밍 환경에서 짱짱 좋음 

4.2.3 Overheads of tracking MRC

tracking overhead도 측정하였는데 오리지널 리눅스의 실행과 수정된 리눅스의 실행결과의 비교를 주기적으로 하여 측정 하였다. 측정동안에는 어떠한 메모리 메니지먼트도 하지 않고 오직 tracking을 추적하였다. 

7%~8%의 오버헤드가 발생하였는데 이것은 데이터 구조를 조작하는 과정과 scan list하는것과 handling page protection faults하는것에서 나오는것이다. 

리얼시스템에서 사용할때는 높은 경쟁이 발생할 경우와 충분한 메모리가 있을경우에는 동작하지 않는 개발 방법으로 더 낮은 오버해드를 가질것이라고 생각한다. 

5. APPLICATION II : MRC-DIRECTED MEMORY ENERGY MANAGEMENT (MRCEM)

5.1 Main Idea

메모리를 다루는것은 에너지효율에 가장중요한 이슈이다. 모바일 이나 하이엔드 컴퓨터 서버에서 기존의 연구들은 에너지를 줄이려면 성능을 줄어들었지만 이들의 연구 같은 경우는 어떠한 어플리케이션의 에너지 소비도 줄일수 있으며 성능 저하 또한 일어나지 않는다. 

이들의 MRC-directed memory energy management는 가정한다. hardware MRC monitor를 사용하여 fine time granularity가질수 있다고 합당한 성능을 내기 위해서 최소한으로 필요하다고 생각되는 결정적인 최소한의 메모리량을 알 수 있다. 예를 들어 프로세서가 Nmrc memory pages를 가지고 있으면 최대 hit율을 가질수 있다면 메모리 파워 컨트롤 알고리즘은 이게 적정이라고 생각하고 Nmrc파워만 남기고 파워를 꺼버린다. 

불행하게도 현제 메모리 기술은 페이지 단위가 아니라 칩단위로 파워를 제어가능하다. So we need a way to map selected pages to chips

MRC는 작동할 칩의 수를 조정한다. 그러기 위해서 또한 다음과 같은 결정이 필요하다. 

(1) what chips should be selected as working chips

(2) how to handle an access to a nonworking chip.

첫 번째 문제를 해결하기 위해, 우리는 working set model 을 활용할 수 있습니다.

MRC 스택의 최상의 페이지를 워킹 칩으로 선택하한다. 모든 다른 칩들은 파워를 죽인다. The power states of working chips are controlled by the basic energy management scheme 페이지가 사용하지 않는 칩에 접근하게 되면 칩을 활성 상태로 바꾸고 워킹 셋에 추가하한다. 

비록 칩의 파워를 없에는 것은 많은 파워를 소비하게 되지만 프로그램의 지역성 때문에 상각되는 요소이다. 

이들의 실험 자체가 연속적으로 페이지를 할당하기 때문에 공간적인 지역성 이 높다. 

At any time, if a chip does not contain any of the top Nmrc pages of the Mattson’s stack, MRC-EM deletes it from the

set of working chips and powers it down. // 어느순간 스택에 포함된 페이지가 없는 칩은 파워를 죽인다. 

칩 스택의 상위 NMRC 페이지의 포함되어 있는지 여부를 추적하기 위해 MRC-EM은 각 메모리 칩 카운터를 유지합니다.

스택에서 페이지가 top으로 이동할 때 마다 이 새 페이지가있는 칩의 카운터는 1 씩 증가합니다.스택 (NMRC + 1) 번째 페이지를 포함 칩 카운터는 하나씩 감소합니다. // 스택에서 낮은 쪽으로 갈수록 카운팅을 줄여서 이게 0이 되면 워킹 set에서 없에고 파워를 죽인다. 

5.2 Experimental Results

We use execution-driven simulation to evaluate MRC-EM. We enhance the widely used SimpleScalar [7] simulator with the MRC monitor and RDRAM power model. We use Wattch [5] to model the energy consumption of the MRC monitor.

We report the results with memory sizes similar to the corresponding application’s data set size. The default epoch length is 10,000 cycles, except in the experiments that studied the effects of epoch length.

5.2.1 Overall Results

Energy*Delay (ED) metric이라는 것으로 표현했는데 

메모리 공간의 한계때문에 절대적인 에너지 소비량에 대해서는 검증 하지 않았다. 

오리지날 보다 짱짱 좋은 성능을 알려 주었다. 주된 이유는 적절한 성능을 제공하는 데 필요한 얼마나 많은 메모리 기본 메모리 에너지 관리 체계에 대한 지침을 제공하는 것입니다. 그림에서 보듯이 정적인 방법보다 동적인 방법이 더 효율적이다. 

하지만 다이나믹 방식은 thresholds가 발생하여 성능이 떨어질수 있으니 threshold tuning이 필요하다. The MRC approach is application-independent, does not require threshold tuning, and can be coupled with any suitable fine grained power saving mechanism in order to conserve memory energy. // 에너지 부분에 대한 설명은 잘 이해가 안된다. 설명도 작고 Energy*Delay (ED) metric이 먼지 몰라서 잘 이해가 안된다 알려면 논문 하나더 봐야 할듯 

5.2.2 Effects of Epoch Length

epoch length가 길어 질수록 ED의 감소 하게 되는데 

5.2.3 Effect of Memory Chip Size

이것도 위와 같은 맥락 

6. RELATED WORK

6.1 Memory Allocation

멀티프로그래밍 시스템에서 memory allocation 연구는 크게 3가지 부류가 존재한다. 

global replacements, local replacements, and demand-based replacements.

global replacements는 물리적 메모리 항목에서 처리 하는것으로 페이지가 어떤 프로세서에 속하여 있는지 상관하지 않는다. 간단한 구현으로 인하여 현대 Linux운영체제에서 많이 사용되고 있다. 하지만 이것은  thrashing을 유발한다. 

현존하는 운영체제들은 load control를 이용하여 thrashing을 다룬다. 

Local page replacements는 개별적인 프로세서 메모리 풀안에서 처리가 된다. 별로라서 일반적으로 사용이 안되고 아주 옛날 정의한 VMS에서 사용한다. 

Demand-based replacements manage memory based on applications dynamic memory needs. 이당시 옛날이지만 이전 연구들은 working set model을 사용하였다. 메모리 메니지 먼트를 가이드 하기 위해서 

여러 scheme들이 제안되었는데 page fault frequency (PFF) algorithm, variable-interval sampled working set policy

기존에 산업에서 적용되어 사용되어온 WSS방법과 다른것은 다음과 같은것이다.

an application’s working set gives what pages should not be replaced, whereas MRC shows how many pages should be resident to provide acceptable performance. 따라서 서로 보완적인 관계가 된다. 

7. CONCLUSIONS

응용 프로그램들의 miss ratio curve는 메모리 메니지 먼트 하기 위한 다양한 정보다 들어 있다.  그러나 런타임에 tracking MRC dynamically하는 것은 매우 도전적인 일이다. 왜 냐면 모든 메모리 접근이 OS를 통과 하는 것이 아니기 때문이다. 

그래거 이 논문에서 도전적인 과제를 다루기 위한 방법 두가지를 제안한다. 하드웨어 방법과 OS만을 사용하는 방법 

하드웨어는 당연히 짱짱 좋은 MRC를 뽑아내고 OS만 사용하는 방법은 조잡한 값을 뽑아 내게 된다. 

그리고 이 공부는 두가지 응용프로그램을 제안한다. 

(1) MRC-directed memory allocation (MRC-MM) for multiprogramming systems

(2) MRC-directed memory energy management (MRC-EM)

실제 리눅스에서 아파치 웹서버에서 MRC-MM 실험결과 에플리케이션의 5.86% 속도향상을 보였고 페이지 폴트가 63.1%감소 하였다, Our execution-driven simulation results with SPEC2000 benchmarks show that the MRC-EM can improve the Energy*Delay metric by 27-58% over previously proposed static and dynamic schemes.

이연구에는 차후 해결해야하는 한계가 있는데 MRC-directed memory allocation는 메모리의 사용의 극대화를 노린다. It can be easily extended to consider process priority and other attributes to ensure fairness 이당시 에 이들은 페이지 힛률 말고 엔드 성능이 더 향상될수 있는 방법을 고안하고 있었다.We expect the results to

be similar to those presented in this paper for most applications. Finally, we have performed experiments only in a few multiprogramming settings. We are in the process of evaluating more applications, especially for MRC-directed energy management. We are also exploring other applications for MRC,