RSS

SSEM Program Execution Complete

July 19th, 2023 • C++, Emulator, NuttXNo Comments »

Program Execution Complete

A while ago I put together an emulator for the Small Scale Experimental Machine (SSEM), also known as the Manchester Baby. This was a basic console application allowing a program written for the Manchester Baby to be run in a console application on a modern computer. As things turned out, I now spend most of my time working in either C or C++. This has left me with a piece of code that is difficult to maintain as I have to relearn Python every time I want to make any improvements.

Time to rewrite the application in C++.

SSEM Simulator

The simulator provides a number of features:

  • Assembler/compiler to take source files and generate the binary to be execution
  • Console interface to control the execution of the application
  • Simulated display of the registers and memory

More information about the Python version of the simulator can be found in this blog and on the Small Scale Experimental Machine web site with full source code available on GitHub.

Porting the Simulator

The aim of the initial port is to provide the same functionality of the original application with any changes necessary to provide additional robustness as we are undoubtedly going to be seeing pointers in the C++ port.

Where possible, the structure of the original Python code has been maintained to keep a 1:1 mapping with the original code and test suite. This will provide an easy way to validate the unit tests in the port against the original Python code. The original Python code was validated against David Sharps Java Simulator.

The long term aim of this port is to provide a way of running the application on a Raspberry Pi Pico connected to hardware which will emulate the original SSEM. The application on the Raspberry Pi Pico will target the NuttX RTOS. As we will see later, compiling and running on NuttX will present some interesting issues.

Initial Port

The first stage of the port is to reproduce the core functionality of the SSEM showing the application output in a console interface targeting C++ 17. The only real complication here is ensure the user interface and platform specific code are abstracted to keep as much functionality in common with a desktop and NuttX implementation as possible.

The original Python code and the C++ port can be found in the Manchester Baby GitHub repository. A quick check of the source code shows that the 1:1 mapping has been kept where possible. The only real significant difference between the two code bases is the separation of the unit tests from the class implementation. The Python code keeps the unit test code in the class definitions themselves, the C++ code implements the unit tests in their own files.

Memory Checks

The switch from Python to C++ brings a new danger, memory access issues and memory leaks.

One memory issue that we can address relatively easily is memory leaks. If we can abstract the core functionality into a self contained group of files then we can use valgrind to check for memory leaks. A small glitch with using valgrind is that the application is not available for Mac from the key repositories. There is an informal project on GitHub.

The issue of valgrind not running on the mach was resolved by putting together a Dockerfile containing common development tools. The memory check could then be run on the desktop using Docker.

Running the Emulator

The emulator can be run on both a desktop computer as well as a board running NuttX.

Run from the Desktop

Running the application on the desktop is the simplest way to test the emulator:

  • Open a command console and change to the Desktop directory in the repository
  • Build the emulator with the command make
  • Run the emulator with the command ./ssem_main

Run on NuttX

Running on NuttX is a little more complex as we need to build the application and the operating system and then deploy the binary to a board. The processes of adding the SSEM application to a Raspberry Pi PicoW board has already been documented in the article Adding a User Application to NuttX. The first step is to follow the steps in the article to add the SSEM basic applicatiom.

The next stage is to copy the contents of the NuttX directory over the application directory created in the above article. The code should then be rebuilt with the command make clean && make -j. The application can now be deployed to the board.

Now we have the OS and the application deployed to the Raspberry Pi (or your board of choice) we can connect a serial adapter to the board and press the enter key twice. This will bring up the NuttX shell. Typing help should show the ssem application deployed to the board. Simply execute this by entering the command ssem.

Application Output

In both cases the emulator should run the hfr989.ssem application (the source for this can be found in the SSEMApps folder in the repository). Both the desktop and the NuttX versions of the emulator will run the SSEM application and will show the start and end state of the SSEM on the console / serial port. The first output will show the SSEM application loaded into the store lines:

NuttShell (NSH) NuttX-10.4.0
nsh> ssem
                   00000000001111111111222222222233
                   01234567890123456789012345678901
   0: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
   1: 0x48020000 - 01001000000000100000000000000000 LDN 18           ; 16402
   2: 0xc8020000 - 11001000000000100000000000000000 LDN 19           ; 16403
   3: 0x28010000 - 00101000000000010000000000000000 SUB 20           ; 32788
   4: 0x00030000 - 00000000000000110000000000000000 CMP              ; 49152
   5: 0xa8040000 - 10101000000001000000000000000000 JPR 21           ; 8213
   6: 0x68010000 - 01101000000000010000000000000000 SUB 22           ; 32790
   7: 0x18060000 - 00011000000001100000000000000000 STO 24           ; 24600
   8: 0x68020000 - 01101000000000100000000000000000 LDN 22           ; 16406
   9: 0xe8010000 - 11101000000000010000000000000000 SUB 23           ; 32791
  10: 0x28060000 - 00101000000001100000000000000000 STO 20           ; 24596
  11: 0x28020000 - 00101000000000100000000000000000 LDN 20           ; 16404
  12: 0x68060000 - 01101000000001100000000000000000 STO 22           ; 24598
  13: 0x18020000 - 00011000000000100000000000000000 LDN 24           ; 16408
  14: 0x00030000 - 00000000000000110000000000000000 CMP              ; 49152
  15: 0x98000000 - 10011000000000000000000000000000 JMP 25           ; 25
  16: 0x48000000 - 01001000000000000000000000000000 JMP 18           ; 18
  17: 0x00070000 - 00000000000001110000000000000000 HALT             ; 57344
  18: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  19: 0xc43fffff - 11000100001111111111111111111111 HALT             ; -989
  20: 0x3bc00000 - 00111011110000000000000000000000 JMP 28           ; 988
  21: 0xbfffffff - 10111111111111111111111111111111 HALT             ; -3
  22: 0x243fffff - 00100100001111111111111111111111 HALT             ; -988
  23: 0x80000000 - 10000000000000000000000000000000 JMP 1            ; 1
  24: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  25: 0x08000000 - 00001000000000000000000000000000 JMP 16           ; 16
  26: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  27: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  28: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  29: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  30: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  31: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0

Reading from left to right, the above output shows the following:

  • Store line number (i.e. the memory address) 0:, 1: etc.
  • The hexadecimal representation of the store line contents.
  • Binary representation of the store line contents
  • Disassembled representation of the store line contents JMP 0 etc.
  • Decimal representation of the store line contents

It must be remembered when reading the above that the least significant bit is at the left of the word and the most significant bit is to the right. This is honoured with the hexadecimal and binary components of the above output. The decimal value to the right should be read in the usual way for a base 10 number.

After a short time the contents of the store lines at the end of the run will be displayed:

Program execution complete.
                   00000000001111111111222222222233
                   01234567890123456789012345678901
   0: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
   1: 0x48020000 - 01001000000000100000000000000000 LDN 18           ; 16402
   2: 0xc8020000 - 11001000000000100000000000000000 LDN 19           ; 16403
   3: 0x28010000 - 00101000000000010000000000000000 SUB 20           ; 32788
   4: 0x00030000 - 00000000000000110000000000000000 CMP              ; 49152
   5: 0xa8040000 - 10101000000001000000000000000000 JPR 21           ; 8213
   6: 0x68010000 - 01101000000000010000000000000000 SUB 22           ; 32790
   7: 0x18060000 - 00011000000001100000000000000000 STO 24           ; 24600
   8: 0x68020000 - 01101000000000100000000000000000 LDN 22           ; 16406
   9: 0xe8010000 - 11101000000000010000000000000000 SUB 23           ; 32791
  10: 0x28060000 - 00101000000001100000000000000000 STO 20           ; 24596
  11: 0x28020000 - 00101000000000100000000000000000 LDN 20           ; 16404
  12: 0x68060000 - 01101000000001100000000000000000 STO 22           ; 24598
  13: 0x18020000 - 00011000000000100000000000000000 LDN 24           ; 16408
  14: 0x00030000 - 00000000000000110000000000000000 CMP              ; 49152
  15: 0x98000000 - 10011000000000000000000000000000 JMP 25           ; 25
  16: 0x48000000 - 01001000000000000000000000000000 JMP 18           ; 18
  17: 0x00070000 - 00000000000001110000000000000000 HALT             ; 57344
  18: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  19: 0xc43fffff - 11000100001111111111111111111111 HALT             ; -989
  20: 0x54000000 - 01010100000000000000000000000000 JMP 10           ; 42
  21: 0xbfffffff - 10111111111111111111111111111111 HALT             ; -3
  22: 0x6bffffff - 01101011111111111111111111111111 HALT             ; -42
  23: 0x80000000 - 10000000000000000000000000000000 JMP 1            ; 1
  24: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  25: 0x08000000 - 00001000000000000000000000000000 JMP 16           ; 16
  26: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  27: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  28: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  29: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  30: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
  31: 0x00000000 - 00000000000000000000000000000000 JMP 0            ; 0
Executed 21387 instructions in 30000000 nanoseconds

The original SSEM ran at about 700 instructions per second, modern PCs and even RP2040 processors are running the application much faster.

Conclusion

Even small boards (such as the Raspberry Pi Pico) running relatively low power processors can now emulate the Manchester Baby running application intended for the SSEM many times faster that the original hardware. The hfr989.ssem application would have run in about 30 seconds in 1948, today we can run this in an emulator in less that 30ms.

Python Emulator

June 10th, 2023 • Emulator, PythonNo Comments »

The Manchester Small Scale Experimental Machine (SSEM) or Manchester Baby as it became known, was the first computer capable of executing a stored program. The Baby was meant as a proving ground for the early computer technology having only 32 words of memory and a small instruction set.

A replica of the original Manchester Baby is currently on show in the Museum of Science and Industry in Castlefield, Manchester.

SSEM Replica

SSEM Replica at the Museum of Science and Industry, Manchester

As you can see, it is a large machine weighing in at over 1 ton (that's imperial, not metric, hence the spelling).

Manchester Baby Architecture

A full breakdown on the Manchester Baby's architecture can be found in the Wikipedia article above as well as several PDFs, all of which can be found online. The following is meant as a brief overview to present some background to the Python code that will be discussed later.

Storage Lines

Baby used 32-bit words with numbers represented in twos complement form. The words were stored in store lines with the least significant bit (LSB) first (to the left of the word). This is the reverse of most modern computer architectures where the LSB is held in the right most position.

The storage lines are equivalent to memory in modern computers. Each storage line contains a 32-bit value and the value could represent an instruction or data. When used as an instruction, the storage line is interpreted as follows:

Bits Description
0-5 Storage line number to be operated on
6-12 Not used
13-15 Opcode
16-31 Not used

As already noted, when the storage line is interpreted as data then the storage line contains a 32-bit number stored in twos complement form with the LSB to the left and the most significant bit (MSB) to the right.

This mixing of data and program in the same memory is known as von Neumann architecture named after John von Neumann. For those who are interested, the memory architecture where program and data are stored in separate storage areas is known as a Harvard architecture.

SSEM Instruction Set

Baby used three bits for the instruction opcode, bits 13, 14 and 15 in each 32 bit word. This gave a maximum of 8 possible instructions. In fact, only seven were implemented.

Binary Code Mnemonic Description
000 JMP S Jump to the address obtained from memory address S (absolute jump)
100 JRP S Add the value in store line S to the program counter (relative jump)
010 LDN S Load the accumulator with the negated value in store line S
110 STO S Store the accumulator into store line S
001 or 101 SUB S Subtract the contents of store line S from the accumulator
011 CMP If the accumulator is negative then add 1 to the program counter (i.e. skip the next instruction)
111 STOP Stop the program

When reading the above table it is important to remember that the LSB is to the left.

Registers

Baby had three storage areas within the CPU:

  1. Current Instruction (CI)
  2. Present Instruction (PI)
  3. Accumulator

The current instruction is the modern day equivalent of the program counter. This contains the address of the instruction currently executing. CI is incremented before the instruction is fetched from memory. At startup, CI is loaded with the value 0. This means that the first instruction fetched from memory for execution is the instruction in storage line 1.

The present instruction (PI) is the actual instruction that is currently being executed.

As with modern architecture, the accumulator is used as a working store containing the results of any calculations.

Python Emulator

A small Python application has been developed in order to verify my understanding of the architecture of the Manchester Baby. The application is a console application with the following brief:

  1. Read a program from a file and setup the store lines
  2. Display the store lines and registers before the program starts
  3. Execute the program displaying the instructions as they are executed
  4. Display the store lines and registers at the end of the program run

The application was broken down into four distinct parts:

  1. Register.py - implement a class containing a value in a register or storage line
  2. StoreLines.py - Number of store lines containing the application and data
  3. CPU.py - Implement the logic of the CPU
  4. ManchesterBaby.py - Main program logic, reading a program from file and executing the program

The source code for the above along with several samples and test programs can be fount on Github.

Register.py

A register is defined as a 32-bit value. The Register class stores the value and has some logic for checking that the value passed does not exceed the value permitted for a 32-bit value. Note that no other checks or interpretation of the value is made.

StoreLines.py

StoreLines holds a number of Registers, the default when created is 32 registers as this maps on to the number of store lines in the original Manchester Baby. It is possible to have a larger number of store lines.

CPU.py

The CPU class executes the application held in the store lines. It is also responsible for displaying the state of the CPU and the instructions being executed.

ManchesterBaby.py

The main program file contains an assembler (a very primitive one with little error checking) for the Baby’s instruction set. It allows a file to be read and the store lines setup and finally instructs the CPU to execute the program.

SSEM Assembler Files

The assembler provided in the ManchesterBaby.py file is primitive and provides little error checking. It is still useful for loading applications into the store lines ready for execution. The file format is best explained by examining a sample file:


--
-- Test the Load and subtract functions.
--
-- At the end of the program execution the accumulator should hold the value 15.
--
00: NUM 0
01: LDN 20 -- Load accumulator with the contents of line 20 (-A)
02: SUB 21 -- Subtract the contents of line 21 from the accumulator (-A - B)
03: STO 22 -- Store the result in line 22
04: LDN 22 -- Load accumulator (negated) with line 22 (-1 * (-A - B))
05: STOP -- End of the program.
20: NUM 10 -- A
21: NUM 5 -- B
22: NUM 0 -- Result

Two minus signs indicate an inline comment. Everything following is ignored.

An instruction line has the following form:

Store line number: Instruction Operand

The store line number is the location in the Store that will be used hold the instruction or data.

Instruction is the mnemonic for the instruction. The some of the instructions have synonyms:

Mnemonic Synonyms
JRP JPR, JMR
CMP SKN
STOP HLT, STP

As well as instructions a number may also be given using the NUM mnemonic.

All of the mnemonics requiring a store number (all except STOP and CMP) read the Operand field as the store line number. The NUM mnemonic stores the Operand in the store line as is.

Testing

Testing the application was going to be tricky without a reference. Part of the reason for developing the Python implementation was to check my understanding of the operation of the SSEM. Luckily, David Sharp has developed an emulator written in Java. I can use this to check the results of the Python code.

The original test program run on the Manchester Baby was a calculation of factors. This was used as it would stress the machine. This same application can be found in several online samples and will be used as the test application. The program is as follows:


--
-- Tom Kilburns Highest Common Factor for 989
--
01: LDN 18
02: LDN 19
03: SUB 20
04: CMP
05: JRP 21
06: SUB 22
07: STO 24
08: LDN 22
09: SUB 23
10: STO 20
11: LDN 20
12: STO 22
13: LDN 24
14: CMP
15: JMP 25
16: JMP 18
17: STOP
18: NUM 0
19: NUM -989
20: NUM 988
21: NUM -3
22: NUM -988
23: NUM 1
24: NUM 0
25: NUM 16

Running on the Java Emulator

Executing the above code in David Sharps emulator gives the following output on the storage tube:

Display Tube Output

Display Tube Output

and disassembler view:

Disassembled Program

Disassembled Program

And running on the Python version of the emulator results in the following output in the console:

Python Output

Python Output

Examination of the output shows that the applications have resulted in the same output. Note that the slight variation in the final output of the Python code is due to the way in which numbers are extracted from the registers. Examination of the bit patterns in the store lines shows that the Java and Python emulators have resulted in the same values.

Conclusion

The Baby presented an ideal way to start to examine computer architecture due to its prmitive nature. The small storage space and simple instruction set allowed emulation in only a few lines of code.