Incorporating speculative execution into scheduling of control-flow intensive behavioral descriptions

Ganesh Lakshminarayana, Anand Raghunathan, Niraj K. Jha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

Speculative execution refers to the execution of parts of a computation before the execution of the conditional operations that decide whether it needs 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-how intensive behavioral descriptions. We demonstrate that failing to take into account information such as resource constraints and branch probabilities can lead to significantly sub-optimal 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 (up to 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.

Original languageEnglish (US)
Title of host publicationProceedings 1998 - Design and Automation Conference, DAC 1998
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages108-113
Number of pages6
ISBN (Print)078034409X
DOIs
StatePublished - Jan 1 1998
Event35th Design and Automation Conference, DAC 1998 - San Francisco, United States
Duration: Jun 15 1998Jun 19 1998

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Other

Other35th Design and Automation Conference, DAC 1998
CountryUnited States
CitySan Francisco
Period6/15/986/19/98

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modeling and Simulation
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Incorporating speculative execution into scheduling of control-flow intensive behavioral descriptions'. Together they form a unique fingerprint.

  • Cite this

    Lakshminarayana, G., Raghunathan, A., & Jha, N. K. (1998). Incorporating speculative execution into scheduling of control-flow intensive behavioral descriptions. In Proceedings 1998 - Design and Automation Conference, DAC 1998 (pp. 108-113). [724449] (Proceedings - Design Automation Conference). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1145/277044.277067