Limits of Instruction-Level Parallelism Capture

We analyse the capacity of different running models to benefit from the Instruction-Level Parallelism (ILP). First, we show where the locks to the capture of distant ILP reside. We show that i) fetching in parallel, ii) renaming memory references and iii) removing parasitic true dependencies on the stack management are the keys to capture distant ILP. Second, we measure the potential of a new running model, named speculative forking, in which a run is dynamically multi-threaded by forking at every function and loop entry frontier and threads communicate to link renamed consumers to their producers. We show that a run can be automatically parallelized by speculative forking and extended renaming. Most of the distant ILP, increasing with the data size, can be captured for properly compiled programs based on parallel algorithms