Merge rendezés a divide-and-conquer módszer használata miatt jól párhuzamosítható. Az algoritmus több különböző párhuzamos változatát fejlesztették ki az évek során. Néhány párhuzamos merge rendezési algoritmus erősen kapcsolódik a szekvenciális felülről lefelé merge algoritmushoz, míg mások eltérő általános struktúrával rendelkeznek, és a K-way merge módszert használják.
Merge sort with parallel recursionEdit
a szekvenciális merge rendezési eljárás két fázisban, a divide fázisban és az merge fázisban írható le., Az első sok rekurzív hívásból áll, amelyek ismételten ugyanazt a megosztási folyamatot hajtják végre, amíg a későbbiek triviálisan rendeződnek (egy vagy semmilyen elemet tartalmaznak). Az intuitív megközelítés a rekurzív hívások párhuzamosítása. A következő pszeudokód a párhuzamos rekurzióval való egyesítés rendezését írja le a villával, majd a kulcsszavak összekapcsolásával:
Ez az algoritmus a szekvenciális változat triviális módosítása, amely nem párhuzamosít jól. Ezért a sebesség nem túl lenyűgöző., Van egy Θ ( n ) {\displaystyle \Theta (n)} tartománya , amely csak a Θ ( log n ) {\displaystyle \Theta (\log n)} javulását jelenti a szekvenciális változathoz képest (lásd az algoritmusok bevezetését). Ez elsősorban a szekvenciális egyesítési módszernek köszönhető, mivel ez a párhuzamos kivégzések szűk keresztmetszete.
Merge rendezés párhuzamos mergingEdit
jobb párhuzamosság érhető el egy párhuzamos merge algoritmus. Cormen et al. jelenítsen meg egy bináris változatot, amely két rendezett al-szekvenciát egyesít egy rendezett kimeneti szekvenciába.,
az egyik szekvenciában (minél hosszabb, ha egyenlőtlen hosszúságú) a középső index elemét választja ki. A másik sorrendben elfoglalt helyét úgy határozzuk meg, hogy ez a sorrend rendezve maradjon, ha ezt az elemet ebbe a helyzetbe helyezzük. Így tudjuk, hogy mindkét szekvencia hány más eleme kisebb, és a kiválasztott elem helyzete a kimeneti szekvenciában kiszámítható. Az így létrehozott kisebb-nagyobb elemek részleges szekvenciái esetében az egyesítési algoritmus ismét párhuzamosan kerül végrehajtásra, amíg el nem éri a rekurzió alapesetét.,
a következő pszeudokód a módosított párhuzamos egyesítési rendezési módszert mutatja a párhuzamos egyesítési algoritmus segítségével(cormen et al.).
annak érdekében, hogy elemezze a kiújulás kapcsolatban a legrosszabb esetben span, a rekurzív hívások parallelMergesort kell építeni csak egyszer miatt párhuzamos végrehajtás, megszerzése
részletes információt a komplexitás a párhuzamos egyesítés eljárás, lásd Merge algoritmus.,
ennek a megismétlődésnek a megoldását
t ∞ sort = Θ ( log (n ) 3 ) {\textstyle T_{\infty }^{\text{sort}}}=\Theta \left (\log (n)^{3}\right)}} adja .
párhuzamos multiway merge soredit
önkényesnek tűnik az egyesítési rendezési algoritmusok bináris egyesítési módszerre történő korlátozása, mivel általában p > 2 processzor áll rendelkezésre. Jobb megközelítés lehet egy K-way merge módszer használata, a bináris merge általánosítása, amelyben k {\displaystyle k} rendezett szekvenciák összeolvadnak., Ez az egyesítési változat jól alkalmazható egy rendezési algoritmus leírására egy babakocsin.
Basic IdeaEdit
a párhuzamos multiway egyesíti a folyamatot négy processzoron t 0 {\displaystyle t_{0}} t 3 {\displaystyle t_{3}}}}.
Multisequence selectionEdit
PseudocodeEdit
Az alábbiakban a párhuzamos multiway merge rendezési algoritmus teljes pszeudokódját adjuk meg., Feltételezzük, hogy a multisequence kiválasztása előtt és után van egy akadályszinkronizálás, így minden processzor megfelelően tudja meghatározni a felosztó elemeket és a szekvencia partíciót.
AnalysisEdit
gyakorlati adaptáció és alkalmazásszerkesztés
a multiway merge rendezési algoritmus nagyon skálázható a magas párhuzamosítási képességével, amely lehetővé teszi számos processzor használatát. Ez teszi az algoritmust életképes jelöltnek a nagy mennyiségű adat, például a számítógépes klaszterekben feldolgozott adatok rendezésére., Továbbá, mivel az ilyen rendszerek memória általában nem korlátozó erőforrás, a hátránya a tér összetettsége merge fajta elhanyagolható. Az ilyen rendszerekben azonban más tényezők is fontossá válnak, amelyeket nem vesznek figyelembe a babakocsi modellezésekor. Itt a következő szempontokat kell figyelembe venni: Memória hierarchia, amikor az adatok nem illeszkedik a processzorok cache, vagy a kommunikációs felső közötti adatcseréhez processzorok, amiből lehet egy szűk keresztmetszet, ha az adatok már nem lehet elérni a megosztott memóriában.
Sanders et al., bemutattak a dolgozatukban egy többszintű multiway mergesorthoz tartozó ömlesztett szinkron párhuzamos algoritmust, amely a P {\displaystyle p} processzorokat p ‘{\displaystyle p’} méretű r {\displaystyle R} csoportokra osztja . Minden processzor helyben rendeződik először. A single level multiway mergesort-tal ellentétben ezeket a szekvenciákat r {\displaystyle R} részekre osztjuk, majd a megfelelő processzorcsoportokhoz rendeljük őket. Ezeket a lépéseket rekurzív módon ismételjük meg ezekben a csoportokban. Ez csökkenti a kommunikációt, különösen elkerüli a sok apró üzenettel kapcsolatos problémákat., A mögöttes valós hálózat hierarchikus struktúrája használható a processzorcsoportok (pl. állványok, klaszterek,…).
további Variánsokszerkesztés
a Merge rendezés volt az egyik első rendezési algoritmus, ahol optimális gyorsítást értek el, Richard Cole-lal egy okos alcsoportosítási algoritmust használva az O(1) egyesítés biztosításához. Más kifinomult párhuzamos rendezési algoritmusok alacsonyabb állandóval azonos vagy jobb időkereteket érhetnek el., Például 1991-ben David Powers leírt egy párhuzamos quicksort (és egy kapcsolódó radix sort), amely működhet O(log n) időben egy CRCW párhuzamos véletlen hozzáférésű gép (PRAM) n processzorok végző particionálás implicit módon. Powers továbbá azt mutatja, hogy egy pipelined változata Batcher Bitonic egyesülések at O (log n)2) idő egy pillangó válogató hálózat a gyakorlatban valójában gyorsabb, mint az O(log n) rendezi a babakocsi, és ő részletes vitát a rejtett általános összehasonlításban, radix és párhuzamos válogatás.