За задание можно получить до 5 баллов, соблюдая следующие условия:
- Написано на C++ ( + 2 балла)
- Задание зачтено ( +3 балла)
В отчете должно быть указано следующие:
- Титульный лист, где указаны ФИО преподавателя, номер задания, номер варианта
- Формулировка задания
- Ссылка на github-репозиторий с работающим кодом
- В конце работы приводятся реальные замеры на вашем ЭВМ в виде таблицы 1 и графика
- Сопоставить график из работа 3 и график из работы 4
- Рассчитать коэффициент ускорения. Результаты внести в таблицу 2. (см. Коэффициент ускорения для многопоточной быстрой сортировки)
- Сделать выводы относительно ускорения. Праивльно ли вами был подобран N?
- Для реализации С++ (реже python) если будет использован
mutex, дать описание что это такое и как он работает. Также вы можете реализовать используяOmp(OpenMP), но в таком случае от вас также требуется описание работы. В своей параллельной схеме я не вижу необходимости в использовании вышеуказанных средств, но вдруг кто-то увидит.
Пример таблицы 1 (2,4, 8 потоки, БС - быстрая сортировка, БС_П - быстрая сортировка параллельная)
| Размер массива | БС (сек) | БС_П 2 потока (сек) | БС_П 4 потока (сек) | БС_П 8 потока (сек) |
|---|---|---|---|---|
| 100 | ххх | ххх | ххх | ххх |
| 1000 | ххх | ххх | ххх | ххх |
| 10000 | ххх | ххх | ххх | ххх |
| 20000 | ххх | ххх | ххх | ххх |
| 30000 | ххх | ххх | ххх | ххх |
| 40000 | ххх | ххх | ххх | ххх |
| 50000 | ххх | ххх | ххх | ххх |
1 Паралельная схема
- Функция
quicksortреализуется аналогично практике 6, за исключением ввода нового параметраnum_threads- количество потоков - Фиксируется
N- длина массива, если массив большой, то происходит Параллельная обработка подмассивов если достаточно потоков - Если подмассивы достаточно маленькие, сортируем их с помощью стандартной сортировки
2 Коэффициент ускорения для многопоточной быстрой сортировки
Для расчёта коэффициента ускорения используем следующую формулу:
3 Формула для коэффициента ускорения (Speedup):
4 Шаги для расчёта коэффициента ускорения:
- Для каждого теста (для каждого размера массива):
- Найдите время выполнения обычной сортировки (Normal quicksort time).
- Найдите время выполнения многозадачной сортировки для каждого количества потоков (Multithreaded quicksort time for N threads).
- Расчитайте коэффициент ускорения для каждого количества потоков:
- Используйте формулу выше, подставив значения для обычной и многозадачной сортировки.
5 Пример расчёта:
Для массива из 100 элементов:
- Время для обычной сортировки: 1.46e-05 секунд.
- Время для многозадачной сортировки с 2 потоками: 7.1e-06 секунд.
- Время для многозадачной сортировки с 4 потоками: 5.4e-06 секунд.
- Время для многозадачной сортировки с 8 потоками: 7.4e-06 секунд.
Коэффициенты ускорения:
- Для 2 потоков:
Speedup2 = (1.46e-05 / 7.1e-06) ≈ 2.06
- Для 4 потоков:
Speedup4 = (1.46e-05 / 5.4e-06) ≈ 2.70
- Для 8 потоков:
Speedup8 = (1.46e-05 / 7.4e-06) ≈ 1.97
6 Таблица 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.