Параллелизм уровня команд. Типы зависимостей

Зависимость между инструкциями

зависимость по данным;
зависимость по именам;
зависимость по управлению.

Зависимость по данным.

Инструкция J зависит по данным от инструкции I если

Зависимость по данным (пример).

Loop: L.D F0,0(R1)
ADD.D F4,F0,F2
S.D F4,0(R1)
DADDIU R1,R1,-8
BNE R1,R2,Loop

Связь между инструкциями

Через регистры
Просто выявить на этапе компиляции. Связь по

Зависимость по именам.

Две инструкции зависят по именам, если использую одинаковые регистры

Тип зависимости по именам

1. Анти зависимость
между инструкциями I и J

Пример зависимостей по именам.

DIV.D F0,F2,F4
ADD.D F6,F0,F8
S.D F6,0(R1)
SUB.D F8,F10,F14
MULT.D F6,F10,F8

Анти зависимость
Зависимость по

Базовый блок

Это максимальная непрерывная последовательность инструкций, в которой не происходит ветвления,

Граф потока управления (Control Flow Graph)

Узлами графа являются базовые блоки.
Направленная дуга

Пример граф потока управления

Зависимость по управлению

Это зависимость всех инструкций базового блока от инструкции ветвления,

Пример зависимости по управлению

mov ebx, mas
mov edx, res
xor esi,esi

m1:
mov eax,[ebx+esi]
add

Граф потока данных.

Узлы графа – инструкции.
Дуга связывает инструкцию производителя с инструкциями

Критерии сохранения корректности программы

1. Сохранение потока данных
Поток значений передаваемых между инструкциями

Когда применяются критерии?

1. При перестановки инструкции в программе.
2. При переходе от

Сохранение потока данных (пример).

DADDU R1,R2,R3
BEQZ R4,L
DSUBU R1,R5,R6
L:
OR R7,R1,R8

DADDU R1,R2,R3
BEQZ R12,skipnext
DSUBU R4,R5,R6
DADDU