Параллелизм на уровне инструкций¶

Что такое ILP¶

ILP (Instruction-Level Parallelism) — способность процессора выполнять несколько инструкций параллельно в пределах одного потока, даже если они записаны последовательно. Это достигается за счёт нескольких аппаратных механизмов:

Pipeline: каждая инструкция проходит через несколько стадий (fetch, decode, execute, writeback); разные стадии разных инструкций выполняются одновременно.
Суперскалярность: несколько независимых инструкций исполняются в одном такте на разных исполнительных устройствах (ALU, умножитель, блок загрузки/записи).
Out-of-order execution: процессор переупорядочивает инструкции, чтобы максимально загрузить исполнительные устройства, сохраняя при этом наблюдаемый порядок результатов.

Ключевое понятие — цепочка зависимостей (dependency chain): если инструкция использует результат предыдущей, она не может начаться, пока та не завершится. Независимые инструкции могут выполняться параллельно.

Pipeline: как инструкции движутся по стадиям¶

Классический пятистадийный конвейер. Каждая стадия занимает один такт; в каждом такте одновременно исполняются разные стадии разных инструкций:

Стадии:  Fetch(IF) ──▶ Decode(ID) ──▶ Execute(EX) ──▶ Memory(MEM) ──▶ Writeback(WB)

Такт:       1       2       3       4       5       6       7
         ┌───────┬───────┬───────┬───────┬───────┬───────┬───────┐
Инстр. 1 │  IF   │  ID   │  EX   │  MEM  │  WB   │       │       │
         ├───────┼───────┼───────┼───────┼───────┼───────┼───────┤
Инстр. 2 │       │  IF   │  ID   │  EX   │  MEM  │  WB   │       │
         ├───────┼───────┼───────┼───────┼───────┼───────┼───────┤
Инстр. 3 │       │       │  IF   │  ID   │  EX   │  MEM  │  WB   │
         └───────┴───────┴───────┴───────┴───────┴───────┴───────┘
          ↑ в такте 5 три инструкции находятся на разных стадиях одновременно

Стадии:

IF (Instruction Fetch) — загрузить следующую инструкцию из кэша инструкций
ID (Instruction Decode) — декодировать опкод, прочитать регистры
EX (Execute) — выполнить инструкцию в ALU / FPU / AGU
MEM (Memory access) — обратиться к кэшу данных (load/store)
WB (Write Back) — записать результат в регистровый файл

Суперскалярность: несколько инструкций в одном такте¶

Суперскалярный процессор имеет несколько параллельных исполнительных устройств. Если инструкции независимы — они идут параллельно:

Зависимые инструкции (цепочка, ILP=1):

Такт:       1       2       3
         ┌─────────────────────────────────────────┐
ALU 0    │ add rax, 1  │ add rax, 1  │ add rax, 1  │   ← только одна ALU занята
         └─────────────────────────────────────────┘
           (каждая ждёт результат предыдущей)

──────────────────────────────────────────────────────

Независимые инструкции (ILP=3, суперскалярность):

Такт:       1
         ┌─────────────────────────────────────────┐
ALU 0    │   add rax, 1   │   ← обновляет rax      │
ALU 1    │   add rbx, 1   │   ← обновляет rbx      │
ALU 2    │   add rcx, 1   │   ← обновляет rcx      │
         └─────────────────────────────────────────┘
           три инструкции выполнились за один такт

Эксперимент: зависимые vs. независимые инструкции¶

#include <iostream>
#include <chrono>

int main() {
    constexpr long iterations = 1'000'000'000L;
    using Clock = std::chrono::steady_clock;

    /* Тест 1: зависимые инструкции — нет ILP */
    auto start = Clock::now();
    long x = 0;
    for (long i = 0; i < iterations; ++i) {
        x = x + 1;  /* каждая зависит от предыдущей */
        x = x + 1;
        x = x + 1;
    }
    auto end = Clock::now();
    auto time_dep = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
    std::cout << "Dependent:    " << time_dep << " ns, x=" << x << "\n";

    /* Тест 2: независимые инструкции — есть ILP */
    start = Clock::now();
    long a = 0, b = 0, c = 0;
    for (long i = 0; i < iterations; ++i) {
        a = a + 1;  /* независима от b и c */
        b = b + 1;  /* независима от a и c */
        c = c + 1;  /* независима от a и b */
    }
    end = Clock::now();
    auto time_ind = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
    std::cout << "Independent:  " << time_ind << " ns, a+b+c=" << a+b+c << "\n";
    std::cout << "Speedup: " << static_cast<double>(time_dep) / time_ind << "x\n";
}

Ожидаемый результат:

Dependent:    3644583984 ns, x=3000000000
Independent:  1736035886 ns, a+b+c=3000000000
Speedup:      2.1x

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

Out-of-order execution¶

Out-of-order execution (OoOE) — процессор самостоятельно переставляет инструкции программы, чтобы максимально загрузить исполнительные устройства, не нарушая при этом наблюдаемую логику программы (для одного потока).

Например:

a = b + c;
d = e * f;   /* не зависит от a */
g = h + i;   /* не зависит от a и d */

Процессор может начать загрузку операндов e,f и h,i одновременно с вычислением b+c, и выдать все три результата быстрее, чем если бы выполнял последовательно.

Однако OoOE создаёт проблемы в многопоточных программах: один поток может наблюдать записи другого потока в порядке, отличном от того, в котором они были сделаны:

/* Поток 1 */       /* Поток 2 */
x = 1;              if (y == 2)
y = 2;                  printf("x=%d\n", x);  /* может напечатать 0! */

Без барьеров памяти (std::atomic, __sync_synchronize) порядок чтения/записи между потоками не гарантируется.

Спекулятивное исполнение¶

Спекулятивное исполнение (speculative execution) — разновидность OoOE, при которой процессор начинает выполнять инструкции по предсказанному пути ветвления ещё до того, как условие вычислено:

cmpq $128, %rax
jl   label
addq %rbx, %rax    # выполняется спекулятивно
label:

Если предсказание оказалось верным, инструкции уже выполнены — бесплатное ускорение. Если нет — результаты откатываются (flush pipeline), но данные уже могли быть загружены в кэш.

Уязвимости Spectre и Meltdown¶

Spectre и Meltdown (2018) — уязвимости, эксплуатирующие побочные эффекты спекулятивного исполнения. Хотя результаты спекулятивных инструкций откатываются, изменения в кэше остаются. Атакующий определяет, какие данные были загружены в кэш, через timing-атаку (измерение времени доступа к памяти).

Meltdown позволяет пользовательскому процессу спекулятивно читать память ядра до того, как процессор проверит права доступа. Защита: KPTI (Kernel Page Table Isolation).

Spectre позволяет обучить branch predictor, чтобы жертва выполнила спекулятивные инструкции, загружающие секретные данные в кэш. Защита: retpoline (замена косвенных переходов), compiler barriers (lfence).

Для прикладного программиста:

Используйте std::atomic для разделяемых данных между потоками.
Применяйте constant-time алгоритмы в криптографическом коде.
Не полагайтесь на секретность адресов памяти как единственную защиту.

Связанные темы¶

Предсказание ветвлений — спекулятивное исполнение и branch predictor
Кэши процессора — взаимодействие OoOE с иерархией памяти
Векторные инструкции (SIMD) — ещё один уровень параллелизма: одна инструкция над несколькими данными

Источники¶

Intel 64 and IA-32 Architectures Optimization Reference Manual — Pipeline and Out-of-Order Execution
Agner Fog, "Microarchitecture of Intel, AMD and VIA CPUs": https://agner.org/optimize/
Spectre/Meltdown paper: https://spectreattack.com/spectre.pdf
man 7 memory_ordering — барьеры памяти в Linux
cppreference: std::atomic — https://en.cppreference.com/w/cpp/atomic/atomic