Sortowanie zajmuje O (n log n) w przypadku szeregowym. Jeśli mamy O (n) procesorów, liczylibyśmy na liniowe przyspieszenie. Istnieją algorytmy równoległe O (log n), ale mają one bardzo wysoką stałą. Nie mają również zastosowania na standardowym sprzęcie, który nie ma w pobliżu procesorów O (n). W przypadku procesorów p rozsądne algorytmy powinny zająć O (n / p log n) czasu.
W przypadku seryjnego sortowanie szybkie ma średnio największą złożoność w czasie wykonywania. Równoległy algorytm szybkiego sortowania jest łatwy do zaimplementowania (patrz tutaj i tutaj ). Jednak nie działa dobrze, ponieważ pierwszym krokiem jest podzielenie całej kolekcji na jeden rdzeń. Znalazłem informacje o wielu algorytmach sortowania równoległego, ale jak dotąd nie widziałem niczego, co wskazywałoby na wyraźnego zwycięzcę.
Chcę posortować listy od 1 miliona do 100 milionów elementów w języku JVM działającym na 8 do 32 rdzeniach.
źródło
Odpowiedzi:
Poniższy artykuł (plik PDF do pobrania) jest studium porównawczym algorytmów sortowania równoległego na różnych architekturach:
Algorytmy sortowania równoległego na różnych architekturach
Zgodnie z artykułem sortowanie próbek wydaje się być najlepsze w przypadku wielu typów architektury równoległej.
Aktualizacja w celu rozwiązania problemu wieku Marka:
Oto nowsze artykuły wprowadzające coś bardziej nowatorskiego (z 2007 roku, które przy okazji wciąż porównuje się z sortowaniem przykładowym):
Ulepszenia sortowania próbek według
AA
Krwawienie (około 2010 r., Niektóre mają zaledwie kilka miesięcy):
Wzorzec sortowania
równoległego Sortowanie równoległe oparte na wielu rdzeniach GPU
Hybrydowe sortowanie równoległe CPU / GPU
Randomized Parallel Sortowanie Algorytm z badaniem eksperymentalnym
Wysoce skalowalne sortowanie równoległe
Sortowanie N-elementów przy użyciu naturalnego porządku: nowe podejście do sortowania adaptacyjnego
Aktualizacja na rok 2013: Oto ostra sytuacja, około stycznia 2013 r. (Uwaga: niektóre linki prowadzą do artykułów w Citeseer i wymagają bezpłatnej rejestracji):
Wykłady uniwersyteckie:
Partycjonowanie równoległe do selekcji i sortowania
Algorytmy sortowania równoległego Wykład Algorytmy sortowania
równoległego Wykład 2
Algorytmy sortowania równoległego Wykład 3
Inne źródła i publikacje:
Nowatorski algorytm sortowania dla architektur wielordzeniowych oparty na adaptacyjnym sortowaniu bitonicznym
Wysoce skalowalne sortowanie
równoległe 2 Równoległe łączenie
równoległe Łączenie 2
równoległych systemów samosortowania dla obiektów
Porównanie wydajności sekwencyjnych algorytmów szybkiego sortowania i równoległych algorytmów szybkiego sortowania
Pamięć współdzielona, przekazywanie wiadomości i hybrydowe sortowanie scalające dla samodzielnych i klastrowych SMP
Różne algorytmy równoległe (sortowanie i inne), w tym implementacje
Hybrydowe źródła i dokumenty GPU i CPU / GPU:
Metoda OpenCL równoległego sortowania algorytmów dla architektury GPU
Sortowanie danych z wykorzystaniem jednostek przetwarzania grafiki
Wydajne algorytmy sortowania na GPU
Projektowanie wydajnych algorytmów sortowania dla wielu procesorów graficznych
Deterministyczne sortowanie próbek dla GPU
Szybkie sortowanie na miejscu dzięki CUDA w oparciu o sortowanie bitoniczne
Szybkie równoległe sortowanie GPU przy użyciu algorytmu hybrydowego
Szybkie równoległe sortowanie algorytmów na procesorach graficznych
Szybkie sortowanie na procesorach i GPU: przypadek braku pasma Sortowanie SIMD Sortowanie
próbek
GPU GPU-ABiSort: optymalne sortowanie równoległe w architekturze strumieniowej
GPUTeraSort: wysoki wydajne sortowanie koprocesorów graficznych do zarządzania dużymi bazami danych
Wysokowydajny algorytm sortowania oparty na porównaniu na wielordzeniowych procesorach graficznych
Równoległe zewnętrzne sortowanie dla procesorów graficznych z obsługą CUDA z równoważeniem obciążenia i niskim narzutem transferu
Sortowanie na procesorach GPU dla dużych zbiorów danych: dokładne porównanie
źródło
Pracowałem zarówno z algorytmem Parallel Quicksort, jak i algorytmem PSRS, który zasadniczo łączy quicksort równolegle z łączeniem.
Dzięki algorytmowi Parallel Quicksort zademonstrowałem prawie liniowe przyspieszenie do 4 rdzeni (dwurdzeniowy z hiperwątkowością), co jest oczekiwane, biorąc pod uwagę ograniczenia algorytmu. Czyste równoległe szybkie sortowanie opiera się na współdzielonym zasobu stosu, co spowoduje rywalizację między wątkami, zmniejszając w ten sposób wzrost wydajności. Zaletą tego algorytmu jest to, że sortuje „na miejscu”, co zmniejsza ilość potrzebnej pamięci. Możesz wziąć to pod uwagę podczas sortowania ponad 100 milionów elementów, jak powiedziałeś.
Widzę, że chcesz sortować w systemie z 8-32 rdzeniami. Algorytm PSRS unika rywalizacji o współdzielony zasób, umożliwiając przyspieszenie przy większej liczbie procesów. Pokazałem algorytm z maksymalnie 4 rdzeniami, jak powyżej, ale wyniki eksperymentów innych wskazują na prawie liniowe przyspieszenie przy znacznie większej liczbie rdzeni, 32 i więcej. Wadą algorytmu PSRS jest to, że nie jest on na miejscu i będzie wymagał znacznie więcej pamięci.
Jeśli jesteś zainteresowany, możesz użyć lub przejrzeć mój kod Java dla każdego z tych algorytmów. Możesz go znaleźć na github: https://github.com/broadbear/sort . Kod jest przeznaczony do zastępowania Java Collections.sort (). Jeśli szukasz możliwości równoległego sortowania w JVM, tak jak powyżej, kod w moim repozytorium może ci pomóc. Interfejs API jest w pełni uogólniony dla elementów implementujących Porównywalny lub implementujących własny komparator.
Czy mogę zapytać, po co chcesz posortować tak wiele elementów? Interesuje mnie potencjalne zastosowanie mojego pakietu do sortowania.
źródło
Spójrz na ten artykuł: Skalowalny algorytm sortowania równoległego wykorzystujący dokładny podział . Dotyczy wielu ponad 32 rdzeni. Jednak szczegółowo opisuje algorytm, który ma złożoność czasu wykonywania O (n / p * log (n) + p * log (n) ** 2) i ma zastosowanie do dowolnych komparatorów.
źródło
Artykuł „Porównanie algorytmów sortowania równoległego w różnych architekturach” może być dobrym miejscem do rozpoczęcia.
źródło