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

by Zhai, Antonia Bingheng

A Compiler Algonthm for Scheduling Non-Numeric Code with Explicitly Forwarded data on a Speculative Multiprocessor Antonia Bingheng Zhai Master of Applied Science Graduate Department of Electrical and Computer Engineering University of Toronto 1998 Thread-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 for- warded 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 pardel execution. This the- sis presents a scheduling algorithm that identifies the frequently occurring threôd-casried 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 al- gorithm is able to exploit pardelism between threads, hence significantly improve the performance of the applications on TLDS architecture.