Memory-Hierarchy Tradeoffs - Models of Computation: Exploring the Power of Computing - page 560

DEFINITION 11.8.1 The block-transfer model (BTM) is a serial computer in which a CPU is
attached to an M -word primary memory and to a secondary memory of unlimited size that stores
words in blocks of size B . Words are moved in blocks between the memories and words that leave
primarymemoryinoneblockmustreturninthatblock.An I/O operation is the movement of a
block to or from secondary memory. The I/O time with the BTM is the number of I/O operations.

The secondary memory in the BTM can be a main memory if the primary memory is a
cache, or can be a disk if the primary memory is a random-access memory. In fact, it can model
I/O operations between any two devices. Since a block can be viewed as the contents of one
track of a disk, the time to retrieve any word on the track is comparable to the time to retrieve
theentiretrack.(SeeSection 11.6 .) Since data is moved in blocks in the BTM, it makes sense
to define simple I/O operations.

DEFINITION 11.8.2 An I/O operation in the BTM is simple if, after a block or word is copied
from one memory to the other, the copy in the first memory is deleted.

Simple I/O operations for the pebble game are defined in Problem 11.10 . In this problem
the reader is asked to show that replacing all I/O operations with simple I/O operations has
the effect of at most doubling the number of I/O operations. The proof of this fact applies
equally well to the BTM.
We illustrate the use of the block-transfer model by examining the sorting problem. We
derive a lower bound on the I/O time for all sorting algorithms and exhibit a sorting algorithm
that meets the lower bound, up to a constant multiplicative factor. To derive the lower bound,
we limit the range of sorting algorithms to those based on the comparison of keys, as stated
below. (Sorting algorithms that are not comparison-based, such as the various forms of radix
sort , assume that keys consist of individual digits and that digits are used to classify keys.)
ASSUMPTION 11.8.1 All words to be sorted are located initially in the secondary memory. The
compare-exchange operation is the only operation available to implement sorting algorithms on
the BTM. In addition, an arbitrary permutation of the contents of the primary memory of the BTM
canbedoneduringthetimerequiredforoneI/Ooperation.

The assumption that the CPU can perform an arbitrary permutation on the contents of the
primary memory during one I/O operation acknowledges that I/O operations take a very long
time relative to CPU instructions.
Algorithms consistent with these assumptions are described by the multiway decision trees
discussed below. They are a generalization of the binary decision tree , a binary tree in which
each vertex has associated with it a comparison between two variables. For example, if keys x 1
and x 2 are compared at the root vertex, the comparison has two outcomes, namely x 1 <x 2 or
x 1 ≥

x 2 , which are associated with the subtrees to the left and right of the root, respectively.
Similar comparisons and outcomes are possible at each vertex of these two subtrees. A sequence
of comparisons terminates on a leaf node.
Since a binary decision tree captures each of the data-dependent comparisons between keys
in comparison-based sorting algorithm, each leaf is associated with the permutation of the
original sequence of variables that puts the sequence into sorted order. Thus, a binary decision
tree for sorting must have at least n ! distinct leaves, one for every permutation of n items. The
length of a path through a binary decision tree is the number of comparisons performed on the
particular input, and the length of the longest path is a measure of the worst-case number of