Re: Xilinx 3s8000?

Thomas Womack wrote:
I think you are entirely misguided in contemplating using ECM to
factor 'hard' numbers such as the RSA Challenge ones; the expected
number of operations would be so large that the calculation would take
literally millions of years.

You may very well be right Tom, but I am alas caught betwix the proverbial rock and hard place. There isn't even the most remote possibility that sieving would fit into the largest FPGA available today, so I am forced to go with the "next best" algorithm which is ECM. Keep in mind that there are a great many opportunities in ECM for parallelization and pipelining. As I mentioned in my original message, the record for ECM factoring the last I heard was 66 decimal digits. It may very well be that I am only able to extend the record by a couple of digits, but at least I will have done something to be proud of and learned a lot about FPGA programming in Verilog HDL. It sure beats sitting around and rotting my brain in front of the boob tube or playing chess on the Internet all day long (Playchess.com is great by the way). It takes me a long time to do a design because of health issues, but at least now I have all the time I need without worrying about schedules and budgets.

In a way, I was sort of gambling that Moore's Law brings large and affordable FPGA's to market faster than the price of conventional computers drop. My plan was to be ready with a fully tested and functional ECM design whenever I was able to afford an FPGA large enough to fit my design. That time is now here, but I hadn't counted on the exorbitant prices of the software necessary to use most vendor's devices. I suppose I'll check on the synthesis capabilities of the free Icarus Verilog package that I use for simulation and see if there are any open source packages I might use to bypass Xilinx's outrageous prices for development tools.


There is a community (Dan Bernstein
probably the mainstay of it) interested in factorisation using
hardware, and the SHARCS conferences contain the people you'd want to
talk to, but a straight ECM implementation hard-wired to factor a
single number is not all that useful.

Even as proof-of-concept? Do you know of anyone else who has ever created an entire ECM factorization design in Verilog? :-) In any case, I think it makes a great hobby (except for the cost of course).

If only because the pricing of
larger FPGAs is not really competitive with the billion 64x64->128
multiplies a second that a $400 dual-core Opteron processor offers.

One nanosecond per 64 bit multiply Tom? That seems a bit of a stretch but I won't quibble over details. So to multiply two 704 bit numbers together (depending upon how it's implemented of course) would require roughly sixty 64-bit multiplies and a bunch of adds. Even so, sixty nanoseconds per 704 bit multiply is pretty impressive. The problem with doing conventional multiplies in ECM is that you have to do a modulo operation after almost every multiply, and modulo is at least as costly in terms of both gate count and time consumption as a multiply; whereas I was able to eliminate a all explicit modulo operations altogether by combining it with my multiplication module. :-)

Because of all the variables and simulation time constraints, it's impossible to get an average value for each ECM iteration for "real" data without being able to run a few test cases in real time on a real FPGA. As soon as I get that done I'll be happy to post the results (for better or worse).

Regards,

Ron
.

Relevant Pages

  • Re: Xilinx 3s8000?
    ... Yes, as I mentioned to Tom elsewhere in this thread, I have written a 100% Verilog implementation of ECM. ... I have no objection to using an FPGA as an accelerator for a program running on a conventional computer, but was hoping to fit the entire thing on one or more FPGA development boards because that keeps things fast and simple. ... That hope may not be justified of course, because some of the same type of technology is used in both CPUs and FPGAs; however, there is no chance that I'll ever be able to afford a cluster of Opterons, but if I can find a way around the exorbitant prices FPGA vendors charge for proprietary software design tools, I could probably afford a fairly high performance FPGA. ...
    (comp.arch.fpga)
  • Re: Newbie question on formatting a field in table design
    ... Each department field is set to the default format ... multiplies the number entered by 100 and adds the "%" sign. ... right of the textbox, then store the number that way and do the ... normalized table design would convert your 11 ...
    (comp.databases.ms-access)
  • Re: assemble 2K FFT by 2 times 1K FFT?
    ... multiplies are more expensive (although I have no particular expertise ... multiplies obviously take several multipliers depending upon the actual ... Ultimately, given the way the FPGA software works, it is difficult to ... trade multiplies and additions directly since it will often figure out the ...
    (comp.dsp)