«Будущее принадлежит параллельным вычислениям». MaksSun
Введение
Золотые времена подошли к концу, когда разработчикам можно было ничего не делать, а программное обеспечение работало с каждым годом все быстрее.
Распараллеливание на уровне данных. Принцип "Разделяй и властвуй".
Алгоритмы последовательных сортировок в прямом виде достаточно сложены для распараллеливания. Поэтому прибегают к стратегии «разделяй и властвуй».
Принцип «разделяй и властвуй» является одной из фундаментальных стратегий в разработке параллельных алгоритмов. Он заключается в разбиении задачи на более мелкие подзадачи, решение которых происходит независимо, а затем объединении результатов этих подзадач для получения окончательного результата.
Принцип «разделяй и властвуй» широко применяется в параллельных вычислениях, чтобы увеличить производительность и эффективность выполнения задач. Он основан на идее, что сложную задачу можно эффективно решить, разбив ее на нескол��ко более простых подзадач, которые могут быть выполнены параллельно.
Процесс параллельного распараллеливания «разделяй и властвуй» включает следующие шаги.
Разделение. Исходная задача разбивается на несколько меньших и независимых подзадач. Это может быть сделано путем разделения данных, декомпозиции пространства поиска или другими методами, в зависимости от конкретной задачи.
Властвование. Каждая подзадача решается независимо и параллельно. Каждая подзадача может быть выполнена на своем собственном процессоре, ядре или узле в вычислительном кластере.
Объединение. Результаты выполнения подзадач объединяются для получения окончательного результата. Этот шаг может включать слияние данных, комбинирование результатов или другие операции, в зависимости от характера задачи.
Принцип «разделяй и властвуй» позволяет распараллелить задачи, которые имеют хорошо определенную структуру и могут быть разбиты на независимые подзадачи. Он обеспечивает возможность эффективного использования параллельных вычислительных ресурсов и ускоряет выполнение задач, особенно для больших объемов данных или вычислительно сложных алгоритмов.
Суть метода "Разделяй и властвуй"
Программная реализация
Этап 1
Самый быстрый алгоритм (который я знаю) сортировки является "Быстрая сортировка" используем его для локальной сортировки.
// Функция для разделения массива на подмассивы с помощью опорного элемента template <class vec, class typ> typ partition(vec& arr, typ low, typ high) { using VectorType = typename std::remove_reference<decltype(arr)>::type::value_type; VectorType pivot = arr[high]; // Выбираем последний элемент в качестве опорного typ i = low - 1; // Индекс меньшего элемента for (typ j = low; j <= high - 1; ++j) { // Если текущий элемент меньше или равен опорному if (arr[j] <= pivot) { ++i; // Увеличиваем индекс меньшего элемента std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1; } // Рекурсивная функция для выполнения быстрой сортировки template <class vec, class typ> void quickSort(vec& arr, typ low, typ high) { if (low < high) { // Индекс опорного элемента после разделения typ pivotIndex = partition<vec, typ>(arr, low, high); // Рекурсивно сортируем элементы до и после опорного элемента quickSort<vec, typ>(arr, low, pivotIndex - 1); quickSort<vec, typ>(arr, pivotIndex + 1, high); } }
Этап 2
Для распараллелив��ния используем потоки (std::thread).
// Функция разделяй и властвуй для быстрой сортировки с использованием потоков template <class vec, class typ> void parallelDivideAndConquerMergeSort(vec& array) { typ size = array.size(); typ numThreads = std::thread::hardware_concurrency(); typ chunkSize = size / numThreads; std::vector<std::thread> threads; for (typ i = 0; i < numThreads; ++i) { typ start = i * chunkSize; typ end = (i == numThreads - 1) ? size - 1 : start + chunkSize - 1; threads.emplace_back(quickSort<vec, typ>, std::ref(array), start, end); } for (auto& thread : threads) { thread.join(); } typ step = chunkSize; while (step < size) { for (typ i = 0; i < size - step; i += 2 * step) { typ left = i; typ mid = i + step - 1; typ right = std::min<typ>(i + 2 * step - 1, size - 1); merge<vec, typ>(array, left, mid, right); } step *= 2; } }
Этап 3
Функция main
int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251); for (size_t i = 1; i <= 10; ++i) { size_t size_vector = i * (size_t)1e7; std::vector<int> arr(size_vector); std::iota(arr.begin(), arr.end(), 0); std::mt19937_64 urng{ 121216 }; std::shuffle(arr.begin(), arr.end(), urng); auto start = std::chrono::steady_clock::now(); //quickSort(arr, (size_t) 0, size_vector); parallelDivideAndConquerMergeSort<std::vector<int>, long long>(arr); auto end = std::chrono::steady_clock::now(); std::cout << "Время выполнения: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " миллисекунд" << std::endl; if (std::is_sorted(arr.begin(), arr.end())) std::cout << "Массив отсортирован"; else std::cout << "Не отсортирован массив"; std::cout << std::endl; } return 1; }
Вычислительные эксперименты
Вычисления проводились на вычислительной системе №1 (ВС №1): персональном компьютере с шестиядерным процессором AMD Ryzen 5 PRO 4400 Ггц с Radeon Graphics 3.70 GHz, 32 Гб оперативной памяти, операционная система Windows 10x64, SSD 128 Гб.
Время выполнения последовательного алгоритма Быстрой сортировки.
В таблице 1 показаны результаты последовательной быстрой сортировки (Quick sort) принципом «разделяй и властвуй», полученные на вычислительной системе № 1 (6 ядер) с использованием технологии потоков (std::thread).
В таблице 2 показаны результаты параллельной быстрой сортировки (Quick sort) принципом «разделяй и властвуй», полученные на вычислительной системе №1 (6 ядер) с использованием технологии потоков (std::thread).
Вывод
Ускорение достигало до 5 раз в��лючительно.
Весь код
#include <iostream> #include <vector> #include <random> #include <numeric> #include <chrono> #include <thread> #include <Windows.h> // Функция для разделения массива на подмассивы с помощью опорного элемента template <class vec, class typ> typ partition(vec& arr, typ low, typ high) { using VectorType = typename std::remove_reference<decltype(arr)>::type::value_type; VectorType pivot = arr[high]; // Выбираем последний элемент в качестве опорного typ i = low - 1; // Индекс меньшего элемента for (typ j = low; j <= high - 1; ++j) { // Если текущий элемент меньше или равен опорному if (arr[j] <= pivot) { ++i; // Увеличиваем индекс меньшего элемента std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1; } // Рекурсивная функция для выполнения быстрой сортировки template <class vec, class typ> void quickSort(vec& arr, typ low, typ high) { if (low < high) { // Индекс опорного элемента после разделения typ pivotIndex = partition<vec, typ>(arr, low, high); // Рекурсивно сортируем элементы до и после опорного элемента quickSort<vec, typ>(arr, low, pivotIndex - 1); quickSort<vec, typ>(arr, pivotIndex + 1, high); } } // Функция разделяй и властвуй для сортировки слиянием с использованием потоков template <class vec, class typ> void parallelDivideAndConquerMergeSort(vec& array) { typ size = array.size(); typ numThreads = std::thread::hardware_concurrency(); typ chunkSize = size / numThreads; std::vector<std::thread> threads; for (typ i = 0; i < numThreads; ++i) { typ start = i * chunkSize; typ end = (i == numThreads - 1) ? size - 1 : start + chunkSize - 1; threads.emplace_back(quickSort<vec, typ>, std::ref(array), start, end); } for (auto& thread : threads) { thread.join(); } typ step = chunkSize; while (step < size) { for (typ i = 0; i < size - step; i += 2 * step) { typ left = i; typ mid = i + step; typ right = std::min<typ>(i + 2 * step, size); std::inplace_merge(array.begin() + left, array.begin() + mid, array.begin() + right); } step *= 2; } } int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251); for (size_t i = 1; i <= 10; ++i) { size_t size_vector = i * (size_t)1e7; std::vector<int> arr(size_vector); std::iota(arr.begin(), arr.end(), 0); std::mt19937_64 urng{ 121216 }; std::shuffle(arr.begin(), arr.end(), urng); auto start = std::chrono::steady_clock::now(); //quickSort(arr, (size_t) 0, size_vector); parallelDivideAndConquerMergeSort<std::vector<int>, long long>(arr); auto end = std::chrono::steady_clock::now(); std::cout << "Время выполнения: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " миллисекунд" << std::endl; if (std::is_sorted(arr.begin(), arr.end())) std::cout << "Массив отсортирован"; else std::cout << "Не отсортирован массив"; std::cout << std::endl; } return 0; }
