... or 65,536 ants?
If you were plowing a field, which would you rather use? Two strong oxen or 1024 chickens?The Connection Machine was an 80's era supercomputer with an unusual architecture. Their processing element (PE) was a 1-bit ALU, hooked up to a few thousand bits of local RAM. A full-sized CM had 65,536 PEs.
-- Seymour Cray
This overview paper quickly makes the basic point of the thing clear. It had a lot of processing power:
The 1-bit PE's were brutally simple and ran at a quite modest 4 MHz. Code from a control unit sends out the same opcode to every single PE. Each one operates from and to their own local storage. This style of architecture, Single Instruction Multiple Data (SIMD), does exist today, but it's hidden away inside modern GPUs and CPUs.
What's it like to program a 1-bit SIMD machine? Well, every operation is done bit-by-bit. So to do a 3 bit add of A and B, you might do:
load A[0] load B[0] add, write result to C[0] load A[1] load B[1] add with carry, write result to C[1] load A[2] load B[2] add with carry, write result to C[2]
and so on. Executing a 32-bit multiply in this way takes a whopping 3000 instructions. And it's all software -- even worse, it's 1-bit software. In the CM-1 there is no hardware for addition, subtraction or multiplication, let alone division. Even so, Connection Machines were marketed as numerical supercomputers, taking on machines such as the Cray which had huge amounts of custom arithmetic hardware. Unsurprisingly the CM-2 and its successors added floating-point accelerators in a blended approach. (I'm sure this made perfect business sense at the time, but of course it didn't end well. It's fun to imagine them instead pursuing wider and wider parallelism, e.g. a CM-2 with 1 million PEs!)
I'm quite interested in the 1-bit idea, and there don't seem to be many SIMD homebrew CPUs. So here are some notes on programming them, and what's possible in FPGAs. I'm doing the math for the (very cheap) Xilinx Spartan 6 XC6LX9 in the Dazzler, and for a newer Spartan 7 XC7S50 available as a $129 development board from Digilent.
The machine isn't hard to think about. In fact it has a kind of radical simplicity that makes the J1 look like a Cadillac. Picture the PE's (here 128) across the page, each with its own column of 1-bit storage.
At boot, memory contains a pattern like this so that each PE knows what its address is. Each operation can read or write one entire "row" of storage. For example, after running a program to compute the square of each PE's own address, memory would look like this:
How many PEs will fit in an FPGA? A lot. FPGAs have large built-in RAMs, and they can all be run in parallel. Adding up all the available RAM port bits in gives about 2000 PEs for the Spartan 6, and 10,000 for the Spartan 7. Each has 256 bits of RAM per PE. Both have enough logic resources to implement a really tiny 1-bit ALU:
I've done a trial synthesis for the smaller FPGA, and it does all fit. I'm hoping that the very simple setup - it's really just a RAM connected to a single LUT - will result in a design that can run at a high clock speed, maybe close to the 300MHz limit of the FPGA's RAM.
Assuming this optimistic case, how fast will it be? Well, adding two 32-bit numbers will take 96 clocks, just like the CM-1. So the Spartan 6 will execute 6 billion 32-bit additions per second. Not bad.
But arithmetic isn't a particularly good fit for such a versatile machine. Something a bit more unusual like running Conway's Life is a better match for its 1-bit flexibility. I estimate the evaluation code for a life cell will take about 150 cycles, so the Spartan 6 will compute 2000/150 = 13 cells per clock, or 4 billion cells per second. This is uselessly fast; if all of local RAM were used as the 2000x256 Life grid, it would run at 7 thousand generations per second.
Generating random numbers using an LFSR is another good application. My back-of-envelope calculation is that each PE would compute 1 bit every 10 clocks, so 60 Gbit/s of random digits.
The larger Spartan 7 would run at around 5X these rates. Not bad for a machine that is all software!
And yes, I'm skipping a whole lot of detail. There needs to be an actual control CPU that runs the algorithm proper. And there needs to be some way for these PEs to talk to the outside world. More in a future newsletter.
Thanks for reading.