SHA256 Round Equivalence

I have calculated the average number of operations in 1 round of SHA256 as follows:

• Bitwise Rotations: 9
• Bitwise Shifts: 1.5
• Bitwise AND: 5
• Bitwise XOR: 10

I have certain proposals that save the following number of operations in one SHA256 evaluation (i.e. 64 rounds) for Bitcoin mining:

• Bitwise Rotations: 12
• Bitwise Shifts: 6
• Bitwise AND: 0
• Bitwise XOR: 12

My question is, how can I represent the above savings in terms of SHA256 rounds?

Do I just consider the additions? So that the saved operations above are equivalent to 24/9.25 = 2.5946 SHA256 rounds per evaluation?

-

Ideally, you'd implement both versions of the SHA-256 algorithm on some common platform, benchmark them and compare their performance. This would give you a measure of their actual real-world performance, or at least something close to it.

If that's not practical, the next option would be to map each operation to some nominal number of CPU cycles typically required to execute it on your target platform (or possibly to nominal gate equivalents, if you're considering hardware implementations instead). Of course, even this measure will still be somewhat platform-dependent. Also, for modern superscalar CPUs, "typical" per-instruction cycle counts may not be all that useful as a performance metric, since actual performance will depend highly on the amount of instruction-level parallelism present in the code.

Finally, for a quick back-of-the envelope estimate, you could simply assume that all the basic arithmetic operations you listed (additions, rotations, shifts, bitwise ops) take the same time to execute, and simply add the operation counts together. Indeed, for many CPUs, this may be reasonably close to the truth: even if the actual execution times differ, they probably won't differ by more than a factor of 2 or 3 at most.

In particular, it's generally pretty safe to assume that addition and bitwise ops are among the fastest instructions on any CPU, and that they'll each take the same number of cycles to execute. Shifts may or may not be slower, depending on the CPU and the type of the shift: one-bit shifts are nearly always fast (and a one-bit left shift can be emulated by addition anyway), but there are some CPUs that have slow multi-bit shifts, and shifts by a non-constant amount may be even slower. Rotations are even more of a mixed bag, but you can generally assume that they're no faster than an equivalent shift and no slower than two shifts (because you can always emulate a rotation using two shifts plus an addition / OR / XOR, and the latter can often be amortized away).

For some example timings, see e.g. this report by Torbjörn Granlund, titled "Instruction latencies and throughput for AMD and Intel x86 processors". Looking at the first two tables, it seems that all the operations you listed do indeed have pretty much identical latencies and throughputs on AMD processors, whereas on Intel processors the throughput varies somewhat (but still by no more than a factor of 3). Of course, all those timings are somewhat artificial, and performance of actual code with mixed and partially interdependent operations may vary noticeably from the "nominal" values.

-
Thank you for the reply. Implementing both versions of the SHA256 algorithm is definitely not feasible for me at this moment. My thesis has a more theoretical approach towards optimising the SHA256 algortihm for faster bitcoin mining. Anyways, I think I will go ahead with your suggestion by assuming that each operation has identical latencies. I can perhaps put up the implementation and bench-marking part in future directions! – Balthazar2012 Aug 22 '13 at 20:04
@Balthazar2012 I would like to point both of you towards Agner Fog's instruction tables. They are pretty much the de facto standard for Intel/AMD latencies and other information. In general his optimization guides are high quality: agner.org/optimize – orlp Aug 23 '13 at 12:08