SCHEDULE: NOV 16-22, 2013

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.

General Transformations for GPU Execution of Tree Traversals

SESSION: GPU Programming

EVENT TYPE: Papers

TIME: 10:30AM - 11:00AM

SESSION CHAIR: Michael Garland

AUTHOR(S):Michael Goldfarb, Youngjoon Jo, Milind Kulkarni

ROOM:205/207

ABSTRACT:
With the advent of programmer-friendly GPU computing, there has been much interest in offloading workloads that can exploit the massive parallelism available on modern GPUs. Exploiting this parallelism and optimizing for the GPU memory hierarchy is well-understood for regular applications that operate on dense data structures such as arrays and matrices. However, there has been significantly less work in the area of irregular algorithms and even less so when dynamic data structures are involved. Recently, irregular algorithms such as Barnes-Hut and kd-tree traversals have been implemented on GPUs, yielding significant performance gains over CPU implementations. However, the implementations often rely on exploiting application-specific semantics to get acceptable performance. We argue that there are general-purpose techniques for implementing irregular algorithms on GPUs that exploit similarities in algorithmic structure rather than application-specific knowledge. We demonstrate these techniques on several tree traversal algorithms, achieving speedups of up to 38x over 32-thread CPU versions.

Chair/Author Details:

Michael Garland (Chair) - NVIDIA

Michael Goldfarb - Purdue University

Youngjoon Jo - Purdue University

Milind Kulkarni - Purdue University

  Click here to download .ics calendar file

  Click here to download .vcs calendar file

  Click here to add event to your Google Calendar

The full paper can be found in the ACM Digital Library