More About Multilevel Machines

Credits

Dr. Niall McMahon
Drawing on previous work by:
Dr. Michael Scriney
Dr. Long Cheng
And sources credited in the references.
Autumn 2022.

Computer Levels

• Level 5
  Problem-oriented language level.
  For example, C, C++, Java and so on.
• Level 4
  Assembly language level.
  Compiled from Level 5.

  ----
  Levels 1 - 3 are the domain of system programming and system software.
  ----

• Level 3
  Operating system (OS) machine level.
  Assembled from Level 4.
  Some instructions carried out directly by L2 microprogram. Others interpreted by the OS.
  System calls are L3 instructions that differ from those in L2.
• Level 2
  Instruction set architecture (ISA) level.
  Partial interpretation from Level 3.
  Microprogram or hardware execution circuit intepreter.
• Level 1
  Microarchitecture.
  Interpretation or direct execution from Level 2.
  Collection of registers (built from 16, 32 or 64 1-bit memories, in turn built from gates.)
  Also the arithmetic logic unit (ALU) circuit.
• Level 0
  Digital logic level.
  Hardware. Logical gates consisting of a few transistors.

Back to the 60s

The following examples are all adapted from Dodd's excellent book (Computers by K.N. Dodd. Pan Books. 1968).

Running a Program

• By pushing start button, computer put into "zero" state.
• Reads tape.
• Carries out instructions.
• Light comes on to indicate finished/ready.
• Operator loads second part.
• Calculation finishes.
• Light comes on.
• Operator takes tape that represents output.
• Tape fed through tape reader by programmer.
• Output.

Memory

• Accumulator (1 word).
• Special store (10 words).
• Main store (990 words).

Basic Operations

• Z zeroes accumulator
• Accumulator denoted by a.
• Store location is n.
• C(a) + C(n) causes the accumulator to be given the value of C(a) (value in accumulator) + C(n) value at n.
• If word n = 275 contains number C(n) = 5.327, then:
  A 275
  adds C(a) + C(275) = 0 + 5.327
• S n - does the opposite.
• M n - equivalent multiplication.
• D n - equivalent division.
• R n - removes result from accumulator and stores it in location n.
• E - indicates complete calculation.

Example Program

Code

11:Z
12: A 1
13: A 2
14: R 3
15: E

Pseudo-Code

• Zero in the accumulator.
• Add contents of 1 to accumulator.
• Add contents of 2 to accumulator.
• Remove accumulator contents to location 3.
• Exit.

Calculation Program

Another program, implementing Dodd's calculator example:

The problem is to multiply 17 by 18, to multiply 19 by 20, to add the results of these two multiplications together and to divide by 2. The program is:

Code

Words 1 - 10 are the working space (or memory).

17 in word 1
18 in word 2
19 in word 3
20 in word 4
2 in word 5

Words 11 - 1000 comprise the main store, i.e. where programs and constants go.

11: Z
12: A 1
13: M 2
14: R 6
15: Z
16: A 3
17: M 4
18: A 6
19: D 5
17: R 7
19: E

Implement a Formula with Values

Problem

z = x(x + y)/(x - (x/y))

Assuming x and y values stored at words 200 and 201.


11: Z
12: A 201
13: D 200
14: R 203
15: Z
16: A 200
17: S 203
18: R 203
19: Z
20: A 200
21: A 201
22: M 200
23: D 203
24: R 202
25: E

Additional Commands

To allow program flow control.


J n
K n
L n
M n (m)

• J n - Jump to position n and then proceed to n + 1 and so on.
• K n : Jump to position n if number in accumulator is positive or zero.
• L n : Jump to position n if number in accumulator is zero.
• M n (m) : address becomes n + C(m).

Income Tax Calculator


11: I 1
12: I 2
13: I 3
14: I 4
15: I 5
16: I 6
17: Z
18: A 5
19: S 6
20: S 1
21: K 27 - so if value in accumulator is negative go to 22, else 27
22: A 1 - Add back the 5000 (it's less than 5000)
23: M 3 - multiply the income by 0.2
24: R 6 - Store it in 6
25: 0 6 - Output balue in 6
26: J 15 - go back to 15 (next person)
27: M 4 - Multiply the excess by 0.4
28: A 2 - Add this to the amount of tax payable on the first 5000 (0.2 * 5000)
29: J 24 - Jump back to 24
5000
1000
0.2
0.4

Instruction Encoding (an ISA Level)

In these examples, instructions can be represented by 20 digits.

If we take an instruction, A 37 (6), the instruction can be written using the encoding that takes the form of an order part A, followed by the modification part 6, followed by the instruction part, 37.

If we use a 5-bit encoding for characters, e.g.


00000 blank
00001 1
00010 2
00011 3
00100 4
00101 5
00110 6
00111 7
01000 8
01001 9
01010 0
01011 ,
01100 .
01101 :
01110 (
01111 )
10000 /
10001 Z
10010 A
10011 S
10100 M
10101 D
10110 R
10111 E
11000 i
11001 o
11010 J
11011 K
11100 L
11101
11110
11111

Then A 37 (6) can be written as,

       
                    10010 00110 0000100101
                    A     (6)   37
                

So, 5 bits, 5 bits, 10 bits.

This is equivalent to an ISA.

Other Levels

We did not go into more detail about other levels, but in Dodd's examples, the lower hardware level(s) are built with transistors at the foundation level, grouped into AND and OR gates, Inverters and Flip-Flops. These are combined to make storage (registers), addition and subtraction units. Using a system clock, data can be moved and combined to create software at higher levels, i.e. the ISA outlined above.