TAOCP 1.3.1 Exercise 19
The execution times given in Section 1.
Section 1.3.1: Description of MIX
Exercise 19. [14] What is the execution time of the program in the preceding exercise, not counting the HLT instruction?
Verified: yes
Solve time: 1m05s
Solution
The execution times given in Section 1.3.1 are:
$$ \begin{aligned} &\text{all STORE operations} &&= 2,\ &\text{all shift operations} &&= 2,\ &\text{ADD} &&= 2,\ &\text{all comparison operations} &&= 2,\ &\text{MOVE of } n \text{ words} &&= 2n+1,\ &\text{NUM, CHAR} &&= 10,\ &\text{all remaining operations} &&= 1. \end{aligned} $$
The program of Exercise 18 executes each instruction exactly once before reaching HLT. Since HLT is not to be counted, we sum the times of the first fifteen instructions:
$$ \begin{array}{l|c} \text{Instruction} & \text{Time}\ \hline \texttt{STZ 1} & 2\ \texttt{ENNX 1} & 1\ \texttt{STX 1(0:1)} & 2\ \texttt{SLAX 1} & 2\ \texttt{ENNA 1} & 1\ \texttt{INCX 1} & 1\ \texttt{ENT1 1} & 1\ \texttt{SRC 1} & 2\ \texttt{ADD 1} & 2\ \texttt{DEC1 -1} & 1\ \texttt{STZ 1} & 2\ \texttt{CMPA 1} & 2\ \texttt{MOVE -1,1(1)} & 2\cdot1+1=3\ \texttt{NUM 1} & 10\ \texttt{CHAR 1} & 10 \end{array} $$
Therefore
$$ 2+1+2+2+1+1+1+2+2+1+2+2+3+10+10 =42. $$
Hence the execution time of the program, excluding the HLT instruction, is
$$ \boxed{42} $$
time units. ∎
The MIX timing rules used above are stated in Section 1.3.1. In particular, MOVE with count $1$ requires $2\cdot1+1=3$ time units, while NUM and CHAR each require $10$ time units.