Xilinx 3s8000?

Jim Granville wrote:
> - you do seem to be rather Xilinx fixated ? :)

Actually Jim, there is a good reason for that. It almost physically 
pains me to say something good about Xilinx in view of this thread's 
history ;-), but their's is the only version of Synplicity that will 
compile and synthesize my design for anything above a bus width of 256 
bits. :-(

Here is the email I received from Synplicity tech support:

     > Hi Ron,
     >
     > This is a bug with pro ASIC mapper and I have filed bug
     > for this issue and I will get this fixed [bug id is: 170164].
     >
     > Design passes when targeted to SX-A technology.
     > Unfortunately, I could not find any workaround for this issue.
     > This design works fine with other technology like xilinx V4,
     > Spartan2 too.
     >
     > Regards,
     > Prashanth

Anyone know how to easily track Synplicity bug reports?

In article <1147022814.787257.294510@i39g2000cwa.googlegroups.com>,
Peter Alfke <alfke@sbcglobal.net> wrote:
>
>Ron wrote:
>> 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. ...
>
>If I remember right, 704 is 11 times 64, so the multiplication would
>take 121 of those 64-bit multipliers, not "roughly sixty"...

It depends on precise details of the implementation, and you have to
write moderately ugly code because the x86 multiply instruction
produces its outputs in fixed registers, but if you apply
Karatsuba-style techniques enough you can get down to below sixty
... one 12x12 requires six 4x4 + some fiddling, one 4x4 requires three
2x2 + some fiddling, one 2x2 requires four, that's 72, or three +
extra fiddling to make 54.

However, Karatsuba techniques really work much better on FPGAs where
you can do the extra adds in parallel; I don't think you'll gain
anything from the three-level decomposition on Opteron.

As you might imagine, I would be ecstatic to see a few wide
multipliers appearing in FPGAs - a 64x64->128 unit isn't _that_ large
an IP block - but the market for number theorists isn't large enough
to pay for the masks, and RSA accelerators are produced in enough
volume for it to be worth making ASICs.

Tom

uh, guy - why the hell u wanna brute force rsa with an fpga. there r quite better (faster and cheaper) methods to do so. hope u calculated the throughput and the years/centurys of trying.

Jim Granville schrieb:

> Well, I was not actually refering to Xilinx (comprehension?)
> - you do seem to be rather Xilinx fixated ? :)

Q: Well, what's your opinion on this case, Dr. Freud?

A: A clear case of P.., aehhh Xilinx envy!

SCNR!
;-)

Regards
Falk

Thomas Womack wrote:
> As you might imagine, I would be ecstatic to see a few wide
> multipliers appearing in FPGAs - a 64x64->128 unit isn't _that_ large
> an IP block

Hi Tom. No, a 64x64->128 integer multiplier isn't that large at all. 
Here is the device utilization report for mine:

Device utilization summary:
---------------------------
Selected Device : 3s500epq208-4
  Number of Slices:                     557  out of   4656    11%
  Number of Slice Flip Flops:           370  out of   9312     3%
  Number of 4 input LUTs:               867  out of   9312     9%
  Number of bonded IOBs:                 18  out of    158    11%
  Number of GCLKs:                        1  out of     24     4%

Keep in mind though that my primary concern at present is minimizing LUT 
(gate) count, not speed, so this multiplier requires N clock cycles to 
multiply two N bit numbers together yielding a 2N length result. If 
you'd like I'll be happy to send you a copy of the Verilog source code 
for my multiplier and the combination multiplier/modulo module (which is 
only slightly larger than the multiplier module). It's 110 lines of Verilog.

Regards,

Ron

frank wrote:
> uh, guy - why the hell u wanna brute force rsa with an fpga.
 > there r quite better (faster and cheaper) methods to do so.

Example please? RSA-640 was solved with a distributed network of 
something like 80 Opterons doing sieving. I wouldn't call those "cheap."

> hope u calculated the throughput and the years/centurys of trying.

That's one of the the shortcomings of ECM that Tom touched on earlier. 
Unlike traditional factorization methods, ECM doesn't even guarantee any 
result at all! Because of that, I had to have two status LEDs; one to 
indicate completion, and another to indicate whether or not a solution 
was found.

The average throughput rate will hopefully be blazingly fast at about 
one or two bits per day. ;-)  There is no input to the FPGA because the 
number to be factored is hard coded into the FPGA (although I could 
easily read it from an external device if needed), and the factor (if 
found) will be displayed on the board's LCD display, so the only thing 
connected to the board during operation is power.

Because of the probabilistic nature of ECM, to the best of my knowledge 
no one has ever been able to calculate how long ECM would require on 
average for a particular factorization. I wonder if Tom Womack has 
investigated this in his work with ECM?

Ron

Ron, it's amazing how nice and patient you can be when you want to...
Greetings
Peter Alfke

Thomas Womack wrote:
> In article <1147022814.787257.294510@i39g2000cwa.googlegroups.com>,
> Peter Alfke <alfke@sbcglobal.net> wrote:
> >
> >Ron wrote:
> >> 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. ...
> >
> >If I remember right, 704 is 11 times 64, so the multiplication would
> >take 121 of those 64-bit multipliers, not "roughly sixty"...
>
> It depends on precise details of the implementation, and you have to
> write moderately ugly code because the x86 multiply instruction
> produces its outputs in fixed registers, but if you apply

You could use the IMUL instruction (signed multiply) you free yourself
from that restriction, you have to make certain that your product will
fit in 32-bits and that your values stay in their restricted place (no
overflow).

Just for fun, here are the figures for a bus-width of 704 bits and 1024 
bits.

Device utilization summary:  (704 bit bus-width)
---------------------------
Selected Device : 3s500epq208-4
  Number of Slices:                    2592  out of   4656    55%
  Number of Slice Flip Flops:          1779  out of   9312    19%
  Number of 4 input LUTs:              4176  out of   9312    44%
  Number of bonded IOBs:                 18  out of    158    11%
  Number of GCLKs:                        1  out of     24     4%

Device utilization summary:  (1024 bit bus-width)
---------------------------
Selected Device : 3s500epq208-4
  Number of Slices:                    2975  out of   4656    63%
  Number of Slice Flip Flops:          2099  out of   9312    22%
  Number of 4 input LUTs:              4896  out of   9312    52%
  Number of bonded IOBs:                 18  out of    158    11%
  Number of GCLKs:                        1  out of     24     4%


The amazing thing is that the slice and LUT counts seem to increase 
*less* than the bus-width increases (ie; the size of the numbers it can 
multiply). I've taken pains to ensure the optimizer isn't optimizing 
something away that it shouldn't, so as far as I know these numbers are 
correct.

The synthesizer reports a maximum frequency of 58MHz for the 64 bit 
design, 16MHz for the 704 bit design, 12 MHz for the 1024 bit design "as 
is" without any tweaking to improve the timing, so it should take about 
1.1 microseconds to multiply two 64 bit numbers together, and 85 
microseconds to multiply two 1024 bit numbers together.

Ron

On Mon, 08 May 2006 16:07:18 -0700, Ron <News5@spamex.com> wrote:

>Just for fun, here are the figures for a bus-width of 704 bits and 1024 
>bits.
>
>Device utilization summary:  (704 bit bus-width)
>---------------------------
>Selected Device : 3s500epq208-4
>  Number of Slices:                    2592  out of   4656    55%
>  Number of Slice Flip Flops:          1779  out of   9312    19%
>  Number of 4 input LUTs:              4176  out of   9312    44%
>  Number of bonded IOBs:                 18  out of    158    11%
>  Number of GCLKs:                        1  out of     24     4%
>
>Device utilization summary:  (1024 bit bus-width)
>---------------------------
>Selected Device : 3s500epq208-4
>  Number of Slices:                    2975  out of   4656    63%
>  Number of Slice Flip Flops:          2099  out of   9312    22%
>  Number of 4 input LUTs:              4896  out of   9312    52%
>  Number of bonded IOBs:                 18  out of    158    11%
>  Number of GCLKs:                        1  out of     24     4%
>
>
>The amazing thing is that the slice and LUT counts seem to increase 
>*less* than the bus-width increases (ie; the size of the numbers it can 
>multiply). I've taken pains to ensure the optimizer isn't optimizing 
>something away that it shouldn't, so as far as I know these numbers are 
>correct.
>
>The synthesizer reports a maximum frequency of 58MHz for the 64 bit 
>design, 16MHz for the 704 bit design, 12 MHz for the 1024 bit design "as 
>is" without any tweaking to improve the timing, so it should take about 
>1.1 microseconds to multiply two 64 bit numbers together, and 85 
>microseconds to multiply two 1024 bit numbers together.


Presumably you could do it rather quicker using the S3's multiplier blocks.....