[Oberon] Fwd: Re: FPGA - RISC multiply/divide

[Skulski, Wojciech]

Tomas:

  it is an interesting topic. Some good reading is provided in Xilinx Data Sheets for the "LogiCORE IP Divider and Generator" v3.0 (Data Sheet DS530.pdf) and v4.0 (Xilinx Data Sheet DS819.pdf). The 3.0 core is probably more relevant to RISC5, because it assumes no particular interface. The 4.0 core is AXI4, which would need to be "wrapped" into some RISC5-compatible VHDL. 

These IP cores are provided by the Core Generator. Using them requires quite a bit of knowledge. The cores can be clocked up to some fairly high clock frequency (between 150 and 400 MHz), what would allow for overclocking relative to the other parts of the design. This technique may sound a bit advanced for a beginner. In any case, the data sheets are worth reading if one is venturing into this territory. The algorithms are well explained, as well as the possible implementations.

Wojtek

________________________________________
From: Oberon [oberon-bounces at lists.inf.ethz.ch] on behalf of Walter Gallegos [waltergallegos at vera.com.uy]
Sent: Friday, May 26, 2017 7:51 AM
To: ETH Oberon and related systems
Subject: [Oberon] Fwd: Re:  FPGA - RISC multiply/divide

Tomas,

No magic, moderns FPGA have DSP blocks with dedicated hardware multipliers in silicon, on the other hand division need be implement into the logic farm; using one of the well know algorithms to keep logic resources within reasonable limits.

Simulator waveforms show the process, 11 divided by 3, quotient = 3 remainder = 2;  one clock period for bit.

[cid:part1.BE49F20D.8FF3FF57 at vera.com.uy]

In practise,  one clock for setting up values, results can be read one clock after calculus done; so, divide a 32 bit number use 34 clocks. Waveforms correspond to our own VHDL version of RISC-5.

Walter,

El miércoles-2017-05-24 a las 13:21, Tomas Kral escribió:

Hi,

This example of binary multiply needs >>>fixed size font<<< to display
properly.

[a] Shift & addition

   0101    =5(4+1)
   0101 x  =5(4+1)
_________

   0101
  0000     shift
 0101      shift
_________
           add above
 011001    =25(16+8+1)


[b] Repeated addition, 5+5+5+5+5

   0101
   0101
   0101
   0101
   0101
__________

 011001    =25(16+8+1)


To multiply 32 bit integers upto 32 cycles are needed. There is some
FPGA magic used, to complete each `MUL'tiply in two cycles only.

How many cycles does `DIV'require?
Looking for the above analogy.

Tomas


On Tue, 23 May 2017 12:36:04 +0200
Tomas Kral <thomas.kral at email.cz><mailto:thomas.kral at email.cz> wrote:



Hi Joerg,

Multiplication ~ repeated addition
Division ~ repeated subtraction

That is a simplification but is not the way implemented in RISC.
Consider 65536 DIV 1, that would require 65536 iterations.

Instead shift (left | right) + (add | sub) is used for DIV and MUL.
This requires much fewer iterations.

My argument is right about the example given in the 16.2.3.

14 DIV 4, is 3 with remainder 2

But the example gives 4 and the remainder 2

Tomas


On Tue, 23 May 2017 11:23:14 +0200
Jörg <joerg.straube at iaeth.ch><mailto:joerg.straube at iaeth.ch> wrote:



Tomas

http://www.homeschoolmath.net/teaching/md/division-repeated-subtraction.php<https://urldefense.proofpoint.com/v2/url?u=http-3A__www.homeschoolmath.net_teaching_md_division-2Drepeated-2Dsubtraction.php&d=DwMDaQ&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r=uUiA_zLpwaGJIlq-_BM9w1wVOuyqPwHi3XzJRa-ybV0&m=RET5JAI6kmjapOT0JjD_eLkYvSskDaSwgN6SCTV5Ceg&s=t9OrmOG5nMEDjFLbAHszSE-VGaWPaG1BmZoXk-rTXgQ&e=>

Jörg



Am 23.05.2017 um 11:09 schrieb Tomas Kral <thomas.kral at email.cz><mailto:thomas.kral at email.cz>:

Hi,

I am reading chapters on RISC implementation. I managed to
understand multiplication - `MUL' instruction, consisting of
shifting x and adding y to the product.

I seem not understanding the division, chapter 16.2.3.
In the example for x=14, y=4 gives quotient q=4, and the remainder
r=2.

But...
q = x DIV y = 3, r = x MOD y = 2
???

--
Tomas Kral <thomas.kral at email.cz><mailto:thomas.kral at email.cz>
--
Oberon at lists.inf.ethz.ch<mailto:Oberon at lists.inf.ethz.ch> mailing list for ETH Oberon and related
systems https://lists.inf.ethz.ch/mailman/listinfo/oberon<https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.inf.ethz.ch_mailman_listinfo_oberon&d=DwMDaQ&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r=uUiA_zLpwaGJIlq-_BM9w1wVOuyqPwHi3XzJRa-ybV0&m=RET5JAI6kmjapOT0JjD_eLkYvSskDaSwgN6SCTV5Ceg&s=BZVgyQk3qDd3V8sH6aTnQM4odJoRVrvHo66_EV9GIWg&e=>










-------------- next part --------------
A non-text attachment was scrubbed...
Name: ATT00001.png
Type: image/png
Size: 21238 bytes
Desc: ATT00001.png
URL: <http://lists.inf.ethz.ch/pipermail/oberon/attachments/20170528/8119b059/attachment.png>