Date: Thu, 13 Mar 2014 14:20:31 -0400
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Wild DAG pebbling resistance

I have a new DAG architecture with a very interesting property.  I can
pebble a 1024 node DAG with no recomputions at all using only 136
pebbles, but for 135 pebbles, the best I've been able to do so far
takes over 300 billion pebble moves.

I cut Solar Designer's "sliding power of two window" in half, so that
when I double the window size, it only covers the higher 1/2 of memory
rather than all of the memory filled so far.  The idea is motivated
from Catena-3, which has a 4-level computation DAG.  The last two rows
look similar to Catena-3, except that for a node in row r pointing to
a node in row r-1, if the position pointed to in row r-1 is less than
the node's position in row r, point to the node in that position in
row r instead.

For Catena-3, a 1024 node graph has zero recomputations with 256
pebbles, but a 2.4X recomputation penalty (about 1,500 extra pebble
moves) for 255 with my algorithm, using evenly spaced pebbles every 4
nodes.  That was the previous best single-pebble reduction penalty.

I don't yet know what magic properties this graph has that makes it so
hard to pebble.  Likely as not it's just taking advantage of
loop-holes in my pebbling heuristics.  For any of you geeks out there
like me who are interested in this sort of thing, I've included an
example 32-node graph below:

n0                 0 pointers 0
n1                 1 pointers 0
n2                 1 pointers 0
n3      -> n1      1 pointers 0
n4      -> n2      2 pointers 0
n5      -> n3      2 pointers 0
n6      -> n4      1 pointers 0
n7      -> n5      1 pointers 0
n8      -> n4      2 pointers 0
n9      -> n6      1 pointers 0
n10     -> n5      2 pointers 0
n11     -> n7      1 pointers 0
n12     -> n8      1 pointers 0
n13     -> n10     1 pointers 0
n14     -> n9      1 pointers 0
n15     -> n11     1 pointers 0
n16     -> n8      1 pointers 0
n17     -> n12     1 pointers 0
n18     -> n10     1 pointers 0
n19     -> n14     1 pointers 0
n20     -> n17     1 pointers 0
n21     -> n13     1 pointers 0
n22     -> n19     1 pointers 0
n23     -> n15     1 pointers 0
n24     -> n16     0 pointers 0
n25     -> n20     1 pointers 0
n26     -> n18     0 pointers 0
n27     -> n22     1 pointers 0
n28     -> n25     0 pointers 0
n29     -> n21     0 pointers 0
n30     -> n27     0 pointers 0
n31     -> n23     0 pointers 0

The code for computing the 0-based node index that a node points to is:

// Find the previous position using Alexander's sliding power-of-two
window, with Catena
// bit-reversal, but with the sliding window 1/2 as big.
static uint32 findSlidingCatenaPos(uint32 pos) {
    // This is a sliding window which is the largest power of 2 < i.
    if(pos < 2) {
        return UINT32_MAX;
    }
    uint32 mask = 1;
    while(mask <= pos) {
        mask <<= 1;
    }
    mask = mask >> 2; // Mask is greatest power of 2 <= pos/2
    uint32 reversePos = mask + bitReverse((pos) & (mask-1), mask);
    if(reversePos + 1 + 2*mask < pos) {
        return reversePos + 2*mask;
    }
    if(reversePos + 1 + mask < pos) {
        return reversePos + mask;
    }
    return reversePos;
}

I do not know what special property this DAG has, but it sure has an
amazingly sharp cliff for recomputation penalties.

Bill

Powered by blists - more mailing lists