5
\$\begingroup\$

I'm working on an assignment which entails creating communicators following the diagonals of an n x n process grid. I'm interested to get feedback regarding the correctness of the solution I developed as well as feedback regarding the efficiency of the solution.

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

/* Example Matrix
 * 0  1  2  3
 * 4  5  6  7
 * 8  9  10 11
 * 12 13 14 15
 */

// Determine what the heads are.
// "Heads" are the first (top) value in the diagonal.
int * find_heads(int world_size, int *heads, int root){
    // Get the "regular" heads. (0, 1, 2, 3, 4 in the Example Matrix)
    int i;
    int head = -1;
    printf("The values in the 'heads' array represents the top values in the diagonal.\n");
    for(i = 0; i <= root; i++){
        head++;
        heads[i] = head;
        printf("heads[%d] = %d\n", i, heads[i]);
    }

    // Get the "irregular" (8, 12 in the Example Matrix) heads.
    int j;
    for(j = 0; j < (root - 2); j++){
        head += root;
        heads[i] = head;
        printf("heads[%d] = %d\n", i, heads[i]);
        i++;
    }

    return heads;
}

// See if rank is in the heads array.
int head_check(int rank, int *heads, int heads_length){
    int i;
    for( i = 0; i < heads_length; i++){
        if (heads[i] == rank){
            return i;
        }
    }
    return -1;
}

// Determine what "color" a rank should be in.
// A color defines a which communicator a rank will be in.
// In this case we are grouping on the diagonals.
int find_color(int world_size, int rank, int *heads, int heads_length){
    int color;
    // How much to subract from a rank until it eventually matches one of the heads.
    int sub = sqrt(world_size) + 1;
    color = -1;
    // Keep subracting from the rank until it matches one of the heads.
    // If it matches a head it is in the same diagonal as that head.
    while(color == -1){
        color = head_check(rank, heads, heads_length);
        rank -= sub;
    }

    return color;
}

int main(int argc, char **argv){

    // Initialize MPI
    MPI_Init(&argc,&argv);

    // Get the number of processes
    int world_size;
    MPI_Comm_size(MPI_COMM_WORLD, &world_size);

    // Get the rank of the process
    int world_rank;
    MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);

    // Exit if number of processes is not a perfect square
    if(world_size != (int)(sqrt(world_size)) * (int)(sqrt(world_size))){
        exit(4);
    }

    int root = sqrt(world_size);

    // Determine how many diagonals there will be in total.
    // 7 in the Example Matrix
    int num_diags = root + (root - 1);

    int heads_length = num_diags;

    // A "head" is the first (top) value in the diagonal.
    // 0, 1, 2, 3, 4, 8, 12 in the Example Matrix
    int *heads = malloc(sizeof(int) * num_diags);

    // The determining of heads only needs to be done once.
    if(world_rank == 0){
        heads = find_heads(world_size, heads, root);
    }

    // Share the heads array with all other ranks.
    MPI_Bcast(heads, heads_length, MPI_INT, 0, MPI_COMM_WORLD);

    // Determine what communicator to join.
    int color;
    color = find_color(world_size, world_rank, heads, heads_length);

    // Create a new communicator and add ranks based on color.
    MPI_Comm diag_comm;
    MPI_Comm_split(MPI_COMM_WORLD, color, world_rank, &diag_comm);

    int diag_size;
    int diag_rank;

    MPI_Comm_rank(diag_comm, &diag_rank);
    MPI_Comm_size(diag_comm, &diag_size);

    // Proof that it works as expected
    printf("world_rank %d, world_size %d, row_rank %d, row_size %d, color %d\n", world_rank, world_size, diag_rank, diag_size, color);

    MPI_Finalize();
    return 0;
}

Example output:

$ mpirun -np 9 diag_comm.exe
The values in the 'heads' array represents the top values in the diagonal.
heads[0] = 0
heads[1] = 1
heads[2] = 2
heads[3] = 3
heads[4] = 6
world_rank 1, world_size 9, row_rank 0, row_size 2, color 1
world_rank 2, world_size 9, row_rank 0, row_size 1, color 2
world_rank 3, world_size 9, row_rank 0, row_size 2, color 3
world_rank 4, world_size 9, row_rank 1, row_size 3, color 0
world_rank 5, world_size 9, row_rank 1, row_size 2, color 1
world_rank 6, world_size 9, row_rank 0, row_size 1, color 4
world_rank 8, world_size 9, row_rank 2, row_size 3, color 0
world_rank 0, world_size 9, row_rank 0, row_size 3, color 0
world_rank 7, world_size 9, row_rank 1, row_size 2, color 3
\$\endgroup\$
4
\$\begingroup\$

Can be simplified

Currently, you create a heads array and then use two functions find_color() and head_check() to find the color of each element using the array. But actually, you can determine the color of each element in a much simpler fashion, without ever needing to create a temporary array in the first place.

Essentially, you are trying to trace back each element to its diagonal starting point ("head"), where the starting point may either be on the top or left edge of the matrix. You can determine which edge a given element's head is on by comparing its row number against its column number. Any element where col >= row will have its head be on the top edge, otherwise its head will be on the left edge.

Given the above, you can reduce all of your color finding code to this one function:

// Rank is the element number, in the range 0..(size*size-1)
// Size is the length of the matrix on one side.
int find_color(int rank, int size)
{
    int row = rank / size;
    int col = rank % size;

    if (col >= row) {
        // Diagonal head must be in top row.
        return col - row;
    } else {
        // Diagonal head must be on left side.
        return (row - col) + size - 1;
    }
}
\$\endgroup\$
4
\$\begingroup\$

Separate display and logic

Your find_heads function fills the heads array and it displays it. Usually you'd want to separate these.

void display_heads(int *heads, int diagonal_count) {
    printf("The values in the 'heads' array represents the top values in the diagonal.\n");

    for (int i = 0; i < diagonal_count; i++) {
        printf("heads[%d] = %d\n", i, heads[i]);
    }
}

And remove the printf commands from find_heads.

The advantage of this is that you can display the heads values as many times as you want now. Or find them without displaying. The two functions are more flexible than the original one.

I like the name diagonal_count better than num_diags. I use plural variables names for arrays and other collections, e.g. heads.

Note that unless you are writing to be compatible with an old C standard, you can define variables in a for loop like in C++.

Don't create unnecessary variables

    // Get the "irregular" (8, 12 in the Example Matrix) heads.
    int j;
    for(j = 0; j < (root - 2); j++){

You only use j to count the number of times that you iterate. But you don't need that.

And the int j; suggests that you aren't compiling to an old standard that requires variables to be defined at the beginning of a block.

    // Get the "irregular" (8, 12 in the Example Matrix) heads.
    for (int n = root * root; head < n; i++) {

This does make the loop a bit goofy though. Is it controlled by n, head, i, or something else?

Or even better might be to rewrite the whole function.

void find_heads(int world_size, int *heads, int root){
    // Get the "regular" heads. (0, 1, 2, 3 in the Example Matrix)
    int i = 0;
    for (; i < root; i++){
        heads[i] = i;
    }

    // Get the "irregular" (4, 8, 12 in the Example Matrix) heads.
    for (int head = root; head < world_size; head += root) {
        heads[i] = head;
        i++;
    }
}

Now the second loop looks like a for loop should. It iterates over head.

The first loop is a bit different. Because we want i to be available outside the loop, we have to declare it outside the loop. We could separate the declaration and the initialization, but that's not recommended. So I moved both outside the loop.

We don't have to define a head variable until the second loop. Until then, the values of head and i are the same.

We don't need to return heads. The array is effectively passed by reference. The function modifies heads directly.

        heads = find_heads(world_size, heads, root);

could just be

        find_heads(world_size, heads, root);

No need to reassign heads.

No need to iterate

int head_check(int rank, int *heads, int heads_length){
    int i;
    for( i = 0; i < heads_length; i++){
        if (heads[i] == rank){
            return i;
        }
    }
    return -1;
}

You iterate over the heads array, but you don't need to do that. You can calculate that directly.

int head_check(int rank, int row_length, int size) {
    if (row >= size) {
        return -1;
    }

    if (rank < row_length) {
        return rank;
    }

    if (rank % row_length == 0) {
        return row_length - 1 + rank / row_length;
    }

    return -1;
}

The original was \$\mathcal{O}(\sqrt{n})\$, where \$n\$ is the size of the matrix. This version is constant time.

The original version was called

        color = head_check(rank, heads, heads_length);

You'd call this version

        color = head_check(rank, root, world_size);

Similarly,

int find_color(int world_size, int rank, int *heads, int heads_length){
    int color;
    // How much to subract from a rank until it eventually matches one of the heads.
    int sub = sqrt(world_size) + 1;
    color = -1;
    // Keep subracting from the rank until it matches one of the heads.
    // If it matches a head it is in the same diagonal as that head.
    while(color == -1){
        color = head_check(rank, heads, heads_length);
        rank -= sub;
    }

    return color;
}

Could be written

int find_color(int rank, int row_length, int size) {
    // after the end of the matrix
    if (rank >= size) {
        return -1;
    }

    int y = rank / row_length;
    int x = rank % row_length;

    // if below the main diagonal
    // the column will be less than the row
    if (x < y) {
        // irregular head
        // subtract x columns will be in column 0
        // first one is row_length and on the second row
        // subtract the column from the row to find the row of the head
        return row_length + y - 1 - x;
    }

    // if on or above the main diagonal
    // regular head
    return rank % (1 + row_length);
}

And then you wouldn't need check_head at all in this code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.