OpenMPI를 사용하는 BFS

Question

OpenMPI를 사용하여 너비 우선 탐색을 구현하려고합니다. (관련이있는 경우 C++에서) 거의 끝나면 아무것도 실행하지 않습니다. 나는 언제/어떻게 실행을 멈출 지 모른다.

graph[start][finish] - there is an edge from vertex start to vertex finish 

나의 현재 알고리즘은 : 다음

는 I 그래프의 모든 에지를 추적하기 위해 2 차원 배열을 사용

1. 루트 거리는 0을 가지며, 다른 사람이 INT_MAX
2. 루트가 모든 인접 노드로 거리를 보내고 중지합니다.
3. 다른 노드는 거리를받습니다.
4. If 새로운 거리가 현재의 거리, 업데이트 거리보다 (작은) 더 나은 내가 정말 그렇게 5 단계를 변경하는 방법을 모르는 3

단계에서 시작

반복 영원히 다른 모든 이웃에게 새로운 거리를 보내 모든 것이 멈 춥니 다. 나는 작은 그래프에서 (그래서 나는 무슨 일이 일어나는지 쉽게 알 수있다.) 모든 비거리가 발견되고 아무런 프로세스도 업데이트를 보내지 않기 때문에 모든 비 루트 프로세스가 3 단계에서 멈추는 것을 의미한다.

알고리즘은 이해하기 쉽고 내 질문은 코드 자체보다는 알고리즘과 관련이 있기 때문에 필자는 코드를 포함하지 않았다.

Answer 1

발견 된 솔루션은 4에서 5 사이의 중간 단계를 추가하여 프로세스에서 루트로 업데이트를 보냅니다.

각 반복 후에 프로세스 p는이 반복 거리를 업데이트했는지 여부를 알려주는 메시지를 루트로 보냅니다. 모든 프로세스가 거리를 업데이트하지 않았다고 "보고"하면 (루트에서) 중지 할 메시지를받습니다. 이 버그/나쁜 로직을 포함 할 수 있으므로

if (rank == 0) // root 
{ 
    distance = 0; 
    for each neighbor 
     send distance 

    vector<bool> status(no_processes - 1, true) 
    while (status contains one true value) 
     receive update from one process 
     update status 

    // status is full of false 
    send all STOP 
} 
else 
{ 
    distance = INT_MAX; 
    while (true) 
    { 
     receive message 

     if STOP 
      stop execution 

     status = false; 
     if (recv_distance + 1 < distance) 
     { 
      status = true 

      distance = recv_distance + 1; 

      for each neighbor 
       send distance 
     } 

     send status to root 
    } 
}