Homework Page: Ceng-111 Homework's

An Example

If HW-1 is submitted the below given sequence, it will compute the sum of its 2nd and 3rd elements, then compare this sum with the 4th element. If the sum equals the 4th element then the 5th element of the sequence is changed to 1 else it is changed to 0.

We will go through each cycle of the process and explain it:

Cycle 1

The machine starts now. So the registers are as follows:

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Since ${\cal I}$ contains , the th (zeroth) element of the sequence, $[{\cal I}]$ is fetched. This will be our current instruction. Looking at the sequence you may realize that this element is 9. Look at the definition of the instruction 9 (given on the previous page), you will see that the action of the instruction 9 is:

$${\cal I}\leftarrow [{\cal I}+ 1]$$

${\cal I}+ 1$ is 1 and therefore $[{\cal I}+ 1]$ is simply [1], in other words the 1st element of the sequence. That is 6. So the value in ${\cal I}$ is changed by the assignment operation to be 6. And now the registers are:

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Cycle 2

${\cal I}$ contains 6. The machine fetches [6] which is 3. Instruction 3 is defined as:

$${\cal R}_1\leftarrow [[{\cal I}+1]] \;,\quad {\cal I}\leftarrow {\cal I}+ 2$$

The first assignment will change the content of ${\cal R}_1$ to be $[[{\cal I}+1]]$. Now do not panic! ${\cal I}$ was holding a value of 6 therefore the inner brackets are nothing else but

$$[[\;\underbrace{{\cal I}+1}_{[6+1] }\;]] \qquad \mbox{which is} \quad [[7]]$$

[7] is the 7th element of the sequence, namely 2. So [[7]] is nothing but [2]. As you must have got used to it by now, this is the 2nd element of the sequence, we go and fetch it. It is 12. Since the first assignment was ${\cal R}_1\leftarrow [[{\cal I}+1]]$ this value found on the right hand side of the assignment, namely the 12, will be stored into ${\cal R}_1$. The second assignment increments the value of ${\cal I}$ by 2. Thus ${\cal I}$ is now 6+2 which is 8. At the end of this cycle the register contents are:

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Cycle 3

Since ${\cal I}$ is containing 8 we fetch [8] as the instruction of this cycle. The 8th element of the sequence is 4. The instruction 4 is defined similar to the instruction 3 but now it is the ${\cal R}_2$ register that receives the value and not ${\cal R}_1$. Going through a very similar argumentation that we did for cycle 2, we conclude that ${\cal R}_2$ will be assigned the value [3] which is 27. Following this assignment, ${\cal I}$ will be incremented by 2. That is how the registers look like:

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Cycle 4

This cycle's instruction is [10]. Looking at the sequence we see that this is the instruction 11. An instruction which adds the content of ${\cal R}_2$ to the content of ${\cal R}_1$ and assigns the sum to ${\cal R}_1$(Please go and check the definition of instruction 11). So the following operation is performed:

$${\cal R}_1\leftarrow 12 + 27$$

So, ${\cal R}_1$ is assigned a value of 39. Due to the definition of instruction 11, the ${\cal I}$ register is incremented by 1. At the end of this cycle the registers read as:

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Cycle 5

Our instruction is [11] which is 4. We have had a similar instruction in cycle 3. But this time $[{\cal I}+ 1]$ is 4 which means that ${\cal R}_2$ is assigned the value [4]. From the sequence we get that this value is 39. So ${\cal R}_2\leftarrow 39$. By the definition, ${\cal I}$ is incremented by 2. Now the registers are:

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Cycle 6

The instruction of this cycle is [13], namely 16. This is a comparison test performed between ${\cal R}_1$ and ${\cal R}_2$. If they are equal ${\cal R}_1$ is changed to , if the value of ${\cal R}_1$ is greater than the value of ${\cal R}_2$ then ${\cal R}_1$ is changed to 1. If it is the third possibility, which is the only one left, namely the case where the value of ${\cal R}_1$ is lesser than the value of ${\cal R}_2$ then ${\cal R}_1$ is changed to -1. In all cases ${\cal I}$ is incremented by one. Following this definition and looking at the contents of the registers we can conclude that HW-1 will change ${\cal R}_1$ to since both ${\cal R}_1$ and ${\cal R}_2$ have the value 39, hence they are equal. The registers are:

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Cycle 7

The instruction is [14] which reads as 10. This is a conditional jump (`jump on non-zero'). If the register ${\cal R}_1$ contains a non zero value then the instruction of the next cycle will be fetched from the sequence position that given at $[{\cal I}+ 1]$. In our case the register ${\cal R}_1$ indeed contains a . So the jump will not take place and the ${\cal I}$ register will simply be incremented by 2. (If the jump would have taken place then ${\cal I}$ would be set to 20 and this would be the position in the sequence from which the instruction for cycle 8 would be fetched) So the registers are

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Cycle 8

The instruction is now [16], that is 2. This will load ${\cal R}_2$ with $[{\cal I}+ 1]$. In our case this is ${\cal R}_2\leftarrow [17]$ and will result in ${\cal R}_2\leftarrow 1$. For an instruction 2, ${\cal I}$ will be incremented by 2. At the end of this cycle we have in the registers

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Cycle 9

The instruction is [18] which is 9 an instruction that performs an unconditional jump. ${\cal I}$ will be set to $[{\cal I}+ 1]$ and that is 22. The registers are

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Cycle 10

The instruction is [22] which is 1. This instruction will load ${\cal R}_1$ with $[{\cal I}+ 1]$. For our case this is 5. Instruction 1 increments ${\cal I}$ by 2. Now we have the registers as

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Cycle 11

We are almost at the end! The instruction in turn is [24], that is 7. An instruction that performs

$$[{\cal R}_1] \leftarrow{\cal R}_2$$

and then increment ${\cal I}$ by one. Due to this definition a $[5] \leftarrow 1$ is carried out. And for the first time we have changed a value in the sequence. Now the 5th element is no more 99 but 1. This was the claimed action of the HW-1 machine with this example sequence. After a following incrementation of ${\cal I}$ the registers are:

$${\cal R}_1 {\cal R}_2 {\cal I}$$

Cycle 12

Yes, unbeliveable but true, the machine stops and we all go home! The instruction for this cycle is [25] which is simply 0. And this means halt.

the final picture of the sequence is:

For sake of completeness we display the registers at the moment of the halt:

$${\cal R}_1 {\cal R}_2 {\cal I}$$

``The name of the song is called `Haddocks' Eyes.'''
``Oh, that's the name of the song, is it?'' Alice said trying to feel interested.

``No, you don't understand,'' the Knight said, looking a little vexed.
``That's what the name is called. Then name really is `The Aged Aged Man.'''
``Then I ought to have said `That's what the song is called'?'' Alice corrected herself.

``No, you oughtn't: that's quite another thing! The song is called `Ways and Means': but that's only what it's called, you know!''
``Well, what is the song, then?'' said Alice, who was by this time completely bewildered.

``I was comming to that,'' the Knight said. ``The song really is `A-sitting On A Gate': and the tune's my own invention.''

-Lewis Carroll, THROUGH THE LOOKING GLASS

Homework Page: Ceng-111 Homework's