Szukam równoległej biblioteki dynamicznych grafów w C ++

Witaj społeczności scicomp,

Pracowałem w obszarze algorytmów graficznych z wykorzystaniem frameworków takich jak NetworkX (Python), JUNG i YFiles (Java). Wchodzę teraz w obszar obliczeń równoległych i wysokowydajnych. W przypadku nowego projektu szukam biblioteki grafów C ++ z następującymi funkcjami:

• ma intuicyjny interfejs, który umożliwia tworzenie algorytmów
• obsługuje operacje dynamiczne: np. dowolne wstawianie i usuwanie węzłów / krawędzi
• obsługuje równoległość: np. chroni programistę przed problemami wynikającymi z wielowątkowości
• ma niski narzut pamięci i nadaje się do obliczeń o wysokiej wydajności

Proszę zasugerować niektóre biblioteki i omówić te kryteria, a także zalety i wady.

Zwiększ bibliotekę wykresów i LEMON

Jak wspomina Daniel w swojej wyczerpującej odpowiedzi , najbardziej wszechstronną ogólną biblioteką C ++ jest Biblioteka Grafów Wzmocnienia . Istnieje nowe rozszerzenie pamięci rozproszonej zdolne do wykonywania podstawowych algorytmów, takich jak wyszukiwanie w pierwszej kolejności i w pierwszej kolejności, minimalne drzewa opinające i wyszukiwanie połączonych komponentów, ale nie znam się na nowym projekcie. Sama biblioteka grafów pomocniczych cieszy się renomą i jest wykorzystywana w wielu projektach na całym świecie.

Jeśli wykonujesz podstawową pracę z grafami HPC, możesz zacząć od biblioteki grafów Boost, ale pamiętaj, że wiele kompilatorów HPC C ++ ma trudności z Boost (pomimo dość ścisłego przestrzegania standardów C ++) i może być konieczne użycie starsza wersja Boost lub kompilator inny niż dostawca, taki jak GCC, aby działał na systemach HPC.

Szybkie przeglądanie repozytoriów LEMON pokazuje, że zespół superkomputerowy IBM BlueGene jest zaangażowany, ale nie widzę żadnych zależności ani konfiguracji MPI, więc prawdopodobnie jest to obecnie tylko biblioteka grafów szeregowych.

Równoważenie obciążenia i dynamiczne dzielenie grafów

Jeśli interesuje Cię równoważenie obciążenia i dynamiczne dzielenie grafów, masz kilka innych opcji. Być może najbardziej znaną biblioteką jest ParMETIS , która została zaktualizowana do wersji 4 w zeszłym roku. ParMETIS ma funkcję ważenia opartego na wierzchołkach, co jest ważne w symulacjach wielofizycznych.

Europejskim konkurentem ParMETIS jest PT-Scotch , który miał lepszą wydajność w przypadku niektórych rodzajów problemów, ale podobnie jak ParMETIS, nie jest często aktualizowany.

Być może zainteresuje Cię również Zoltan , który jest częścią meta-pakietu Sandia National Laboratories Trilinos do obliczeń naukowych w C ++. Zoltan posiada własne hierarchiczne partycjonery i interfejsy do ParMETIS i PT-Scotch.

Graph500

Jeśli pracujesz nad najnowocześniejszymi funkcjami wyszukiwania równoległego, optymalizacji (najkrótsza ścieżka z jednego źródła) i zorientowania na krawędzie (maksymalny zestaw niezależny), zainteresuje Cię również swobodnie dostępny test porównawczy Graph500 .

Być może szukasz biblioteki grafów pomocniczych . Ma parser do odczytu wykresów określonych w formacie DOT GraphViz. Chociaż tak naprawdę nie wiem o narzutach pamięci, zapewnia ona wariant równoległości .

Inną biblioteką grafów jest LEMON, ale tak naprawdę nie wiem, a jeśli ma ona obsługę równoległości, nie jest reklamowana. Ta strona robi dobre wrażenie;)

Chciałbym również wspomnieć o STINGER , dynamicznej strukturze danych graficznych zaprojektowanej dla równoległości. Według strony internetowej jest on przeznaczony do następujących celów:

Przenośność: Algorytmy napisane dla STINGERA można łatwo tłumaczyć / przenosić między wieloma językami i strukturami

Produktywność: STINGER powinien zapewniać wspólną abstrakcyjną strukturę danych, tak aby duża społeczność grafów mogła szybko wykorzystywać nawzajem swoje badania. Jest to podobne w filozofii do algorytmów numerycznych, domyślnie wykorzystywanych przez społeczności rzadkich i gęstych macierzy.

Wydajność: uznaje się, że żadna pojedyncza struktura danych nie jest optymalna dla każdego algorytmu grafowego. Celem STINGER jest skonfigurowanie rozsądnej struktury danych, która może dobrze uruchamiać większość algorytmów. Nie powinno być znaczącego zmniejszenia wydajności przy korzystaniu z STINGER w porównaniu z inną ogólną strukturą danych w szerokim zestawie typowych algorytmów graficznych. STINGER powinien przyjąć przestrzeń adresową pamięci współużytkowanej i zezwalać na algorytmy sekwencyjne lub równoległe. Struktura danych powinna umożliwiać algorytmom równoległym wykorzystywanie współbieżności tam, gdzie to możliwe.

Nie jest tak ogólny jak LEMON lub Boost Graph Library i na wcześniejszym etapie rozwoju. Jeśli to sprawdzisz, będę zainteresowany Twoimi komentarzami.