TY - JOUR
T1 - Incorporating speculative execution into scheduling of control-flow-intensive designs
AU - Lakshminarayana, Ganesh
AU - Raghunathan, Anand
AU - Jha, Niraj K.
N1 - Funding Information: Manuscript received August 10, 1998; revised September 1, 1999, This work was supported in part by the National Science Foundation (NSF) under Grant No. 9319269 and in part by Alternative System Concepts, Inc. under an SBIR contract from Air Force Rome Laboratories. This paper was recommended by Associate Editor R. Gupta.
PY - 2000/3
Y1 - 2000/3
N2 - Speculative execution refers to the execution of parts of a computation before the execution of the conditional operations that decide whether they need to be executed. It has been shown to be a promising technique for eliminating performance bottlenecks imposed by control flow in hardware and software implementations alike. In this paper, we present techniques to incorporate speculative execution in a fine-grained manner into scheduling of control-flow-intensitive behavioral descriptions. We demonstrate that failing to take into account information such as resource constraints and branch probabilities can lead to significantly suboptimal performance. We also demonstrate that it may be necessary to speculate simultaneously along multiple paths, subject to resource constraints, in order to minimize the delay overheads incurred when prediction errors occur. Experimental results on several benchmarks show that our speculative scheduling algorithm can result in significant (upto seven-fold) improvements in performance (measured in terms of the average number of clock cycles) as compared to scheduling without speculative execution. Also, the best and worst case execution times for the speculatively performed schedules are the same as or better than the corresponding values for the schedules obtained without speculative execution.
AB - Speculative execution refers to the execution of parts of a computation before the execution of the conditional operations that decide whether they need to be executed. It has been shown to be a promising technique for eliminating performance bottlenecks imposed by control flow in hardware and software implementations alike. In this paper, we present techniques to incorporate speculative execution in a fine-grained manner into scheduling of control-flow-intensitive behavioral descriptions. We demonstrate that failing to take into account information such as resource constraints and branch probabilities can lead to significantly suboptimal performance. We also demonstrate that it may be necessary to speculate simultaneously along multiple paths, subject to resource constraints, in order to minimize the delay overheads incurred when prediction errors occur. Experimental results on several benchmarks show that our speculative scheduling algorithm can result in significant (upto seven-fold) improvements in performance (measured in terms of the average number of clock cycles) as compared to scheduling without speculative execution. Also, the best and worst case execution times for the speculatively performed schedules are the same as or better than the corresponding values for the schedules obtained without speculative execution.
UR - http://www.scopus.com/inward/record.url?scp=0034157132&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0034157132&partnerID=8YFLogxK
U2 - https://doi.org/10.1109/43.833200
DO - https://doi.org/10.1109/43.833200
M3 - Article
SN - 0278-0070
VL - 19
SP - 308
EP - 324
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 3
ER -