Skip navigation

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

Event Date: April 16, 2015
Speaker: Zhijia Zhao
Speaker Affiliation: North Carolina State University
Time: 10:30am
Location: MSEE 239
Contact Name: Professor Sam Midkiff
Contact Phone: 765-49-43440
Contact Email:


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 exiting opportunities in program parallelization and optimizations.



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 through principled approaches. His research includes collaborations with Intel Labs, IBM Research and Mozilla Foundations.