Fast Paths in Concurrent Programs.

Wen Xu, Sanjeev Kumar, Kai Li.

In the Proceedings of ACM/IEEE International Conference on Parallel Architecture and Compilation Techniques (PACT), Nice, France, September 2004.

Paper: pdf [0.29MB ], ps [0.35MB ]
Talk: ppt

Compiling concurrent programs to run on a sequential pro- cessor presents a difficult tradeoff between execution time and size of generated code. On one hand, the process-based approach to compilation generates reasonable sized code but incurs significant execution overhead due to concurrency. On the other hand, the automata-based approach incurs a much smaller execution overhead but can result in code that is several orders of magnitude larger.

This paper proposes a way of combining the two approaches so that the performance of the automata-based approach can be achieved without suffering the code size increase due to it. The key insight is that the best of the two approaches can be achieved by using symbolic execution (similar to the automata-based approach) to generate code for the com- monly executed paths (referred to as fast paths) and using the process-based approach to generate code for the rest of the program. We demonstrate the effectiveness of this ap- proach by implementing our techniques in the ESP compiler and applying them to a set of filter programs and to VMMC network firmware.