2
병렬 컴퓨팅에서 일반적으로 원점 문제를 일부 하위 작업으로 나누고이를 블록 및 스레드로 매핑하는 첫 번째 단계입니다.CUDA 프로그래밍의 블록에 그래프를 매핑하는 효율적인 방법이 있습니까?
일반적인 데이터 구조의 문제는 매트릭스 곱셈, FFT 등 매우 쉽고 효율적입니다.
그러나 최단 경로, 그래프 순회, 트리 검색과 같은 그래프 이론 문제는 불규칙한 데이터 구조를 가지고 있습니다. 최소한 내 생각에는 GPU를 사용할 때 문제를 블록과 스레드로 분할하는 것이 쉽지 않은 것 같습니다.
이런 종류의 파티션에 효율적인 솔루션이 있는지 궁금합니다.
단순화를 위해 단일 소스 최단 경로 문제를 예를 들어 설명합니다. 나는 그래프를 어떻게 나눌 것인가에 집중하여 지역 성과 합쳐 놓았다.
합니다. 특정 응용 프로그램을 염두에 두셨습니까? 당신이 요구하는 범위를 좁힐 수 있습니까? – talonmies
찾고있는 알고리즘의 적용 영역에 대해 더 많이 말해 줄 수 있습니까? 가장 가까운 이웃 검색에서 경험을 공유 할 수 있지만 스패닝 트리 검색과 같은 일반적인 그래프 문제에 대해 질문하는 경우 도움이 될 수 없습니다. – geek
@ marina.k 단일 소스 최단 경로 문제에서 작업하지 않습니다. 첫째, 많은 핵심 시스템에서 Dijkstra 알고리즘을 구현하는 것이 어렵다는 것입니다. 둘째, Dijkstra 알고리즘과 유사한 반복 솔루션을 사용하면 노드 간의 제약이 매우 복잡하고 불규칙하므로 공유 메모리를 사용하여 캐시하기 위해 지역성과 합치기를 보장하기가 어렵습니다. – konjac