«Будущее принадлежит параллельным вычислениям». 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;
}
