DOC PREVIEW
Berkeley COMPSCI 252 - Modeling Program Predictability

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Modeling Program Predictability Yiannakis Sazeides and James E. Smith Department of Electrical and Computer Engineering University of Wisconsin-Madison 14 15 Engr. Dr. Madison, WI 53706 [email protected], [email protected] Abstract Basic properties of program predictability -for both val- ues and control - are dejned and studied. We take the view that program predictability originates at certain points during a program’s execution,Jlows through subsequent in- structions, and then ends at other points in the program. These key components of predictability: generation, prop- agation, and termination; are defined in terms of a model. The model is based on a graph derived from dynamic data dependences and a predictor Using the SPEC95 benchmarks, we analyze the pre- dictability phenomena both separately and in combination. Examples are provided to illustrate relationships between model-based characteristics and program constructs. It is shown that most predictability derives from program control structure and immediate values, not program input data. Furthermore, most predictability originates from a rela- tively small number of generate points. The analysis of ob- tained results suggests a number of ramifications regarding predictability and its use. 1 Introduction The need for higher levels of instruction level paral- lelism is pushing high performance processor implementa- tions toward widespread use of prediction and speculation. Ultimately this could lead to substantially new processing paradigms. However, it may be premature to start reaching for radically new paradigms at this point - first some ba- sic research and understanding of program predictability is required. Data, addresses, and control interact in complex ways, and these interactions should be understood before prediction can be fully exploited for increased performance. We propose a model for studying program predictability. This model, or related models, should prove useful for: Understanding the underlying phenomena that lead to predictability. Finding relationships among computations that may point to more accurate and more efficient predictors. Identifying critical points for prediction; i.e. places where prediction and speculation may have greater payoff. Eventually identifying new microarchitecture paradigms based on prediction rather than using it as just an add-on. We do not achieve all these goals in this paper - we only take a first step. We concentrate primarily on model devel- opment and study the first of the above items in some depth. However, we include discussion suggesting possible direc- tions for pursuing the others. Data value prediction is the primary focus, but we also include control prediction be- cause the interactions between data and control are key for effective prediction and speculation. Further extensions to address and dependence prediction are clearly possible, but we do not pursue them here. 1.1 The Dynamics of Program Predictability Because predictability is based on program behavior, we informally introduce some of the key concepts using a code example. Then, we make some general observations about program behavior that will provide a basis for understand- ing predictability phenomena. Fig. 1 shows a frequently executed code sequence taken from the invalidatefor-call function in the SPECINT95 benchmark 126.gcc. The code sequence tests bits in a mask that correspond to 64 machine registers; consequently, it is a loop that executes 64 iterations. Beside each instruction is a regular expression that describes the sequence of values produced by the instruction each time the function is called. 1063-6897198 $10.00 0 1998 IEEE 730 LLl: 1 2 3 4 5 6 8 LL2: 9 10 11 OpCode Operands Values Produced add $6,$0,$0 0 srl $2,$6,5 (o)32(1)32 sll $2,$2,2 (o)32(4)32 addu $2,$2,$19 (Ox1002f8b0)32 (Ox1002f8b4)32 IW !fxw (Ox8000bfff)32(0xfffffffQ32 andi $3,$6,31 (41, . . ,31)2 SflV $2,$2,$3 ~0,~1,..,~62,~31 andi $2,$2,1 (1)‘4(o)‘(1)1(o)‘5(1)33 beq $2,O,LL2 (NT)‘4(T)‘(NT)‘(T)15(NT)33 addiu $6,$6,1 1,2, . . ,64 slti $2,$6,64 w3 (0)’ bne $2,O,LL 1 (T)63 (NT)* Figure 1. Example Code from 126.gcc For instruction 6 the vi correspond to values not essential to the example. Note that the use of regular expressions is for illustrative purposes, program sequences do not necessar- ily have to be regular expressions - at least not compactly represented ones. In the example, register $6 is initialized by adding the value 0 to itself outside the loop ($0 = 0, by definition in the instruction set we are using). Each time through the loop, the value in register $6 is incremented by one from instruc- tion 9. This means that the values in register $6 form the sequence 0,1,2,3,...64. This sequence would be predictable by a stride predictor - i.e. the values in the sequence dif- fer by a constant. After the second value in the sequence, a typical stride predictor would recognize the stride and start making correct predictions. Hence, assuming stride predic- tion, predictability has been generated at that point. And this predictability is propagated by each of the successive executions of instruction 9. Instruction 1 also uses the values in register $6. It shifts each of these by an immediate 5. The resulting sequence of 32 zeros and 32 ones is also largely predictable by a stride predictor (where the stride is 0). Hence, the predictability generated by the stride one sequence at the input of the shift (instruction 1) is propagated through to the output of the instruction. After 32 zero values, however, the output of in- struction 1 will change to one. At that point the predictabil- ity terminates, but is almost immediately re-generated when the sequence of ones is detected by the predictor. Going on, instruction 2 shifts the result of instruction 1 by an imme- diate 2. Hence, the outputs of instruction 2 are also pre- dictable - the predictability generated by instruction 9 prop- agates still further. And predictability continues to propa- gate through instructions 3 and 4,


View Full Document

Berkeley COMPSCI 252 - Modeling Program Predictability

Documents in this Course
Quiz

Quiz

9 pages

Caches I

Caches I

46 pages

Lecture 6

Lecture 6

36 pages

Lecture 9

Lecture 9

52 pages

Figures

Figures

26 pages

Midterm

Midterm

15 pages

Midterm

Midterm

14 pages

Midterm I

Midterm I

15 pages

ECHO

ECHO

25 pages

Quiz  1

Quiz 1

12 pages

Load more
Download Modeling Program Predictability
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Modeling Program Predictability and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Modeling Program Predictability 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?