Graphics Reference
In-Depth Information
A common rule of thumb is that programs spend 90
%
of their time running only
10
%
of their program code. The 90
10 rule is an approximation—for example,
code percentages varied between six and 57 in tests reported by John Hennessy
and David Patterson [HP96]—but it suggests an essential truth, which is that the
outcomes of computing
events,
such as generating an address or taking a branch,
are not evenly distributed. Instead, these events, when treated as random vari-
ables, have probability distributions that are unfair (meaning that outcomes have
different probabilities) and dependent (meaning that the probability distributions
themselves change with the history of recent events).
An unfair coin is undesirable, but unfair and dependent probability distribu-
tions in computing are an important opportunity—they allow system designers
to make optimizations that dramatically improve performance and efficiency. In
computer science the term
locality
describes the nature of the unfair, dependent
probability distributions that are observed in functional computing systems. In this
section we define various forms of locality and study how system designers take
advantage of them.
/
In treating memory abstractly as an ordered array of items, two observations have
been made about the patterns of access to these items during the execution of a
program. First, an item that has been accessed recently has an increased proba-
bility of being accessed again. This program property is called
temporal locality.
Second, items whose addresses are similar tend to be accessed close together in
time. This program property, though it is also time-dependent, is called
spatial
locality
to emphasize its application to multiple items. Together, temporal and
spatial locality constitute
locality of reference.
While locality of reference is observed in all computing systems, design deci-
sions significantly affect how much is observed. Consider the sequence in which
instructions are fetched. A computer could be designed such that each instruction
specified the address of the subsequent instruction, allowing execution to skip
arbitrarily through the code. But this approach is never taken.
13
Instead, design-
ers universally choose to execute instructions sequentially, except in the special
case of branching. This choice directly increases spatial locality in an obvious
way. Because most branches cause short sequences of instructions to be repeated
(i.e., they
loop
), sequential instruction fetching also increases temporal locality.
Indeed, this single decision frequently ensures that locality of reference is greater
for instruction accesses than it is for data accesses, despite designers' attempts to
increase the latter.
Because GPU shaders are typically much smaller than the data structures they
access, GPU designers are more concerned with data locality than they are with
code locality. An example of a design decision that greatly affects GPU data local-
ity is the way that 2D texel coordinates, which specify a single texel in a 2D tex-
ture image, are mapped to the (1D) memory addresses of the texel-data storage
locations. When fragments generated by the rasterization of a small triangle are
13. To this author's knowledge. But partially randomized execution sequences are now
employed as a security measure, to thwart the attempts of computer “hackers.”
