20160120

1. [HPCA’15] Priority-based cache allocation in throughput processors 읽기 (paper)
– 높은 throughput을 내고 memory latency를 숨기고자, GPU에서는 대량의 multithreading을 사용한다. 그러나 multithreading은 공유 자원에 대한 경쟁을 유발할 수 있고, 이로 인해 성능 저하가 발생할 수 있다. 선행 연구들에서 이런 문제를 해결하고자 throttling을 제안했다. 캐시에 대한 쓰레드 경쟁을 줄이고자 thread-level parallelism을 throttling하는 것. 하지만 throttling을 통한 해법은 공유 자원의 underutilization을 유발할 수 있다. 이 논문에서는 이를 해결하고자 쓰레드 스케쥴링을 캐시 관리 기법과 연관하는 priority-based cache allocation (PCAL)을 제안한다.
– 병렬 처리 어플리케이션을 실행하기 위해 GPU가 널리 사용되고 있음. GPU는 메모리 접근 시간을 줄이고 처리량을 늘리고자 대량의 multithreading을 사용한다. 최근에는 GPU 메모리 시스템도 캐시를 적용하고 있다. GPU에서 locality를 살리는 것이 성능 향상에 중요해지고 있다. 하지만 실제로는 여러 개의 쓰레드가 동시에 실행되면서, 쓰레드가 경쟁 상태에 놓이는 경우가 많다. 이러한 경쟁은 cache sensitive한 어플리케이션의 성능을 크게 떨어뜨린다. 이처럼 쓰레드 수준의 병렬성은 증가했으나, 공유 자원에 대한 경쟁의 증가로 인해 성능이 떨어지는 현상을 performance valley라고 한다 (Figure from paper).
performance valley.PNG
– GPU 캐시의 효율성을 높이기 위해 최근 연구에서는 쓰레드 수준의 병렬성을 제한해 캐시 경쟁을 줄이고자 했다(throttling). Throttling 기법은 시스템 전체에서 사용 가능한 쓰레드의 수를 줄임으로써 캐시 경쟁을 줄인다. Throttling 기법은 그 특성 상, 시스템에서 사용 가능한 공유 자원을 효율적으로 사용하지 못한다는 문제점이 있다.
– 이를 해결하고자 이 논문에서는 priority-based cache allocation(PCAL)을 제안한다. Thread level parallelism을 조절해 병렬성을 제한해, 전체 시스템이 performance valley에 빠지는 것을 막으면서도, 공유 자원의 낭비가 없도록 하는 것이다. 기존의 throttling에서는 active한 thread들이 모두 캐시를 사용할 수 있었다면, PCAL은 전체 쓰레드를 regular threads와 non-polluting threads로 분류하고, regular thread들만 캐시를 사용할 수 있도록 한다. 기존의 throttling 기법과 비교해 PCAL은 더 많은 수의 thread를 실행함으로써, performance valley에 빠지지 않게 하면서도 공유 자원을 최대한 사용할 수 있는 것이다. regular threads와 non-polluting threads의 구분은 priority token을 사용해 구분한다. Priority token을 보유한 thread만 캐시를 사용할 수 있다. Priority token을 가진 thread만이 캐시에 삽입하거나, 캐시로부터 캐시 블록을 빼낼 수 있다 (Figure from paper).
PCAL architecture.PNG
– 실험에는 GPGPU-Sim을 사용함. NVIDIA GTX480에 맞추어 실험함.
– PCAL과 유사한 연구로 bypass-on-stall (BOS)가 있었음. BOS는 선행 요청이 끝나기를 기다리지 않고, 캐시를 건너뛰는 기법이다. 선행 요청이 이미 모든 캐시 블록을 사용하고 있거나, 모든 MSHR을 사용하고 있으면, 선행 요청이 끝나기를 기다리지 않고 캐시를 bypass한다.
– 이 연구에서는 PCAL에서 적용할 수 있는 전략 두 가지를 소개할 수 있다. ITLP, MTLP이다. ITLP는 캐시 hit rate를 유지하면서 TLP를 증가시키는 전략이다. 쓰레드 throttling을 적용한 다음, 공유 자원이 충분히 사용되지 않은 상황에서 적용한다. Priority token을 실행 중인 쓰레드에게 모두 나누어준다. 이로써 실행 중인 쓰레드들은 regular thread가 된다. 그 다음, 공유 자원을 모두 사용할 수 있게끔 non-polluting 쓰레드를 추가한다. MLTP는 TLP를 유지하면서 캐시 hit rate를 증가시키는 전략이다. Throttling을 적용한 다음에 공유 자원이 충분히 사용되고 있다면, non-polluting 쓰레드를 더 추가할 수 없다. 이 때에는 쓰레드의 수는 유지하면서 regular thread의 수를 줄여나간다. 이로써 TLP를 줄이지 않고도 캐시 효율을 높일 수 있다.
– 이러한 전략을 실제로 static PCAL과 dynamic PCAL을 사용해 적용할 수 있다. static PCAL은 소프트웨어 수준에서 프로그래머가 미리 파라메터를 조절하는 것이고, dynamic PCAL은 프로그래머의 도움 없이 동적으로 파라메터를 조절하는 것이다.


2. [SOSP’15] COZ: Finding Code that Counts with Causal Profiling 읽기 (paper, slides)


– 개발자에게는 소프트웨어의 성능을 개선하는 것이 중요하다. 최적화할 지점을 찾기 위해 개발자들은 profiler에 의존하지만, profiler는 프로그램이 해당 코드를 실행한 시간만 보여준다. 이러한 정보는 프로그램을 최적화하는 것에 도움을 주지 못한다. 이 논문에서는 causal profiling을 제안한다. causal profiling은 프로그래머에게 정확히 어느 부분을 최적화하는 것이 성능 개선에 도움이 되는지 알려준다. causal profiling은 performance experiments를 실행 중에 수행함으로써 이뤄진다. 매 performance experiments마다 코드를 virtually speeding up 함으로써 성능 개선이 미치는 효과를 확인한다. Virtual speed up은 해당 라인의 속도를 직접 빠르게 할 수는 없으므로, 다른 것을 상대적으로 느리게 해서 속도 향상 효과를 확인하는 것이다. 추가적으로, causal profiling은 throughput과 latency의 측정도 가능하게 한다. 개발자들이 throughput을 측정하기 위해서는 특정 지점에 progress point를 삽입하면 된다. progress point를 지나는 요청의 수를 측정해 throughput을 확인할 수 있다. throughput을 측정하기 위해서는 progress point 한 개, latency를 측정하기 위해서는 progress point 두 개를 사용하면 된다.
– Evaluation section이 마음에 듦. vCache에서도 같은 방식으로 evaluation을 작성함.
– Coz가 performance experiments마다 virtually speed up 할 코드를 선택할 때에는 최근에 실행된 코드를 선택한다.
– Little’s Law를 사용하면 throughput에서 latency를 유도할 수 있음.
littles law.PNG
– causal profiling이라는 새로운 개념을 소개한 것은 신선함. 게다가 causal profiling의 구현을 해서 github에 공개까지 함 (https://github.com/plasma-umass/coz). 실제로 가속할 수는 없으므로 virtual speed up이라는 개념을 도입한 것도 좋음. 그리고 최근에 많이 사용되는 multi-thread workload를 고려해, latency, throughput을 측정할 수 있는 progress point를 도입한 것도 좋음.
– 하지만 causal profiling이 항상 같은 profiling 결과를 낼 수 있는지는 의문스러움. Virtually speed up할 코드를 선택할 때, 최근에 실행한 코드를 선택한다고만 되어있음. 그리고 speed up할 때 그 비율도 랜덤하게 선택함 (0~100% 사이에서 5 단위로). 이렇게 했을 때, speed up potential이 매번 다르게 보이지는 않는지 궁금함. 그리고 execution path가 매번 다르다면 profiling이 되지 않는 경우도 생길 수 있을 것 같음. Virtual speed up이 실제로 speed up이 되지 않는 것을 가상으로 speed up해보겠다는 것인데, 말 그대로 “virtual” speed up 이므로, 실제로 해당 부분이 가속이 될 것인지 아닌지는 알 수가 없음. Virtual speed up을 사용하면 전체 실행 시간 중에서 critical path에 있으면서, 가장 많은 실행 시간 비율을 차지하는 루틴을 찾을 수는 있을 것 같음. 하지만 그렇다고 해서 그 루틴이 덜 optimize되었다는 것을 의미하지는 않음. optimize 불가능할 수도 있음. 그리고 virtual speed up을 통해 실행 시간에 미치는 영향을 보겠다는 것이, 어떻게 보면 motivation과 상반되는 내용일 수 있음. Virtual speed up을 통해 전체 실행 시간에 큰 영향을 미치는 루틴은, 기존의 실행 시간 기반의 profiling에서도 긴 실행 시간을 차지했을 가능성이 높음.
– Evaluation의 작성 방식이 마음에 듦. Evaluation을 작성할 때마다 어떻게 작성해야 하는지 고민되는데, 해당 section에서 보이고자 하는 것을 먼저 이야기하고 이를 결과로 보여주는 방식이 좋았음. [MICRO’15] vCache: Architectural Support for Transparent and Isolated Virtual LLCs in Virtualized Environments에서도 같은 방식을 택하고 있었음.

In this section, we evaluate vCache in three key aspects. First, we show that…

– 발표 영상을 보았는데, 도움이 많이 되었다. 학회장에서는 질문이 갑자기 나와 잘 이해되지 않는 경우가 많았다. 발표 영상을 꾸준히 보는 것이 질문 이해에 도움이 될 것 같다. 질문할 때 그리고 답변할 때 일반적으로 쓸 수 있는 문장을 배울 수 있었다.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

Recent Posts
누적 방문자 수
  • 144,084 hits
%d bloggers like this: