Last visit was: Fri Jul 19, 2024 5:36 am
It is currently Fri Jul 19, 2024 5:36 am



 [ 54 posts ]  Go to page Previous  1, 2, 3, 4
 Astorisc : A pipelined Risc-V from scratch ? 
Author Message

Joined: Thu Feb 25, 2021 8:27 am
Posts: 32
Location: Belgium
Thank you!
I knew about Booth's algorithm and quickly rejected it because it would have been impractical to build using discrete components, but I hadn't realized there was this radix-4 variant. I'll definitely try and grok it!
At first glance, it looks like I'd need some setup circuitry to encode the multiplicand.
A shifter is quite easy and not too expensive to build with only two pairs of 16-bit buffers (one of them being active at a time while the other one is 3-stated), so not a big deal.
The adder would need to be expanded to handle subtraction as well, but again, that's not too difficult.

The difficulty, at least for me, will be to understand how the encoding of the operands will be affected by their "signedness".
There are four different multiplication instructions in RV32, and I intend to implement them all.
  • MUL returns the lower 32 bits of the result, that's the easy one :)
  • MULH returns the upper 32 bits of the full product for signed × signed,
  • MULHU returns the upper 32 bits for unsigned × unsigned
  • MULHSU returns the upper 32 bits for signed × unsigned.
The last one, MULHSU, is useful to implement multi-word multiplication.

In any case, it looks very promising, thanks again.

Now, I haven't even started implementing support for multi-cycle instructions in the Execute stage of the pipeline, who knows what corner-cases I'll discover there :D

_________________
https://www.alrj.org/pages/Astorisc.html


Wed Apr 05, 2023 7:36 am WWW

Joined: Mon Oct 07, 2019 2:41 am
Posts: 619
Some where in the old BYTES I read about a hardware version for the 6800. The got ya there, was a -1 argument.
Some thing like a * b -> h,l as hardware ports. if a was -1 you had to swap a and b.
Check that your version does not have that problem.
Ben.
PS.Byte Magazine Volume 02 Number 07 The old brain cells are not what they used to be.
Regular multiply. Booth's version may be software.6809? I do remember it had bug.
PPS.
Byte Magazine Volume 03 Number 04 software
Byte Magazine Volume 03 Number 05 hardware chip


Wed Apr 05, 2023 9:16 pm

Joined: Sun Mar 27, 2022 12:11 am
Posts: 41
alrj wrote:
The difficulty, at least for me, will be to understand how the encoding of the operands will be affected by their "signedness".
There are four different multiplication instructions in RV32, and I intend to implement them all.
  • MUL returns the lower 32 bits of the result, that's the easy one :)
  • MULH returns the upper 32 bits of the full product for signed × signed,
  • MULHU returns the upper 32 bits for unsigned × unsigned
  • MULHSU returns the upper 32 bits for signed × unsigned.

I thought I had some information clearly explaining how the radix-4 version of modified Booth worked, but I can't find it now. So I'm not 100% sure, but the unsigned version might need some extra adder and or multiplicand bits.

At least I think the unsigned multiply might need to be treated as signed multiply.


Thu Apr 06, 2023 3:59 am

Joined: Mon Oct 07, 2019 2:41 am
Posts: 619
Perhaps a 16 bit unsigned multiply for address indexing like foo[a,b] and general purpose multiply later
be designed.


Thu Apr 06, 2023 4:16 am

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1789
I think the usual approach is to record the signs, make things positive, do the multiplication, and then fixup the sign. But be sure to test for edge cases! (I'm a bit worried about MININT, which you can't make positive...)


Thu Apr 06, 2023 6:51 am

Joined: Thu Feb 25, 2021 8:27 am
Posts: 32
Location: Belgium
oldben wrote:
Byte Magazine Volume 03 Number 04 software
Byte Magazine Volume 03 Number 05 hardware chip

I'll definitely have a look at these Byte articles, thank you for looking up the references.

oldben wrote:
Perhaps a 16 bit unsigned multiply for address indexing like foo[a,b] and general purpose multiply later
be designed.

Well, in this project, the instruction set is already defined, it's the RISC-V one. Fortunately, it means that I can perfectly leave the multiply out for the moment, as it is an optional extension to the ISA :)

DockLazy wrote:
I thought I had some information clearly explaining how the radix-4 version of modified Booth worked, but I can't find it now. So I'm not 100% sure, but the unsigned version might need some extra adder and or multiplicand bits.

At least I think the unsigned multiply might need to be treated as signed multiply.

BigEd wrote:
I think the usual approach is to record the signs, make things positive, do the multiplication, and then fixup the sign. But be sure to test for edge cases!

Perhaps it's only a matter of doing a sign- or a zero-extension of the operands accordingly?

Anyway, I'll leave the multiply for later.

At the moment I'm a bit overwhelmed by the intricate dependencies between the CSRs (some of which are also memory-mapped!), the interrupts, exceptions, and the pipeline.
I'm realizing that the CSRs as specified in RISC-V are not exactly simple to implement for somebody like me with no experience! For instance, the ones that are memory-mapped need two distinct read ports, since one of them could be loaded in the Decode (or Execute) stage on a CSRR* instruction, while also being read by a Load instruction in the Memory stage...
Plus all the "magic" that must happen when entering or leaving a trap handler...
For a processor built from discrete logic, that won't be a small piece.

_________________
https://www.alrj.org/pages/Astorisc.html


Thu Apr 06, 2023 7:04 am WWW

Joined: Sun Mar 27, 2022 12:11 am
Posts: 41
BigEd wrote:
I think the usual approach is to record the signs, make things positive, do the multiplication, and then fixup the sign. But be sure to test for edge cases! (I'm a bit worried about MININT, which you can't make positive...)
Booth's algorithm works natively with signed integers. Odd one out here are unsigned integers.

The problem here is I'm unsure if having an unsigned integer stick a bit in the sign slot will break the algorithm or not.


Fri Apr 07, 2023 2:27 am

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1789
I stand corrected!


Fri Apr 07, 2023 8:04 am

Joined: Wed Apr 24, 2013 9:40 pm
Posts: 213
Location: Huntsville, AL
I have not been following this thread closely. However, the discussion about multiplication utilizing Booth’s algorithm struck a chord. Its correct signed integer multiplication is natively supported by Booth’s. For this to occur, a sticky guard bit is added on the left. I’ve previously reasoned out the modification required for Booth’s to correctly and fully handled unsigned multiplication. That is, extend the length off the operants by 1 bit on the left, and then apply Booth’s. The resulting product will be correct for all 2n LSBs of the resultant. Assuming a 1-bit Booth’s implementation, the modification to support unsigned operants will require 1 additional cycle compared to the version supporting n-bit signed operants.

I think a similar modification, padding / extending the operants on the left, can be used when Booth’s algorithm is computed using 2 or more bits per cycle. My GitHub repo has some of these algorithms implemented in Verilog. The embedded comments may be helpful.

_________________
Michael A.


Fri Apr 07, 2023 8:06 am
 [ 54 posts ]  Go to page Previous  1, 2, 3, 4

Who is online

Users browsing this forum: CCBot and 0 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software