Self-parallelization of sequential object codes

Abstract

This paper describes a novel approach to automatic parallelization of a program at runtime, without any software intervention. A conventional processor is augmented with hardware extensions and N such augmented processors are considered. During normal execution, one of the processors performs conventional sequential execution of a program, while the others capture the control and communication patterns of a sequential segment. Making an optimistic assumption that these patterns are going to be repeated, they compose, on the fly, an equivalent parallel program segment. When the segment is repeated, the N processors switch into a parallel mode and execute the parallel segment. The hardware extensions also enable the processors to detect when the behavior of the program departs from the repeated pattern and to automatically switch to sequential execution from that point with appropriate adjustments to the program state. The parallel segments are cached and switching between sequential and parallel execution takes place as and when appropriate. At all times, program state (equivalent to sequential execution) is preserved and the parallel execution is totally invisible above the machine organization and the scheme is completely devoid of any software intervention. We report preliminary simulations of the concept, which demonstrate good potential to effectively tap parallelism up to a factor of 10 using about 16 processors.