Number-theoretic FPGA function implementation suggestions? - Page 2

rdotson · 2005-09-24, 08:03

Please delete the comment from divider.v that says:

"// on *both* posedge and negedge of clock"

I use to actually use both clock edges, but found that it was a bad idea for reasons too lengthy to go into here.

-- Ron

jasonp · 2005-09-25, 00:54

Quote:

Originally Posted by rdotson

That sounds like it might be an excellent application for an FPGA Jason, and in fact I believe it was my original question that I started this thread with.

If you happen to recall who the "somebody" was who has already implemented a first draft of it, please contact me because I would love to see what's already been done before I spend to much time on it. I have no desire to waste my time reinventing the wheel.

See http://klabs.org/mapld04/presentatio...0_craven_s.ppt

All elements in the transform should be modulo 2^64-2^32+1, and you can choose a primitive root for this prime such that many of the modular multiplications are modular shifts by a constant. In an FPGA implementation arithmetic modulo this prime would be incredibly fast, especially if your implementation is bit-serial like you're suggesting.

Quote:

Originally Posted by rdotson

In any case however, if you or anyone could point me to an example of a working program that implements an FFT using modular math that's written in a conventional programming language, then I'll be happy to give it a try provided it looks do-able to me. I need a conventional program to start with so that I have a baseline against which I can test my Verilog code output, and to generate test cases, and to generate intermediate results for debugging.

I don't think there's a single package that does everything. Here are some suggestions:

Years ago I wrote an integer convolution library (www.boo.net/~jasonp/icl11.tar.gz) optimized for the alpha. It has all the small steps of what I believe a high-performance big integer FFT would need, and also contains a complete LL test demo. However, it doesn't use the above prime, and has loads of assembly language intended for the alpha.

Mikko Tommila's apfloat library should be portable, and does have transforms with the above prime. See www.apfloat.org. His page used to have a high-level description of how number-theoretic FFTs work, which was very helpful for me.

Finally, Nick Craig-Wood has written a package for the ARM that uses this prime. The source code has loads of comments on exactly how the fast arithmetic is supposed to work (PM me if you want the source).

I don't know verilog, but I've thought a lot about doing something like this in hardware. If you want more technical pointers we can discuss them off-list.

jasonp

rdotson · 2005-09-25, 02:47

WOW, Jason - you've given me an incredible amount of information to work with! Thank you. It may be sometime before you hear from me again because it's going to take awhile for me to digest it all, but I will PM you with my email address because I would like the source code for the Nick Craig-Wood ARM package if possible. I've always felt that it's best to have too much information rather than too little, since I can always discard what isn't revelevent/interesting.

-- Ron

================================
P.S.

Here is a Pop Quiz for anyone who may have actually downloaded my Verilog IGCDEX code and tried it out:

1. For 10 points: Which of the four test cases in "testIgcdex.v" fails?

2. For 10^[(10)^100] points: Fix the bug and send me the revised code!

(I do have an older version that works in all test cases, but it uses both clock edges and slows the entire circuit down by 50%)

Peter Nelson · 2005-09-25, 04:19

Re: "attempt to turn us into VLSI hardware designers"

.... some of us already are! ROFL

Re: no operating system on FPGA

Why not?

If its a xilinx Virtex 2 pro or virtex 4 fx it has powerpc cores, and you can use ram to store a rudimentary OS.

If its pretty much any Xilinx FPGA you can run KCSM1/2/3 mini processor (finite state machine based which runs SHORT programs).

You can graduate to microblaze, a processor design in hardware from the same author which even may run compiled linux.

Interfacing to a harddrive making an IDE interface is not too difficult and there is some simple code to read the first file of a FAT volume into your chip available on opencores site. You can make a bootstrap loader in the on-chip block ram downloaded in the config bitstream, and then load your "real" os from disk using it.

Also plenty alternative microprocessor implementations for FPGAs eg emulate microchip pic compatible or RISC or ESA's LEO or whatever.

The neat thing about say picoblaze is you can add custom assembly instructions and interface them direct to the logic in the fpga. So a hybrid can be made of doing fast stuff in hardware and other in sw on fsm which would otherwise take too many gates of pure logic.

If you attach external DDR or DDR2 to your fpga and embed a memory controller into it you can do much nicer things.

Also if your device is large enough in gates you can paralellise your blocks to improve throughput. ie double up your logic to double your processing.

When you get hold of your development board, what size of device will it be (in gates, blocks etc), and which manufacturer's fpga? This might give people some idea of what size problem you could attempt to solve inside it. Does the board support some external memory?

Regards, Peter

On seeing this thread I was surprised it was in "the lounge".

I believe it would be much more appropriate under the "HARDWARE" heading (where some previous mention of fpgas has gone on).

Perhaps a nice moderator will relocate it for us.

akruppa · 2005-09-25, 07:13

This thread really belongs in the hardware forum. I'm moving it.

Alex

rdotson · 2005-09-25, 10:57

Thanks Alex for moving the thread. I probably should have put it here in the first place, but all the other threads (except for one other one that I started here previously) are about conventional computers as far as I can tell - which has nothing to do with true hardware level design.
==============================================

Hi Peter,

Thanks for your reply. I understand what you're saying, and in fact one of my last projects for my employer while I was still able to work was to write the firmware for an 8051 core embedded in an ASIC (yes, they could afford those things).

I guess it's really a question of point-of-view, so rather than try to respond to each of the specific products you mentioned, let me just try to convey to you the sort of "epiphany" I had about the subject, and why I think embedded microprocessor cores are a bad idea in general (there are always exceptions).

Please consider these two points:

1. You can do everything and much more in Verilog that you can do with the instruction set of a microprocessor.

2. You have a finite number of gates, or Logic Units (LUTs), or whatever to work with.

I agree that Verilog is much more tedious to code than microprocessor languages (for which there exist C and even C++ compilers), but I am extremely loath to sacrifice FPGA gates to implement a sequential CPU, and that's why I would never do it myself. What *would* make sense to me, and what I may very well do myself, is to use a standalone microcontroller to interface to two or three separate FPGA development boards so that it could orchestrate the top level of things and keep all the FPGAs busy all the time if possible. That way, the microprocessor wouldn't be wasting gates and LUTs inside your FPGAs and it could be used to easily interface to a regular PC.

At the moment however, I'm more interested in the algorithmic issues (interesting problems for implementation in generic Verilog HDL) rather than details of specific FPGAs - speaking of which:

Here is what I have on hand at the moment. When you read the specs for the first one be sure to put down your coffee first, otherwise you'll spill it all over your keyboard.

1. One Xilinx CPLD Design Kit that cost $49 and contains an XC2C256-7TQ144 CoolRunner-II CPLD and XC9572XL-10VQ44 CPLD. Stop Laughing! In my own defense, this was my very first FPGA board and I purchased it because it was cheap in order to decide whether I even wanted to attempt to program these things or not. For those not familiar with this device, neither of the CPLDs on the board have enough gates to do much more than flash LEDs.

2. One LatticeEC Standard Evaluation Board with a LFEC20E-5F484C-41 FPGA on it (that's not a typo by the way. That part number is directly from the silk screening on the FPGA even though the web page says the board comes with a LFEC20E-4F484C-41 device). This turned out to be an extremely poor choice, because although the FPGA is pretty roomy, there is no easy way to interface to the FPGA I/O pins (I would have to install pins in the prototyping holes and wire wrap them to my own connector). The only built-in I/O connector is for the PCI bus, which the board plugs into. The FPGA side of the PCI interface is pretty simple, but once upon a time I had the extremely unpleasant task of writing a device driver for Windows for a PCI board, and it was such an unpleasant experience I never want to repeat it. I have a book on writing Linux device drivers which I suspect is probably easier than for Windows, but still probably wouldn't be a walk in the park.

What I'm trying to order (if food were as difficult to purchase as Actel FPGAs are, everyone would have starved to death long ago!) is an Actel ProASIC3 Starter Kit with the A3PE600 part which contains 600K "system gates." I had so much trouble with Actel (they have no discernable customer support whatsoever) that I called up the old Actel sales rep for the company I used to work for and talked to him about it. It was an interesting conversation and he was very polite and wanted to be helpful, but neither he nor anyone else except AVNET is authorized to sell to individuals. Because of some type of blasted reorganization within Actel, the ONLY distributor for Actel development boards is AVNET. AVNET won't take my credit card number until they get a price check from the factory (the Actel sales rep had already told me the board was $350 and there is a two month wait for it). Anyhow, avoid AVNET and Actel both like the plague if you can. In my case however, their ProASIC3 is the biggest and baddest FPGA on the block that I can afford, and my preliminary fitter/mapper reports (I've been using their free Actel Libero® Integrated Design Environment tools even though I don't have their board yet) seem to indicate that unless I'm making some horrible mistake, it should be able to accommodate just about anything I can throw at it - er; download to it I mean.

Even though I've downloaded all the fancy free development software tools from all four major manufacturers (Altera, Actel, Lattice, Xilinx), I still mostly use the free Icarus simulator I mentioned earlier because it's quick and convenient for me. If I run into tough problems, I sometimes try one of the compilers for a specific device just to get better error messages, because each compiler/synthesizer seems to have it's own personality and quirks.

I guess that's all for now. I'm out of steam.

Regards,

Ron

rdotson · 2005-09-25, 11:15

That link to the Actel ProASIC3 starter kit should have been:
http://www.actel.com/products/tools/...tarterkit.aspx

Peter Nelson · 2005-09-25, 13:04

Ron, I have a Xilinx CPLD here from an old product and yes the gates were not that impressive quantity :-)

I agree with your thoughts on some embedded processors, however, there are exceptions as you say.

Ken Chapman (who works for Xilinx UK) wanted to get the best of both worlds so he designed a very compact (in terms of gates) microcontroller called KCSM (Ken Chapman State Machine). It is aka "PICOBLAZE" and has gone through versions 1,2,3. V3 is suitable for eg Spartan 3 and uses about 50 cents worth of the on board gates. (If you really wanted to you could put MANY of the KCSM onto a fpga, so only using one will not noticeably eat up your gate budget for other logic).

Now the catch, Picoblaze is FREE BUT only for running in Xilinx chips :-)

You may however find it illustrative to go and get the sources and see what he did (either for subsequent use on a Xilinx board you may buy) OR to design your own compact microcontroller. Just register with the Xilinx site (lots of good techie info). As part of the download process if asked for your Xilinx field application engineer's name just put "Ken Chapman" and it should work.

You will have heard of "marketing gates" that is you can't directly compare claimed gate counts between rival fpga vendors. eg Xilinx has some nice embedded multipliers, and lots of ram as distributed AND block ram. Others have different architecture.

So I dont know if your proasic3 board will be good or not.

That is IF you can get hold of it. A supplier of mine once made a mpeg playback hardware card using Actel fpga onboard.

Have you considered the widely available boards using Xilinx Spartan 3? They are easily within your budget meaning you could get a device with more gates.

The Xilinx toolset is free BUT will not work for the largest devices unless you pay more money. At present the largest Spartan 3 the free tools will work with is the XC3S1500 (see datasheet xilinx website).

I think Altera are also pretty good but have only little experience.

As you say ASIC is expensive (and getting more expensive in NRE costs as process geometry goes up).

However both Altera and Xilinx let you migrate your FPGA design to a kind-of-asic (Xilinx call theirs "Hardcopy") basically the config gets hard burned into the final layer of the chip.

This means a) you have much lower NRE costs than asic, but cheaper per unit chip cost than fpga. Additionally you dont need external configuration memory. Also the same design will run faster on these platforms.

I suggest that such process is achievable, unlike fullblown asic.

So, a math accelerator chip of some sort designed in fpga then migrated to such halfway house chip could be made in volume at reasonable cost.

If you want to see some idea of what you might put in it, try looking at www.clearspeed.com datasheets of the CSX600. (96 core math accelerator).

2005-09-24, 08:03	#12
rdotson Jul 2005 2³×5 Posts	P.S. Please delete the comment from divider.v that says: "// on both posedge and negedge of clock" I use to actually use both clock edges, but found that it was a bad idea for reasons too lengthy to go into here. -- Ron

2005-09-25, 11:15	#18
rdotson Jul 2005 40₁₀ Posts	Oops, correction That link to the Actel ProASIC3 starter kit should have been: http://www.actel.com/products/tools/...tarterkit.aspx

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Basic Number Theory 7: idempotents and Euler's function	Nick	Number Theory Discussion Group	17	2016-12-01 14:27
Suggestions on good number theory books???	Erasmus	Other Mathematical Topics	12	2010-04-13 23:33
Number Theoretic Transforms	paulunderwood	Software	7	2006-09-19 15:56
ECM/FPGA Implementation	rdotson	Hardware	12	2006-03-26 22:58
Search for a number theoretic function related to "prime divisor sums"	juergen	Math	2	2004-07-10 23:01

2005-09-25, 02:47	#14
rdotson Jul 2005 50₈ Posts	WOW, Jason - you've given me an incredible amount of information to work with! Thank you. It may be sometime before you hear from me again because it's going to take awhile for me to digest it all, but I will PM you with my email address because I would like the source code for the Nick Craig-Wood ARM package if possible. I've always felt that it's best to have too much information rather than too little, since I can always discard what isn't revelevent/interesting. -- Ron ================================ P.S. Here is a Pop Quiz for anyone who may have actually downloaded my Verilog IGCDEX code and tried it out: 1. For 10 points: Which of the four test cases in "testIgcdex.v" fails? 2. For 10^[(10)^100] points: Fix the bug and send me the revised code! (I do have an older version that works in all test cases, but it uses both clock edges and slows the entire circuit down by 50%)

2005-09-25, 04:19	#15
Peter Nelson Oct 2004 23² Posts	Re: "attempt to turn us into VLSI hardware designers" .... some of us already are! ROFL Re: no operating system on FPGA Why not? If its a xilinx Virtex 2 pro or virtex 4 fx it has powerpc cores, and you can use ram to store a rudimentary OS. If its pretty much any Xilinx FPGA you can run KCSM1/2/3 mini processor (finite state machine based which runs SHORT programs). You can graduate to microblaze, a processor design in hardware from the same author which even may run compiled linux. Interfacing to a harddrive making an IDE interface is not too difficult and there is some simple code to read the first file of a FAT volume into your chip available on opencores site. You can make a bootstrap loader in the on-chip block ram downloaded in the config bitstream, and then load your "real" os from disk using it. Also plenty alternative microprocessor implementations for FPGAs eg emulate microchip pic compatible or RISC or ESA's LEO or whatever. The neat thing about say picoblaze is you can add custom assembly instructions and interface them direct to the logic in the fpga. So a hybrid can be made of doing fast stuff in hardware and other in sw on fsm which would otherwise take too many gates of pure logic. If you attach external DDR or DDR2 to your fpga and embed a memory controller into it you can do much nicer things. Also if your device is large enough in gates you can paralellise your blocks to improve throughput. ie double up your logic to double your processing. When you get hold of your development board, what size of device will it be (in gates, blocks etc), and which manufacturer's fpga? This might give people some idea of what size problem you could attempt to solve inside it. Does the board support some external memory? Regards, Peter On seeing this thread I was surprised it was in "the lounge". I believe it would be much more appropriate under the "HARDWARE" heading (where some previous mention of fpgas has gone on). Perhaps a nice moderator will relocate it for us.

2005-09-25, 07:13	#16
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	This thread really belongs in the hardware forum. I'm moving it. Alex

2005-09-25, 10:57	#17
rdotson Jul 2005 2³·5 Posts	Thanks Alex for moving the thread. I probably should have put it here in the first place, but all the other threads (except for one other one that I started here previously) are about conventional computers as far as I can tell - which has nothing to do with true hardware level design. ============================================== Hi Peter, Thanks for your reply. I understand what you're saying, and in fact one of my last projects for my employer while I was still able to work was to write the firmware for an 8051 core embedded in an ASIC (yes, they could afford those things). I guess it's really a question of point-of-view, so rather than try to respond to each of the specific products you mentioned, let me just try to convey to you the sort of "epiphany" I had about the subject, and why I think embedded microprocessor cores are a bad idea in general (there are always exceptions). Please consider these two points: 1. You can do everything and much more in Verilog that you can do with the instruction set of a microprocessor. 2. You have a finite number of gates, or Logic Units (LUTs), or whatever to work with. I agree that Verilog is much more tedious to code than microprocessor languages (for which there exist C and even C++ compilers), but I am extremely loath to sacrifice FPGA gates to implement a sequential CPU, and that's why I would never do it myself. What would make sense to me, and what I may very well do myself, is to use a standalone microcontroller to interface to two or three separate FPGA development boards so that it could orchestrate the top level of things and keep all the FPGAs busy all the time if possible. That way, the microprocessor wouldn't be wasting gates and LUTs inside your FPGAs and it could be used to easily interface to a regular PC. At the moment however, I'm more interested in the algorithmic issues (interesting problems for implementation in generic Verilog HDL) rather than details of specific FPGAs - speaking of which: Here is what I have on hand at the moment. When you read the specs for the first one be sure to put down your coffee first, otherwise you'll spill it all over your keyboard. 1. One Xilinx CPLD Design Kit that cost $49 and contains an XC2C256-7TQ144 CoolRunner-II CPLD and XC9572XL-10VQ44 CPLD. Stop Laughing! In my own defense, this was my very first FPGA board and I purchased it because it was cheap in order to decide whether I even wanted to attempt to program these things or not. For those not familiar with this device, neither of the CPLDs on the board have enough gates to do much more than flash LEDs. 2. One LatticeEC Standard Evaluation Board with a LFEC20E-5F484C-41 FPGA on it (that's not a typo by the way. That part number is directly from the silk screening on the FPGA even though the web page says the board comes with a LFEC20E-4F484C-41 device). This turned out to be an extremely poor choice, because although the FPGA is pretty roomy, there is no easy way to interface to the FPGA I/O pins (I would have to install pins in the prototyping holes and wire wrap them to my own connector). The only built-in I/O connector is for the PCI bus, which the board plugs into. The FPGA side of the PCI interface is pretty simple, but once upon a time I had the extremely unpleasant task of writing a device driver for Windows for a PCI board, and it was such an unpleasant experience I never want to repeat it. I have a book on writing Linux device drivers which I suspect is probably easier than for Windows, but still probably wouldn't be a walk in the park. What I'm trying to order (if food were as difficult to purchase as Actel FPGAs are, everyone would have starved to death long ago!) is an Actel ProASIC3 Starter Kit with the A3PE600 part which contains 600K "system gates." I had so much trouble with Actel (they have no discernable customer support whatsoever) that I called up the old Actel sales rep for the company I used to work for and talked to him about it. It was an interesting conversation and he was very polite and wanted to be helpful, but neither he nor anyone else except AVNET is authorized to sell to individuals. Because of some type of blasted reorganization within Actel, the ONLY distributor for Actel development boards is AVNET. AVNET won't take my credit card number until they get a price check from the factory (the Actel sales rep had already told me the board was $350 and there is a two month wait for it). Anyhow, avoid AVNET and Actel both like the plague if you can. In my case however, their ProASIC3 is the biggest and baddest FPGA on the block that I can afford, and my preliminary fitter/mapper reports (I've been using their free Actel Libero® Integrated Design Environment tools even though I don't have their board yet) seem to indicate that unless I'm making some horrible mistake, it should be able to accommodate just about anything I can throw at it - er; download to it I mean. Even though I've downloaded all the fancy free development software tools from all four major manufacturers (Altera, Actel, Lattice, Xilinx), I still mostly use the free Icarus simulator I mentioned earlier because it's quick and convenient for me. If I run into tough problems, I sometimes try one of the compilers for a specific device just to get better error messages, because each compiler/synthesizer seems to have it's own personality and quirks. I guess that's all for now. I'm out of steam. Regards, Ron

2005-09-25, 13:04	#19
Peter Nelson Oct 2004 529₁₀ Posts	Ron, I have a Xilinx CPLD here from an old product and yes the gates were not that impressive quantity :-) I agree with your thoughts on some embedded processors, however, there are exceptions as you say. Ken Chapman (who works for Xilinx UK) wanted to get the best of both worlds so he designed a very compact (in terms of gates) microcontroller called KCSM (Ken Chapman State Machine). It is aka "PICOBLAZE" and has gone through versions 1,2,3. V3 is suitable for eg Spartan 3 and uses about 50 cents worth of the on board gates. (If you really wanted to you could put MANY of the KCSM onto a fpga, so only using one will not noticeably eat up your gate budget for other logic). Now the catch, Picoblaze is FREE BUT only for running in Xilinx chips :-) You may however find it illustrative to go and get the sources and see what he did (either for subsequent use on a Xilinx board you may buy) OR to design your own compact microcontroller. Just register with the Xilinx site (lots of good techie info). As part of the download process if asked for your Xilinx field application engineer's name just put "Ken Chapman" and it should work. You will have heard of "marketing gates" that is you can't directly compare claimed gate counts between rival fpga vendors. eg Xilinx has some nice embedded multipliers, and lots of ram as distributed AND block ram. Others have different architecture. So I dont know if your proasic3 board will be good or not. That is IF you can get hold of it. A supplier of mine once made a mpeg playback hardware card using Actel fpga onboard. Have you considered the widely available boards using Xilinx Spartan 3? They are easily within your budget meaning you could get a device with more gates. The Xilinx toolset is free BUT will not work for the largest devices unless you pay more money. At present the largest Spartan 3 the free tools will work with is the XC3S1500 (see datasheet xilinx website). I think Altera are also pretty good but have only little experience. As you say ASIC is expensive (and getting more expensive in NRE costs as process geometry goes up). However both Altera and Xilinx let you migrate your FPGA design to a kind-of-asic (Xilinx call theirs "Hardcopy") basically the config gets hard burned into the final layer of the chip. This means a) you have much lower NRE costs than asic, but cheaper per unit chip cost than fpga. Additionally you dont need external configuration memory. Also the same design will run faster on these platforms. I suggest that such process is achievable, unlike fullblown asic. So, a math accelerator chip of some sort designed in fpga then migrated to such halfway house chip could be made in volume at reasonable cost. If you want to see some idea of what you might put in it, try looking at www.clearspeed.com datasheets of the CSX600. (96 core math accelerator).