Re: [cryptography] 5x speedup for AES using SSE5?
Hovav Shacham wrote:
On Aug 24, 2008, at 5:20 AM, Peter Gutmann wrote:
Speaking of CPU-specific optimisations, I've seen a few algorithm
proposals
from the last few years that assume that an algorithm can be scaled
linearly
in the number of CPU cores, treating a multicore CPU as some kind of
SIMD
engine with all cores operating in lock-step, or at least engaging in
some
kind of rendezvous every couple of cycles (for example the
recently-discussed
MD6 uses a round of 16 steps, if I read the description correctly)
My impressions from Ron's talk were different. For multicore systems,
the tree structure of the hash allows parallelism at a much higher
granularity. For hardware implementation, the feedback-register
structure of the round function means that 16 steps can be computed in
parallel. I didn't get the sense that Ron intends for the second kind
of parallelism to be used in software implementations.
Hovav.
From the MD6 powerpoint, it does look good for parallelism. When using
SSE5 (to get back on topic :-), you should be able to do 2 blocks in the
one instruction stream. I can't remember enough of the other SSE
instructions to know if the relevant 64bit shifts are present before SSE5.
The only place where I've used multiple CPUs in crypto so far has been
in RSA's CRT, where, due to the magic of
OpenMP support, and a little bit of state splitting, I get the following
throughput numbers for dual core 2.5ghz, athlon64
doing 1024-2 RSA private key operations (number per second)
For normal single threaded, 4650 per cpu second and wall clock second.
OpenMP, 4330 per CPU second, 7360 wall clock second.
So in this case, the OpenMP overhead is about 8% CPU. MD6 has smaller
chunks, and lots of them, so it will probably scale quite well.
OpenMP, it makes it very easy to put in parallelism. In this CRT
implementation, it was a simple
#pragma omp parallel for
for (i=0; i2; i++)
/* CRT code */
A few changes were made to make sure the structures were not shared, but
nothing that affects performance.
OpenMP is now in gcc 4.2 which is nice.
MD6, should be just as stupidly easy,
#pragma omp parallel for
for (block_num=0; block_num(data_len/512); block_num++) {
MD6_block((ret_st[block_num]), input + block_num*512, block_num,
level, not_root, )
}
Repeat up the levels (depending of memory availability).
eric
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [cryptography] 5x speedup for AES using SSE5?
Peter Gutmann wrote: Is there some feature of multicore CPUs that I'm missing, or is it a case of cryptographers abstracting a bit too much away? And if it's the latter, should someone tell them that multicore CPUs don't actually work that way? I can't speak to the former issue, but I seem to remember that the numbers Rivest showed at the talk were actual performance measurements, not projections, and that it was basically linear. Kevin - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [cryptography] 5x speedup for AES using SSE5?
On Aug 24, 2008, at 5:20 AM, Peter Gutmann wrote: Speaking of CPU-specific optimisations, I've seen a few algorithm proposals from the last few years that assume that an algorithm can be scaled linearly in the number of CPU cores, treating a multicore CPU as some kind of SIMD engine with all cores operating in lock-step, or at least engaging in some kind of rendezvous every couple of cycles (for example the recently- discussed MD6 uses a round of 16 steps, if I read the description correctly) My impressions from Ron's talk were different. For multicore systems, the tree structure of the hash allows parallelism at a much higher granularity. For hardware implementation, the feedback- register structure of the round function means that 16 steps can be computed in parallel. I didn't get the sense that Ron intends for the second kind of parallelism to be used in software implementations. Hovav. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [cryptography] 5x speedup for AES using SSE5?
Paul Crowley wrote: http://www.ddj.com/hpc-high-performance-computing/201803067 In the above Dr Dobb's article from a little over a year ago, AMD Senior Fellow Leendert vanDoorn states the Advanced Encryption Standard (AES) algorithm gets a factor of 5 performance improvement by using the new SSE5 extension. However, glancing through the SSE5 specification, I can't see at all how such a dramatic speedup might be achieved. Does anyone know any more, or can anyone see more than I can in the spec? http://developer.amd.com/cpu/SSE5/Pages/default.aspx I've only just seen this, but I've been playing with the VIA's AES and looking at Intels AES instructions. I believe the PPERM instruction will be rather important. Combined with the packed byte rotate and shift some rather interesting SIMD byte fiddles should be possible. From my initial look, it should be possible to implement AES without tables, doing SIMD operations on all 16 bytes at once. I've not looked at it enough yet, but currently I'm doing an AES round in about 140 cycles a block (call it 13 per round plus overhead) on a AMD64, (220e6 bytes/sec on a 2ghz cpu) using normal instructions. I don't believe they will be taking 30 instructions , so they probably have 4-8 SSE instructions per round, it then comes down to how many SSE execution units there are to execute in parallel. As for VIA, on a 1ghz C7 part, cbc mode, 128bit key, for 16byte aligned, I'm getting about 24 cycles per block, for unaligned, about 67 cycles. The chip does ECB mode at 12.6 cycles a block if aligned (2 at a time). It does not handle unaligned ECB, so with manual alignment, 75 cycles. Not bad for a single issue cpu considering the x86 instruction version of AES I have takes 1010 cycles per block. For the intel AES instructions, from my readings, it will be able to do a single AES (128bit) in a bit more that 60 cycles (10 rounds, 6 cycle latency for the instructions). The good part is that they will pipeline. So if you say do 6 AES ecb blocks at once, you can get a throughput of about 12 cycles a block (intel's figures). This is obviously of relevance for counter mode, cbc decrypt and more recent standards like xts and gcm mode. Part of the intel justification for the AES instruction seems to stop cache timing attacks. If the SSE5 instructions allow AES to be done with SIMD instead of tables, they will achieve the same affect, but without as much parallel upside. It also looks like the GF(2^8) maths will also benefit. eric (who has only been able to play with via hardware :-( - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [cryptography] 5x speedup for AES using SSE5?
Speaking of CPU-specific optimisations, I've seen a few algorithm proposals from the last few years that assume that an algorithm can be scaled linearly in the number of CPU cores, treating a multicore CPU as some kind of SIMD engine with all cores operating in lock-step, or at least engaging in some kind of rendezvous every couple of cycles (for example the recently-discussed MD6 uses a round of 16 steps, if I read the description correctly) to exchange data. This abstraction seems to be particularly convenient when dealing with things like hash trees. However I'm not aware of any multicore CPU that actually works this way, you'd need to have exclusive use of each core by one thread and use incredibly expensive (compared to the other primitive CPU operations used in hashing) barriers or something similar to ensure synchronisation. Is there some feature of multicore CPUs that I'm missing, or is it a case of cryptographers abstracting a bit too much away? And if it's the latter, should someone tell them that multicore CPUs don't actually work that way? Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
