TAOCP 2.2.2 Exercise 3

The purpose of (8) is to replace fixed-base addressing by relative addressing when the base location $L_0$ varies.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.2: Sequential Allocation

Exercise 3. [21] Suppose that MIX is extended as follows: The I-field of each instruction is to have the form $8I_1 + I_2$, where $0 \le I_1 \le 8$, $0 \le I_2 \le 8$. In assembly language one writes 'OP ADDRESS,I1:I2' or (as presently) 'OP ADDRESS,I2' if $I_1 = 0$. The meaning is to perform first the "address modification" $I_1$ on ADDRESS, then to perform the "address modification" $I_2$ on the resulting address, and finally to perform the OP with the new address. The address modifications are defined as follows:

0: $M = A$

1: $M = A + rI1$

2: $M = A + rI2$

$\ldots$

6: $M = A + rI6$

7: $M =$ resulting address defined from the 'ADDRESS,I1:I2' fields found in location $A$. The case $I_1 = I_2 = 7$ in location $A$ is not allowed. (The reason for the latter restriction is discussed in exercise 5.)

Here $A$ denotes the address before the operation, and $M$ denotes the resulting address after the address modification. In all cases the result is undefined if the value of $M$ does not fit in two bytes and a sign. The execution time is increased by one unit for each "indirect-addressing" (modification 7) operation performed.

As a nontrivial example, suppose that location 1000 contains 'NOP 1000,1:7'; location 1001 contains 'NOP 1000,2'; and index registers 1 and 2 respectively contain 1 and 2. Then the command 'LDA 1000,7:2' is equivalent to 'LDA 1004', because

$$ 1000,7:2 = (1000,1:7),2 = (1001,7),2 = (1000,2),2 = 1002,2 = 1004. $$

a) Using this indirect addressing feature (if necessary), show how to simplify the coding on the right-hand side of (8) so that two instructions are saved per reference to the table. How much faster is your code than (8)?

b) Suppose there are several tables whose base addresses are stored in locations BASE + 1, BASE + 2, BASE + 3, ...; how can the indirect addressing feature be used to bring the Ith element of the Jth table into register A in one instruction, assuming that I is in rI1 and J is in rI2?

c) What is the effect of the instruction 'ENT4 X,7', assuming that the (3:3)-field in location $X$ is zero?

Verified: no
Solve time: -

Solution

(a)

The purpose of (8) is to replace fixed-base addressing by relative addressing when the base location $L_0$ varies. The code in (8) is

LD1   I
LDA   BASE(0:2)
STA   *+1(0:2)
LDA   *,1

The instruction LDA *,1 is modified so that its address field becomes the current value of BASE, then indexed by rI1. Thus the effective address is $\text{BASE}+I$.

With the new addressing feature, location BASE may contain an instruction whose address field is the current base location. For example, let location BASE contain

NOP   0,1

with its address field replaced dynamically by the current value of $L_0$. Then the instruction

LDA   BASE,7:1

performs the following address calculation:

$$ \text{BASE},7:1 = (L_0,1) = L_0+rI1. $$

Hence the desired table element is obtained directly.

The revised code is therefore

LD1   I
LDA   BASE,7:1

Two instructions are saved, namely the LDA BASE(0:2) and STA *+1(0:2) of (8).

To compare speeds, count execution times. In MIX, LD1, LDA, and STA each require $2$ time units. The original code (8) therefore requires

$$ 2+2+2+2=8 $$

time units.

The new code requires

$$ 2+2+1=5 $$

time units, because one indirect-addressing operation contributes one additional unit of time.

Thus the saving is

$$ 8-5=3 $$

time units per reference. The new code is faster by a factor of

$$ \frac{8}{5}. $$

Hence the relative-addressing reference is reduced from $8$ to $5$ time units.

$$ \boxed{\text{Use } \texttt{LDA BASE,7:1};\ \text{3 time units faster, factor } 8/5} $$

(b)

Suppose the base address of the $J$th table is stored in location BASE + J. The problem is to bring the $I$th element of the $J$th table into register A, assuming $I$ is in rI1 and $J$ is in rI2.

The address modification $2$ adds rI2, so

$$ \text{BASE},2=\text{BASE}+J. $$

Applying indirect addressing next,

$$ \text{BASE},2:7 = (\text{BASE}+J,7), $$

which becomes the base address stored in location BASE+J.

Finally applying modification $1$ adds rI1, giving

$$ \text{BASE},2:7:1 = (\text{base of table }J)+I. $$

Since only two modifications are permitted, we encode the stored base information so that the indirect step already includes indexing by rI1. Let each location BASE+J contain an instruction of the form

NOP   L0,1

where $L_0$ is the base of the corresponding table. Then the single instruction

LDA   BASE,2:7

works as follows:

$$ \text{BASE},2:7 = (\text{BASE}+J,7) = (L_0,1) = L_0+rI1. $$

Thus the Ith element of the Jth table is loaded into register A in one instruction.

LDA   BASE,2:7

$$ \boxed{\texttt{LDA BASE,2:7}} $$

provided each location BASE+J contains a word of the form NOP L0,1, with $L_0$ the base address of table $J$.

(c)

Consider the instruction

ENT4  X,7

The 7 modification means indirect addressing. Hence the address is determined by the instruction stored at location $X$.

Suppose the $(3{:}3)$-field in location $X$ is zero. In MIX format, the $(3{:}3)$-field contains the index specification $I_1$. Since this field is zero, the instruction at location $X$ has no first address modification.

If location $X$ contains an instruction of the form

OP ADDRESS,I2

then

$$ X,7=(\text{ADDRESS},I_2). $$

Therefore ENT4 X,7 enters into register rI4 the effective address that would result from executing the instruction stored at $X$, except that no operation is actually performed.

In particular, if location $X$ contains OP ADDRESS,I2, then after execution

$$ rI4=\text{ADDRESS}+rI_{I_2}, $$

with the convention that $I_2=0$ means no indexing.

Thus ENT4 X,7 places in rI4 the effective address defined by the instruction in location $X$.

This completes the proof.

∎