Параллельное программирование

Параллельное программирование – это методология конструирования программ, в которых несколько вычислительных действий выполняются одновременно (конкурентно) на множестве вычислительных ресурсов: ядрах процессора, потоках, графических устройствах, распределённых узлах. В основе лежит формализация одновременности (concurrency) и действительной параллельности (parallelism), учёт зависимостей данных и управление разделяемыми ресурсами. Для подготовки к ЕГЭ тема важна по трём причинам:

• она углубляет понимание алгоритмов и оценок времени выполнения;

• развивает навыки формальной логики и трассировки исполнения (что напрямую помогает в задачах ЕГЭ на исполнителей, алгоритмы, таблицы и блок-схемы);

• учит декомпозиции задач и анализу узких мест – компетенции, проверяемые в заданиях повышенного уровня.

Теоретические основы

Модели параллелизма и архитектуры

• Задачный (task parallelism): независимые задачи выполняются параллельно (шаблон fork–join, pipeline).

• Данновый (data parallelism): одно и то же действие применяется к множеству элементов (векторизация, GPU-ядра, map/reduce).

• Память и взаимодействие:
  

  • Общая память (shared memory): потоки разделяют адресное пространство; требуется синхронизация.

  • Распределённая память (message passing): узлы обмениваются сообщениями; нет общей памяти, но есть коммуникационные задержки.

• Классификация Флинна: SISD, SIMD, MISD (редко), MIMD. Современные CPU–MIMD, GPU – преимущественно SIMD/SIMT.

Основные понятия производительности

• Работа T₁​: суммарное время последовательного исполнения всех операций.

• Длина критического пути / глубина T∞: минимально возможное время при бесконечном числе процессоров (определяется зависимостями).
  

Синхронизация и корректность

• Критическая секция: участок кода, который должен выполняться атомарно.

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

• Состояния ошибок: гонка данных (data race), взаимная блокировка (deadlock), активная блокировка (livelock), голодание (starvation).

Правила безопасности:

1. Защищайте все разделяемые изменяемые данные.

2. Согласовывайте порядок захвата нескольких блокировок (глобальный порядок – противоядие от deadlock).

3. Минимизируйте гранулярность критических секций, но не дробите так, чтобы нарушить атомарность.

4. Отдавайте предпочтение неизменяемым структурам и локальным данным.

5. Избегайте ложного совместного использования (false sharing) – не размещайте часто изменяемые данные разных потоков в одной кэш-линии.

6. Учитывайте модель памяти (последовательная согласованность, happens-before).

Шаблоны и стратегии

• Fork–Join: рекурсивная декомпозиция (параллельная сортировка, умножение матриц, параллельный DFS/BFS).

• Map–Reduce: независимая обработка элементов → редукция (сумма, максимум, гистограмма).

• Pipeline (конвейер): стадии обрабатывают разные части потока данных.

• SPMD: одинаковая программа на всех процессорах с разными индексами данных.

• Планирование: статическое (распределение заранее) и динамическое (work-stealing, очереди задач) – балансировка нагрузки.

Практические принципы (правила проектирования)

1. Декомпозиция: делите задачу на максимально независимые подзадачи; измеряйте уровень параллелизма T1/T∞

2. Гранулярность: соотносите объём работы задачи со стоимостью создания/синхронизации потока/задачи. Мелкие задачи → высокие накладные расходы.

3. Локальность: добивайтесь пространственной и временной локальности доступа в кэш (блоковая обработка, разделение по данным).

4. Синхронизация «по потребности»: блокируйте только то, что необходимо, на минимальный срок.

5. Избегайте точки серилизации: очереди, глобальные счётчики и единственные мьютексы могут «ломать» масштабируемость. Применяйте шардирование/батчинг/lock-free структуры.

6. Нагрузочное тестирование: оценивайте S(p) и E(p) для разных p, ищите колена кривых (diminishing returns).

7. Повторяемость результатов: фиксируйте источники недетерминизма (состояния гонок, неупорядоченные операции ввода-вывода), внедряйте детерминированные редукции.

Связь с подготовкой к ЕГЭ по информатике

Хотя формальные параллельные конструкции в КИМ ЕГЭ встречаются редко, мышление параллелизмом напрямую помогает:

• в задачах на трассировку алгоритмов и исполнителей – анализ зависимостей, построение временных диаграмм, оценка числа итераций;

• в заданиях на оценку сложности – понимание критического пути, узких мест и линейного/нелинейного ускорения;

• при разборе блок-схем – выявление независимых ветвей;

• в работе с таблицами и массивами – мысленная векторизация (операция над всем столбцом/массивом).

Практикуйте: составление диаграмм Ганта для этапов обработки, расчёт ускорения и эффективности, поиск последовательных фрагментов, ограничивающих масштабирование.

Мини-репертуар базовых параллельных алгоритмов

• Параллельная редукция (сумма/максимум): дерево редукции глубины O(log n) при работе O(n).

• Префикс-сумма (scan): upsweep + downsweep или алгоритмы Блека–Шоулза/Хиллеса–Стилла – ключ к параллельным свёрткам, гистограммам и сортировкам поразрядно.

• Параллельная сортировка: mergesort/quick-sort с разделением данных, балансировкой и локальными буферами для уменьшения контендиции.

• Графовые обходы: фронтирный BFS (уровневая параллельность), компрессия фронтира, сокращение конфликтов записи.

• Плотные линалг-ядра: блоковое умножение матриц (локальность кэша, тайлинг, распределение блоков).

Типичные ошибки и их профилактика

• Data race: два потока пишут/читают один объект без синхронизации → используйте мьютексы/атомики, структурируйте владение.

• Deadlock: циклическое ожидание блокировок → глобальный порядок, таймауты, try-lock, двухфазные протоколы.

• Livelock/Starvation: чрезмерные повторы или вытеснение задач → справедливые очереди, квоты, back-off.

• False sharing: независимые переменные в одной кэш-линии → выравнивание/пэддинг, массив «по потокам».

• Чрезмерная гранулярность: слишком много крошечных задач → агрегируйте работу (batch), используйте порог рекурсии.

Пять упражнений (теория + практика для ЕГЭ-мышления)

Упражнение 1. Оценка ускорения и эффективности

Упражнение 2. Трассировка параллельной редукции

Упражнение 3. Анализ зависимостей и теорема Брента

Упражнение 4. Безопасность разделяемых структур

Рассмотрите псевдокод параллельной гистограммы по K корзинам: потоки бегут по разным сегментам массива и делают bin[a[i]]++.
a) Объясните источник гонок данных.
b) Предложите две стратегии устранения: (1) локальные гистограммы + финальная редукция; (2) атомарные инкременты с шардированием корзин.
c) Оцените влияние обеих стратегий на кэш-локальность и масштабируемость при больших K и при малых K.
Связь с ЕГЭ: оформите рассуждение как сравнение алгоритмов с указанием числа обращений и потенциальных «узких мест».

Упражнение 5. Конвейер и балансировка

Имеется трёхстадийный конвейер обработки пакетов:

• S1: предобработка (2 у.е.),

• S2: вычисление признаков (5 у.е.),

• S3: агрегация (3 у.е.).

Пакетов N=20.
a) Постройте диаграмму Ганта и найдите время прогрева/затухания, теоретическую пропускную способность и полное время обработки.
b) Предложите способ балансировки (дублирование узкой стадии, разбиение S2 на два подпотока) и пересчитайте предел пропускной способности.
c) Сформулируйте правило выбора числа экземпляров стадии, минимизирующее суммарное время.
Связь с ЕГЭ: аналогично задачам на процессы/исполнителей – вычисления по таблице времени.

Заключение

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