Отчет (1127765)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиПрактикум по курсу"Суперкомпьютеры и параллельная обработка данных"Разработка параллельной версии программы для перемножения матриц сиспользованием ленточного алгоритма.ОТЧЕТо выполненном заданиистудента 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-.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
