MPI并行化二维数组最小值求解求助：串行转并行改造问题

Hey there! Let's walk through fixing your MPI parallelization for finding the matrix minimum. Your core idea (using MPI_Scatter to split the matrix and MPI_Reduce to find the global min) is solid, but there are a few critical issues with how you're handling memory, MPI buffers, and parallel logic that's causing the garbage output.

Key Issues in Your Attempt #

• Non-contiguous 2D Array: Your original int** arr uses separate malloc calls for each row, meaning the memory isn't contiguous. MPI requires contiguous buffers for collective operations like MPI_Scatter—this is a major source of garbage data.
• Incorrect Scatter Buffer: The receive buffer in your MPI_Scatter call (&arr[rows][cols]) is way out of bounds of your original array. Each process needs its own separate buffer to hold its chunk of the matrix.
• Wrong MPI_Reduce Parameters: You're passing rows*cols/numprocs as the count, but MPI_Reduce only needs to send one value per process (your local minimum), not the entire chunk.
• Uncoordinated Data Generation: Every process is calling srand(time(NULL)), which can lead to identical random numbers across processes if they start at the same time. We should let rank 0 generate all data and distribute it.
• Memory Management: Only rank 0 was freeing memory, but other processes might also allocate buffers that need cleanup.

Fixed Parallel Code #

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

int main(int argc, char *argv[]) {
    int rows, cols, global_min, local_min, numprocs, rank;
    int done = 0;
    double startwtime = 0.0, endwtime;
    int namelen;
    char processor_name[MPI_MAX_PROCESSOR_NAME];

    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Get_processor_name(processor_name, &namelen);

    while (!done) {
        // Step 1: Rank 0 gets matrix dimensions and broadcasts to all processes
        if (rank == 0) {
            printf("\nEnter the height/width of the matrix (0 0 to exit):\n");
            scanf("%d %d", &rows, &cols);
        }
        MPI_Bcast(&rows, 1, MPI_INT, 0, MPI_COMM_WORLD);
        MPI_Bcast(&cols, 1, MPI_INT, 0, MPI_COMM_WORLD);

        // Check exit condition
        if (rows == 0 || cols == 0) {
            done = 1;
            MPI_Barrier(MPI_COMM_WORLD);
            continue;
        }

        int total_elements = rows * cols;
        int chunk_size = total_elements / numprocs;
        int remainder = total_elements % numprocs;

        // Step 2: Allocate buffers
        int *matrix = NULL;
        int *local_chunk = (int*)malloc(chunk_size * sizeof(int));
        if (!local_chunk) {
            fprintf(stderr, "Rank %d: Failed to allocate local chunk\n", rank);
            MPI_Abort(MPI_COMM_WORLD, 1);
        }

        if (rank == 0) {
            // Contiguous 1D array simulates 2D matrix for MPI compatibility
            matrix = (int*)malloc(total_elements * sizeof(int));
            if (!matrix) {
                fprintf(stderr, "Rank 0: Failed to allocate matrix\n");
                MPI_Abort(MPI_COMM_WORLD, 1);
            }
            // Seed random generator once (only rank 0)
            srand(time(NULL));
            for (int i = 0; i < total_elements; i++) {
                matrix[i] = rand();
            }
            // Optional: Print full matrix (only rank 0 to avoid clutter)
            printf("\nGenerated Matrix:\n");
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    printf("%d ", matrix[i*cols + j]);
                }
                printf("\n");
            }
            startwtime = MPI_Wtime();
        }

        // Step 3: Distribute matrix chunks to all processes
        MPI_Scatter(matrix, chunk_size, MPI_INT, local_chunk, chunk_size, MPI_INT, 0, MPI_COMM_WORLD);

        // Step 4: Each process finds its local minimum
        local_min = local_chunk[0];
        for (int i = 1; i < chunk_size; i++) {
            if (local_chunk[i] < local_min) {
                local_min = local_chunk[i];
            }
        }

        // Step 5: Rank 0 handles leftover elements (if total elements aren't divisible by numprocs)
        if (rank == 0 && remainder > 0) {
            int remainder_min = matrix[total_elements - remainder];
            for (int i = total_elements - remainder + 1; i < total_elements; i++) {
                if (matrix[i] < remainder_min) {
                    remainder_min = matrix[i];
                }
            }
            if (remainder_min < local_min) {
                local_min = remainder_min;
            }
        }

        // Step 6: Reduce all local mins to find global minimum (rank 0 gets result)
        MPI_Reduce(&local_min, &global_min, 1, MPI_INT, MPI_MIN, 0, MPI_COMM_WORLD);

        // Step 7: Rank 0 prints results and cleans up
        if (rank == 0) {
            endwtime = MPI_Wtime();
            printf("\nGlobal Minimum: %d\n", global_min);
            printf("Wall Clock Time: %f seconds\n", endwtime - startwtime);
            fflush(stdout);
            free(matrix);
        }

        // Cleanup local buffer for all processes
        free(local_chunk);
        MPI_Barrier(MPI_COMM_WORLD);
    }

    MPI_Finalize();
    return 0;
}

Key Fixes Explained #

1. Contiguous Memory: We use a 1D array to simulate the 2D matrix, ensuring memory is contiguous—this is mandatory for MPI collective operations to work correctly.
2. Broadcast Dimensions: Rank 0 sends matrix dimensions to all processes via MPI_Bcast, so everyone knows how much data to allocate and process.
3. Proper Scatter Setup: Each process allocates its own local_chunk buffer to receive its portion of the matrix, eliminating out-of-bounds access.
4. Correct Reduce Usage: We pass 1 as the count to MPI_Reduce because each process only sends its single local minimum value. The MPI_MIN operator efficiently computes the global minimum.
5. Remainder Handling: If the total number of elements isn't divisible by the number of processes, rank 0 handles the leftover elements separately and merges that result into its local minimum.
6. Coordinated Random Generation: Only rank 0 seeds the random number generator, ensuring unique values across the matrix.
7. Safe Memory Cleanup: Every process frees its own local buffer, and rank 0 frees the full matrix to avoid memory leaks.

Compilation & Run Instructions #

To compile and run (assuming you have an MPI implementation like OpenMPI installed):

mpicc -o matrix_min matrix_min.c
mpiexec -n 4 ./matrix_min

Replace 4 with the number of processes you want to use.

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