Parallel Computer Architecture

182 CHAPTER 3 Programming for Performance

Spatial Locality The organization of the computation and the lexicographic sorting

of the itemsets and transactions causes most of the traversals through the data to be

simple front-to-back sweeps that exhibit very good predictability and spatial local-

ity. This is particularly important in reading from disk, since it is important to amor-

tize the high start-up costs of a disk read over a large amount of useful data.

Temporal Locality As discussed earlier, proceeding over one equivalence class at a

time is much like blocking, although how successful it is depends on whether the

data for that equivalenc ...