Ball Computer Blog

3D Printing Rocks

2010-02-23T19:02:00.000-08:00

I decided that, rather than do yet more simulation, I'd start trying to prototype my gates.

The simplest way to do this seemed to be designing them in some CAD tool and having a 3D print done. I spent a number of weekends going through Blender tutorials, only to figure out that it just wasn't the right tool for the job. It's much more aimed at making cool pictures and animations, and not so good for constraints like "all walls must be at least 2mm thick". After getting stumped there and working on other things for a while, some friends turned me on to OpenSCAD. I'd just like to give a big shout out to Clifford Wolf, the author--it's a great tool, and I had my first design in about 1 day of work. I tweaked it a bit more before I had the prints done, but still, it was really fast to work with.

Here are a couple of shots of the gate I printed; I got one side in transparent plastic so that I could see what was going on inside, but I got the rest in white because it was much cheaper. Big thanks to shapeways.com for getting me my parts in 9 days, upload-to-delivery, for half the price that I could have gotten it done in the U.S.

Here's the fully-assembled gate, lacking only the metal axle, a 3/8" D-profile steel shaft. The shaft's way bigger and heavier than I wanted, but apparently it's hard to find small, light shafts with that profile.

Here are the 3 parts laid out so that you can see inside. Those circles and doughnuts on the transparent gate are actually on the far side; they're alignment pegs and sockets, and the white one has them too. They're so that you can slap a whole stack of these gates together without worrying about binding on the axle.

I've already designed the next generation, about 2/3 the size and with a very different axle that I hope will reduce friction quite a bit. I also picked up some tungsten carbide bearings to replace the steel ones I started with--doubling gravity may be cheating, but if it works, I'm for it.

1.0 is ready to go!

2009-05-17T11:48:00.000-07:00

I've now completed the Ball Computer v1.0. Woot!

Check it out in all its nearly-incomprehensible glory!

Let's have a quick review of the steps to getting it built, so that you can understand how far along I am, and how much further I have to go. Here's the old version of the steps to getting it built. I'm going to update that, as plans have changed a little and I want to flesh out what I've done a bit more than I did the last time.

Prove it's possible by planning out the basic logic architecture.
Write the tool [BCD] needed for the design [ongoing, but it had to get good enough to use before starting step 3].
Design all the major components of the CPU, such as the ALU and RAM. Build a state machine that tests each solo component to my satisfaction.
Hook the components together with additional logic to implement the instructions. Write short tests that validate each individual instruction.This is what I've just completed.
Add a 3D interface to BCD so as to be able to show off what it might look like, do placement, and figure out how big it's going to be.
Prototype designs for all the physical gates.
Write a decent instruction test suite for real design verification. [I may see if I can outsource this or adapt an existing suite if there's anything close. Also, I'll have to improve BCD such that I can run a large suite efficiently via automation.]
Redesign everything for parallel operation [multiple balls in flight at a time, necessary for reasonable speed]. Here the test suite helps validate that nothing broke in the redesign.
Write a time+cost estimate for construction. The size estimate from the 3D model helps here.
Find someone who wants one and someone to pay for it.

I see that I keep adding steps ahead of me, and have managed to put off any physical prototyping a bit longer. That's a bit disturbing, but I'll keep an eye on it.

Multiply, Mac

2009-05-07T21:15:00.000-07:00

OK, a bit of debugging and test-code writing later, I now have functional MUL, SMUL, MAC, and SMAC instructions:

MUL 1111 1 dest srcB 0 0 srcA
SMUL 1111 1 dest srcB 1 0 srcA
MAC 1111 1 dest srcB 0 1 srcA
SMAC 1111 1 dest srcB 1 1 srcA

They all write their result's low byte back to the destination register at completion. This does take time, so it might not be a good idea for MAC/SMAC, but it was simplest to do them all the same way, and this is all going to have to be redone when I parallelize the cpu anyway.

There's currently no way to get at the top byte of the accumulator; that's going to be accessible through IO space, the one part of the machine as yet unimplemented. Most of the machinery for it is already there, though; it's sharing most of the memory access logic, state machines, and instruction decode apparatus.

Step 3 is dangerously close to complete.

Yes, I'm still alive

2009-05-03T21:52:00.001-07:00

I haven't got any new diagrams to show you, but I have actually done a little work on the machine since my last post oh-so-long ago.

In November I put in a long-needed randomizer, so that simulated gates get set to a random position at startup if not explicitly set to a value. This of course shook out a few bugs [generally of the "I completely forgot to hook that gate up" type], and it also pointed out some UI improvements that BCD needed in order to make it clear what was initialized to zero and what was just defaulting to zero.

Yesterday I dug back in to familiarize myself with the system, then did a bit of cleanup of the load immediate instruction's implementation.

Today I implemented the 4 multiply instructions [mul/mac/smul/smac], but have yet to begin debugging them. I wrote a quick test ROM for mul, and it failed, but I'm not going to start debugging tonight. That seems like a good place to start next time.

It's alive!

2007-01-15T18:15:00.000-08:00

As of this weekend, I've implemented:

Load Immediate
A basic disassembler
Euclid's algorithm in Ball Computer assembly code.

...and it ran!

Well, not first try, obviously. Hence the disassembler. But it ran.

That's all hand-assembled machine code, BTW, as I haven't yet figured out the assembler that A. wrote for me over a year ago. I guess I'll have reason to, now; I should write up a reasonable test suite for it, to make sure I haven't missed any corner cases. First I've got to learn enough Parsec to bring it up to date with the changes in machine code since I gave A. the instruction set documentation.

Still to be completed for Ball Computer 1.0 are the I/O instructions and MUL/MAC [or whatever I decide to implement there]. Currently the only thing off in I/O space is the multiplier, but there may eventually be some actual I/O [for displays, input of parameters, etc.], so I'm going to make it reasonably general.

When I say jump...

2006-07-03T18:46:00.000-07:00

After far more struggling than it should have taken, I've gotten all the jump and branch instructions in. What took so long was that I realized that I could make these instructions much more efficient than the ones I'd put in already...and that I could optimize many of the earlier ones in similar ways. However, since lots of the earlier logic is a bit snarled, I ended up breaking everything and having to back out half of my changes. So the new instructions are fast [and could be a bit faster], and the old instructions are waiting to be optimized. I'm not sure whether I'll do that yet; it may wait until I'm ready to do BC 2.0 [with parallel calculations instead of the current one-ball-at-a-time serialized ones].

Down:

addc
addci
add
addi
subc
subci
sub
subi
or
ori
xor
xori
and
andi
sh
shi
lbr
lba
sbr
sba
b
bc
bal
j
jc
jal

To Go:

lsbr
lsba
ssbr
ssba
li

The multiplier will be accessed via instructions such as [ls]sb[ar]: load/store special byte to [immediate address/register address]. It's essentially off in IO space, or in a coprocessor, if you will.

Hmm...I may get rid of the 'b' in all those load+store instructions; it's a bit silly on an 8-bit machine.

Memory

2006-06-25T17:12:00.000-07:00

I've now implemented and tested the 4 memory-access instructions:

lba - Load a byte from an immediate 8-bit address

sba - Store a byte to an immediate 8-bit address

lbr - Load a byte from an address that's the sum of the contents of a register and a 5-bit offset

sbr - Store a byte to an address that's the sum of the contents of a register and a 5-bit offset

The offset is currently unsigned, but I can see that it might be more useful as a signed value. I could easily sign-extend it in the memory address unit, but I haven't yet decided whether I should. There remains the question of whether it will ever get used at all, of course. Will programs that fit in 256 instructions actually feel the need for stack-pointer-relative local variables? We shall see.

Scripting tools

2006-06-11T21:14:00.000-07:00

I've not done any more logic design since my last post, but my tools have gotten a great upgrade. My tests are now completely self-verifying, and can be scripted [to a certain extent]. Bcd can now, under scripted control: load a design file, create a simulator, set values in it, run it for some number of cycles, and check the results. Script files can include other script files, so I have one master test that runs each of my opcode tests in sequence without having to reload the design. This is a big time-saver, as loading the CPU design takes about 30 seconds, but creating, running, and cleaning up the simulator takes only about a second.

I've also done most of the markup I mentioned last post, and therefore can set and test values by byte [by word for the ROM] instead of bit-by-bit. The values also show up in the GUI at the top level, so I don't have to drill down 3 levels deep to read out the registers. Here's what the ROM looks like. It's really got 256 words, but if I show only the first 32, it's easier to read. Plus I haven't had any need to show more than the first word so far, but I have high hopes of needing more some day ;'>.

Shifting the night away

2006-05-28T15:17:00.000-07:00

After making a small change which could easily have killed all the instructions I'd gotten working so far [but didn't], I now have the shift instructions [immediate or register shift amount, left or right, logical or arithmetic] working.

I'm not sure which instructions I'll work on next. There's a bunch of design work that's going to have to be done for either the memory or PC stuff, and I want to see if I can possibly reuse the ALU state machines.

However, before I do that I want to add to the code that lets me load in tests and helps me visualize data within the simulator. Currently I have to enter tests bit-by-bit, and I'd like to be able to simplify my input files such that I can just input bytes. Similarly, I need to mark up my design files a bit in order to see more of what's going on inside the simulator. The code for that part's already in, but I should add a bunch of annotations to the XML source of the design to make use of it.

Further down the line, I'll be building on that to have self-verifying tests. I'm not sure I'll get that far before getting back to logic design, though.

Down:

addc
addci
add
addi
subc
subci
sub
subi
or
ori
xor
xori
and
andi
sh
shi

To Go:

lbr
lba
lsbr
lsba
sbr
sba
ssbr
ssba
b
bc
bal
jal
jmp
li

I'm back again.

2006-04-02T23:42:00.000-07:00

After another long hiatus, and moving back from Norway, I've started work again.

Today I got all of the other ALU instructions working, and put in a first pass at the shifter logic. I've found one bug in it so far, and I don't think I'm going to get through it tonight.

Down:

addc
addci
add
addi
subc
subci
sub
subi
or
ori
xor
xori
and
andi

To Go:

sh
shi
lbr
lba
lsbr
lsba
sbr
sba
ssbr
ssba
b
bc
bal
jal
jmp
li

I'm back!

2006-01-08T11:36:00.000-08:00

After spending a lot of time adding data-visualization tools to BCD, then moving to Norway and dropping the whole project for months, I've finally started work again. It generally went something like this: try the instruction, and see that it doesn't work. Find the logic error, but while fixing it, find that BCD malfunctions. Chase that misbehavior, but find that in adding debugging code, you've managed to invoke some little-used code path that turns out to have a crashing bug in it.

Ugh.

At any rate, I managed to fix my way back up that stack far enough to get all the instructions I've tried working [at least for trivial tests], and that feels like a good place to stop for the night.

Down:

addi
subi
addci
subci

To Go:

lots

First light!

2005-10-23T23:17:00.000-07:00

Two weeks ago, on the evening of Friday, October seventh, the Ball Computer executed its first full instruction [an "addi"]. Whee! That includes reading the program counter, fetching the instruction from ROM, reading a value from a register, adding a constant to it, dealing with the CCR, doing the register writeback, incrementing the PC, and getting ready to run the next instruction.

I was quite pleased to find that it only took a few hours of debugging to get it working, and that the errors were pretty minor: one place where I'd swapped bit 12 and 14 of the opcode, and a number of connections that I'd just forgotten to hook up [all but one of them just the ball return for junk outputs].

I'm now taking a break from debugging ALU ops in order to improve visibility into values within bcd. This should make it much faster and easier to debug the rest of the opcodes.

Incidentally, the instruction took a whopping 1600 gate delays [and therefore 1600 wire delays] to execute. If each of those delays is on the order of 0.5 seconds in real hardware, we're talking about 25 minutes per instruction! However, I'm pretty sure I can improve on that by a factor of 10 with fast gates and the parallelization of processing that I've got planned for version 2.0 of the CPU.

Back on the horse

2005-10-04T09:25:00.000-07:00

What with my vacation, far too many weddings, work, and general busyness, I haven't managed a single post in just over 2 months. Nor have I managed to do any work and just not post about it. However, that's all over now...for a bit.

Sunday night I got back to work on the cpu design, and am now able to report great progress. Why? Because I was clever enough not to test what I had designed! Had I in fact run a simulation, I would have found that none of it worked, stayed up until all hours trying to fix it, and perhaps ended the night dissatisfied and with it all still broken. Not having done any testing, I can report that I've made lots of progress, and that it merely needs a bit of debugging. Isn't that great?

Anyway, what I got in on Sunday is the rest of the ALU operation state machines. That means absolutely everything needed in order to execute any type of ADD, SUB, AND, OR, or XOR instruction [immediate or register arguments, carry-in from CCR or not, writeback to a register, CCR bits CVZS set as appropriate afterwards, increment the PC and turn off the stove when you're done]. Whee! Actual instructions, and they might even work!

Anyway, here is an image of the top-level design, shrunk down to the point where you really can't see anything. For those of you with more time on your hands, here is a much bigger image of same, blown up to the point where you can just about read my notes if you squint.

I's quietly proud.

2005-07-31T22:56:00.000-07:00

As of this week, I have acquired my first minion. My friend A. has begun to write an assembler for the Ball Computer, in Haskell. An instruction-set simulator will follow shortly thereafter.

Mua-ha-ha-ha!

Teaser--the first view of the CPU

2005-07-17T23:44:00.000-07:00

After much preparation, I've finally started to assemble the CPU. Sorry for the teaser, but this diagram is 1) completely nonfunctional; it'd just start dropping balls on the floor shortly after starting up, and 2) not an imagemap. Given that it doesn't work anyway, and most of its components are already documented, I didn't bother setting up all the links for each of the subcomponent definitions.

What I've done here is mainly just plunk down the components I've designed so far and make the obvious connections between them. The less-obvious connections, which is to say those which will vary based on the particular instruction, are still missing. As I put in the instruction decode logic, I'll be able to add and test a few instructions at a time until the CPU is complete.

As I bolt things together, I've been finding small changes that need to be made in some of the components. In some cases it's as simple as deleting functionality that's going to be taken care of more efficiently elsewhere, but generally it's just rearranging ports such that more internal information is exposed to the enclosing scope. Many of the components toss all setup balls out a single "junk" output when they're done with them, which throws away such information as "what values were input?" and "was that the last of the setup balls?". These turn out to be quite handy for the controlling state machines, who then don't need to waste time and gates maintaining the same data themselves.

Incidentally, I expect that I'll do the branch and jump instructions first [unconditional first, then the conditional ones], as it's pretty hard to test a CPU if it doesn't have a working program counter, and the PC design is fairly closely tied to the branch and jump logic.

The Shifter

2005-07-09T22:17:00.000-07:00

OK, here's the latest version of the shifter. I've altered its carry-out behavior such that Cout holds the value of the last ball shifted off the end. This way it can be used for single-bit tests. It's going to be much faster than an ALU operation, so that might come in handy.

This shifter is basically set-up-and-flow-through. Once you've input the shift amount, shift direction, and whether the shift is arithmetic or logical, the input balls just go straight to the appropriate outputs. Balls shifted off the end get rotated all the way around, set to zero or one as appropriate to any needed sign extension, and inserted back into the byte. The only awkwardness is in the need for one extra ball input after the first bit [the MSB] of the operand; I use that to set up the sign-extension logic.

I've also made some modifications to the ALU, but haven't yet posted the new version. They're not very big mods: I've added zero-detection [which may eventually get pulled out] and changed the interface a bit. Now instead of having to pour balls into a port until being told to move on to the next phase of operation [several times], you just put one ball into each port until the last one, which always takes 11 for result readout [8 data bits, V, Z, and C].

Now I really do just have to put it all together. Yow!

New improved ALU

2005-06-26T19:37:00.000-07:00

Ever have to go back to the very first code you'd ever written in a language...code that you'd optimized quite a bit...code that you hadn't commented enough...and try to add in a tiny new feature?

Sucks, don't it?

Well, that's just what I've done here. The ALU was my first major design using BCD. It contains the most complicated logic of any design, and I stupidly optimized the heck out of it. The design is quite contorted in various places...and I wasn't even that good at ball-logic-based design, so I ended up throwing away some of the benefits of the optimization through odd choices in other parts of the design.

However, it works, so I'm not messing with it too much. I've removed a couple of redundant gates, but otherwise all I did was add support for one new opcode: SubC. This is the subtract-with-carry-in that you'd use to do a higher-byte subtraction, where the carry-in is from the condition code register. On the bottom byte, you force it to be one [since we're doing twos-complement math].

Here it is, in all its twisted glory. You have my apologies about the size of the images [especially that one page deeper than the above link], but if I make them any smaller, there's no way to read the details. I recommend using a web browser that allows you to zoom in and out at will [I use Opera].

Next up, I've got to fix the overflow behavior in the shifter. Huh; I just went to make the word "shifter" a link, and realized that I've never put up any images of the two shifters I've designed. Well, perhaps I'll use them as filler if I'm too busy to create the final version.

[Image] ALU with SubC test

2005-06-26T19:35:00.000-07:00

Click on the yellow boxes to see inside them.

[Image] ALU with SubC

2005-06-26T19:30:00.000-07:00

Click on the yellow boxes to see inside them.

The Signed Multiplier

2005-06-15T00:28:00.000-07:00

Here's a test of a multiplier that can handle both signed and unsigned inputs, as promised. As I'd expected, there was an easier and faster way to do it than sign-extending the inputs. Since the sign extension would have produced either an 8-bit -1 or an 8-bit zero, if each high bit is nonzero I just have to multiply the other byte by -1 [which is as easy as a complement-and-add-one] and shift it by 8 bits [which is trivially done in the routing].

[Image] Signed Multiplier Test

2005-06-15T00:17:00.000-07:00

Click on the yellow boxes to see inside them.

[Image] Signed Multiplier

2005-06-15T00:07:00.000-07:00

Click on the yellow boxes to see inside them.

You thought the ROM was big?

2005-05-28T11:49:00.000-07:00

You thought the ROM was big? Meet the RAM.

That's actually a link to the state machine I used to test the RAM itself, so that you can see what its interface is like.

Note that I'm using a ROM to hold a sequence of simple instructions [here just addresses and data], just as I did in the PCU test. While my designs are getting bigger and more complicated, I'm able to leverage the components I already trust in order to test the new ones.

With the creation of this component, I now have [in a half-assed way] all the parts that one would need to make a CPU. All the rest is pretty much glue logic and some instruction-decode state machines. However, most of the components need a little tweaking before I can really put them all together. For example, the ALU doesn't have a carry-in signal yet, the multiplier doesn't give 16-bit results for signed inputs, the shifter doesn't produce the precise overflow behavior that I want, and they've got a variety of different control interfaces.

My plan for the rest of Step 3 is:

Improve bcd's simulator interface, to make testing easier and faster;
Decide on a standard control paradigm for all components;
Go through all the components, one by one, and make the necessary improvements;
[Finally!] put it all together and proceed to Step 4: write+run test code for the complete CPU.

[Image] RAM test

2005-05-28T11:43:00.000-07:00

Click on the yellow boxes to see inside them.

[Image] RAM block 2 256x8

2005-05-28T11:41:00.000-07:00

Click on the yellow boxes to see inside them.

[Image] RAM block 2 16x8

2005-05-28T11:38:00.000-07:00

Click on the yellow boxes to see inside them.

[Image] 1 to 32

2005-05-28T11:36:00.000-07:00

Click on the yellow boxes to see inside them.

No new diagrams this week.

2005-05-11T20:04:00.000-07:00

Nor for the next couple of weeks, I expect. I've been improving bcd [my CAD program; it stands for Ball Computer Designer] instead of using it.

When I was working on the huge ROM diagram [with all its thousand+ connections], I got so sick of connecting ports by hand that I ended up doing much of the work in the raw XML files in which I store my database. What with all the vim macros, search-and-replace regexps, and copy-and-pasting, I'm not sure I actually saved any time. Still, I think I made fewer mistakes that way than if I'd used bcd, and I had to do far less mousing.

It occurred to me that much of the work in such a diagram is quite mechanical, and could be done automatically by a properly-trained tool. Thus I've now added a connection-extrapolation feature to bcd. I make and select two connections, and it guesses where the next [and subsequent] connections should go. I'll probably do the same thing for ports and cell instances before I get back to work, as my next diagram will probably be the RAM. Think: like the ROM, but with half again as many components and connections. Whee!

The Multiplier

2005-04-25T23:25:00.000-07:00

Having looked at just how large the ROM [and, by implication, the forthcoming RAM] are going to be, suddenly another 350 gates for a dedicated multiplier don't seem so bad. Of course, this one only works for unsigned numbers, but it's not too hard to add in the hardware for signed multiplication as well. I'll either do that by sign-extending the inputs or by something slightly more complex, but I don't quite have time to manage it tonight.

You will note [and I use the word will rather speculatively, I realize] that the multiplier is a bit more complex than it needs to be. The accumulator is obvious and minimal, but the circuits that feed into it are actually optimized for speed. I could just have done the simple 64-ball-paths crossbar of the 8 bits of each input. That would always have completed its calculations in a predictable amount of time [(64 balls) + (arg input, reset, and readout)], but it would often have spent lots of its time multiplying zero by zero. The design I decided to use instead recognizes zeroes in Op0 and skips all processing [including state machine reset] on those bits. Of course, the state machines used to do that recognition aren't free. The processing time is (10 balls per bit) + (the other stuff). That gives us a worst case [multiplying by -1] of (80 balls) + (all the other stuff), but that'll be quite rare. It's made rarer still by the fact that any constant -1 multiplications can just be replaced by complements, which should be significantly faster.

[Image] Multiplier Test

2005-04-25T23:23:00.000-07:00

Click on the yellow boxes to see inside them.

[Image] Multiplier

2005-04-25T23:21:00.000-07:00

Click on the yellow boxes to see inside them.

[Image] 1 to 16

2005-04-25T23:09:00.000-07:00

Click on the yellow boxes to see inside them.

The Program Counter Unit

2005-04-10T22:37:00.000-07:00

If the ALU is the heart of the CPU, then the PCU is surely the bit that nags you to get off your ass and do things. Wait--no--maybe it's the brain. Yeah, that's probably it.

It's a bit awkward for me to try to abstract out a monolithic PCU block for testing. At least in my design, the PCU is quite closely tied in to the master state machine that controls the entire CPU. What I've ended with up here is therefore not a box labelled "PCU" that you just hook up to your ROM, RAM, ALU, etc. It's a set of pieces:

The readable register that's used to index into the instruction ROM;
The writable other half to that register, linked to it with pulleys in order to carry the state uphill; and
The Next PC register, used to increment the PC, hold the new value for a jump, or dump out PC+1 to the link register.

In this test I'm just displaying the link register's value rather than actually using it, and my opcodes are just:

nop
branch to immediate value
branch-and-link to immediate value

In order to have a complete view of all sorts of different branching instructions, well...I'd have to have done a lot more work. I'll get there, but for today at least I've tested all the basic parts I'll need.

Incidentally, the two small text boxes in the screen shot, which are probably too small to read, contain the following text:


Phases of operation:

   Read Next PC->PC
   Increment PC
   Read PC->ROM
   Process instruction

Opcodes for this test [bits 15-14 only]:

   0x0000: No-op
   0x4000: No-op
   0x8000: branch to addr in bits 13-6
   0xC000: branch-and-link to addr in 13-6

[Image] PCU Test

2005-04-10T22:30:00.000-07:00

Click on the yellow boxes to see inside them.

[Image] 1 to 16 Triggered

2005-04-10T22:28:00.000-07:00

Click on the yellow boxes to see inside them.

The biggest ROM ever built.

2005-03-27T20:02:00.000-08:00

Well, it will be, anyway, if I do manage to build it. This ROM is 256 words of 16 bits each: 0.5KB. It will probably also comprise more than a ton of building materials. It uses about 9180 gates and nearly 14000 connections. Of course, you could remove 4096 gates and 8192 connections if you don't mind programming it by moving connections around, instead of just flipping gates. If you rarely reprogram it, that might be a big win; it'd be just like the old electronic computers which were programmed by plugging wires into switchboards.

This diagram is scaled way down from the others, and is the first that I've chosen to post with full-depth drawing turned on [so that you can see inside each of the smaller 16x16 ROM cells].

Incidentally, speaking of scaling: I realized the other day that I've been posting mostly full-scale images. The code that dumps out screen shots was supposed to have been putting out images scaled down to 60% of regular size, but it turned out that it was only scaling down the top-level diagram, and that all of the other images linked from there are full-scale. I may go back and fix that up [now that I've fixed my code], but it's a bit of a pain to get it all set up, so that may take a while. While the tool dumps out images and image maps for me, it's still a bit of manual scutwork to get it all into blogger + photobucket.

[Image] ROM cell 256x16

2005-03-27T19:34:00.000-08:00

Click on the yellow boxes to see inside them.

The [almost-]complete ALU

2005-03-09T22:58:00.000-08:00

I've just posted imagemaps of the latest revision of my ALU. It understands 5 opcodes [ADD, SUB, AND, OR, XOR] and produces both unsigned [C] and signed [V] overflow signals. What it currently lacks is the ability to make use of a carry in. Without that, you can't do 16-bit ADDs or SUBs efficiently. I'll get there, but I wanted to put this up to show some progress.

I've also got two different versions of the shifter [nearly] done. I'll probably put one of them up next. The reason that I'm not fully satisfied with either of them is, again, the carry stuff. Do they need to take a carry in? It's really useful if you want to do a 16-bit-wide, one-bit shift. However, since my shifters are capable of doing 0-7-bit shifts, what does a carry [in or out] mean? I figure I'll want to set the carry out flag by the first bit that comes out, no matter how far you shift [as long as that's at least one bit]. But what about the carry in, when you shift by more than one bit?

There's another problem there, though--I've already written the instruction set, and I don't have a bit left for "does the shift take a carry in". Oops...any thoughts on how important that is?

Of course, that question would be easier to answer if you knew the rest of the instruction set. I'll post it soon. It's not set in stone, but it is guiding my design of the computer, and I'd love to get feedback on it.

[Image] ALU test

2005-03-09T22:53:00.000-08:00

Click on the yellow boxes to see inside them.

[Image] ALU

2005-03-09T22:47:00.000-08:00

Click on the yellow boxes to see inside them.

[Image] 8-bit adder

2005-03-09T22:44:00.000-08:00

Click on the yellow boxes to see inside them.

[Image] 1 to 16

2005-03-09T22:36:00.000-08:00

Click on the yellow boxes to see inside them.

Understanding the diagrams

2005-02-26T13:30:00.000-08:00

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

2005-02-25T00:06:00.000-08:00

"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

2005-02-24T23:32:00.000-08:00

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.

Introduction

2005-02-24T23:27:00.000-08:00

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

[Image] Reg Test

2005-02-21T21:33:00.000-08:00

Click on the yellow boxes to see inside them.

[Image] Reg Test:Register File

2005-02-21T21:28:00.000-08:00

Click on the yellow boxes to see inside them.

[Image] Reg Test:Register File:R0

2005-02-21T21:26:00.000-08:00

Click on the yellow boxes to see inside them.

[Image] Reg Test:Register File:R0:R0

2005-02-21T21:24:00.000-08:00

Click on the yellow boxes to see inside them.

[Image] Reg Test:Register File:R0:R1

2005-02-21T21:21:00.000-08:00

Click on the yellow boxes to see inside them.

[Image] Reg Test:Register File:R1

2005-02-21T21:16:00.000-08:00

Click on the yellow boxes to see inside them.

[Image] Reg Test:Register File:R1:R0

2005-02-21T21:13:00.000-08:00

Click on the yellow boxes to see inside them.

[Image] Reg Test:Register File:R1:R1

2005-02-21T20:54:00.000-08:00

Click on the yellow boxes to see inside them.