An actual multiply instruction in 8bit?

[zip accident]

https://forums.giantitp.com/showthread. ... nstruction

I know I don't know, I thought somebody here probably does.

[NorthWay]

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

[gilesgoat]

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

No I think you are confusing it with BCD Rotation, there were some shift/rotate instructions that operate on "BCD digits" i.e. 4 bits i.e. 1/2 byte.

I don't think there's been ANY 8 bit cpu of the past with anything close to a mul/div.

In fact my z80 books shows me RLD and RRD that operates on "nibbles".

But no I think you have to go to 16 bits CPUs at least ( like the Z8001/Z8002 ) before you can see some real multiplication instructions.

Mind you "my other books" about Bit-Slices show many examples how you can "more or less easily" implement mul/div using some of them but I still think unless you go to REALLY complex HW ( that takes LOADS of gates ) you always end up with more or less "the pen an paper algorithm" where to multiply N*N bits you need at least N steps and 2N bits of results.

Mind you not very long ago I was doing some "code experiments" of integer mul/div with sign "IN C but designed to work with an experimental HW based around a simple full-adder thing".

I ended up with shit like this :

Code: Select all

uint32_t AddSub32Bits(uint32_t A, uint32_t B, bool addsub)
{
	uint32_t sum = 0;
	uint32_t cy = 0;
	uint32_t out = 0;

	if (addsub == true)
	{
		B = ~B;
		cy = 1;
	}

	sum = (uint32_t)A + (uint32_t)B + cy;

	return (sum);
}

uint32_t UMul16Bits(uint16_t A, uint16_t B)
{
	int i;

	uint32_t sa, sb, sc;
	uint16_t mask = 0x0001;

	sa = 0;
	sb = A;

	for (int i = 0; i < 16; i++)
	{
		sc = 0;
		if (B & mask)
		{
			sc = sb;
		}

		sa = AddSub32Bits(sa, sc, false);

		sb = sb << 1;
		mask = mask << 1;
	}

	return sa;
}

uint32_t Negate32IfTrue(uint32_t A, bool neg)
{
	bool addsub;
	uint32_t B, ret;

	B = 0;
	addsub = neg;

	ret = AddSub32Bits(B, A, addsub);
	return ret;

}

int32_t SMul16Bits(int16_t A, int16_t B)
{
	uint16_t UA, UB;
	uint32_t UMUL;

	uint16_t sign_A = A & 0x8000;
	uint16_t sign_B = B & 0x8000;

	uint16_t sign_M = sign_A ^ sign_B;

	UA = AbsoluteVal(A);
	UB = AbsoluteVal(B);

	UMUL = UMul16Bits(UA, UB);

	printf("UMUL %08x\n", UMUL);

	UMUL = Negate32IfTrue(UMUL, sign_M);

	return (int32_t)UMUL;
}

Multiplication was as a charm and so division but "I have a problem" when trying to "convert" or better to say "interpret" all that as "fixed point arithmetic".

I mean I was doing stuff like this ..

Code: Select all

int16_t To8dot8(float a)
{
	uint16_t res;

	a *= 256.0f;
	res = (int16_t)a;
	return res;
}

float ToFloatFrom8fot8(int16_t a)
{
	float res;

	res = a / 256.0f;
	return res;
}


		printf("Float X : "); scanf("%f", &x);
		printf("Float Y : "); scanf("%f", &y);

		ix = To8dot8(x);
		iy = To8dot8(y);

		i_res = AddSub16Bits(ix, iy, &carry_out, false);

		f = ToFloatFrom8fot8(i_res);

		printf("X + Y = %f\n", f);

		printf("ix %d, iy %d\n", ix, iy);

		smul = SMul16Bits(ix, iy);

		smul = (smul >> 8) & 0x0000ffff;

		i_res = (int16_t)smul;

		f = ToFloatFrom8fot8(i_res);

		printf("X * Y = %f\n", f);

Multiplication and add/sub works fine, it produces exactly the result you'd expect ..

But it's the division that still struggles me ..

I mean I *THINK* to get "the best result" you should SHIFT SIMULTANEOUSLY to the LEFT ( i.e. keep multiplying by two ? ) until the 15th bit of ANY of the two is '1' and then you can divide and get 'the most precision' ?

Or dunno what you should do with the reminder ..

I mean imagine you have two 16 bits numbers you divide and you get an 8 bit result and a reminder ..

It's not "big precision" really and you always end up with a pure integer result ..

I have not worked that out yet ...

[EDIT] i.e. if I do "10/3" i get "3 with reminder 1" .. but if I am not wrong in 8.8 I shoud get as result 3.B ( i.e. 00000011 00001011 ) and that should be 3.04 which is 'wrong' but better than '3' alone.

Or something like that ...

[edit2] actually no I should get "853" and that would be 3.34375 ..

[Dio]

I had a look at practicality when I was fiddling with 8-bit-RISC designs. Firstly, multicycle multiply instructions are a terrible fit for RISC (so don't; with a good multiply algorithm and a loopmode buffer you can get 60-odd cycle 8x8 multiply) .

The Z80 could pretty easily have added something close to it. Compare LDIR; implementing something similar but doing a single MUL iteration ( srl a; if cs, add hl,de; if a!=0, pc-2, sla e, rl d, if cs set v; ) in 16-24 cycles for a <200 cycle multiply (it's ~500 cycles usually, so this is quite a bit faster). 8x16->32 would also have been possible, and with a few ALU tweaks it might have been closer to 10 cycles per iteration. But they didn't.

[gilesgoat]

Yesterday after "big reasoning" ( while writing stuff on a bit of TP ) I tihnk I realized "what I am doing wrong with my division", I'll have to modify it, but I think to get "a decent precision" what I need is more bits.

I am curious to see where 8.8 gets you "graphically" but I already suspect a 16.16 is the minimal necessary.

My idea in a "test setup" is to make a small Matrix/Vector multiplier "with that logic" and see what actual results you may really get.

Then if it really goes anywhere I'd like to try a VHDL implementation and see if I can make it work for real

[KlaxonCow]

And, of course, in binary, doubling is just shifting all the bits one to the left and halving is just shifting all the bits one to the right.

So the algorithm is dead simple.

First, we need a running total. Initialise this to zero. Note that the size of this "total" variable only needs to be double the size of the numbers you're multiplying (so if it's 8-bits * 8-bits, then the result will always fit within 8 * 2 = 16 bits).

Take the first number - we'll call it A - and then shift it right. The lowest bit will, on most CPUs, be shifted into the carry bit. So we can "shift right, branch on carry" to tell if it's a one or a zero.

If it's a one, then add B to the running total. Then we shift B left to double it, and this is our new B (B needs to also be twice as big - 16-bits for an 8-bit multiply - to not lose bits out the other end).

And that's it. Just rinse and repeat that until you've shifted out all the bits of A, and the running total is your answer.

It's only halving and doubling - which is just bit shifting in binary - and addition.

The problem, though, is that though this is a dead simple algorithm, it's a loop. So you've got to repeat this at least 8 times for an 8-bit number or 16 times for 16-bit numbers and so forth.

In theory, you could create an absolute massive circuit that does all this as (nominally) "a single operation" - an "unrolled loop" in the silicon itself, not looping around but actually just doing it 8 times in a row. But - certainly for the 8-bit era - that's ridiculous amount of transistors to waste on a single instruction (and it's the polar opposite of RISC to do it like that).

So, yeah, as far as I'm aware - from everything I've encountered - there is no 8-bit CPU that did this.

And I think it all just boils down to "transistor budget" (vs. cycle count). I mean, you've got two shift instructions, a "branch on carry" and an "add" in each step, which you're doing at least 8 times - and then all the not-trivial "overhead" of wiring up all the bits to the right places. Or, even if you want to simplify it by not "unrolling" that loop, then you've got that one step (shift, branch, add, shift) but then you're asking the CPU to run it in a loop at least 8 times (so now you're haemorrhaging cycles instead of transistors).

It's asking too much of a humble 8-bit, I fear.

Basically, you'd have this 8-bit chip with its amazing multiply instruction. "Can it do anything else?" Umm, no, not really. We ran out of transistors.


p.s. Technically, all of them could do multiplication and (integer) division by powers of two. Just bit shifting. It's multiplying by any arbitrary numbers where it gets complicated.

[gilesgoat]

In theory, you could create an absolute massive circuit that does all this as (nominally) "a single operation" - an "unrolled loop" in the silicon itself, not looping around but actually just doing it 8 times in a row. But - certainly for the 8-bit era - that's ridiculous amount of transistors to waste on a single instruction (and it's the polar opposite of RISC to do it like that).

And in practice too, I am sure Dio knows all this very well.

I read there are probably "countless algorithms to do multiplications" ( or at least quite many ) , what you say "all in one go" I read can be obtained by things called "Wallace Trees" or "Dadda Trees" or "Barrel Shifters" ( a combination of all of them ) you could think at them more or less like "an array of adders in cascade".

Yes they do require "massive amount of gates/transistors/silicon space" also then you have to start carefully keeping into account "gate delays" and such.

To me an N*N multiplication algo that requirtes N steps and 2*N bits adder/accumulator "is not too bad" means that if you are multiplying two 16x16 bits you need 16 cycles of shift/if/add and a on a 32 bits result, as I said and in the "code" I posted I am trying to do some "simulation" to see if I could really implement it into HW and see what I can get out.

Basically turns out I'd need a 32 bits full-adder with carry ( which is some AND/XOR gates ) two 32 bits "registers" that can be also at the same time shift-registers, one 4 bits counter and some little logic, I have to really try once to put it all togheter ( in VHDL ) and see how much it takes ( in terms of 'cells' ) to synthesize it.

Division is "similar" with a subtractor/other logic.

What is "amazing" you say "too complex for an 8 bits cpu", true, but things like the CDC6000 ALREADY had FLOATING POINT with sum, mul, division,"all you need" and those were REALLY made with DISCRETE transistors and still were "not huge" you could have fitted it in a not that big room.

I'd wish I could see the schematics of a CDC6000, I'd be very curious to see how they implemented such featrues.

Must have use "really strange optimisations" ( HW optimisations ).

[edit] - unfortunately NO Transistor Level schematics but ( for the brave ) : http://www.bitsavers.org/pdf/cdc/cyber/ ... _Aug78.pdf

[Dio]

The Z80 was basically the transistor limit for a mid-70s cheap microprocessor at about 8k. You can't fit a one-cycle multiplier in there, it's just not possible.

You probably could do an 8-bit barrel shifter though. I mean, consider the ARM, which had a full 32-bit ALU with barrel shifter in about 25k transistors; an 8-bit version would probably have been possible in 8k.

My 8-bit RISC design (based loosely on RISC-ifying the Z80) reckons it's possible to squeeze in an 8-bit ALU with barrel shift, ~256 2r1w register bits and 8 bytes of prefetch queue with memory and DMA controller; the Z80 already has this many register bits (albeit single-port, and only a 4-bit ALU) and it's is well over half decode and sequencer, so there's lots of spare area there.

[gilesgoat]

OK "this is it" I take it as a challenge "do that damned multiplier in VHDL and see if it really works as you think it should" ..

I may be limited to 8x8 if I want to make one "on real HW" but I'll do in the VHDL source so it's scalable to NxN bits ..

"Has to be done"

[edit] - in VHDL I can always simulate the HW and see results even without the need to phisically build it.

[venusian]

It's not 'classic', arriving in 1997, but the 8 bit Atmel AVR has a handful of multiply instructions.

It also has a rather fabulous DMA/IO/interrupt system that could have been the interesting basis for a games machine.

[KlaxonCow]

The Z80 was basically the transistor limit for a mid-70s cheap microprocessor at about 8k. You can't fit a one-cycle multiplier in there, it's just not possible.

Yeah, that was my suspicion. Though, you know, you're the one who can actually speak with some practical authority on this, I was just guessing, from theory, that that's probably the likely reason.

You probably could do an 8-bit barrel shifter though.

But I'm thinking that would just be trading transistors for clock cycles.

Because you could have that one "step" in a loop 8 times. But then we need to sync this all up, so - I'm imagining - you've got to make sure that the "step" is fully complete, before you go back up and loop again. Using the last step's output as the next step's input. So, at the very least, that's 8 "ticks" of the clock.

And the clock cycles do matter, in that if your single multiply instruction takes a stupid number of clock cycles to complete, there's a good argument that you're better off not having it. You're wasting a ton of transistors on something that can, strictly, be "done manually".

(And there are optimisations possible when doing it manually. Like, as mentioned, multiplication and division by powers of two is, in fact, already a single instruction - just a bit shift - so, with certain known numbers, you can beat a generic multiplier. For example, you know you want to multiply things by 40 or 80 - because it's to calculate screen positions on a 40 / 80 column display - but you'd be better off doing (32 * A) + (8 * A), which is the same thing as (40 * A), but you can do multiplication by powers of two by just shifting bits. Or if you've got to do both 40 and 80, calculate "times 40" and then bit shift it once to get the "times 80" result. Like, if you know, in advance, what one of the numbers is going be - it's not a multiplication by any old arbitrary numbers - then you'll have a way to get the answer with way less steps, if you're being clever about it.)

But, well, I mean, it's the RISC vs. CISC argument in a nutshell, isn't it?

The RISC argument that it's better, overall, to have a bunch of super-fast single-cycle "primitive" instructions and then "roll your own" complex multiply instruction out of those, than to cram the chip with big complex instructions that eat transistors and clock cycles for breakfast.

And, as we all know, RISC architecture is going to change everything, because RISC is good:

[KlaxonCow]

OK "this is it" I take it as a challenge "do that damned multiplier in VHDL and see if it really works as you think it should" ..

Good luck.

Because, yeah, I'd also love to know exactly what's involved, as I've never actually, you know, built my own multiply instruction in hardware for real (I'd hazard a guess that very few people actually have). So report back.

I've covered how it would work, in theory, and it's not an inherently complex procedure. But I do think that, once you start doing it with logic gates and transistors, trying to cram it all into a single cycle instruction, it'll explode in size.

Because, like, at every step, you've got a full addition in there (to tally up your "running total" as you go along). And if you're doing a 8 * 8 multiply, the addition needs to be a 16-bit addition (for the same reason why B and "running total" also need to be twice the size, to be big enough to hold all possible answers).

So, you know, if you're "unrolling" this - no barrel shifting but laid out as one big circuit - then you've got to have eight 16-bit additions inside this single multiply instruction.

It's all very possible - I've basically already given the recipe, with some help from Johnny Ball - but I fear that it'd explode in size very rapidly.

And if your transistor budget is a max of 8K, as Dio says, then it's way too many transistors to use up on a single CISC instruction.

But, that said, if you've got today's transistor budgets then have at it. A single cycle multiply on an 8-bit would have been the thing of dreams in the '80s, yeah?

[Dio]

But I'm thinking that would just be trading transistors for clock cycles.

Well, if you're trying to do something RISC-y, you kind of don't have a choice. If you want to aim for one instruction per clock, you need a bit of prefetch, a pipeline, everything to run single cycle, and no side effects. So you either do one shift per clock or a barrel shifter.

But compared to a multiplier a barrel shifter really isn't that bad. In 8 bit it's just 60-odd pass transistors and maybe a few buffer amps. While a single-cycle multiplier is a lot of adders and even if you avoid carry propagation the number of stages means all sorts of propagation delay issues (or a pipelined ALU).

Frankly, it's not worth it. Multiplies aren't that common. The 68000 had the right compromise - use the facilities of the chip to implement the multiply in the fewest cycles possible. A RISC design means you can do that in code, not in microcode.

[gilesgoat]

After much thinking in the "meditation room" I came out with a couple of designs I am still finishing/working on it ..

We'll see if anything will come out from the VHDL synthesis ...

[gilesgoat]

"I am working on it" .. but I won't publish anything until I got something that works ...