Параллелизм

Параллелизм — это свойство систем, при котором несколько вычислительных процессов или задач выполняются одновременно. В информатике и параллельных вычислениях параллелизм противопоставляется последовательному выполнению, где задачи исполняются одна за другой. Параллелизм может быть реализован на разных уровнях: от отдельных инструкций в процессоре до целых программ, работающих на разных компьютерах. Ключевое отличие параллелизма от конкурентности (concurrency) заключается в том, что параллелизм предполагает одновременное выполнение (физическое или логическое), тогда как конкурентность — это свойство системы управлять несколькими задачами, которые могут выполняться вперемежку, но не обязательно одновременно.

История

Идея параллельного выполнения вычислений возникла задолго до появления электронных компьютеров. В 1840-х годах Чарльз Бэббидж разрабатывал проект аналитической машины, которая могла бы выполнять несколько операций одновременно. Однако практическая реализация параллелизма стала возможна только с развитием цифровых вычислительных машин в середине XX века.

В 1950-х годах появились первые компьютеры с параллельной архитектурой, например, IBM 704 (1954), который поддерживал одновременную работу нескольких устройств ввода-вывода. В 1960-х годах были разработаны концепции многозадачности и многопроцессорности, в частности, в операционной системе CTSS (Compatible Time-Sharing System, 1961). В 1970-х годах появились векторные процессоры, такие как Cray-1 (1976), которые могли выполнять одну операцию над целым массивом данных за один такт.

В 1980-х годах началось активное развитие параллельных вычислительных систем: суперкомпьютеры с тысячами процессоров (например, Connection Machine, 1985), а также многопроцессорные системы на общей памяти (SMP, Symmetric Multi-Processing). В 1990-х годах параллелизм стал массовым благодаря появлению многоядерных процессоров для персональных компьютеров (например, Intel Pentium D, 2005). В 2000-х годах параллелизм проник в графические процессоры (GPU) и мобильные устройства. В 2010-х годах началось развитие гетерогенных вычислений, объединяющих CPU, GPU и специализированные ускорители (например, FPGA, ASIC).

Классификация

Параллелизм классифицируют по нескольким признакам.

По уровню выполнения

• Инструкционный параллелизм (ILP, Instruction-Level Parallelism) — одновременное выполнение нескольких машинных инструкций в одном процессоре. Реализуется через конвейеризацию, суперскалярность и спекулятивное выполнение.
• Параллелизм на уровне данных (DLP, Data-Level Parallelism) — одновременная обработка нескольких элементов данных одной инструкцией. Характерен для векторных процессоров и SIMD-расширений (SSE, AVX, NEON).
• Параллелизм на уровне задач (TLP, Task-Level Parallelism) — одновременное выполнение нескольких независимых задач или потоков. Реализуется в многопоточных процессорах, многоядерных системах и кластерах.
• Параллелизм на уровне памяти — одновременный доступ к разным областям памяти, например, в многоканальных контроллерах памяти или NUMA-архитектурах (Non-Uniform Memory Access).

По архитектуре (таксономия Флинна)

В 1966 году Майкл Флинн предложил классификацию компьютерных архитектур по числу потоков команд и данных:

• SISD (Single Instruction, Single Data) — один поток команд, один поток данных. Классическая последовательная архитектура (фон Неймана).
• SIMD (Single Instruction, Multiple Data) — один поток команд, несколько потоков данных. Векторные процессоры, GPU, DSP.
• MISD (Multiple Instruction, Single Data) — несколько потоков команд, один поток данных. Редкая архитектура, применяется в отказоустойчивых системах (например, в некоторых системах управления).
• MIMD (Multiple Instruction, Multiple Data) — несколько потоков команд, несколько потоков данных. Наиболее распространённая архитектура для параллельных вычислений: многоядерные процессоры, кластеры, суперкомпьютеры.

По способу организации памяти

• Системы с общей памятью (Shared Memory) — все процессоры имеют доступ к единому адресному пространству. Примеры: SMP (Symmetric Multi-Processing), NUMA. Проблемы: синхронизация доступа, когерентность кэша.
• Системы с распределённой памятью (Distributed Memory) — каждый процессор имеет собственную локальную память; обмен данными осуществляется через сообщения (Message Passing). Примеры: кластеры, суперкомпьютеры на основе MPI (Message Passing Interface).
• Гибридные системы — сочетают общую и распределённую память, например, в современных суперкомпьютерах (узлы с общей памятью, соединённые сетью).

Устройство и реализация

Параллелизм реализуется на нескольких уровнях вычислительной системы.

Аппаратный уровень

• Многоядерные процессоры — несколько вычислительных ядер на одном кристалле, каждое из которых может выполнять свой поток инструкций. Примеры: Intel Core i7, AMD Ryzen, ARM Cortex-A.
• Многопоточность (Simultaneous Multithreading, SMT) — технология, позволяющая одному ядру выполнять несколько потоков одновременно, используя неиспользуемые ресурсы конвейера. Примеры: Intel Hyper-Threading, AMD Zen.
• Векторные и SIMD-блоки — специализированные блоки, выполняющие одну инструкцию над несколькими элементами данных. Примеры: SSE (Streaming SIMD Extensions), AVX (Advanced Vector Extensions), NEON (ARM).
• Графические процессоры (GPU) — содержат тысячи ядер, оптимизированных для параллельной обработки данных (SIMT, Single Instruction, Multiple Threads). Примеры: NVIDIA CUDA, AMD ROCm.
• Специализированные ускорители — FPGA (Field-Programmable Gate Array), ASIC (Application-Specific Integrated Circuit), нейропроцессоры (NPU) для задач машинного обучения.

Программный уровень

• Потоки (Threads) — легковесные процессы, разделяющие общее адресное пространство. Управляются операционной системой или библиотеками (POSIX Threads, Java Threads, OpenMP).
• Процессы — изолированные экземпляры программы с собственным адресным пространством. Взаимодействуют через межпроцессное взаимодействие (IPC: pipes, sockets, shared memory).
• Модели параллельного программирования:
• OpenMP — стандарт для параллельного программирования на общей памяти (директивы компилятора, C/C++/Fortran).
• MPI — интерфейс передачи сообщений для распределённой памяти.
• CUDA — платформа параллельных вычислений на GPU от NVIDIA.
• OpenCL — открытый стандарт для гетерогенных вычислений (CPU, GPU, FPGA).
• TBB (Threading Building Blocks) — библиотека C++ для параллельного программирования от Intel.
• Go goroutines — лёгкие потоки, управляемые рантаймом языка Go.
• Erlang/Elixir — модель акторов для параллельных систем с распределённой памятью.
• Синхронизация — механизмы для координации доступа к общим ресурсам: мьютексы (mutex), семафоры, условные переменные, атомарные операции, барьеры памяти.

Применение

Параллелизм используется в широком спектре задач, где требуется высокая производительность или обработка больших объёмов данных.

Научные вычисления

• Моделирование климата, погоды, океанских течений.
• Молекулярная динамика (расчёт траекторий атомов и молекул).
• Квантовая химия (расчёт электронных структур).
• Астрофизика (симуляция эволюции галактик).
• Биоинформатика (анализ геномов, секвенирование ДНК).

Инженерные расчёты

• Вычислительная гидродинамика (CFD) — расчёт потоков жидкостей и газов.
• Метод конечных элементов (FEM) — прочностные расчёты конструкций.
• Оптимизация топологии и аэродинамики.
• Сейсмическое моделирование.

Обработка данных

• Параллельные базы данных (распределённые запросы, MapReduce, Spark).
• Анализ больших данных (Big Data) — кластеризация, классификация, регрессия.
• Машинное обучение и глубокое обучение — обучение нейронных сетей на GPU и TPU (Tensor Processing Unit).
• Обработка изображений и видео (фильтрация, сжатие, распознавание).
• Криптоанализ и перебор ключей.

Системное программное обеспечение

• Операционные системы (многозадачность, многопоточность).
• Веб-серверы (обработка множества запросов одновременно).
• СУБД (параллельные транзакции, репликация).
• Компиляторы (автоматическая параллелизация циклов).

Встраиваемые системы и реальное время

• Цифровая обработка сигналов (DSP — Digital Signal Processing).
• Управление роботами и дронами.
• Автомобильные системы (автопилот, обработка данных с лидаров).
• Телекоммуникационное оборудование (базовые станции, маршрутизаторы).

Проблемы и ограничения

Параллелизм не является панацеей и сопряжён с рядом фундаментальных и практических проблем.

Закон Амдала

Закон Амдала (1967) утверждает, что максимальное ускорение параллельной программы ограничено долей последовательных вычислений. Если в программе 10% кода не может быть распараллелено, то теоретическое ускорение не превысит 10 раз, даже при бесконечном числе процессоров. Это фундаментальное ограничение параллелизма.

Закон Густафсона

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

Синхронизация и гонки данных

При параллельном доступе к общим данным возникают состояния гонки (race conditions), когда результат зависит от порядка выполнения потоков. Для их предотвращения используются механизмы синхронизации, которые вносят накладные расходы и могут приводить к взаимным блокировкам (deadlocks) и голоданию (starvation).

Когерентность кэша

В системах с общей памятью каждый процессор имеет собственный кэш. Изменение данных в одном кэше должно быть корректно отражено в других кэшах. Протоколы когерентности (например, MESI, MOESI) обеспечивают это, но увеличивают задержки и энергопотребление.

Энергопотребление и тепловыделение

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

Программная сложность

Разработка параллельных программ значительно сложнее последовательных. Требуется учитывать синхронизацию, балансировку нагрузки, масштабируемость, отладку и тестирование. Многие классические алгоритмы плохо поддаются распараллеливанию.

Интересные факты

• Самый мощный суперкомпьютер мира (по состоянию на 2024 год) — El Capitan (США) с производительностью около 1,7 экзафлопс (10^18 операций с плавающей запятой в секунду), содержащий более 8 миллионов ядер.
• Первый коммерческий многоядерный процессор для настольных ПК — Intel Pentium D (2005) с двумя ядрами.
• В 2023 году компания NVIDIA выпустила GPU H100 с 80 миллиардами транзисторов и 18 432 ядрами CUDA.
• Параллелизм широко используется в криптовалютах: майнинг биткоина основан на параллельном переборе хешей (SHA-256).
• В 2019 году команда из Google впервые продемонстрировала «квантовое превосходство» на процессоре Sycamore, выполнив за 200 секунд задачу, которая заняла бы у классического суперкомпьютера 10 000 лет. Квантовые вычисления — это принципиально иная форма параллелизма, основанная на суперпозиции и запутанности.

Источники

• Флинн М. «Некоторые компьютерные организации и их эффективность» (IEEE Transactions on Computers, 1972).
• Амдал Г. «Достоверность однопроцессорного подхода к достижению крупномасштабных вычислительных возможностей» (AFIPS Conference Proceedings, 1967).
• Густафсон Дж. «Переоценка закона Амдала» (Communications of the ACM, 1988).
• Хеннесси Дж., Паттерсон Д. «Компьютерная архитектура: количественный подход» (6-е издание, 2019).
• «Параллельные вычисления: от многопроцессорных систем до GPU» (учебник, под ред. В. П. Гергеля, 2015).
• Официальные документы Intel, AMD, NVIDIA, ARM по архитектуре и параллелизму.