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. 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@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@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@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@email.cz> -- Oberon@lists.inf.ethz.ch mailing list for ETH Oberon and related systemshttps://lists.inf.ethz.ch/mailman/listinfo/oberon
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@lists.inf.ethz.ch] on behalf of Walter Gallegos [waltergallegos@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@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@email.cz><mailto:thomas.kral@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@iaeth.ch><mailto:joerg.straube@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@email.cz><mailto:thomas.kral@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@email.cz><mailto:thomas.kral@email.cz> -- Oberon@lists.inf.ethz.ch<mailto:Oberon@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=>
On Sun, 28 May 2017 20:04:21 +0000 "Skulski, Wojciech" <skulski@pas.rochester.edu> wrote:
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.
I see 34 clocks, so `DIV' is the lengthiest RISC instruction, so it seems. -- Tomas Kral <thomas.kral@email.cz>
Tomas: not only is DIV the longest instruction, but also its timing depends on the arguments. I think that the DIV hardware should be treated like a peripheral rather than a genuine part of RISC5 CPU. Working with such a peripheral, you write the operands to the memory registers, and a while later you read the result from another register. Note that the DSP slice, which is now a standard part of any newer CPU, is capable of more than just DIV. Have a look at Spartan-6 DSP48A1 Slice Description, User Guide UG389. These beasts are highly configurable. Even more important, their features keep evolving. The Spartan-3 multiplier, which was capable of basically one thing, has now evolved into a complicated coprocessor capable of many other things. IMHO, trying to catch up with all these capabilities by adding them to the language is going to fail, because it is a moving target, which depends on the FPGA generation and the FPGA vendor. IMHO, a safer approach is to move the advanced numerics away from the language proper into the application domain. This leaves us with a question what to do with DIV. Is it appropriate to define DIV in the language and implement it with fabric logic without using the DSP slices? One can let DIV become a part of the official RISC5, if it is not done already. In such a way the problem is solved at the lowest denominator level, while advanced numerical applications can use DSP slices as peripherals. Wojtek ________________________________________ From: Oberon [oberon-bounces@lists.inf.ethz.ch] on behalf of Tomas Kral [thomas.kral@email.cz] Sent: Monday, May 29, 2017 8:45 AM To: oberon@lists.inf.ethz.ch Subject: Re: [Oberon] Fwd: Re: FPGA - RISC multiply/divide On Sun, 28 May 2017 20:04:21 +0000 "Skulski, Wojciech" <skulski@pas.rochester.edu> wrote:
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.
I see 34 clocks, so `DIV' is the lengthiest RISC instruction, so it seems. -- Tomas Kral <thomas.kral@email.cz> -- Oberon@lists.inf.ethz.ch mailing list for ETH Oberon and related systems https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.inf.ethz.ch_mailman_listinfo_oberon&d=DwICAg&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r=uUiA_zLpwaGJIlq-_BM9w1wVOuyqPwHi3XzJRa-ybV0&m=xHNydlE_wv2InbWzIpsa5jGUqldG6kdWndIncBClo2w&s=pwZHzW52ZFR8_OLbnOw4O4OF4j1K6nq-oStymO9dFPo&e=
On Mon, 29 May 2017 15:32:45 +0000 "Skulski, Wojciech" <skulski@pas.rochester.edu> wrote:
Working with such a peripheral, you write the operands to the memory registers, and a while later you read the result from another register. Hi, this is how `FPU' works?
-- Tomas Kral <thomas.kral@email.cz>
We are playing on the FPGA arena; DIV and others maths can be implemented from fully parallel to fully serial. Implemented fully parallel each DIV need zero clocks cycles, results are available before next clock edge; implemented as fully serial each DIV need word width plus two clock cycles. In middle the designer have some divide and conquer techniques. Off course, consumed resources and max operation frequency are implementation's dependant. MUL is another simple example, can be described in VHDL as y <= x * m; The implementation tool understand that need instantiate the multiplier inside of DSP block, this simple description has several speed penalties; for speed up the multiplication the designer add pipeline registers but pipeline registers add clocks delays. This is the game in FPGA arena. As Wojtek say; FPGA DSP blocks are powerful marvels that can build for example symmetric filters with peak performance over 4500 GMAC; compare with 30 GMAC of mulit-core DSP architectures. About move some maths outside of RISC5; our VHDL versions do not have floating point support, as our main maths process are in hardware and use binary fixed point we limit our software to integers. Following this line, IMHO would be more interesting to have a read instruction pair to provide blocking/non blocking read support than the DIV instruction. With this pair of instructions, the designer writes to value into a register and can select whether or not the CPU waits for the result. Walter El lunes-2017-05-29 a las 12:32, Skulski, Wojciech escribió:
Tomas:
not only is DIV the longest instruction, but also its timing depends on the arguments. I think that the DIV hardware should be treated like a peripheral rather than a genuine part of RISC5 CPU. Working with such a peripheral, you write the operands to the memory registers, and a while later you read the result from another register. Note that the DSP slice, which is now a standard part of any newer CPU, is capable of more than just DIV. Have a look at Spartan-6 DSP48A1 Slice Description, User Guide UG389. These beasts are highly configurable. Even more important, their features keep evolving. The Spartan-3 multiplier, which was capable of basically one thing, has now evolved into a complicated coprocessor capable of many other things. IMHO, trying to catch up with all these capabilities by adding them to the language is going to fail, because it is a moving target, which depends on the FPGA generation and the FPGA vendor. IMHO, a safer approach is to move the advanced numeric s away f rom the language proper into the application domain.
This leaves us with a question what to do with DIV. Is it appropriate to define DIV in the language and implement it with fabric logic without using the DSP slices? One can let DIV become a part of the official RISC5, if it is not done already. In such a way the problem is solved at the lowest denominator level, while advanced numerical applications can use DSP slices as peripherals.
Wojtek
________________________________________ From: Oberon [oberon-bounces@lists.inf.ethz.ch] on behalf of Tomas Kral [thomas.kral@email.cz] Sent: Monday, May 29, 2017 8:45 AM To: oberon@lists.inf.ethz.ch Subject: Re: [Oberon] Fwd: Re: FPGA - RISC multiply/divide
On Sun, 28 May 2017 20:04:21 +0000 "Skulski, Wojciech" <skulski@pas.rochester.edu> wrote:
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. I see 34 clocks, so `DIV' is the lengthiest RISC instruction, so it seems.
-- Tomas Kral <thomas.kral@email.cz> -- Oberon@lists.inf.ethz.ch mailing list for ETH Oberon and related systems https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.inf.ethz.ch_mailman_listinfo_oberon&d=DwICAg&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r=uUiA_zLpwaGJIlq-_BM9w1wVOuyqPwHi3XzJRa-ybV0&m=xHNydlE_wv2InbWzIpsa5jGUqldG6kdWndIncBClo2w&s=pwZHzW52ZFR8_OLbnOw4O4OF4j1K6nq-oStymO9dFPo&e= -- Oberon@lists.inf.ethz.ch mailing list for ETH Oberon and related systems https://lists.inf.ethz.ch/mailman/listinfo/oberon
-- Walter Daniel Gallegos Programmable Logic & Software Consultoría, Diseño, Entrenamiento. Montevideo, Uruguay EMAIL walter@waltergallegos.com Tel +598 26 23 44 60 | Cel +598 99 18 58 88 El presente correo y cualquier posible archivo adjunto está dirigido únicamente al destinatario del mensaje y contiene información que puede ser confidencial. Si Ud. no es el destinatario correcto por favor notifique al remitente respondiendo anexando este mensaje y elimine inmediatamente el e-mail y los posibles archivos adjuntos al mismo de su sistema. Está prohibida cualquier utilización, difusión o copia de este e-mail por cualquier persona o entidad que no sean las específicas destinatarias del mensaje. This e-mail and any attachment is confidential and is intended solely for the addressee(s). If you are not intended recipient please inform the sender immediately, answering this e-mail and delete it as well as the attached files. Any use, circulation or copy of this e-mail by any person or entity that is not the specific addressee(s) is prohibited.
participants (3)
-
Skulski, Wojciech -
Tomas Kral -
Walter Gallegos