Ich suche eine parallele dynamische Grafikbibliothek in C ++

11

Hallo Scicomp-Community,

Ich habe im Bereich der Graph-Algorithmen mit Frameworks wie NetworkX (Python), JUNG und YFiles (Java) gearbeitet. Ich betrete jetzt den Bereich des parallelen und hochleistungsfähigen Rechnens. Für ein neues Projekt suche ich eine C ++ - Grafikbibliothek mit folgenden Funktionen:

  • verfügt über eine intuitive Benutzeroberfläche, die die Entwicklung von Algorithmen ermöglicht
  • unterstützt dynamische Operationen: zB beliebige Einfügungen und Löschungen von Knoten / Kanten
  • unterstützt die Parallelisierung: z. B. schützt den Programmierer vor Problemen, die beim Multithreading auftreten
  • hat einen geringen Speicheraufwand und ist für Hochleistungsrechnen geeignet

Bitte schlagen Sie einige Bibliotheken vor und diskutieren Sie diese Kriterien sowie Vor- und Nachteile.

algorithms parallel-computing libraries graph-theory clstaudt
quelle

Antworten:

11

Boost Graph Library und LEMON

Wie Daniel in seiner umfassenden Antwort erwähnt , ist die Boost Graph Library die umfassendste allgemeine C ++ - Bibliothek . Es gibt eine neue Erweiterung für verteilten Speicher, die einige grundlegende Algorithmen ausführen kann, z. B. Breitensuche und Tiefensuche, minimale Spannbäume und Suche nach verbundenen Komponenten, aber ich bin mit dem neuen Projekt nicht sehr vertraut. Die Boost Graph Library selbst ist bekannt und wird in vielen Projekten auf der ganzen Welt verwendet.

Wenn Sie grundlegende HPC-Diagrammarbeiten ausführen, möchten Sie möglicherweise mit der Boost-Diagrammbibliothek beginnen. Beachten Sie jedoch, dass viele HPC C ++ - Compiler Probleme mit Boost haben (trotz der recht strengen Einhaltung der C ++ - Standards) und möglicherweise eine verwenden müssen ältere Version von Boost oder ein Compiler eines anderen Anbieters wie GCC, damit es auf HPC-Systemen funktioniert.

Ein kurzer Blick in die LEMON-Repositorys zeigt, dass das IBM BlueGene-Supercomputing-Team beteiligt ist, ich sehe jedoch keine Abhängigkeiten oder Konfigurationen für MPI, sodass es sich derzeit wahrscheinlich nur um eine serielle Diagrammbibliothek handelt.

Lastausgleich und dynamische (Neu-) Partitionierung von Graphen

Wenn Sie an Lastausgleich und dynamischer Diagrammpartitionierung interessiert sind, haben Sie mehrere weitere Optionen. Die vielleicht bekannteste Bibliothek ist ParMETIS , die letztes Jahr auf Version 4 aktualisiert wurde. ParMETIS bietet eine vertexbasierte Gewichtung, die für Multi-Physik-Simulationen wichtig ist.

Der europäische Konkurrent von ParMETIS ist PT-Scotch , das bei bestimmten Arten von Problemen eine bessere Leistung erzielt hat, jedoch ähnlich wie ParMETIS nicht häufig aktualisiert wird.

Sie könnten auch an Zoltan interessiert sein , das Teil des Trilinos-Metapakets der Sandia National Laboratories für wissenschaftliches Rechnen in C ++ ist. Zoltan verfügt über eigene hierarchische Partitionierer und Schnittstellen zu ParMETIS und PT-Scotch.

Graph500

Wenn Sie an der Spitze der gleichzeitigen Suche, Optimierung (kürzester Pfad aus einer Quelle) und kantenorientiert (maximaler unabhängiger Satz) arbeiten, interessieren Sie sich auch für den frei verfügbaren Graph500-Benchmark .

Aron Ahmadia
quelle
1
Frage: Die Parallel Boost Graph Library ist für Parallelität mit verteiltem Speicher gedacht. Ist die normale Boost Graph Library für die Parallelisierung von Shared Memory mit OpenMP geeignet?
Clstaudt
@clstaudt - Dies wird problemspezifisch sein. Sie müssen sich eingehender mit den Details Ihres Algorithmus befassen, um eine bessere Antwort zu erhalten (und es wäre wahrscheinlich eine neue Frage).
Aron Ahmadia
5

Vielleicht ist die Boost Graph Library genau das, wonach Sie suchen. Es verfügt über einen Parser zum Lesen von Diagrammen, die im DOT-Format von GraphViz angegeben sind. Obwohl ich nicht wirklich über Speicher-Overhead Bescheid weiß, bietet es eine Variante für die Parallelisierung .

Eine andere Grafikbibliothek ist LEMON, aber ich weiß es nicht wirklich und wenn es Parallelisierung unterstützt, wird es nicht angekündigt. Die Website macht aber einen guten Eindruck;)

Daniel Eberts
quelle
LEMON sieht auch für mich gut aus, aber ich habe absolut keine Ahnung, ob ich es für OpenMP (Shared Memory Parallel Code) verwenden kann.
Clstaudt
Ich auch nicht, um ehrlich zu sein. Aber vielleicht können Sie es verwenden, um gemeinsam genutzte Datenstrukturen für Ihr Problem zu deklarieren und die Algorithmen in verschiedenen Threads auszuführen. Vielleicht können Sie Ihr Problem in geeignete Teilprobleme unterteilen.
Daniel Eberts
5

Ich möchte auch STINGER erwähnen , eine dynamische Graphendatenstruktur , die für Parallelität ausgelegt ist. Laut der Website ist es für die folgenden Ziele ausgelegt:

Portabilität: Für STINGER geschriebene Algorithmen können problemlos zwischen mehreren Sprachen und Frameworks übersetzt / portiert werden

Produktivität: STINGER sollte eine gemeinsame abstrakte Datenstruktur bereitstellen, damit die große Graph-Community die Forschungsentwicklungen der anderen schnell nutzen kann. Dies ähnelt in der Philosophie der impliziten Verwendung von spärlichen und dichten Matrizen durch numerische Algorithmen.

Leistung: Es ist bekannt, dass keine einzelne Datenstruktur für jeden Diagrammalgorithmus optimal ist. Das Ziel von STINGER ist es, eine sinnvolle Datenstruktur zu konfigurieren, die die meisten Algorithmen gut ausführen kann. Es sollte keine signifikante Leistungsminderung für die Verwendung von STINGER im Vergleich zu einer anderen allgemeinen Datenstruktur über einen breiten Satz typischer Graphalgorithmen geben. STINGER sollte einen gemeinsam genutzten Speicheradressraum annehmen und sowohl sequentielle als auch parallele Algorithmen zulassen. Die Datenstruktur sollte es parallelen Algorithmen ermöglichen, die Parallelität nach Möglichkeit auszunutzen.

Es ist nicht so allgemein wie LEMON oder Boost Graph Library und befindet sich in einem früheren Entwicklungsstadium. Wenn Sie es überprüfen, würde mich Ihre Kommentare interessieren.

clstaudt
quelle
STINGER Kommt aus David Baders Labor an der Georgia Tech. Er ist in der HPC-Community für seine Arbeit am Graph500 bekannt, danke, dass Sie diesen erwähnt haben!
Aron Ahmadia