Параллельные алгоритмы

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

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

1. Граф зависимостей и «работа–высота»
   

   Любой параллельный алгоритм удобно моделировать ориентированным ациклическим графом

   G = (V, E)

   где вершины V – элементарные шаги (атомарные операции), а ребра E задают зависимости «сначала → потом». Две ключевые величины:

   • Полная работа:

   T₁ = ∑_{v ∈ V} cost(v)

   время выполнения на одном процессоре (последовательно).

   • Критический путь (высота, или span):

   T∞ = max_{пути P в G} ∑_{v ∈ P} cost(v)

   минимально возможное время на бесконечном числе процессоров (ограничено только зависимостями).

   Фундаментальная оценка для p процессоров (теорема Брента/Грэма):

   T_p ≥ max( T₁ / p , T∞ )

   и при разумном планировании достижима асимптотически:

   T_p ≤ T₁ / p + O(T∞)

   Отсюда ускорение и эффективность:

   S_p = T₁ / T_p

   E_p = S_p / p

2. PRAM-модель и типы конфликтов
   

   В модели PRAM (Parallel Random Access Machine) процессоры синхронны, доступ к памяти – за единицу времени. Существуют варианты по конфликтам чтения/записи:

   • EREW: exclusive read / exclusive write – ни одновременного чтения, ни записи в одну ячейку;

   • CREW: concurrent read / exclusive write – одновременное чтение разрешено;

   • CRCW: concurrent read / concurrent write – одновременно читают/пишут (требует правил разрешения записи: произвольная/минимум/сумма и т. п.).

   Модель PRAM упрощает анализ, задавая верхнюю планку параллелизма; при реализации добавляются накладные расходы коммуникаций, кэш-иерархий и синхронизации.

3. Законы масштабирования
   

   Закон Амдала (фиксированная задача, доля последовательного кода f):

   S_p ≤ 1 / ( f + (1 - f) / p )

   Закон Густавасона–Барсиса (масштабируемые задачи, наращиваемая «параллельная часть»):

   S_p ≈ p - α · (p - 1)

   где α – доля последовательной работы при увеличении размера задачи.

   Эти законы дополняют модель «работа–высота»: Амдал ограничивает потолок ускорения, а T∞ фиксирует «узкое место» зависимостей.

Корректность параллельных программ

1. Детерминизм и гонки данных
   

   Гонка данных возникает, если два параллельных шага обращаются к одной ячейке, и хотя бы один – запись, без «до-после» отношения в G. Отсутствие гонок – необходимое (но не всегда достаточное) условие детерминизма.

   Инварианты формулируются так же, как в последовательных программах, но проверяются на всех допустимых межплетениях (interleavings). В практических доказательствах используют редукции к коммутативным/ассоциативным операциям, барьеры и атомарные секции.

2. Мёртвые блокировки и живучесть
   

   Классические необходимые условия взаимной блокировки (Коффман): взаимное исключение, удержание и ожидание, отсутствие вытеснения, круговое ожидание. Нарушение хотя бы одного – стратегия предотвращения.

   Прогресс: каждый порожденный параллельный шаг должен либо завершиться, либо корректно отмениться (не «зависнуть» из-за неблокирующих структур и спин-циклов).

3. Линераризуемость операций
   Для параллельных структур данных важен критерий: каждая операция выглядит так, будто она выполняется в некоторый мгновенный момент времени между началом и концом вызова. Это свойство гарантируется либо строгой синхронизацией, либо конструкциями без блокировок (CAS, LL/SC), что не требуется знать глубоко для ЕГЭ, но полезно как концепт корректности.
   

Синхронизация и обмен данными

1. Примитивы
   

   • Барьеры – выравнивание фаз (все дошли – все пошли).

   • Мьютексы/критические секции – взаимоисключение.

   • Семафоры – подсчёт ресурса; обобщение мьютекса.

   • Атомарные операции – инкременты/минимумы/обмены без блокировок.

   • Редукции – ассоциативное объединение частичных результатов (sum/min/max/XOR и т. п.).

2. Ассоциативность и параллелизм
   

   Если операция ⊕ ассоциативна (и по возможности коммутативна), редукцию можно делать деревом высоты O(log n):

   (((a₁ ⊕ a₂) ⊕ (a₃ ⊕ a₄)) ⊕ ... )

   – классическая основа многих параллельных схем (скан, сортировки разделяй-и-властвуй, матричные умножения блоками).

3. Параллельный префикс (scan)
   

   Для массива A[1..n] и операции ⊕:

   prefix[i] = A[1] ⊕ A[2] ⊕ ... ⊕ A[i]

   Выполним за

   T₁ = O(n),   T∞ = O(log n)

   двухфазно (восхождение дерева – «upsweep», нисхождение – «downsweep»). Это ключевой строительный блок многих конвейерных и потоковых алгоритмов.

Инженерные соглашения и правила проектирования

1. Декомпозиция по данным/задачам. Сначала строится DAG зависимостей, затем выбирается стратегия: data parallel (map/reduce/scan) или task parallel (активные задачи).
2. Гранулярность. Задачи не должны быть слишком мелкими (накладные расходы планировщика) и слишком крупными (плохая балансировка). Эмпирически: «несколько десятков – сотен микросекунд» работы на задачу для CPU.
3. Локальность и кэш. Обход по строкам/блокам, блочное умножение матриц, объединение редких синхронизаций.
4. Избегать ложного совместного использования (false sharing): разные потоки не должны активно писать в разные переменные, но попадающие в одну кэш-линию.
5. Идемпотентность и восстановление. В параллельных циклах токсичны необратимые побочные эффекты (I/O); отделяйте вычисление от эффектов.
6. Планировщик «work-stealing». Для рекурсивных D&C-алгоритмов – оптимальное распределение работы при минимальной ручной координации.
7. Измерять, затем оптимизировать. Метрики: T_p, S_p, E_p, глубина очередей, промахи кэша, задержки синхронизации.

Параллельные шаблоны

• Map/Filter/Reduce. Независимая обработка элементов, затем редукция.
• Scan (prefix-sum). Префиксные агрегаты, ранжирование, компактификация.
• Divide-and-Conquer. Рекурсивное деление на независимые подзадачи (быстрая сортировка, слияние, FFT).
• Stencil/Neighborhood. Сеточные схемы с локальными зависимостями (скользящее окно).
• Pipeline. Конвейеры стадий с буферами (стриминг).
• Графовые обходы. «Фронтовые» BFS/SSSP, где фронт параллелится по вершинам/ребрам.

Примеры (языконезависимые псевдокоды)

1. Параллельная сумма (редукция)
   

   function parallel_sum(A):

     // разбиение на p блоков

     локально: s_j = sum(A[chunk_j])          // независимо

     глобально: S = reduce(s_j, +)             // дерево сложения

     return S

   Анализ: T₁ = Θ(n), T∞ = Θ(log p + n/p) с оптимальным p.

2. Параллельный префикс (сумма)
   

   // upsweep

   for d = 0..⌈log₂ n⌉-1 parallel:

     for i = 1..n step 2^{d+1} parallel:

       A[i+2^{d+1}-1] := A[i+2^d-1] + A[i+2^{d+1}-1]

   
   

   // downsweep

   A[n] := 0

   for d = ⌈log₂ n⌉-1 .. 0 parallel:

     for i = 1..n step 2^{d+1} parallel:

       t := A[i+2^d-1]

       A[i+2^d-1] := A[i+2^{d+1}-1]

       A[i+2^{d+1}-1] := t + A[i+2^{d+1}-1]

   Результат: A[i] становится prefix[i].

Мини-шпаргалка 

1. Работа–высота:
   T_p ≥ max( T₁ / p , T∞ )

   S_p = T₁ / T_p

   E_p = S_p / p

2. Амдал:
   S_p ≤ 1 / ( f + (1 - f) / p )

3. Густавасон:
   S_p ≈ p - α · (p - 1)

4. Идеальная редукция по дереву (n – степень двойки): 
   T₁ = Θ(n)

   T∞ = Θ(log n)

5. Условие отсутствия перегрузки очереди в конвейере (простой критерий):
   λ_stage < 1 / T_stage   для каждой стадии

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

• Гонки данных. Запись без синхронизации → недетерминизм. Решение: атомики/мьютексы/редукции; переразбиение на «частные» буферы с последующим слиянием.
• Слишком мелкая гранулярность. Время планирования сравнимо с полезной работой. Решение: батчирование элементов.
• Ложное совместное использование. Частые записи в соседние ячейки. Решение: выравнивание структур, padding.
• Барьеры «на каждый чих». Избыточные фазы убивают масштабируемость. Решение: локальные зависимости, асинхронные очереди.
• Неразделение вычислений и I/O. Параллельная запись в файл вызывает блокировки. Решение: буферы и последовательный писатель.
• Переоценка p. Ускорение не растёт после насыщения кэшей/памяти. Решение: профилировать, ограничить число исполнителей.

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

• Графы: построение DAG, нахождение критического пути, топологическая сортировка.
• Сложность: вычисление T₁, оценка T∞, применение формул ускорения.
• Логика и инварианты: корректность редукций, доказательства отсутствия гонок.
• Массивы и строки: распараллеливание подсчётов частот, префикс-сумм, фильтрации.
• Вероятности/проценты: интерпретация эффективности, доли последовательной части (Амдал).

Пять упражнений 

Упражнение 1. «Оценка ускорения по Амдалу»
Условие. В алгоритме 12% работы неизбежно последовательны. Оцените верхнюю границу ускорения на p = 16 ядрах и предел при p → ∞.
Решение.

f = 0.12

S₁₆ ≤ 1 / (0.12 + 0.88/16) = 1 / (0.12 + 0.055) = 1 / 0.175 ≈ 5.714

S_∞ ≤ 1 / f = 1 / 0.12 ≈ 8.333

Ответ. На 16 ядрах – не более ≈ 5.7×; предельное ускорение – ≈ 8.33×. 

Упражнение 2. «Работа–высота и теорема Брента»
Условие. Для задачи n = 2¹⁶ известны оценки: T₁ = 10⁸ шагов, T∞ = 5·10³ шагов. Оценить нижнюю границу T₆₄ и максимально достижимое ускорение S₆₄.
Решение.

T₆₄ ≥ max( T₁/64 , T∞ ) = max( 10⁸/64 , 5·10³ )

= max( 1.5625·10⁶ , 5·10³ ) = 1.5625·10⁶ шагов

S₆₄ ≤ T₁ / T₆₄ ≈ 10⁸ / 1.5625·10⁶ ≈ 64

Критический путь здесь не лимитирует; упираемся в T₁/p.
Ответ. T₆₄ ≥ 1.5625·10⁶; ускорение близко к идеальному (до накладных расходов).

Упражнение 3. «Дерево редукции и глубина»
Условие. Над n = 1024 числами выполняется ассоциативная редукция. Оцените высоту дерева операций и число параллельных фаз.
Решение.

Для степени двойки:

высота = log₂ n = log₂ 1024 = 10

Столько же параллельных фаз (каждая сокращает массив вдвое).
Ответ. 10 фаз; T∞ = Θ(log n) = 10 (в абстракции PRAM). 

Упражнение 4. «Дедлок: обнаружение и предотвращение»
Условие. Два потока P1 и P2 используют два ресурса R1 и R2. P1 захватывает R1, затем R2; P2 – R2, затем R1. Докажите, что возможен дедлок, и предложите универсальное правило его предотвращения.
Решение.

Возможна ситуация: P1 держит R1, ждёт R2; P2 держит R2, ждёт R1 – круговое ожидание, выполнены все условия Коффмана.
Правило предотвращения: глобальный порядок захвата – все потоки запрашивают ресурсы в одном и том же порядке (например, R1 → R2). Тогда невозможен цикл ожидания.
Ответ. Дедлок устраняется тотальным порядком на ресурсах. 

Упражнение 5. «Параллельная фильтрация и префикс-сумма»
Условие. Дан массив A[1..n]. Требуется параллельно удалить все чётные элементы (сжать массив). Разрешено использовать операции: пометка, префикс-сумма, расстановка.
Решение.

1. Пометка: B[i] = 1, если A[i] нечётен; иначе 0. (параллельно)
2. Префикс: P = scan(B, +) – количество нечётных до позиции i.
3. Расстановка: если B[i]=1, то C[P[i]] = A[i]. (параллельно)

Сложности:

T₁ = Θ(n)

T∞ = Θ(log n)  // за счёт scan

Ответ. Алгоритм использует ассоциативность сложения и достигает оптимальной глубины Θ(log n).

Чек-лист разработчика параллельных алгоритмов (и абитуриента ЕГЭ)

• Построен DAG зависимостей; оценены T₁ и T∞.
• Выбрана стратегия: data/task parallel; определена гранулярность.
• Операции редукции – ассоциативные/коммутативные; префикс-сумма при необходимости.
• Исключены гонки данных; критические секции минимальны.
• Минимизируются барьеры; локальность доступа – высокая.
• Измерены S_p, E_p; сопоставлены с Амдалом и «работа–высота».
• Для задач ЕГЭ: уверенно считаю log, проценты, строю топологический порядок, разбираю таблицы истинности и инварианты.

Контрольные вопросы для самопроверки

1. Сформулируйте оценки Брента и объясните, почему они задают нижнюю границу времени на p процессорах.
2. Приведите пример ассоциативной операции и объясните, как из неё построить редукцию Θ(log n).
3. В чём различие между законами Амдала и Густавасона по предпосылкам и выводам?
4. Почему глобальный порядок на ресурсах предотвращает дедлок?
5. Как параллельный префикс используется для компактификации массива?

Заключение

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