인덱스 테이블에서의 순서 보존 선택을위한 병렬 알고리즘

Question

인덱스 테이블에서의 순서 보존 선택은 직렬 코드에서는 쉽지 않지만 멀티 스레딩에서는 덜 효율적입니다. 특히 효율성을 유지하려는 경우 (전체 점 멀티 스레딩)을 피할 수 있습니다. 시리얼 코드 나는이 멀티 스레드 (TBB 또는 OpenMP를를 사용하는 말), 특히 data.size() < key.size() 경우를 할 수있는 방법

template<typename T> 
std::vector<T> select_in_order(
    std::vector<std::size_t> const&keys, // permutation of 0 ... key.size()-1 
    std::vector<T> const&data)   // anything copyable 
{ // select data[keys[i]] allowing keys.size() >= data.size() 
    std::vector<T> result; 
    for(auto key:keys) 
    if(key<data.size()) 
     result.push_back(data[key]); 
    return result; 
} 

생각해?

Answer 1

찾고있는 병렬 연산은 Stream Compaction입니다. 알고리즘은 비 단순 비록

은 또, 평행 효율적으로 구현 될 수있다. 최선의 방법은 이미 구현 한 라이브러리 (예 : Thrust)를 사용하는 것입니다. 그러나 실제로 구현하고자한다면, 알고리즘에 대한 설명은 GPU Programming Chapter 39.3.1 또는 Udacity's Intro to Parallel Programming course, Lesson 4.5에서 찾을 수 있습니다.

본질적으로, 그것은 다음 Scatter을하고, 술어의 배열을 통해 Scan을 고려, 별도의 배열에 (당신의 예에서, key<data.size()) 배열 에 대한 boolean predicate, mapping을 정의하는 것을 포함한다.

Map() 및 Scatter()은 병렬로 쉽게 구현할 수 있습니다. Scan()의 구현은 간단하지 않은 부분입니다. 대부분의 병렬 라이브러리에는 Scan() 구현이 있습니다. 그렇지 않은 경우 위의 링크는 여러 가지 병렬 검색 알고리즘을 설명합니다.

---

GPU와 같이 많은 코어가 있다고 가정합니다. CPU에서는 직렬로 처리하는 것이 더 빠를 것입니다. 또는 배열을 큰 청크로 나누려면 연속적으로 청크를 처리하고 (다른 코어를 병렬로 연결)을 병합하고 결과를 다시 병합합니다.어떤 방법이 가장 좋은지는 데이터 에 따라 달라집니다 (대부분의 키가 최종 배열에있을 것으로 예상되는 경우 더 좋은 방법입니다).

Answer 2

스레드간에 키를 분할합니다 (예 : N 개의 스레드로 T1에 키 {0, key.size()/N - 1}을주고, T2는 {key.size()/N, 2 * key.size()/N - 1} 등의 키를 얻습니다. TN은 키 {(N - 1)/N * keys.size(), keys.size() - 1}를 얻습니다. 각 스레드는 결과를 스레드 로컬 컨테이너에 넣고 스레드가 완료되면 컨테이너를 병합합니다. 이렇게하면 스레드간에 동기화를 수행 할 필요가 없습니다.

컨테이너를 병합하는 가장 효율적인 방법은 T1의 목록에 T2의 목록을 추가하는 것이 쉽기 때문에 컨테이너를 연결 목록으로 만드는 것입니다. 그러나 링크 된 목록은 병렬 처리가 잘되지 않으므로 피하는 것이 좋습니다.

또 다른 옵션은 각 스레드가 결과를 thead-local 배열에 저장하고 스레드가 완료되면이 배열을 병합하는 것입니다. 이 병합을 병렬로 수행 할 수 있습니다 (각 스레드 결과의 크기는 T {N} results.size()입니다. 마지막 병합 배열 final_results을 사용하면 T1은 데이터를 final_results[0, T1results.size()-1]에 병합하고 T2는 데이터를 final_results[T1results.size(), T1results.size() + T2results.size()-1]에 병합하고 결과를 병합합니다 final_results[T1results.size() + T2results.size(), T1results.size() + T2results.size + T3results.size()-1] 등).

다른 옵션은 key을 키로 사용하고 data[key]을 값으로 사용하여 TBB에서 공유 concurrent_hash_map을 사용하는 것입니다.