параллельный поиск минимального и максимального элементов в двумерном целочисленном массиве с применением технологии openmp. пр2 пп Еременко. Отчет по практической работе 2 по дисциплине Параллельное программирование

• Название: Отчет по практической работе 2 по дисциплине Параллельное программирование
• Анкор: параллельный поиск минимального и максимального элементов в двумерном целочисленном массиве с применением технологии openmp
• Дата: 07.11.2021
• Размер: 375.42 Kb.
• Имя файла: пр2 пп Еременко.docx
• Тип: Отчет; #265171

МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение высшего образования «МИРЭА – Российский технологический университет» РТУ МИРЭА

Институт Информационных технологий
Кафедра Математического обеспечения и стандартизации информационных технологий

ОТЧЕТ ПО ПРАКТИЧЕСКОЙ РАБОТЕ № 2
по дисциплине
«Параллельное программирование» Тема: «Параллельное программирование с использованием основ технологии OpenMP»
Выполнил студент группы ИКБО-07-18	Еременко И.А.
Принял преподаватель	Филатов А.С.

Лабораторная работа выполнена	«__»_______202__ г.	(подпись студента)
«Зачтено»	«__»_______202__ г.	(подпись руководителя)

Москва 2021

1. Цель работы

• 
  Отработка принципов распараллеливания программ;
  
• 
  Реализация простейшей многопоточной программы;
  
• 
  Анализ эффективности параллельной программы по сравнению с последовательной программой.
  

2. Постановка задачи

1. 
   Составить программу, реализующую распараллеленное вычисление, согласно индивидуальному варианту.
   
2. 
   Провести ручное тестирование программы на небольшом объеме входных данных. Результаты тестирования в виде скриншотов экранов включить в отчет по выполненной работе.
   
3. 
   Провести контрольные прогоны программы для нескольких разных значений параметра n и установленных количествах потоков p = 1, 2, 4, 8, 16, 32 и 64. В индивидуальном варианте задания приведены рекомендуемые параметры n. Значения параметра nможно переопределить самостоятельно таким образом, чтобы уменьшить относительную погрешность результатов. Результаты прогонов в виде скриншотов экранов включить в отчет по выполненной работе.
   
4. 
   Полученные результаты свести в сводную таблицу.
   
5. 
   Вычислить показатели ускорения, эффективности и стоимости параллельной реализации программы.
   
6. 
   Построить графики времени выполнения, изменения ускорения, эффективности и стоимости параллельной реализации в зависимости от параметра p.
   
7. 
   Провести анализ полученных результатов. Сделать выводы о проделанной работе, основанные на полученных результатах.
   
8. 
   Оформить отчет с подробным описанием разработанной программы, принципов программной реализации распараллеленной обработки данных, описанием текста исходного кода и проведенного тестирования программы.
   

Вариант №9. Условие задания:

Составить программу, реализующую последовательный и параллельный поиск минимального и максимального элементов в двумерном целочисленном массиве A[n,n]. Провести тестирование программы на массиве размером n = 5, сформированном вводом с клавиатуры. Рабочий массив А сформировать, используя генератор псевдослучайных чисел. Провести контрольные прогоны программы для размеров n = 100, 500, 1000, 1500, 2000.

Решение

Для нахождения минимального и максимального значения в двумерном массиве необходим вложенный цикл, который будет проходить по каждому элементу массива и путем сравнения с переменными находить требуемые величины. Этот вложенный цикл должен быть распараллелен.

Для создания параллельных циклов используется директива #pragma omp for. Она создает в параллельной области параллельный цикл и распределяет итерации цикла по потокам. Точкой синхронизации потоков (барьером) по умолчанию является конец цикла. Опция private устанавливает локальные переменные каждому потоку на все время его существования.

Для анализа эффективности параллельной программы необходимо ознакомиться с показателями эффективности параллельных программ.

Показатели эффективности параллельного алгоритма

• 
  Ускорение;
  
• 
  Эффективность;
  
• 
  Стоимость.
  

Ускорение (speedup), получаемое при использовании параллельного алгоритма для p потоков, по сравнению с последовательным вариантом выполнения вычислений определяется величиной



– это отношение времени последовательного выполнения программы к времени параллельного выполнения программы Величина n применяется для параметризации вычислительной сложности решаемой задачи и может пониматься, к примеру, как размер входных данных задачи.

Эффективность (efficiency) использования параллельным алгоритмом ресурсов компьютера (процессоров, ядер или потоков) при решении задачи определяется соотношением



Величина эффективности определяет среднюю долю времени выполнения алгоритма, в течение которой процессоры (ядра или потоки) реально задействованы для решения задачи. Из приведенных соотношений можно показать, что в наилучшем случае и .

При выборе надлежащего параллельного способа решения задачи может оказаться полезной оценка стоимости (cost) вычислений, определяемой как произведение времени параллельного решения задачи и числа используемых процессоров



В связи с этим можно определить понятие стоимостно-оптимального (cost-optimal) параллельного алгоритма как метода, стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма.

Функция parallel_sort реализует нахождение максимального и минимального значения в двумерном массиве. Значение min инициализируется 30000, max- 0. Для прохождения по всем элементам двумерного массива необходим основной и вложенный цикл. Вложенный цикл проходится по всем элементам массива. Именно этот цикл и будет распараллеливаться. В этом цикле происходит сравнение актуального минимального и максимального значения с каждым элементом массива, при удовлетворении операции сравнения происходит присвоение минимальной или максимальной переменной значения элемента массива. Алгоритм завершает свою работу при сравнении со всеми элементами массива.

// находжение минимального и максимального значения в двумерном массиве void parall_min_max(std::vector> matrix, int n, int countThreads) { int i, j; int min=30000; int max = 0; double start_time, end_time; int ct = countThreads; start_time = clock(); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (matrix[i][j] > max) { max = matrix[i][j]; } if (matrix[i][j] < min) { min = matrix[i][j]; } } } end_time = clock(); double time_consistent = end_time - start_time; start_time = clock(); omp_set_num_threads(ct); #pragma omp parallel { #pragma omp for private(i, j) for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (matrix[i][j] > max) { max = matrix[i][j]; } if (matrix[i][j] < min) { min = matrix[i][j]; } } } } end_time = clock(); std::cout << "Размерность матрицы: " << n <<"x"<< n << " Потоки: " < std::cout << "Максимум: " < double speedup = (end_time - start_time) / time_consistent; std::cout << "Ускорение: " << speedup << " Эффективность: "<< speedup/ct << " Стоимость " << ct*(end_time - start_time) << " мс" << std::endl; }

Пользователю на выбор предлагается два варианта: заполнение массива вручную для проверки правильности алгоритма и заполнение массива при помощи генератора случайных чисел. Если пользователь выбирает первый вариант, то ему необходимо ввести 25 элементов массива. Для автоматического теста программа выведет размерность массива, количество потоков, время, затраченное на поиск минимального и максимального значений, минимальное и максимальное значение и данные для аналитики: стоимость, ускорение, эффективность. Для ручного теста будут выведены время, затраченное на сортировку, изначальный массив, максимальное и минимальное значение.



Рис. 1 Интерфейс программы

3. Тестирование

Для тестового прогона программы пользователь вручную заполняет двумерный массив из 25 элементов.



Рис. 2 Тестовый прогон

Рабочий прогон программы проводится для массивов размерностью nxn, где n = 100, 500, 1000, 1500 и 2000. Они заполняются случайными целыми числами в диапазоне от 0 до 30000. К каждому из них применяется поиск минимального и максимального значения с количеством потоков: 1, 2, 4, 8, 16, 32, 64. Для каждого массива с разными размерностями и поточностью высчитываются и выводятся: размерность массива, количество потоков, время, затраченное на поиск минимального и максимального значений, минимальное и максимальное значение и данные для аналитики: стоимость, ускорение, эффективность.



Рис. 3 Рабочий прогон

На основе полученных данных заполним таблицы и построим графики для различных n.

Таблица 1. Рабочий прогон (n = 100)

Количество потоков	Время выполнения (мс)	Ускорение	Эффективность	Стоимость
1	2	-	-	-
2	3	0,666	0,333	6
4	4	0,5	0,013	16
8	7	0,143	0,017	56
16	10	0,2	0,013	160
32	26	0,078	0,002	832
64	49	0,04	0,001	3136

Рис. 4 График времени выполнения от количества потоков (n = 100)

Рис. 5 График ускорения от количества потоков (n = 100)

Рис. 6 График эффективности от количества потоков (n = 100)

Рис. 7 График стоимости от количества потоков (n = 100)

Таблица 2. Рабочий прогон (n = 500)

Количество потоков	Время выполнения (мс)	Ускорение	Эффективность	Стоимость
1	48	-	-	-
2	20	1.5	0,751	40
4	15	3,267	0,816	60
8	17	2,941	0,368	136
16	22	2,864	0,179	352
32	32	1,593	0,049	1024
64	54	0,963	0,015	3456

Рис. 8 График времени выполнения от количества потоков (n = 500)

Рис. 9 График ускорения от количества потоков (n = 500)

Рис. 10 График эффективности от количества потоков (n = 500)

Рис. 11 График стоимости от количества потоков (n = 500)

Таблица 3. Рабочий прогон (n = 1000)

Количество потоков	Время выполнения (мс)	Ускорение	Эффективность	Стоимость
1	172	-	-	-
2	91	1,429	0,714	182
4	49	3,449	0,862	196
8	56	2,768	0,346	448
16	51	3,431	0,215	816
32	57	2,859	0,089	1824
64	78	2,372	0,037	4992

Рис. 12 График времени выполнения от количества потоков (n = 1000)

Рис. 13 График ускорения от количества потоков (n = 1000)

Рис. 14 График эффективности от количества потоков (n = 1000)



Таблица 4. Рабочий прогон (n = 1500)

Количество потоков	Время выполнения (мс)	Ускорение	Эффективность	Стоимость
1	365	-	-	-
2	205	1,571	0,785	410
4	114	3,14	0,785	456
8	95	3,547	0,443	760
16	105	3,028	0,189	1680
32	102	3,392	0,106	3264
64	123	3,163	0,049	7872

Рис. 15 График времени выполнения от количества потоков (n = 1500)

Рис. Рис. 16 График ускорения от количества потоков (n = 1500)

Рис. 17 График эффективности от количества потоков (n = 1500)

Рис. 18 График стоимости от количества потоков (n = 1500)

Таблица 5. Рабочий прогон (n = 2000)

Количество потоков	Время выполнения (мс)	Ускорение	Эффективность	Стоимость
1	592	-	-	-
2	293	1,911	0,956	586
4	192	3,156	0,789	768
8	117	5,572	0,697	936
16	131	4,26	0,266	2096
32	159	3,365	0,105	5088
64	163	3,405	0,053	10432

Рис. 19 График времени выполнения от количества потоков (n = 2000)

Рис. 20 График ускорения от количества потоков (n = 2000)

Рис. 21 График эффективности от количества потоков (n = 2000)

Рис. 22 График стоимости от количества потоков (n = 2000)

Из результатов выполнения программы видно:

1. 
   При росте числа потоков снижается прирост ускорения.
   
2. 
   Начиная с некоторого количества потоков, прирост ускорения становится отрицательным, и программа начинает работать медленнее, чем с меньшим количеством потоков. При этом, чем меньше n, тем меньшее количество потоков для этого необходимо.
   
3. 
   На малом кол-ве данных распараллеливание не ускоряет работу алгоритма.
   

4. Вывод

В результате выполнения работы я:

1. 
   Научился программировать параллельные циклы средствами OpenMP;
   
2. 
   Научился рассчитывать показатели эффективности параллельных программ.
   
3. 
   Проанализировал полученные данные и сделал выводы
   

5. Исходный код программы

#include #include #include #include using namespace std; //функция рассчета с ручным заполнением void min_max_matrix_hands(int n1) { int a[5][5]; int n = n1; int m = n1; int min = 100000; int max = 0; cout << "заполнение вручную: \n"; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) std::cin >> a[i][j]; //a[i][j] = 1 + rand() % 500; clock_t start = clock(); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (a[i][j] > max) { max = a[i][j]; } if (a[i][j] < min) { min = a[i][j]; } } clock_t end = clock(); cout << "\n Минимальное и максимальное значение: " << min << " " << max << "\n"; cout << "\n Время работы в руном режиме: " << end - start << " мс\n"; } //функция заполнения матрицы void fill(std::vector>& matrix, int n) { srand(1); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrix[i][j] = 1 + rand() % 30000; } } } void parall_min_max(std::vector> matrix, int n, int countThreads) { int i, j; int min=30000; int max = 0; double start_time, end_time; int ct = countThreads; start_time = clock(); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (matrix[i][j] > max) { max = matrix[i][j]; } if (matrix[i][j] < min) { min = matrix[i][j]; } } } end_time = clock(); double time_consistent = end_time - start_time; start_time = clock(); omp_set_num_threads(ct); #pragma omp parallel { #pragma omp for private(i, j) for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (matrix[i][j] > max) { max = matrix[i][j]; } if (matrix[i][j] < min) { min = matrix[i][j]; } } } } end_time = clock(); std::cout << "Размерность матрицы: " << n <<"x"<< n << " Потоки: " < std::cout << "Максимум: " < double speedup = (end_time - start_time) / time_consistent; std::cout << "Ускорение: " << speedup << " Эффективность: "<< speedup/ct << " Стоимость " << ct*(end_time - start_time) << " мс" << std::endl; } int main() { setlocale(LC_ALL, "Russian"); std::cout << " Еременко И.А, ИКБО-07 Вариант 9" << std::endl; while (true) { std::cout << "Выберите тип ввода:\n1 - Ручной ввод\n2 - Генератор случайных чисел" << std::endl; int choice; std::cin >> choice; if (choice == 1) { min_max_matrix_hands(5); } if (choice == 2) { int i = 0; int countTheads; int n = 100; std::vector> matrix(n, std::vector(n)); fill(matrix, n); for (countTheads = 1; countTheads < 65; countTheads = countTheads * 2) { parall_min_max(matrix, n, countTheads); } std::cout << std::endl; for (int n = 500; n < 2001; n = n + 500) { std::vector> matrix(n, std::vector(n)); fill(matrix, n); for (countTheads = 1; countTheads < 65; countTheads = countTheads * 2) { parall_min_max(matrix, n, countTheads); } std::cout << std::endl; } } } }