hhenrichsen/00_README.md

## 00_README.md

      
    Raw
  

              00_README.md
            
          
    Hypercube Topology Bitshift Indexing

Introduction

This is a hypercube, or a 2D representation of a 3D representation of it:

Say we wanted each point in the cube to be able to reach out to its neighbors.
We could do some math specific to each dimension, ensuring that numbers loop
back around and such, but that's more complicated than we like, especially when
we're sure that there's a pattern -- we're working with vertices in a power of
two, so there must be one.
The forumula we're given for this working in bits is this:
rank^(1<<m)

Where rank is the ID of the node, just as each node has an ID in the image above.
m is the dimension that we want to reach out in. Since I drew a 4-dimensional
square above, we'll work with m values of 0-3.
Bit Shifting

So how does this work? First, let's talk about the << (left bit shift) and ^
(bitwise XOR) operators. Both of these work in binary, so let's look at some binary
equations:
Left Bit Shift

   0001 (1)
<<    1 (1)
------------
   0010 (2)

   0101 (5)
<<    1 (1)
------------
   1010 (10)
   
   0001 (1)
<<   10 (2)
------------
   0100 (4)

So it moves the bits left by however many spaces we tell it to, basically multiplying it by 2^n.
Bitwise XOR

  0110 (6)
^ 1010 (10)
-----------
  1100 (12)
  
  0001 (1)
^ 1011 (11)
-----------
  1010 (10)

So it takes the bits where they are different from each other and sets them to 1.
Putting it together

So say we have a rank of 0, or in binary 0000. If we want to get its neighbors
in the 0th dimension, we'll plug it into the above formula:
0000^(0001<<0000)
0000^0001
0001 (1)

For the 1st dimension:
0000^(0001<<0001)
0000^0010
0010 (2)

For the 2nd:
0000^(0001<<0010)
0000^0100
0100 (4)

For the 3rd:
0000^(0001<<0011)
0000^1000
1000 (8)

Wow, a more complicated way to count by powers of two! Here's the connections visualized:

The cool part is that it works for any node so let's try with node 2:
0010^(0001<<0000)
0000^0001
0011 (3)

For the 1st dimension:
0010^(0001<<0001)
0010^0010
0000 (0)

For the 2nd:
0010^(0001<<0010)
0010^0100
0110 (6)

For the 3rd:
0010^(0001<<0011)
0010^1000
1010 (10)

Here's the same visualized:

Synchronizing a Network

If we tell each node to reach out in dimension n, we can synchronize a network in log_2(n) operations:
Dimension 0:


Now 8 different lines are synched with each other.
Dimension 1:


Now 4 different squares are synched with each other. Yellow lines are existing connections.
Dimension 2:


Now 2 different cubes are synched with each other.
Dimension 3:


Now the full hypercube is synched.