sponsored byIEEEACMThe International Conference for High Performance 
Computing, Networking, Storage and Analysis
FacebookTwitterGoogle PlusLinkedInYouTubeFlickr

SCHEDULE: NOV 16-21, 2014

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

Optimizing Data Locality for Fork/Join Programs Using Constrained Work Stealing

SESSION: Data Locality and Load Balancing

EVENT TYPE: Papers

TIME: 2:00PM - 2:30PM

SESSION CHAIR: Didem Unat

AUTHOR(S):Jonathan Lifflander, Sriram Krishnamoorthy, Laxmikant V. Kale

ROOM:388-89-90

ABSTRACT:

We present an approach to improving data locality across different phases of fork/join programs scheduled using work stealing. The approach consists of: (1) user-specified and automated approaches to constructing a steal tree, the schedule of steal operations and (2) constrained work stealing algorithms that constrain the actions of the scheduler to mirror a given steal tree. These are combined to construct work stealing schedules that maximize data locality across computation phases while ensuring load balance within each phase. These algorithms are also used to demonstrate dynamic coarsening, an optimization to improve spatial locality and sequential overheads by combining many finer-grained tasks into coarser tasks while ensuring sufficient concurrency for locality-optimized load balance. Implementation and evaluation in Cilk demonstrate performance improvements of up to 2.5x on 80 cores. We also demonstrate that dynamic coarsening can combine the performance benefits of coarse task specification with the adaptability of finer tasks.

Chair/Author Details:

Didem Unat (Chair) - Koç University

Jonathan Lifflander - University of Illinois at Urbana-Champaign

Sriram Krishnamoorthy - Pacific Northwest National Laboratory

Laxmikant V. Kale - University of Illinois at Urbana-Champaign

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar


Paper provided by the ACM Digital Library

Paper also available from IEEE Computer Society