Статья

Название статьи АНАЛИЗ МАСШТАБИРУЕМОСТИ АЛГОРИТМОВ КОЛЛЕКТИВНЫХ ОБМЕНОВ НА РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
Автор М.Г. Курносов
Рубрика РАЗДЕЛ III. РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛЕНИЯ И СИСТЕМЫ
Месяц, год 11, 2016
Индекс УДК 004.272
DOI 10.18522/2311-3103-2016-11-7587
Аннотация При разработке параллельных программ для вычислительных систем (ВС) с массовым параллелизмом значительное место по частоте использования и приходящемуся на них суммарному времени выполнения занимают коллективные операции обменов информацией (групповые, глобальные, collective communications). В них участвуют все ветви параллельной программы: трансляционная передача («один-всем», one-to-all broadcast/scatter), коллекторный прием («все-одному», all-to-one gather/reduce), трансляционно-циклический обмен («каждый-всем», all-to-all gather/reduce). Для реализации каждой коллективной операции, имеется множество алгоритмов, из которого необходимо выбрать оптимальный – обеспечивающий минимум времени выполнения операции. Для такого сравнительного анализа в моделях параллельных вычислений (BSP – bulk synchronous parallel, Дж. Хокни, LogP, LogGP, PLogP) строят аналитические оценки времени выполнения алгоритмов, как функции от параметров системы и коллективной операции: числа процессоров, показателей производительности каналов связи, размеров передаваемых сообщений. В данной работе для коллективной операции корневой редукции (all-to-one reduce) в модели параллельных вычислений LogP построены аналитические выражения (оценки) времени выполнения алгоритмов ее реализации. В отличие от известных работ, выражения построены для общих и частных (особых) случаев значений параметров вычислительной системы и коллективных операций. Для учета копирования сообщений в памяти вычислительных узлов модель LogP расширена дополнительным параметром [лямбда] – время, требуемое на копирование одного байта в памяти вычислительного узла. На примере алгоритма -параллельных цепочек продемонстрирован подход к построению оптимальных в модели LogP алгоритмов коллективных операций. Предложенный оптимизированный алгоритм -параллельных цепочек реализован в стандарте MPI. Результаты экспериментов на вычислительных кластерах с сетями связи стандарта MPI подтверждают полученные теоретические результаты, в частности рекомендации относительно выбор числа k цепочек. Выбор конкретной математической модели параллельных вычислений обусловлен спецификой алгоритма и целевой ВС. Например, если алгоритм реализует группировку сообщений в пакеты больших размеров, то целесообразно использовать модель LogGP, которая в явном виде учитывает издержки на передачу сообщений больших размеров.

Скачать в PDF

Ключевые слова Коллективные обмены; глобальные обмены; LogP; MPI; параллельное программирование; вычислительные системы.
Библиографический список 1. Хорошевский В.Г. Распределенные вычислительные системы с программируемой структурой // Вестник СибГУТИ. – 2010. – № 2. – С. 3-41.
2. Степаненко С.А. Мультипроцессорные среды суперЭВМ. Масштабирование эффективности. – М.: Физматлит, 2016. – 312 с.
3. Hoefler T., Moor D. Energy, Memory, and Runtime Tradeoffs for Implementing Collective Communication Operations // Journal of Supercomputing Frontiers and Innovations. – 2014.
– Vol. 1, No. 2. – P. 58-75.
4. Balaji P., Buntinas D., Goodell D., Gropp W., Hoefler T., Kumar S., Lusk E., Thakur R., Traff J. MPI on Millions of Cores // Parallel Processing Letters. – 2011. – Vol. 21, Issue 1. – P. 45-60.
5. Alverson R., Roweth D., Kaplan L. The Gemini System Interconnect // International Symposium on High Performance Interconnects. – 2010. – P. 83-87.
6. Eisley N., Heidelberger P., Senger R. The IBM Blue Gene/Q interconnection network and message unit // International Conference for High Performance Computing, Networking, Storage and Analysis. – 2011. – P. 1-10.
7. Абрамов С.М., Заднепровский В.Ф., Шмелёв А.Б., Московский А.А. СуперЭВМ ряда 4 семейства. СКИФ: штурм вершины суперкомпьютерных технологий // Вестник ННГУ.
– 2009. – № 5. – P. 200-210.
8. Левин В.К., Четверушкин Б.Н., Елизаров Г.С., Горбунов В.С., Лацис А.О., Корнеев В.В., Соколов А.А., Андрюшин Д.В., Климов Ю.А. Коммуникационная сетьМВС-Экспресс // Информационные технологии и вычислительные системы. – 2014. – № 1. – С. 10-24.
9. Симонов А.С., Макагон Д.В., Жабин И.А., Щербак А.Н., Сыромятников Е.Л., Поляков Д.А. Первое поколение высокоскоростной коммуникационной сети Ангара // Наукоемкие технологии. – 2014. – Т. 15, № 1. – С. 21-28.
10. Thakur R., Rabenseifner R., Gropp W. Optimization of collective communication operations in MPICH // Int. Journal of High Performance Computing Applications. – 2005. – Vol. 19 (1).
– P. 49-66.
11. Bruck J. [et al.]. Efficient Algorithms for All-to-All Communications in Multiport Message Passing Systems // IEEE Trans. Parallel Distrib. Syst. – 1997. – Vol. 8 (11). – P. 1143-1156.
12. Курносов М.Г. Алгоритмы трансляционно-циклических информационных обменов в иерархических распределенных вычислительных системах // Вестник компьютерных и информационных технологий. – 2011. – № 5. – С. 27-34.
13. Аветисян А.И., Гайсарян С.С., Иванников В.П., Падарян В.А. Прогнозирование произво-дительности MPI-программ на основе моделей // Автоматика и телемеханика. – 2007.
– Вып. 5. – С. 8-17.
14. Pjesivac-Grbovic J., Angskun T. [et al.]. Performance analysis of MPI collective operations // Cluster Computing. – 2007. – Vol. 10. – P. 127-143.
15. Hoefler T., Schneider T., Lumsdaine A. LogGOPSim – Simulating LargeScale Applications in the LogGOPS Model // Proc. of Int. Symposium on High Performance Distributed Computing. – 2010. – P. 597-604.
16. Culler D., Karp R., Patterson D. [et al.]. LogP: Towards a Realistic Model of Parallel Compu-tation // ACM SIGPLAN Notices. – 1993. – Vol. 28, No. 7. – P. 1-12.
17. Kielmann T. [et. al.]. Fast Measurement of LogP Parameters for Message Passing Platforms // Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing.
– Springer Verlag, 2000. – P. 1176-1183.
18. Fagg G., Pjesivac-Grbovic J., Bosilca G., Dongarra J., Jeannot E. Flexible collective com-munication tuning architecture applied to Open MPI // Proc. of Euro PVM/MPI. – 2006.
– P. 1-10.
19. Worsch T., Reussner R., Werner A. On Benchmarking Collective MPI Operations // Proceed-ings of the 9th EuroPVM/MPI Users' Group Meeting. – 2002. – P. 271-279.
20. Курносов М.Г. MPIPerf: пакет оценки эффективности коммуникационных функций биб-лиотек стандарта MPI // Вестник Нижегородского университета им. Н.И. Лобачевского. – 2012. – № 5 (2). – С. 385-391.

Comments are closed.