Hardware accelerated LL Testing

[alpertron]

The multiplication circuit shown in Knuth's book does not require floating point support. It requires 11 flip-flops and some combinatorial logic per bit and each block only communicates with the block at its left and the block at its right. So I assume that it may be clocked faster than 500-600 MHz.

[bsquared]

Originally Posted by alpertron

The multiplication circuit shown in Knuth's book does not require floating point support. It requires 11 flip-flops and some combinatorial logic per bit and each block only communicates with the block at its left and the block at its right. So I assume that it may be clocked faster than 500-600 MHz.

In FPGA's, not much faster. The maximum frequency is limited by things other than your design (clock tree, the FPGA fabric, etc.)

[chris2be8]

Several years ago I read the spec for an Inmos A100. It was basically several multiply-adders arranged so you could load 1 number into it, then feed a 2nd number in a word at a time, each stage multiplied the input word by its word of the first number, added previous result, then passed the result along so you could multiply two numbers in time proportional to the total length of the numbers. Several chips could be chained to process numbers large than 1 chip could handle.The total number of gates was proportional to the shorter of the numbers to be processed. Larger numbers could be done in slices.

Obviously today you could put a lot more stages on 1 chip than you could then.

Chris

[ewmayer]

Originally Posted by alpertron

If you can design custom hardware with millions of gates, it is very simple to perform a multiplication in O(n) time (where n is the number of bits) by reading the end of the section 4.3.3 of Donald Knuth's TAOCP.

If you could use billions of gates (not now, but in the future that will not be very expensive), you will be able to multiply two numbers a lot faster than a PC.

And what kind of clock rate would you be able to achieve on such hardware capable of multiplying many-megabit exponents? O(n) loses to O(n log n) if the implied constant is more than log n greater due to your circuit covering the backyard.

[bsquared]

Originally Posted by ewmayer

And what kind of clock rate would you be able to achieve on such hardware capable of multiplying many-megabit exponents? O(n) loses to O(n log n) if the implied constant is more than log n greater due to your circuit covering the backyard.

To be fair, the backyard circuit he said was O(log n), so the constant would need to be O(n), not O(log n).

[alpertron]

Originally Posted by ewmayer

And what kind of clock rate would you be able to achieve on such hardware capable of multiplying many-megabit exponents? O(n) loses to O(n log n) if the implied constant is more than log n greater due to your circuit covering the backyard.

For the 100-megabit case, a 1GHz FPGA or ASIC would require 100 msec in order to perform the iteration. According to http://www.mersenne.org/report_benchmarks/ the fastest processors perform a few percent faster. This is because Knuth's multiplier requires 1 clock cycle per bit while current processors operate with 128 or 256 bits simultaneously.

[Ken_g6]

All this ASIC talk made me think I'd heard of something like that before. But it took me awhile to remember the name. It was called a Dubner Cruncher. I wonder how hard it would be to make something similar today?

[jasonp]

If memory serves, a Dubner Cruncher was an off-the-shelf signal processor chip on an ISA board. It was much faster than PCs of its day because DSP chips are designed for high-throughput multiply-add chains, which are the bottleneck in filtering signals in real time. By comparison, PCs sucked at those kinds of computations.

Nowadays PCs can pipeline that stuff just as much as DSP chips can, to the point where you use DSP chips for reasons other than favorable performance compared to PCs (i.e. space, weight, power or real-time responsiveness constraints).

A modern-day accelerator looks a lot like a latter-day GPU: lots of memory bandwidth, but a much larger arithmetic throughput than PC chips. The need for wide access to memory to execute an FFT means the largest speedup you see for LL testing on a GPU is a factor of ~4x, whereas for Mersenne-mod trial factoring (which only depends of lots of ALUs) you see a GPU run 100x faster.

[fruitflavor]

not a full out custom chip but AMD is providing possible alternatives.

http://www.bit-tech.net/news/hardwar...-semi-custom/1

possible 2p G34 chip with larger L3?

[Manpowre]

I guess its memory size that limits some of this on GPU. As the GPUs only can adress max 8gb of memory. The last cards has 6gb, but not even close to whats needed for proper testing.

With Maxwell architecture from Nvidia, where they place an ARM cpu onchip with the GPU, the GPU itself can adress the hosts memory, so inserting 128gb mem on a machine, and virtualize even more to SSD will make it happen.

[ewmayer]

Originally Posted by Manpowre

I guess its memory size that limits some of this on GPU. As the GPUs only can adress max 8gb of memory. The last cards has 6gb, but not even close to whats needed for proper testing.

6gb is "not even close to whats needed for proper testing" of what, exactly?