Btukfyl

I'm trying to write an implementation of a hyper quicksort in MPI, but I'm having an issue where a process gets stuck on MPI_Recv().

While testing with 2 processes, it seems that inside the else of the if (rank % comm_sz == 0), process 1 is never receiving the pivot from process 0. Process 0 successfully sends its pivot and recurses through the method correctly. If put in some print debug statements and received the output:

(arr, 0, 2, 0, 9)

Rank 0 sending pivot 7 to 1

(arr, 1, 2, 0, 9)

Rank 1 pre-recv from 0

After which, the post-recv message from rank 1 never prints. Rank 0 prints its post-send message and continues through its section of the array. Is there something wrong with my implementation of MPI_Send() or MPI_Recv() that may be causing this?

Here is my code for the quicksort:

(For reference, comm_sz in the parameters for the method refers to the number of processes looking at that section of the array.)

void hyper_quick(int *array, int rank, int comm_sz, int s, int e) {

    printf("(arr, %d, %d, %d, %d)n", rank, comm_sz, s, e);

    // Keeps recursing until there is only one element

    if (s < e) {

            int pivot;

            if (comm_sz > 1) {

                    // One process gets a random pivot within its range and sends that to every process looking at that range

                    if (rank % comm_sz == 0) {

                            pivot = rand() % (e - s) + s;

                            for (int i = rank + 1; i < comm_sz; i++) {

                                    int partner = rank + i;

                                    printf("Rank %d sending pivot %d to %dn", rank, pivot, partner);

                                    MPI_Send(&pivot, 1, MPI_INT, partner, rank, MPI_COMM_WORLD);

                                    printf("Rank %d successfully sent %d to %dn", rank, pivot, partner);

                            }

                    }

                    else {

                            int partner = rank - (rank % comm_sz);

                            printf("Rank %d pre-recv from %dn", rank, partner);

                            MPI_Recv(&pivot, 1, MPI_INT, partner, rank, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

                            printf("Rank %d received pivot %d from %dn", rank, pivot, partner);

                    }

            }

            else {

                    pivot = rand() % (e - s) + s;

            }

            int tmp = array[pivot];

            array[pivot] = array[e];

            array[e] = tmp;

            // Here is where the actual quick sort happens

            int i = s;

            int j = e - 1;

            while (i < j) {

                    while (array[e] >= array[i] && i < j) {

                            i++;

                    }

                    while (array[e] < array[j] && i < j) {

                            j--;

                    }

                    if (i < j) {

                            tmp = array[i];

                            array[i] = array[j];

                            array[j] = tmp;

                    }

            }

            if (array[e] < array[i]) {

                    tmp = array[i];

                    array[i] = array[e];

                    array[e] = tmp;

                    pivot = i;

            }

            else {

                    pivot = e;

            }

            // Split remaining elements between remaining processes

            if (comm_sz > 1) {

                    // Elements greater than pivot

                    if (rank % comm_sz >= comm_sz/2) {

                            hyper_quick(array, rank, comm_sz/2, pivot + 1, e);

                    }

                    // Elements lesser than pivot

                    else {

                            hyper_quick(array, rank, comm_sz/2, s, pivot - 1);

                    }

            }

            // Recurse remaining elements in current process

            else {

                    hyper_quick(array, rank, 1, s, pivot - 1);

                    hyper_quick(array, rank, 1, pivot + 1, e);

            }

    }

Rank 0 sending pivot 7 to 1

MPI_Send(&pivot, 1, MPI_INT, partner, rank, MPI_COMM_WORLD);

                                      ^^^^

So the sender tag is zero.

Rank 1 pre-recv from 0

MPI_Recv(&pivot, 1, MPI_INT, partner, rank, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

                                      ^^^^

And the receiver tag is one.

If the receiver asks for only messages with a specific tag, it will not receive a message with a different tag.

Sometimes there are cases when A might have to send many different types of messages to B. Instead of B having to go through extra measures to differentiate all these messages, MPI allows senders and receivers to also specify message IDs with the message (known as tags). When process B only requests a message with a certain tag number, messages with different tags will be buffered by the network until B is ready for them. [MPI Tutorial -- Send and Receive]