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

Sector of a
Cylinder

Disk Rotation

In Out

Disk

Controller

Head Movement

Figure 11.13 A disk unit with three platters and two heads per disk. Each track is divided into
four sectors and heads move in and out on a common arm. The memory of the disk controller
holds the contents of one track on one disk.

same. Figure 11.13 suggests why this is so. A disk spinning at 3,600 rpm that has 40 sectors
per track and 512 bits per sector (its block size) requires about 10 msec to find data in the track
under the head. However, the time to read one sector of 64 bytes (512 bits) is just .42 msec.
To model this phenomenon, we assume that the time to access k disk sectors with con-
secutive addresses is α + kβ ,where α is a large constant and β is a small one. (This topic is
also discussed in Section 7.3 .) Given the ratio of α to β ,itmakessensetomovedatatoand
from a disk in blocks of size about equal to the number of bytes on a track. Some operating
systems move data in track-sized blocks, whereas others move them in smaller units, relying
upon the fact that a disk controller typically keeps the contents of its current track in a fast
random-access memory so that successive sector accesses can be done quickly.
The gross characteristics of disks described by the above assumption hold for other storage
devices as well, although the relative values of the constants differ. For example, in the case of a
tape unit, advancing the tape head to the first word in a consecutive sequence of words usually
takes a long time, but successive words can be read relatively quickly.
The situation with interleaved random-access memory is similar, although the physi-
cal arrangement of memory is radically different. As depicted in Fig. 11.14 , an interleaved
random-access memory is a collection of 2 r memory modules, r 1, each containing 2 k

b -bit words. Such a memory can simulate a single 2 r + k -word b -bit random-access memory.
Words with addresses 0, 2 r ,22 r ,32 r , ... ,2 k− 1 2 r are stored in the first module, words with
addresses 1, 2 r + 1, 2 2 r + 1, 3 2 r + 1, ... ,2 k− 1 2 r + 1 in the second module, and words with
addresses 2 r

≥

1, 2 2 r 1, 3 2 r 1, 4 2 r 1, ... ,2 r + k 1 in the last module.

To access a word in this memory, the high order k bits are provided to each module. If
a set of words is to be read, the words with these common high-order bits are copied to the
registers. If a set of words is to be written, new values are copied from the registers to them.
When an interleaved memory is used to simulate a much faster random-access memory,
aCPUwritestoorreadsfromthe2 r registers serially, whereas data is transferred in parallel
between the registers and the modules. The use of two sets of registers ( double buffering )

− − − − −