The final design

The final design

Here’s an overview of the computer, showing its various functional blocks. As you can see, the display shows ‘00059’. The computer is running an elegant program, due to Michael Fryers, which calculates primes.

block diagram

How does the program work?

The program tests the odd numbers in sequence for primality, 2 being treated as a special case. Each candidate prime p is tested for divisibility by a sequence of trial divisors q, which run through the odd numbers from 3 up to p-2. The division is performed by repeated subtraction using one of the adder inputs as a temporary register to hold the values p-q, p-3q, p-5q and so on. The first step of the repeated subtraction algorithm doubles as the test for when the trial divisor q has reached p.

Here’s a commented disassembly of the program. Don’t forget (a) that execution starts from register 1 (register 0 is the display); (b) that because there is one branch delay slot, the instruction immediately following a branch is executed before the branch is actually taken; and (c) that arithmetic is ones’ complement. The diligent student will want to verify that the result of the addition implicit in line 10 always represents zero as ‘plus zero’ (i.e. the all-zeros value), rather than ‘minus zero’ (the all-ones value).

Reg  Hex  Disassembly

 1  001e  MOV R0 ,R30  ; set display to 2
 2  361f  MOV R54,R31  ; initialise mask register for sign bit test
 3  2021  MOV R32,R33  ; set candidate prime p=3
 4  3c22  MOV R60,R34  ; the trial divisor q is stored in the adder as its
                       ; negative: here it is initialised to -1, i.e. q=1
 5  3d23  MOV R61,R35  ; other summand=-2
 6  3c3d  MOV R60,R61  ; next trial divisor q=q+2
 7  3d20  MOV R61,R32  ; move p to adder summand input a, which holds remainder
 8  3924  MOV R57,R36  ; for the first time round the loop, set the target
                       ; for the branch if subtraction gives zero to 20: this
                       ; detects the case p==q, which means we have done all
                       ; the trial divisors and p is prime
 9  3725  MOV R55,R37  ; if subtraction result non-zero, target is 13
10  383d  MOV R56,R61  ; test a-q
11  3f38  MOV R63,R56  ; branch to selected target
12  3d3d  MOV R61,R61  ; a-=q
13  3d3d  MOV R61,R61  ; a-=q (continuing here if subtraction result not zero)
14  353d  MOV R53,R61  ; move a-q to and-not register to check sign
15  3926  MOV R57,R38  ; target is 9 if a-q positive (round subtraction loop
                       ; again)
16  3727  MOV R55,R39  ; else target is 5 (q does not divide p, so try next q)
17  3836  MOV R56,R54  ; test a-q AND 0x8000
18  3f38  MOV R63,R56  ; branch to selected target
19  3928  MOV R57,R40  ; reset target for other branch to 21 (a zero result
                       ; from the subtraction now indicates q properly
                       ; divides p and so p is composite)
20  0020  MOV R0 ,R32  ; p is prime: write it to the display
21  3d20  MOV R61,R32  ; move p to adder
22  3c1e  MOV R60,R30  ; other summand=2
23  3f29  MOV R63,R41  ; goto 4 to try new p
24  203d  MOV R32,R61  ; p+=2
25                     ; unused
26                     ; unused
27                     ; unused
28                     ; unused
29                     ; unused
30  0002               ; constant 2
31  7fff               ; constant mask for sign bit testing
32  0005               ; current candidate p
33  0003               ; constant 3
34  fffe               ; constant -1
35  fffd               ; constant -2
36  0014  20           ; branch target: trial divisor q equal to candidate p,
                       ; and hence prime found
37  000d  13           ; branch target: trial divisor q less than candidate p
38  0009   9           ; branch target: more subtractions to do
39  0005   5           ; branch target: next trial divisor q
40  0015  21           ; branch target: subtraction gave zero, so p composite
41  0004   4           ; branch target: next candidate p
42  fffc               ; constant -3

The access time of the register bank is approximately equal to the time for an electron to run from the bottom to the top and back. Since each register is six cells high, and there are 64 registers, the access time is approximately 2 times 6 times 64, or 768 generations. Two accesses are needed per instruction (one to read the instruction, and one for its register read), and there is a small overhead in decoding the instruction, so the instruction cycle time is set at 2304 generations. The computer ran for about 14 million generations to produce the picture above.

See the computer in action

Here’s an experimental demonstration of the Wireworld computer in action, calculating primes. Java required.

What are we going to do now?

Please feel free to reverse-engineer any parts of the design that we haven’t covered in detail: the binary-to-BCD converter should be quite a challenge. If you’re that dedicated, you shouldn’t have any difficulty working out the format of this zip file. If you let us know how you get on, then, given your permission, we’ll add your descriptions to this website with suitable credits.

Before you do that, you’ll probably want to play with Wireworld yourself for a bit. There are several programs available to let you do this: a web search for ‘wireworld automaton’ will find a few. You could try adding the name of your favourite operating system or programming language to the search terms. Golly has a pretty user interface and is very fast. Alternatively, you are welcome to try the following rather spartan programs: wirun.c and witopgm.c. The first is a program to process a Wireworld pattern for a given number of generations. On an 850 MHz Athlon it executes one generation for the computer design in about 3 ms, and the computer therefore runs at about one instruction every six seconds. The second program converts the text file format used by wirun.c into a portable grey map, which can easily be converted to other graphics formats. The -map option to pgmtoppm is useful for producing colour output - this is how the pictures on these pages were produced.

<Previous page  Wireworld index


This page most recently updated Sat Apr 19 11:38:37 BST 2014
Word Matcher

Options...
Type a pattern, e.g.
h???o
into the box and click ‘Go!’ to see a list of matching words. More...


Qxw screen
Qxw is a free (GPL) crossword construction program. Answer treatments, circular and hex grids, jumbled entries, more besides. New release 20140331 for both Linux and Windows. More...

Practical Signal Processing front cover
My book, ‘Practical Signal Processing’, is published by Cambridge University Press. You can order it directly from them, or via amazon.co.uk or amazon.com. Paperback edition now also available. Browse before you buy at Google Books. Wydanie polskie.

If you find this site useful or diverting, please consider a donation to NASS (a UK registered charity), to KickAS (in the US), or to a similar body in your own country.

Copyright ©2004–14.
All trademarks used are hereby acknowledged.