Я ищу библиотеку параллельных динамических графов в C ++

Привет сообщество scicomp,

Я работал в области графовых алгоритмов, используя такие фреймворки, как NetworkX (Python), JUNG и YFiles (Java). Сейчас я вхожу в область параллельных и высокопроизводительных вычислений. Для нового проекта я ищу библиотеку графов C ++ со следующими функциями:

• имеет интуитивно понятный интерфейс, который позволяет разработку алгоритма
• поддерживает динамические операции: например, произвольные вставки и удаления узлов / ребер
• поддерживает распараллеливание: например, защищает программиста от проблем, возникающих при многопоточности
• имеет низкую нагрузку на память и подходит для высокопроизводительных вычислений

Пожалуйста, предложите несколько библиотек и обсудите эти критерии, а также плюсы и минусы.

Boost Graph Library и LEMON

Как Дэниел упоминает в своем исчерпывающем ответе , наиболее полнофункциональной общей библиотекой C ++ является библиотека графов ускорения . Существует новое расширение распределенной памяти, способное выполнять некоторые базовые алгоритмы, такие как поиск в ширину и в глубину, поиск минимальных связующих деревьев и поиск связанных компонентов, но я не очень знаком с новым проектом. Сама Boost Graph Library пользуется хорошей репутацией и используется во многих проектах по всему миру.

Если вы выполняете базовую работу с графиками HPC, вы можете начать с библиотеки графов Boost, но имейте в виду, что многие компиляторы HPC C ++ испытывают трудности с Boost (несмотря на довольно строгое соблюдение стандартов C ++), и вам может потребоваться использовать более старая версия Boost или компилятор стороннего производителя, такой как GCC, для работы в системах HPC.

Быстрый просмотр репозиториев LEMON показывает, что есть команда суперкомпьютеров IBM BlueGene, но я не вижу каких-либо зависимостей или конфигурации для MPI, так что на данный момент это скорее всего будет библиотека последовательных графов.

Балансировка нагрузки и динамическое (пере) разбиение графа

Если вас интересует балансировка нагрузки и динамическое разбиение графа, у вас есть еще несколько вариантов. Пожалуй, самая известная библиотека - это ParMETIS , которая была обновлена ​​до версии 4 в прошлом году. ParMETIS имеет взвешивание на основе вершин, что важно для мультифизического моделирования.

Европейским конкурентом ParMETIS является PT-Scotch , который имеет лучшую производительность для определенных типов проблем, но, как и ParMETIS, не часто обновляется.

Вы также можете быть заинтересованы в Zoltan , который является частью метапакета Sandia National Laboratories Trilinos для научных вычислений на C ++. Золтан имеет свои собственные иерархические разделители и интерфейсы как в ParMETIS, так и в PT-Scotch.

graph500

Если вы работаете на переднем крае параллельного поиска, оптимизации (кратчайший путь из одного источника) и ориентированных на ребро (максимальный независимый набор), вас также заинтересует свободно доступный тест Graph500 .

Возможно, библиотека Boost Graph - это то, что вы ищете. Он имеет парсер для чтения графиков, указанных в формате DOT GraphViz. Хотя я действительно не знаю о накладных расходах памяти, он предоставляет вариант для распараллеливания .

Другая графическая библиотека - LEMON, но я действительно не знаю ее, и если она имеет поддержку распараллеливания, она не рекламируется. Это сайт производит хорошее впечатление;)

Я также хотел бы упомянуть STINGER , динамическую структуру данных графа, разработанную для параллелизма. По данным сайта, он предназначен для следующих целей:

Переносимость: алгоритмы, написанные для STINGER, могут быть легко переведены / портированы между несколькими языками и средами

Производительность: STINGER должен предоставить общую абстрактную структуру данных, чтобы большое графическое сообщество могло быстро использовать исследовательские разработки друг друга. В философии это похоже на неявное использование в сообществе численных алгоритмов разреженных и плотных матриц.

Производительность: признается, что ни одна структура данных не является оптимальной для каждого алгоритма графа. Задача STINGER - настроить разумную структуру данных, которая может хорошо работать с большинством алгоритмов. Не должно быть существенного снижения производительности при использовании STINGER по сравнению с другой общей структурой данных в широком наборе типичных алгоритмов графов. STINGER должен принимать адресное пространство разделяемой памяти и разрешать как последовательные, так и параллельные алгоритмы. Структура данных должна позволять параллельным алгоритмам использовать параллелизм, где это возможно.

Он не такой общий, как LEMON или Boost Graph Library, и находится на более ранней стадии разработки. Если вы проверите это, мне будут интересны ваши комментарии.