Graphics Reference
In-Depth Information
On a CPU with nonblocking hit-under-miss loads, the earlier loop would be better
written in an interleaved fashion to have processing go on while the next cache line
is being fetched.
Elem a = elem[0];
// Load the cache line of the first four array elements
for(inti=0;i<4*n;i+=4){
Elem e = elem[i + 4];
// Cache miss. Fetches next cache line using nonblocking load
Elem b = elem[i + 1];
// These following three values are in cache and...
Elem c = elem[i + 2];
// ...are loaded as hit-under-miss; no stalls
Elem d = elem[i + 3];
Process(a);
// Process the data from the cache line that...
Process(b);
// ...was fetched in the previous iteration
Process(c);
Process(d);
a=e;
// e now in cache, and so is b, c, and d of next iteration
}
This particular code fetches one element beyond the end of the
elem
array, although
the element is not actually processed. When reading data beyond the end of the array
is a problem, the data access can be avoided by unrolling the last loop iteration and
handling that iteration separately.
13.4
Cache-aware Data Structures and Algorithms
It is wise to design with best cache utilization in mind. Algorithms and data structures
so designed, targeted for a given platform configuration, are referred to as
cache aware
or
cache conscious
.
To illustrate how cache awareness influences the code design, the following
subsections include code examples of the ideas presented. First is a compact and
cache-efficient representation for
k
-d trees. After that a compact representation of
an AABB tree is presented, showing how quantization can be used to reduce storage
requirements.
For code that must perform well across several different architectures, an alter-
native to constructing multiple cache-aware versions is to implement
cache oblivious
code. Such code promises to be reasonably cache efficient on any traditional cache
setup. Cache obliviousness is discussed in Section 13.4.3.
13.4.1
A Compact Static
k
-d Tree
A node in a
k
-d tree must hold a type specifying whether the node is an inter-
nal node or a leaf node. If the node is internal, it must also contain two more
