Dataintensiva, grafbaserade beräkningar är genomgripande i flera vetenskapliga tillämpningar och är kända för att vara ganska utmanande att implementera på distribuerade minnessystem. I detta arbete utforskar vi designutrymmet för parallella algoritmer för Breadth-First Search (BFS), en viktig subrutin i flera grafalgoritmer. Vi presenterar två högjusterade parallella metoder för BFS på stora parallella system: en nivåsynkron strategi som bygger på en enkel vertex-baserad partitionering av grafen, och en tvådimensionell gles matris partitionering-baserad metod som minskar parallell kommunikation overhead. För båda tillvägagångssätten presenterar vi även hybridversioner med intranode multithreading. Vår nya hybrid tvådimensionella algoritm minskar kommunikationstiderna med upp till en faktor på 3,5, i förhållande till en gemensam vertexbaserad metod. Vår experimentella studie identifierar exekveringssystem där dessa metoder kommer att vara konkurrenskraftiga, och vi visar extremt hög prestanda på ledande distribuerade parallella system. Till exempel, för en 40 000-kärnig parallell körning på Hopper, ett AMD Magny-Cours-baserat system, uppnår vi en BFS prestanda på 17,8 miljarder kantbesök per sekund på en oriktad graf på 4,3 miljarder hörn och 68,7 miljarder kanter med skev gradfördelning.
Buluç och Madduri REF implementerade den första SpMSpV-algoritmen för att lösa BFS på distribuerade system.
Parallel breadth-first search on distributed memory systems
{'venue': 'Proceedings of The International Conference for High Performance Computing, Networking, Storage, and Analysis (SC 2011)', 'journal': None, 'mag_field_of_study': ['Computer Science']}