Bounding Memory Interference Delay in COTS-based Multi-Core Systems

Bounding Memory Interference Delay in COTS-based Multi-Core Systems

Hyoseung Kim, Dionisio de Nizy, Bjorn Andersson, Mark Kleiny, Onur Mutlu, Ragunathan (Raj) Rajkumar

Electrical and Computer Engineering, Carnegie Mellon University

Software Engineering Institute, Carnegie Mellon University

Abstract - In commercial-off-the-shelf (COTS) multi core systems, a task running on one core can be delayed by other tasks running simultaneously on other cores due to interference in the shared DRAM main memory. Such memory interference delay can be large and highly variable, thereby posing a significant challenge for the design of predictable real-time systems. In this paper, we present techniques to provide a tight upper bound on the worst-case memory interference in a COTS-based multi core system. We explicitly model the major resources in the DRAM system, including banks, buses and the memory controller. By considering their timing characteristics, we analyze the worst case memory interference delay imposed on a task by other tasks running in parallel. To the best of our knowledge, this is the rst work bounding the request re-ordering effect of COTS memory controllers. Our work also enables the quantification of the extent by which memory interference can be reduced by partitioning DRAM banks. We evaluate our approach on a commodity multi-core platform running Linux/RK. Experimental results show that our approach provides an upper bound very close to our measured worst-case interference.

Introduction 

문제 

In multi-core systems, main memory is a major shared resource among processor cores. Tasks running concurrently on different cores contend with each other to access main memory, thereby increasing their execution times. In multi-core systems, main memory is a major shared resource among processor cores.  // 멀티코어들이 하나의 테스크를 처리 함에 있어 메인 메모리를 공유하는것은 한번에 하나의 메모리 영역에ㅔ만 접근이 가능하기 때문에 실행시간이 지연이 발생한다. 특히 리얼 타임 성향의 메모리 intensive 애플리케이션은 더욱 심하다.

an upper bound on the memory interference delay is needed to evaluate their schedulability // 현실적은 부분을 해결하려는 노력이 보인다. 지금 현 시스템에 리얼 타임 성향의 테스트 셋이 동작 할 수 있는지 알기 위해서는 미리 스케줄링 예상 가능해야 한다. 안전성을 위해서 스케줄링을 미리 예상할 때 최악의 실행 시간을 이용한다.

기존 연구의 단점

기존 멀티코어의 메모리 바인딩 방법은 RR 이나 FCFS 였다. 상한 실행시간을 알기 위한 중요한 정보를 숨기기 때문이다. ? 

기존 연구 단점의 이유 

Specifically, in modern COTS-based systems, the main memory typically consists of DRAM to cope with high performance and capacity demands. The DRAM system contains multiple resources such as ranks,  banks and buses, and the access time varies considerably depending on the requested address and the rank/bank states. // 정보를 숨기는 이유는 Dram의 구조 때문이다.  bank나 rank의 상태에 따라 접근 시간이 달라진다.? DRAM 구조에 대한 공부 필요 

또한 멀티코어의 메모리 요청 처리는 하드웨어로 이루어진다. First ready first come first service  (FR-FCFS)policy 

그러므로 이전 연구는 메모리 모델을 지나치게 간략화 헸기 때문에 지나치게 비관적이거나 낙관적인 상한 실행 값을 나타낸다. 

아 ~~ 기존 상한값 계산 연구들은 멀티 코어가 메모리를 요청하는 하드웨어적 인 스케줄링 시간을 블랙 박스로 두고 계산 하였지만 이연구에서는 구 하드웨어 스케줄링 부분을 화이트 박스로 두고 계산 하여 이전 연구보다 더 정확한 상한 실행시간을 계산 할 수 있다. 

본 논문이 한일 

In this paper, we propose a white-box approach for bounding memory interference.

By explicitly considering the timing characteristics of major resources in the DRAM system,

including the re-ordering effect of FR-FCFS and the rank/bank/bus timing constraints,  we obtain a tight upper bound on the worst-case memory interference delay for a task when it executes in parallel with other tasks.

Our technique combines two approaches:

a request-driven and a job-driven approach.

request-driven 방법은 테스크들이 소유한 메모리 요청에 집중한다. 

The request-driven approach focuses on the task’s own memory requests

job-driven 방법은 테스크들의 실행에 메모리 요청 간섭에 집중한다. 

the job-driven approach focuses on interfering memory requests during the task’s execution.

Combining them, our analysis yields a tight upper bound on the worst-case response time of a task in the presence of memory interference.

BACKGROUND ON DRAM SYSTEMS

The memory interference delay in a DRAM system is largely affected by two major components:

 (i) the DRAM chips where the actual data are stored

 (ii) the memory controller that schedules memory read/write requests to the DRAM chips.

A. DRAM Organization

DRAM에서의 지연 요소 

The DRAM access latency varies depending on which row is currently stored in the row-buffer of a requested bank. If a memory request accesses a row already in the row-buffer, the request is directly serviced from the row-buffer, thereby resulting in a short latency. This case is called a row hit. If the request is to a row that is different from the one in the row-buffer, the currently open row should be closed by a prechargecommand and the requested row should be delivered to the row-buffer by an activate command. hen the request can beserviced from the row-buffer. This case is called a row conflict and results in a much longer latency. //row hit 이냐 conflict 이냐 

B. Memory Controller

The memory controller is a mediator between the last-level cache of a processor and the DRAM chips.