가장 빠른 멀티 스레딩 정렬 방법

Question

현재 CSV 파일을 읽고 CSV 파일의 모든 데이터로 구성된 하나의 큰 정렬 된 CSV 파일을 출력하는 멀티 스레드 분류기를 만듭니다. 지금 당장은 mergesort를 사용하여 각각의 CSV를 개별 스레드로 정렬 한 다음 스레드의 모든 데이터가 함께 연결될 때 마지막으로 정렬 할 계획입니다. 나는 단지 mergesort를 사용하는 것이 "빠름"으로 간주 될지 궁금하다. 스레드가 정렬 된 데이터를 함께 연결하면 데이터는 개별 섹션에서 정렬되지만 전반적으로 정렬되지는 않습니다.

Answer 1

데이터 용량은 얼마입니까? 정렬은 O(n log n)이고 본질적으로 병렬 처리 할 수없는 최종 병합 단계는 물론 O(n)이므로 log n이 완전히 거대하지 않거나 비교 비용이 데이터 이동 비용에 비해 비례하여 높지 않은 한 멀티 스레드 정렬.

여전히 시도하고 싶다면 연결 목록의 최종 병합 정렬을하는 것이 좋습니다. 근본적으로 전체적인 정렬을 다시하는 것과 같은 속도가 될 것입니다. 대신 전체 병합 정렬 대신 단일 병합 작업을 사용하여 각 스레드 쌍의 출력을 병합하려고합니다. 마지막 단계에서 2 개의 목록 만 병합 할 때까지 매번 정렬 된 목록의 수를 반으로 줄이면서이 작업을 반복하십시오. 계층 구조의 두 "형제"스레드가 작업을 끝내면 한 스레드가 종료되고 다른 스레드가 계층에서 위로 이동하고 형제의 출력을 병합하는 스레드간에 계층 관계를 설정하여이 작업을 스레드로 나눌 수 있습니다 .

Answer 2

병합 정렬은 다중 스레드 상향식 병합 정렬을 만들기 전까지는 병합 함수에서 비교적 긴밀한 루프로 인해 메모리 바운드 될 것이라고 생각했습니다. 4 개의 스레드를 사용하면 단일 스레드 병합 정렬보다 약 3 배 빠릅니다. 이 예에서 배열은 4 부분으로 나뉘며 각 부분은 병합 정렬 된 다음 스레드 0은 1/4 분기 배열 0과 1을 병합하고 스레드 2는 1/4 분기 배열 2와 3을 병합합니다. 그러면 스레드 0은 두 개의 절반 배열을 병합합니다. 텍스트 파일 일종의

https://codereview.stackexchange.com/questions/148025/multithreaded-bottom-up-merge-sort

GNU 정렬은, 원래 파일을 가정 (초기 임시 파일을 생성하기 위해 사용 된 첫 번째 패스에 대한 포인터들의 어레이에서 다중 스레드 병합 정렬을 수행하는 것은보다 큰 사용 가능한 메모리). 초기 패스 후에는 병목 현상이 프로세서 속도가 아닌 디스크 I/O 속도이기 때문에 임시 파일을 단일 스레드 방식으로 16 가지 방식으로 병합합니다.