Fri 22 Jun 2018 17:00 - 17:25 at Grand Ballroom AB - Parallelism Chair(s): Julian Dolby

A classic problem in parallel computing is to take a high-level parallel program written, for example, in nested-parallel style with fork-join constructs and run it efficiently on a real machine. The problem could be considered solved in theory, but not in practice, because the overheads of creating and managing parallel threads can overwhelm their benefits. Developing efficient parallel codes therefore usually requires extensive tuning and optimizations to reduce parallelism just to a point where the overheads become acceptable.

In this paper, we present a scheduling technique that delivers provably efficient results for arbitrary nested-parallel programs, without the tuning needed for controlling parallelism overheads. The basic idea behind our technique is to create threads only at a beat (which we refer to as the "heartbeat") and make sure to do useful work in between. We specify our heartbeat scheduler using an abstract-machine semantics and provide mechanized proofs that the scheduler guarantees low overheads for all nested parallel programs. We present a prototype C++ implementation and an evaluation that shows that Heartbeat competes well with manually optimized Cilk Plus codes, without requiring manual tuning.

Fri 22 Jun
Times are displayed in time zone: Eastern Time (US & Canada) change

16:10 - 17:25: ParallelismPLDI Research Papers at Grand Ballroom AB
Chair(s): Julian DolbyIBM Thomas J. Watson Research Center
16:10 - 16:35
Talk
PLDI Research Papers
Changwan Hong, Aravind Sukumaran-RajamOhio State University, USA, Jinsung KimOhio State University, USA, Prashant Singh Rawat, Sriram KrishnamoorthyPacific Northwest National Laboratories, Louis-Noël PouchetColorado State University, Fabrice RastelloINRIA, P. SadayappanOhio State University
Media Attached
16:35 - 17:00
Talk
PLDI Research Papers
Roshan DathathriUniversity of Texas at Austin, USA, Gurbinder GillUniversity of Texas at Austin, USA, Loc HoangUniversity of Texas at Austin, USA, Hoang-Vu DangUniversity of Illinois at Urbana-Champaign, USA, Alex BrooksUniversity of Illinois at Urbana-Champaign, USA, Nikoli DrydenUniversity of Illinois at Urbana-Champaign, USA, Marc SnirUIUC, Keshav PingaliUniversity of Texas at Austin, USA
Media Attached
17:00 - 17:25
Talk
PLDI Research Papers
Umut A. AcarCarnegie Mellon University, Arthur CharguéraudInria, Adrien Guatto, Mike Rainey, Filip SieczkowskiUniversity of Wrocław
Media Attached