C Programming: Mapping / Addressing Hypercube Topologies

Recently I have been working furiously to get some experiments done with the robots. I had to conduct 50 hours of experiments, and combined with retakes I think I clocked something like 80 hours in the lab. Lots of overnight sessions. After that, I had to write my results up, which felt like the end of a marathon. I'm still have corrections to make, but the bulk of it is over. Phew!

Today I want to post some more source code. I am exploring how lots of nodes (computers, robots, anything that communicates) is effected by the way they are arranged. I have had some trouble visualising how a hypercube is connected. These two youtube videos explain it for 4 dimensions, (or 16 nodes).

Part 1
Part 2

However, you can have hypercubes to as many dimensions you like, as long as you keep the number of nodes as a power of 2 (2, 4, 8, 16, 32). I have found it impossible to visualise what that would look like. Wikipedia has an article, but it wasn't helping me to think of an efficient way to program an algorithm to efficiently map communication between the nodes. Typically, I would want an elegant For Loop to whistle through each connection.

From those youtube videos, I realised that each node, with a binary address, maps to another node if only 1 bit changes. So 0101 would map to 0001, 0100, 0111, and 1101. I still couldn't figure out a sweet algorithm to loop through these bitwise values. Instead, I opted for a brute force search that you run once and creates a look up table to use from there on.

Here is the source code after the break and a brief example of how it is called.   You should be able to map any dimension of hypercube as long as it as the number of nodes is a power of 2 and your computer has enough memory :) Again, I can't guarantee its correct operation, but I hope it helps someone. After making the initial call, hypercube_struct_t.map will contain a 2D table. This maps the source node to a destination by decimal index.  



Compile with -lm for the math.h library.

I think this needs a bit more of an explanation.
1) Construct a list of bitmasks that are single bit values. If we need 4 bits to address 16 nodes, we need 4 masks which will be 0001, 0010, 0100, and 1000.
2) Take a source node address, such as 1100.
2) Exclusive Or this with a potential target address, capture the result.
3) Logical And the result with each mask value. If any is true, only 1 bit must of changed, and we have a good mapping.
4) We need to repeat this operation between the source node address and all other addresses.

Importantly, we loop through a number of masks to however many dimensions there are, but we are only achieving the number of mappings up to the connection degree.  The number of nodes grows exponentially, whilst the connection degree grows linearly.  I think iterating through the look up table is an efficient method.


#include <stdio.h>
#include <math.h>




typedef struct hypercube_details {
    int max_islands;        // Will contain  how many islands (power of 2)
    unsigned int max_degree;    // Will contain the maximum degree of connectivity
    unsigned int max_dimensions;    // Will contain max number of bits for address space
    unsigned int ** map;        // mapping, 2d array : map[ an island ][ to max_degree ] 
} hypercube_struct_t;




int makeHypercube( hypercube_struct_t * hc_ptr, int islands );
void freeHypercube( hypercube_struct_t * hc_ptr );




int main(void) {

    int source, connection;

    // Create the hypercube variable    
    hypercube_struct_t hypercube;

    // Call the make function.
    if( makeHypercube( &hypercube, 64) == 0 ) {
        printf("Something went wrong :(\n");
    } else {
        

        // example usage:

        // For each node/island.
        for( source = 0; source < hypercube.max_islands; source++ ) {
            printf("Island %d connects to islands: ",source);           
            for( connection = 0; connection < hypercube.max_degree; connection++ ) {
                printf("%d,", hypercube.map[source][connection]);                
            }
            printf("\n");
        }


        // and eventually free up the memory
        freeHypercube( &hypercube );

    }



}





int makeHypercube( hypercube_struct_t * hc_ptr, int islands ) {

    unsigned int target,source,dimension, degree;
    double d_temp;
    
    unsigned int * mask;
    
    hc_ptr->max_islands = islands;


    printf("%d Islands\n", hc_ptr->max_islands);

    // The degree is how many other nodes one node connects too
    hc_ptr->max_degree = log2(hc_ptr->max_islands);
    printf("Max degree should be %d\n", hc_ptr->max_degree);
    
    // Work out what power of base 2 this number is.
    d_temp = log2(hc_ptr->max_islands)/log2(2);
    hc_ptr->max_dimensions = (unsigned int)d_temp;
    if( d_temp - (double)hc_ptr->max_dimensions > 0.001 ) {
        printf("Error: Number of islands is not a power of 2, abort\n");
        return 0;
    }

    printf("Max Dimensions %d\n", hc_ptr->max_dimensions);

    // We create a number of bit masks equal to the maximum bits
    // required to map the addresses in binary.
    mask = malloc( hc_ptr->max_dimensions * sizeof( unsigned int ));
    
    mask[0] = 1;
    for( dimension = 1; dimension < hc_ptr->max_dimensions; dimension++ ) {
        mask[dimension] = (int)pow(2,dimension);
    }

    // We create a look up table map for each island, with the
    // max number of degree entries.
    hc_ptr->map = malloc( hc_ptr->max_islands * sizeof( unsigned int *));
    for( source = 0; source < islands; source++ ) {
        hc_ptr->map[source] = malloc( hc_ptr->max_degree * sizeof( unsigned int ));
    }        


    // We iterate through all the combinations and check for just a one 
    // bit change between addresses, saving to our map table.
    // We check that we dont create more address mappings than we malloc'd
    // by tracking the degree variable.  This shouldn't happen, but just to
    // be safe :)
    for( source = 0; source < hc_ptr->max_islands; source++ ) {
            
        degree = 0;
        
        for( target = 0; target < hc_ptr->max_islands; target++ ) {

            for( dimension = 0; dimension < hc_ptr->max_dimensions; dimension++ ) {

                if( (source ^ target) == mask[dimension] ) {
                    
                    if( degree > hc_ptr->max_degree ) {
                    
                        freeHypercube( hc_ptr );        
                        printf("\n Error, found an address match beyond the max degrees, abort\n");
                        return NULL;
                    
                    } else {

                        hc_ptr->map[source][degree] = target;
                        degree++;
                    }
                }
            }
        }     }
        
    free( mask );
    
}

void freeHypercube( hypercube_struct_t * hc_ptr ) {
    int i;

    for( i = 0; i < hc_ptr->max_islands; i++ ) {
        free( hc_ptr->map[i] );
        hc_ptr->map[i] = NULL;
    }    
    free( hc_ptr->map );
    hc_ptr->map = NULL;

    return;
}