Алгоритм Томасуло

Сентябрь 3, 2022

Главная
Алгебра
Алгоритм Томасуло

Содержание

2. Алгоритм Тамасуло Разрешение конфликтов RAW происходит за счет запуска инструкции, только когда готовы ее операнды. Устранение
3. Схема процессора для реализации алгоритма Тамасуло
4. Состав процессора Очередь планирования (Instruction queue)[ОП] Регистровый файл (FP Registers) [РФ] Станции резервирования (Reserve Station) [СР]
5. Схема процессора для реализации алгоритма Тамасуло
6. Этапы исполнения инструкции Классический конвейер Выборка инструкции Выборка операндов Исполнение Сохранение результата Алгоритм Тамасуло Выборка инструкции
7. Устройство СР Состоит из двух дескрипторов операндов. Дескриптор операнда содержит значение операнда или ссылку, если значение
8. Планирование инструкций Выборка с вершины ОП. Выборка происходит по 1 инструкции за такт. Выборка осуществляется в
9. Ожидание готовности операндов, исполнение, сохранение результатов Инструкция ожидает в СР до тех пор, пока не будут
10. Обработка инструкций загрузки и сохранения. Инструкция загрузки: Вычисление адреса Выполнение загрузки по адресу Инструкция сохранения: Вычисление
11. Порядок исполнения инструкций загрузки и сохранения. Определяется наличием зависимостей между инструкциями по ячейкам памяти. Адреса ячеек
12. Файл переименования Находиться в РФ. Содержит имена переименованных регистров. Состоит из двух полей: Если значение находиться
13. Пример 1 1. L.D F6,34(R2) 2. L.D F2,45(R3) 3. MUL.D F0,F2,F4 4. SUB.D F8,F2,F6 5. DIV.D
14. Обозначения Op — операция, которая будет выполняться Vj, Vk— готовые значения операндов. Qj, Qk— ссылка на
15. Такт 0
16. Такт 1
17. Такт 2
18. Такт 3
19. Такт 4
20. Такт 5
21. Такт 6
22. Такт 7
23. Такт 8
24. Такт 9
25. Такт 10
26. Такт 11
27. Такт 12
28. Такт 15
29. Такт 16
30. Такт 56
31. Такт 57
32. Пример 2 1. L.D F6,34(R2) 2. L.D F2,45(R3) 3. MUL.D F0,F2,F4 4. SUB.D F8,F2,F6 5. DIV.D
33. Такт 0
34. Такт 4
35. Такт 5
36. Такт 6
37. Такт 7
38. Такт 8
39. Такт 9
40. Такт 15
41. Такт 16
42. Такт 17
43. Такт 18
44. Такт 19
45. Такт 20
46. Такт 21
47. Такт 57
48. Такт 58
49. Общее описание алгоритма
50. Достоинства и недостатки алгоритма. Достоинства: Повышение пропускной способности Уменьшение времени простоя процессора Недостатки Большие аппаратные затраты
52. Скачать презентацию

Слайд 2

Алгоритм Тамасуло
Разрешение конфликтов RAW происходит за счет запуска инструкции, только когда

готовы ее операнды.
Устранение WAR и WAW конфликтов происходит за счет переименования регистров с использованием станций резервирования (Reserve Station).
RS используются для хранения операндов инструкции и воссоздания графа зависимостей по данным между инструкциями, которые находятся в исполнении.

Слайд 3

Схема процессора для реализации алгоритма Тамасуло

Слайд 4

Состав процессора
Очередь планирования (Instruction queue)[ОП]
Регистровый файл (FP Registers) [РФ]
Станции резервирования (Reserve

Station) [СР]
Простое вещественное устройство (FP adder)
Сложное вещественное устройство (FP Muliplier)
Общая шина данных (Common Data Bus)[ОШД]
Устройство вычисление адреса (Address Unit)
Буфера загрузки (Load buffer)
Буфера сохранения (Store buffer)
Устройство работы с памятью (Memory Unit).

Слайд 5

Схема процессора для реализации алгоритма Тамасуло

Слайд 6

Этапы исполнения инструкции
Классический конвейер
Выборка инструкции
Выборка операндов
Исполнение
Сохранение результата
Алгоритм Тамасуло
Выборка инструкции
Планирование инструкции
Ожидание

готовности операндов
Исполнение
Сохранение результата

Слайд 7

Устройство СР
Состоит из двух дескрипторов операндов.
Дескриптор операнда содержит значение операнда или

ссылку, если значение операнда на момент планирования еще не вычислено.
Ссылка - это номер СР, который содержит инструкцию вычисляющую данный операнд.

Слайд 8

Планирование инструкций
Выборка с вершины ОП.
Выборка происходит по 1 инструкции за

такт.
Выборка осуществляется в программном порядке, так как очередь FIFO
Декодирование.
Назначение на исполнительное устройство.
Если все СР устройства заняты, то инструкция возвращается в ОП и ожидает освобождения RS.
Выборка операндов.
Если операнды вычислены, то они выбираются из РФ, если нет то в дескрипторах СР устанавливается ссылки на другие СР.

Слайд 9

Ожидание готовности операндов, исполнение, сохранение результатов
Инструкция ожидает в СР до тех

пор, пока не будут вычислены все ее операнды и записаны в соответствующие дескрипторы.
Передача вычисленного операнда происходит по ОШД вместе с номером СР, который его содержал.
Каждая СР слушает ОШД и сравнивает значение номер передаваемого по ней СР с ожидаемым. Если номера совпадает то она забирает значение операнда с ОШД.
Передаваемые по ОШД данные сохраняются в РФ.
Если все операнды находятся СР, то инструкция отправляется на исполнение.

Слайд 10

Обработка инструкций загрузки и сохранения.
Инструкция загрузки:
Вычисление адреса
Выполнение загрузки по

адресу
Инструкция сохранения:
Вычисление адреса
Ожидания готовности операнда.
Выполнение сохранения по адресу.
Буфер загрузки: поле адреса.
Буфер сохранения: поле адреса, СР для операнда.

Слайд 11

Порядок исполнения инструкций загрузки и сохранения.
Определяется наличием зависимостей между инструкциями

по ячейкам памяти.
Адреса ячеек вычисляются на первом этапе.
Инструкция загрузки ожидает завершения всех предшествующих инструкций сохранения по данному адресу.
Инструкция сохранения ожидает завершения всех предшествующих инструкций загрузки и сохранения по данному адресу.

Слайд 12

Файл переименования
Находиться в РФ.
Содержит имена переименованных регистров.
Состоит из двух полей:
Если значение

находиться в регистре, то ссылка равна нулю, если нет то ссылка указывает на СР, которая его вычислит.

Слайд 13

Пример 1
1. L.D F6,34(R2)
2. L.D F2,45(R3)
3. MUL.D F0,F2,F4
4. SUB.D F8,F2,F6
5. DIV.D

F10,F0,F6
6. ADD.D F6,F8,F2

Допущения
Латентность загрузки/сохранения : 2
Латентность сложения/вычитания : 2
Латентность умножения : 10
Латентность деления: 40
СР для загрузки/сохранения: 3
СР для простых арифм. орпер. : 3
СР для сложных арифм. орпер. : 2
Планирование инструкций происходит отдельно от процесса исполнения.

Слайд 14

Обозначения
Op — операция, которая будет выполняться
Vj, Vk— готовые значения операндов.
Qj, Qk—

ссылка на СР, на которой будет рассчитан соответствующий операнд. Значение «0» – данные записаны в Vj или Vk соответственно.
Busy — флаг занятости.
Issue — стадия планирования инструкции.
Complete — стадия выполнения и завершения выполнения.
Result — стадия сохранения результата

Слайд 15

Такт 0

Слайд 16

Такт 1

Слайд 17

Такт 2

Слайд 18

Такт 3

Слайд 19

Такт 4

Слайд 20

Такт 5

Слайд 21

Такт 6

Слайд 22

Такт 7

Слайд 23

Такт 8

Слайд 24

Такт 9

Слайд 25

Такт 10

Слайд 26

Такт 11

Слайд 27

Такт 12

Слайд 28

Такт 15

Слайд 29

Такт 16

Слайд 30

Такт 56

Слайд 31

Такт 57

Слайд 32

Пример 2
1. L.D F6,34(R2)
2. L.D F2,45(R3)
3. MUL.D F0,F2,F4
4. SUB.D F8,F2,F6
5. DIV.D

F10,F0,F6
6. ADD.D F6,F8,F2

Допущения
Латентность загрузки/сохранения : 2
Латентность сложения/вычитания : 2
Латентность умножения : 10
Латентность деления: 40
СР для загрузки/сохранения: 3
СР для простых арифм. орпер. : 3
СР для сложных арифм. орпер. : 1
Планирование инструкций происходит отдельно от процесса исполнения.

Слайд 33

Такт 0

Слайд 34

Такт 4

Слайд 35

Такт 5

Слайд 36

Такт 6

Слайд 37

Такт 7

Слайд 38

Такт 8

Слайд 39

Такт 9

Слайд 40

Такт 15

Слайд 41

Такт 16

Слайд 42

Такт 17

Слайд 43

Такт 18

Слайд 44

Такт 19

Слайд 45

Такт 20

Слайд 46

Такт 21

Слайд 47

Такт 57

Слайд 48

Такт 58

Слайд 49

Общее описание алгоритма

Слайд 50

Достоинства и недостатки алгоритма.
Достоинства:
Повышение пропускной способности
Уменьшение времени простоя процессора
Недостатки
Большие аппаратные

затраты на реализацию дополнительных устройств.

Алгоритм Томасуло

Содержание

Алгоритм ТамасулоРазрешение конфликтов RAW происходит за счет запуска инструкции, только когда

Схема процессора для реализации алгоритма Тамасуло

Состав процессораОчередь планирования (Instruction queue)[ОП]Регистровый файл (FP Registers) [РФ]Станции резервирования (Reserve

Схема процессора для реализации алгоритма Тамасуло

Устройство СРСостоит из двух дескрипторов операндов.Дескриптор операнда содержит значение операнда или

Планирование инструкцийВыборка с вершины ОП. Выборка происходит по 1 инструкции за

Ожидание готовности операндов, исполнение, сохранение результатовИнструкция ожидает в СР до тех

Обработка инструкций загрузки и сохранения. Инструкция загрузки: Вычисление адресаВыполнение загрузки по

Порядок исполнения инструкций загрузки и сохранения. Определяется наличием зависимостей между инструкциями

Файл переименованияНаходиться в РФ.Содержит имена переименованных регистров.Состоит из двух полей:Если значение

Пример 11. L.D F6,34(R2)2. L.D F2,45(R3)3. MUL.D F0,F2,F44. SUB.D F8,F2,F65. DIV.D

Обозначения Op — операция, которая будет выполняться Vj, Vk— готовые значения операндов. Qj, Qk—

Такт 0

Такт 1

Такт 2

Такт 3

Такт 4

Такт 5

Такт 6

Такт 7

Такт 8

Такт 9

Такт 10

Такт 11

Такт 12

Такт 15

Такт 16

Такт 56

Такт 57

Пример 21. L.D F6,34(R2)2. L.D F2,45(R3)3. MUL.D F0,F2,F44. SUB.D F8,F2,F65. DIV.D

Такт 0

Такт 4

Такт 5

Такт 6

Такт 7

Такт 8

Такт 9

Такт 15

Такт 16

Такт 17

Такт 18

Такт 19

Такт 20

Такт 21

Такт 57

Такт 58

Общее описание алгоритма

Достоинства и недостатки алгоритма.Достоинства:Повышение пропускной способности Уменьшение времени простоя процессораНедостаткиБольшие аппаратные

Похожие презентации

Алгоритм Тамасуло
Разрешение конфликтов RAW происходит за счет запуска инструкции, только когда

Состав процессора
Очередь планирования (Instruction queue)[ОП]
Регистровый файл (FP Registers) [РФ]
Станции резервирования (Reserve

Устройство СР
Состоит из двух дескрипторов операндов.
Дескриптор операнда содержит значение операнда или

Планирование инструкций
Выборка с вершины ОП.
Выборка происходит по 1 инструкции за

Ожидание готовности операндов, исполнение, сохранение результатов
Инструкция ожидает в СР до тех

Обработка инструкций загрузки и сохранения.
Инструкция загрузки:
Вычисление адреса
Выполнение загрузки по

Порядок исполнения инструкций загрузки и сохранения.
Определяется наличием зависимостей между инструкциями

Файл переименования
Находиться в РФ.
Содержит имена переименованных регистров.
Состоит из двух полей:
Если значение

Пример 1
1. L.D F6,34(R2)
2. L.D F2,45(R3)
3. MUL.D F0,F2,F4
4. SUB.D F8,F2,F6
5. DIV.D

Обозначения
Op — операция, которая будет выполняться
Vj, Vk— готовые значения операндов.
Qj, Qk—

Пример 2
1. L.D F6,34(R2)
2. L.D F2,45(R3)
3. MUL.D F0,F2,F4
4. SUB.D F8,F2,F6
5. DIV.D

Достоинства и недостатки алгоритма.
Достоинства:
Повышение пропускной способности
Уменьшение времени простоя процессора
Недостатки
Большие аппаратные