Gigatron optimisation for a lite version?

Using, learning, programming and modding the Gigatron and anything related.
Forum rules
Be nice. No drama.
tocksin
Posts: 25
Joined: 22 Jun 2018, 14:12

Gigatron optimisation for a lite version?

Post by tocksin »

I've been reading about some other CPU designs, and came across one which has no ALU, but does arithmetic via ROM look-up tables. It only does a 8-bit increment and decrement, but proves that any arithmetic function can be supported with those two functions (and technically only increment). Additionally you can do comparison by using indexed RAM read/writes. And from that comparison you can do conditional branches (equal or not equal to).

Looking at the Gigatron schematic and code, the operation of the video should work just fine without the ALU. The ALU takes 10 chips, so removing them would save quite a lot of space. I figure it would remove about a third of the space on the board. It would also free up the instruction set quite a lot to allow for extra instructions for external I/O.

It would also reduce the capabilities of the Gigatron though, but I'm not sure how much. If I had the time I'd rewrite the ROM from scratch without using ALU functions except increment, decrement, BEQ/BNE. I'm not sure if you could do some kind of code analysis to try to figure out how much of a slow-down you'd see. I'm also not sure how much "fun" it would be to code. Without basic bitwise instructions it could get laborious. Again, it might be interesting to try. But most coding is intended to be done in the higher level language anyway.

I can see if this project existed back in the 70s/80s that this would be a marketed as a low-cost Gigatron-lite type of computer. I'm not sure if I'd ever put time into it considering I don't really have time to finish my current Gigatron project, but it is interesting.
GigaMike
Posts: 7
Joined: 21 Jan 2020, 19:48

Re: Gigatron optimisation for a lite version?

Post by GigaMike »

I am fairly new to Gigatron. But what strikes me the most about this project is that the design has ended up with something that is actually useful and performant within its constraints of being a 8-bit computer based on TTL chips.

The real question is what are you trying to achieve without an ALU?
  • Save board space - Make a bigger board with the extra function (or conversely use SMD and keep it small)
  • Save money - Probably not if you have to buy a ROM to act as the ALU instead
  • Save instructions - Perhaps but there are a whole lot of NOPs that could be used or you could look at the expansion bus idea for more I/O
  • Intellectual exercise - OK but probably not that useful to anyone. Conceptually you could build an adder only using increment and test if zero operations but it would be painfully slow. That's why all real-world CPUs have some kind of ALU in them.
User avatar
marcelk
Posts: 488
Joined: 13 May 2018, 08:26

Re: Gigatron optimisation for a lite version?

Post by marcelk »

The idea comes up frequently enough that it is the Gigatron FAQ :-). In the 1970s, very big ROMs were either slow, and large arrays of fast small ones completely out of place. Large capacity and fast-enough ROMs that can take over an 8-bit ALU function or some other complex logic only came about in the late 1980s, early 1990s (I didn't really date it, but all those "megabit" projects were late-1980s). But if you allow something like that on your critical path, why not also allow other programmable logic from those days as well? It feels weird to accept a "modern" ROM while insisting on mixing it with just TTL. So we considered, but that direction didn't appeal much to me.

Once we stumbled upon the signalling diode solution, it was clear what the Gigatron was going to be about. From that moment on you could look deep into the instruction set: it wasn't any longer becoming yet another board with just a bunch of little black boxes. So then we decided to use only SSI/MSI chips in the CPU proper and the 74LS181 had to go as well. We still stayed well under 40 chips, that was important: We didn't know of any other single-board TTL CPU with so much performance that software can do what normally requires a lot of extra hardware.

(The kit comes with a megabit ROM of course, but it doesn't have to be super fast and most of its capacity is used as cold storage: the Gigatron software kernel is tiny. As this isn't in the CPU proper, I consider that a different situation.)

Having expressed my general dislike for "ROM-as-logic", I highly appreciate two cool ROM-based designs that are out there:

The first is the Gray-1 design. That replaces all logic with ROMs. That is very cool.

The second is the 4-bit Nibbler. We studied it well before the project. I really like that minimalism while it is good enough for Tic-Tac-Toe, but it is hard to program for. [Later I had an idea for a simplified Nibbler-like computer, using some Gigatron ideas. But I couldn't squeeze the whole system in 10 chips, which would be my goal for such a 4-bit computer. That count would have to include the clock, an integrated 74LS181 ALU and one EEPROM. I always ended up with 11 chips. I didn't try truly hard to eliminate the 11th chip, but it wasn't immediately clear to me how to get there.]
alastair
Posts: 68
Joined: 10 Oct 2019, 14:28

Re: Gigatron optimisation for a lite version?

Post by alastair »

I always liked the idea of putting the ALU in the ROM and worked on some designs way back in the 80's. I'm bringing one to life after being inspired by the Gigatron. ROMs were pretty small back then, so I had to get creative since a single function to handle two 8-bit values takes up 64k bytes.

You can break the calculation down and use a smaller data width in the ALU. E.g. the Z80 had a 4-bit ALU and used an internal multiplexer and cache to complete an 8-bit operation in two cycles. This allows you to use a smaller ROM but adds back some complexity. ROMs are also a lot slower than discrete logic, so you have to start pipelining things to prevent the lookup delay getting in the way of execution.

In the end you tend to end up with the same number of chips either way (for equivalent performance). One advantage of the ROM is the ability to add custom and specialized functions though. This can be an appealing option, but you are not going to eliminate chips to gain this advantage.
tocksin
Posts: 25
Joined: 22 Jun 2018, 14:12

Re: Gigatron optimisation for a lite version?

Post by tocksin »

Well, I wasn't thinking of adding another ROM, but just using the program ROM. All it takes is 256 byte table to do an increment. Then use an indexed load to get the new value. But the philosophy is still the same - where do you want to do your calculating? I guess my preference is to figure out the absolute bare minimum number of chips and still have a usable computer - it can't be so slow that it can't do anything. Maybe that's my EE background - minimize the chips to minimize the cost (much like Woz). Like when they used to put chicklet keyboards on computers to save cost, but that went too far and make it unusable.
alastair
Posts: 68
Joined: 10 Oct 2019, 14:28

Re: Gigatron optimisation for a lite version?

Post by alastair »

I guess it depends what you're to achieve. If the blinkenlights are enough then a simple increment ALU should give you plenty of patterns. Something that simple wouldn't be able to support the video generation though.
User avatar
marcelk
Posts: 488
Joined: 13 May 2018, 08:26

Re: Gigatron optimisation for a lite version?

Post by marcelk »

alastair wrote: 24 Jan 2020, 01:44 One advantage of the ROM is the ability to add custom and specialized functions though. This can be an appealing option, but you are not going to eliminate chips to gain this advantage.
Probably not. We also tried the Z80 approach but indeed it didn't save any chips. It only made it harder to understand. So we went back to the regular layout we now know. Flexibility is where the multiplexer ALU shows its teeth: the function is fully specified from the outside, by the little diode ROM in our case (but you could carry the entire truth table in the instruction if you want). I'm aware of one designer who wants his TTL CPU to have the "A == B" function, using the same ALU. The Gigatron doesn't have that, only "A == 0". But after some brainstorming, we found it could indeed be wired for "A == B" by feeding it the truth table for "(A xor not B) + 1" with de desired result rolling out of CO if I'm not mistaken
PurpleGirl
Posts: 48
Joined: 09 Sep 2019, 08:19

Re: Gigatron optimisation for a lite version?

Post by PurpleGirl »

I've played with some ideas along this line. The ALU takes about 45ns, and the fastest ROM you can get is about 45ns, though you might be able to push it some. So no real advantage if you want to replace the whole ALU.

A useful way to use ROM for calculation would be a multiplier. I would use a 16-bit x 64k ROM, and 8 address bits would be the multiplier and 8 address bits would be the multiplicand. You could write a simple program to make the image to burn. The downside is that the maximum number is 255 * 255, or 65,025, though 16 bits can hold 65535 (256^2-1), or 510 digits short. But it would not work in the Gigatron due to being just 8 bits.

Adding the ability to do powers could be done with an 8-bit ROM, but you wouldn't be able to square past 15. This could be done better in a simple RAM lookup table in code.

Shifting could be done with a ROM. Just use a 64k, 8-bit ROM. Maybe use the lower address bits as the value to be shifted and the upper bits for the number of bits. Another way to do it would be to have a crapload of registers, each wired off by the number of bits to shift. More complex would be circuitry to slide a single register the number of bits to shift. Or, you could try your hand with 56 transistors for each direction. You might be able to do both directions from one direction if you add a couple of inverters.

I've thought about using ROM for the instruction decoder. That might actually gain some speed in the case of overclocking the Gigatron, but the main advantage would be the ability to arbitrarily assign instructions. So some of the nops and Ac=0 instructions could be used to add additional addressing modes, another register, the ability to access the operand, signal an external device, or whatever. I mention the Ac=0 instructions since the Harvard architecture makes them useless because there is no advantage to getting the zero from the ALU over getting it from the operand. This is different from the 8086/8088 where zeroing the accumulator can happen in 1 cycle, zeroing a general register may take 2, and zeroing from the operand would take 4+ cycles. The 286 (and maybe even the NEC 808x clones) and higher could do a little better since they added a dedicated ALU to the address unit. So using the 8088, if you needed to zero multiple registers, you'd do XOR AX, AX and MOV from AX to the other registers. But this gives us no advantage.

Speaking of ROM for a decoder, if one wanted to do it with speed, they could find a way to shadow it on boot. So the control map gets copied to 10ms SRAM and could decode at up to 100 Mhz. Shadowing it could open up the possibility of changing instructions on the fly, and even self-modifying code even in ROM. It wouldn't be true self-modifying code, but the code could change what the instructions mean. A jump could be rendered as a nop, you could decrement instead of increment, etc. But you'd need Assembly for that. And maybe an instruction could be added to reinitialize the instruction stack if necessary.

Now, if space and/speed is your concern, you might consider an FPGA implementation. If one is going to cheat and go beyond what was available for vintage machines, you might as well do it in FPGA. In that regard, it is mostly one good-sized EPROM.
tocksin
Posts: 25
Joined: 22 Jun 2018, 14:12

Re: Gigatron optimisation for a lite version?

Post by tocksin »

As a short diversion, I put together a quick datapath and instruction set based on the non-ALU Gigatron. The datapath is basically the same except without the ALU. I added a few extras just for fun - maybe a keyboard, UART, or SPI interface.
Dataflow Block Diagram(small).png
Dataflow Block Diagram(small).png (54.95 KiB) Viewed 7209 times

Also I figure since so much of the instruction set was not needed, why not redo the instruction set to include more possible memory read configurations and source/destination options. After all, the only thing the computer will be doing is moving data from one place to another now. I put together one example instruction set without doing any implementation or optimization. There's a [X,D] and [Y,D] which helps with block transfer (moving a sprite to video memory for example). Most importantly there's still the [Y,X++] to OUT functionality so video is still possible. It's possible it could be implemented without a diode ROM.
2020-01-28 10_47_56-Instruction planning.xlsx - Excel.png
2020-01-28 10_47_56-Instruction planning.xlsx - Excel.png (26.92 KiB) Viewed 7209 times

This is fundamentally a one-instruction computer now because it just moves data from one place to another. Even the jump instruction just moves data to the PC (although it does so conditionally sometimes). I include some examples of how to do arithmetic and comparing for BEQ/BNE. But I think a lot of games and programs can be done without complex math. For loops or while loops are still easy, but I can only imagine how long the Mandelbrot image would take to execute.
2020-01-28 10_52_37-Instruction planning.xlsx - Excel.png
2020-01-28 10_52_37-Instruction planning.xlsx - Excel.png (52.66 KiB) Viewed 7209 times

I don't know if I'd ever take it further than this, but it's a fun little diversion to see what's possible. I might try a quick code analysis of the existing ROMv4 assembly to see which memory addressing modes are used most to make those more available. I will say that when I did a one-instruction move-only CPU it was interesting to code, so we'll see. Maybe I'd try an FPGA implementation before I did a 74xx prototype.
User avatar
marcelk
Posts: 488
Joined: 13 May 2018, 08:26

Re: Gigatron optimisation for a lite version?

Post by marcelk »

This is the fastest and clearest way to evaluate an idea. Much better than just English, and very to the point. Thank you. Some quick feedback:

1. The block diagram doesn't make it clear to me what bus A and bus B are connected to, because they seem to be drawn as one.

2. IR3 is used in two instruction tables. Is that overlap deliberate? (I didn't punish my brain over it.)

I didn't go over the arithmetic examples yet.

It surprised me how non-redundant the standard ALU operations turn out to be once you write actual code. At an earlier stage in our concept phase we believed we could get away with only ADD and NAND. But then you end up with something that is almost unworkable in software land. [That was also during a time when we hoped that the majority of the decoding logic could be implemented with a single 74LS48 "BCD to 7-segment" IC. Believe it or not, we were pretty close to having a design based around that concept. Initially, the HaD.io project even had the decoder expressions for that as its title backdrop :-)].

A similar experience with the condition decoder, that got added at the last minute. We were heading for just BMI/BPL, and I'm glad we regained our sanity just in time on that one as well.
I might try a quick code analysis of the existing ROMv4 assembly to see which memory addressing modes are used most to make those more available
A color map would be insightful indeed. I never made one. It should be easy by ripping every even byte from a rom file.
Post Reply