使用MPI_Gather合并各进程素数数组时出现异常的技术求助

Hey there! Let’s tackle that annoying extra zero problem you’re hitting when gathering primes with MPI. Those zeros pop up because MPI_Gather expects all processes to send the same number of elements by default—but since different ranges have different numbers of primes, the shorter buffers get padded with zeros. Here’s how to fix this properly.

Why the Zeros Happen #

Each process finds a variable number of primes (e.g., process 0 finds 4 primes, process 1 finds 2, process 2 finds 3). When you use plain MPI_Gather, it assumes every send buffer is the same length. So the process with only 2 primes will send its 2 primes plus whatever garbage/zeros are left in its buffer to reach the fixed length. Those extra values end up in your final array.

Solution 1: Use MPI_Gatherv (Recommended for Scalability) #

MPI_Gatherv is designed for gathering variable-length data from multiple processes. Here’s a step-by-step implementation:

1. Each process counts its local primes
2. Gather all counts to the root process so it knows how much data to expect from each rank
3. Calculate displacement values (where each process’s data starts in the root’s buffer)
4. Gather the primes with MPI_Gatherv to avoid padding zeros

Example Code Snippet (C) #

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

// Helper function to find primes in a range (your existing logic)
int find_primes(int start, int end, int *primes) {
    int count = 0;
    for (int num = start; num <= end; num++) {
        int is_prime = 1;
        for (int i = 2; i*i <= num; i++) {
            if (num % i == 0) {
                is_prime = 0;
                break;
            }
        }
        if (is_prime && num >= 2) {
            primes[count++] = num;
        }
    }
    return count;
}

int main(int argc, char **argv) {
    MPI_Init(&argc, &argv);
    int rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    // Split your number range (adjust based on your logic)
    int total_range = 20;
    int range_per_process = total_range / size;
    int start = rank * range_per_process + 2; // Start from 2 (first prime)
    int end = (rank == size-1) ? total_range : (rank+1)*range_per_process +1;

    // Local prime storage (make buffer large enough for your range)
    int local_primes[100];
    int local_count = find_primes(start, end, local_primes);

    // Step 1: Gather all local prime counts to root
    int *counts = NULL;
    if (rank == 0) {
        counts = malloc(size * sizeof(int));
    }
    MPI_Gather(&local_count, 1, MPI_INT, counts, 1, MPI_INT, 0, MPI_COMM_WORLD);

    // Step 2: Calculate total primes and displacement array for root
    int total_primes = 0;
    int *displs = NULL;
    if (rank == 0) {
        displs = malloc(size * sizeof(int));
        displs[0] = 0;
        total_primes = counts[0];
        for (int i = 1; i < size; i++) {
            displs[i] = displs[i-1] + counts[i-1];
            total_primes += counts[i];
        }
    }

    // Step 3: Gather variable-length prime arrays with MPI_Gatherv
    int *all_primes = NULL;
    if (rank == 0) {
        all_primes = malloc(total_primes * sizeof(int));
    }
    MPI_Gatherv(local_primes, local_count, MPI_INT, all_primes, counts, displs, MPI_INT, 0, MPI_COMM_WORLD);

    // Root process prints the clean prime list (no zeros!)
    if (rank == 0) {
        printf("All primes found: ");
        for (int i = 0; i < total_primes; i++) {
            printf("%d ", all_primes[i]);
        }
        printf("\n");

        // Clean up allocated memory
        free(counts);
        free(displs);
        free(all_primes);
    }

    MPI_Finalize();
    return 0;
}

Solution 2: Manual Send/Recv (Simpler for Smaller Programs) #

If you prefer avoiding MPI_Gatherv, you can have the root process explicitly request the number of primes from each rank before receiving the actual primes:

Example Code Snippet #

// Inside main(), after calculating local_count and local_primes
if (rank == 0) {
    int all_primes[200];
    int current_index = 0;

    // Add root's own primes first
    for (int i = 0; i < local_count; i++) {
        all_primes[current_index++] = local_primes[i];
    }

    // Receive from each other process
    for (int i = 1; i < size; i++) {
        int remote_count;
        // First get the number of primes from rank i
        MPI_Recv(&remote_count, 1, MPI_INT, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        // Then receive the primes themselves
        MPI_Recv(&all_primes[current_index], remote_count, MPI_INT, i, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        current_index += remote_count;
    }

    // Print results
    printf("All primes found: ");
    for (int i = 0; i < current_index; i++) {
        printf("%d ", all_primes[i]);
    }
    printf("\n");
} else {
    // Send count first, then primes
    MPI_Send(&local_count, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
    MPI_Send(local_primes, local_count, MPI_INT, 0, 1, MPI_COMM_WORLD);
}

Key Notes #

• Buffer Size: Make sure your local prime buffer is large enough to hold all primes in the process’s range—otherwise you’ll get memory corruption.
• Memory Management: Always free dynamically allocated memory (like counts and displs in the first example) to avoid leaks.
• Edge Cases: Don’t forget to handle the last process’s range correctly (since total range might not divide evenly by the number of processes).

内容的提问来源于stack exchange，提问作者Adjit