SC13 Home > SC13 Schedule > SC13 Presentation - Towards Tera-Scale Performance for Longest Common Subsequence Using Graphics Processors

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.

Towards Tera-Scale Performance for Longest Common Subsequence Using Graphics Processors

SESSION: Research Poster Reception

EVENT TYPE: Posters, Electronic Posters, and Education Posters

TIME: 5:15PM - 7:00PM

AUTHOR(S):Adnan Ozsoy, Arun Chauhan, Martin Swany

ROOM:Mile High Pre-Function

GPUs have been attracting more and more high-performance users recently. However, the computation and memory access patterns in certain classes of algorithms do not lend themselves to hardware optimizations on GPUs, without which they fall far short of the promised performance. One such class of algorithms is longest common subsequence (LCS). In this paper, we describe a novel technique to optimize LCS for one-to-many matching problem on GPUs by transforming the computation into bit-wise operations and a post-processing step. The former can be highly optimized and achieves more than a trillion operations (cell updates) per second (CUPS)---a first for LCS algorithms. The latter is more efficiently done on CPUs, in a fraction of the bit-wise computation time. The bit-wise step promises to be a foundational step and a fundamentally new approach to developing algorithms for increasingly popular heterogeneous environments that could dramatically increase the applicability of hybrid CPU-GPU environments.

Chair/Author Details:

Adnan Ozsoy - Indiana University Bloomington

Arun Chauhan - Indiana University Bloomington

Martin Swany - Indiana University Bloomington

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