병렬 범위 우선 검색

너비 우선 검색 알고리즘은 계층별로 그래프 정점을 탐색하는 방법이다.그것은 다른 그래프 알고리즘의 일부로 사용될 수 있는 그래프 이론의 기본 알고리즘이다.예를 들어, BFS는 Dinic의 알고리즘에 의해 그래프에서 최대 흐름을 찾는 데 사용된다.더욱이 BFS는 데이터 집약적인 슈퍼컴퓨팅 문제의 벤치마크인 Graph500 벤치마크에서도 커널 알고리즘 중 하나이다.^[1]이 글에서는 병렬 컴퓨팅의 사용을 통해 BFS를 가속화할 수 있는 가능성에 대해 논의한다.

직렬 너비 우선 검색

기존의 순차 BFS 알고리즘에서는 프런티어와 다음 프런티어를 저장하기 위해 두 개의 데이터 구조가 생성된다.프런티어는 원천 정점으로부터 같은 거리("레벨"이라고도 함)를 갖는 정점을 포함하며, 이러한 정점은 BFS에서 탐구할 필요가 있다.이 꼭지점의 모든 이웃을 확인할 것이며, 아직 탐사되지 않은 몇몇 이웃을 발견하여 다음 개척지로 보낼 것이다.BFS 알고리즘의 시작에서 주어진 소스 꼭지점 s는 프론티어의 유일한 꼭지점이다.다음 개척지를 형성하는 첫 번째 단계에서 s의 모든 직접 이웃을 방문한다.각 층 이동 후, "다음 개척지"는 변경지로 전환되고 새로운 다음 개척지에 새로운 꼭지점이 저장될 것이다.다음의 사이비 코드는 그것의 아이디어를 개략적으로 설명하는데, 그 안에서 프런티어와 다음 프런티어의 데이터 구조를 각각 FS와 NS라고 부른다.

1    define bfs_sequential(graph(V,E), source s): 2        for all v in V do 3            d[v] = -1; 4        d[s] = 0; level = 1; FS = {}; NS = {}; 5        push(s, FS); 6        while FS !empty do 7            for u in FS do  8                for each neighbour v of u do  9                    if d[v] = -1 then 10                       push(v, NS); 11 d[v] = 레벨; 12 FS = NS, NS = {}, 레벨 = 레벨 + 1;

병렬화의 첫 단계

단순하고 직관적인 솔루션으로서, 고전적인 PRAM(Parallel Random Access Machine) 접근방식은 위에서 제시한 순차 알고리즘의 확장일 뿐이다.두 개의 포루프(라인 7과 라인 8)를 병렬로 실행할 수 있다.다음 개척지(10호선)의 갱신과 거리 증가(11호선)는 원자적일 필요가 있다.원자력은 중단과 일시 중지 없이 전체적으로만 실행할 수 있는 프로그램 운영이다.

그러나 이 간단한 병렬화에는 두 가지 문제가 있다.첫째, 거리 점검(9호선)과 거리 업데이트 운영(11호선)은 두 개의 양성 인종을 도입한다.한 꼭지점의 이웃도 국경의 다른 꼭지점의 이웃이 될 수 있기 때문이다.결과적으로, 이 이웃의 거리는 한 번 이상 조사되고 업데이트될 수 있다.이러한 인종이 자원을 낭비하고 불필요한 오버헤드를 초래하지만, 동기화의 도움으로 BFS의 정확성에 영향을 주지 않기 때문에 이러한 인종이 양성적이다.둘째로, 병렬 프로세싱으로 인한 각 계층 이동의 속도 향상에도 불구하고, 국경선의 모든 인접 정점을 완전히 발견하기 위해서는 모든 계층 뒤에 장벽 동기화가 필요하다.이 계층별 동기화는 필요한 통신의 단계가 두 꼭지점 사이의 가장 긴 거리인 O(d)와 같다는 것을 나타낸다. 여기서 O는 큰 O 표기법이고 d는 그래프 지름이다.

이러한 단순 병렬화의 점증적 복잡성은 최악의 경우 순차 알고리즘과 동일하지만, BFS 병렬화를 더 잘 달성하기 위해 일부 최적화를 할 수 있다. 예를 들면 다음과 같다.

1. 장벽 동기화 완화.병렬 BFS의 정확성을 보장하기 위해 각 계층 이동 후 장애물 동기화가 필요하다.결과적으로, 장벽 동기화 비용을 줄이는 것은 병렬 BFS 속도를 높이는 효과적인 방법이다.
2. 인접 검색을 위한 로드 밸런싱.각 계층 이동 후 장벽 동기화가 있기 때문에 모든 처리 주체는 마지막 작업이 완료될 때까지 기다려야 한다.따라서 가장 이웃이 많은 병렬 실체가 이 계층의 시간 소비를 결정한다.부하분산의 최적화를 통해 계층간 이동시간을 줄일 수 있다.
3. 메모리 참조의 위치 개선.분산된 메모리를 가진 병렬 시스템에서 원격 메모리 레퍼런스는 로컬 메모리 레퍼런스에 비해 통상 통신비용이 추가되는 다른 처리 엔티티로부터 데이터를 얻고 있다.따라서 로컬 메모리 참조는 원격 메모리 참조보다 빠르다.더 나은 데이터 구조를 설계하거나 데이터 구성을 개선함으로써 더 많은 로컬 메모리 참조로 이어질 수 있으며 원격 메모리 참조에 필요한 통신을 줄일 수 있다.

공유 메모리가 있는 병렬 BFS

분산 메모리가 있는 병렬 BFS에 비해 공유 메모리는 메모리 대역폭이 높고 대기 시간이 짧다.모든 프로세서가 메모리를 함께 공유하기 때문에, 모든 프로세서가 메모리를 직접 이용할 수 있다.따라서 개발자들은 원격 로컬 메모리에서 데이터를 얻기 위해 분산 메모리에 필요한 메시지 전달 프로세스를 프로그래밍할 필요가 없다.따라서 메시지의 오버헤드는 피한다.^[2]

그러나 각 층의 정점 수와 각 정점의 이웃 수는 매우 불규칙한 것으로 나타나기 때문에 BFS의 메모리 액세스와 작업 분포가 매우 불규칙하게 된다.병렬 BFS에서 이 기능은 불균형 부하로 인한 병렬화의 이점을 감소시킨다.결과적으로 공유 메모리의 병렬 BFS를 로드 밸런싱으로 만드는 것이 매우 중요하다.더욱이 데이터 지역성을 탐구하는 것은 병렬 처리 속도를 높일 수 있다.

공유 메모리의 많은 병렬 BFS 알고리즘은 용기 중심 접근법과 정점 중심 접근법의 두 가지 유형으로 나눌 수 있다.^[3]컨테이너 중심 접근방식에서, 현재의 최전방과 다음 꼭지점 전선을 저장하기 위해 두 개의 데이터 구조가 생성된다.다음 꼭지점 변경은 각 단계의 마지막 부분에서 현재의 변경으로 전환된다.데이터 저장 장소에 따른 동기화 비용과 데이터 인접성 간에 트레이드오프가 있다.이 두 데이터 구조는 데이터 인접성을 지원하지만 추가적인 부하 분산 메커니즘이 필요한 모든 처리 실체(예: 스레드)에 보관될 수 있다.또는, 그들은 처리 실체로부터의 동시 접속을 위해 특별한 데이터 구조를 사용하는 암묵적 로드 밸런싱을 제공하기 위해 글로벌할 수 있다.그러나 그렇게 되면 그러한 처리 실체는 동시에 작동하게 되고 동기화를 위해 더 많은 노력이 필요하다.

게다가, 컨테이너의 데이터 구성을 최적화할 수 있다.직렬 BFS와 일부 병렬 BFS의 대표적인 데이터 구조는 FIFO 큐로, 삽입 및 삭제 작업 비용이 일정 시간밖에 들지 않는 단순하고 빠르기 때문이다.

또 다른 대안은 가방 구조다.^[4]봉지에 삽입하는 작업은 최악의 경우 O(logn) 시간이 걸리는 반면 FIFO만큼 빠른 상각된 일정한 시간만 소요된다.또한, 두 개의 가방을 결합하는 데는 ((lgn) 시간이 소요되며, 여기서 n은 작은 가방 안에 있는 원소의 수입니다.백 스플릿 작업에도 θ(lgn) 시간이 걸린다.가방 구조의 도움으로 일정한 수의 꼭지점(세밀도 파라미터에 따라)이 하나의 가방에 저장되고 가방 구조가 기본 평행 실체가 된다.게다가 환원기는 가방 구조와 결합하여 정점을 병렬로 쓰고 효율적으로 통과할 수 있다.

정점 중심 접근법은 정점을 평행 반복을 가능하게 하는 평행 실체로 취급한다.각 꼭지점은 평행 실체에 할당된다.이 정점 중심 접근법은 그래프 깊이가 매우 낮은 경우에만 잘 작동할 수 있다.BFS의 그래프 깊이는 그래프에서 소스 정점까지의 모든 정점의 최대 거리로 정의된다.따라서 모든 스레드가 정확히 하나의 꼭지점에 매핑된 경우 정점 중심 접근방식은 GPU에 적합하다.^[3]

분산 메모리가 있는 병렬 BFS

분산 메모리 모델에서 각 처리 엔티티는 자체 메모리를 가지고 있다.이 때문에 처리주체는 지역 데이터를 공유하거나 원격 데이터에 접근하기 위해 서로 메시지를 주고 받아야 한다.

1-D 파티셔닝

1D 파티셔닝은 병렬 BFS를 분산 메모리와 결합하는 가장 간단한 방법이다.정점 분할을 기반으로 한다.로드 밸런싱은 병렬화의 이점을 얻을 수 있는 방법을 결정하는 데이터 파티션에서 여전히 중요한 문제다.즉, 분산 메모리가 있는 각 프로세서(예: 프로세서)는 거의 동일한 수의 꼭지점과 송신 에지를 담당해야 한다.데이터 저장 구현을 위해, 각 프로세서는 각 정점에 대한 각 행이 대상 정점 지수로 표현되는 나가는 가장자리의 행인 로컬 정점의 인접 행렬을 저장할 수 있다.

공유 메모리 BFS와 달리, 한 프로세서의 인접 정점을 다른 프로세서에 저장할 수 있다.결과적으로, 각 프로세서는 프로세서에 메시지를 보내면서 통과 상태에 대해 알려줄 책임이 있다.또한 각 프로세서는 로컬 다음 꼭지점 프런티어를 구성하기 위해 다른 모든 프로세서의 메시지도 처리해야 한다.분명히 현재의 국경과 다음 꼭지점 국경을 교환할 때 각 단계마다 하나의 올투올 커뮤니케이션(각 실체가 다른 모든 것에 대해 서로 다른 메시지를 가지고 있다는 의미)이 필요하다.

다음의 1-D 분산 메모리 BFS^[5] 유사 코드는 원래 3D torus 네트워크 아키텍처를 가진 IBM BlueGene/L 시스템을 위해 설계되었다.동기화는 병렬 BFS의 주요 추가 비용이기 때문에, 본 논문의 저자들은 또한 포인트 투 포인트 통신을 기반으로 확장 가능한 전체 통신 기술을 개발했다.그 후, 그들은 그것의 고대역폭 토러스 네트워크를 이용하여, 지점간 통신의 수를 줄였다.

다음 알고리즘에서 BFS 트래버설의 주요 단계는 다음과 같다.

1. 프로세서 보기(라인 8): 로컬 스토리지에서 정점을 사용하여 프런티어 FS 구성
2. 전역 보기(라인 10–11): 모든 프로세서의 FS가 비어 있으면 통과 종료
3. 프로세서 뷰(라인 13): FS의 인접 정점에 기반하여 다음 프론티어 구성(일부는 다른 프로세서에 저장될 수 있음)
4. 글로벌 뷰(라인 15-18): 각 프로세서에 대해 전체 통신을 실행하여 로컬 다음 프론티어 NS에 어떤 로컬 정점을 넣어야 하는지 알린다.
5. 프로세서 보기(20-22호선): 다른 모든 프로세서에서 메시지 수신, 현재 프론티어의 로컬 꼭지점 거리 값 업데이트, NS를 FS로 변경

1 정의 1_D_distributed_memory_BFS( graph(V,E), source s): 2        //normal initialization 3        for all v in V do 4            d[v] = -1; 5        d[s] = 0; level = 0; FS = {}; NS = {}; 6        //begin BFS traversal 7        while True do: 8            FS = {the set of local vertexes with level} 9            //all vertexes traversed 10           if FS = {} for all processorS:11NS에서 그 동안 루프는 NS지역 vertexes에 현재 국경 13NS에 기반을 두고 12//construct)=14//synchronization:0<>에all-to-all 통신 15^j<>p.16N_j{vertexes의 FS이웃들과 지역이 아니지역 vertexes}{vertexes.을 소유했다 해지하는yprocessor j} 17 processor j 18에 N_j를 전송 j 18 processor j 19 //processor로부터 N_j_rcv를 수신하여 로컬 다음 꼭지점 프론티어를 형성한 후 NS_rcv = Union(N_j_rcv) 21에서 NS_rcv 및 d[v] = -1 d22 d[v] 레벨 +1

다중 스레딩과 결합하여 다음과 같은 1D 분산 메모리 BFS의 사이비 코드도 스레드 스택과 스레드 장벽을 지정하는데, 이는 논문에서 나온 것이다.^[6]

다중 스레딩을 통해 프런티어 FS의 로컬 정점을 분할하여 하나의 프로세서 내부의 다른 스레드에 할당할 수 있으며, 이는 BFS 트래버설과 더욱 평행하게 된다.그러나, 위의 방법과는 달리, 우리는 각각의 스레드에 대해 더 많은 데이터 구조가 필요하다.예를 들어, 이 스레드의 꼭지점에서 인접 정점을 저장하기 위해 준비된 스레드 스택.각 스레드는 p-1 로컬 스토리지를 가지고 있으며 여기서 p는 프로세서 수입니다.각 스레드는 다른 모든 프로세서에 대한 메시지를 분리해야 하기 때문이다.예를 들어, 만약 j 프로세서가 그 정점의 소유자라면, 그들은 이웃 정점을 그들의 j-th 스택에 넣어 j 프로세서로 보내는 메시지를 형성할 것이다.더욱이 동기화를 위해서는 스레드 장벽도 필요하다.그 결과, 멀티스레딩이 가능한 분산 메모리는 병렬화의 정교화에서 유리할 수 있지만, 스레드에 추가 동기화 비용도 도입한다.

다음 알고리즘에서 BFS 트래버설의 주요 단계는 다음과 같다.

1. 스레드 뷰(라인 19-22): 자신에게 할당된 정점을 기준으로 인접 정점의 소유자 프로세서를 찾아 해당 소유자의 스레드 스택 베이스에 넣으십시오.
2. 프로세서 보기(라인 23): 스레드 장벽을 실행하고 (동일한 프로세서의) 모든 스레드가 작업을 마칠 때까지 기다리십시오.
3. 프로세서 보기(25~26행): 소유자가 같은 모든 스레드의 모든 스레드 스택을 병합(다음 단계의 대상이 있음)
4. 글로벌 뷰(라인 28-30): 마스터 스레드와 전체 통신을 실행하여 각 프로세서에 다음 프론티어에 배치해야 할 로컬 정점을 알려준다.
5. 프로세서 보기(라인 31): 스레드 장벽을 실행하고 통신이 완료될 때까지 기다리십시오(마스터 스레드의 경우).
6. 프로세서 보기(라인 33): 다음 테두리부터 각 스레드에 정점을 할당하십시오.
7. 스레드 뷰(라인 34-36): 정점을 방문하지 않은 경우, 해당 정점의 거리 값을 업데이트하고 다음 프론티어 NS를 위해 스레드 스택에 넣으십시오.
8. 프로세서 보기(라인 37): 스레드 장벽을 실행하고(동일한 프로세서의 모든 스레드) 작업이 완료될 때까지 기다리십시오.
9. 프로세서 보기(라인 39): 모든 스레드에서 다음 프론티어를 위한 집계 스레드 스택
10. 프로세서 보기(라인 40): 스레드 장벽을 실행하고 모든 스레드가 스택에 있는 모든 정점을 보낼 때까지 기다리십시오.

1 정의 1_D_distributed_memory_BFS_with_threads(graph(V,E), source s): 2        // normal initialization 3        for all v in V do 4            d[v] = -1; 5        level = 1; FS = {}; NS = {}; 6        // find the index of the owner processor of source vertex s 7        pu_s = find_owner(s); 8        if pu_s = index_pu then 9            push(s,FS); 10           d[s] = 0; 110<>에 FS!){}과 owne을 찾18//traverse vertexes니 스레드에 나는 16// BFS 가로지르는 17일 시작하//메시지를 초기화 12^j<>p 13sendBuffer_j나{}을 끓여 공유 메시지 버퍼를 평균 탄착 중심점 통신 15thrdBuffer_i_j고 14recvBuffer_j){}을 끓여){}//thread-local다.개발을 제일의 것이다F이웃 FS의 각 u에 병렬로 너의 각 이웃들의 v을 위해 21개의 pu_v니 20나 find_owner(v)22push(vthrdBuffer_i_(pu_v))23스레드로부터의 장벽 24을 끓여0<>25sendBuffer을 형성할 스레드 스택을 결합한^;p 26thrd 합병하니 19j<>vertexes.버퍼_i_j 병렬 27 // 전체 통신 28 마스터 스레드가 있는 전체 집단 단계: 29 1. sendBuffer 30 2. 새로 찾은 정점을 수신하여 recvBuffer 31 Thread Barrier 32 // 업데이트 레벨로 집계하여 각 정점에 대해 새로 방문한 정점 33을 대상으로 한다.u recvBuffer in recvBuffer에서 d[u] = -1이면 35 d[u] = 레벨 36 푸시(u, NS_i) 37 스레드 장벽 38 // Aggregate NS를 형성하고 새로운 FS 39 = Union(NS_i) 40 스레드 장벽 41 레벨 = 레벨 + 1f를 형성하십시오.

2-D 파티셔닝

BFS 알고리즘은 항상 인접 행렬을 그래프의 표현으로 사용하기 때문이다.매트릭스의 자연적인 2D 분해도 고려할 수 있는 옵션이 될 수 있다.2D 파티셔닝에서 각 프로세서는 2D 인덱스(i,j)를 가진다.가장자리와 꼭지점은 인접성 하위 매트릭스가 저장되는 2D 블록 분해가 있는 모든 프로세서에 할당된다.

총 P=R·C 프로세서가 있는 경우 인접 매트릭스는 아래와 같이 구분된다.

이 분할 후 C 열과 R·C 블록 행이 있다.각 프로세서의 경우 C 블록, 즉 프로세서(i,j)가 A 블록을_i,j⁽¹⁾ A 블록에_i,j^(C) 저장한다.기존의 1D 파티셔닝은 R=1 또는 C=1을 사용한 2D 파티셔닝과 동일하다.

일반적으로 2D 파티셔닝을 기반으로 한 병렬 에지 처리는 '확장' 단계와 '접기' 단계인 2가지 통신 단계로 구성할 수 있다.^[6]

"확장" 단계에서 주어진 정점에 대한 에지 목록이 인접 행렬의 열인 경우, 프론티어의 각 정점 v에 대해 v의 소유자는 자신의 프로세서 열에 있는 다른 프로세서에 v가 방문되었음을 알릴 책임이 있다.각 프로세서는 정점의 부분 에지 목록만 저장하기 때문이다.이 통신 후에 각 프로세서는 정점에 따라 의 열을 가로지르고 그들의 이웃을 찾아 다음 개척지를 형성할 수 있다.^[5]

"접기" 단계에서는, 그 결과 다음 개척지의 꼭지점을 그들의 주인 프로세서로 보내어 현지에서 새로운 개척지를 형성한다.2D 파티셔닝에서 이 프로세서는 동일한 프로세서 행에 있다.^[5]

이 2D 파티셔닝 알고리즘에서 BFS 트래버설의 주요 단계는 (각 프로세서에 대해):

1. 확장 단계(라인 13-15): 로컬 정점을 기준으로 프로세서 열의 프로세서에만 메시지를 보내 정점이 프런티어에 있음을 알리고, 프로세서에서 메시지를 수신하십시오.
2. (17-18호선): 수신되는 모든 메시지를 병합하여 순 프론티어 N을 형성한다. 수신된 메시지의 모든 정점을 다음 프론티어에 배치해서는 안 되며, 그 중 일부는 이미 방문했을 수 있다.다음 프론티어는 거리 값이 -1인 꼭지점만 포함한다.
3. 접기 단계(20-23): 다음 프론티어의 로컬 꼭지점에 기초하여 프로세서 행으로 이러한 꼭지점의 소유자 프로세서에 메시지를 전송하십시오.
4. (25-28): 모든 수신 메시지를 병합하고 다음 변경에서 꼭지점 거리 값을 업데이트하십시오.

아래의 의사 코드는 2D BFS 알고리즘에 대한 자세한 내용을 설명하며, 이 알고리즘은 논문에서 제공된다.^[5]

1 정의 2_D_distributed_memory_BFS( graph(V,E), source s): 2        // normal initialization 3        for all v in V do 4            d[v] = -1; 5        d[s] = 0;  6        // begin BFS traversal 7        for l = 0 to infinite do: 8            F = {the set of local vertexes with level l} 9            // all vertexes traversed 10           if F = {} for all processors then: 11이 프로세서 열의 모든 프로세서 q에 대해 선택된 프로세서 13에 메시지를 전송하여 루프 12 /// 정점을 통과하는 동안 종료: 14 프로세서에 F 보내기 Q 16 //에서 수신 F 15qr 프런티어 트래버설 17r F = 유니언{모든 q 18 N에 대해qr F} = 이 프로세서의 에지 목록을 사용하여r F의 정점 근처// 이 프로세서 행의 모든 프로세서 q에 대해 소유자 프로세서 20에 메시지를 전송하여 인접 정점을 브로드캐스트: 21q N = {vertexes in N 소유 프로세서 q} 22 프로세서 q에 N 보내기qq 24 //에서 Nqr 수신r 25 N = Union{Nqr} = 모든 q 26 // 레이어 거리 업데이트 27에r 대해 다음 레이어 통과에 사용되는 다음 프론티어 형식(N) 및 d(v) = -1 do: 28 레벨 = l + 1

2D 파티셔닝에서는 "확장" 또는 "접기" 단계에서는 각각 열 또는 열 프로세서만 통신에 참여한다.^[5]이는 1D 파티셔닝에서 모든 프로세서가 전체 통신 작업에 관여하기 때문에 1D 파티셔닝보다 2D 파티셔닝의 장점이다.게다가 2D 파티셔닝은 로드 밸런싱 개선을 위해 더욱 유연하므로 확장성과 스토리지 효율적인 접근 방식이 훨씬 용이하다.

구현 최적화 전략

병렬 BFS의 기본 개념과는 별도로, 병렬 BFS 알고리즘의 속도를 높이고 효율성을 향상시키기 위해 일부 최적화 전략을 사용할 수 있다.방향 최적화, 로드 밸런싱 메커니즘, 개선된 데이터 구조 등과 같은 병렬 BFS에 대한 최적화는 이미 몇 가지 있다.

방향 최적화

원래의 하향식 BFS에서, 각 꼭지점은 프론티어의 모든 정점의 이웃을 검사해야 한다.그래프의 지름이 낮을 때, 이것은 때때로 효과적이지 않다.^[7] 그러나 작은 세계 그래프와 같이 내부의 정점들은 평균보다 훨씬 높은 도들을 가지고 있다.^[8]앞에서 언급한 바와 같이, 평행 BFS의 한 양성 인종은 국경에서 둘 이상의 정점이 공통적인 인접 정점을 가지고 있다면, 인접 정점의 거리를 여러 번 점검하는 것이다.거리 업데이트는 동기화의 도움을 받아 여전히 정확하지만, 자원은 낭비된다.사실, 다음 개척지의 정점을 찾기 위해서, 각각의 방문하지 않은 정점은 단지 그 이웃 정점이 프론티어에 있는지 확인하기만 하면 된다.이것은 또한 방향 최적화를 위한 핵심 아이디어다.더 좋은 것은, 각각의 꼭지점들은 만약 상당한 수의 이웃들이 국경 지역에 있다면, 들어오는 가장자리를 확인함으로써 빠르게 부모를 찾을 수 있다는 것이다.

이 논문에서 저자들은 각 꼭지점들이 그들의 부모들 중 어느 누구라도 최전방에 있는지 확인만 하면 되는 상향식 BFS를 소개한다.^[8]이것은 국경선이 비트맵으로 대표되는 경우에 효율적이라고 판단될 수 있다.하향식 BFS와 비교했을 때 상향식 BFS는 경합 방지를 위해 상위 BFS를 자체 검사하여 불합격 확인을 줄인다.

그러나 상향식 BFS는 하나의 꼭지점의 직렬화 작업이 필요하며, 정점의 많은 부분이 변경부에 있을 때만 더 잘 작동한다.결과적으로 방향 최적화된 BFS는 하향식 BFS와 상향식 BFS를 결합해야 한다.보다 정확히 말하면, BFS는 하향 방향으로 시작하고, 정점 수가 지정된 임계값을 초과할 때 상향 BFS로 전환해야 하며, 그 반대의 경우도 마찬가지다.^[8]

부하균형

로드 밸런싱은 병렬 BFS뿐만 아니라 모든 병렬 알고리즘에서도 매우 중요하다. 균형 잡힌 작업은 병렬화의 이점을 개선할 수 있기 때문이다.실제로 거의 모든 병렬 BFS 알고리즘 설계자는 알고리즘의 작업 분할을 관찰하고 분석해야 하며 이를 위한 부하 분산 메커니즘을 제공해야 한다.

무작위화는 부하 분산을 달성하기 위한 유용하고 간단한 방법 중 하나이다.예를 들어,^[6] 종이에서는 그래프를 분할하기 전에 모든 정점 식별자를 임의로 섞어서 통과시킨다.

데이터 구조

CSR(압축된 스파스 행), 가방 구조, 비트맵 등 평행 BFS가 얻을 수 있는 특수한 데이터 구조가 있다.

CSR에서, 정점의 모든 보조성은 I의 인접성 옆에 정점 i+1이 인접하여 연속적인 메모리 덩어리에 정렬되고 압축적으로 저장된다.왼쪽의 예에서는 C와 R이라는 두 개의 배열이 있다.배열 C는 모든 노드의 인접 목록을 저장한다.배열 R은 색인을 C에 저장했고, 항목 R[i]은 배열 C에 있는 정점 i의 인접 목록의 시작 색인을 가리킨다.CSR은 정점 인접성에 접근하는 데 일정한 시간만 소요되기 때문에 매우 빠르다.그러나 그것은 1D 파티셔닝을 위한 공간 효율적일 뿐이다.^[6]CSR에 대한 자세한 내용은 에서 확인할 수 있다.^[9]2D 파티셔닝의 경우 하이퍼 스파스 매트릭스용 DCSC(Doubly Compressed Sparse Columns)가 더 적합하다.^[10]

논문에서 저자들은 가방 구조라고 불리는 새로운 데이터 구조를 개발한다.^[4]가방 구조는 페넌트 데이터 구조로 구성된다.페넌트는 2노드x의^k 나무로, 여기서 k는 음이 아닌 정수다.이 나무의 각 루트 x는 자식들에게 x.left와 x.right 두 개의 포인터를 가지고 있다.나무의 뿌리는 남은 원소의 완전한 이진수인 왼쪽 아이만 가지고 있다.^[4]

가방 구조는 백본 어레이 S가 있는 페넌트의 모음입니다.S의 각 항목 S[i]는 null 포인터 또는 s 크기의ⁱ 페넌트에 대한 포인터다.봉지에 삽입하는 작업은 O(1) 상각시간이 소요되며, 두 봉지의 결합은 θ(lgn)시간이 소요된다.백 스플릿은 또한 θ(lgn) 시간이 걸린다.이 가방 구조로, 병렬 BFS는 하나의 데이터 구조로 층의 정점을 병렬로 쓰고 나중에 효율적으로 병렬로 이동시킬 수 있다.^[4]

더욱이 비트맵은 상향식 BFS에 관계없이, 또는 하향식^[9] BFS에 정점이 방문되었는지 여부를 확인하기 위해 이미 어떤 정점을 방문했는지 외우는 데에도 매우 유용한 데이터 구조다.^[11]

벤치마크

Graph500은 데이터 집약적인 슈퍼컴퓨팅 문제의 첫 번째 벤치마크다.^[1]이 벤치마크는 처음에 두 개의 끝점이 있는 에지 튜플을 생성한다.그런 다음 커널 1은 리디렉션되지 않은 그래프를 구성하며, 이 그래프는 커널 2만 이후에 실행될 경우 에지의 무게가 할당되지 않는다.사용자는 생성된 그래프의 커널 2에서 BFS를 실행하거나 커널 3에서 단일 소스-짧은 경로로 실행하도록 선택할 수 있다.이러한 커널의 결과는 검증되고 실행 시간은 측정될 것이다.

또한 Graph500은 커널 2와 3에 대한 두 가지 참조 구현을 제공한다.참조된 BFS에서 정점 탐사는 단순히 대상 프로세서에 메시지를 보내 방문 이웃을 알려주고 있다.추가적인 부하 분산 방법은 없다.동기화를 위해 MPI3 위에 SPMD 통신 라이브러리를 구축한 AML(Active Messages Library) 장벽은 Graph500과 같은 미세한 곡물 애플리케이션에 사용하려고 함) 장벽이 각 계층 후 일관된 통과를 보장한다.참조된 BFS는 결과의 정확성 확인에만 사용된다.따라서 사용자는 하드웨어를 기반으로 자체 BFS 알고리즘을 구현해야 한다.출력 BFS 트리가 올바른 한 BFS 선택은 제한되지 않는다.

결과의 정확성은 참조된 BFS의 결과와의 비교에 기초한다.커널 2 및/또는 커널 3을 실행하기 위해 64개의 검색 키만 샘플링되기 때문에 검색 키가 샘플에 없다는 이유만으로 이 결과가 참조된 결과와 다를 때 그 결과도 올바른 것으로 간주된다.또한 이 64개의 검색 키는 커널을 순차적으로 실행하여 평균과 분산을 계산하고, 단일 검색의 성능을 측정한다.

TOP500과 달리 Graph500의 성능 메트릭은 초당 통과된 에지(TEPS)이다.

참고 항목

• 병렬 알고리즘
• 분산 알고리즘

참조