Title :
Probabilistic Models Towards Optimal Speculation of DFA Applications
Author :
Zhao, Zhijia ; Wu, Bo
Author_Institution :
Dept. of Comput. Sci., Coll. of William & Mary, Williamsburg, VA, USA
Abstract :
Applications based on Deterministic Finite Automata (DFA) are important for many tasks, including lexing in web browsers, routing in networks, decoding in cryptography and so on. The efficiency of these applications are often critical, but parallelizing them is difficult due to strong dependences among states. Recent years have seen some employment of speculative execution to address that problem. Even though some promising results have been shown, existing designs are all static, lack of the capability to adapt to specific DFA applications and inputs to maximize the speculation benefits. In this work, we initiate an exploration to the inherent relations between the design of speculation schemes and the properties of DFA and inputs. After revealing some theoretical findings in the relations, we develop a model-based approach to maximizing the performance of speculatively executed DFA-based applications. Experiments demonstrate that the developed techniques can accelerate speculative executions by a factor of integers compared to the state-of-the-art techniques.
Keywords :
cryptography; deterministic automata; finite automata; network routing; online front-ends; probabilistic automata; DFA application; Web browser; cryptography decoding; deterministic finite automata; model-based approach; network routing; optimal speculation benefit; probabilistic model; speculation scheme; speculative execution; state-of-the-art technique; Adaptation models; Analytical models; Computational modeling; Data models; Decoding; Doped fiber amplifiers; Mathematical model;
Conference_Titel :
Parallel Architectures and Compilation Techniques (PACT), 2011 International Conference on
Conference_Location :
Galveston, TX
Print_ISBN :
978-1-4577-1794-9
DOI :
10.1109/PACT.2011.53