PARALELNO PRETRAŽIVANJE GRAFA NA ARHITEKTURAMA SA DISTRIBUIRANOM I DELJENOM MEMORIJOM
Ključne reči:
pretraživanje grafa, distribuirani sistemi, paralelni sistemi
Apstrakt
Glavni fokus ovog rada jeste pokušaj unapređenja algoritama pretrage grafova, pogotovo za grafove sa velikim brojem čvorova. Ovaj rad pruža informacije vezane za algoritme paralelne pretrage grafa, na računarskim arhitekturama sa distribuiranom i deljenom memorijom. Svaka od predstavljenih implementacija analizirana je za različite parametre, kako bi se testirale njene performanse. Zaključak samog istraživanja jeste da paralelna pretraga grafa može biti performantna na računarskim arhitekturama sa deljenom memorijom, dok implementacija na arhitekturama sa distribuiranom memorijom jedino ima smisla za grafove koji ne mogu da se smeste u radnoj memoriji jednog procesora.
Reference
[1] D. A. Bader, Massive Graph Analytics, CRC Press, 2022.
[2] A. Yoo, E. Chow, K. Henderson, W. McLendon, U. Catalyurek i B. Hendrickson, A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L, ACM/IEEE Conference on Supercomputing, 2005.
[3] W. T. Tutte, Cambridge mathematical library: Graph theory, Cambridge: Cambridge University Press, 2001.
[4] K. Mehlhorn, Data structures and algorithms 2, Berlin: Springer, 2011.
[5] M. Neerajkumar, An efficient algorithm for shortest path tree in dynamic graph, LAP Lambert Academic Publishing, 2014.
[2] A. Yoo, E. Chow, K. Henderson, W. McLendon, U. Catalyurek i B. Hendrickson, A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L, ACM/IEEE Conference on Supercomputing, 2005.
[3] W. T. Tutte, Cambridge mathematical library: Graph theory, Cambridge: Cambridge University Press, 2001.
[4] K. Mehlhorn, Data structures and algorithms 2, Berlin: Springer, 2011.
[5] M. Neerajkumar, An efficient algorithm for shortest path tree in dynamic graph, LAP Lambert Academic Publishing, 2014.
Objavljeno
2024-06-03
Sekcija
Elektrotehničko i računarsko inženjerstvo
