20160201

1. [ISCA’11] Vantage: Scalable and Efficient Fine-Grain Cache Partitioning 읽기 (paper, slides)
– 이 논문에서는 많은 수의 fine-grained partition을 제공하는 cache partitioning 기법인 Vantage를 제안한다. 다양한 cache partitioning 기법이 제안되었으나, 지금까지 제안된 기법들은 coarse-grained한 단위로 partition을 생성한다는 문제가 있다.
vantage summary.PNG– Cache partitioning 기법은 allocation policy와 partitioning scheme으로 구성됨. Allocation policy는 각 partition에 어느 정도의 캐시 크기를 할당할지 결정하는 것. Partitioning scheme은 어떻게 실제로 캐시를 분할할 것인지에 대한 것. 여기서는 partitioning scheme에 대해 이야기하려는 것.
– 이상적인 partitioning scheme에 대해 정의하고 있음. 이상적으로는 fine-grained partition을 매우 많이, 오버헤드 없이 제공해야 함. 동적 생성과 제거도 가능해야 함. 하지만 지금까지 제안된 기법들은 이러한 요구 사항을 충족하지 못하고 있음. 특히 fine-grained 하지 못하다는 특성을 가짐. Vantage에서는 fine-grained한 여러 개의 partition을 관리할 수 있는 기법을 제안하고자 함.
Strict partitioning은 캐시 라인이 들어갈 수 있는 위치를 제약함으로써 캐시를 분할함. Way partitioning, set partitioning등이 있음. 우선 way partitioning의 경우, 구현은 쉽지만 그 단위가 coarse-grained하다는 문제가 있음. 생성할 수 있는 partition의 수가 way의 수에 제약됨. 그리고 way partitioning을 하게 되면 associativity가 떨어지게 됨. Strided access pattern에 취약해질 수 있음. 이러한 associativity 손실을 막고자 캐시를 set으로 나눌 수 있음 (reconfigurable cache, molecular cache). 하지만 이렇게 하는 것은 캐시 구조에 많은 변화를 요구함. 그리고 set partitioning을 적용하기 위해서는 모든 프로세스의 주소 공간이 완벽히 분리되어 있어야 함 (왜?… 잘 이해되지 않음 -> 관련 논문 읽어봐야 이해할 수 있을 듯). Page coloring도 strict하게 cache partitioning을 할 수 있는 한 가지 방법이다. 하지만 이 경우에 coarse-grained하다는 문제점이 있고, 캐시가 hash indexing을 쓰고 있다면 효과가 없다는 문제가 있음.
Soft partitioning은 캐시 할당 또는 교체 기법의 조정을 통해 partition을 생성, 관리함. Soft partitioning은 strict partitioning의 문제들 (coarse-grained하다는 점, 하드웨어 수정이 필요하다는 점)은 없으나, partition 사이에 간섭이 발생할 수 있다는 문제와 partition 크기 조절이 힘들다는 문제가 있음. Soft partitioning의 사례로 selective cache allocation과 pseudo-insertion pseudo-partitioning(PIPP)이 있으나, PIPP의 경우에는 scalable하지 않음.
– 이상적인 cache partitioning 기법, 기존의 partitioning 기법에 대한 비교 대조를 해주고 있어서 도움이 되었음. Cache partitioning의 개념을 잡는 것에 도움이 되었음.
vantage comparison.PNG
– Vantage는 교체 시점에 partition size를 유지한다. 평균적으로 각 partition의 삽입과 교체 수준을 관리함으로써 partition 크기를 유지한다. 이것이 churn-based management이다. 하지만 이렇게 평균적으로 partition 크기를 유지하는 것은 partition 사이의 간섭을 일으킬 수 있다. 이를 해결하기 위해 Vantage는 cache 전체를 partition하지 않고, 일부만을 partition한다. 전체 cache를 managed region과 unmanaged region으로 나누고, managed region만을 partition한다. 이렇게 하면 eviction은 항상 unmanaged region에서 일어나도록 해, managed region 내에 있는 partition끼리의 간섭은 제거할 수 있음.
– Cache에서 managed region과 unmanaged region을 나누는 것에는 zcache에서 사용한 analytical framework를 적용한다. 캐시의 각 캐시 라인이 모두 0에서 1 사이의 eviction priority를 가진다고 할 때, eviction probability의 분포는 1에 가까워야 한다. Associativity가 높을수록 eviction probability가 1에 몰려있고, associativity가 낮을수록 eviction probability가 1에 몰려있지 않다. Associativity가 높을수록 쫓겨나야 할 cache line이 쫓겨난다는 의미. Vantage는 zcache에서 구현되는 것을 가정하고 있으며, 전체 캐시를 managed region과 unmanaged region으로 나눌 때 이 개념을 적용한다. Cache replacement가 발생할 때 교체가 대부분 unmanaged region에서 발생하도록 함으로써, managed region에서 발생하는 교체를 최소화한다. Unmanaged region이 일종의 victim cache로 동작하는 것.
vantage region division.PNGvantage concept.PNG
– Vantage에서는 unmanaged region으로 보내기 위한 일종의 threshold를 정하는데, 이 threshold가 aperture이다. Aperture가 10%인 경우, eviction priority가 0.9 이상이면 unmanaged region으로 demote한다.
– 모든 partition이 동일한 size와 churn을 갖는다면, aperture는 모두 동일함. 한편, 한 partition의 size가 작을수록, churn이 높을수록 aperture는 커진다. 큰 aperture는 eviction 대상에 선정되기 힘듦을 의미한다. 따라서 size가 작은 partition에서 많은 캐시 라인을 evict하는 것이 맞으므로 aperture가 상대적으로 크게 설정됨. 그리고 insertion rate이 높을수록 더 많은 캐시 라인을 evict해야 하므로 aperture가 상대적으로 크게 설정됨.
– 이렇게 제안한 Vantage 기법은 fine-grained partition을 제공한다는 장점이 있지만 현실적으로 무리인 가정을 한 것이 세 가지 있음. 계산을 너무 많이 요구함. Robust하지 않음. 모든 캐시 라인의 eviction priority를 알아야 함. 이와 같은 가정 없이도 구현할 수 있도록 두 가지 대안을 제시함. feedback-based aperture control, setpoint-basd demotion을 제안함. Feedback-based aperture control은 feedback에 기반해 aperture를 설정하겠다는 것. Setpoint-based aperture control은 timestamp를 기준으로 demotion을 결정하겠다는 것.
– cache side-channel attack 방어를 위해 cache partitioning하는 논문도 소개하고 있었음. [BSDCan’05] Cache missing for fun and profit


2. [ISCA’13] ZSim: fast and accurate microarchitectural simulation of thousand-core systems 읽기 (paper, slides)
– 이 논문은 microarchitectural simulator에 관련된 논문이다. 아키텍쳐 연구에서 simulation을 사용하고 있는데, simulation은 느리다는 문제점이 있다. ZSim에서는 세 가지 기법을 사용해 simulator를 가속하고자 한다.
– 아키텍쳐 연구에서 simulation을 사용해 연구를 진행하는데, simulator가 느리다. gem5, Flexus, MARSS 모두 200KIPS에 불과하다. 이 속도로는 1초 실행을 simulation하는데 8시간이 걸림. ZSim의 속도는 최대 1500MIPS라고 함.
zsim introduction.PNG
– Ideal한 simulator라면 빠르고 정확하며, 다양한 워크로드를 실행할 수 있어야 한다. 그리고 수정하기도 쉬워야 함. 이러한 조건들을 모두 만족하는 simulator가 없음. 빠른 simulation을 위한 기법으로 FPGA와 병렬 시뮬레이션(parallel and discrete evente simulation) 등이 제안되었음. FPGA는 개발이 어렵고 컴파일에 너무 오랜 시간이 소요됨. 그리고 병렬 시뮬레이션은 동기화를 너무 자주 하는 바람에 scalability가 떨어짐.
– 여기서는 크게 세 가지 기법을 사용해 simulation의 속도 향상을 도모한다. Dynamic binary translation에 기반한 instruction driven timing model을 사용해 시뮬레이션을 10~100배 정도 가속한다. 그리고 기존의 병렬 시뮬레이션이 동기화를 너무 자주한다는 문제를 해결하고자 bound-weave algorithm을 사용해 병렬 시뮬레이션을 수행한다. 마지막으로 lightweight user-level virtualization을 통해 다양한 워크로드 실행을 가능하도록 한다.
zsim techniques.PNG– Daniel Sanchez의 논문을 연달아 읽게 되었는데, 어느 정도 공통점이 있는 것 같다. 우선 논문 제목이 Z로 시작한다는 점이 Zcache와 동일함. 그보다도 ideal한 것을 정의하고, 현재와 비교해 차이점을 파악해서 그 차이를 해결하려는 시도가 유사함. Vantage에서는 ideal partitioning 기법에 대해 정의하고, 현재와의 gap을 파악해 문제를 해결하려 했음. 여기에서도 ideal simulator에 대해 정의하고, 현재와의 gap을 파악해 문제를 해결함. 연구 문제 발견 및 해결에 좋은 접근 방법인 것 같다.
– Section 2에서는 여러가지 simulation 기법에 대해 소개하고 있음. Simulation 기법은 크게 user-level vs full-system; functional vs timing; trace-driven vs execution driven; cycle-driven vs event driven으로 나눌 수 있다고 함.
– Emulation 기법은 명령어를 해석한 것을 바탕으로 functional model과 timing model을 구동해 결과를 보는 것. gem5, Flexus, MARSS가 여기에 속한다고 함. 한편 instrumentation-based 기법은 simulation 시점에서 binary에 instrumentation call을 삽입해 실험하는 것. Instrumentation을 통해 timing model을 구동하며, 이 때문에 functional model에 대한 필요가 없다고 함. CMPSim, Graphite 등이 여기에 속한다고 한다.
– Full-system simulator는 운영체제를 지원하기 위한 특권 모드와 주변 장치까지 지원하는 simulator이다. 이를 사용하면 multithreaded, multiprocess 워크로드를 실행할 수 있음. gem5, Flexus, MARSS가 여기에 속함. User-level simulator는 user application만 실행함. 따라서 user-level simulator는 단순한 워크로드밖에 실행하지 못함.
– 첫째로 ZSim에서는 instruction driven timing simulation을 통해 10~100배 가속한다고 함. OoO 코어 모델은 Westmere를 본따 모델링했으며, 검증 결과 몇 가지 알려지지 않은 사항을 제외하고는 같다고 한다. 다만 아직 instruction driven timing simulation이 어떻게 동작하는지 잘 이해가 되지는 않음. Cycle-accurate full-system simulator인 MARSS는 사용해보았지만, 그 외의 코드는 본 적이 없기 때문이다. 아마 관련 simulator를 사용해보고, 코드를 보다 보면 이해할 수 있을 것이라 생각함. 그래도 기회가 된다면 알아보도록 하자.
– 둘째로 ZSim에서는 병렬 시뮬레이션에서 발생할 수 있는 synchronization 오버헤드를 줄이고자 bound-weave algorithm을 사용함. 병렬 실행에서는 path-altering interference와 path-preserving interference가 발생함. Path-altering interference는 짧은 시간동안 실행된다면 거의 발생하지 않음. 이 점에 착안해 짧은 실행 시간동안 path-altering interference를 무시하고 그대로 실행하고(bound), 그 이후에 이벤트 순서를 맞추는 방식(weave)으로 simulation한다.
– 셋째로 수천 개의 코어를 simulation하기 위해 user-level에서 lightweight 가상화를 적용함.
– 전반적으로 하고자 하는 내용은 어느 정도 이해가 되면서도, 상세한 것까지 모두 이해하기는 힘들었음. Simulator를 어느 정도 써보긴 했지만, 그래도 simulator를 다양하게 많이 써보지는 못했기 때문이다. 그리고 기존에 있다는 문제들에 대한 이해도 부족했음. 병렬 시뮬레이션에서 발생하는 문제가 무엇인지, path-altering interference, path-preserving interference는 무엇인지, 각 simulator 방식의 장단점과 특징은 무엇인지, instruction driven timing simulation은 무엇인지 등.
– Path-altering interference는 여러 개의 메모리 요청이 OoO로 실행됨으로 인해, 요청의 처리 경로가 경우에 따라 달라지는 문제. 두 개의 요청 A, B가 있을 때, 요청 A가 요청 B의 캐시 블록을 쫓아내는 경우에 OoO 실행으로 인해 경로가 바뀔 수 있음. 또는 두 개의 요청 A, B가 같은 캐시 블록을 요청하는 경우, 누가 먼저 도착하느냐에 따라 경로가 바뀜. Path-preserving interference는 경로는 바뀌지 않지만 timing이 달라지는 문제. 서로 다른 두 요청이 같은 bank에 접근하는 경우에 발생할 수 있다.
zsim interference.PNG


3. Path ORAM에 대한 세미나
– 오늘 승흔이가 ORAM과 path ORAM에 대해 발표함. 관련된 내용은 2016/01/18에 추가함.


4. Milos Prvulovic, High Performance Computer Architecture
– 오늘도 Udacity에서 Milos Prvulovic의 컴퓨터 구조 강의를 들었음. Many cores 섹션을 들음. Many-core system에서 발생할 수 있는 문제에 대해 설명함.
many core challenges.PNG
– 첫째로 코어의 수가 증가하면, coherence traffic이 증가함. 그리고 코어의 수가 증가함에 따라 쓰기 연산이 많아져, bus throughput 요구량이 높아짐. Bus가 bottleneck이 되고, 이를 해결하기 위한 on-chip network가 필요해짐. Bus는 코어의 수가 늘어나면 더 낮은 속도로 동작해야 하므로 bandwidth는 떨어지는데, bus 사용량은 많아져 bus가 bottleneck이 됨. Mesh의 경우에는 코어 수의 증가에 따라 bandwidth도 높아지는 장점이 있음.
many core challenges 1.PNG
– 둘째로, 코어의 수가 증가하면 off-chip traffic이 증가함. 코어 당 cache miss의 수는 동일한데, 코어의 수가 늘어나므로 전체 miss의 수가 늘어나는 것이다. Cache miss가 많아지면 memory request가 많아지는 것도 당연함. 하지만 프로세서의 칩 수는 늘어나지 않으므로 bottleneck이 발생함. 이런 memory request를 줄이기 위해 LLC의 크기를 더 크게 하는 방법이 있을 수 있지만, 이렇게 되는 경우에 한 개의 큰 캐시가 발생하는 문제가 있음. 한 개의 LLC를 여러 개의 코어가 공유하면 bottleneck이 됨. 이를 방지하고자 distributed LLC를 사용할 수 있음.
many core challenges 2.PNG

– Distributed LLC는 여러 개의 LLC slice가 한 개의 LLC처럼 동작하게 됨. 하지만 slice 되어 있으므로, 여러 개의 interface를 가질 수 있어 bottleneck 현상이 해소됨. 그렇다면 데이터를 어느 LLC slice에 넣느냐는 문제가 생김. Round robin으로 넣을 수도 있을 것이나, 그렇게 되면 locality가 떨어짐. 이를 해결하고자 운영체제의 page에 기반해 분산할 수도 있음.
many core challenges 2 distributed LLC.PNG
– 셋째로 coherence directory가 너무 커질 수 있다는 문제가 있음. 모든 메모리 블록에 대한 정보를 유지하지 않고, 일부만 유지하는 partial directory를 사용함. 실제로 사용하는 것만 유지한다. 모든 directory entry가 사용되면 LRU 사용해 교체한다.
– 넷째로 코어끼리 전력을 나눠 사용해야 한다는 문제가 있음. 전력 공급이 같을 때, 코어의 수가 많아질수록 한 코어가 사용 가능한 전력은 줄어듦. 따라서 frequency를 낮출 수밖에 없고, 결과적으로 single threaded program은 낮은 성능을 보이게 된다. 한편, 이런 문제를 해결하기 위해 frequency boosting을 사용할 수 있음. 하지만 이 경우에도 모든 전력을 사용하지는 못함. 과열이 발생할 수 있기 때문이다.
many core challenges 4.PNG– 마지막으로 운영체제가 프로세서를 잘 이해하지 못해, 제대로 사용하지 못하는 문제가 발생할 수 있음. 네 개의 코어를 가진 두 개의 칩에서 SMT를 활성화해 사용한다고 하자. 세 개의 쓰레드를 실행한다고 할 때, 프로세서를 이해하지 못하면 두 개의 칩 중에 한 개의 칩만 사용할 수 있음. 이러한 문제를 해결하려면 소프트웨어가 프로세서를 이해하고 있어야 함.

Advertisements
Tagged with: , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,
Posted in 1) Memo

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

누적 방문자 수
  • 98,786 hits
%d bloggers like this: