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

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

Astorisc : A pipelined RiscV from scratch ?
Author 
Message 
alrj
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 radix4 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 16bit buffers (one of them being active at a time while the other one is 3stated), 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 multiword multiplication. In any case, it looks very promising, thanks again. Now, I haven't even started implementing support for multicycle instructions in the Execute stage of the pipeline, who knows what cornercases I'll discover there

Wed Apr 05, 2023 7:36 am 


oldben
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 


DockLazy
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 radix4 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 


oldben
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 


BigEd
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 


alrj
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 RISCV 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 radix4 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 zeroextension 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 memorymapped!), the interrupts, exceptions, and the pipeline. I'm realizing that the CSRs as specified in RISCV are not exactly simple to implement for somebody like me with no experience! For instance, the ones that are memorymapped 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.

Thu Apr 06, 2023 7:04 am 


DockLazy
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 


BigEd
Joined: Wed Jan 09, 2013 6:54 pm Posts: 1789

I stand corrected!

Fri Apr 07, 2023 8:04 am 


MichaelM
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 1bit Booth’s implementation, the modification to support unsigned operants will require 1 additional cycle compared to the version supporting nbit 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 

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

