The predictability of data values.
The predictability of data values is studied at a fundamental level. Two basic predictor models are defined: Computational predictors perform an operation on previous values to yield predicted next values. Examples we study are stride value prediction (which adds a delta to a previous value) and last value prediction (which performs the trivial identity operation on the previous value); Context Based} predictors match recent value history (context) with previous value history and predict values based entirely on previously observed patterns. To understand the potential of value prediction we perform simulations with unbounded prediction tables that are immediately updated using correct data values. Simulations of integer SPEC95 benchmarks show that data values can be highly predictable. Best performance is obtained with context based predictors; overall prediction accuracies are between 56% and 91%. The context based predictor typically has an accuracy about 20% better than the computational predictors (last value and stride). Comparison of context based prediction and stride prediction shows that the higher accuracy of context based prediction is due to relatively few static instructions giving large improvements; this suggests the usefulness of hybrid predictors. Among different instruction types, predictability varies significantly. In general, load and shift instructions are more difficult to predict correctly, whereas add instructions are more predictable.
Introduction
There is a clear trend in high performance processors toward
performing operations speculatively, based on predic-
tions. If predictions are correct, the speculatively executed
instructions usually translate into improved performance.
Although program execution contains a variety of information
that can be predicted, conditional branches have received
the most attention. Predicting conditional branches
provides a way of avoiding control dependences and offers
a clear performance advantage. Even more prevalent
than control dependences, however, are data dependences.
Virtually every instruction depends on the result of some
preceding instruction. As such, data dependences are often
thought to present a fundamental performance barrier.
However, data values may also be predicted, and operations
can be performed speculatively based on these data
predictions.
An important difference between conditional branch
prediction and data value prediction is that data are taken
from a much larger range of values. This would appear to
severely limit the chances of successful prediction. How-
ever, it has been demonstrated recently [1] that data values
exhibit "locality" where values computed by some instructions
tend to repeat a large fraction of the time.
We argue that establishing predictability limits for program
values is important for determining the performance
potential of processors that use value prediction. We believe
that doing so first requires understanding the design
space of value predictors models. Consequently, the goals
of this paper are twofold. Firstly, we discuss some of the
major issues affecting data value prediction and lay down
a framework for studying data value prediction. Secondly,
for important classes of predictors, we use benchmark programs
to establish levels of value predictability. This study
is somewhat idealized: for example, predictor costs are ignored
in order to more clearly understand limits of data
predictability. Furthermore, the ways in which data prediction
can be used in a processor microarchitecture are not
within the scope of this paper, so that we can concentrate
in greater depth on the prediction process, itself.
1.1 Classification of Value Sequences
The predictability of a sequence of values is a function
of both the sequence itself and the predictor used to predict
the sequence. Although it is beyond the scope of this paper
to study the actual sources of predictability, it is useful for
our discussion to provide an informal classification of data
sequences. This classification is useful for understanding
the behavior of predictors in later discussions. The following
classification contains simple value sequences that can
also be composed to form more complex sequences. They
are best defined by giving examples:
28 -13 -99 107 23 456.
Constant sequences are the simplest, and result from
instructions that repeatedly produce the same result. Lipasti
and Shen show that this occurs surprisingly often, and
forms the basis for their work reported in [1]. A stride sequence
has elements that differ by some constant delta. For
the example above, the stride is one, which is probably the
most common case in programs, but other strides are pos-
sible, including negative strides. Constant sequences can
be considered stride sequences with a zero delta. A stride
sequence might appear when a data structure such as an array
is being accessed in a regular fashion; loop induction
variables also have a stride characteristic.
The non-stride category is intended to include all other
sequences that do not belong to the constant or stride cat-
egory. This classification could be further divided, but we
choose not to do so. Non-strides may occur when a sequence
of numbers is being computed and the computation
is more complex than simply adding a constant. Traversing
a linked list would often produce address values that have
a non-stride pattern.
Also very important are sequences formed by composing
stride and non-stride sequences with themselves. Repeating
sequences would typically occur in nested loops
where the inner loop produces either a stride or a non-stride
sequence, and the outer loop causes this sequence to be repeated

Repeated
Repeated 7.
Examination of the above sequences leads naturally to
two types of prediction models that are the subject of discussion
throughout the remainder of this paper:
Computational predictors that make a prediction by computing
some function of previous values. An example of a
computational predictor is a stride predictor. This predictor
adds a stride to the previous value.
Context based predictors learn the value(s) that follow a
particular context - a finite ordered sequence of values - and
predict one of the values when the same context repeats.
This enables the prediction of any repeated sequence, stride
or non-stride.
1.2 Related Work
In [1], it was reported that data values produced by
instructions exhibit "locality" and as a result can be pre-
dicted. The potential for value predictability was reported
in terms of "history depth", that is, how many times a value
produced by an instruction repeats when checked against
the most recent n values. A pronounced difference is observed
between the locality with history depth 1 and history
depth 16. The mechanism proposed for prediction, how-
ever, exploits the locality of history depth 1 and is based on
predicting that the most recent value will also be the next.
In [1], last value prediction was used to predict load values
and in a subsequent work to predict all values produced by
instructions and written to registers [2].
Address prediction has been used mainly for data
prefetching to tolerate long memory latency [3, 4, 5], and
has been proposed for speculative execution of load and
store instructions [6, 7]. Stride prediction for values was
proposed in [8] and its prediction and performance potential
was compared against last value prediction.
Value prediction can draw from a wealth of work on
the prediction of control dependences [9, 10, 11]. The majority
of improvements in the performance of control flow
predictors has been obtained by using correlation. The correlation
information that has been proposed includes local
and global branch history [10], path address history
[11, 12, 13], and path register contents [14]. An interesting
theoretical observation is the resemblance of the predictors
used for control dependence prediction to the prediction
models for text compression [15]. This is an important observation
because it re-enforces the approach used for control
flow prediction and also suggests that compression-like
methods can also be used for data value prediction.
A number of interesting studies report on the importance
of predicting and eliminating data dependences.
Moshovos [16] proposes mechanisms that reduce misspeculation
by predicting when dependences exist between
store and load instructions. The potential of data dependence
elimination using prediction and speculation in combination
with collapsing was examined in [17]. Elimination
of redundant computation is the theme of a number of
software/hardware proposals [18, 19, 20]. These schemes
are similar in that they store in a cache the input and output
parameters of a function and when the same inputs are detected
the output is used without performing the function.
Virtually all proposed schemes perform predictions based
on previous architected state and values. Notable exceptions
to this are the schemes proposed in [6], where it is
predicted that a fetched load instruction has no dependence
and the instruction is executed "early" without dependence
checking, and in [21], where it is predicted that the operation
required to calculate an effective address using two
operands is a logical or instead of a binary addition.
In more theoretical work, Hammerstrom [22] used information
theory to study the information content (en-
tropy) of programs. His study of the information content of
address and instruction streams revealed a high degree of
redundancy. This high degree of redundancy immediately
suggests predictability.
1.3 Paper

Overview

The paper is organized as follows: in Section 2, different
data value predictors are described. Section 3 discusses
the methodology used for data prediction simulations. The
results obtained are presented and analyzed in Section 4.
We conclude with suggestions for future research in Section
5.
2 Data Value Prediction Models
A typical data value predictor takes microarchitecture
state information as input, accesses a table, and produces
a prediction. Subsequently, the table is updated with state
information to help make future predictions. The state information
could consist of register values, PC values, instruction
fields, control bits in various pipeline stages, etc.
The variety and combinations of state information are
almost limitless. Therefore, in this study, we restrict ourselves
to predictors that use only the program counter value
of the instruction being predicted to access the prediction
table(s). The tables are updated using data values produced
by the instruction - possibly modified or combined with
other information already in the table. These restrictions
define a relatively fundamental class of data value predic-
tors. Nevertheless, predictors using other state information
deserve study and could provide a higher level of predictability
than is reported here.
For the remainder of this paper, we further classify
data value predictors into two types - computational and
context-based. We describe each in detail in the next two
subsections.
2.1 Computational Predictors
Computational predictors make predictions by performing
some operation on previous values that an instruction
has generated. We focus on two important members of this
class.
Last Value Predictors perform a trivial computational
operation: the identity function. In its simplest form, if the
most recent value produced by an instruction is v then the
prediction for the next value will also be v. However, there
are a number of variants that modify replacement policies
based on hysteresis. An example of a hysteresis mechanism
is a saturating counter that is associated with each
table entry. The counter is incremented/decremented on
prediction success/failure with the value held in the table
replaced only when the count is below some threshold. Another
hysteresis mechanism does not change its prediction
to a new value until the new value occurs a specific number
of times in succession. A subtle difference between the
two forms of hysteresis is that the former changes to a new
prediction following incorrect behavior (even though that
behavior may be inconsistent), whereas the latter changes
to a new prediction only after it has been consistently observed

Stride Predictors in their simplest form predict the next
value by adding the sum of the most recent value to the
difference of the two most recent values produced by an
instruction. That is if vn\Gamma1 and vn\Gamma2 are the two most
recent values, then the predictor computes
As with the last value predictors, there are important
variations that use hysteresis. In [7] the stride
is only changed if a saturating counter that is incre-
mented/decremented on success/failure of the predictions
is below a certain threshold. This reduces the number of
mispredictions in repeated stride sequences from two per
repeated sequence to one. Another policy, the two-delta
method, was proposed in [6]. In the two-delta method, two
strides are maintained. The one stride (s1) is always up-dated
by the difference between the two most recent val-
ues, whereas the other (s2) is the stride used for computing
the predictions. When stride s1 occurs twice in a row then
it is used to update the prediction stride s2. The two-delta
strategy also reduces mispredictions to one per iteration for
repeated stride sequences and, in addition, only changes
the stride when the same stride occurs twice - instead of
changing the stride following mispredictions.
Other Computational Predictors using more complex
organizations can be conceived. For example, one could
use two different strides, an "inner" one and an "outer"
one - typically corresponding to loop nests - to eliminate
the mispredictions that occur at the beginning of repeating
stride sequences. This thought process illustrates a significant
limitation of computational prediction: the designer
must anticipate the computation to be used. One could
carry this to ridiculous extremes. For example, one could
envision a Fibonacci series predictor, and given a program
that happens to compute a Fibonacci series, the predictor
would do very well.
Going down this path would lead to large hybrid predictors
that combine many special-case computational predictors
with a "chooser" - as has been proposed for conditional
branches in [23, 24]. While hybrid prediction for data values
is in general a good idea, a potential pitfall is that it
may yield an ever-escalating collection of computational
predictors, each of which predicts a diminishing number
of additional values not caught by the others.
In this study, we focus on last value and stride methods
as primary examples of computational predictors. We
also consider hybrid predictors involving these predictors
and the context based predictors to be discussed in the next
section.
2.2 Context Based Predictors
Context based predictors attempt to "learn" values that
follow a particular context - a finite ordered sequence of
previous values - and predict one of the values when the
same context repeats. An important type of context based
predictors is derived from finite context methods used in
text compression [25].
Finite Context Method Predictors (fcm) rely on
mechanisms that predict the next value based on a finite
number of preceding values. An order k fcm predictor
uses k preceding values. Fcms are constructed with counters
that count the occurrences of a particular value immediately
following a certain context (pattern). Thus for
each context there must be, in general, as many counters
as values that are found to follow the context. The predicted
value is the one with the maximum count. Figure 1
shows fcm models of different orders and predictions for
an example sequence.
In an actual implementation where it may be infeasible
to maintain exact value counts, smaller counters may be
used. The use of small counters comes from the area of
text compression. With small counters, when one counter
reaches the maximum count, all counters for the same context
are reset by half. Small counters provide an advantage
if heavier weighting should be given to more recent history
instead of the entire history.
In general, n different fcm predictors of orders 0 to n-
1 can be used for predicting the next value of a sequence,
with the highest order predictor that has a context match
being used to make the prediction. The combination of
more than one prediction model is known as blending [25].
There are a number of variations of blending algorithms,
depending on the information that is updated. Full blending
updates all contexts, and lazy exclusion selects the prediction
with the longer context match and only updates the
counts for the predictions with the longer match or higher.
Other variations of fcm predictors can be devised by
reducing the number of values that are maintained for a
given context. For example, only one value per context
might be maintained along with some update policy. Such
policies can be based on hysteresis-type update policies as
discussed above for last value and stride prediction.
Correlation predictors used for control dependence prediction
strongly resemble context based prediction. As far
as we know, context based prediction has not been considered
for value prediction, though the last value predictor
can be viewed as a 0th order fcm with only one prediction
maintained per context.
2.3 An Initial Analysis
At this point, we briefly analyze and compare the proposed
predictors using the simple pattern sequences shown
in Section 1.1. This analysis highlights important issues as
a
ca b c
a a
a b
a c
b a
c a
c ca b c
a b c0 0
a a a
a a b
a b c
b c ac a a
0th order Model
a b c
Context
Next Symbol
FrequencySequence:a a a b c a a a b c a a a ?
1st order Model 2nd order Model 3rd order Model
Prediction: a
Prediction: a
Prediction: a

Figure

1: Finite Context Models
well as advantages and disadvantages of the predictors to
be studied. As such, they can provide a basis for analyzing
quantitative results given in the following sections.
We informally define two characteristics that are important
for understanding prediction behavior. One is the
Learning Time (LT) which is the number of values that
have to be observed before the first correct prediction. The
second is the Learning Degree (LD) which is the percentage
of correct predictions following the first correct prediction

We quantify these two characteristics for the classes of
sequences given earlier in Section 1.1. For the repeating
sequences, we associate a period (p), the number of values
between repetitions, and frequency, the number of times
a sequence is repeated. We assume repeating sequences
where p is fixed. The frequency measure captures the
finiteness of a repeating sequence. For context predictors,
the order (o) of a predictor influences the learning time.

Table

summarizes how the different predictors perform
for the basic value sequences. Note that the stride
predictor uses hysteresis for updates, so it gets only one incorrect
prediction per iteration through a sequence. A row
of the table with a "-" indicates that the given predictor is
not suitable for the given sequence, i.e., its performance is
very low for that sequence.
As illustrated in the table, last value prediction is only
useful for constant sequences - this is obvious. Stride prediction
does as well as last value prediction for constant
sequences because a constant sequence is essentially zero
stride. The fcm predictors also do very well on constant
sequences, but an order predictor must see a length
sequence before it gets matches in the table (unless some
form of blending is used).
For (non-repeating) stride sequences, only the stride
Prediction Model
Sequence Last Value Stride FCM

Table

1: Behavior of various Prediction Models for Different
Value Sequences
predictor does well; it has a very short learning time and
then achieves a 100% prediction rate. The fcm predictors
cannot predict non-repeating sequences because they rely
on repeating patterns.
For repeating stride sequences, both stride and fcm predictors
do well. The stride predictor has a shorter learning
time, and once it learns, it only gets a misprediction each
time the sequence begins to repeat. On the other hand,
the fcm predictor requires a longer learning time - it must
see the entire sequence before it starts to predict correctly
but once the sequence starts to repeat, it gets 100% accuracy
(Figure 2). This example points out an important
tradeoff between computational and context based predic-
tors. The computational predictor often learns faster - but
the context predictor tends to learn "better" when repeating
sequences occur.
Finally, for repeating non-stride sequences, only the
fcm predictor does well. And the flexibility this provides
is clearly the strong point of fcm predictors. Returning to
our Fibonacci series example - if there is a sequence containing
a repeating portion of the Fibonacci series, then an
fcm predictor will naturally begin predicting it correctly
following the first pass through the sequence.
Of course, in reality, value sequences can be complex
combinations of the simple sequences in Section 1.1, and
a given program can produce about as many different sequences
as instructions are being predicted. Consequently,
in the remainder of the paper, we use simulations to get a
more realistic idea of predictor performance for programs.
3 Simulation Methodology
We adopt an implementation-independent approach for
studying predictability of data dependence values. The reason
for this choice is to remove microarchitecture and other
implementation idiosyncrasies in an effort to develop a basic
understanding of predictability. Hence, these results
can best be viewed as bounds on performance; it will take
additional engineering research to develop realistic implementations

Steady State
Repeats Same Mistake
Repeated
Steady State
Misspredictions
period
Learn
Prediction
CONTEXT BASED

Figure

2: Computational vs Context Based Prediction
We study the predictability of instructions that write results
into general purpose registers (i.e. memory addresses,
stores, jumps and branches are not considered). Prediction
was done with no table aliasing; each static instruction was
given its own table entry. Hence, table sizes are effectively
unbounded. Finally, prediction tables are updated immediately
after a prediction is made, unlike the situation in
practice where it may take many cycles for the actual data
value to be known and available for prediction table updates

We simulate three types of predictors: last value prediction
(l) with an always-update policy (no hysteresis),
stride prediction using the 2-delta method (s2), and a finite
context method (fcm) that maintains exact counts for
each value that follows a particular context and uses the
blending algorithm with lazy exclusion, described in Section
2. Fcm predictors are studied for orders 1, 2 and 3. To
form a context for the fcm predictor we use full concatenation
of history values so there is no aliasing when matching
contexts.
Trace driven simulation was conducted using the Simplescalar
toolset [26] for the integer SPEC95 benchmarks
shown in Table 2 1 . The benchmarks were compiled using
the simplescalar compiler with -O3 optimization. Integer
benchmarks were selected because they tend to have less
data parallelism and may therefore benefit more from data
predictions.
For collecting prediction results, instruction types were
grouped into categories as shown in Table 3. The ab-
1 For ijpeg the simulations used the reference flags with the following
changes: compression.quality 45 and compression.smoothing factor 45.
Benchmark Input Dynamic Instructions
Flags Instr. (mil) Predicted (mil)
compress 30000 e 8.2 5.8 (71%)
gcc gcc.i 203 137 (68%)
ijpeg specmun.ppm 129 108 (84%)
m88k ctl.raw 493 345 (70%)
xlisp 7 queens 202 125 (62%)

Table

2: Benchmarks Characteristics
Instruction Types Code
Addition, Subtraction AddSub
Loads Loads
And, Or, Xor, Nor Logic
Shifts Shift
Compare and Set Set
Multiply and Divide MultDiv
Load immediate Lui
Floating, Jump, Other Other

Table

3: Instruction Categories
breviations shown after each group will be used subsequently
when results are presented. The percentage of predicted
instructions in the different benchmarks ranged between
62%-84%. Recall that some instructions like stores,
branches and jumps are not predicted. A breakdown of the
static count and dynamic percentages of predicted instruction
types is shown in Tables 4-5. The majority of predicted
values are the results of addition and load instructions.
We collected results for each instruction type. However,
we do not discuss results for the other, multdiv and lui instruction
types due to space limitations. In the benchmarks
we studied, the multdiv instructions are not a significant
contributor to dynamic instruction count, and the lui and
"other" instructions rarely generate more than one unique
value and are over 95% predictable by all predictors. We
note that the effect of these three types of instructions is
included in the calculations for the overall results.
For averaging we used arithmetic mean, so each benchmark
effectively contributes the same number of total predictions

4 Simulation Results
4.1 Predictability

Figure

3 shows the overall predictability for the selected
benchmarks, and Figures 4-7 show results for the important
instruction types. From the figures we can draw a number
Type com gcc go ijpe m88k perl xlis
Loads 686 29138 9929 3645 2215 3855 1432
Logic 149 2600 215 278 674 460 157
MultDi 19 313 196 222 77 26 25
Other 108 5848 1403 517 482 778 455

Table

4: Predicted Instructions - Static Count
Type com gcc go ijpe m88k perl xlis
Loads 20.5 38.6 26.2 21.4 24.8 43.1 48.6
Logic 3.1 3.1 0.5 1.9 5.0 3.1 3.4
Shift 17.4 7.7 13.3 16.4 3.2 8.2 3.2
Set 7.4 5.4 4.9 4.2 15.2 5.6 3.2
Lui 3.3 3.7 11.4 0.2 6.9 2.4 0.8
Other 5.7 2.1 1.3 0.3 2.1 3.3 4.8

Table

5: Predicted Instructions - Dynamic(%)
of conclusions. Overall, last value prediction is less accurate
than stride prediction, and stride prediction is less
accurate than fcm prediction. Last value prediction varies
in accuracy from about 23% to 61% with an average of
about 40%. This is in agreement with the results obtained
in [2]. Stride prediction provides accuracy of between 38%
and 80% with an average of about 56%. Fcm predictors of
orders 1, 2, and 3 all perform better than stride prediction;
and the higher the order, the higher the accuracy. The order
3 predictor is best and gives accuracies of between 56%
and over 90% with an average of 78%. For the three fcm
predictors studied, improvements diminish as the order is
increased. In particular, we observe that for every additional
value in the context the performance gain is halved.
The effect on predictability with increasing order is examined
in more detail in Section 4.4. Performance of the
stride and last value predictors varies significantly across
different instruction types for the same benchmark. The
performance of the fcm predictors varies less significantly
across different instruction types for the same benchmark.
This reflects the flexibility of the fcm predictors - they perform
well for any repeating sequence, not just strides.
In general both stride and fcm prediction appear to have
higher predictability for add/subtracts than loads. Logical
instructions also appear to be very predictable especially
by the fcm predictors. Shift instructions appear to be the
most difficult to predict.
Stride prediction does particularly well for add/subtract
compress cc1 go ijpeg m88k perl xlisp
%of
Predictions

Figure

3: Prediction Success for All Instructions
instructions. But for non-add/subtract instructions the performance
of the stride predictor is close to last value pre-
diction. This indicates that when the operation of a computational
predictor matches the operation of the instruction
(e.g. addition), higher predictability can be expected. This
suggests new computational predictors that better capture
the functionality of non-add/subtract instructions could be
useful. For example, for shifts a computational predictor
might shift the last value according to the last shift distance
to arrive at a prediction. This approach would tend to lead
to hybrid predictors, however, with a separate component
predictor for each instruction type.
4.2 Correlation of Correctly Predicted Sets
In effect, the results in the previous section essentially
compare the sizes of the sets of correctly predicted values.
It is also interesting to consider relationships among the
specific sets of correctly predicted values. Primarily, these
relationships suggest ways that hybrid predictors might be
constructed - although the actual construction of hybrid
predictors is beyond the scope of this paper.
The predicted set relationships are shown in Figure 8.
Three predictors are used: last value, stride (delta-2), and
fcm (order 3). All subsets of predictors are represented.
Specifically: l is the fraction of predictions for which only
the last value predictor is correct; s and f are similarly defined
for the stride and fcm predictors respectively; ls is the
fraction of predictions for which both the last value and the
stride predictors are correct but the fcm predictor is not; lf
and sf are similarly defined; lsf is the fraction of predictions
for which all predictors are correct; and np is the fraction
for which none of the predictors is correct.
In the figure results are averaged over all benchmarks,
but the qualitative conclusions are similar for each of the1030507090compress cc1 go ijpeg m88k perl xlisp
%of
Predictions

Figure

4: Prediction Success for Add/Subtract Instructions1030507090compress cc1 go ijpeg m88k perl xlisp
%of
Predictions

Figure

5: Prediction Success for Loads Instructions1030507090compress cc1 go ijpeg m88k perl xlisp
%of
Predictions
(Logic)

Figure

Prediction Success for Logic Instructions1030507090compress cc1 go ijpeg m88k perl xlisp
%of
Predictions

Figure

7: Prediction Success for Shift Instructions
All AddSu Loads Logic Shift Set
Predictions
s
ls
lf
sf
lsf

Figure

8: Contribution of different Predictors
individual benchmarks. Overall, Figure 8 can be briefly
summarized:
small number, close to 18%, of values are not predicted
correctly by any model.
ffl A large portion, around 40%, of correct predictions is
captured by all predictors.
ffl A significant fraction, over 20%, of correct predictions
is only captured by fcm.
ffl Stride and last value prediction capture less than 5%
of the correct predictions that fcm misses.
The above confirms that data values are very pre-
dictable. And it appears that context based prediction is
necessary for achieving the highest levels of predictabil-
ity. However, almost 60% of the correct predictions are
also captured by the stride predictor. Assuming that context
based prediction is the more expensive approach, this
suggest that a hybrid scheme might be useful for enabling
high prediction accuracies at lower cost. That is, one
should try to use a stride predictor for most predictions,
and use fcm prediction to get the remaining 20%.
Another conclusion is that last value prediction adds
very little to what the other predictors achieve. So, if either
stride or fcm prediction is implemented, there is no
point in adding last value prediction to a hybrid predictor.
The important classes of load and add instructions yield
results similar to the overall average. Finally, we note that
for non-add/subtract instructions the contribution of stride
prediction is smaller, this is likely due to the earlier observation
that stride prediction does not match the func-20406080100
% of Static Instructions that FCM does better than Stride
Normalized
AddSub
Loads
Logic

Figure

9: Cumulative Improvement of FCM over Stride
tionality of other instruction types. This suggests a hybrid
predictor based on instruction types.
Proceeding along the path of a hybrid fcm-stride pre-
dictor, one reasonable approach would be to choose among
the two component predictors via the PC address of the instruction
being predicted. This would appear to work well
if the performance advantage of the fcm predictor is due to
a relatively small number of static instructions.
To determine if this is true, we first constructed a list
of static instructions for which the fcm predictor gives better
performance. For each of these static instructions, we
determined the difference in prediction accuracy between
fcm and stride. We then sorted the static instructions in
descending order of improvement. Then, in Figure 9 we
graph the cumulative fraction of the total improvement versus
the accumulated percentage of static instructions. The
graph shows that overall, about 20% of the static instructions
account for about 97% of the total improvement of
fcm over stride prediction. For most of individual instruction
types, the result is similar, with shifts showing slightly
worse performance.
The results do suggest that improvements due to context
based prediction are mainly due to a relatively small
fraction of static instructions. Hence, a hybrid fcm-stride
predictor with choosing seems to be a good approach.
4.3 Value Characteristics
At this point, it is clear that context based predictors
perform well, but may require large tables that store history
values. We assume unbounded tables in our study,
but when real implementations are considered, of course
this will not be possible. To get a handle on this issue, we
study the value characteristics of instructions. In particu-
Predicted
Instructions >65536163841024644
Figure

10: Values and Instruction Behavior
lar we report on the number of unique values generated
by predicted instructions. The overall numbers of different
values could give a rough indication of the numbers of
values that might have to be stored in a table.
In the left half of Figure 10, we show the number different
values produced by percentages of static instructions
(an s prefix). In the right half, we determine the fractions
of dynamic instructions (a d prefix) that correspond to each
of the static categories. From the figure, we observe:
ffl A large number, 50%, of static instructions generate
only one value.
ffl The majority of static instructions, 90%, generate
fewer than 64 values.
ffl The majority, 50%, of dynamic instructions correspond
to static instructions that generate fewer than
values.
ffl Over 90% of the dynamic instructions are due to static
instructions that generate at most 4096 unique values.
ffl The number of values generated varies among instruction
types. In general add/subtract and load instructions
generate more values as compared with logic
and shift operations.
ffl The more frequently an instruction executes the more
values it generates.
The above suggest that a relatively small number of values
would be required to predict correctly the majority of
dynamic instructions using context based prediction - a
positive result.
From looking at individual benchmark results (not
shown) there appears to be a positive correlation between
programs that are more difficult to predict and the programs
that produce more values. For example, the highly
predictable m88ksim has many more instructions that produce
few values as compared with the less predictable gcc
and go. This would appear to be an intuitive result, but
there may be cases where it does not hold; for example if
values are generated in a fashion that is predictable with
computational predictors or if a small number of values
occur in many different sequences.
4.4 Sensitivity Experiments for Context Based
Prediction
In this section we discuss the results of experiments that
illustrate the sensitivity of fcm predictors to input data and
predictor order. For these experiments, we focus on the gcc
benchmark and report average correct predictions among
all instruction types.
Sensitivity to input data: We studied the effects of different
input files and flags on correct prediction. The fcm predictor
used in these experiments was order 2. The prediction
accuracy and the number of predicted instructions for
the different input files is shown in Table 6. The fraction of
correct predictions shows only small variations across the
different input files. We note that these results are for unbounded
tables, so aliasing affects caused by different data
set sizes will not appear. This may not be the case with
fixed table sizes.
In

Table

7 we show the predictability for gcc for the same
input file, but with different compilation flags, again using
an order 2 fcm predictor. The results again indicate that
variations are very small.
Sensitivity to the order: experiments were performed for
increasing order for the same input file (gcc.i) and flags.
The results for the different orders are shown in Figure
11. The experiment suggests that higher order means better
performance but returns are diminishing with increasing
order. The above also indicate that few previous values are
required to predict well.
Conclusions
We considered representatives from two classes of prediction
models: (i) computational and (ii) context based.
Simulations demonstrate that values are potentially highly
predictable. Our results indicate that context based prediction
outperforms previously proposed computational prediction
(stride and last value) and that if high prediction
correctness is desired context methods probably need to be
used either alone or in a hybrid scheme. The obtained results
also indicate that the performance of computational
prediction varies between instruction types indicating that
File Predictions (mil) Correct (%)
recog.i 192 78.6
stmt.i 372 77.8

Table

of 126.gcc to Different Input Files
Flags Predictions (mil) Correct (%)
none
ref flags 137 77.1

Table

7: Sensitivity of 126.gcc to Input Flags with input
file gcc.i72768084
Order
Prediction
Accuracy

Figure

11: Sensitivity of 126.gcc to the Order with input
file gcc.i
its performance can be further improved if the prediction
function matches the functionality of the predicted instruc-
tion. Analysis of the improvements of context prediction
over computational prediction suggest that about 20% of
the instructions that generate relatively few values are responsible
for the majority of the improvement. With respect
to the value characteristics of instructions, we observe
that the majority of instructions do not generate many
unique values. The number of values generated by instructions
varies among instructions types. This result suggests
that different instruction types need to be studied separately
due to the distinct predictability and value behavior.
We believe that value prediction has significant potential
for performance improvement. However, a lot of innovative
research is needed for value prediction to become an
effective performance approach.
6

Acknowledgements

This work was supported in part by NSF Grants MIP-
9505853 and MIP-9307830 and by the U.S. Army Intelligence
Center and Fort Huachuca under Contract DABT63-
95-C-0127 and ARPA order no. D346. The views and
conclusions contained herein are those of the authors and
should not be interpreted as necessarily representing the
official policies or endorsements, either expressed or im-
plied, of the U. S. Army Intelligence Center and Fort
Huachuca, or the U.S. Government.
The authors would like to thank Stamatis Vassiliadis for
his helpful suggestions and constructive critique while this
work was in progress.



--R

"Value locality and data speculation,"
"Exceeding the dataflow limit via value prediction,"
"Effective hardware-based data prefetching for high performance processors,"
"Examination of a memory access classification scheme for pointer intensive and numeric programs,"
"Prefetching using markov pre- dictors,"
"A load instruction unit for pipelined processors,"
"Speculative execution via address prediction and data prefetching,"
"Speculative execution based on value prediction,"
"A study of branch prediction strategies,"
"Alternative implementations of two-level adaptive branch prediction,"
"Target prediction for indirect jumps,"
"Improving the accuracy of static branch prediction using branch correlation,"
"Dynamic path-based branch correlation,"
"Compiler synthesized dynamic branch prediction,"
"Analysis of branch prediction via data compression,"
"Dynamic speculation and synchronization of data depen- dences,"
"The performance potential of data dependence speculation & collaps- ing,"
"An architectural alternative to optimizing compilers,"
"Caching function results: Faster arithmetic by avoiding unnecessary computation,"
"Dynamic instruction reuse,"
"Zero-cycle loads: Microarchitecture support for reducing load latency,"
"Information content of cpu memory referencing behavior,"
"Combining branch predictors,"
"Using hybrid branch predictors to improve branch prediciton in the presence of context switches,"

"Evaluating future microprocessors: The simplescalar tool set,"
--TR
Text compression
Alternative implementations of two-level adaptive branch prediction
Improving the accuracy of static branch prediction using branch correlation
Dynamic path-based branch correlation
Zero-cycle loads
Using hybrid branch predictors to improve branch prediction accuracy in the presence of context switches
Analysis of branch prediction via data compression
Value locality and load value prediction
Examination of a memory access classification scheme for pointer-intensive and numeric programs
Compiler synthesized dynamic branch prediction
Exceeding the dataflow limit via value prediction
The performance potential of data dependence speculation MYAMPERSANDamp; collapsing
Speculative execution via address prediction and data prefetching
Dynamic speculation and synchronization of data dependences
Dynamic instruction reuse
Prefetching using Markov predictors
Target prediction for indirect jumps
Effective Hardware-Based Data Prefetching for High-Performance Processors
An architectural alternative to optimizing compilers
A study of branch prediction strategies
Information content of CPU memory referencing behavior

--CTR
G. Surendra , S. Banerjee , S. K. Nandy, On the effectiveness of flow aggregation in improving instruction reuse in network processing applications, International Journal of Parallel Programming, v.31 n.6, p.469-487, December
Ehsan Atoofian , Amirali Baniasadi, Speculative trivialization point advancing in high-performance processors, Journal of Systems Architecture: the EUROMICRO Journal, v.53 n.9, p.587-601, September, 2007
Chao-Ying Fu , Matthew D. Jennings , Sergei Y. Larin , Thomas M. Conte, Value speculation scheduling for high performance processors, ACM SIGOPS Operating Systems Review, v.32 n.5, p.262-271, Dec. 1998
Martin Burtscher, An improved index function for (D)FCM predictors, ACM SIGARCH Computer Architecture News, v.30 n.3, June 2002
Po-Jen Chuang , Young-Tzong Hsiao , Yu-Shian Chiu, An Efficient Value Predictor Dynamically Using Loop and Locality Properties, The Journal of Supercomputing, v.30 n.1, p.19-36, October 2004
Avinash Sodani , Gurindar S. Sohi, Understanding the differences between value prediction and instruction reuse, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.205-215, November 1998, Dallas, Texas, United States
Sang-Jeong Lee , Pen-Chung Yew, On Table Bandwidth and Its Update Delay for Value Prediction on Wide-Issue ILP Processors, IEEE Transactions on Computers, v.50 n.8, p.847-852, August 2001
Chao-ying Fu , Jill T. Bodine , Thomas M. Conte, Modeling Value Speculation: An Optimal Edge Selection Problem, IEEE Transactions on Computers, v.52 n.3, p.277-292, March
Michael Bekerman , Stephan Jourdan , Ronny Ronen , Gilad Kirshenboim , Lihu Rappoport , Adi Yoaz , Uri Weiser, Correlated load-address predictors, ACM SIGARCH Computer Architecture News, v.27 n.2, p.54-63, May 1999
Avinash Sodani , Gurindar S. Sohi, An empirical analysis of instruction repetition, ACM SIGOPS Operating Systems Review, v.32 n.5, p.35-45, Dec. 1998
Jinsuo Zhang, The predictability of load address, ACM SIGARCH Computer Architecture News, v.29 n.4, September 2001
Yuan Chou , Brian Fahs , Santosh Abraham, Microarchitecture Optimizations for Exploiting Memory-Level Parallelism, ACM SIGARCH Computer Architecture News, v.32 n.2, p.76, March 2004
Jian Huang , David J. Lilja, Extending Value Reuse to Basic Blocks with Compiler Support, IEEE Transactions on Computers, v.49 n.4, p.331-347, April 2000
Mark Oskin , Frederic T. Chong , Matthew Farrens, HLS: combining statistical and symbolic simulation to guide microprocessor designs, ACM SIGARCH Computer Architecture News, v.28 n.2, p.71-82, May 2000
Dean M. Tullsen , John S. Seng, Storageless value prediction using prior register values, ACM SIGARCH Computer Architecture News, v.27 n.2, p.270-279, May 1999
Tarun Nakra , Rajiv Gupta , Mary Lou Soffa, Value prediction in VLIW machines, ACM SIGARCH Computer Architecture News, v.27 n.2, p.258-269, May 1999
Yiannakis Sazeides , James E. Smith, Modeling program predictability, ACM SIGARCH Computer Architecture News, v.26 n.3, p.73-84, June 1998
Daniel A. Connors , Wen-mei W. Hwu, Compiler-directed dynamic computation reuse: rationale and initial results, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.158-169, November 16-18, 1999, Haifa, Israel
Daniel A. Connors , Hillery C. Hunter , Ben-Chung Cheng , Wen-Mei W. Hwu, Hardware support for dynamic activation of compiler-directed computation reuse, ACM SIGPLAN Notices, v.35 n.11, p.222-233, Nov. 2000
Characterization of value locality in Java programs, Workload characterization of emerging computer applications, Kluwer Academic Publishers, Norwell, MA, 2001
M. Burrows , U. Erlingson , S.-T. A. Leung , M. T. Vandevoorde , C. A. Waldspurger , K. Walker , W. E. Weihl, Efficient and flexible value sampling, ACM SIGPLAN Notices, v.35 n.11, p.160-167, Nov. 2000
Jos Gonzlez , Antonio Gonzlez, The potential of data value speculation to boost ILP, Proceedings of the 12th international conference on Supercomputing, p.21-28, July 1998, Melbourne, Australia
M. Burrows , U. Erlingson , S-T. A. Leung , M. T. Vandevoorde , C. A. Waldspurger , K. Walker , W. E. Weihl, Efficient and flexible value sampling, ACM SIGOPS Operating Systems Review, v.34 n.5, p.160-167, Dec. 2000
Daniel A. Connors , Hillery C. Hunter , Ben-Chung Cheng , Wen-mei W. Hwu, Hardware support for dynamic activation of compiler-directed computation reuse, ACM SIGOPS Operating Systems Review, v.34 n.5, p.222-233, Dec. 2000
Martin Burtscher, TCgen 2.0: a tool to automatically generate lossless trace compressors, ACM SIGARCH Computer Architecture News, v.34 n.3, p.1-8, June 2006
Juan M. Cebrian , Juan L. Aragon , Jose M Garcia , Stefanos Kaxiras, Adaptive VP decay: making value predictors leakage-efficient designs for high performance processors, Proceedings of the 4th international conference on Computing frontiers, May 07-09, 2007, Ischia, Italy
Robert S. Chappell , Francis Tseng , Adi Yoaz , Yale N. Patt, Difficult-path branch prediction using subordinate microthreads, ACM SIGARCH Computer Architecture News, v.30 n.2, May 2002
Chia-Hung Liao , Jong-Jiann Shieh, Exploiting speculative value reuse using value prediction, Australian Computer Science Communications, v.24 n.3, p.101-108, January-February 2002
G. Surendra , Subhasis Banerjee , S. K. Nandy, On the effectiveness of prefetching and reuse in reducing L1 data cache traffic: a case study of Snort, Proceedings of the 3rd workshop on Memory performance issues: in conjunction with the 31st international symposium on computer architecture, p.88-95, June 20-20, 2004, Munich, Germany
Glenn Reinman , Brad Calder , Dean Tullsen , Gary Tyson , Todd Austin, Classifying load and store instructions for memory renaming, Proceedings of the 13th international conference on Supercomputing, p.399-407, June 20-25, 1999, Rhodes, Greece
Andreas Moshovos , Gurindar S. Sohi, Read-after-read memory dependence prediction, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.177-185, November 16-18, 1999, Haifa, Israel
Compiler controlled value prediction using branch predictor based confidence, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.327-336, December 2000, Monterey, California, United States
Zhang , Rajiv Gupta, Whole Execution Traces, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.105-116, December 04-08, 2004, Portland, Oregon
Jeremy Singer , Chris Kirkham, Dynamic analysis of program concepts in Java, Proceedings of the 4th international symposium on Principles and practice of programming in Java, August 30-September 01, 2006, Mannheim, Germany
Trace processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.138-148, December 01-03, 1997, Research Triangle Park, North Carolina, United States
Bryan Black , Brian Mueller , Stephanie Postal , Ryan Rakvic , Noppanunt Utamaphethai , John Paul Shen, Load execution latency reduction, Proceedings of the 12th international conference on Supercomputing, p.29-36, July 1998, Melbourne, Australia
Ilya Ganusov , Martin Burtscher, Efficient emulation of hardware prefetchers via event-driven helper threading, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA
Pedro Marcuello , Antonio Gonzlez , Jordi Tubella, Speculative multithreaded processors, Proceedings of the 12th international conference on Supercomputing, p.77-84, July 1998, Melbourne, Australia
Nana B. Sam , Martin Burtscher, On the energy-efficiency of speculative hardware, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy
Byung-Kwon Chung , Jinsuo Zhang , Jih-Kwon Peir , Shih-Chang Lai , Konrad Lai, Direct load: dependence-linked dataflow resolution of load address and cache coordinate, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
Timothy H. Heil , Zak Smith , J. E. Smith, Improving branch predictors by correlating on data values, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.28-37, November 16-18, 1999, Haifa, Israel
Youfeng Wu , Dong-Yuan Chen , Jesse Fang, Better exploration of region-level value locality with integrated computation reuse and value prediction, ACM SIGARCH Computer Architecture News, v.29 n.2, p.98-108, May 2001
Freddy Gabbay , Avi Mendelson, The effect of instruction fetch bandwidth on value prediction, ACM SIGARCH Computer Architecture News, v.26 n.3, p.272-281, June 1998
Parthasarathy Ranganathan , Sarita Adve , Norman P. Jouppi, Reconfigurable caches and their application to media processing, ACM SIGARCH Computer Architecture News, v.28 n.2, p.214-224, May 2000
Huiyang Zhou , Thomas M. Conte, Enhancing memory level parallelism via recovery-free value prediction, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
Peng , Jih-Kwon Peir , Qianrong Ma , Konrad Lai, Address-free memory access based on program syntax correlation of loads and stores, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.3, p.314-324, June
Matthew C. Chidester , Alan D. George , Matthew A. Radlinski, Multiple-path execution for chip multiprocessors, Journal of Systems Architecture: the EUROMICRO Journal, v.49 n.1-2, p.33-52, July
Chi-Hung Chi , Jun-Li Yuan , Chin-Ming Cheung, Cyclic dependence based data reference prediction, Proceedings of the 13th international conference on Supercomputing, p.127-134, June 20-25, 1999, Rhodes, Greece
Nana B. Sam , Martin Burtscher, Improving memory system performance with energy-efficient value speculation, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005
Madhu Mutyam , Vijaykrishnan Narayanan, Working with process variation aware caches, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
Tanaus Ramrez , Alex Pajuelo , Oliverio J. Santana , Mateo Valero, Kilo-instruction processors, runahead and prefetching, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy
Luis Ceze , Karin Strauss , James Tuck , Josep Torrellas , Jose Renau, CAVA: Using checkpoint-assisted value prediction to hide L2 misses, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.2, p.182-208, June 2006
Glenn Reinman , Brad Calder, Predictive techniques for aggressive load speculation, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.127-137, November 1998, Dallas, Texas, United States
Sangyeun Cho , Pen-Chung Yew , Gyungho Lee, Access region locality for high-bandwidth processor memory system design, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.136-146, November 16-18, 1999, Haifa, Israel
Ravi Bhargava , Lizy K. John, Latency and energy aware value prediction for high-frequency processors, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
Onur Mutlu , Hyesoon Kim , Yale N. Patt, Address-Value Delta (AVD) Prediction: Increasing the Effectiveness of Runahead Execution by Exploiting Regular Memory Allocation Patterns, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.233-244, November 12-16, 2005, Barcelona, Spain
Huiyang Zhou , Thomas M. Conte, Enhancing Memory-Level Parallelism via Recovery-Free Value Prediction, IEEE Transactions on Computers, v.54 n.7, p.897-912, July 2005
J. Gonzlez , A. Gonzlez, Control-Flow Speculation through Value Prediction, IEEE Transactions on Computers, v.50 n.12, p.1362-1376, December 2001
Martin Burtscher , Benjamin G. Zorn, Hybrid Load-Value Predictors, IEEE Transactions on Computers, v.51 n.7, p.759-774, July 2002
Huiyang Zhou , Jill Flanagan , Thomas M. Conte, Detecting global stride locality in value streams, ACM SIGARCH Computer Architecture News, v.31 n.2, May
Ilya Ganusov , Martin Burtscher, Future execution: A prefetching mechanism that uses multiple cores to speed up single threads, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.4, p.424-449, December 2006
Afrin Naz , Krishna Kavi , JungHwan Oh , Pierfrancesco Foglia, Reconfigurable split data caches: a novel scheme for embedded systems, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
Brad Calder , Glenn Reinman , Dean M. Tullsen, Selective value prediction, ACM SIGARCH Computer Architecture News, v.27 n.2, p.64-74, May 1999
Pedro Marcuello , Antonio Gonzlez, Clustered speculative multithreaded processors, Proceedings of the 13th international conference on Supercomputing, p.365-372, June 20-25, 1999, Rhodes, Greece
Andreas Moshovos , Gurindar S. Sohi, Reducing Memory Latency via Read-after-Read Memory Dependence Prediction, IEEE Transactions on Computers, v.51 n.3, p.313-326, March 2002
Martin Burtscher , Amer Diwan , Matthias Hauswirth, Static load classification for improving the value predictability of data-cache misses, ACM SIGPLAN Notices, v.37 n.5, May 2002
Jian Huang , David J. Lilja, Balancing Reuse Opportunities and Performance Gains with Subblock Value Reuse, IEEE Transactions on Computers, v.52 n.8, p.1032-1050, August
Smruti R. Sarangi , Wei Liu, Josep Torrellas , Yuanyuan Zhou, ReSlice: Selective Re-Execution of Long-Retired Misspeculated Instructions Using Forward Slicing, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.257-270, November 12-16, 2005, Barcelona, Spain
Timothy Sherwood , Suleyman Sair , Brad Calder, Predictor-directed stream buffers, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.42-53, December 2000, Monterey, California, United States
Daehyun Kim , Mainak Chaudhuri , Mark Heinrich, Leveraging cache coherence in active memory systems, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
Zhang , Rajiv Gupta, Whole execution traces and their applications, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.3, p.301-334, September 2005
Sangyeun Cho , Pen-Chung Yew , Gyungho Lee, A High-Bandwidth Memory Pipeline for Wide Issue Processors, IEEE Transactions on Computers, v.50 n.7, p.709-723, July 2001
Sang-Jeong Lee , Pen-Chung Yew, On Augmenting Trace Cache for High-Bandwidth Value Prediction, IEEE Transactions on Computers, v.51 n.9, p.1074-1088, September 2002
Lucian Codrescu , D. Scott Wills , James Meindl, Architecture of the Atlas Chip-Multiprocessor: Dynamically Parallelizing Irregular Applications, IEEE Transactions on Computers, v.50 n.1, p.67-82, January 2001
Martin Burtscher, VPC3: a fast and effective trace-compression algorithm, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
Glenn Reinman , Brad Calder , Todd Austin, Optimizations Enabled by a Decoupled Front-End Architecture, IEEE Transactions on Computers, v.50 n.4, p.338-355, April 2001
Yiannakis Sazeides , James E. Smith, Limits of Data Value Predictability, International Journal of Parallel Programming, v.27 n.4, p.229-256, Aug. 1999
Martin Burtscher , Nana B. Sam, Automatic Generation of High-Performance Trace Compressors, Proceedings of the international symposium on Code generation and optimization, p.229-240, March 20-23, 2005
Suleyman Sair , Timothy Sherwood , Brad Calder, A Decoupled Predictor-Directed Stream Prefetching Architecture, IEEE Transactions on Computers, v.52 n.3, p.260-276, March
S. Subramanya Sastry , Rastislav Bodk , James E. Smith, Rapid profiling via stratified sampling, ACM SIGARCH Computer Architecture News, v.29 n.2, p.278-289, May 2001
Martin Burtscher , Ilya Ganusov , Sandra J. Jackson , Jian Ke , Paruj Ratanaworabhan , Nana B. Sam, The VPC Trace-Compression Algorithms, IEEE Transactions on Computers, v.54 n.11, p.1329-1344, November 2005
Context Based Prediction;Last Value Prediction;stride prediction;prediction;value prediction