SC13 Home > SC13 Schedule > SC13 Presentation -

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.

SESSION: Applications of Automata Processor in High-performance Parallel Processing

EVENT TYPE: Emerging Technologies

TIME: 5:10PM - 5:30PM

Presenter(s):Srinivas Aluru, Kevin Skadron

ROOM:Booth 3947

The Automaton Processor (AP) directly implements a non-deterministic finite automaton substrate, but provides extra features that make it capable of much more. In fact, it is Turing-complete. This presentation illustrates some additional capabilities of the AP. Aluru will present ongoing work at Georgia Tech for solving bioinformatics applications. Numerous applications in bioinformatics deal with sequence data and finding approximate matches. This talk will focus on the (l,d) motif finding problem, the problem of finding a motif of length l that is present in at least q of the n given sequences, with each occurrence different from the motif in at most d positions. This problem is NP-hard and the largest instance reported to date is (26,11). Using the resources available in a single Automata Processor board, we have been able to design a parallel algorithm to solve many larger instances, including (39,18) and (40,17). Skadron will explain work at the University of Virginia showing how to achieve the fundamental concepts of universal computing - local memory, data/instruction stream and sharing units for different operation on AP. We have implemented two Turing-Machine-equivalent Cellular Automata, Elementary Cellular Automata (ECA) and Game of Life (2D CA), on AP and obtained significant speedup, showing that the AP is Turing-complete. We also show the AP implementations of three other applications: run-length encoding, graph connectivity, and shortest path.

Chair/Presenter Details:

Srinivas Aluru - Georgia Institute of Technology

Kevin Skadron - University of Virginia

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