20160616

1. Deterministic Replay and Data Race Detection for Multithreaded Programs, 이동윤 교수님
Title: Deterministic Replay and Data Race Detection for Multithreaded Programs
Speaker: Prof. Dongyoon Lee (Virginia Tech)
Time: June 16 (Thursday) 11:00 AM
Location: E3-1 #4443 (오상수 세미나실)

Abstract:
With the advent of multiprocessor systems, it is now the role of the programmers to explicitly expose parallelism and take advantage of parallel computing resources. However, multithreaded programs are vulnerable to concurrency errors such as data races. To help programmers develop more reliable and secure concurrent programs, this talk presents DoublePlay, a deterministic replay system; and TxRace, a data race detector.

DoublePlay is an efficient OS-based deterministic replay system that records and reproduces the execution of multithreaded programs on multiprocessors. DoublePlay introduces a new insight that it is sufficient for many replay uses to guarantee only the same output and the final states between the recorded and replayed executions, and thus it is possible to support replay at a low cost.

TxRace is a light-weight dynamic data race detector that leverages commodity hardware transactional memory (HTM) to speed up data race detection. TxRace exploits the observation that the conflict detection mechanism of HTM can be repurposed for data race detection; and addresses challenges in using the current best-effort commodity HTMs.

Speaker Biography:
Dongyoon Lee is an Assistant Professor in the Computer Science department at Virginia Tech. He received the M.S. (2009) and Ph.D. (2013) degrees in Computer Science and Engineering at the University of Michigan, Ann Arbor; and the B.S. (2004) degree in Electrical Engineering from the Seoul National University in Korea. Before joining VT, he worked as an academic visitor in the next generation middleware platforms department at IBM T. J. Watson Research Center. He has been awarded Google Research Award; ProQuest Distinguished Dissertation Award; VMWare Graduate Fellowship; and the best paper at ASPLOS 2011.

많은 시스템에서 멀티코어 시스템을 사용하고 있음. 소프트웨어 수준에서 이를 사용해 성능을 높여야 함. Multithreaded program에서 data race 발생할 수 있음. Therac-2, northeast blackout, NASDAQ stock price mismatch 모두 data race 문제로 인해 생김. 이러한 문제를 해결하기 위한 두 가지 기법을 소개하고자 함.
Determinisitc replay는 data race를 탐지하기 위해 실행을 기록해두었다가, 재생하는 기법이다. Multi-threaded 프로그램 non-deterministic하다는 특성으로 인해 디버깅이 어렵다. 이를 활용하면 올바른 실행인지 추후 확인하기도 쉽다. Uniprocessor에서는 실행의 기록과 재생이 쉬웠다. 하지만 multicore에서 이것이 어려워짐. 지금까지는 multiprocessor replay를 위해서는 외부로부터의 프로그램 입력을 기록했음. 공유 메모리 명령 의존성도 기록되어야 했음. 이같이 하면 value determinism, schedule determinism을 보장할 수 있음. Value determinism은 명령어가 같은 값을 읽고 쓰는 것을 보장. Schedule determinism은 thread interleaving이 같음을 보장. 이 연구에서는 external determinsism을 도입한다. output과 최종 상태가 같음을 보장하는 것. 기존에는 모든 메모리 의존성을 기록했다면, 제안하는 기법에서는 external determinism을 보장할 만큼만 메모리 의존성을 기록하자는 것. Happens-before relationship을 활용하면, 모든 메모리 의존성을 기록하지 않고도 이것을 추정할 수 있다. External determinism을 보장하기 위해서는 system call 입출력을 기록된 것과 비교하면 된다. 만약에 결과가 다르다면 rollback and replay를 수행한다. 일정 epoch 주기로 checkpoint를 뜨고, 상태가 기록된 것과 달라지면 checkpoint된 지점으로 rollback한다(optimistic). Rollback이 반복되면 uniprocessor 모드로 실행한다. Input은 모두 기록된다고 가정한다. 따라서 시간도 recorded process와 replayed process가 동일하다. 스케쥴링만 relax하고자 하는 것. Offline replay는 실행 중에 shadow online replay를 동시에 함으로써 달성한다. Shadow online replay를 pipelining해서 성능을 높인다.
TxRace는 dynamic data race detector이다. 많은 dynamic data race detector가 연구되었다. Software based solution은 sound, complete하지만 오버헤드가 심하다. Hardware based solution은 경량이지만…? 문제가 있다. TxRace는 SW+HW solution을 제안한다. Custom hardware 없이 성능을 높이고자 함. Transactional memory는 transaction의 atomicity를 보장한다. HTM은 transactional memory를 제공하지만, 어떤 명령어로 인해, 어떤 주소에서 발생했는지 알지 못한다(unable to pinpoint). 그리고 HTM은 false conflicts(false positive)가 있을 수 있다. HTM은 cache line을 단위로 conflict를 탐지하기 때문이다. HTM은 non-conflict aborts가 발생할 수 있다. Hardware buffer 초과로 인해 abort될 수도 있고, 입출력으로 인해 abort될 수도 있다. TxRace는 two-phase data race detection이다. HTM를 사용하여 빠르게 potential data race를 확인하고, 이를 SW를 사용해 data race를 sound하고 complete하게 확인한다(google’s Thread Sanitizer). 하지만 이 시스템은 모든 data race를 탐지하지는 못한다(false negative). 실제 하드웨어에서 실행하기 때문에 thread interleaving을 마음대로 조정하지 못하기 때문.
하드웨어 기반의 data race detector는 일반적으로 cache coherence protocol을 사용한다. 같은 데이터를 여러 개의 코어가 접근하는지 확인하면 data race를 확인할 수 있기 때문이다.


2. A Case for Specialized Server Architecture, Babak Falsafi (EPFL) 교수님
Title : A Case for Specialized Server Architecture
Speaker : Prof. Babak Falsafi (EPFL)
Time : Tommorow, June. 16 (Thursday) 4 pm
Location : E3-1 #4443 (오상수 세미나실)

Abstract :
Large-scale IT services are now increasingly run in memory due to tight application latency demands. With services centered mostly around data, datacenter owners often integrate as much DRAM into a single blade as technology allows, and use low-latency high-bandwidth network fabrics to aggregate near-neighbor DRAM into large memory pools. DRAM now accounts for a substantial fraction of overall server capital and operation costs, and as such designers are increasingly customizing server hardware, software and infrastructure for online services around memory. In this talk, I will first motivate specialized server design for in-memory computing and then present promising avenues to explore specialization to improve server design.

Speaker Bio :
Babak is Professor in the School of Computer and Communication Sciences and the founding director of the EcoCloud research center investigating data-centric cloud technologies at EPFL. He has made numerous contributions to multiprocessor server design including an architecture underlying the Sun (now Oracle) WildFire/WildCat servers, memory system technologies incorporated in IBM BlueGene/P and Q, and server evaluation methodologies in use by AMD and HP. His latest proposal for server processor designs for scale-out services has laid the foundation for specialized processors such as Cavium ThunderX. He is a fellow of ACM and IEEE.

Dennard scaling이 끝남. Dennard scaling으로 인한 전력 절감 가능성 줄어듦. Data center는 energy-sustainable하지 않다. 미래에는 데이터를 잘 다뤄야하게 될 것. ecocloud 연구센터에서는 에너지 효율적인 데이터 중심 연산을 추구한다. 서버들은 얼마나 효율적인가? 예전에는 클라우드를 위한 벤치마크가 없었고, 이를 확인하기 위해 CloudSuite를 만듦. 대부분의 서버 워크로드가 메모리 요청 처리에 사이클을 소모함. 최대 4 instructions를 retire 할 수 있음에도 평균적으로 1 instruction retire. 인텔이 데스크탑을 타겟으로 프로세서를 디자인했기 때문에 발생하는 현상. 서버 워크로드에서 instruction-fetch miss가 높음. 명령어의 working set 크기가 수 MB에 달함. L1 접근 4 cycles, L2 접근 10 cycles, L3 접근 39 cycles 소모되는데, working set이 너무 커서 캐시 레벨에서 적절히 처리하지 못하고 pipeline이 비어버림. 많은 경우에 miss가 발생하기 때문에 캐시가 수십MB가 있어도 무의미하다. SPEC workload의 경우에는 cache sensitive하더라도, scale out workload는 cache sensitive하지 않다.


3. SoK가 무엇인지 알게 됨
논문을 읽으면서 논문 제목 앞에 SoK라고 붙은 것들이 종종 있어서, 무엇인지 의아했었는데 알게 됨. SoK는 Systematization of Knowledge papers의 약자라고 함 (http://oakland31.cs.virginia.edu/cfp.html).

Systematization of Knowledge Papers. In addition to the standard research papers, we are also soliciting papers this year focused on systematization of knowledge. The goal of this call is to encourage work that evaluates, systematizes, and contextualizes existing knowledge. These papers will provide a high value to our community but would otherwise not be accepted because they lack novel research contributions. Suitable papers include survey papers that provide useful perspectives on major research areas, papers that support or challenge long-held beliefs with compelling evidence, or papers that provide an extensive and realistic evaluation of competing approaches to solving specific problems. Submissions will be distinguished by a checkbox on the submission form. They will be reviewed by the full PC and held to the same standards as traditional research papers, except instead of emphasizing novel research contributions the emphasis will be on value to the community. Accepted papers will be presented at the symposium and included in the proceedings.

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

누적 방문자 수
  • 88,534 hits
%d bloggers like this: