The final designThe final designHere’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. 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 actionHere’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 Mon Jul 6 15:42:43 BST 2015 |
Word Matcher
New:
ARM Cortex-M0 floating-point library in 1 kbyte;
Pound Shop BASIC;
Logic Tutor;
The Goom Strikes Bach
Qxw is a free (GPL) crossword construction program.
Answer treatments, circular and hex grids, jumbled entries, more besides.
Release 20140331 for both Linux and Windows.
More...
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–15.
All trademarks used are hereby acknowledged. |