Mathematics Events
[PAST EVENT] Model-Centric Speculative Parallelization for Scalable Data Processing
Access & Features
- Open to the public
Speaker: Junqiao Qiu from UC Riverside
Abstract:
Exploiting parallelism is key to designing and implementing high-performance data processing on modern processors. However, there are many data processing routines running in serial, due to the sequential nature of their underlying computation models, such as finite-state machines (FSMs), a classic but inherently sequential computational model with applications in data decoding, parsing, and pattern matching.
In this talk, I will present techniques using speculation to “break” the inherent data dependencies, thus enabling scalable data-parallel processing. First, I will introduce a basic speculative parallelization scheme that breaks the state transition dependencies in FSM computations. Then, more interestingly, I will show how a broader range of applications, known as bitstream processing, can benefit from FSM-based speculative parallelization techniques. The key idea is to extract the variable bits that cause dependencies from programs and model their value-changing patterns with FSMs. Such techniques, for the first time, offer a principled approach to addressing the parallelization challenges in bitstream programs. With this approach, we demonstrate that a rich set of performance-critical bitstream kernels can be effectively parallelized, with up to linear speedups on parallel processors. Finally, I will also briefly discuss the major challenges in designing effective speculative parallelization frameworks for FSM-based computations and present some of my forward-looking research ideas.
Short Bio
Junqiao Qiu is a Ph.D. candidate in the Computer Science and Engineering Department at University of California Riverside, advised by Prof. Zhijia Zhao. He received his Bachelor's degree in Electronics and Communications Engineering from Sun Yat-sen University in 2011. His research interests are broadly in the area of programming systems and runtime support for parallel computing and scalable data processing. He is a recipient of the Dissertation Year Program (DYP) Award and Dean’s Distinguished Fellowship.
Contact
Bin Ren