Biton fajta

biton fajta
Biton válogató hálózat nyolc bemenethez
Szerző	Kenneth Edward Batcher
célja	Rendezési algoritmus
legrosszabb idő
Legjobb idő
Átlagos idő

A bitonikus rendezés egy párhuzamos  algoritmus az adatok rendezésére , egy rendezési hálózat létrehozásának módszere . Kenneth Batcher amerikai informatikus fejlesztette ki 1968-ban. Az algoritmus a "bitonszekvencia" fogalmán alapul. A nevet a monoton szekvenciával [1] analógia alapján választottuk ki .

A bitonikus rendezés az egyik legrégebbi párhuzamos rendezési algoritmus [2] . A páros-páratlan egyesítési rendezés mellett ez az egyik első módszer tetszőleges számú bemenethez rendezési hálózat felépítésére [3] .

Az algoritmus leírása

Az algoritmus a bitonikus sorozatok rendezésén alapul. Ilyen sorozatnak nevezzük azt a sorozatot, amely először nem monoton csökken, majd nem növekszik monoton, vagy ciklikus eltolódás következtében ilyen formára redukálódik [3] [4] [2] .

Bármely bitonikus szekvencia, minden egy vagy két elemből álló szekvencia, valamint bármely monoton szekvencia szintén bitonikus. Például a {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} sorozatok bitonikusak, de a {4,6,1,9,2 } are not is. A rendezetlen elemek minden egyes halmaza két elemből álló bitonsorozatok halmazának tekinthető [3] [4] [5] [2] .

A bitonikus egyesítési folyamat a bitonikus sorozatot teljesen rendezett szekvenciává alakítja. A bitonikus rendezési algoritmus bitonikus transzformációk alkalmazásából áll, amíg a halmaz teljesen rendeződik [5] [2] .

Példa

Az ábrán egy 16 elemből álló bitonos rendezési hálózat látható, amely növekvő sorrendben rendezi a halmazt. A nyilak az összehasonlítókat jelölik , amelyek két számot hasonlítanak össze, és szükség esetén felcserélik őket úgy, hogy a nyíl iránya a nagyobb számra mutasson.

A piros téglalapokat zöld és kék téglalapokká egyesítik. A kék téglalapokban a komparátorok nyilai lefelé mutatnak (növekvő sorozatokat hoznak létre), a zöld téglalapoknál felfelé mutatnak (csökkenő sorozatokat hoznak létre). Ezeknek a téglalapoknak ugyanaz a felépítése: a piros téglalapot a teljes sorozatra alkalmazzuk, majd az eredmények mindegyik felére, és így tovább. Ha egy ilyen téglalap bemeneteire bitonikus sorozatot táplálunk, akkor a kimeneten egy teljesen rendezett szekvenciává alakítjuk. A kék és zöld mezők együttes eredménye egy bitonikus sorozat.

A kék és zöld téglalapok minden oszlopa N darab rendezett sorozatot vesz (a legelső lépésben 16 rendezett sorozatot 1 elemmel), és N/2 rendezett sorozattá alakítja őket.

Alternatív ábrázolás

Létezik egy alternatív és elterjedtebb ábrázolása a Biton fajtának, amely eltér Butcher eredeti verziójától. Az adatokat különböző irányba mozgó komparátoroktól való megszabadulás érdekében megváltoztattuk a köztük lévő kapcsolatokat, azon tulajdonság alapján, hogy bármelyik két rendezett sorozatból (azaz monotonból) bitonikus szekvenciát kaphatunk, ha az egyikben a sorrendet az ellenkezőjére változtatjuk [ 4 ] .

Így az ábra összes kék téglalapja ugyanazokat a műveleteket hajtja végre. A barna téglalapok módosított piros blokkok, amelyek be- és kimenetei alul fordított sorrendben vannak csatlakoztatva.

Felfedezési előzmények

Az 1960-as évek közepén Kenneth Batcher a Goodyear Aerospace nél dolgozott , ahol több ezer feldolgozóelemet tartalmazó párhuzamos processzorok tervezésével foglalkozott. Az adatok rendezési problémájának megoldásán dolgozva arra a következtetésre jutott, hogy a szekvenciális rendezési algoritmusok túl lassúak, és szükséges tanulmányozni a párhuzamos rendezési algoritmusok létrehozásának lehetőségét. Áttekintette a jól ismert egyesítést , és megállapította, hogy annak első lépései könnyen párhuzamosíthatók, de a későbbi összevonások szekvenciálisak és időigényesek. Ennek eredményeként felfedezett két egyesítésen alapuló algoritmust, a bitonikus rendezést és a páros-páratlan összevonási rendezést . Batcher ezeket az algoritmusokat az 1968-as Joint Computer Conference "Sorting Networks and their applications" című cikkében mutatta be [3] .

Batcher később maga is elismerte, hogy a név írástudatlan, mivel egy latin előtagot és egy görög gyökeret egyesít. Helyesebb elnevezés a "ditonikus" [3] [5] .

Befolyás és alkalmazás

A bitonikus rendezés az egyik első párhuzamos rendezési algoritmus. Ennek az algoritmusnak a közzététele, valamint a Batcher által is javasolt páros-páratlan összevonási rendezési algoritmussal együtt ösztönözte a párhuzamos algoritmusok tervezésének és elemzésének kidolgozását általában, és különösen a párhuzamos rendezést [2] .

Nagy párhuzamosságuk miatt a bitonszortírozókat széles körben alkalmazzák olyan eszközökben, amelyek masszívan párhuzamos számítást céloznak, mint például a GPU -k [6] és az FPGA -k [7] , de a modern szuperszámítógépekben ritkán használják [1] .

A korai GPU-kban a korlátozott API és a szórási művelet elérhetetlensége miatt a bitonikus rendezés volt a domináns algoritmus. Különösen a GPU-k számára fejlesztették ki a "GNUTeraSort" algoritmust, amely a bitonikus és bitonikus rendezésen , majd a GPU-ABiSorton alapul, adaptív bitonikus rendezést használva. A CUDA hardver- és szoftverarchitektúrájának megjelenésével más párhuzamos rendezési algoritmusok hatékony változatai is megjelentek, és jelenleg a bitenkénti rendezés dominál a GPU-n [1] .

Jegyzetek

1. ↑ 1 2 3 Kalé, Solomonik, 2011 .
2. ↑ 1 2 3 4 5 Akl, 2011 .
3. ↑ 1 2 3 4 5 Baddar, Batcher, 2012 .
4. ↑ 1 2 3 Cormen et al., 2001 .
5. ↑ 1 2 3 Knuth, 1998 .
6. ↑ Owens JD et al., 2008 .
7. ↑ Mueller, Teubner, Alonso, 2009 .

Irodalom

• Laxmikant V. Kale, Edgar Solomonik. Sorting  (angol)  // Encyclopedia of Parallel Computing : encyclopedia. - Springer , 2011. - P. 1855-1861 . - ISBN 978-0-387-09765-7 .
• Selim G. Akl. Bitonic Sort  (angol)  // Encyclopedia of Parallel Computing : encyclopedia. - Springer , 2011. - P. 139-146 . - ISBN 978-0-387-09765-7 .
• Sherenaz W. Al-Haj Baddar, Kenneth E. Batcher. Bitonikus összevonás // Sorting Networks tervezése: Új paradigma . - Springer , 2012. - S.  2-5 . — 148 p. — ISBN 978-1461418504 .
• Donald E. Knuth . Bitonikus rendezés // A számítógépes programozás művészete . - 2. - Addison-Wesley , 1998. - T. 3. - S. 230-232. — 780 s. — ISBN 9780201896855 .
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Bitonikus rendezés // Bevezetés az algoritmusokba . - 2. - MIT Press , 2001. - S. 608-611. — 984 p. — ISBN 9780070131514 .
• Mueller R., Teubner J., Alonso G. Adatfeldolgozás az FPGA-kon  //  Proceedings of the VLDB Endowment. - 2009. - augusztus. — P. 910-921 . - doi : 10.14778/1687627.1687730 .
• Owens JD et al. GPU számítástechnika  //  Proceedings of the IEEE. - 2008. - május ( 96. évf. , 5. sz.). - 879-899 . o . - doi : 10.1109/JPROC.2008.917757 .