Отчет (Разработка параллельной версии программы для перемножения матриц с использованием ленточного алгоритма (отчёт))

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиПрактикум по курсу"Суперкомпьютеры и параллельная обработка данных"Разработка параллельной версии программы для перемножения матриц сиспользованием ленточного алгоритма.ОТЧЕТо выполненном заданиистудента 321 учебной группы факультета ВМК МГУАграновского Михаила ЛеонидовичаМосква, 2016 г.Оглавление1Постановка задачи .................................................................................................................................................... - 2 -2Описание алгоритма ленточного умножения матриц ...........................................................................................

- 2 -32.1Основа: последовательный алгоритм ............................................................................................................. - 2 -2.2Параллельный алгоритм .................................................................................................................................. - 3 -Результаты замеров времени выполнения ............................................................................................................ - 3 3.1Таблицы.............................................................................................................................................................. - 3 -3.23D-графики .........................................................................................................................................................

- 4 -3.2.1OpenMP на Regatta .................................................................................................................................... - 4 -3.2.2MPI на Regatta ............................................................................................................................................ - 5 -3.2.3OpenMP на Bluegene ................................................................................................................................. - 5 -3.2.4MPI на Bluegene .........................................................................................................................................

- 6 -3.2.5OpenMP на ноутбуке ................................................................................................................................. - 6 -4Анализ результатов ................................................................................................................................................... - 7 -5Выводы ....................................................................................................................................................................... - 7 --1-1 Постановка задачиСтавится задача перемножения двух квадратных матриц при помощи т.н. ленточного алгоритма: = A x B, A, B, C ∈ Результатом перемножения матриц А и B является матрица С, каждый элемент которой есть скалярноепроизведение соответствующих строк матрицы A и столбцов матрицы B.Требуется:1.

Реализовать параллельные алгоритмы ленточного перемножения матриц с помощью технологийпараллельного программирования OpenMP и MPI.2. Сравнить их эффективность.3. Исследовать масштабируемость полученных программ и построить графики зависимости временивыполнения программ от числа используемых ядер и объёма входных данных.2 Описание алгоритма ленточного умножения матриц2.1 Основа: последовательный алгоритмПростейшая форма алгоритма ленточного умножения матриц имеет следующий вид:void ribbonMult(int *a, int *b, int *c, int n){for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {auto pElem = &(c[i * n + j]);*pElem = 0;for (int k = 0; k < n; k++) {*pElem += a[i * n + k] * b[k * n + j];}}}}-2-Этот алгоритм является итеративным и ориентирован на последовательное вычисление строк матрицы С.Предполагается выполнение n*n*n операций умножения и столько же операций сложения элементов исходныхматриц.

Количество выполненных операций имеет порядок O(n**3).2.2 Параллельный алгоритмРазбиваем задачу вычисления конечной матрицы на подзадачи по вычислению строк и распределяем их попотокам (OpenMP) / процессам (MPI). Разбиение на вычисление отдельных полей не производим, т.к. размерыматриц при вычислениях и так будут на порядки превышать число потоков (процессов).Ниже приведены краткие заметки по реализациям параллельных алгоритмах на OpenMP и MPI. Коды программможно найти в github-репозитории: https://github.com/agrml/ribbonMultiplicationSummaryВ OpenMP-версии вся модификация когда сводится к добавлению клаузы omp parallel for.В MPI-версии производится широковещательная рассылка заполненных матриц a, b, а в конце работы – reduceрезультатов.

Для синхронизации используются команды MPI_Barrier.Реализованные алгоритмы проверялись на корректность и совпадение по результатам с последовательнымалгоритмом (соответствующий код закомментирован).3 Результаты замеров времени выполненияНиже приведены результаты замеров времени программ на суперкомпьютерах Bluegene и Regatta:непосредственно в табличной форме и наглядно на 3D-графиках.Программа была запущена в конфигурациях:на Regatta - 1,2,4,8,16 ядер для MPI и OpenMP-программы;на Bluegene - 1,2,4 для OpenMP; 1,2,4,8,16,32,64,128,256 для MPI.Также для сравнения OpenMP-версия программы была запущена на ноутбуке (Core i5-6300HQ 2.30GHz × 4, 24GBRAM, Ubuntu 16.04)Каждая конфигурация была запущена 3 раза.

Ниже приведены усредненные результаты.3.1 Таблицы-3---3.2 3D-графики3.2.1OpenMP на Regatta-4-3.2.2MPI на Regatta3.2.3OpenMP на Bluegene-5-3.2.4MPI на BluegeneЗамечание к графику: может показаться, что на размере матрицы в 2560 строк скорость выполнения выросла. Этоне так: на графике нету данных по вычислению на 1 процессоре по причине превышения ограничения повремени (см. таблицу).3.2.5OpenMP на ноутбуке-6-4 Анализ результатовНа одинаковых конфигурациях OpenMP показал результаты лучшие, чем MPI.

Однако в абсолютном зачетепобеждает MPI на 256 процессорах Bluegene. Так как система заточена под прогопроцессорные вычисления(множество относительно слабых процессоров), результаты запуска на Bluegene OpenMP-версии не впечатляют. Впрактических целях OpenMP (да и любые другие многопоточные (multithread) программы) следует выполнять наRegatta.Заметим, что задача прекрасна поддалась распараллеливанию и зависимость скорости работы от числавычислителей близка к линейной.В сравнении с временем работы на ноутбуке принципиальный выигрыш дает выполнение на 256 вычислителяхBluegene. Заметим, что на ПК уже зависимость времени работы от числа потоков не линейная, а переход от 4потоков (число ядер процессора, Intel Hiperthreading отсутствует) к 8 сопровождается спадомпроизводительности.

На суперкомпьютерах данную ситуацию поймать не удалось.5 ВыводыВыполнена работа по разработке параллельной версии алгоритма ленточного умножения матриц. Изученытехнологии написания параллельных алгоритмов OpenMP и MPI. Проанализировано время выполненияалгоритмов на различных вычислительных системах.Технология OpenMP крайне удобна в использовании, причем дает колоссальный прирост производительности нарассчитанных на многопоточные вычисления системах, в том числе и на персональных компьютерах.MPI можно назвать более низкоуровневой технологией: разработка MPI-программы знакомит с основамивзаимодействия вычислительных узлов суперкомпьютера. При этом MPI заточена именно на многопроцессорныесистемы и наибольшую скорость работы показала именно MPI-реализация, запущенная на наибольшем числевычислителей суперкомпьютера Bluegene.-7-.