面试题：C语言Dijkstra算法的并行化

并行化设计思路

任务划分：
- 节点划分：可以按节点进行任务划分。将图中的节点集合划分为多个子集，每个子集分配给一个线程或进程处理。例如，在一个有N个节点的图中，若有P个处理器，可将节点按顺序分成P份，每份约N/P个节点。每个线程/进程负责处理自己子集内节点的距离更新工作。
- 层次划分：采用层次化的划分方式。先对图进行粗粒度划分，比如将图按区域划分为几个大的子图，每个子图分配给一个进程处理。然后在每个进程内部，再对其负责的子图按节点进行细粒度划分，分配给线程处理。
同步数据：
- 共享内存（OpenMP）：使用共享变量来存储距离数组等全局数据。线程通过临界区（#pragma omp critical）来安全地更新共享数据。例如，当一个线程发现到某个节点的更短路径时，需要更新全局的距离数组，此时要进入临界区以避免竞争条件。
- 分布式内存（MPI）：进程间通过消息传递来同步数据。每个进程维护自己局部的距离数组。当一个进程更新了自己局部数组中某个节点的距离后，若该节点的信息可能影响其他进程，就需要通过MPI的通信函数（如MPI_Send和MPI_Recv）将更新后的信息发送给相关进程。例如，边界节点的距离更新需要通知相邻子图对应的进程。
可能遇到的问题及解决方案：
- 竞争条件：
  - 问题：多个线程/进程同时尝试更新共享数据（如距离数组）时可能产生不一致。
  - 解决方案：在共享内存环境下，使用临界区、互斥锁（omp_lock_t）等机制；在分布式内存环境下，通过合理的消息传递顺序和同步点来避免。
- 负载不均衡：
  - 问题：不同线程/进程处理的任务量可能差异较大，导致部分处理器闲置，整体效率不高。
  - 解决方案：动态任务分配。在OpenMP中，可以使用#pragma omp task结合#pragma omp taskwait来动态分配任务，让空闲的线程获取新任务。在MPI中，可以采用工作窃取算法，空闲进程向忙碌进程请求任务。
- 通信开销：
  - 问题：在分布式内存环境下，频繁的消息传递会带来较大的通信开销，降低并行效率。
  - 解决方案：减少不必要的通信。可以批量发送数据，而不是每次小更新都发送消息。另外，优化通信拓扑结构，例如使用环形拓扑或树形拓扑来减少通信延迟。

基于OpenMP的关键代码实现

#include <stdio.h>
#include <omp.h>
#include <limits.h>

#define V 9 // 图中节点数

// 找到距离数组中最小值的节点
int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, minIndex;
    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
}

// 打印距离数组
void printSolution(int dist[]) {
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}

// Dijkstra算法并行化实现
void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int sptSet[V];
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = 0;
    }
    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = 1;

        #pragma omp parallel for
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                #pragma omp critical
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    printSolution(dist);
}

基于MPI的关键代码实现

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

#define V 9 // 图中节点数

// 找到距离数组中最小值的节点
int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, minIndex;
    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
}

// 打印距离数组
void printSolution(int dist[]) {
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}

// Dijkstra算法并行化实现
void dijkstra(int graph[V][V], int src, int rank, int size) {
    int dist[V];
    int sptSet[V];
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = 0;
    }
    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = 1;

        // 局部更新
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }

        // 进程间同步
        int globalDist[V];
        MPI_Allgather(dist, V, MPI_INT, globalDist, V, MPI_INT, MPI_COMM_WORLD);
        for (int i = 0; i < V; i++) {
            dist[i] = globalDist[i];
        }
    }
    if (rank == 0) {
        printSolution(dist);
    }
}

在MPI程序的main函数中：

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

    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };

    dijkstra(graph, 0, rank, size);

    MPI_Finalize();
    return 0;
}

星途面试题库

面试题：C语言Dijkstra算法的并行化

知识考点

面试题答案

并行化设计思路

基于OpenMP的关键代码实现

基于MPI的关键代码实现