[Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.16 No.1, pp.1-23 (January 1999)

A Compiler-Based Speculative Execution Scheme
For ILP Enhancement

L. Wang and Ted C. Yang+
Graduate Institute of Information Engineering
Feng Chia University
Taichung, Taiwan 407, R.O.C.
+Computer & Communications Research Lab.
Hsinchu, Taiwn 310, R.O.C.
E-mail: tedyang@ccl.itri.org.tw

Instruction-level parallelism (ILP) consists of a family of processor and compiler design techniques that speedup execution by causing individual operations to execute in parallel. For control-intensive programs, however, there is usually insufficient ILP in a basic block for effective exploitation by ILP processors. Speculative execution is the execution of instructions before it is known whether these instructions should be executed. Thus, it can be used to alleviate the effects of conditional branches. To effectively exploit ILP, the compiler must boost instructions across branches. However, a hazard may be introduced by speculatively executed instructions that incorrectly overwrite a value when a branch is mispredicted. To eliminate such side effects, we propose a solution in this paper which uses scheduling techniques. If the result of a boosted instruction can be stored in another location until the branch is committed, the undesired side effect can be avoided. A scheduling algorithm called LESS with a renaming function is proposed for passing different identifiers along different execution paths to maintain the correctness of the program until the data is no longer used or modified. The hardware implementation for this method is relatively simple and rather efficient. Simulation results show that the speedup achieved using LESS is better than that obtained using other existing methods. For example, LESS achieves a performance improvement of 12%, on average, compared to the CRF scheme, a solution proposed recently which uses the concept of shadow register pairs.

Keywords: ILP processors, speculative execution, boosting architecture, compiler scheduling, identifier renaming

Full Text () Retrieve PDF document (200001_01.pdf : 3,563,874 bytes)

Received September 1, 1997; revised May 20 & September 8, 1998; accepted November 2, 1998.
Communicated by Lionel M. Ni.