HASS: A Scheduler for Heterogeneous Multicore Systems

※ 2013년 12월 15일 작성된 자료임

Daniel Shelepov et al, "HASS: a scheduler for heterogeneous multicore systems," ACM SIGOPS Operating Systems Review 43.2 pp. 66-75, 2009

Summary

본 논문은 Single-ISA heterogeneous multi-core processor의 전체 throughput을 향상시킬 수 있는 스케줄링 알고리즘을 제안한다. 해당 논문이 출판되는 시점까지 관련 연구들이 봉착하고 있었던 가장 큰 문제는 낮은 성능의 코어에서 높은 성능의 코어로 프로세스가 이동했을 때 어느 정도 성능 향상이 이루어 질지 예측하기 힘들다는 것이었다. 많은 연구들이 동적인 CPI 모니터링 같은 오버헤드가 높은 수단에 의지하고 있었다. 본 논문은 memory-bound 프로세스가 상대적으로 성능 향상이 작다는 점에 착안한다. 사전 모니터링을 통해 memory-bound 프로세스들을 구분하기 위한 정보(last-level cache miss rate)를 저장하고, 스케줄링 때 이 정보를 사용하여 해당 프로세스들을 낮은 성능의 코어에 할당시키며 문제를 해결한다. 실험 결과 효과적으로 memory-bound 프로세스들을 구분해 내었으며, 최대 13%의 성능 향상을 보였다.

Different speedup of a memory-bound process and a CPU-bound process in heterogeneous multicores

Review

이 논문의 저자들은 논문이 출판된 2009년을 기점으로 유수의 학회에 관련 논문을 제출하며 전성기를 맞는다. (TOCS '12, SIGMETRICS '13) 그런 점에서 single-ISA heterogeneous multi-core processor에 관심이 있는 사람이라면 아이디어를 확인하고 넘어갈 필요가 있다. 본 논문의 contribution은 다음과 같다.

1. CPI (cycles per instruction) 같은 복잡한 metric에 의존하지 않고, 프로세스의 특성을 사용하여 speedup을 예측하는 방법을 제시하였다.
2. 오버헤드를 줄이기 위해 offline 모니터링을 제안하였고, 실험 결과 훌륭한 예측률을 보였다.

물론 연구가 초기 단계였기 때문에 해결책이 정교하지 못하다는 점에서 아쉬움이 남는다. Memory latency를 상수로 두는 가정은 현대의 NUMA architecture에 적합하지 않다. Memory stall을 제외하였을 때의 speedup이 모든 프로세스에 대해 상수라는 가정도 좀 비약이 아닐까 싶다. 스케줄링 알고리즘에서 optimal assignment와 regular assignment 사이의 분기 조건도 명시하지 않았다.