Return-address prediction in speculative multithreaded environments

Mohamed Zahran, Manoj Franklin

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

Abstract

There is a growing interest in the use of speculative multithreading to speed up the execution of sequential programs. In this execution model, threads are extracted from sequential code and are speculatively executed in parallel. This makes it possible to use parallel processing to speed up ordinary applications, which are typically written as sequential programs. This paper has two objectives. The first is to highlight the problems involved in performing accurate return address predictions in speculative multithreaded processors, where many of the subroutine call instructions and return instructions are fetched out of program order. A straightforward application of a return address stack popular scheme for predicting return addresses in single-threaded environments does not work well in such a situation. With out-of-order fetching of call instructions as well as return instructions, pushing and popping of return addresses onto and from the return address stack happen in a somewhat random fashion. This phenomena corrupts the return address stack, resulting in poor prediction accuracy for return addresses. The second objective of the paper is to propose a fixup technique for using the return address stack in speculative multithreaded processors. Our technique involves the use of a distributed return address stack, with facilities for repair when out-of-order pushes and pops happen. Detailed simulation results of the proposed schemes show significant improvements in the predictability of return addresses in a speculative multithreaded environment.

Original languageEnglish (US)
Title of host publicationHigh Performance Computing - HiPC 2002 - 9th International Conference, Proceedings
EditorsSartaj Sahni, Viktor K. Prasanna, Uday Shukla
PublisherSpringer Verlag
Pages609-619
Number of pages11
ISBN (Print)3540003037, 9783540003038
DOIs
StatePublished - 2002
Event9th International Conference on High Performance Computing, HiPC 2002 - Bangalore, India
Duration: Dec 18 2002Dec 21 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2552
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Conference on High Performance Computing, HiPC 2002
CountryIndia
CityBangalore
Period12/18/0212/21/02

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Return-address prediction in speculative multithreaded environments'. Together they form a unique fingerprint.

  • Cite this

    Zahran, M., & Franklin, M. (2002). Return-address prediction in speculative multithreaded environments. In S. Sahni, V. K. Prasanna, & U. Shukla (Eds.), High Performance Computing - HiPC 2002 - 9th International Conference, Proceedings (pp. 609-619). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2552). Springer Verlag. https://doi.org/10.1007/3-540-36265-7_57