(Some of) Colossus in an FPGA

As described well elsewhere, for example in the Wikipedia article, Colossus was a special-purpose computer, built by Tommy Flowers at Bletchley Park around 1944, as part of the war-time work to break the encryption of intercepted German transmissions. It's a very important, very early milestone in the history of electronic computing.

Colossus counted the number of times some chosen condition was true for the letters of the intercepted message, usually after combining the letters with an electronically-synthesised stream of cipher-key material. An unusually high or low count was, broadly speaking, an indication that one piece of the code-breaking process had been successful.

A previous post described in more detail a typical task for which Colossus was used, and gave a worked example in Python.

A Field Programmable Gate Array is often described as 'programmable hardware', in that it is a chip consisting of a large connected array of small but flexible logic components, which can be configured to perform the desired task. The configuration is done in a high-level language such as VHDL. FPGAs typically also contain a sprinkling of special-purpose elements such as clock circuitry, RAM, arithmetic, I/O, etc. An FPGA is a 'half-way house' between a general purpose CPU, which is easy to program but slow at run-time for some tasks, and a fully custom chip, which can be extremely quick at run-time but whose design is difficult and time-consuming. I've been curious about FPGAs for a while and looking for an excuse to learn the basics about them.

The goal for this project was to implement enough of Colossus on an FPGA to be able to replicate the 'Chi wheel setting' Python output from the previous post. I expected this to be a good-sized project for learning: achievable but not trivial.

The features on the above list will give the core Colossus functionality, but the design will lack several features of the real thing. For example, I have not implemented the 'multiple test' (aka 'remembering') facility; I do not handle 'limitations' or 'spanning'; there is no palette of 'triggers' for the wheel patterns; there is no patch panel; and no doubt there are other differences. But this feature set does implement enough of Colossus to replicate the wheel-setting task.

The input and output components of Colossus necessarily have a different embodiment in the FPGA:

One interesting aspect of the real Colossus was the feature whereby the counts resulting from one run of the tape are latched in relays for printing so the next loop of the tape can do useful work [53G(c)]. This makes sense in the context of the whole machine being clocked from the tape, and the fact that the tape ran continuously.

I was keen to capture some of the essence of this, and perhaps even extend it: every processing stage should be working whenever it can. The approach I took was vaguely motivated by a quick read-through of the book Communicating Sequential Processes (freely available online), but not in any sense formally.

Consider the different pieces of state as 'slots' which can hold data. A worker in some component processes the contents of one slot, placing the result in another slot. The collection of workers is controlled by a set of 'schedulers', which make sure there are no conflicts over which process is working with which slot.

From this perspective, the processing required to start with a work-unit (a pair of candidate settings of the Chi(3) and Chi(4) wheels) and produce the corresponding result (printer record consisting of stepping counts and the number of times that 'q(3)+q(4)==0') is shown below. In the diagram,

• Data-slots are green rounded rectangles
• Workers are grey rectangles
• Schedulers are orange rectangles.

The left branch does the bulk of the work: the actual tape run and counting. The right branch just copies the settings in case the count turns out to be promising and we need to print the resulting record.

Note that data which are constant over a particular long run (for example, the tape contents and the starting wheel patterns) do not feature in the data-flow diagram.

This gives us a very different view of the system to the previous diagram, although most of the same components are represented. This view concentrates on the logical flow between data-slots, rather than the control signals which achieve a particular worker's task. One logical worker can trigger activity in more than one physical component (in particular the 'run tape once' worker).

There is also a component whose job is to feed work-units in at the top, and another one whose job is to collect the 'printer records' from the bottom.

An advantage of FPGAs, for suitable problems, is the ability to do lots of things in parallel. A 'long run' is a good candidate for this, requiring 754 runs through the tape in the case of our Chi(3)/Chi(4) run, with no communication required between these computations.

The design therefore consists of multiple 'body' components, with a 'head' at the top to distribute work units to the bodies, and a 'tail' at the bottom to collate the results from the bodies. It turned out that the design was using c.2/3 of the resources on my XuLA board with two bodies, so the parallelism was limited, but the principle was shown to be sound.

The overall data-flow, combining a head, two bodies, and a tail, is thus as follows. The orange 'body pipeline' box below stands for the above figure.

The 'initiate-run' slot is a dummy; a commmand from the RPi (see below) sets this to 'available' to set the whole run off.

The 'iterate/source' scheduler repeatedly asks the 'stepping generator' worker for the 'next' value, and has a protocol for detecting when the iteration is done. The 'distribute' and 'collect/sink' schedulers choose among a collection (here just two) of potential consumers or producers, which is done by polling. These schedulers have 'indexed' workers, to control which consumer or producer from the collection is to act.

To reduce demand for physical pins, the 'command' and 'data' buses are multiplexed onto one 8-bit bus, with a separate bit to indicate whether the RPi is currently presenting a command or data value. The physical connection between the RPi and the XuLA board is thus over two 8-bit 'ports' with a few extra control lines. An alternative (perhaps better in retrospect) would have been to use some kind of serial port.

It took some effort to set up, but the approach I took was to build a framework which allowed the unit testing to be done in Python. This effort paid off, and it was productive to be able to write and drive tests from the flexible and familiar pytest environment. The simulated design has a simple 'command line' (REPL) implemented in VHDL, and then Python code which talks to the REPL over a Unix named pipe (FIFO).

As well as the benefits of the pytest framework, I could capture a spool of commands sent to the REPL, and replay them to the GUI logic-analyzer / simulator, to track down bugs.

Finally, the real benefit came when the time came to actually synthesise the design to the real FPGA. I wrote a small piece of C++ code which behaved like the simulation REPL, but which truly drove the RPi's GPIO pins and read the FPGA's response from other GPIO pins. Then, by making the Python unit test code talk to this client rather than the simulation, I could use the self-same unit tests against the real FPGA. Furthermore, the same system could be used to perform the actual 'long run' task, and in fact the first 'long run' was done on the actual FPGA (not in simulation), and it behaved correctly first time.

Various pieces of state in the system have a start-up value determined by an initialization clause in their VHDL definition. The alternative is to have dedicated 'reset' functionality throughout. From a brief bit of reading, it seems that in fact the 'reset' approach is recommended: relying on initialization for signals is sometimes tool- or part-specific which means it's difficult to port the design to, say, ASIC technology. From my direct experience, it made unit testing more fiddly because the FPGA Colossus carried state from one unit test to the next, which meant each test had to ensure all state it relied on was set correctly.

There is more than one way to set Colossus up to count 'q(3)+q(4)==0' on delta-de-Chi:

• Z, the intercepted encrypted message, can be punched 'as is' onto the tape. Likewise, the known Chi patterns can be used 'as is' to configure the Chi patterns within Colossus. Then the Q selector is configured to calculate 'Q = delta-Z + delta-Chi'. This is the approach taken in the above work.
• Delta-Z can be pre-computed and punched onto the tape. What Colossus thinks of as 'Z' is therefore truly 'delta-Z'. Likewise, we can compute the (cyclic) delta of the true known Chi-wheel patterns, and configure these as the Chi patterns within Colossus. What Colossus thinks of as 'Chi' is therefore truly 'delta-Chi', and we configure 'Q = Z + Chi'.
• Or indeed a mixture of the above.

Note that existence of any 'delta' operation in the Q-Selector means that first letter is not counted. GRT describes a test which should give a count equal to the tape length; then says 'It is better to count /s in delta-Z + delta-Chi which checks Colossus delta-ing simultaneously; this of course reduces the score by 1' [23K(c), emphasis added]. This is why a q_delta signal is sent from the Q-Selector to the Movement Controller.

Suppose we have fully broken the key for a message, and so know the Chi, Psi, and Mu wheels' patterns and settings. By specifying 'Q = Z + Chi + Psi', we can recover the plain text of an encrypted message by snooping the 'Q' bus after each movement. This is one of the unit tests. Note that the real Colossus had no such 'snoop' facility, and Bletchley Park instead had separate machines for decryption.

The following observation on 'long runs' occurred to me; I don't know whether it is new or common knowledge:

All wheels have pairwise co-prime lengths, and therefore it should be the case that configuring 'fast' stepping for the two wheels involved in the 'long run' still explores all the possibilities, but prints the results in a different order.

The specimen runs given in GRT [section 23D, 'Annotated Exhibits', starting p.84] make use of the 'multiple testing' facility of the real Colossus, and so necessarily have one wheel stepping 'fast' and one 'slow'.

I added a unit test which configures the FPGA Colossus to perform the 'step both fast' long run, and so confirmed the predicted behaviour.

The duplication of the entire 'body' in this design is not the only way in which multiple Colossus instances could have been achieved. For instance, a single bedstead could have been used, feeding the Z stream to the multiple bodies. This would avoid needing one BRAM per body instance, at the cost of requiring extra synchronisation against the Z stream. It would perhaps even return to the original Colossus design of a continually-running tape.

Of course, the real Colossus's 'remembering' circuits achieved a speed-up by a factor of five.

The design currently takes the modest 12MHz clock on the XuLA board directly as the system clock. I did make a brief attempt at using the clock multiplier primitives — the resulting design seemed to meet timing, and passed all unit tests in simulation. However, it didn't work on the real FPGA. One thought is that it takes some time for the multiplied clock to become stable, and my laziness at not implementing proper 'reset' functionality was coming back to haunt me. Or perhaps the higher clock speed required more current than could be drawn over USB.

This would be a big job, and might involve more research, as the information in GRT is not completely explicit on every point.

It would be interesting to read "A technical description of COLOSSUS I" (D. C. Horwood, August 1973) as held in the UK's National Archive, and see how the original designers approached some of the implementation problems.