Challenging the 'Embarrassingly Sequential': A Principled Approach to Parallelize Finite State Machines

Speaker:        Zhijia Zhao
                College of William and Mary

Title:          "Challenging the 'Embarrassingly Sequential':
                A Principled Approach to Parallelize Finite State Machines"

Date:           Monday, 30 March 2015

Time:           11:00am - 12:00 noon

Venue:          Room 1505 (near lifts 25/26), HKUST

Abstract:

Parallelization is key to the computing efficiency and scalability of
modern applications. In the spectrum of parallelism, at the most
challenging end lies the category of Finite-State Machine (FSM)
applications, which are also known as "embarrassingly sequential"
applications. In these applications, the core computation can be
formulated as an abstract machine with a finite number of possible states.
Transitions among the states follow some predefined mechanism that can be
represented with a state-transition graph.

The special difficulty for parallelizing FSM applications is as suggested
by its nickname: They are inherently sequential. Dependences exist between
every two steps of their computations. For the extreme difficulty,
parallelizing general FSM applications has been lying beyond the reach of
existing techniques. This talk will present how to overcome the
difficulties through a principled approach---the first disciplined way of
speculative parallelization. The talk will additionally cover some other
recent progress and exciting opportunities in program parallelization and
optimizations.

***********************
Biography:

Zhijia Zhao is currently a Research Associate at North Carolina State
University, and a PhD candidate at the College of William and Mary. His
research lies in the broad field of programming systems and parallel
computing, with an emphasis on enabling effective parallel execution on
modern computing hardware (e.g. Multicore and GPU). His research includes
collaborations with Intel Labs, IBM Research and Mozilla Foundations.