그래프상의 두 노드 사이에 가능한 모든 경로에 대한 GPU 기반 검색

내 작업은 Migliore, Martorana 및 Sciortino의 알고리즘을 광범위하게 사용하여 가능한 모든 간단한 경로를 찾습니다. 즉 노드가 두 번 이상 나오지 않는 경우, 그래프는 An Algorithm to find All Paths between Two Nodes in a Graph에 설명되어 있습니다. (이 알고리즘은 본질적으로 깊이 우선 탐색이고 직관적으로 재귀 적이지만 저자는 또한 비 반복적 인 스택 기반 구현을 제시합니다.) 이러한 알고리즘을 GPU에서 구현할 수 있는지 알고 싶습니다. 현재이 문제에서 어떤 실제 병렬 처리가 있는지 고민하고 있습니다. 예를 들어, 쓰레드를 모니터링하고 디스 패칭하는 비용은 (하드웨어 쓰레드에 의한) 협조적인 그래프 검색을 금지 할 수 있습니다. 또는 그래프가 분할되어 검색을 위해 개별 하드웨어 스레드에 할당되는 경우 나누기 및 정복 전략이 작동 할 수 있습니다. 그러나 (1) 그래프를 분할하고 (2) 하위 작업을 공식화하고 (3) 파티션에서 검색 결과를 결합하는 방법을 알아 내야합니다.그래프상의 두 노드 사이에 가능한 모든 경로에 대한 GPU 기반 검색

출처

2011-01-05 Olumide

잠재적으로 지수 적으로 많은 경로가 있습니다. 모든 경로 목록 또는 경로 수만 나열하거나 모든 경로를 열거 할 수있는 암시 적 구조를 찾고 있습니까? – templatetypedef

나는 그러한 모든 경로의 목록에 관심이 있습니다. – Olumide

GPU는 메모리로드 (산술 밀도)의 수에 비해 계산 수가 많은 작업에 매우 적합합니다. 또한 프로세서의 SIMD 특성 때문에 분기를 잘 처리하지 못하기 때문에이 문제는 GPU 포팅에 적합하지 않다고 생각합니다. – Samsdram

조금 녹슬 었습니다. Dijkstra는 어떨까요?

Boolean[] visited;    // [node] = true; 
Boolean[][] connected;   // [node][i] = node 
Vector<Vector<Integer>>[] path; // this should suck 
Integer startNode; 
Integer endNode; 
Queue queue0; //for thread 0 
Queue queue1; //for thread 1 

while (queue0.hasNext()) { 
    Integer node = queue.getNext(); 
    if visited[node] { 
     continue; 
    } else { 
     visited[node] = true; 
    } 

    for (nextNode: connected[node]) { 
     for (i) { 
     path[nextNode].append(path[node][i].clone().append(node)); 
     } 
     if (nextNode%2 == 0) { queue0.add(nextNode); } 
     if (nextNode%2 == 1) { queue1.add(nextNode); } 
    } 
}

경로 [말단 노드] [내가] //은 StartNode

파티션에서 말단 노드에 i 번째 경로 : 노드 %에서 2 개
하위 온 : 당신은 공유 : 결합 노드
에서 갈 장소를 찾을 기억, 맞지?

출처

2011-01-05 06:57:46

답변의 마지막 부분을 이해하지 못합니다. 각 하드웨어 스레드가 깊이 검색을 수행하도록 제안 하시겠습니까? – Olumide

이고 GPU에서는이를 허용하지 않습니다. 시간 내 주셔서 죄송합니다. –

문제가 GPU에서 쉽게 수행 될 수 있다고 생각하지 않습니다. 대부분의 GPU 전원을 사용하는 GPU 프로그램 :

스레드의 수는 있지만 그 수는 일정합니다. 새 스레드를 생성하거나 이전 스레드를 삭제하지 않습니다.
통합 메모리 액세스를 선호합니다. 인접한 스레드가 메모리의 다른 영역에 완전히 액세스하면 (보통 그래프 알고리즘이 수행함) 속도가 느려집니다.
재귀 및 스택을 싫어합니다. 최신 NVIDIA Fermi 카드는 함수 호출을 지원하며 스레드는 스택을 가질 수 있지만 스레드 수가 많기 때문에 스택이 매우 짧습니다 (또는 많은 메모리를 소비합니다). 내가하지을

는 더 효율적인 GPU 알고리즘이 없다고 말하지만, 나는 효율적인 코드로 기존 알고리즘을 변형 할 간단한 방법이 없다고 생각합니다.

출처

2011-02-27 20:41:42 CygnusX1

그래프상의 두 노드 사이에 가능한 모든 경로에 대한 GPU 기반 검색

답변

관련 문제