edu-csa

# Архитектура компьютера

## Лекция 15-16

### Не фон Неймановские процессоры. <br/> ПЛИС. High-Level Synthesis. <br/> Классификации Флинна и Дункана. <br/> CGRA

Пенской А.В., 2025

---

## Немного повторов

----

### Источники роста производительности?

1. Частота.
1. Специализация системы команд, аппаратуры.
1. Параллелизм уровня бит, инструкций, задач.
1. Адаптация структуры вычислителя под задачу и параллелизм.
1. Динамическая адаптация.

--------------------------

#### И препятствия на его пути

1. Закон Мура
1. Закон Амдала
1. Закон Деннарда
1. Power Wall
1. Memory Wall

</div><div class="col">

![](/fig/proc-performance-grow.jpg)

</div></div>

----

## Виды процессоров (повтор)

### Гибкость и эффективности

![](/fig/architecture-comparison-flexibility-performance-energy.png)

(1) Application-Specific Integrated Circuit
(2) **Coarse-Grained Reconfigurable Arrays**
(3) **Field-Programmable Gate Array**

</div><div class="col">

(4) **Digital Signal Processor** <br/>
(5) **Graphics Processing Unit** <br/>
(6) Central Processing Unit

</div></div>

---

### Spatial vs. Temporal Computation

![](/fig/cgra-alg.png)

#### Temporal Computation

![](/fig/cgra-temporal-computation.png)

"Схема" последовательно выполняет требуемые задачи.

</div><div class="col">

#### Spatial Computation

![](/fig/cgra-asic-structured.png)

Схема повторяет граф вычислений. Параллелизм (конвейер, потоки).

![](/fig/cgra-fpga-in-a-box.png)

"Переплетается"

</div></div>

---

### Программируемые логические интегральные схемы

<dl>
  <dt> ПЛИС </dt>
  <dd>  интегральная микросхема, используемая для создания конфигурируемых цифровых электронных схем. </dd>
</dl>
 
- Логика работы задаётся данными, а не конструкцией.
- Для формирования конфигурации используется специальное ПО и Hardware Description Languages (HDL): Verilog, VHDL...
- "[Ре]конфигурируется", а не "программируется".

</div><div class="col">

![](/fig/fpga-design-flow.jpg)

</div></div>

----

#### Hardware Description Language <br/> Register Transfer Level (RTL)

![](/fig/verilog-and-rtl.png)

----

#### ПЛИС/СБИС (FPGA/ASIC)

![](/fig/fpga-vs-asic-cost.png)

[Источник](https://towardsdatascience.com/introduction-to-fpga-and-its-architecture-20a62c14421c)

</div><div class="col">

#### ПЛИС. Этапы синтеза

![](/fig/fpga-synthesis.jpg)

</div></div>

----

#### ПЛИС. Устройство

![](/fig/fpga-internal.png)

</div><div class="col">

#### ПЛИС. Lookup tables (LUT)

![](/fig/fpga-lut.png)

</div></div>

----

### CPU vs. FPGA

![](/fig/cgra-cpu-vs-fpga.jpeg)

Тут: MoC с точки зрения — как мы используем аппаратные ресурсы.

---

### Высокоуровневый синтез /1 <br/> (High-Level Synthesis)

Проблемы:

1. Множество вариантов отображения алгоритма в цифровую схему.
1. Выбор зависит от требований.
1. Изменение требований может вызвать перепроектирование.
1. Разработка схем трудоёмка и требует специалистов.
1. Медленные тесты.

</div><div class="col">

![](/fig/hls-tradeoff-examples.png)

**Spatial** vs. **Temporal Computation**

</div></div>

----

#### Высокоуровневый синтез /2

![](/fig/hls-design-flow.png)

----

#### Высокоуровневый синтез. Достоинства

1. Скорость проектирования. Быстрое прототипирование.
1. Переносимость между разными целевыми платформами.
1. Адаптируемость микроархитектуры под новые условия.
1. Автоматизация процесса оптимизации схемы.

#### Высокоуровневый синтез. Недостатки

1. Ограниченный контроль за результатом синтеза. "Чудеса"
1. Кривая обучения (специальность HLS Engineer)
1. Уровень зрелости технологии сильно варьируется:
    - верификация результата;
    - стабильность работы.

---

### Другие подходы описания аппаратуры

#### Chisel

Constructing Hardware in a **Scala** Embedded Language

![](/fig/chisel-design-and-validation-flow.png)

</div><div class="col">

![](/fig/chisel-code-example.jpeg)

</div></div>

----

#### Bluespec

**High-level hardware description language**. It has a variety of advanced features including a powerful **type system** that can prevent errors prior to synthesis time, and its most distinguishing feature, **Guarded Atomic Actions**, allow you to define hardware components in a modular manner based on their invariants, and let **the compiler pick a scheduler**.

![](/fig/bluespec-flow.jpg)

</div><div class="col">

![](/fig/bluespec-example.jpg)

</div></div>

----

- **Clash** — Clash is a **functional** hardware description language that borrows both its syntax and semantics from the functional programming language Haskell.
- **PyHDL** — turns Python into a hardware description and verification language, providing hardware engineers with the power of the Python ecosystem.
- ...

---

## Классификация параллельных процессоров

1. Таксономия Флинна (1979 год)
2. Классификация Дункана (1990 год)
3. CGRA Classification (2019)

Liu, Leibo, et al. "A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications." ACM Computing Surveys (CSUR) 52.6 (2019): 1-39.

---

### Таксономия Флинна

Классификация параллельных процессоров на основе:

1. количества потоков инструкций.
1. количества потоков данных.

Достоинства: простая и понятная.

Недостатки:

1. Не применима к не фон Неймановским архитектурам.
1. Перегруженность класса MIMD.

</div><div class="col">

![](/fig/flynns-taxonomy.png)

</div></div>

----

#### SISD (Single Instruction, Single Data)

![](/fig/flynns-sisd.png)

1. Простой последовательный процессор.
1. Абсолютное большинство рассмотренных ранее процессоров.
1. Включая процессоры с низкоуровневым параллелизмом.

----

#### SIMD (Single Instruction, Multiple Data)

![](/fig/flynns-simd.png)     
![](/fig/proc-cpu-vs-gpu.png)

1. Одновременное выполнение несколькими процессорами одной инструкции (Lockstep execution).
1. Назначение: однообразная обработка множества наборов данных.
1. Пример: GPU, поиск блока для BitCoin, мат. моделирование.
1. Ключевое ограничение: операции ветвления.

----

#### SIMT (Single Instruction, Multiple Threads)

![](/fig/simt.png)

</div><div class="col">

![](/fig/simt-code.png) 
![](/fig/simt-process.png)

</div></div>

1. Расширение SIMD, позволяющее работать с оператором ветвления.
1. Широко применяется в современных GPU и GPGPU (CUDA).
1. Включает механизмы синхронизации потоков между собой для достижения lockstep execution.

----

#### MISD (Multiple Instruction, Single Data)

![](/fig/flynns-misd.png)

1. Один поток данных обрабатывается разными наборами инструкций.
1. Обычно выделяется для полноты классификации.
1. На практике — повышение надёжности работы систем. Защита от ошибок проектирования и алгоритмов. Параллельная разработка и эксплуатация решений задачи.

----

#### MIMD (Multiple Instruction, Multiple Data)

![](/fig/flynns-mimd.png)

1. Множество процессоров автономно выполняют различные инструкции над различными данными.
1. Самый разнообразный класс процессоров по классификации Флинна.
1. Не выделяются подвиды, поэтому будут рассмотрены в контексте классификации Дункана.

---

## Классификация Дункана

Задачи:

1. Абстрагироваться от низкоуровневого параллелизма (конвейер, суперскаляр, VLIW).
1. Переиспользовать элементы таксономии Флинна от 1966.
1. Актуализировать и включить новинки на 1990 год.
1. Навести порядок в MIMD.

--------------------

- Достоинства: относительная полнота.
- Недостатки: сложность, "искусственность".
- Новинки отмечены: `*`.

</div><div class="col">

![](/fig/taxonomy-duncan.png)

[Duncan, Ralph, "A Survey of Parallel Computer Architectures", IEEE Computer. February 1990, pp. 5-16.](https://ieeexplore.ieee.org/document/44900)

</div></div>

----

### Классификация Дункана. Уровень 1

1. **Синхронные архитектуры**

Параллельные архитектуры с единым механизмом управления (глобальные часы, центральный блок управления и т.п.). **Различаются механизмами синхронизации**.

1. **MIMD архитектуры**

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

1. **MIMD парадигма** (MIMD paradigm architectures)

Архитектура MIMD процессора определяется моделью вычислений (MoC). MoC определяет характер потоков данных, принципы взаимодействия и синхронизации. **Различаются MoC**.

---

### Синхронные архитектуры

Класс процессорных архитектур, обладающих единым/централизованным/синхронным управлением, определяющим поведение всего процессора в целом.

- Векторные архитектуры.
- SIMD архитектуры:
    - Процессорные массивы.
    - Ассоциативные массивы.
- Систолические массивы.
- Совмещение памяти и вычислений`*`.

----

#### Sync. Векторные архитектуры

<dl>
  <dt> Скалярная величина </dt>
  <dd>  величина, которая может быть представлена числом (целочисленным или с плавающей точкой). </dd>
</dl>
 
--------------------

<dl>
  <dt> Вектор </dt>
  <dd>  величина, представленная последовательностью скалярных величин. </dd>
</dl>
 
--------------------

Векторные операции — операции, выполняемые на последовательностях данных.

</div><div class="col">

```c
for (i = 0; i < 10; i++)
    c[i] = a[i] + b[i];
```

```asm
  move  $10, count   ; count := 10
loop:
  load  r1, a
  load  r2, b
  add   r3, r1, r2   ; r3 := r1 + r2
  store r3, c
  add   a, a, $4     ; move on
  add   b, b, $4
  add   c, c, $4
  dec   count        ; decrement
  jnez  count, loop  ; loop back if count != 0
```

```asm
  ; v1, v2, v3 -- vector registers
  move   $10, count    ; count = 10
  vload  v1, a, count
  vload  v2, b, count
  vadd   v3, v1, v2
  vstore v3, c, count
```

</div></div>

----

##### Векторные архитектуры. Устройство

![](/fig/vector-architecture-register-to-register.png)

1. Сокращение количества обрабатываемых инструкций.
1. Конвейерное исполнение векторных операций.
1. Множество функциональных узлов (суперскалярность).

----

#### Sync. SIMD Архитектуры

Single Instruction Multiple Data

##### SIMD. Процессорные массивы

![](/fig/simd-processor-array.png)

Эквивалент SIMD в классификации Флинна.

----

##### SIMD. Ассоциативный массив

(Content-Addressable <br/> Parallel Processor, CAPP)

![](/fig/associative-memory-comparison-operation.png)

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

</div><div class="col">

Процессор основанный на ассоциативной памяти (Content-addressable memory, CAM)

![](/fig/cam-ram.gif)

</div></div>

----

#### Sync. Систолические архитектуры

Конвейерные мультипроцессоры:

1. данные ритмично поступают из памяти,
1. проходят через сеть процессоров,
1. и возвращаются в память.

Синхронизация — через глобальные часы, такт вычислений (не путать с тактовым сигналом).

Процессоры объединены локальными связями, и каждый цикл процессоры выполняют короткие неизменные операции.

</div><div class="col">

![](/fig/systolic-flow.png)

</div></div>

----

##### Sync. Систолические архитектуры. Пример

![](/fig/systolic-process-example.png)

----

###### SIMD. Совмещение памяти и Вычислений `*`

Пример: перемножение матриц в нейронных вычислителях. $Out = In \times Parameters$.

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

</div><div class="col">

![](/fig/simd-memory-array.jpg)

(результат 1.2 на след. слайде)

</div></div>

----

![](/fig/simd-memory-array-2.jpg)

---

### MIMD архитектура

Ключевой вопрос — организация памяти:

- разделяемая,
- распределённая.

Аналогия из современных веб приложений:

- синхронизация через единую базу данных;
- микросервисная архитектура.

----

#### MIMD. Разделяемая память

1. Координация совместной работы через общую память.
1. Ключевая проблема: координация доступа, согласование кешей.
1. Примеры подходов:
    - (a) шинное соединение;
    - (b) перекрестная шина 2x2;
    - (c) сеть на кристалле, запрос маршрутизируется от P к M.
1. Широко распространены, так как привычны и прозрачны для программистов.

</div><div class="col">

![](/fig/mimd-shared-memory.png)

</div></div>

----

#### MIMD. Распределённая память

1. Координация совместной работы через прямое взаимодействие процессоров.
1. Данные/сигналы явно передаются между процессорами (message passing).
1. Мотивация: обеспечить масштабируемость многопроцессорной архитектуры и доступ к локальным данным процессора.

</div><div class="col">

![](/fig/mimd-structure.png)

</div></div>

----

##### MIMD. Распределённая память. Топология

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

1. **Кольцевая** топология + [хорды]. Мало процессоров, передача данных не доминирует.
1. **Ячеистая** / сетка. Соединены соседи + [диагональные] + [кольцевые]. Топологическое соответствие матричным алг.
1. **Дерево**. Алгоритмы поиска и сортировки, обработка изображений, потоковые и редукционные машины.
1. **Гиперкуб**. Коммуникационный диаметр $log_{2}N$.
1. **Реконфигурируемые**. Фиксируем сеть конфигурацией, а не маршрутом.

</div><div class="col">

![](/fig/mimd-distributes-memory.png)

</div></div>

---

### MIMD парадигма (paradigm architectures)

Имеется в виду парадигма программирования или точнее — модель вычислений (MoC).

- MIMD/SIMD
- Потоковая архитектура (Dataflow)
- Редукционная архитектура
- Wavefront

----

#### MIMD/SIMD

1. Гибридные архитектуры, где управление MIMD (малые задачи) осуществляется в стиле SIMD (крупные задачи).
1. Отношение ведущий — ведомый (master — slave) может быть представлено деревом:
    - корень работает как SIMD и распределяет задания;
    - листья работают как MIMD с локальной памятью.
1. Аналогия: `fork/join`.

</div><div class="col">

![](/fig/mimd-simd-hybrid.png)

</div></div>

----

##### MIMD/SIMD. Transport Triggered Architecture (TTA) Processor `*`

![](/fig/tta-instruction.png)

1. Запуск вычислений инициируется пересылкой данных, управляемой диспетчером.
1. Непосредственное выполнение инструкций — отсутствует.
1. Долгая обработка + быстрая пересылка $\rightarrow$ параллелизм.

----

#### Потоковая архитектура (Dataflow)

<dl>
  <dt> Потоковые архитектуры </dt>
  <dd>  возможность выполнения и исполнения инструкций определяется исключительно наличием входных аргументов для инструкций. Порядок выполнения инструкций непредсказуем. </dd>
</dl>
 
--------------------

1. Алгоритм представляется в виде графа вычислений.
1. Отсутствует память и канал доступа как "бутылочное горлышко".
1. Проблема — передача данных между узлами.
1. Аналогия: микросервисные архитектуры.

</div><div class="col">

![](/fig/dataflow-graph.png)

![](/fig/conceptual-representation-of-the-data-flow-computer-architecture.png)

(реконфигурируемая топология)

</div></div>

----

##### Потоковая архитектура (Dataflow). Устройство

1. Распределённая память. Топология кольцо.
1. По кольцу посылаются токены (метка + значение).
1. Получатели пересылают токен дальше и сохраняют значение, если являются адресатом.
1. Если задача разблокируется (все необходимые токены получены) — запускается работа.
1. Результат работы отправляется токеном по кольцу.

</div><div class="col">

![](/fig/dataflow-token-machine.png)

</div></div>

----

#### Редукционная архитектура (Reduction)

<dl>
  <dt> Редукционные архитектуры (ориентированные на запрос) </dt>
  <dd>  инструкции разрешаются к выполнению, когда их результаты требуются в качестве операндов для уже разрешенных инструкций. </dd>
</dl>
 
--------------------

1. Разрабатывались для параллелизма и функционального программирования.
1. Выполнение: выборка инструкций, замена инструкции на её результат в графе вычислений.
1. Проблемы: ссылочная прозрачность, разворачивание вычислительного графа, нормальные/ленивые вычисления.

</div><div class="col">

![](/fig/reduction-architecture.png)

</div></div>

----

##### Редукционная архитектура (Reduction). Устройство

![](/fig/proc-reduction-simple.png)

[An Architecture for Combinator Graph Reduction (TIGRE)](https://users.ece.cmu.edu/~koopman/tigre/index.html)

</div><div class="col">

![](/fig/proc-reduction-calls.png)

</div></div>

Notes: В аппаратуре встречается редко. Часто встречается в мире функционального программирования на уровне Run-Time/Вирт. машины.

----

#### Wavefront

1. Комбинация систолической архитектуры с асинхронным потоковым исполнением.
1. Управление происходит динамически, за счёт распространения сигнала по сети.
1. Синхронизация и режим работы выстраиваются динамически.
1. Проще в программировании. Лучше масштабируется.
1. Риски переполнения буферов в Run-Time.

</div><div class="col">

![](/fig/wavefront.png)

</div></div>

---

### Coarse-Grained Reconfigurable Architecture

Выводы из классификаций Флинна и Дункана:

1. Огромное разнообразие подходов к построению процессора.
2. Противоречие между пространственными и временными вычислениями (Spatial & Temporal Computation).
3. Противоречие между универсальностью и эффективностью.

Выделяется ниша:

- Domain-Specific Flexibility ("Предметно-специально гибких").
- Сочетающих пространство и время.
- Управляемых конфигурацией и данными (Configuration / Data-driven execution).

Заполняется крупно-гранулярно реконфигурируемыми архитектурами — **CGRA**.

----

#### CGRA: Hybrid Spatial & Temporal Computation

CGRA архитектура определяет (снизу-вверх):

1. вычислительные блоки доступны и с какими интерфейсами (данные/управление);
1. коммуникацию между вычислительными блоками;
1. механика управления процессором;
1. механика планирования вычислительного процесса;
1. программы и программирование.

</div><div class="col">

![](/fig/cgra-alg.png)

![](/fig/cgra-temporal-spatial.png)

1. Крайне разнообразны, не имеют проработанной теории.
1. Являются актуальным направлением в развитии процессоров.

</div></div>

----

#### CGRA Classification

![](/fig/cgra-classification.png)

----

#### CGRA. Computation model

![](/fig/cgra-computation-model.png)

- **SСSD** — single configuration, single data
- **SCMD** — single configuration, multiple data
- **MCMD** — multiple configuration, multiple data

----

#### CGRA. Execution Model

![](/fig/cgra-exec-model.png)

----

#### CGRA: Challenges & Trends

![](/fig/cgra-trends.png)