АНАЛИЗ СОВРЕМЕННЫХ ИНСТРУМЕНТАЛЬНЫХ ЯЗЫКОВЫХ СРЕДСТВ ДЛЯ ПОИСКА И ПОСТРОЕНИЯ ЭФФЕКТИВНЫХ АСИНХРОННЫХ АЛГОРИТМОВ

ВВЕДЕНИЕ. Современные вычислительные системы включают несколько ядер или процессоров. В их основе лежать сложные и дорогостоящие аппаратные части, такие как L1, L2, L3 уровни кэша, SRAM память.

Но при этом истинная эффективность достигается в правильных методах работы с этими многопоточными средствами. Необходимо учитывать время жизни потока, функционирование кэш линии, ложное разделение кэша (false sharing), стоимость создания потоков - всё это существенно влияет на временную сложность и определяет действительную ценность алгоритма.

Проблемная область. Для точной оценки эффективности необходим в обширный инструментарий и глубокие знания в низкоуровневых механизмах работы. Классические модели, такие как закон Амдала или Густафсона – Барсиса не позволяют с достаточной степенью точности дать оценку времени работы алгоритма. Необходимо учитывать системные вызовы (создание потока, ожидание future), переключение контекста, а также загрузку процессора.

ЦЕЛЬ НАСТОЯЩЕЙ РАБОТЫ. Привести примеры алгоритмов и их асинхронных версий, оценить время работы. Разработать на основании их математическую модели. Реализовать последовательные и параллельные версии алгоритмов, измерить время выполнения для различных размеров данных и числа потоков, сопоставить с теоретическими моделями и сформулировать практические рекомендации.

МАТЕРИАЛ И МЕТОДЫ ИССЛЕДОВАНИЯ. Приведём классические законы, для описания параллельных вычислений:

Закон Амдала (1967) устанавливает предельное ускорение S(p) программы при фиксированном объёме данных:

где α – доля последовательного кода, p – число процессоров. При p→∞ ускорение стремится к 1/α, то есть даже бесконечное количество ядер не может ускорить программу более чем в 1/α раз.

Закон Густафсона (1988) учитывает возможность масштабирования задачи: с ростом числа процессоров увеличивается и размер входных данных. В такой постановке ускорение выражается как:

однако, данные модели полезны для теоретических оценок, для реальных случаев они не учитывают накладные расходы, и время создания потоков.

В языке C++ при использовании std::async с политикой std::launch::async создаётся новый поток для каждой задачи. Даже на современных системах создание потока занимает 1–2 мкс и требует выделения памяти под стек (обычно 1–8 Мбайт). При мелкой задаче затраты на создание потоков превышают выигрыш от параллельного выполнения.

В качестве примера можно рассмотреть стандартные алгоритмы сортировки.

Базовая последовательная сортировка слиянием (Merge Sort) имеет сложность O(n log⁡ n). Её параллельная версия использует рекурсивное разделение массива. Для избежания излишнего дробления задач вводится порог (threshold): если размер подмассива меньше или равен порогу, сортировка выполняется последовательно.

Оптимальное значение порога, при котором эффективен однопоточный алгоритм, лежит между 300 до 2000 элементом, а также зависит от типа данных и архитектуры системы.

Для бинарного поиска создание отдельного потока на каждый рекурсивный вызов нецелесообразно из-за логарифмической сложности. Поэтому лучшим решением было разработать отдельный класс пула потоков, который переиспользует фиксированное число потоков. Задачи помещаются в очередь и распределяются между рабочими потоками. Использование класса распределяет задачи между заданным числом потоков, что снижает накладные расходы на создание потоков по сравнению с вызовом std::async для каждой подзадачи.

Математическая модель алгоритмов представлена в следующем виде

Последовательное время сортировки слиянием:

Параллельное время (приблизительная оценка):

Ускорение:

Для бинарного поиска последовательное время T_seq=⌈log⁡₂n⌉t_comp, параллельное – с разбиением на p сегментов даёт T_par≈γpt_sync+log⁡₂(n/p)t_comp, где γ – эмпирический коэффициент накладных расходов на разбиение (≈ 0,1). При любых входных данных у параллельного бинарного поиска, мы получаем заметное падение эффективности.

РЕЗУЛЬТАТЫ И ОБСУЖДЕНИЕ Эксперименты проводились на процессоре Intel Core i7-12700K (14 потоков, 8 физических ядер), частота 3,6 ГГц, ОС Ubuntu 22.04, компилятор g++ 11.3 с ключами -O3 -march=native. Для каждого размера массива и числа потоков выполнялось 10 запусков, результаты усреднены. Размер массива для сортировки выбран n=150 000.

Таблица 1.

Сравнение ускорения сортировки слиянием

По результатам тестирования можно наблюдать, что реальное ускорение оценивается примерно в 3,06x при максимальном числе потоков. Для закона Амдала теоретические результаты дают оценку 2,52x и 9.45x для Густафсона – Барсиса, результаты имеют значительно отличаются от теоретических оценок. Параллельный бинарный поиск во всех экспериментах показал ускорение < 1, что делает данную реализацию абсолютно неэффективной.

ВЫВОДЫ. Параллельные алгоритмы эффективны далеко не для всех задач и требуют дополнительного анализа и тщательной разработки. Асинхронный алгоритм сортировки слиянием эффективен при размере входных данных размером более 10000 элементов. Максимальное ускорение составило 3,06× против 1,48× в нескольких потоках. Теоретические оценки не являются точным прогнозом стабильности из-за дополнительных накладных расходов и ресурсов. Бинарный поиск не улучшил свои показатели при многопоточной работе.

ПУТИ ДАЛЬНЕЙШЕГО РАЗВИТИЯ. Необходимо провести дополнительный анализ и разработать адаптивный порог переключения (зависящий также от числа потоков и размера кэш-памяти), необходимо учитывать паттерны доступа к кэш-памяти процессора. Изучить и использовать SIMD-инструкций (AVX2) для ускорения последовательного слияния, осуществить переход на более лёгкие средства параллелизма: std::execution::par (C++17) и std::jthread (C++20), а также провести анализ кэш промахов L3 кэша процессора.