Мет указ ЛР. Мет.указ_ЛР_. Образовательная программа 7М06102 Вычислительная техника и про граммное обеспечение
 Скачать 1.74 Mb.
|
|
0 Карагандинский технический университет МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ Дисциплина PVV 5106 «Параллельные и высокопроизводительные вы- числения» Модуль RPPO 02 «Разработка и проектирование программного обеспече- ния» Образовательная программа 7М06102 «Вычислительная техника и про- граммное обеспечение» Факультет инновационных технологий Кафедра Информационно-вычислительных систем 2021 1 Методические указания к выполнению лабораторных работ по дисциплине разработаны к.т.н., Томиловой Н.И. Обсуждена на заседании кафедры информационно-вычислительных систем Протокол № __20__ от «_20_»_____05______2021г. Зав. кафедрой ____ Калинин А.А._ «_20_»_____05___2021 г. (подпись) (ФИО) Одобрена учебно-методическим советом факультета инновационных технологий Протокол № ____10__ от «__21_»____05______2021 г. Председатель ___ Савченко Н.К. «__21_»____05____2021 г. (подпись) (ФИО) 2 Содержание 1 Python. Системные инструменты параллельного выполнения 2 Параллельные методы умножения матрицы на вектор 3 Параллельные методы матричного умножения 4 Параллельные методы решения систем линейных уравнений 5 Сортировка данных 6 Обработка графов 7 Решение дифференциальных уравнений в частных производных Лабораторная работа № 1 Тема: Python. Системные инструменты параллельного выполнения Цель работы: Усвоить концепцию параллелизма, научиться создавать несколько операций одновременно и распределять нагрузку между ядрами процессора с использованием языка программирования Python. Краткие теоретические сведения При параллельном программировании производительность приложений и программных систем может быть улучшена, потому как появляется возможность одновременно обрабатывать запросы, а не ждать завершения предыдущего. Процесс – это часть виртуальной памяти и ресурсов, которую ОС выделяет для выполнения программы. Если открыть несколько экземпляров одного приложения, под каждый система выделит по процессу. Например, в современных браузерах за каждую вкладку может отвечать отдельный процесс. Поток – это самая маленькая единица выполнения в операционной системе. Она сама по себе не является программой, а работает внутри программы. Другими словами, потоки не являются независимыми друг от друга и совместно используют раздел кода, раздел данных и т. д. С другими потоками. У каждого приложения есть как минимум один процесс, а у каждого процесса – минимум один поток, который называют главным и из которого при необходимости запускают новые. Разница между потоками и процессами: потоки используют память, выделенную под процесс, а процессы требуют себе отдельное место в памяти. Поэтому потоки создаются и завершаются быстрее: системе не нужно каждый раз выделять им новое адресное пространство, а потом высвобождать его. 3 процессы работают каждый со своими данными – обмениваться чем-то они могут только через механизм межпроцессного взаимодействия. Потоки обращаются к данным и ресурсам друг друга напрямую: что изменил один — сразу доступно всем. Поток может контролировать «собратьев» по процессу, в то время как процесс контролирует исключительно своих «дочек». Поэтому переключаться между потоками быстрее и коммуникация между ними организована проще. Многопоточность — разбитие процесса на потоки, которые параллельно обрабатываются процессором в одну единицу времени. Вычислительная нагрузка распределяется между двумя или более ядрами, так что интерфейс и другие компоненты программы не замедляют работу друг друга. Многопоточные приложения можно запускать и на одноядерных процессорах, но тогда потоки выполняются по очереди. Преимущества многопоточности заключаются в следующем: скорость обмена данными — многопоточность повышает скорость вычислений, поскольку каждое ядро или процессор обрабатывает отдельные потоки одновременно. программа остается отзывчивой — она позволяет программе оставаться отзывчивой, поскольку один поток ожидает ввода, а другой одновременно запускает графический интерфейс. доступ к глобальным переменным — в многопоточности все потоки определенного процесса могут получить доступ к глобальным переменным, и если есть какое-либо изменение в глобальной переменной, то это видно и другим потокам. использование ресурсов — запуск нескольких потоков в каждой программе улучшает использование процессора, а время простоя процессора уменьшается. иовместное использование данных. Нет необходимости в дополнительном пространстве для каждого потока, поскольку потоки в программе могут совместно использовать одни и те же данные. Python включает в себя ряд разных параллельных конструкций, таких как как threading, queues и multiprocessing. Модуль threading использовался как главный способ достижения параллельности. Несколько лет назад, модуль multiprocessing был добавлен в пакет стандартных библиотек Python. Для реализации многопоточности модуль run () — является точкой входа для потока. start () —запускает поток, вызывая метод run. 4 join ([время]) — ожидает завершения потоков. isAlive () — проверяет, выполняется ли еще поток. getName () — возвращает имя потока. setName () — Метод setName () устанавливает имя потока. threading.activeCount () — возвращает количество активных объектов потока threading.currentThread () — возвращает количество объектов потока в элементе управления потоком вызывающей стороны. threading.enumerate () — возвращает список всех объектов потока, которые в данный момент активны. Лабораторная работа рассчитана на 2 часа аудиторных занятий и состоит в изучении теоретического материала и получении практических навыков при работе с потоками в python. Сдача лабораторной работы заключается в ответах на контрольные вопросы и созданием потоков в Python. Содержание отчета (в электронном виде): 1. Название и цель работы 2. Ответы на контрольные вопросы 3. Скрипты выполненных заданий в Python. Задания: 1) Осуществить проверку скриптов из примера Example1, Example2, Example3. (в примере 2 и 3 использовать собственные ссылки на файлы) 2) Привести пример скрипта по созданию демонических потоков в Python. Контрольные вопросы 1. Что такое параллелизм? 2. Как вы понимаете понятие многопоточность? 3. В чем разница между потоками и процессами? 4. Перечислите основные команды класса Thread? 5 Лабораторная работа № 2 Тема: Параллельные методы умножения матрицы на вектор Цель работы: Произвести сравнительный анализ затраченного времени двух методов параллельного умножения матрицы на вектор. Краткие теоретические сведения. Для многих методов матричных вычислений характерным является повторение одних и тех же вычислительных действий для разных элементов матриц. Данный момент свидетельствует о наличии параллелизма по данным при выполнении матричных расчетов и, как результат, распараллеливание матричных операций сводится в большинстве случаев к разделению обрабатываемых матриц между потоками. Выбор способа разделения матриц приводит к определению конкретного метода параллельных вычислений; существование разных схем распределения данных порождает целый ряд параллельных алгоритмов матричных вычислений. Наиболее общие и широко используемые способы разделения матриц состоят в разбиении данных на полосы (по вертикали или горизонтали) или на прямоугольные фрагменты (блоки). 1. Ленточное разбиение матрицы. При ленточном (block-striped) разбиении каждому потоку выделяется то или иное подмножество строк (rowwise или горизонтальное разбиение) или столбцов (columnwise или вертикальное разбиение) матрицы. Разделение строк и столбцов на полосы в большинстве случаев происходит на непрерывной (последовательной) основе. Вертикальное разбиение (разделение данных по столбцам). Для того, чтобы реализовать такой подход, необходимо распараллелить внутренний цикл алгоритма умножения матрицы на вектор. В результате данного подхода параллельные области будут создаваться для вычисления каждого отдельного элемента результирующего вектора. Программа будет представляться в виде набора последовательных (однопотоковых) и параллельных (многопотоковых) участков. Подобный принцип организации параллелизма получил название «вилочного» (forkjoin) или пульсирующего параллелизма. При выполнении многопотокового участка каждый поток выполняет умножение одного элемента своего столбца исходной матрицы на один элемент вектора. Следующий за этим однопотоковый участок производит суммирование полученных результатов для того, чтобы вычислить элемент результирующего вектора. Таким образом, программа будет состоять из чередования n многопотоковых и n однопотоковых участков. 6 2. Блочный метод - основан на ином способе разделения данных – на разбиении матрицы на прямоугольные фрагменты (блоки). При использовании блочного представления матрицы A базовые подзадачи целесообразно определить на основе вычислений, выполняемых над матричными блоками. Для нумерации подзадач могут использоваться индексы располагаемых в подзадачах блоков матрицы A, т.е. подзадача (i,j) производит вычисления над блоком Aij. Помимо блока матрицы A каждая подзадача должна иметь доступ к блоку вектора b. При этом для блоков одной и той же подзадачи должны соблюдаться определенные правила соответствия – операция умножения блока матрицы Aij может быть выполнена только, если блок вектора b'(i,j) имеет вид: Теперь ознакомимся с визуальным выполнением параллельного умножение матрицы на вектор с помощью программы ПараЛаб: 1) Блочное разбиение: Запускаем Паралаб, создаём новый эксперимент. Затем задаём в пункте меню «Система» топологию сети «Решётка» Затем пункте меню «Задача» выбираем пункт «Умножение матрицы на вектор», затем кликаем по пункту «Метод решения» видим, что для данной топологии доступен только блочный метод. В пункте «Параметры задачи» задаём размерность 150 и запускаем выполнение. Рис.1 – результат выполнения. 7 Вариант Количество узлов Размерность объектов 1 8 2100-2500 2 9 2200-2600 3 10 2300-2700 4 11 2400-2800 5 12 2500-2900 6 13 2800-3200 7 14 1900-2300 8 15 1700-2100 9 16 1600-2000 10 20 2100-2500 Контрольные вопросы: 1. Какие существуют показатели эффективности параллельного алгоритма? 2. Расскажите о законе Амдаля, каков его эффект? 3. Опишите закон Густавсона –Барсиса. 4. Что такое масштабируемость параллельного алгоритма? 5. В чём заключается метод горизонтального разбиения? 6. В чём заключается метод вертикального разбиения? 7. В чём заключается метод блочного разбиения? ЛАБОРАТОРНАЯ РАБОТА № 3 Тема: «Параллельные методы матричного умножения» Цель работы: ознакомиться со способами реализации методов матричного умножения в программной системе «Paralab». Теоретические основы Матрица – это математический объект, записываемый в виде прямоугольной таблицы элементов. Эта таблица представляет собой 8 совокупность строк и столбцов, на пересечении которых находятся её элементы. Количество строк и столбцов задает размер матрицы. Умножение матрицы A размера m×n и матрицы B размера n×k приводит к получению матрицы С размера m×k, каждый элемент которой определяется скалярным произведением соответствующей строки матрицы А и столбца матрицы В. В данной работе рассматриваются только квадратные матрицы, т. е. m=n=k. При умножении матриц результирующая матрица C представляется разбитой на квадратные блоки. Каждый процессор многопроцессорной вычислительной системы отвечает за вычисление одного (алгоритмы Фокса и Кэннона) или нескольких (ленточный алгоритм) блоков результирующей матрицы С. Лабораторная работа рассчитана на 1 час аудиторных занятий и состоит в изучении теоретического материала и получении практических навыков при работе с параллельными вычислениями в программной системе ПараЛаб. Сдача лабораторной работы заключается в ответах на контрольные вопросы и выполнении заданий по умножению матриц в программной системе ПараЛаб. Содержание отчета (в электронном виде): 1. Название и цель работы 2. Ответы на контрольные вопросы 3. Результаты проведенных экспериментов. Задания к лабораторной работе №4: 1. Опишите работу ленточного алгоритма умножения двух матриц размерностью 4x4 со случайными элементами. Решение можно привести в виде схематического изображения или программного кода. Пример функции параллельного матричного умножения на языке С++ с использованием библиотеки mpi.h: void MatrixMultiplicationMPI(double *&A, double *&B, double *&C, int &Size) { int dim = Size; int i, j, k, p, ind; double temp; MPI_Status Status; int ProcPartSize = dim/ProcNum; int ProcPartElem = ProcPartSize*dim; double* bufA = new double[ProcPartElem]; double* bufB = new double[ProcPartElem]; double* bufC = new double[ProcPartElem]; int ProcPart = dim/ProcNum, part = ProcPart*dim; if (ProcRank == 0) { Flip(B, Size); } MPI_Scatter(A, part, MPI_DOUBLE, bufA, part, MPI_DOUBLE, 0, MPI_COMM_WORLD); MPI_Scatter(B, part, MPI_DOUBLE, bufB, part, MPI_DOUBLE, 0, MPI_COMM_WORLD); 9 temp = 0.0; for (i=0; i < ProcPartSize; i++) { for (j=0; j < ProcPartSize; j++) { for (k=0; k < dim; k++) temp += bufA[i*dim+k]*bufB[j*dim+k]; bufC[i*dim+j+ProcPartSize*ProcRank] = temp; temp = 0.0; } } int NextProc; int PrevProc; for (p=1; p < ProcNum; p++) { NextProc = ProcRank+1; if (ProcRank == ProcNum-1) NextProc = 0; PrevProc = ProcRank-1; if (ProcRank == 0) PrevProc = ProcNum-1; MPI_Sendrecv_replace(bufB, part, MPI_DOUBLE, NextProc, 0, PrevProc, 0, MPI_COMM_WORLD, &Status); temp = 0.0; for (i=0; i < ProcPartSize; i++) { for (j=0; j < ProcPartSize; j++) { for (k=0; k < dim; k++) { temp += bufA[i*dim+k]*bufB[j*dim+k]; } if (ProcRank-p >= 0 ) ind = ProcRank-p; else ind = (ProcNum-p+ProcRank); bufC[i*dim+j+ind*ProcPartSize] = temp; temp = 0.0; } } } MPI_Gather(bufC, ProcPartElem, MPI_DOUBLE, C, ProcPartElem, MPI_DOUBLE, 0, MPI_COMM_WORLD); delete []bufA; delete []bufB; delete []bufC; } 2. Создайте в системе ПараЛаб новое окно вычислительного эксперимента и назовите его «Лабораторная работа 4». 3. Изменяя число вычислительных узлов, проведите серию экспериментов «Матричное умножение» для алгоритма Кэннона в соответствии с исходными данными, представленными в вашем индивидуальном задании: 10 № вар иан та Метод решения Разме рност ь матри цы Топология Произв одитель ность процесс оров Латентнос ть Пропускн ая способнос ть Метод передачи данных 1 Алгоритм Кэннона 100 Решетка 1 0 10 Передача сообщений 2 200 1.2 10 100 Передача пакетов 3 300 1.5 50 500 Передача сообщений 4 400 2 70 1000 Передача пакетов 5 500 2.5 100 2000 Передача сообщений 6 600 3 130 2500 Передача пакетов 7 900 3.5 150 5000 Передача сообщений 8 1000 4 160 7000 Передача пакетов 9 3000 4.5 180 8500 Передача сообщений 10 5000 5 200 10000 Передача пакетов Результаты представьте в виде таблицы или графика. 4. Изменяя число вычислительных узлов, проведите серию экспериментов «Матричное умножение» для ленточного алгоритма Фокса в соответствии с исходными данными, представленными в вашем индивидуальном задании: № вар иан та Метод решения Разме рност ь матри цы Топология Произв одитель ность процесс оров Латентнос ть Пропускн ая способнос ть Метод передачи данных 1 Алгоритм Фокса 100 Решетка 1 0 10 Передача сообщений 2 200 1.2 10 100 Передача пакетов 3 300 1.5 50 500 Передача сообщений 4 400 2 70 1000 Передача пакетов 5 500 2.5 100 2000 Передача сообщений 6 600 3 130 2500 Передача пакетов 7 900 3.5 150 5000 Передача сообщений 11 8 1000 4 160 7000 Передача пакетов 9 3000 4.5 180 8500 Передача сообщений 10 5000 5 200 10000 Передача пакетов Результаты представьте в виде таблицы или графика. 5. Полученные результаты приложите к отчету о проведенной лабораторной работе Контрольные вопросы 1. Что такое матрица? 2. Опишите алгоритм умножения матриц. 3. Какие методы матричного умножения рассматриваются в программной системе Paralab? 4. В чем состоит отличие ленточного алгоритма от алгоритмов Кэнона и Фокса? Лабораторная работа № 4 Тема: Параллельные методы решения систем линейных уравнений Цель: Реализация работы параллельного программирования в системе Паралаб. Выполнение решения системы линейных уравнений методом Гаусса и методом сопряженных градиентов. Краткие теоретические сведения Система линейных алгебраических уравнений (линейная система, также употребляются аббревиатуры СЛАУ, СЛУ) — система уравнений, каждое уравнение в которой является линейным — алгебраическим уравнением первой степени. В классическом варианте коэффициенты при переменных, свободные члены и неизвестные считаются вещественными числами, но все методы и результаты сохраняются (либо естественным образом обобщаются) на случай любых полей, например, комплексных чисел. Решение систем линейных алгебраических уравнений — одна из классических задач линейной алгебры, во многом определившая её объекты и методы. Кроме того, линейные алгебраические уравнения и методы их 12 решения играют важную роль во многих прикладных направлениях, в том числе в линейном программировании, эконометрике. Известно обобщение понятия системы линейных алгебраических уравнений на случай бесконечного множества неизвестных (бесконечная система линейных алгебраических уравнений). Системы линейных уравнений возникают при решении ряда прикладных задач, описываемых дифференциальными, интегральными или системами нелинейных (трансцендентных) уравнений. Они могут появляться также в задачах математического программирования, статистической обработки данных, аппроксимации функций, при дискретизации краевых дифференциальных задач методом конечных разностей или методом конечных элементов и др. Матрицы коэффициентов систем линейных уравнений могут иметь различную структуру и свойства. Матрицы решаемых систем могут быть плотными и их порядок может достигать несколько тысяч строк и столбцов. При решении многих задач могут появляться системы, обладающие симметричными положительно определенными ленточными матрицами с порядком в десятки тысяч и шириной ленты в несколько тысяч элементов. И, наконец, при рассмотрении большого ряда задач могут возникать системы линейных уравнений с разреженными матрицами с порядком в миллионы строк и столбцов. Метод Гаусса является широко известным прямым алгоритмом решения систем линейных уравнений, для которых матрицы коэффициентов являются плотными. Если система линейных уравнений является невырожденной, то метод Гаусса гарантирует нахождение решения с погрешностью, определяемой точностью машинных вычислений. Основная идея метода состоит в приведении матрицы А посредством эквивалентных преобразований к треугольному виду, после чего значения искомых неизвестных могут быть получены непосредственно в явном виде. Задания к лабораторной работе. 1. Выполнить эксперименты согласно варианту (Таблица 1) по решению линейных уравнений методом Гаусса и методом сопряженных градиентов в системе ПараЛаб. Провести сравнительный анализ. Таблица 1. Варианты индивидуальных заданий № Кол-во узлов Кол-во процессоров Кол-во ядер Кол-во упражнений Метод линейного уравнения 1 5 2 1 100 Метод Гаусса и метод 2 3 6 1 2 200 13 4 сопряженных градиентов 5 3 2 3 150 6 7 4 2 1 180 8 9 2 1 2 130 10 2. Выполнить распараллеливание линейных уравнений методом Гаусса на языке C++. Контрольные вопросы: 1. Что представляет собой система линейных уравнений? 2. Опишите реализацию метода Гаусса для решения систем линейных уравнений. 3. Какие показатели эффективности для параллельного варианта метода Гаусса? 4. Опишите реализацию метода сопряженных градиентов. 5. Какой из алгоритмов обладает лучшими показателями ускорения? Лабораторная работа № 5 Тема: Сортировка данных Цель работы: изучить основные способы распараллеливания алгоритмов сортировки. Краткие теоретические сведения. Сортировка является одной из типовых проблем обработки данных, и обычно понимается как задача размещения элементов неупорядоченного набора значений в порядке монотонного возрастания или убывания (здесь и далее все пояснения для краткости будут даваться только на примере упорядочивания данных по возрастанию). Вычислительная трудоемкость процедуры упорядочивания является достаточно высокой. Так, для ряда известных простых методов (пузырьковая сортировка, сортировка включением и др.) количество необходимых операций определяется квадратичной зависимостью от числа упорядочиваемых данных 14 , где n – количество элементов массива Для более эффективных алгоритмов (сортировка слиянием, сортировка Шелла, быстрая сортировка) трудоемкость определяется величиной Данное выражение дает также нижнюю оценку необходимого количества операций для упорядочивания набора из значений; алгоритмы с меньшей трудоемкостью могут быть получены только для частных вариантов задачи. Ускорение сортировки может быть обеспечено при использовании нескольких ( , ) процессоров. Исходный упорядочиваемый набор в этом случае разделяется между процессорами; в ходе сортировки данные пересылаются между процессорами и сравниваются между собой. Результирующий (упорядоченный) набор, как правило, также разделен между процессорами; при этом для систематизации такого разделения для процессоров вводится та или иная система последовательной нумерации и обычно требуется, чтобы при завершении сортировки значения, располагаемые на процессорах с меньшими номерами, не превышали значений процессоров с большими номерами. Оставляя подробный анализ проблемы сортировки для специального рассмотрения, в пособии основное внимание уделяется изучению параллельных способов выполнения для ряда широко известных методов внутренней сортировки, когда все упорядочиваемые данные могут быть размещены полностью в оперативной памяти ЭВМ. Параллельное обобщение базовой операции сортировки 1. При детальном рассмотрении способов упорядочивания данных, применяемых в алгоритмах сортировки, можно обратить внимание, что многие методы основаны на применении одной и той же базовой операции "сравнить и переставить" (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановки этих значений, если их порядок не соответствует условиям сортировки // операция "сравнить и переставить" if ( a[i] > a[j] ) { temp = a[i]; a[i] = a[j]; a[j] = temp; } Целенаправленное применение данной операции позволяет упорядочить данные; в способах выбора пар значений для сравнения собственно и проявляется различие алгоритмов сортировки. Так, например, в пузырьковой сортировке осуществляется последовательное сравнение всех соседних элементов; в результате прохода по упорядочиваемому 15 набору данных в последнем (верхнем) элементе оказывается максимальное значение ("всплывание пузырька"); далее для продолжения сортировки этот уже упорядоченный элемент отбрасывается и действия алгоритма повторяются // пузырьковая сортировка for ( i=1; i } 2. Для параллельного обобщения выделенной базовой операции сортировки рассмотрим первоначально ситуацию, когда количество процессоров совпадает с числом сортируемых значений (т.е. ). Тогда сравнение значений и , располагаемых, например, на процессорах и , можно организовать следующим образом: - выполнить взаимообмен имеющихся на процессорах и значений (с сохранением на этих процессорах исходных элементов); - сравнить на каждом процессоре и получившиеся одинаковые пары значений ( , ); результаты сравнения используются для разделения данных между процессорами – на одном процессоре (например, ) остается меньший элемент, другой процессор (т.е. ) запоминает для дальнейшей обработки большее значение пары , 3. Рассмотренное параллельное обобщение базовой операции сортировки может быть надлежащим образом адаптировано и для случая , когда количество процессоров является меньшим числа упорядочиваемых значений. В данной ситуации каждый процессор будет содержать уже не единственное значение, а часть (блок размера ) сортируемого набора данных. Эти блоки обычно упорядочиваются в самом начале сортировки на каждом процессоре в отдельности при помощи какого-либо быстрого алгоритма (предварительная стадия параллельной сортировки). Далее, следуя схеме одноэлементного сравнения, взаимодействие пары процессоров и для совместного упорядочения содержимого блоков и может быть осуществлено следующим образом: - выполнить взаимообмен блоков между процессорами и ; - объединить блоки и на каждом процессоре в один отсортированный блок двойного размера (при исходной упорядоченности 16 блоков и процедура их объединения сводится к быстрой операции слияния упорядоченных наборов данных); - разделить полученный двойной блок на две равные части и оставить одну из этих частей (например, с меньшими значениями данных) на процессоре , а другую часть (с большими значениями соответственно) – на процессоре Рассмотренная процедура обычно именуется в литературе как операция "сравнить и разделить" (compare-split). Следует отметить, что сформированные в результате такой процедуры блоки на процессорах и совпадают по размеру с исходными блоками и и все значения, расположенные на процессоре , являются меньшими значений на процессоре . Алгоритм пузырьковой сортировки Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания – сравнение пар значений упорядочиваемого набора данных происходит строго последовательно. В связи с этим для параллельного применения используется не сам этот алгоритм, а его модификация, известная в литературе как метод чет-нечетной перестановки (odd-even transposition). Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода – в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами. Т.е., на всех нечетных итерациях сравниваются пары , ,…, (при четном ), на четных итерациях обрабатываются элементы , ,…, После -кратного повторения подобных итераций сортировки исходный набор данных оказывается упорядоченным. Получение параллельного варианта для метода чет-нечетной перестановки уже не представляет каких-либо затруднений – сравнение пар значений на итерациях сортировки любого типа являются независимыми и могут быть выполнены параллельно. 17 Рис 1. Пример чет-нечетной перестановки для 6 элементов Программная реализация. #include #include #include #include A = new int(size); cout << "Before sort:" << endl; for (int i = 0; i A[i] = rand(); cout << A[i] << " "; } cout << endl; int N = size; int i = 0, j = 0; int first; double start, end; start = omp_get_wtime(); for (i = 0; i < N - 1; i++) { first = i % 2; //0 если 0,2,4... //1 если 1,3,5... #pragma omp parallel for default(none),shared(A,first) for (j = first; j < N - 1; j += 2) { if (A[j] > A[j + 1]) { swap(&A[j], &A[j + 1]); } } } end = omp_get_wtime(); cout << "After sort:" << endl; 18 for (i = 0; i } printf("\n-------------------------\n Time Parallel= %f", (end - start)); } void swap(int *num1, int *num2) { int temp = *num1; *num1 = *num2; *num2 = temp; } Быстрая сортировка Существует множество параллельных обобщений алгоритма быстрой сортировки. Рассмотрим наиболее простой способ, но тем не менее дающий хорошее ускорение последовательного алгоритма на многопроцессорных системах. Пусть, исходный набор данных расположен на первом процессоре, с него начинается работа алгоритма: Процессор выбирает ведущий элемент, сортирует остальные элементы относительно него (большие - в правую сторону, меньшие - в левую); Меньшую часть он отдает другому свободному процессору; После этого процессор продолжает работать с большей частью одновременно, в то время как другой процессор работает с меньшей по принципу начиная с 1го пункта; Когда все процессоры получат свою часть, ускорение алгоритма будет максимальным. В ходе работы алгоритма исходный набор окажется разделенным на две части (случайно), меньшая из которых передастся другому свободному процессору, большая останется на исходном для дальнейшей обработки. Далее обе части опять будут разделены и опять на двух исходных останутся большие части (на первом процессоре всё равно большая), а меньшие отправятся другим процессорам. В этом заключается ускорение алгоритма. При задействовании всех процессов, все части параллельно будут сортироваться последовательным алгоритмом. 19 Рис 2. Пример параллельного выполнения быстрой сортировки #include #include }; int main() { QuickSort a; double start, end; omp_set_nested(true); a.init(); start = omp_get_wtime(); a.Sort(); end = omp_get_wtime(); a.Display(); printf("\n-------------------------\n Time Parallel= %f", (end - start)); } void sort(int *a, int low, int high) { if (high < low || low == high) return; if (high == low + 1) { if (a[low] > a[high]) swap(a[low], a[high]); return; } int pivotidx = partition(a, low, high); printf ("Pivot element has been placed at correct position: %d by thread: %d \n" ,pivotidx, omp_get_thread_num()); #pragma omp parallel sections { #pragma omp section { sort(a, low, pivotidx); 20 } #pragma omp section { sort(a, pivotidx + 1, high); } } } int partition(int *a, int low, int high) { int pivot = low; int pivotval = a[low]; int leftpointer = low; int rightpointer = high; while (leftpointer < rightpointer) { while (a[leftpointer] <= a[pivot] && leftpointer <= high) ++leftpointer; if (leftpointer > high) --leftpointer; while (a[rightpointer] >= a[pivot] && rightpointer >= low) --rightpointer; if (rightpointer < low) ++rightpointer; if (leftpointer < rightpointer) swap(a[leftpointer], a[rightpointer]); } a[low] = a[rightpointer]; a[rightpointer] = pivotval; return rightpointer; } void QuickSort::init() { cout << "Enter the number of elements in the array: "; cin >> len; arr = new int[len]; for (int i = 0; i < len; ++i) arr[i] = rand(); } void QuickSort::Sort() { sort(arr, 0, len - 1); } void QuickSort::Display() { cout << "Sorted array is: " << endl; for (int i = 0; i < len; ++i) cout << arr[i] << " "; cout << endl; } Лабораторная работа рассчитана на 1 час аудиторных занятий и состоит в изучении теоретического материала и получении практических навыков при работе с параллельными методами сортировки в программной системе ПараЛаб и языке C++. Сдача лабораторной работы заключается в ответах на контрольные вопросы и выполнении заданий по сортировке в программной системе ПараЛаб и средствами языка C++. Содержание отчета (в электронном виде): 2. Название и цель работы 3. Ответы на контрольные вопросы 4. Результаты выполненных заданий. Вариант Количество узлов Размер массива 21 1 8 2000-2400 2 2500-2900 3 3000-3400 4 3500-3900 5 4000-4400 6 16 4500-4900 7 5000-5400 8 5500-5900 9 6000-6400 10 6500-6900 Задания: 1)Выполнить задачу по сортировке данных в системе ПараЛаб используя метод быстрой сортировки. Количество узлов и размер массива представлены в таблице 1. Результаты представьте в виде таблицы. 2)Выполнить задачу по сортировке данных в системе ПараЛаб используя метод пузырька. Количество узлов и размер массива представлены в таблице 1. Результаты представьте в виде таблицы. 3)Используя стандартную функцию быстрой сортировки языка C++ и приведенный выше пример ее параллельной реализации выполнить сортировку массива и сравнить скорость выполнения. Для размеров массива использовать данные из таблицы 1 уменьшенные в 100 раз. Результат представьте в виде скриншота. Контрольные вопросы: 1.Расскажите про параллельное обобщение базовой операции сортировки? 2.Приведите пример распараллеливания алгоритма пузырьковой сортировки? 3.Приведите пример распараллеливания алгоритма быстрой сортировки? 4.Что понимается под параллельной программой в рамках OpenMP? 5. Что такое Параллельный фрагмент, Параллельный фрагмент и Параллельная секция? 22 Лабораторная работа № 6 Тема: Параллельные а лгоритмы на графах Цель работы: изучить практическое применение алгоритмов на графах. Краткие теоретические сведения. Представление данных в виде графа используется во многих прикладных областях, однако обработка больших объемов таких данных на современных вычислительных системах выполняется менее эффективно, чем данных, полученных в ходе научного моделирования. Поэтому в научном и техническом сообществе большое внимание уделяется разработке эффективных реализаций алгоритмов на графах для высокопроизводительных систем. Это подтверждается большим числом научных публикаций, разработкой новых библиотек. Материалы к изучению: Параллельные алгоритмы на графах (Гергель) - http://www.hpc- education.ru/files/lectures/gergel/ch_10.pdf Способы хранения графов – https://dexp.in/russian/graph-storage/ Дополнительный материалы к изучению: 1. Параллельная обработка больших графов - https://ppt-online.org/671535 2. Обзор систем обработки больших графов - https://www.dislab.org/GraphHPC-2017/slides/GraphHPC- 2017_6_Chernoskutov_Review-of-Big-Graphs-Processing-Systems_ru.pdf (Особо не углубляться, просто ознакомиться и понять, где и почему используются графы на практике) 3. Поиск в ширину - https://foxford.ru/wiki/informatika/algoritm-poiska-v- shirinu 4. Алгоритм Дейкстры – https://foxford.ru/wiki/informatika/algoritm- deykstry 5. Алгоритм Флойда-Уоршелла - https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D 0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BB%D0% BE%D0%B9%D0%B4%D0%B0 6. Алгоритм Прима – https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D 0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B 8%D0%BC%D0%B0 23 Исходные коды: Алгоритм Ссылка на источник Технологий Параллельный поиск в ширину (Breadth-first search) https://github.com/starlordvk/Parallel-BFS C++, MPI Последовательны й и параллельный алгоритм Флойда - Уоршелла (Поиск наикратчайших путей в графе) https://grwoodw.github.io/python102/12- parallel_programming/ Python, multiprocessin g Алгоритм Флойда - Уоршелла (Поиск наикратчайших путей в графе) https://github.com/LopesManuel/MPI-Floyd- Warshall-C С, MPI Алгоритм Прима (Нахождение минимального остовного дерева в графе) https://github.com/elahehrashedi/MPI_Prime_MS T C, MPI Алгоритм Дейкстры (Поиск наикратчайших путей в графе) https://github.com/Lehmannhen/MPI-Dijkstra С, MPI Также примеры алгоритмов Флойда и Дейкстры есть в лекции учебника Гергеля (см. список материалов). Реализация с OpenMP. При работе с MPI, не забудьте его установить, а также прописать переменные окружения (Environment Variables) Установка на Windows 10 - https://www.microsoft.com/en- us/download/details.aspx?id=57467 Лабораторная работа рассчитана на 2 часа аудиторных занятий и состоит в изучении теоретического материала и получении практических навыков при работе с параллельными алгоритмами на графах. Сдача лабораторной работы заключается в ответах на контрольные вопросы и выполнении заданий по алгоритмам на графах. Содержание отчета (в электронном виде): 1. Название и цель работы 2. Ответы на контрольные вопросы 24 3. Результаты выполненных заданий. Задания к лабораторной работе: Таблица 1 1) Провести эксперимент с решением задачи по поиску наикратчайшего пути в графе в системе ПараЛаб. Топология, задача и количество вершин представлены в таблице 1. Результаты эксперимента представьте в виде таблицы или графика. 2) Написать программу с реализацией одного из параллельного алгоритма на графах. Алгоритм представлен по варианту в таблице Результат представьте в виде скриншота. Контрольные вопросы: 1. Приведите определение графа. Какие основные способы используются для задания (хранения) графов? 2. В чем состоит задача поиска всех кратчайших путей? 3. Приведите общую схему алгоритма Флойда. Какова временная сложность алгоритма (О-нотация)? 4. В чем состоит способ распараллеливания алгоритма Флойда? 5. В чем заключается задача нахождения минимального охватывающего дерева? Приведите пример использования задачи на практике. 6. Приведите общую схему алгоритма Прима. Какова временная сложность алгоритма (О-нотация)? 7. В чем состоит способ распараллеливания алгоритма Прима? Paralab Программирование Вариант Топология Задача Кол- во узлов Количество вершин графа Алгоритм 1 Полный граф Алгоритм Дейкстры 5 От 8 до 20 (Шаг 4, т.е 4 эксперимента: 8- 12-16-20) Алгоритм Дейкстры 2 3 8 Алгоритм Прима 4 5 16 Алгоритм Флойда- Уоршелла 6 Решетка Алгоритм Флойда 7 9 8 9 9 Поиск в ширину 10 25 Лабораторной работы №7 Тема: Параллельный метод решения дифференциальных уравнений в частных производных Цель работы: Ознакомиться с последовательным и параллельным методом решения дифференциальных уравнений в частных производных. Теоретические основы Дифференциальные уравнения в частных производных представляют собой широко применяемый математический аппарат при разработке моделей в самых разных областях науки и техники. В качестве примера рассмотрим проблему численного решения задачи Дирихле для уравнения Пуассона, определяемую как задачу нахождения функции u(x,y), удовлетворяющей в области определения D уравнению: где 𝐷 0 −граница области D. Подобная модель может быть использована для описания установившегося течения жидкости, стационарных тепловых полей, процессов теплопередачи с внутренними источниками тепла и деформации упругих пластин и др. Далее в качестве области задания D будет использоваться единичный квадрат. Одним из наиболее распространенных подходов численного решения дифференциальных уравнений является метод конечных разностей (метод сеток). Следуя этому подходу, область решения D представляется в виде дискретного (как правило, равномерного) набора (сетки) точек. Область D может быть задана в виде 26 где величина N задает количество узлов по каждой из координат области D. На рисунке 1 представлена эта дискретная сетка. Рисунок 1 – Прямоугольная сетка области D (тёмные точки – внутренние узлы) Если обозначить при подобном дискретном представлении аппроксимацию функции u(x,y) в точках (𝑥 𝑖 , 𝑦 𝑖 ) через 𝑢 𝑖𝑗 , то уравнение Пуассона можно представить в конечно-разностной форме: Выведем из этой формулы 𝑢 𝑖𝑗 : Данный результат служит основой для построения различных итерационных схем решения задачи Дирихле, в которых в начале вычислений формируется некоторое приближение для значений 𝑢 𝑖𝑗 , а затем эти значения последовательно уточняются в соответствии с приведенным соотношением. Метод Гаусса-Зейделя для проведения итераций уточнения использует правило 27 Выполнение итераций происходит до тех пор, пока изменения значений 𝑢 𝑖𝑗 не станет меньше некоторой величины (требуемой точности вычислений). Параллельное выполнение алгоритма решения дифференциальных уравнений в частных производных Параллельного выполнения можно добиться путём разбиения всей сетки на полосы, в каждой из которых процессор будет усреднять значение искомой функции, при этом важным моментом является синхронизация нахождения полученной точности. Лабораторная работа рассчитана на 1 час аудиторных занятий и состоит в изучении теоретического материала и получении практических навыков решения дифференциальных уравнений в частных производных и в работе с параллельными вычислениями в программной системе ПараЛаб. Сдача лабораторной работы заключается в ответах на контрольные вопросы и выполнении заданий по решению дифференциальных уравнений в частных производных. Содержание отчета (в электронном виде): 2. Название и цель работы. 3. Результаты проведенных экспериментов. 4. Ответы на контрольные вопросы. Задания к лабораторной работе №8: 1. Создать в системе ПараЛаб новое окно вычислительного эксперимента, назвать его «Лабораторная работа 8». 2. Провести серию экспериментов «Решение дифференциальных уравнений» методом Гаусса-Зейделя в соответствии с исходными данными, представленными в индивидуальном варианте из следующей таблицы: № вар иан та Разме рност ь матри цы Топология Граничные условия Наибольшее количество итераций Размер сетки Точность вычислений 1 100 Решетка Нулевые 200 50 0.1 2 200 Гиперкуб Дуга 200 100 0.01 3 300 Полный граф Случайные 300 50 0.001 4 400 Решетка Нулевые 300 100 0.1 5 500 Гиперкуб Дуга 400 60 0.01 6 600 Полный граф Случайные 400 80 0.001 28 7 900 Решетка Нулевые 500 60 0.1 8 1000 Гиперкуб Дуга 500 80 0.01 9 3000 Полный граф Случайные 600 60 0.001 10 5000 Решетка Нулевые 600 80 0.1 Результаты представьте в виде таблицы. 3. Написать программу параллельного решения дифференциального уравнения на С++ с параметрами из таблицы ниже, результат предоставить в виде скриншота запущенной программы. № вар иан та Граница g Функция f Граничное значение сетки Размерность сетки/количество процессоров Точность вычислений 1 0 ≤ 𝑥, 𝑦 ≤ 10 𝑓(𝑥, 𝑦) = 𝑥 2 − √𝑥𝑦 50 6 0.1 2 45 7 3 40 9 4 35 10 0.01 5 30 12 6 0 ≤ 𝑥, 𝑦 ≤ 1 𝑓(𝑥, 𝑦) = 36sin(𝑥 − 𝑦) 36 14 7 36 16 8 36 18 0.001 9 18 20 10 18 22 В качестве примера ниже представлен код для функции 𝑓(𝑥, 𝑦) = 100 sin(𝑥) sin(𝑦) + 50cos(𝑥 + 𝑦), значения сетки - 30, размерности сетки – 9, точности вычислений – 0.001. Скриншот кода представлен на рисунке 2. 29 Рисунок 2 – Скриншот выполнения кода #include #include #include } int main(){ int dimension_size = 4, // размер дискретной сетки без границы actual_size = dimension_size+2; // размер дискретной сетки с границей double upper_bound = 1.0, // задаём верхнюю границу eps = 0.001;// задаём точность вычислений double *field = new double[actual_size*actual_size]; double *function = new double[actual_size*actual_size]; omp_set_num_threads(dimension_size); // устанавливаем количество потоков, равное function_fill(function, &function_task, actual_size,upper_bound); // заполняем матрицу значениями функции f boundary_fill(field, actual_size);// заполняем матрицу значениями границы g printf("Дискретная сетка функции u:"); print_matrix(field, actual_size); // вывод значений функции u printf("Дискретная сетка функции f:"); print_matrix(function, actual_size); // вывод значений функции f solve_diff_equation(field,function,dimension_size,upper_bound,eps); // находим решение printf("Результат:"); print_matrix(field, actual_size); // выводим вычисленные значения функции u // очищение памяти delete[] field; delete[] function; } 30 //заполнение матрицы значениями функции void function_fill(double*&function_array,double (*function)(double, double), const int actual_size, const double upper_bound){ double h = upper_bound / (actual_size-1); for(int x = 0;x //вывод матрицы void print_matrix(double*&matrix, const int size){ printf("\n"); for(int i = 0;i } //заполнение матрицы граничными значениями void boundary_fill(double*&field, const int actual_size){ for(int i = 0;i } //решение дифференциального уравнения void solve_diff_equation(double* &u, const double* const &f, const int n, const double upper_bound, double eps = 0.01){ int i,j, actual_size = n + 2; double temp, dmax, // максимальная разность между значениями текущей и предыдущей итерации dm, // максимальная разность между значениями текущей и предыдущей итерации одного потока d, // переменная, используящаяся для определения разности значений текущей и предыдущей итерации h = upper_bound/(n+1); // шаг сетки temp = dmax = dm = d = 0.0; omp_lock_t dmax_lock; 31 omp_init_lock (&dmax_lock); do { printf("Начало новой итерации\n"); dmax = 0; //максимальное изменение значений u #pragma omp parallel for shared(u,n,dmax) \ private(i,j,temp,d,dm) for ( i=1; i %d\n", omp_get_thread_num() + 1, i); for ( j=1; j %1$d вычисляет значение u[%2$d,%3$d], оно равно 0.25(u[%4$d,%3$d]+u[%5$d,%3$d]+u[%2$d,%6$d]+u[%2$d,%7$d]- %8$.2f*f[%2$d,%3$d]) = %9$.2f\n", omp_get_thread_num() + 1, i, j,i-1,i+1,j-1,j+1,h*h, u[i*actual_size + j]); if(dm < d) dm = d; } omp_set_lock(&dmax_lock); if ( dmax < d ) dmax = d; omp_unset_lock(&dmax_lock); } // конец параллельной области } while ( dmax > eps ); } Контрольные вопросы 1. Как определяется задача Дирихле для уравнения Пуассона? 2. Опишите процедуру решения дифференциальных уравнений. 3. Какие граничные условия можно задать в программной системе Paralab? Список литературы 1. ЭУР КарГТУ «Технологии высокоскоростных вычислений», 2019 2. В.Гергель. Высокопроизводительные вычисления для многоядерных 32 многопроцессорных систем. Учебник, – Нижний Новгород; Изд-во ННГУ им. Н.И.Лобачевского, 2011 3. Жалнин Р.В. и.др. Основы параллельного программирования с использованием технологий MPI и OpenMP– Саранск: Изд-во СВМО, 2013. 4. Марк Лутц. Программирование на Python. Тома 1 и 2, 4-е издание. – Пер. с англ. – СПб.: Символ-Плюс, 2011. – 992 с |