Главная страница
Навигация по странице:

  • ОТЧЕТ ПО ПРАКТИЧЕСКОЙ РАБОТЕ № 2 по дисциплине

  • Количество потоков Время выполнения ( мс ) Ускорение

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


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









    МИНОБРНАУКИ РОССИИ

    Федеральное государственное бюджетное образовательное учреждение

    высшего образования

    «МИРЭА Российский технологический университет»

    РТУ МИРЭА

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


    ОТЧЕТ ПО ПРАКТИЧЕСКОЙ РАБОТЕ 2

    по дисциплине

    «Параллельное программирование»
    Тема: «Параллельное программирование с использованием основ технологии OpenMP»




    Выполнил студент группы ИКБО-07-18





    Еременко И.А.


    Принял преподаватель



    Филатов А.С.




    Лабораторная работа выполнена

    «__»_______202__ г.


    (подпись студента)











    «Зачтено»


    «__»_______202__ г.


    (подпись руководителя)


    Москва 2021
    1. Цель работы


    • Отработка принципов распараллеливания программ;

    • Реализация простейшей многопоточной программы;

    • Анализ эффективности параллельной программы по сравнению с последовательной программой.
    1. Постановка задачи


    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 Интерфейс программы
    1. Тестирование


    Для тестового прогона программы пользователь вручную заполняет двумерный массив из 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. На малом кол-ве данных распараллеливание не ускоряет работу алгоритма.
    1. Вывод


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

    1. Научился программировать параллельные циклы средствами OpenMP;

    2. Научился рассчитывать показатели эффективности параллельных программ.

    3. Проанализировал полученные данные и сделал выводы
    1. Исходный код программы



    #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;

    }

    }
    }

    }


    написать администратору сайта