Сравнение технологий параллельного программирования MPI и Charm++ на примере задачи построения минимального остовного дерева в графе
(Стр. 18-25)
Подробнее об авторах
Мазеев Артем Валерьевич
инженер-программист
АО «НИЦЭВТ» Семенов Александр Сегреевич канд. техн. наук, начальник сектора
АО «НИЦЭВТ» Фролов Александр Сегреевич начальник отдела
АО «НИЦЭВТ»
АО «НИЦЭВТ» Семенов Александр Сегреевич канд. техн. наук, начальник сектора
АО «НИЦЭВТ» Фролов Александр Сегреевич начальник отдела
АО «НИЦЭВТ»
Аннотация:
В работе представлено исследование, как алгоритм GHS поиска минимального остовного дерева в графе может быть реализован при помощи модели передачи сообщений (библиотека MPI), модели с управлением потоком сообщений (язык Charm++), а также при реализации модели vertex-centric на языке Charm++. Оптимизированные реализации алгоритма GHS с использованием MPI и Charm++ демонстрируют приблизительно одинаковую производительность на 32-узловом вычислительном кластере, производительность реализации с подходом vertex-centric - на 1-2 порядка хуже.
Образец цитирования:
Мазеев А.В., Семенов А.С., Фролов А.С., (2015), СРАВНЕНИЕ ТЕХНОЛОГИЙ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ MPI И CHARM++ НА ПРИМЕРЕ ЗАДАЧИ ПОСТРОЕНИЯ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА В ГРАФЕ. Computational nanotechnology, 4 => 18-25.
Список литературы:
Message Passing Interface Homepage. URL: http://www.mpi-forum.org (дата обращения: 16.12.2015).
Kale L. Charm++: A portable concurrent object oriented system based on C++ / L. Kale, S. Krishnan // SIGPLAN Not. - 1993. - 28(10). - P. 91-108.
Фролов А.С. Использование Charm++ для решения графовых задач в масштабах экзафлопсных вычислений / Фролов А.С., А.С. Семенов // Современные информационные технологии и ИТ-образование. - 2015. - Том 2(№11). - С. 608-614.
McCune R. Thinking Like a Vertex: a Survey of Vertex-Centric Frameworks for Large-Scale Distributed Graph Processing / McCune R., Weninger T., Madey G. // ACM Comput. Surv. - 2015. - 48(2).
Wesolowski L. et al. Tram: Optimizing fine-grained communication with topological routing and aggregation of messages // Parallel Processing (ICPP), 2014 43rd International Conference on. - IEEE, 2014. - C. 211-220.
Prim R. C. Shortest connection networks and some generalizations // Bell system technical journal. - 1957. - Т. 36. - №. 6. - С. 1389-1401.
Kruskal J. B. On the shortest spanning subtree of a graph and the traveling salesman problem // Proceedings of the American Mathematical society. - 1956. - Т. 7. - №. 1. - С. 48-50.
Boruvka O. O jistém problému minimálniım (about a certain minimal problem) // Praca Moravske Prirodovedecke Spolecnosti. v3. - 1926. - С. 37-58.
Gallager R. G. A distributed algorithm for minimum-weight spanning trees / Gallager R. G., Humblet P. A., Spira P. M. // ACM Transactions on Programming Languages and systems (TOPLAS). - 1983. - Т. 5. - №. 1. - С. 66-77.
Awerbuch B. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems // Proceedings of the nineteenth annual ACM symposium on Theory of computing. - ACM, 1987. - С. 230-240.
Симонов А.С. и др. Первое поколение высокоскоростной коммуникационной сети «Ангара» // Наукоемкие технологии. - 2014. - Т. 15, №1. - С. 21-28.
Слуцкин А.И. и др. Разработка межузловой коммуникационной сети ЕС8430 «Ангара» для перспективных суперкомпьютеров // Успехи современной радиоэлектроники. - 2012. - №1. - С. 6-10.
Chakrabarti D. R-MAT: A Recursive Model for Graph Mining / Chakrabarti D., Zhan Y., Faloutsos // SDM. - 2004. - Т. 4. - С. 442-446.
Kale L. Charm++: A portable concurrent object oriented system based on C++ / L. Kale, S. Krishnan // SIGPLAN Not. - 1993. - 28(10). - P. 91-108.
Фролов А.С. Использование Charm++ для решения графовых задач в масштабах экзафлопсных вычислений / Фролов А.С., А.С. Семенов // Современные информационные технологии и ИТ-образование. - 2015. - Том 2(№11). - С. 608-614.
McCune R. Thinking Like a Vertex: a Survey of Vertex-Centric Frameworks for Large-Scale Distributed Graph Processing / McCune R., Weninger T., Madey G. // ACM Comput. Surv. - 2015. - 48(2).
Wesolowski L. et al. Tram: Optimizing fine-grained communication with topological routing and aggregation of messages // Parallel Processing (ICPP), 2014 43rd International Conference on. - IEEE, 2014. - C. 211-220.
Prim R. C. Shortest connection networks and some generalizations // Bell system technical journal. - 1957. - Т. 36. - №. 6. - С. 1389-1401.
Kruskal J. B. On the shortest spanning subtree of a graph and the traveling salesman problem // Proceedings of the American Mathematical society. - 1956. - Т. 7. - №. 1. - С. 48-50.
Boruvka O. O jistém problému minimálniım (about a certain minimal problem) // Praca Moravske Prirodovedecke Spolecnosti. v3. - 1926. - С. 37-58.
Gallager R. G. A distributed algorithm for minimum-weight spanning trees / Gallager R. G., Humblet P. A., Spira P. M. // ACM Transactions on Programming Languages and systems (TOPLAS). - 1983. - Т. 5. - №. 1. - С. 66-77.
Awerbuch B. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems // Proceedings of the nineteenth annual ACM symposium on Theory of computing. - ACM, 1987. - С. 230-240.
Симонов А.С. и др. Первое поколение высокоскоростной коммуникационной сети «Ангара» // Наукоемкие технологии. - 2014. - Т. 15, №1. - С. 21-28.
Слуцкин А.И. и др. Разработка межузловой коммуникационной сети ЕС8430 «Ангара» для перспективных суперкомпьютеров // Успехи современной радиоэлектроники. - 2012. - №1. - С. 6-10.
Chakrabarti D. R-MAT: A Recursive Model for Graph Mining / Chakrabarti D., Zhan Y., Faloutsos // SDM. - 2004. - Т. 4. - С. 442-446.
Ключевые слова:
графы, суперкомпьютеры.
Статьи по теме
1. ВЫЧИСЛИТЕЛЬНЫЕ КОМПЛЕКСЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Страницы: 5-8 Выпуск №4871
ЕЖЕГОДНЫЙ НАУЧНО-ТЕХНИЧЕСКИЙ СЕМИНАР GraphHPC
графы
суперкомпьютеры
параллельная обработка
семинар
Подробнее
1. ТЕХНОЛОГИИ ВЫЧИСЛИТЕЛЬНОЙ ОБРАБОТКИ Страницы: 6-17 Выпуск №5869
Обзор инструментальных средств разработки параллельных графовых приложений для суперкомпьютерных комплексов
параллельная обработка графов
программные модели
вычислительные модели
суперкомпьютеры
экзафлопс
Подробнее
ВЫЧИСЛИТЕЛЬНЫЕ КОМПЛЕКСЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Страницы: 35-38 Выпуск №3497
ТЕНДЕНЦИИ РАЗВИТИЯ СУПЕРКОМПЬЮТЕРОВ
суперкомпьютеры
вычислительные нанотехнологии
параллельные вычисления
Подробнее