Topic: Official Open Source FPGA Bitcoin Miner (Last Update: April 14th, 2013) - page 44. (Read 432967 times)

I just wanted to add that this statement is not true.  The computation of future rounds of W (above the initial 16 values) uses mixing functions S0() and S1() (in the SHA-nomenclature), which are not composable with add arithmetic.  So the need to compute S0(W[0]) + A is not the same as computing S0(W[0] + A).  The nonce is the value feeding the S0() function, so you need to recompute the entire W block if it changes.

It's a great idea (I tried this too), but it just doesn't work.

I don't trust synthesizers. I've gotten optimizations by simply moving things into separate modules to clearly define the hierarchy.

Yeah, I will have to try that. Last time I tried, it was at 50MHz.

I tried routing 16 rounds only. Worked fine. 32 was fine. But then at 64 it failed. So it's doing something weird ...

I certainly hope not. The Spartan series is supposed to compete with Altera's Cyclone which routes these designs without any problems. Their architectures are certainly different, but if it can't even route a 64-round SHA-256 design on an LX150 then ... I dunno what to think about Xilinx.

Thank you! It will take me some time to double check it and commit it to the repo; it's a busy week at my job. I'm posting these replies during compilation rounds 

Anyway, this is great input TheSeven, I really appreciate it. It makes me a little more worried about cramming the design into my LX150, but it's all good discussion and I'll keep working at it regardless.

Nice one, liked it


http://dl.dropbox.com/u/23683845/fpgaminer-xilinx.zip


2x 64 digesters, 2 final adders and the =0 comparison


I don't think two of those pipelines actually fit in there. I've got 60% slice usage on the LX150, and on the LX100 the placer failed even though it has more slices than slices actually used on the LX150.
Have you tried routing it at a lower clock frequency? Start out with something ridiculous like 10MHz to check if the design can be routed at all, and then increase it until things get tight.
If it doesn't route for 10MHz as well, my suspicion would be that the Spartan series just don't support as flexible routing as the Virtex series do.

Regarding your optimizations, I'm fairly sure that at least part 1 and possibly also part 4 will be performed automatically by xst.

Wow, Terasic apparently noticed this project and posted it on their Facebook page. Neato! And they also gave a shout-out to Bitcoin! 

Sure, that'd be great!

You mention 131 pipelined stages. I assume you mean something like, 128 round modules, 2 final adder stages, and a third ... misc stage?

My estimate for the 6SLX150-3N comes from assuming that Xilinx's estimation on equivalent LCs is accurate and that the design would use a similar number of 4-LUTs and FFs on Xilinx, as compared to Altera.

The optimized design can fit into 80K LEs on a Cyclone 3, possibly 75K with some more cramming; at 80MHz and one cycle per full-hash. Assuming LE == LC that would allow two of those to fit into the 6SLX150-3N because it has the equivalent of 150K LCs. That would achieve a combined hash-rate of 160MH/s.

Obviously, you can see that my assumptions all come from "LE == LC." Indeed, when I've synthesized my design for the 6SLX150, utilization was roughly what I expected. But as you pointed out, routing is where I got stuck. ISE refused to route the design. That's on my list of things to do; figure out why ISE won't route the design, even though it will route a cut-down design (only implementing a few rounds instead of all 128) just fine, and utilization is <70%.

The code isn't on the public repo yet, no, because it's a work in progress and I haven't taken the time to put it up yet. It's on the list of things to do

There are four classes of optimizations:

1) The last 3 rounds the second SHA-256 pass are not needed. You only need to check that Round64.H is equal to 0, and the last three rounds do not affect H. Here's the math:


That allows you to remove 3 full rounds and 9 adders.


2) Pre calculating the first few stages of the first SHA-256 pass is also possible. The first pass is calculated from the 512-bit DATA string that getwork requests give us, and the MIDSTATE. Between pieces of work, all of that data remains constant, except for the nonce, which we are increasing. The nonce is at W[3] (0 based), and W[3] isn't used until Round4. So, you can run the first 3 rounds of SHA-256 on a controller (PC, microcontroller, whatever) before handing the "work" to the FPGA. The FPGA then picks up where you left off and never has to calculate those first 3 rounds.

That amounts to giving the FPGA Midstate, Data, and Midstate', where Midstate' is the 256-bit state as of your pre-calced Round3.


3) Quite a large amount of W can be pre-calced off the FPGA as well. Again, Data is constant except for the 4th word which is the nonce. I won't go into the math here, because it's rather long. The first 16 values of W are sourced directly from Data, so that's a no-brainer. However, also note that all of Data after the first 4 words (after the nonce) is constant for all getwork requests! So you can actually hard code those values as they are in the code on the public repo. What that code doesn't do, however, is just add K with the known W values, thus saving you an adder for the first 16 rounds.

After the first 16 rounds, everything up to round 35 (I think) has some amount of W that can be pre-calculated off the FPGA and given to it with the rest of the work data.


4) The final optimization is this:

Having to add K and W makes the adder tree larger. K is a constant and always known. W can be calculated at any point before a given round. H is also known at least one round ahead of time (as you've learned in the first optimization). So it's possible to do this calculation in the previous round:


and then in the next round:


That shrinks the critical path down, allowing for higher clock rates. Note that I haven't implemented that particular optimization, so double check that I did my math right.

Really? I had the opposite impression.
BTW, if you want to, you could host my VHDL version in your git repository as well, for the Xilinx users.


Never ever. I'm if you mean XC6SLX150-3, this isn't going to cross 120MH/s, at least not with this design.
I've tried to synthesize a fully-unrolled (131 pipeline stages) design for that FPGA, and even though it fits (it doesn't on the LX100 variant), there seem to be difficulties routing it, and attempting to synthesize it for 120MHz didn't work out at all. The router is still running (since almost 48 hours now), so I don't even know which frequency it did reach yet.


This is where you apparently know more about the algorithm than I do. I've just translated your code to VHDL.
Could you provide some details on your optimizations? Is the optimized verilog code available somewhere?
Getting rid of 3 rounds would very likely allow to increase the clock frequency even further.
EDIT: Now that I think about it, I see how the last rounds could be removed, but I'm fairly certain that the synthesis tool was clever enough to have done that already.

It seems like the Xilinx devices are far cheaper, for reasons I can't explain. The only problem is my code doesn't currently support Xilinx. I'm working on it, but until it's done there's no way to know for sure if the utilization and performance is similar.

Back-of-the-napkin:
You'd want to go with, obviously, the chips giving the lowest $ per MH/s figure. The price scaling on the chips is very non-linear. A quick scan over the Altera Cyclone 4 series shows that a Cyclone 4, C40-7N chip has the lowest (best) ratio. It's $82.96 in singles from Altera's website and would produce an estimated 40MH/s (if you can fit a half-mining core in it). That's $2.08 per MH/s. You'd probably get a small discount if you're buying 128 to build a big array, or if their sales team can price match Xilinx's offerings. 128 of those babies would get you 5GH/s and consume ~320Watts.

For reference, Xilinx's SLX150-3N chips are ~$120 in some quantity, with an estimated performance of 160MH/s. That's $0.75 per MH/s.

Wow, I'm surprised utilization is 97%, but I guess that's fairly close to the 90K LEs that my unoptimized version uses on Cyclone 3/4. You can apply the usual optimizations (last 3 rounds aren't needed, pre-calced W, etc) to get better utilization but I'm not sure you could cram much into whatever space that would save you. You can also play with the adder trees a bit, moving W + k into the prior rounds to improve MHz performance.

They aren't going to tell you how it works. They want to sell it.