edu-csa

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

## Лекция 14

### Уровневая организация. <br/> Языки высокого уровня. <br/> Низкоуровневый параллелизм

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

---

## Уровневая организация

это естественный способ организации вычислительных систем

Примеры:

1. Lava Flow или уровневая организация курильщика $\longrightarrow$
1. Уровневый архитектурный стиль (Layered Style)
1. OSI Model
1. Уровни организации вычислительного процесса

Количество уровней — десятки.

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

![](/fig/lava-antipattern.jpeg)

</div></div>

----

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

![](/fig/style-layered.png)

- Изоляция, модифицируемость и переносимость
- Управление сложностью и структура кода разработчикам
- Разделения интересов

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

(**Layered Style**)

![](/fig/style-layered-2.png)

![](/fig/style-layered-3.png) 
![](/fig/style-layered-4.png)

</div></div>

----

### Open Systems Interconnection (OSI) Model

Зачем уровни? Обеспечить **модульность** и **вариативность**.

1. Application Layer
1. Presentation Layer
1. Session Layer
1. Transport Layer
1. Network Layer
1. Data Link Layer
1. Physical Layer

Что неверно в визуализации?

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

![](/fig/osi-meme.png)

</div></div>

----

### Уровни организации выч. процесса

![](/fig/platform-general-view.png)

1. Layered project organization.
1. Frameworks, библиотеки, API.
1. Языки программирования.
1. Операционные системы.
1. Системы команд (ISA), ПЛИС.
1. Виртуализированные ресурсы.

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

![](/fig/vertical-horizontal-arch.png)

</div></div>

----

### Разделение на уровни (Disaggregation)

![](/fig/platform-disaggregation.png)

- Интегрированные решения <br/> (in-house). Уровни переплетены и адаптированы.

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

- Уровни разделены по индустриям/специальностям.
- Эффект масштаба.
- Независимое существование. Закон Мура. [Proebsting's Law](https://proebsting.cs.arizona.edu/law.html)

</div></div>

----

### Смешение уровней. Интеграция

![](/fig/platform-levels-mix-for-realtime.jpg)

1. Зачем: для обеспечения системных характеристик: энергопотребление, реальное время, производительность.
1. Смешение уровней $\longrightarrow$ рост связанности и сложности системы.
1. Смешение уровней при разработке.
1. Сквозные инструментальные решения.

----

### Документирование. Граф актуализации

1. Цепочка преобразований моделей выч. процесса через:
    - стадии жизненного цикла <br/> (Design $\rightarrow$ Dev $\rightarrow$ Use),
    - вычислительные платформы (High- $\rightarrow$ Low-level Langs $\rightarrow$ ISA $\rightarrow$ HW $\rightarrow$ Physic).
1. Ориентированный ациклический граф, вершины — модели, рёбра — трансляции/интерпретации.
1. Назначение: анализ инструментальных цепочек.

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

![](/fig/actualization-graph-adv.png)

</div></div>

Подробности: [Разработка и исследование архитектурных стилей проектирования уровневой организации встроенных систем](http://fppo.ifmo.ru/?page1=16&page2=52&page_d=1&page_d2=142415)

---

## Вокруг процессора фон Неймана

1. Параллелизм уровня инструкций, <br/> (Low-Level Parallelism):
    - Суперскалярность
    - VLIW
1. Языки программирования высокого уровня. Структурное программирование.

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

![](/fig/vertical-horizontal-arch-high-lang-instr-parallelism.png)

</div></div>

---

## Низкоуровневый параллелизм <br/> (Low-Level Parallelism)

("не влияет" на прикладное программирование)

1. **Конвейеризация**. Разбиение выполнения инструкции на последовательность этапов.
1. **Множественные функциональные узлы в ЦПУ**. Независимые функциональные блоки для арифметических и булевых операций, выполняемых одновременно.
    - Суперскалярный процессор
    - Very Long Instruction Word

---

### Суперскалярный процессор

Проблемы:

- разные операции выполняются в разное время (сумма, деление);
- простаивание конвейера во время длинных операций.

Решение:

- анализ потока инструкций на лету и автоматическая параллелизация инструкций, прозрачная для программиста.

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

![Concept of a superscalar processor](/fig/superscalar-processor-two-unit.png)

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

----

#### Суперскалярный процессор. Структура

1. Инструкции читаются в очередь команд по порядку.
1. Декодируются и перемещаются на станции резервирования.
1. Станции резервирования выполняют переупорядочивание:
    - по мере доступности данных;
    - по мере доступности вычислительных ресурсов.

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

![](/fig/proc-superscalar-processor-organisation.png)

</div></div>

Notes: 18-600 Foundations of Computer Systems, Carnegie Mellon University, J.P. Shen

----

#### Суперскалярный процессор. Достоинства

1. Рост производительности. Сглаживание длительности выполнения инструкций.
1. Повышение уровня загрузки ресурсов.
1. Совместимость с существующим машинным кодом.
1. Компилятор может устранить значительное количество конфликтов за счёт сортировки инструкций.

#### Суперскалярный процессор. Недостатки

1. Конфликты по данным оказывают значительное влияние на производительность и сложность процессора.
1. Высокое энергопотребление.
1. Проблемы детерминированности работы многоядерных процессоров.

----

#### Барьеры памяти (Fence)

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

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

```с
// Processor 1:
while (f == 0);
// Memory fence required here
print(x);

// Processor 2:
x = 42;
// Memory fence required here
f = 1;
```

![](/fig/barrier-effect-example.png)

</div></div>

---

### Very Long Instruction Word (VLIW)

**RISC**: упростим процессор за счёт языков высокого уровня!

**VLIW**: упростим процессор за счёт переноса параллелизма инструкций в compile-time!

1. Много АЛУ.
1. Объединим несколько инструкций в одну.
1. Уберём из механизмы суперскаляра.
1. Компилятор знает всё $\longrightarrow$ максимальная оптимизация и параллелизм.

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

![](/fig/superscalar-and-vliw-scheme.png)

</div></div>

----

#### VLIW. Система команд и устройство

![](/fig/vliw-isa.png)

----

#### VLIW. Достоинства

1. Упрощение процессора, снижение энергопотребления.
1. Упрощение декодера. Рост частоты.
1. Компилятор имеет больше информации о коде, он лучше знает, что параллельно!

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

#### VLIW. Недостатки

1. Сложность компилятора.
1. Высокая нагрузка на каналы данных и регистровые файлы.
1. Конфликты конвейера приводят к простою всех узлов.
1. Проблемы условных переходов.
1. Низкая плотность кода.
1. Ширина команды — огр. микроархитектуры.

</div></div>

![](/fig/cisc-risc-vliw-isa.png)

Notes: <https://www.isi.edu/~youngcho/cse560m/vliw.pdf>

---

### VLIW vs. Superscalar

(структурированный поток vs. просто поток инструкций)

![](/fig/proc-superscalar-vs-vliw.jpg)

----

### Уровневая организация. <br/> Суперскаляр $\longleftrightarrow$ VLIW

![](/fig/proc-superscalar-epic-vliw.png)

Notes: Understanding EPIC Architectures and Implementations, Mark Smotherman, <https://people.computing.clemson.edu/~mark/464/acmse_epic.pdf>

---

## Языки высокого уровня

Инструкции и Go To $\rightarrow$ Структурные блоки и их последовательность

1. Естественные элементы для архитектуры фон Неймана:
    - последовательный код$^*$,
    - условный оператор$^*$,
    - циклы, подпрограммы.
1. Распределение регистров. Математические выражения.
1. Функции, области видимости и автоматическая память.
1. Исключения, состояния и перезапуски.$^{**}$
1. Полиморфизм. Замыкания.$^{**}$

- $^*$ — переосмыслены.
- $^{**}$ — опустим.

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

![](/fig/structural-programming.png)
![](/fig/structural-programming-proc.png) 
Подробности: [Курс ФП. История](https://gitlab.se.ifmo.ru/functional-programming/main)

</div></div>

----

### Распределение регистров. Выражения

![](/fig/proc-prog-instruction-selection.png) 
![](/fig/proc-prog-reg-allocations.png)

1. Проблемы:
    - кол-во регистров конечно (ARM 15/31, x86 8/16, MIPS 32/32),
    - не все регистры одинаковы (особенно в CISC).
1. Проблема компилятора или программиста низкого уровня.
1. Код не ограничивается выражениями.
1. Согласование использования регистров между вызовами процедур.

----

#### Раскраска регистров

![](/fig/register-allocation.png)

$R_1, R_2$ — регистры аргументов.

$R_{LK}$ — возврат, $R_1$ — результат.

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

Источник: [Register allocation](https://cs420.epfl.ch/archive/20/c/08_reg-alloc.html)

В статье пример с Lisp.

</div></div>

---

### Подпрограммы. Процедуры

1. Зачем:
    - переиспользование машинного кода,
    - оптимизация работы кеша инструкций.
1. Инструкции:
    - Через `inline`.
    - Через `goto`.
    - Через `call`, `return`.
1. Данные: рабочая память выделена статически.
1. Нет реентерабельности.
1. Проблемы: кеширование, сброс регистров, переходы и конвейер.

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

```c
int *x, *y;
void *SWAP_RET;
int tmp;

swap:
    tmp = *x;
    *x = *y;
    *y = tmp;
    goto SWAP_RET;
```

```c
int tmp;

void swap(int *x, int *y) {
    tmp = *x;
    *x = *y; // прерывание: isr()
    *y = tmp;
}

int a, b;

void isr() {
    a = 1;
    b = 2;
    swap(&a, &b);
}
```

</div></div>

----

#### Реентерабельность. Рекурсивный вызов

1. Реализация через `call`, `return`.
    - Статическое выделение памяти для каждого входа.
    - Автоматическая память, стек: `push`, `pop` (рекурсия).
1. Зачем:
    - параллелизм уровня задач,
    - рекурсивные алгоритмы.
1. Проблемы: автоматическая память, утечки данных, перезапись адреса возврата.

```c
int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n - 1);
}
```

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

```c
struct swap {int* x; int* y; int tmp;};

void swap(struct swap* base) {
    base->tmp = *(base->x);
    *(base->x) = *(base->y);
    *(base->y) = base->tmp;
}

struct swap enter1, enter2;
swap(&enter1);
swap(&enter2);

void swap(int* x, int* y) {
    int tmp; // reserve mem
    tmp = *x;
    *x = *y;
    *y = tmp;
}
```

![](/fig/prog-recursive-procedure.png)

</div></div>

---

### Переосмысление условного оператора

- (1) Традиционный подход: встроенная конструкция языка, реализуемая инструментарием (компилятор, интерпретатор).
- (2) Полиморфизм + замыкания (анонимные функции). Smalltalk.

```smalltalk
Bool subclass: #Object !

True subclass: #Bool
  ifTrue: aBlock ifFalse: bBlock
    ^ aBlock value ! !

False subclass: #Bool
  ifTrue: aBlock ifFalse: bBlock
    ^ bBlock value ! !
```

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

```smalltalk
(17 * 13 > 220).
>>>true

(17 * 13 > 220)
       ifTrue: [ 'bigger' ]
       ifFalse: [ 'smaller' ].
>>>'bigger'

n := 1.
[ n < 1000 ] whileTrue: [ n := n*2 ].
n
>>> 1024
```

</div></div>

----

- (3) Нормальный порядок вычислений. Ленивые вычисления.

Охватывающее выражение полностью редуцируется, применяя функции до вычисления аргументов (с кешированием).

```python
def my_if(cond, if_true, if_false):
    if cond:
        if_true
    else:
        if_false

my_if(True,
      print("foo"),
      print("bar"))
```

```python
if True:
    print("foo")
else:
    print("bar")
```

```python
print("foo")
```

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

Нормальный порядок (~макросы)

``` go
#define square(X) ((X) * (X))

x = square(1 + 2);
-> x = ((1 + 2) * (1 + 2));
```

Ленивые вычисления:

```haskell
let square x = x * x
 in square (1 + 2)
--
let square x = x * x
    tmp = 1 + 2
 in square tmp
--
let square x = x * x
    tmp = 1 + 2
 in tmp * tmp
```

</div></div>

---

### Переосмысление последовательного кода

- (1) Optional Chaining (Swift).

Глубокий JSON с опциональными полями.

```swift
let string: String? = "hello" // or nil
let count = string?.count
if count != nil {
    print(count!)
}
```

----

- (2) `async/await`

То, что выглядит последовательным кодом, им не является (кооперативная многозадачность).

```python
import asyncio

async def main():
    print('hello')
    await asyncio.sleep(1) # будет возвращено замыкание, с оставшимся
                           # кодом, которое будет выполнено после
                           # завершения sleep.
    print('world')

asyncio.run(main()) # asyncio.run обеспечивает ожидание асинхронных
                    # функций и запуск соответствующих замыканий.
                    # (кооперативная многозадачность)
```

----

- (3) Монады. Явно определяем операцию связывания (`bind`, `>>=`):
    - результата прошлого шага
    - и действия следующего шага.

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

```haskell
class Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b

instance Monad Maybe where
    return :: a -> Maybe a
    return x = Just x

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
    Nothing >>= _ = Nothing
    Just x  >>= f = f x

string = Just "hello"
count = string >>= (\s -> return (length s))
```

Async/Await — см. библиотеку lwt для OCaml.

Детали: см. курс [Функционального программирования](https://gitlab.se.ifmo.ru/functional-programming/main).