A compiler algorithm for scheduling non-numeric code with explicitly forwarded data on a speculative multiprocessor

grantor: University of TorontoThread-Level Data Speculation (TLDS) aim to improve the performance of non-numeric applications by parallelize likely independent threads. When frequently occurring thread-carried data dependences exist, the sources of the data dependences are explicitly forwarded between threads. With forwarding, the performance of the multi-processor is determined by the critical forwarding path length, which is equal to the non-overlapping portions of the thread. The compiler can schedule instructions to minimize the critical forwarding path length, and improve the performance of the parallel execution. This thesis presents a scheduling algorithm that identifies the frequently occurring thread-carried data dependences and moves the sources of these data dependences as early as possible in the thread. This scheduling algorithm aggressively moves the identified operations and computations that they depend on across a large number of instructions. This algorithm is able to exploit parallelism between threads, hence significantly improve the performance of the applications on TLDS architecture.M.A.Sc