Ball Computer Blog: February 2005

Understanding the diagrams

Any post whose title begins with "[Image]" is a bcd circuit diagram. Each box in the diagram represents a functional unit of a design, just like an IC in an electronic circuit diagram. I've color-coded them by type, and each type has different attributes and displays different data during simulation. The values shown in most images will be the default values, unless otherwise noted [for example, if I say that I'm showing a simulation in progress].

Basic Cells

Each basic cell [always outlined in blue] is made up of one or more of the fundamental gates that make up the computer, described in the introduction and in this post. All gates in a single basic cell are considered to share a single axis, so they'll all always be in the same state [0 or 1]. The state is displayed both in the position of the pink arms and by the large digit displayed at the right side of the gate.

Terminal Cells

Each terminal cell [always outlined in purple] represents a magical piece of machinery that I haven't designed yet. There should be very few of these in the design, and most of them will go away when I hook all the components together. Generally they're just dumb sources or sinks of balls [things that spit out balls or make them vanish], but I've also got special ones that spit out balls on demand [when tugged on via a pulley]. I have ideas for how they will work in physical form, but it's not relevant to the design, so I'll just deal with that during Step 5.

Container Cells

Each container cell [always outlined in yellow] represents a composite cell made up of other components. It's just my way of reusing blocks of logic. I will generally be uploading diagrams as clickable image maps, so that you can click on a container cell and see the design that it represents.

Here's another view of a container cell. In this image I've turned on "full-depth" drawing, so you can see the cell's interior logic drawn on top of its normal image. I generally keep this turned off to remove the clutter [and to speed up the designs that are big enough to matter], but it can come in handy during simulation [or just to show off how friggin' huge some of my designs are].

Ports

Ports and connections are the means by which cells are connected. They can represent attachment points for the tubes that will carry balls around [the red and blue ports, for inputs and outputs respectively] and for cords that connect pulleys [the yellow and green ports, for single-cord and double-cord pulleys, respectively]. The ports show up both as small boxes on cells and as larger boxes in the internal views of container cells.

Connections

Connections represent either tubes through which balls roll or cords attached to pulleys. Both are shown in bcd as straight off-white lines [yellow if they've been selected]. Connections currently default to having no wire delays [balls flow through them in zero time]; I'll probably change that to one gate delay per connection later on. When a connection has delays [i.e. is slow, such as a spiral tube that would take a ball a while to roll through], you'll see a rectangular box containing digits which are either '0' or '1'. Each '1' represents a ball. As the simulation clocks, the '1's shift from left to right through the box, and when they run off the end, the ball comes out of the connection into its output port.

Sometimes it's useful to hide connections. On designs with quite a few connections, it's often really hard to see one particular line on which you're trying to focus. For these occasions, I will generally "stub out" the offending connections. Here's what the stubs look like:

Note that connections turn yellow when selected, and may be drawn either on top of or beneath ports and cells.

Now that you understand all that, take a look at this diagram, which is a state machine that I built to test my 8-byte register file [the lowest byte of which always reads as 0].

How to get state uphill

"But," I hear you thinking, "Gravity-driven balls are all very well and good for calculation, but at some point you're going to have to bring the results back uphill for storage." Yes, that's true, but I've got it all figured out. I'm going to do it with ~~mirrors~~ pulleys.

In fact, I may even use several kinds of pulleys.

In the traditional pulley, two wheels are forced to move in lock-step by a loop of cord that goes completely around both of them.

We can make a similar pulley system that has pretty much the same behavior by using two rods, and connecting the ends of each to the corresponding ends of the other with 2 separate strings. It doesn't have quite the range of motion of the traditional pulley, but I expect that it'll be enough for my gates, which require only 60° of rotation.

However, if we remove one of the strings, we get more interesting behavior. For example, in the below diagram, the lower pulley can tip the upper one to the right by tipping to the right itself [thus pulling on the cord], but can't force it to tip to the left.

Likewise, the upper can tip the lower to the left, but not to the right.

In bcd, I allow pulley connections that represent either double-corded pulleys or one of the two single-corded possibilities. However, rather than think of them as left-connected or right-connected pulleys, I describe them in terms of their actions in relationship to the gates to which they are connected. That is, when do they send a signal [tug on a cord], and what do they do when they receive a tug?

The three types of pulleys are therefore:

S or SOSROR [Send On Set, Reset On Receive]

R or SORSOR [Send On Reset, Set On Receive]

D or DOUBLE [Send On Toggle, Toggle On Receive]

Obviously one can't connect a D pulley to an S or R pulley, but an S can connect to either an S or R, and vice-versa.

Next

How I'm doing it

Step 1 was to prove to myself that it was all possible.

Sure, I know that any digital computer can be built from the simplest gates [with some restrictions--I'm being approximate here]. That doesn't mean that I personally can come up with a reasonable design in finite time. As it turned out, this became one of the many design projects that I would pick up now and then, think about for a couple of months, and then put down for a couple more. I would frequently decide, "But what if, instead, I optimize for {ease of opcode decode, size of instruction, quantity of routing logic, etc.}?" and start from scratch again.
One day, after about 4 years of this, I decided, "There are a lot of ways to do this. I should just pick one". The architecture and instruction set were done one week and 30 pages of notes later.

At this point, the project had gotten further than any of my other design projects ever had, so I decided to proceed to:

Step 2, in which I write a CAD tool, which I call Ball Computer Designer [bcd for short], to enable me to test out designs. Sure, I could have gone straight to physical construction, but as a software engineer [and someone who's helped tape out chips] I feel strongly that the best way to experiment is in simulation. Plus, who's going to offer me funding to build the sculpture, and a place to put it, without some proof that I know what I'm talking about? OK, so it's also possible that I could have adapted an existing CAD or simulation framework from electronic to ball logic, saving myself a whole heap of coding, but where would be the fun in that?

Now, two additional years later, I now find myself the proud owner of 15000+ lines of C++ and 200+ lines of feature requests and bug descriptions. However, the tool is now Good Enough to start using, and so I proceed to:

Step 3, in which I will design and test the actual gate-level logic of all components of the CPU.

So far I've been quite pleased with how easy it is to put the components together. My first attempt was a 4-bit proof-of-concept ALU, which could add, subtract, and, or, and xor [no overflow/negative/zero/carry checks in or out yet]. After that, I decided to go straight to full-scale components, and I've done a few of them in as many days. That's days of actual work on the project, unfortunately, not calendar days. I only get to work on this in my Copious Spare Time™.

However, that being said, I've decided to start sharing what I've got, and hope to be updating this blog at least once every two weeks. I'll be posting reports on my progress along with images taken from bcd. They're not screen shots, since most of the designs don't fit on one screen. Also, because the GUI library I'm using doesn't support writing images to files, I'm using a different one to write out the PNGs for this blog.

After much struggling to try to get the PNGs to look good, I've determined that FLTK uses Xft for fonts, and GD uses FreeType fonts, and never the twain shall meet. So the PNGs are a bit uglier than what I'm actually seeing at home; I'm sorry about that. If you know an easy way to fix it, please do let me know.

For future reference, Step 4 is writing test software to verify the design, Step 5 is prototyping and testing the physical gate designs and the structure needed to hold them all in place, Step 6 is to produce a total cost and time estimate for construction, and Step 7 is to find someone who wants one built. I think it could be both

a terrific way to teach kids how computers work.
wicked cool.

Have you ever seen any of the many kinetic sculptures that involve balls rolling down tracks? Here is an example. I've loved them since I was a child, when I first saw the one in the Port Authority building in New York.

These sculptures vary tremendously; some have all kinds of different structures which toss the ball around, make noises, or are themselves tossed around by the ball. Others are made of very few components, but take each ball through a quite complex set of paths.

In many of them, there is a deterministic decision-making structure. As each ball goes through it, it is directed to one of two output paths. Specifically, the one that the previous ball didn't take. The structure toggles back and forth, and its outputs alternate output paths. It looks a bit like this:

The ball enters at the top, is guided to one side, flips the trigonal gate to that side, and exits at the bottom. The next ball finds the gate flipped the other way, and so the reverse happens.

Being a computer geek, I can't help looking at that gate as one bit of state, and noting that if one links several of them together, such that the left-hand output of each feeds into the next, one creates what looks suspiciously like a binary counter. Furthermore, if one is allowed to drop balls into any of the gates directly, rather than just sending them in the top one, one can do twos-complement addition and subtraction!

There is a complication, of course, in that we can't read the state out without also writing to it. However, we can alter this "toggle" gate a bit by breaking off its two lower arms, and then we can read the state out [noting which way the output ball went], but not write to it. Also, we can break off only one of the two lower arms, and then we have a gate that a ball can flip one way, but not the other--just like the set or reset functionality of an electronic flip-flop.

OK, now we have gates that we can toggle, query, set, and reset [I call them t, q, s, and r gates]--but not all at the same time. That is, each has only a single function, so you can toggle a bit but not read it, or read a bit but not set it in the first place. We can fix this by connecting several of these gates together, by attaching them all to a common axle, forcing them all to move in sync with each other. Tada! We now have the basic building block of digital logic...and more importantly, a tremendous time-sink for me.

Why is it a time-sink? Because, having figured out how to make these gates, I decided to build a ball sculpture that is simultaneously an entire computer [OK, an 8-bit CPU] out of them.

Next