Zbornik radova Fakulteta tehničkih nauka u Novom Sadu

Elektrotehničko i računarsko inženjerstvo

God. 39 Br. 06 (2024): Zbornik radova Fakulteta tehničkih nauka

PARALELNO PRETRAŽIVANJE GRAFA NA ARHITEKTURAMA SA DISTRIBUIRANOM I DELJENOM MEMORIJOM

  • Stefan Aleksić
DOI:
https://doi.org/10.24867/27BE03Aleksic
Predato
June 3, 2024
Objavljeno
2024-06-03

Apstrakt

Glavni fokus ovog rada jeste pokušaj unapređenja algoritama pretrage grafova, pogotovo za grafove sa velikim brojem čvorova. Ovaj rad pruža infor­macije 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 me­morijom 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.