[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150819041042.GA15310@openwall.com>
Date: Wed, 19 Aug 2015 07:10:43 +0300
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: PHC: Argon2 on GPU
On Wed, Aug 19, 2015 at 04:47:32AM +0200, Agnieszka Bielec wrote:
> I have argon from github https://github.com/khovratovich/Argon2 from
> branch master. should I work now on 'enhcance' branch?
You'll need to switch at some point, but since you already did so much
work on the original Argon2, I think it makes sense for you to stick
with it for a while longer.
Regarding optimizations, especially for GPU:
I think the modulo division operations are causing a lot of latency:
[solar@...er opencl]$ fgrep % argon2*.cl
argon2d_kernel.cl: reference_block_offset = (phi % r);
argon2i_kernel.cl: uint reference_block_index = addresses[0] % r;
argon2i_kernel.cl: uint reference_block_index = addresses[i] % r;
On GPU, this means having local and private memory tied up to code that
doesn't actually touch that memory but is instead doing this division
operation for many cycles in a row. This is extremely wasteful. I think
this might explain the unexpectedly poor performance on AMD GCN. (Maybe
NVIDIA has relatively low latency integer division hardware.)
For Argon2i, you should be able to easily optimize this overhead out,
since all the indices are known in advance (they are the same each
time, by design, as required to avoid cache timing leaks). You should
also be able to optimize out the hashing that produces those indices
(before the modulo division), but that's relatively minor (yet by all
means make this optimization as well if you do precompute the indices).
This means you will need some memory to store those indices in (1536 of
them for our current benchmarks? meaning something like 3 KB?), but this
memory can be shared between different concurrent hash computations.
For Argon2d, optimizing this is not easy, and the speedup potential is
lower. Yet there could be ways:
Fast Division Algorithm with a Small Lookup Table
http://arith.stanford.edu/~hung/papers/asilomar.pdf
"This paper presents a new division algorithm, which requires two
multiplication operations and a single lookup in a small table. The
division algorithm takes two steps. The table lookup and the first
multiplication are processed concurrently in the first step, and the
second multiplication is executed in the next step. This divider uses a
single multiplier and a lookup table with 2/sup m/(2m+1) bits to produce
2 m-bit results that are guaranteed correct to one ulp. By using a
multiplier and a 12.5 KB lookup table, the basic algorithm generates a
24-bit result in two cycles."
It might also be practical to adapt methods normally used for
floating-point to producing precise integer results (there might need to
be some trial and error to confirm or come up with precise results, and
you'll need to implement this in code too):
https://en.wikipedia.org/wiki/Division_algorithm#Fast_division_methods
http://stackoverflow.com/questions/12227126/division-as-multiply-and-lut-fast-float-division-reciprocal
Someone with a GPU working on a much simpler subset of the problem:
http://stackoverflow.com/questions/2616072/faster-integer-division-when-denominator-is-known
(just to illustrate the problem of slow integer division on GPUs).
Before you spend a lot of time on this, I suggest that you replace this
modulo operation with something simpler (and wrong), yet in some ways
similar, e.g.:
static inline uint32_t wrap(uint64_t x, uint32_t n)
{
uint64_t a = (x + n) & (n - 1);
uint64_t b = x & n;
uint64_t c = (x << 1) & n;
return ((a << 1) + b + c) >> 2;
}
(and its OpenCL equivalent, with proper data types). Of course, this
revision of Argon2 won't match Argon2's normal test vectors, but you
should be able to see roughly what performance you could get if you
later optimize the division.
Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
