스레드를 사용하여 병렬 기수 정렬의 개념을 이해하는 데 약간의 어려움이 있습니다.제공된 스레드 수를 사용하는 병렬 기수 정렬
Most Significant Digit 방법을 사용하면 버킷 1 ~ 9를 만들고 MSD를 사용하여 숫자를 버킷으로 나눌 수 있습니다.
버킷 당 스레드가 1 개인 경우 병렬로 정렬 할 수 있습니다.
그러나 주어진 수의 프로세서 (예 : 4)로 처리해야한다면 어떻게 9 개의 버킷을 4 개의 프로세서로 분할 할 수 있습니까?
온라인에서 봤던 다이어그램은 번호를 x 프로세서의 파티션 번호 (x 정렬)로 나누고 각 프로세서가 주어진 파티션의 모든 숫자를 정렬하는 것으로 시작하는 것이 좋습니다. 하지만 x 번호 버킷은 각각 자체적으로 정렬되어 있지만 숫자의 전체 벡터/배열은 정렬되지 않습니다. 그러면 다음에 무엇을 할 것인지 잘 모르겠습니다.
x 파티션을 정렬 한 후 x 파티션을 병합합니다. 이것은 log2 (x)가 2-way merge를 수행하거나 single-pass가 x-way merge를 할 때 수행 될 수 있습니다. x 방향 병합은 일반적으로 힙을 사용하여 x 요소 (요소가 어느 파티션에 속하는지)를 가장 빨리 결정합니다. 초기화 이외에 요소는 한 번에 하나씩 힙에서 제거되고 힙에 추가됩니다. 결국 x 파티션 중 하나의 끝에 도달하고 병합은 x-1 병합이됩니다. 마지막으로 하나의 파티션 만 남기고 출력 배열에 복사됩니다.
어레이가 너무 커서 파티션이 코어의 L1 및 L2 캐시보다 훨씬 크면 모든 코어가 공통 L3 (및 존재하는 경우 L4) 캐시를 공유하므로 충돌로 인해 병렬 기수 정렬에 많은 도움이되지 않습니다 및 메인 메모리를 포함한다. 예를 들어, 각 코어의 L1 캐시는 32KB이고 각 코어의 L2 캐시는 256KB 일 수 있습니다.
대체 방법은 배열을 z 256KB 파티션으로 분할 한 다음 z 파티션에 대해 한 번에 x 기수 정렬을 수행하는 것입니다. 마지막 단계는 z 정렬 된 256KB 파티션을 z 방식으로 병합하는 것입니다.
기본 기수를 사용하는 대신 기본 기수 10을 사용하는 대신 8 비트 필드에 기본 256을 사용할 수 있습니다 (대신 요소를 필드로 분할하여 나눌 수 있습니다).