# Параллельное мышление: как алгоритмические примитивы меняют архитектуру данных

Источник: https://www.youtube.com/watch?v=Ba3TqxSgnTk
Канал: Stanford Online
Опубликовано: 19.09.2024

---

## Параллельное мышление: архитектура данных и алгоритмические примитивы
[[JUMP:00:42]]

В восьмой лекции курса Stanford CS149 по параллельным вычислениям ведущий детально разбирает концепцию «параллельного мышления». В центре внимания — переход от низкоуровневого управления потоками (threads) к использованию высокоуровневых операций над коллекциями данных. Такой подход позволяет разработчикам не заботиться о зависимостях и синхронизации, делегируя их эффективным библиотечным реализациям.

### 🛠 Базовые примитивы: Map и Fold
[[JUMP:06:43]]

Основой для построения параллельных алгоритмов являются универсальные примитивы, позволяющие абстрагироваться от деталей работы с «железом».

*   **Map**: Классическая высокоуровневая функция, применяющая оператор `f` к каждому элементу последовательности. Параллелизация здесь тривиальна: достаточно разделить данные на части и распределить обработку между потоками.
*   **Fold (свертка)**: Операция, сводящая последовательность к единственному значению (например, сумма). Для параллелизации Fold критически важно, чтобы используемая функция была **ассоциативной**. В противном случае порядок применения операций не гарантирует идентичный результат.

### 📈 Сканирование (Scan): от последовательности к префиксным суммам
[[JUMP:20:01]]

Scan — более сложная операция, которая возвращает последовательность промежуточных результатов (префиксных сумм). В отличие от Map, она требует более изощренных подходов для параллелизации.

*   **Алгоритм с затратами $O(n \log n)$**: Легко реализуем на SIMD-устройствах (например, внутри WARP в CUDA), где каждый поток выполняет одну операцию за шаг, но суммарно работа возрастает.
*   **Эффективный алгоритм $O(n)$**: Использует метод «вверх-вниз» (upsweep и downsweep) по дереву. Хотя он требует больше этапов (коэффициент 2), он оптимален по количеству совершаемых операций.

Как отмечает спикер, выбор между этими алгоритмами зависит от целевой архитектуры: для машин с тысячами независимых процессоров лучше подходит версия $O(n)$, для SIMD-блоков — классический логарифмический подход.

### 🔗 Сегментированное сканирование и разреженные матрицы
[[JUMP:45:05]]

Сегментированный скан (segmented scan) применяется, когда данные представлены как «последовательность последовательностей». Это критически важно для эффективной работы с графами или разреженными матрицами, где строки имеют разную длину.

Пример использования в **Compressed Sparse Row (CSR)**:

1.  Матрица хранится как плоский список ненулевых значений и индексов столбцов.
2.  Операция умножения вектора на такую матрицу сводится к сбору (gather) элементов, поэлементному умножению (map) и сегментированному сканированию для суммирования результатов по строкам.

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

### 🌍 Практическое применение: библиотеки и фреймворки
[[JUMP:116:08]]

Ведущий подчеркивает, что современные инструменты активно используют описанные концепции для абстракции параллелизма:

*   **NVIDIA Thrust**: C++ библиотека для GPU, предоставляющая высокоуровневый API для Map, Sort, Scan и других примитивов.
*   **Apache Spark**: Распределенная система, где работа с данными ведется через RDD (Resilient Distributed Datasets) — по сути, те же последовательности, на которых базируются все описанные операции.

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