TAOCP 7.1.3 Exercise 85

Let $i=(i_4 i_3 i_2 i_1 i_0)_2$, $j=(j_4 j_3 j_2 j_1 j_0)_2$, $k=(k_4 k_3 k_2 k_1 k_0)_2$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 85. [22] [22] (K. D. Tocher, 1954.) Imagine that you have a vintage 1950s computer with a drum memory for storing data, and that you need to do some computations with a $32 \times 32 \times 32$ array $a[i, j, k]$, whose subscripts are 5-bit integers in the range $0 \le i, j, k < 32$. Unfortunately your machine has only a very small high-speed memory. You can access only 128 consecutive elements of the array in fast memory at any time. Since your application usually moves from $a[i,j,k]$ to a neighboring position $a[i',j',k']$, where $|i - i'| + |j - j'| + |k - k'| = 1$, you have decided to allocate the array so that, if $i = (i_4 i_3 i_2 i_1 i_0)_2$, $j = (j_4 j_3 j_2 j_1 j_0)_2$, and $k = (k_4 k_3 k_2 k_1 k_0)_2$, the array entry $a[i, j, k]$ is stored in drum location $(k_4 j_4 i_4 k_3 j_3 i_3 k_2 j_2 i_2 k_1 j_1 i_1 k_0 j_0 i_0)_2$. By interleaving the bits in this way, a small change to $i$, $j$, or $k$ will cause only a small change in the address.

Discuss the implementation of this addressing function: (a) How does it change when $i$, $j$, or $k$ changes by $\pm 1$? (b) How would you handle a random access to $a[i,j,k]$, given $i$, $j$, and $k$? (c) How would you detect a "page fault" (namely, the condition that a new segment of 128 elements must be swapped into fast memory from the drum)?

Verified: yes
Solve time: 6m02s

Solution

Let $i=(i_4 i_3 i_2 i_1 i_0)_2$, $j=(j_4 j_3 j_2 j_1 j_0)_2$, $k=(k_4 k_3 k_2 k_1 k_0)_2$. The drum address is the 15-bit integer

$A(i,j,k)=(k_4 j_4 i_4, k_3 j_3 i_3, k_2 j_2 i_2, k_1 j_1 i_1, k_0 j_0 i_0)_2,$

so bit positions $0,3,6,9,12$ correspond to $i_0,\dots,i_4$, positions $1,4,7,10,13$ to $j_0,\dots,j_4$, and positions $2,5,8,11,14$ to $k_0,\dots,k_4$.

(a)

Changing $i$, $j$, or $k$ by $\pm 1$ corresponds to adding or subtracting $1$ in a 5-bit binary integer, hence performing binary addition with carry confined to 5 bits.

For $i \leftarrow i \pm 1$, only the bits $i_0,\dots,i_4$ are affected, and carries propagate within this 5-bit block. In the interleaved address these bits occupy positions $0,3,6,9,12$, so the operation modifies exactly those five bit positions and no others. Each bit flip in $i$ induces a flip in the corresponding address position, while carries may propagate through consecutive $i$-positions in increasing significance order.

The same holds for $j$ and $k$, with their bits located at disjoint position sets ${1,4,7,10,13}$ and ${2,5,8,11,14}$ respectively. Therefore a $\pm 1$ change in any coordinate changes only its five designated bit positions in $A(i,j,k)$, and within those positions the pattern is exactly the binary increment or decrement pattern of a 5-bit counter.

No interaction occurs between coordinates because their bit positions are disjoint in the interleaving.

(b)

Random access requires computing $A(i,j,k)$ from the binary expansions. Write each coordinate as

$i=\sum_{t=0}^{4} i_t 2^t,\quad j=\sum_{t=0}^{4} j_t 2^t,\quad k=\sum_{t=0}^{4} k_t 2^t.$

The address is constructed by placing each bit into its fixed interleaved position:

$A(i,j,k)=\sum_{t=0}^{4} \left(i_t 2^{3t} + j_t 2^{3t+1} + k_t 2^{3t+2}\right).$

This can be computed in constant time using masking and shifts. For each coordinate, extract its bits and spread them:

$i \mapsto \sum_{t=0}^{4} (i_t \ll 3t), \quad j \mapsto \sum_{t=0}^{4} (j_t \ll (3t+1)), \quad k \mapsto \sum_{t=0}^{4} (k_t \ll (3t+2)).$

The three results are combined by bitwise OR, since their bit supports are disjoint:

$A(i,j,k) = I \mid J \mid K.$

Thus random access is achieved by a fixed sequence of bit tests, shifts, and OR operations, independent of $n=32$ except for constant word size.

(c)

A segment contains $128=2^7$ consecutive drum locations, so the segment index of address $A$ is

$P(A)=\left\lfloor \frac{A}{128} \right\rfloor = A \gg 7.$

A page fault occurs exactly when the computed page index differs from the page currently resident in fast memory. If the current loaded segment has index $P_0$, then a fault occurs when

$A(i,j,k) \gg 7 \ne P_0.$

Equivalently, the low 7 bits determine the position inside the segment and the remaining 8 bits determine the segment identity. A change of $(i,j,k)$ triggers a page fault precisely when the interleaved address crosses a multiple of $128$, that is when bit $7$ or higher of $A$ changes relative to the previous access.

Since the addressing function is explicit, detection reduces to computing $A(i,j,k)$ and comparing its upper bits with the cached page identifier. This completes the specification of page-fault detection for the interleaved layout. ∎