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

[Walter Gallegos]

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.

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>  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>  wrote:
>>
>>> Tomas
>>>
>>> http://www.homeschoolmath.net/teaching/md/division-repeated-subtraction.php
>>>
>>> Jörg
>>>
>>>> Am 23.05.2017 um 11:09 schrieb Tomas Kral<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>
>>>> --
>>>> Oberon at lists.inf.ethz.ch  mailing list for ETH Oberon and related
>>>> systemshttps://lists.inf.ethz.ch/mailman/listinfo/oberon
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.inf.ethz.ch/pipermail/oberon/attachments/20170526/5135794d/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/png
Size: 21238 bytes
Desc: not available
URL: <http://lists.inf.ethz.ch/pipermail/oberon/attachments/20170526/5135794d/attachment.png>