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 known as "embarrassingly sequential" applications. As suggested by its nickname: They are inherently sequential, and hence especially difficulty to parallelize.;This dissertation presents three important classes of computations in this category and a series of model-based techniques to overcome their parallelization challenges. They are: 1)Finite-State Machine (FSM)-based computations, which can be formulated as an abstract machine with a finite number of possible states and transitions among the states; 2)Just-in-Time (JIT) compilation, a key component in compilers for managed programming languages, such as Java and JavaScript; and 3)HTML parsing, the step that transforms unstructured byte streams into tree-like structures in web browsers. Though coming from different domains, they share the same parallelization difficulty -- carrying prevalent dependencies with their computations: The next state in every FSM transition depends on earlier state(s); Each function to compile by JIT compiler depends on previous executed functions; The handling of each byte or token by an HTML parser depends on what it has observed.;For the extreme difficulty, parallelizing these applications has been lying beyond the reach of existing techniques. This dissertation presents how to overcome the difficulties through a principled approach -- the first disciplined way of speculative parallelization. The dissertation additionally covers some other recent progress and exiting opportunities in program parallelization and optimizations. Together, they demonstrate the large potential of the principled approach for advancing the state of the art of code parallelization and optimizations. They represent a new direction to narrow the gap between modern computing hardware and the computing efficiency of software applications.
展开▼
