Computational nanotechnology Выпуск №4 — 2015

Сравнение технологий параллельного программирования MPI и Charm++ на примере задачи построения минимального остовного дерева в графе
(Стр. 18-25)

Мазеев Артем Валерьевич Семенов Александр Сегреевич Фролов Александр Сегреевич

Мазеев Артем Валерьевич инженер-программист
АО «НИЦЭВТ» Семенов Александр Сегреевич канд. техн. наук, начальник сектора
АО «НИЦЭВТ» Фролов Александр Сегреевич начальник отдела
АО «НИЦЭВТ»

Оплатить 390 руб. (Картой) Оплатить 390 руб. (Через QR-код)

Нажимая на кнопку купить вы соглашаетесь с условиями договора оферты

Аннотация:

В работе представлено исследование, как алгоритм 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.

Ключевые слова:

графы, суперкомпьютеры.