최고의 평균 케이스 성능을 갖는 병렬 정렬 알고리즘은 무엇입니까?

최고의 평균 케이스 성능을 갖는 병렬 정렬 알고리즘은 무엇입니까?

---

일련의 경우 정렬은 O (n log n)를 사용합니다. 만약 우리가 O (n) 프로세서를 가지고 있다면 우리는 선형 속도 향상을 원할 것입니다. O (log n) 병렬 알고리즘이 존재하지만 상수가 매우 높습니다. 또한 O (n) 프로세서 근처에없는 상용 하드웨어에는 적용되지 않습니다. p 프로세서의 경우 합리적인 알고리즘은 O (n / p log n) 시간이 걸립니다.

일련의 경우 빠른 정렬은 평균적으로 런타임 복잡성이 가장 좋습니다. 병렬 빠른 정렬 알고리즘은 구현하기 쉽습니다 ( here 및 here 참조 ). 그러나 첫 번째 단계는 전체 컬렉션을 단일 코어로 분할하는 것이므로 성능이 좋지 않습니다. 많은 병렬 정렬 알고리즘에 대한 정보를 찾았지만 지금까지 명확한 승자를 가리키는 것은 없습니다.

8 ~ 32 개의 코어에서 실행되는 JVM 언어로 1 백만 ~ 1 억 개의 요소 목록을 정렬하려고합니다.

---

다음 기사 (PDF 다운로드)는 다양한 아키텍처의 병렬 정렬 알고리즘에 대한 비교 연구입니다.

다양한 아키텍처의 병렬 정렬 알고리즘

이 기사에 따르면 샘플 정렬 은 많은 병렬 아키텍처 유형에서 가장 좋은 것으로 보입니다.

Mark의 연령 문제를 해결하기 위해 업데이트 :

다음은 더 새로운 것을 소개하는 최신 기사입니다 (2007 년 btw는 여전히 샘플 정렬과 비교됩니다).

샘플 분류 AA-Sort 개선

출혈 가장자리 (2010 년경, 몇 달 전) :

병렬 정렬 패턴
많은 코어 GPU 기반 병렬 정렬
하이브리드 CPU / GPU 병렬 정렬
실험적 연구를 통한 무작위 병렬 정렬 알고리즘 자연 순서를 사용한
확장 성이 뛰어난 병렬
정렬 N- 요소 정렬 : 새로운 적응 정렬 방법

2013 년 업데이트 : 2013 년 1 월 경에 최첨단 기술이 적용되었습니다. (참고 : 일부 링크는 Citeseer의 논문으로 연결되며 무료로 등록해야합니다) :

대학 강의 :
선택 및 정렬을위한 병렬 파티셔닝
병렬 정렬 알고리즘 강의
병렬 정렬 알고리즘 강의 2
병렬 정렬 알고리즘 강의 3

다른 소스 및 논문 :
적응 형 바이 토닉 정렬을 기반으로하는 많은 코어 아키텍처를위한 새로운 정렬 알고리즘
고 확장 병렬 정렬 2
병렬 병합
병렬 독립형 및 클러스터 된 SMP에 대한 순차적 퀵 정렬 및 병렬 퀵 정렬 알고리즘의 공유 메모리, 메시지 전달 및 하이브리드 병합 정렬에 대한 2 개의
병렬 자체 정렬 시스템 병합
성능 구현 비교 구현을 포함한 다양한 병렬 알고리즘 (정렬 등)



GPU와 CPU / GPU 하이브리드 소스 및 논문 :
GPU 아키텍처에 대한 병렬 정렬 알고리즘의 OpenCL을 방법
그래픽 처리 장치 사용하여 데이터 정렬
GPU에서 정렬을 위해 효율적인 알고리즘을
매니 코어 GPU를위한 설계 효율적인 정렬 알고리즘
의 GPU를 들어 정렬 결정적 샘플
빠른에서 현재 위치와 정렬 비트 코닉 정렬 기반의 CUDA
하이브리드 알고리즘을 사용한 고속 병렬 GPU 분류 GPU의
고속 병렬 정렬 알고리즘
CPU 및 GPU의 고속 분류 : 대역폭을 모르는 SIMD 정렬
GPU 샘플 의 경우
GPU-ABiSort : 스트림 아키텍처에서 최적의 병렬 정렬
GPUTeraSort : 높음 대규모 데이터베이스 관리를위한 고성능 그래픽 코 프로세서 정렬
High performance comparison-based sorting algorithm on many-core GPUs
Parallel external sorting for CUDA-enabled GPUs with load balancing and low transfer overhead
Sorting on GPUs for large scale datasets: A thorough comparison

---

I have worked with both a Parallel Quicksort algorithm and a PSRS algorithm that essentially combines quicksort in parallel with merging.

With the Parallel Quicksort algorithm, I have demonstrated near linear speedup with up to 4 cores (dual core with hyper-threading), which is expected given the limitations of the algorithm. A pure Parallel Quicksort relies on a shared stack resource which will result in contention among threads, thus reducing any gain in performance. The advantage of this algorithm is that it sorts 'in-place,' which reduces the amount of memory needed. You may want to consider this when sorting upwards of 100M elements as you stated.

I see you are looking to sort on a system with 8-32 cores. The PSRS algorithm avoids contention at the shared resource, allowing speedup at higher numbers of processes. I have demonstrated the algorithm with up to 4 cores as above, but experimental results of others report near linear speedup with much larger numbers of core, 32 and beyond. The disadvantage of the PSRS algorithm is that it is not in-place and will require considerably more memory.

If you are interested, you may use or peruse my Java code for each of these algorithms. You can find it on github: https://github.com/broadbear/sort. The code is intended as a drop-in replacement of Java Collections.sort(). If you are looking for the ability to perform parallel sorting in a JVM as you state above, the code in my repo may help you out. The API is fully genericized for elements implementing Comparable or implementing your own Comparator.

May I ask what you are looking to sort that many elements for? I'm interested to know of potential applications for my sorting package.

---

Take a look at this paper: A Scalable Parallel Sorting Algorithm Using Exact Splitting. It is concerned with many more than 32 cores. However, it describes in detail an algorithm, which has a running time complexity of O(n/p * log(n) + p * log(n)**2) and is applicable for arbitrary comparators.

---

The paper "Comparison of Parallel Sorting Algorithms on Different Architectures" may be a good place for you to start.

참고URL : https://stackoverflow.com/questions/3969813/which-parallel-sorting-algorithm-has-the-best-average-case-performance