An actual multiply instruction in 8bit?

[NorthWay]

Hm. I thought either Z80 or 6809 had something like a half byte multiply? Or am I muddling that with something else?

I think the something else might have been a nibble parity status bit - was that a thing?

[gilesgoat]

Hm. I thought either Z80 or 6809 had something like a half byte multiply? Or am I muddling that with something else?

I think the something else might have been a nibble parity status bit - was that a thing?

You SHOULD be "retro nerds" and know your CPUs by heart !!!

The Z80 had the "Parity/Overflow bit" and the "Half Carry" bit that is a carry from bit 3 to bit 4, used in BCD instructions and especially the famous "DAA" ( Decimal Accumulator Adjust ).

You spend too much time with high level languages you forgot how ASM works

[edit] ok "I am the person you can ask how a triode works and/or how to really make it work" so there's that ( and that's still working on his Z80 projects )

[Dio]

You spend too much time with high level languages you forgot how ASM works

Naah, you go too far down the asm route and you never forget. In fact it's the HLLs that are fading, the asm remains strong.

[gilesgoat]

.... "Late night experiments" ....

Code: Select all

=========================================================================
HDL Synthesis Report

Macro Statistics
# Adders/Subtractors                                   : 1
 16-bit adder                                          : 1
# Counters                                             : 1
 3-bit down counter                                    : 1
# Registers                                            : 2
 16-bit register                                       : 2
# Multiplexers                                         : 1
 1-bit 8-to-1 multiplexer                              : 1

=========================================================================

Re-checking device resources ...
Mapping a total of 72 equations into 8 function blocks.................................

Design Multiplier has been optimized and fit into device XC95144XL-5-TQ100.

*************************  Mapped Resource Summary  **************************

Macrocells     Product Terms    Function Block   Registers      Pins           
Used/Tot       Used/Tot         Inps Used/Tot    Used/Tot       Used/Tot       
72 /144 ( 50%) 467 /720  ( 65%) 180/432 ( 42%)   35 /144 ( 24%) 35 /81  ( 43%)

I have to create then a "VHDL testbench" and see if it does anything and/or what it does ...

In THEORY it does the multiplication ( unsigned for now ) 8x8 bits in 8 steps via "shift and add", no different than what you'd do on paper by and with a pen.

"Takes the bit of 'B' and if it's 1 sums "A" else sums "0" then "A" is shifted 1 position left".

If it works I'll make some small PDF in LaTEX explaining how it works

What is a bit "amazing" is that thing that I believe is "ultra simplified" eats 1/2 of an XC95144 so 72 macrocells, must be said I think ONE single FF element consumes 1 macrocell so that's what fucks up a bit, but yeah .. "consumes space" ..

[KlaxonCow]

but yeah .. "consumes space" ..

Indeed.

Also, another thing to think of is who's going to create a CPU with one kick-arse single cycle multiply instruction... but not much of anything else?

That is, if you've supplying multiply then you've surely also got to supply divide. And division is the more gnarly one to implement than multiplication. Multiplication was actually "the easy case" here.

The division algorithm is featured in this video:



So it's a "left shift, subtract, branch on carry, store result" loop, basically.

And the point is that if you're implementing this CPU with its one cycle multiply, you're setting expectations that your divide is also going to be as awesome.

So, you know, if the multiply eats half your macrocells, and then the divide also eats a similar number (maybe even slightly more) then, there you go, your CPU has the most amazing multiply and divide instructions... but there's no room for anything else. Like, you know, addition and subtraction. Much less the very basics like "load / store / mov", push / pop, jumps, conditional branches, etc. which you really need to make the CPU useful in the first place.

And, indeed, as me and Dio were discussing about CISC vs. RISC, the point is that if you've got those basic instructions - addition, subtraction, bit shift, branches, etc. - then a coder can "roll their own" multiply and divide anyway. So the argument is that it makes more sense to focus on making those few basic instructions super-fast, which is the RISC mindset. A reduced instruction set, but now you can devote all those transistors / macrocells to making this small "core" of instructions super-fast and then anything more complex - like multiplications and divisions - can be built up from the basic instructions.

Another aspect of that argument is that, well, how often is code actually multiplying and dividing? Particularly because a good coder / compiler is going to be always avoiding them anyway, knowing that they can do "powers of two" incredibly fast with a bit shift - so whenever that's possible, that's what they're actually going to be doing, not actually using the "multiply" instruction.

Like, you're indexing an array. If you make sure that they all start on a "power of two", then you can bit shift (and add the base address) to convert your index into a pointer - e.g. base + index << 2 for 32-bits - rather than actually invoking the real multiply instruction - e.g. base + (index * 4).

It's a lot of effort and how often is it really going to be used?

Whereas, if you concentrate on making addition, AND / OR, bit shift, branches, etc. - those "core" instructions - super-fast and single cycle, that's effort that's going to be rewarded all the time. The whole CPU just runs faster. And, to make room for that, perhaps just not bother with multiply and divide instructions at all? As they can be composed of other instructions, there's an argument that they're not truly elemental operations.

Basically, on top of the technical considerations, there's just the practical ones. What use is a CPU with these super-amazing multiply and divide instructions, when there's no room for anything else? And it'd be an odd CPU to try to sell to people where you can boast a single cycle multiply... but, umm, there's not enough room to also "unroll" addition as well, so the addition takes 8 cycles to complete. Like, it's an extremely weirdly lob-sided CPU design. You could do it, but who'd actually want that?

[gilesgoat]

Yesterday I've done a bit of "VHDL testbenching" which means "write a VHDL 'stimulus process' ( i.e. simulating the input waveforms you want ) and see the output of the DUT ( Device Under Test ) via simulation".

After 4 or 6 iterations where I realised I had a few "stupid bugs" in my idea/implementation things started to almost work.

Except .. that I am ending up with a situation where I need 9 clock cycles to do an 8x8 bits multiplication, too complex to explain "why 9 and not 8" in short it's because I still need "a final pulse for a FF to latch the final sum".

But there's still "some little problem going" so I am NOT going to post any results here until is 100% working.

"How often is used multiply/divide" .. "depending what you need to do" .. in MY case I'd love to try to use something like that with fixed point arithmetic do multiply 3x3 or 4x4 matrices by vectors, so "the final goal" would be "a matrix/vectors multiplier" so it would be ALL about multiply and sum.

Divide .. eh .. "at the end of lot of computations" you NEED to divide to get "screen coords" and try as you may you can't get rid of divide.

Anyway "I am getting somewhere" but it's not fully correct yet, I have to think more on it, surely it's a bit more complex than it sounds to make a working thing.

[gilesgoat]

Tah Dah .. "a bit of fix there and there" .. still testing but you can see "it appears to be working" ...



It multiplies "A" by "B" and the result is that "Product" ( in yellow ).

It takes precisely N+1 clock cycles to multiply ( unsigned ) two N*N bits, with that particular chip it should be no problem ( haven't checked timings fully yet ) to go 10ns per cycle so 90ns per multiplication, that's about 11M 8x8 bits multiplications per second.

Now I should find "something to make a pic" and I could write something in Latex for the posterity about "Giles' multiplier" but it's absolutely nothing special, it does the multiplication via SHIFT + Add "as you'd do by hand".

It misses also some "support things" in the sense of it's critical that "Start" signal is triggered precisely like that ( otherwise crap happens ) and that the data must be STABLE for all the 9 clock cycles.

To be "a real multiplier" it may need some better "clock gen circuitery" I mean at least something that generates that "START" pulse in that way, I could also easy add a "busy" line to tell when multiplication starts/ends.

But yeah I think "you can't do it simpler than this", it uses a latch a summer, some gates and 1 counter .. it could be very easily extended to arbitraty MxN bits but yeah "time to write a paper ( for your amusement ) about all this"

[gilesgoat]

"Deep meditation with Settimana Enigmistica and some paper and a pencil" ...

"I got an idea" about how you could do it "in 1 clock cycle" but I can't do it with the chips I have ..

Let's see if this reasoning works ...

Let's consider 2 eight bits numbers M, N we want to multiply.

Let's think M,N as [D][C] x [A] where A,B,C,D are 4 bits "nibbles".

We can rewrite M x N = (A + 16 * B) x ( C + 16 * D)

So MxN = A*C + 16 *D * A + 16 * B * C + 16 * B * 16 * D

Re-ordering a bit ..

M x N = A * C + 16 * A * D + 16 * B * C + 256 * B * D

Now imagine we have 4 ROMs of 256x8 bytes each ( it would be the same ROM but we need to be able to access 4 copies of this ROM SIMULTANEOUSLY ) .

If we create a ROM that contains all the 4x4 products ( result 8 bits ) we could simultaneously "compute" ( i.e. read from the ROM ) the "partial products" :

AxC, AxD, BxC , BxD

Expand/align them properly into I think we need only TWO 16 bits adders and voila' you have your "1 cycle multiplier".

Now 4x256 bytes "ROMS" are "absolutely NOT unthinkable into an FPGA", that would be really 1K of ROM.

Yes "a bit silly" but could be a building block for a more complex multiplier I guess, not even sure if this 8x8 multiplier would take more/less silicon that the other one I made which is made with "real gate logic", this actually could be more efficient/easier to implement but I doubt they'd do like that in a 8bit MCU.

[Dio]

It's a 16-bit carry-save adder into a carry-propagate adder.

It's still not practical for 8-bit though. 256x8x4 is the same number of transistors as a Z80 .

[gilesgoat]

It's a 16-bit carry-save adder into a carry-propagate adder.

It's still not practical for 8-bit though. 256x8x4 is the same number of transistors as a Z80 .

WOW ... I did not know that .. I read that the Z80 contains approx 8500 transistors ..

.. that's BANANEZ .. if you consider you need at least 2 ? 4 ? transistors to make a logic gate ( and / or ) ...

I mean it's really SMALL and I wonder "in terms of efficiency" if any CPLD/FPGA is actually so efficients as they were able to be "manually" when they had little resources and big limits.

[KlaxonCow]

"How often is used multiply/divide" .. "depending what you need to do" .. in MY case I'd love to try to use something like that with fixed point arithmetic do multiply 3x3 or 4x4 matrices by vectors, so "the final goal" would be "a matrix/vectors multiplier" so it would be ALL about multiply and sum.

So you basically want to make a GPU, then?

No, the general gist of what I was saying, of course, is just that, when designing a CPU, you've also got to think of the whole thing as a complete unit, not just individual instructions.

You can't reasonably forget that you also need "mov / load / store", AND / OR / XOR, "jmp" / "call / jsr", push / pop, etc. because those basic instructions make the thing work in the first place. You've got to be able to compare and branch, and call subroutines and do simple counts ("inc / dec"). The very basics of program structure - for "FOR" loops, "WHILE"s, "IF this THEN jump here", etc..

That stuff's not really optional, or how the hell would you program this CPU to do anything remotely useful?

So, the gist of what I was getting at is that you can't reasonably waste half your transistor count on a single instruction, before you've at least covered these "basics".

Those instructions have to be in there to guarantee that your CPU is, in fact, actually Turing Complete. Because, you know, Turing Completeness really is not an "optional extra" for a CPU design.

My point was just that you have to think of the overall picture. The whole point of why you're designing the CPU in the first place - to actually run programs that do useful things.

It's easy to get neurotic on individual instructions and counting cycles, and then miss the overall "big picture". Real easy to do in assembly language, for sure, where you see people counting cycles and re-ordering instructions and being very neurotic about the small details to "optimise" their code - but the biggest wins are always algorithmic and at a higher level.

Messing around with individual instructions can win you a few clock cycles here and there, but a change of algorithm can change an "O(n^2)" to a "O(log n)" instead.

Basically, always optimise from the top down. Because the biggest wins are algorithmic. Sometimes, you can shuffle a problem around so that you, in fact, don't have to calculate anything at all - and, obviously, no amount of messing around with individual instructions is going to beat the "zero cycles" of not having to do any work at all.

Like, the argument about which is the fastest sorting algorithm. Well, actually, the fastest possible sorting algorithm is never to have unsorted data in the first place. If it's already sorted, then the sort algorithm is "do nothing" - and that's zero cycles - so nothing can ever beat that, no matter how bloody clever it might be.

Of course, sometimes you can't pre-arrange things to be already sorted, but often you actually can, if you're the one creating the data in the first place.

And this is what I mean about "top down optimisation". Optimising the algorithm will always be the biggest win. And, indeed, the wins can be so big, that you never need concern yourself with the "small print" of individual instructions.

That is, when optimising code, start at the highest level and work your way down. And you'll probably find that you never need to actually reach the bottom, as you already made it run more than super-fast enough to do the job just fine.

(Also, it just doesn't make logical sense to do it in reverse, because "the big" is composed of "the small". So if you're messing with individual instructions, then you move up to looking at the overall program structure, you might then realise that "actually, if I move this and do that, then I can throw out that subroutine altogether". Oh dear. All that time spent optimising it, and it ain't even needed? This is not a sensible approach, if you value your time. So start at the very top and work down.)

[Dio]

WOW ... I did not know that .. I read that the Z80 contains approx 8500 transistors ..

.. that's BANANEZ .. if you consider you need at least 2 ? 4 ? transistors to make a logic gate ( and / or ) ...

The 6502 was way less, something like 3500, although only a bit smaller in die area, because Faggin was very, very good at layout. (And yes, the CEO laid out the CPU himself).

But the Z80 is also weird as hell. The register file is crazy dense and it's only got a 4-bit ALU, but it spends fully two thirds of its area on instruction decode and sequencing. It you scale the proportions of something more like the first ARM, you can clearly get something RISC-ish into the same footprint. I reckon it could achieve 5x performance reasonably easily (instruction bandwidth ends up the limit in most foreseeable scenarios, even with a page-mode capable DRAM controller integrated).

Nobody carried on evolving 8-bit CPUs though, they did the two generations and then bailed out for wider buses, so they didn't really notice that they were leaving so much on the table. It wasn't until CPUs got to 32-bit and they had to start lateral thinking rather than just going wider that they started to think about it more.

[gilesgoat]

@Klaxon_Cow :

"you are starting to miss a bit the point here" .. all this started with a discussion about "mutiply instructions in HW", I wanted to see "how hard can it be" to create an HW multiplier ( is hard if you want to really make it "good" ) .

But I put something together in HW that as you can see CAN multiply two 8 bits numbers Was really more or less a test of "how hard can it be ? Can I really make one ?" I never tried to do one before.

I would never dream in making a whole GPU/CPU but more some "support chip" and/or "dedicated ASIC" for certain functions.

If I'd had "a chip" where I'd give it "a mem address" and say "this is a 4x4 matrix" and another address where I say "this is a bunch of vectors" and "this is N, go multiply all those N vectors for that 4x4 and then put the result back in memory" that would be already "a huge help".

It would be more "sort of" a "micro DSP" than a GPU.

Actually this is precisely stuff you SHOULD be able to do with a DSP, but so far I never touched on that's territory I am really NOT familiar with ( and to my LITTLE knowledge are 'some of the most exoteric things to code' I mean the HW is usually designed in a really WEIRD way ).

Anyway someone started with "an 8 bit multiplier" and "my challenge" was to see if I could have made "something working in HW" to see how it is, looks like I've done it.

[KlaxonCow]

Yes, sorry. Perhaps I was not clear.

I was not commenting on what you'd done there at all.

I was still talking in terms of the earlier general topic of how you'd never fit all of that onto these 8-bit CPUs - along with everything else that you really, really need to include - as they just didn't have the transistor budget.

That, because of that tight transistor budget, you have to think of the whole CPU design - and, in that context, it would be right, I reckon, to drop multiply and divide (as these are not elementary operations and you can do them with adds and subs and bit shifts instead), in order to afford all those transistors to just getting the basic "core" of Turing Completeness working, first and foremost.

I didn't think you were going to build a whole CPU here. Really, it was only a reply to what you wrote, as I was "springboarding" off something you said to talk about that, but it was not really directly addressing what you'd done there. That, perhaps, was not made more obvious by me. My bad.

[gravy]

6809 does have MUL of two 8-bit registers to a 16 bit result and takes 10/11 cycles.

It's such an excellent processor.