[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 27 Jan 2014 11:51:16 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] An argument for Catena-2
On Mon, Jan 27, 2014 at 8:34 AM, Dmitry Khovratovich
<khovratovich@...il.com> wrote:
> Hi Bill,
>
> it seems that your 10X estimate is a bit pessimistic. If you have only half
> of memory available, you can split it in half and store every 4th point
> (v_i) from the first two rows in memory.
Very cool analysis! You are correct. My 10X estimate was high.
I've tested your pebbling strategy and verified it, with 1 caveat: you
need an additional 3 free pebbles to be able to pebble the graph. For
your example, we place 4 fixed pebbles, but we only have 4. you need
3 more for the pebbling to be possible.
When I use G/2 + 3 pebbles, I can verify the pebbling time for larger
sizes. For G == 2048, I pebble the graph using 1027 pebbles with a
2.6X penalty.
When I add the sub-Catena-7 graph in the first row, using your
strategy, I can pebble the graph with 1034 pebbles (I need 7 more for
the first row) with a penalty of 12.2X. Using a Catena-3 sub-graph in
the first row, I get 5.1X.
Switching up to Catena-3, instead of a pebble every 4, we have to drop
to a pebble every 6 in the first three rows, and use a total of G/2 +
4 pebbles. For G == 8192, using 1028 pebbles, I get a total compute
effort that is 9.4X higher than when I have 2048 pebbles.
Adding a Catena-3 sub-graph in the first node takes it up to 49X. For
a Catena-8 graph, on a smaller (so it would run faster) graph of G ==
1024, and 143 pebbles, I needed 728X more pebble placements.
It seems to me that the sub-Catena graph may be needed after all.
Bill

Powered by blists - more mailing lists