ДЗ Лабораторная работа №4 "Знакомство с параллелизацией"#
Warning
За задание можно получить до 5 баллов, соблюдая следующие условия:
- Написано на C++ ( + 2 балла)
- Задание зачтено ( +3 балла)
В отчете должно быть указано следующие:
1. Титульный лист, где указаны ФИО преподавателя, номер задания, номер варианта
2. Формулировка задания
3. Ссылка на github-репозиторий с работающим кодом
4. В конце работы приводятся реальные замеры на вашем ЭВМ в виде таблицы 1 и графика
5. Сопоставить график из работа 3 и график из работы 4
6. Рассчитать коэффициент ускорения. Результаты внести в таблицу 2. (см. Коэффициент ускорения для многопоточной быстрой сортировки)
7. Сделать выводы относительно ускорения. Праивльно ли вами был подобран N?
7. Для реализации С++ (реже python) если будет использован mutex, дать описание что это такое и как он работает. Также вы можете реализовать используя Omp (OpenMP), но в таком случае от вас также требуется описание работы. В своей параллельной схеме я не вижу необходимости в использовании вышеуказанных средств, но вдруг кто-то увидит.
Пример таблицы 1 (2,4, 8 потоки, БС - быстрая сортировка, БС_П - быстрая сортировка параллельная)
| Размер массива | БС (сек) | БС_П 2 потока (сек) | БС_П 4 потока (сек) | БС_П 8 потока (сек) |
|---|---|---|---|---|
| 100 | ххх | ххх | ххх | ххх |
| 1000 | ххх | ххх | ххх | ххх |
| 10000 | ххх | ххх | ххх | ххх |
| 20000 | ххх | ххх | ххх | ххх |
| 30000 | ххх | ххх | ххх | ххх |
| 40000 | ххх | ххх | ххх | ххх |
| 50000 | ххх | ххх | ххх | ххх |
Паралельная схема#
- Функция
quicksortреализуется аналогично практике 5, за исключением ввода нового параметраnum_threads- количество потоков - Фиксируется
N- длина массива, если массив большой, то происходит Параллельная обработка подмассивов если достаточно потоков - Если подмассивы достаточно маленькие, сортируем их с помощью стандартной сортировки
Коэффициент ускорения для многопоточной быстрой сортировки#
Для расчёта коэффициента ускорения используем следующую формулу:
Формула для коэффициента ускорения (Speedup):#
Шаги для расчёта коэффициента ускорения:#
- Для каждого теста (для каждого размера массива):
- Найдите время выполнения обычной сортировки (Normal quicksort time).
-
Найдите время выполнения многозадачной сортировки для каждого количества потоков (Multithreaded quicksort time for N threads).
-
Расчитайте коэффициент ускорения для каждого количества потоков:
- Используйте формулу выше, подставив значения для обычной и многозадачной сортировки.
Пример расчёта:#
Для массива из 100 элементов:#
- Время для обычной сортировки: 1.46e-05 секунд.
- Время для многозадачной сортировки с 2 потоками: 7.1e-06 секунд.
- Время для многозадачной сортировки с 4 потоками: 5.4e-06 секунд.
- Время для многозадачной сортировки с 8 потоками: 7.4e-06 секунд.
Коэффициенты ускорения:#
- Для 2 потоков:
- Для 4 потоков:
- Для 8 потоков:
Таблица 2. Коэффициенты ускорения для всех тестов:#
| Размер массива | Время обычной сортировки (с) | Время сортировки с 2 потоками (с) | Время сортировки с 4 потоками (с) | Время сортировки с 8 потоками (с) | Speedup (2 потока) | Speedup (4 потока) | Speedup (8 потока) |
|---|---|---|---|---|---|---|---|
| 100 | 1.46e-05 | 7.1e-06 | 5.4e-06 | 7.4e-06 | 2.06 | 2.70 | 1.97 |
| 1000 | 0.0001802 | 5.37e-05 | 6.45e-05 | 5.23e-05 | 3.35 | 2.79 | 3.44 |
| 10000 | 0.0032846 | 0.0009314 | 0.0008785 | 0.0008313 | 3.53 | 3.74 | 3.95 |
| 20000 | 0.0053028 | 0.0018631 | 0.0018122 | 0.0018589 | 2.84 | 2.92 | 2.85 |
| 30000 | 0.0077676 | 0.0052955 | 0.0024391 | 0.0023903 | 1.47 | 3.18 | 3.24 |
| 40000 | 0.0104027 | 0.0031628 | 0.0027341 | 0.0029274 | 3.29 | 3.81 | 3.55 |
| 50000 | 0.0132361 | 0.0035579 | 0.0034121 | 0.003922 | 3.73 | 3.88 | 3.37 |
Коэффициент ускорения позволяет оценить, насколько быстрее работает многозадачная версия алгоритма по сравнению с обычной версией. Как видно из таблицы, ускорение значительно варьируется в зависимости от размера массива и числа потоков. Например, для массива из 1000 элементов скорость увеличивается с 3.35 для 2 потоков до 3.44 для 8 потоков, но для более крупных массивов ускорение может снижаться из-за накладных расходов на создание и управление потоками.
Примечание : данная таблица посчитана для C++. на Python результаты могут быть иными. Подозреваю, что Speedup у вас будет в таком случае напротив меньше 1.