Enhancing instruction-level parallelism through compiler-controlled speculation
Bringmann, Roger Alexander
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/21595
Description
Title
Enhancing instruction-level parallelism through compiler-controlled speculation
Author(s)
Bringmann, Roger Alexander
Issue Date
1995
Doctoral Committee Chair(s)
Hwu, Wen-Mei W.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
Abstract
The available instruction level parallelism (ILP) is extremely limited within basic blocks of non-numeric programs (1) (2) (3). An effective VLIW or superscalar processor must optimize and schedule instructions across basic block boundaries to achieve higher performance. An effective structure for ILP compilation is the superblock (4). The formation and optimization of superblocks increase ILP available to the scheduler along important execution paths by systematically removing constraints due to the unimportant paths. Superblock scheduling is then applied to extract the available ILP and map it to the processor resources.
The major technique employed to achieve compact superblock schedules is speculative execution. Speculative execution refers to executing an instruction before knowing that its execution is required. Such an instruction will be referred to as a speculative instruction. In the general sense, speculative execution may be engineered at run-time using dynamic scheduling or at compile-time. Superblock techniques utilize compile-time engineered speculative execution, or speculative code motion. A compiler may utilize speculative code motion to achieve higher performance in three major ways. First, in regions of the program where insufficient ILP exists to fully utilize the processor resources, useful instructions may be executed. Second, instructions starting long dependence chains may be executed early to reduce the length of critical paths. Finally, long latency instructions may be initiated early to overlap their execution with useful computation. Speculative execution is generally employed by all aggressive scheduling techniques. For example, Tirumalai et al. showed that modulo scheduling of while loops depends on speculative support to achieve high performance (5). Without speculative support, very little execution overlap between loop iterations is achieved.
This dissertation discusses the problems that must be addressed to perform compile-time speculation for acyclic global scheduling, classifies existing speculation models based upon how they solve these problems and discusses two new compile-time or compiler-controlled speculation models--write-back suppression speculation and safe speculation.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
