dz2

Интел Студия – Архитектура микропроцессоров
Домашнее задание 2
Рассмотрим следующий код MIPS
LD R0, 12(SP)
DSUB R4, R0, R2
DADD R8, R1, R0
AND R9, R2, R1
BNEZ R8, label1
DADD R5, R4, R1
ADD R11, R4, R0
Идентифицируйте каждую зависимость: перечислите инструкции, данные, по которым существует зависимость, тип зависимости (2 балла)
Примем, что процессора MIPS имеет пятиступенчатый конвейер (с его структурой можно ознакомиться с помощью лекционного материала или же воспользуйтесь приложением А книги Хеннеси и Паттерсона, ссылка на материал размещена в конце файла). Примем, что регистровый файл пишется в первой половине цикла процессора (например, по нарастающему фронту тактового сигнала), а читается во второй половине цикла процессора (соответственно, по ниспадающему фронту тактового сигнала). Какие из зависимостей, перечисленных в пункте (а), при прохождении этой последовательности команд в конвейере становятся конфликтами, и какую задержку в тактах вводит каждый конфликт? (Примем, что forwarding-логика в данной реализации конвейера отсутствует.)(3 балла)
Рассмотрим следующий код: label1: LD R1, 0(R2) DADDI R1, R1, #1 SD 0(R2), R1 DADDI R2, R2, #4 DSUB R4, R3, R2 BNEZ R4, label1 предположим, что начальное значение R3 = R2+96, конвейер процессора имеет 5 стадий (рисунок А.1 из Хеннеси и Паттерсона, см. в конце файла), доступ в память занимает 1 цикл (т.е. 0 тактов задержки).
Покажите расписание прохождения инструкций в конвейере, в котором отсутствует оборудование для bypass и forwarding, но учитывая, что чтение и запись из/в регистрового файла в одном такте представляет собой своеобразный forward (см. рис. А.6, см. конец файла). Примем, что инструкция перехода очищает конвейер. Если все обращения к памяти занимают 1 такт, рассчитайте (и проиллюстрируйте таблицей) время исполнения последовательности команд в описанном конвейере. (7 баллов)
Покажите расписание прохождения инструкций в конвейере, в котором присутствует типичное оборудование (описанное в лекциях) для bypass и forwarding (см. рис. А.6, см. конец файла). Примем, что исполнение перехода осуществляется, как будто исполнение ни одного перехода не предсказано верно. Если все обращения к памяти занимают 1 такт, рассчитайте (и проиллюстрируйте таблицей) время исполнения последовательности команд в описанном конвейере. (7 баллов)
Покажите расписание прохождения инструкций в конвейере, в котором присутствует типичное оборудование (описанное в лекциях) для bypass и forwarding, кроме того, используются переходы с задержкой исполнения на один такт. Сделайте расписание этих инструкций в виде цикла, включая слот задержки исполнения перехода. Возможна перестановка инструкций и изменение их операндов, но не трансформации, изменяющие количество инструкций или их код операции. Если все обращения к памяти занимают 1 такт, рассчитайте (и проиллюстрируйте таблицей) время исполнения последовательности команд в описанном конвейере. (7 баллов)
До появления на рынке RISC и CISC архитектур, доминирующими архитектурами на рынке были процессоры с аккумуляторным регистром и стековые машины (см. рис. 2.1 и 2.2 Хеннеси и Паттерсон - они приведены в конце файла). Оба этих типа архитектур могли быть реализованы с помощью сравнительно небольшого числа логических вентилей. Однако, причиной вытеснения с рынка этих архитектур является не только удешевление транзисторов и возможность размещения большего количества вентилей на подложке при уменьшении цены микросхемы. Рассмотрим причины смены архитектуры процессоров.
Рассмотрим следующий фрагмент кода C = A+B E = D-C Используя рисунок 2.2 из Хеннеси и Паттерсона, напишите последовательности инструкций для исполнения это фрагмента для стековой, аккумуляторной и load-store архитектуры. (Примем, что для стековой архитектуры инструкция вычитания вычитает вершину стека из под-вершины стека. Пример, что вычитание для аккумуляторной архитектуры вычитает значение из памяти из аккумулятора. Используйте разные регистры для различных значений для load-store архитектуры.) Тщательно изучите зависимости в написанном коде. Для каждой зависимости перечислите команды, участвующие в зависимости, данные, тип зависимости. Проанализируйте архитектуры с точки зрения их потенциала для выделения параллелизма на уровне инструкций. Расположите архитектуры по степени возрастания этого потенциала. (5 баллов)
Для ваших кодов опишите расписания инструкций, которые может сгенерировать компилятор для каждой архитектуры. (4 балла)
У алгоритма Томасуло есть один недочёт: за один цикл через одну шину данных может быть сохранён только один результат.
Используя рисунки 3.2 (архитектура системы) и 3.63 [в электронной версии книги 3.64] (длительности выполнения команд) из Хеннеси и Паттерсона (они расположены далее в файле), напишите последовательность команд из не более 10 инструкций, которые при исполнении алгоритма Томасуло приводят к конфликту из-за конкуренции за занятие шины CDB. Покажите, где в последовательности команд происходит этот конфликт. (7 баллов)
Обобщите ваше решение для предыдущего пункта – опишите характеристики последовательности инструкций, которые приводят к структурному конфликту в системе с n шинами CDB. (10 баллов)
Примем, что таблица (буфер) адресов переходов предполагает соответствующие штрафы в 0, 2 и 2 цикла процессора для корректного предсказания условного перехода, некорректного предсказания перехода и ненахождения инструкции в буфере. Примем, что конструкция буфера предусматривает различение условных и безусловных переходов, сохраняя адрес следующей инструкции для условного перехода и копию следующей инструкции для безусловного перехода.
Какой штраф предусмотрен в случае нахождения в буфере безусловного перехода? (5 баллов)
Определите прирост производительности от оптимизации «склеивание переходов» для безусловных переходов. (Детальнее про эту оптимизацию можно прочитать в [ Cкачайте файл, чтобы посмотреть ссылку ]. Кратко: для безусловного перехода, предсказание для которого всегда верно, мы помещаем в таблицу адресов переходов – BTB – не адрес следующее инструкции, а саму следующую инструкцию, которая подаётся непосредственно из BTB в конвейер.) Примем 90% уровень корректного предсказания переходов, процент безусловных переходов в программе – 5%, штраф при ненахождении инструкции в буфере – 2 цикла. Какой прирост производительности будет от такой оптимизации? Какой должен быть (минимальный) процент нахождения инструкций в буфере, чтобы от применения данной оптимизации наблюдался прирост производительности? (10 баллов)
(Дискуссия) Рассмотрим одну из проблем реализации алгоритма Томасуло. Представим себе, что инструкция поступает на станцию резервирования, в то время (в тот же самый такт), пока один из её операндов поступает по шине CDB. Что произойдёт в данном случае? Перед тем, как команда поступает на станцию резервирования, операнды выбираются из регистрового файла, но как только инструкция поступает на станцию, операнды всегда принимаются по CDB. Поскольку и инструкция, и ярлык операнда находятся «в пути» к станции резервирования, этот ярлык не может быть сравнён с ярлыком операнда, который находится на CDB. Возможен ли случай, когда находящаяся на станции резервирования инструкция будет вечно ожидать свой операнд, который был уже пропущен на шине CDB? Как можно решить эту проблему? Возможно, некоторые шаги алгоритма Томасуло придётся разделить по времени. Объясните (проиллюстрируйте) решение. (15 баллов)
Рассмотрим реализацию команд CISC-класса для арифметико-логических операций, где в качестве операнда могут выступать один регистр и одно слово в памяти. Чтобы не усложнять учебную реализацию, примем, что для этих команд возможен только один тип адресации – регистровый косвенный, т.е. полный адрес операнда должен храниться в регистре, возможность использования дополнительного смещения отсутствует. Например, операция ADD R1, R2, (R3) складывает значения регистра R2 и слова памяти, адрес которого задан в регистре R3, и помещает результат в регистр R1. Команды, выполняющие операции в АЛУ над двумя регистровыми операндами остаются в системе команд неизменными. Ответьте на следующие вопросы (во всех случаях мы отталкиваемся от стандартной реализации 5-ти ступенчатого целочисленного конвейера MIPS, описанной в лекции).
Изменится ли порядок традиционных ступеней конвейера при реализации описанной косвенной адресации? Объясните почему. (5 баллов)
Опишите, какая forwarding-логика должна быть добавлена в изменённый конвейер: опишите, откуда, куда и какая информация будет перенаправляться. (7 баллов)
Какие новые конфликты по данным возможны в изменённом конвейере из-за добавления нового режима адресации? Проиллюстрируйте эти конфликты, предоставив последовательность инструкций, создающих конфликт. (7 баллов)
Перечислите все случаи, когда изменённый конвейер (поддерживающий новый режим адресации) будет выполнять некоторую программу за время, отличное от времени выполнения той же последовательности на стандартном (неизменённом) конвейере. Опишите пару последовательностей инструкций (одну последовательность для исходного конвейера, вторую – для изменённого) для иллюстрации этого факта. (8 баллов)
Примем, что все инструкции проходят каждую ступень конвейера за 1 такт. Опишите все случаи, когда процессор с изменённым конвейером может иметь различный CPI по сравнению с процессором со стандартным конвейером для некоторой программы. (8 баллов)
Использование задержанных переходов (способы использования слотов для задержанных инструкций показаны на рис. А.14 Хеннеси и Паттерсон, рисунок приведен в конце файла) может значительно увеличить производительность процессора. Предположим, что есть один слот задержки и конвейер определяет исполнение перехода на второй ступени.
Каков штраф для каждого способа использования слотов при отложенном переходе, если переход исполнен и если не исполнен, и какое условие должно быть выполнено (если есть такие условия), чтобы исполнение переходов было корректным. (5 баллов)
Инструкция перехода типа «отменить-если-не-принят» не исполняет инструкцию в слоте задержки, если переход не выполнен (не принят). Таким образом, компилятору не нужно быть слишком консервативным при заполнении слота задержки (при компиляции программы). Каков штраф для каждого способа использования слотов при отложенном переходе, если переход исполнен и если не исполнен, и какое условие должно быть выполнено (если есть такие условия), чтобы исполнение переходов было корректным. (7 баллов)
Примем, что система инструкций содержит как задержанные перехода, так и переходы типа «отменить если не принят». Когда компилятор должен использовать инструкции перехода каждого типа и откуда (из каких участков кода для каждого примера) должен быть заполнен слот задержки? (8 баллов)
Предположим, архитектура MIPS имеет только один регистровый файл (для целых чисел и чисел с плавающей точкой). Используйте формат таблицы А.22 из Хеннеси и Паттерсон (дана в файле ниже) для конструирования forwarding-таблицы для целочисленных операций и операций с плавающей запятой. Игнорируйте наличие операций деления для целых чисел и чисел с плавающей точкой. (15 баллов)
Рассмотрим варианты реализации алгоритма Томасуло на примере выполнения типичного кода для обработки векторов в цикле. Это цикл DAXPY (double-precision aX plus Y) – основная операция решения СЛАУ методом исключений Гаусса. Следующий код исполняет операцию Y = aX + Y для вектора длиной 100 элементов. Предусловия: R1 = 0, a хранится в F0. lbl1: L.D F2, 0(R1) ; загрузка X(i) MUL.D F4, F2, F0 ; умножение a*X(i) L.D F6, 0(R2) ; загрузка Y(i) ADD.D F4, F4, F6 ; сложить a*X(i) + Y(i) S.D F6, 0(R2) ; сохранить Y(i) DADDUI R1, R1, #8 ; увеличить индекс X на 1 DADDUI R2, R2, #8 ; увеличить индекс Y на 1 DSGTUI R3, R1, #800 ; проверить завершение цикла BEQZ R3, lbl1 ; переход Информация о функциональных устройствах предоставлена в таблице 3.62 Хеннеси и Паттерсон (находится в конце файла – в электронной версии не представлена). Примем, что: - Функциональные устройства процессора не конвейеризированы - Не существует forwarding-логики между функциональными устройствами процессора – результаты передаются по CDB - Ступень исполнения (EX) вычисляет эффективный адрес и производит доступ в память для загрузок и сохранений. Таким образом, конвейер выглядит как IF / ID / IS / EX / WB. - Загрузка из памяти занимает один такт. - Ступени конвейера IS (запуск на выполнение) и WB (запись результата) выполняются за один такт. - Существует 5 слотов буферов загрузки и 5 слотов буферов сохранения. - Примем, что исполнение инструкции BEQZ/BNEQZ занимает 0 тактов.
Используем single-issue алгоритм Томасуло (рис. 3.2 из Хеннеси и Паттерсона представлен ниже в файле) в конвейере с временными параметрами работы конвейера, представленными на рис. 3.63 [в электронной версии 3.64] из Хеннеси и Паттерсон. Укажите количество циклов простоя для каждой инструкции и номера тактов начала исполнения каждой инструкции (т.е. входа на ступень EX) – для трёх первых итераций цикла. Сколько циклов требуется для выполнения одной итерации цикла. Распишите ваш ответ в форме таблицы – по типу таблицы 3.25 из Хеннеси и Паттерсона (приведена ниже в файле). (8 баллов)
Предположим, что конвейер имеет временные параметрами работы, представленные на рис. 3.63 [в электронной версии 3.64] из Хеннеси и Паттерсона, но функциональные устройства полностью конвейеризированы. Предположим two-issue алгоритм Томасуло для процессора с одним целочисленным функциональным устройством, требующим для выполнения один такт (латентность – 0 тактов) для всех целочисленных операций. Укажите количество циклов простоя для каждой инструкции и номера тактов начала исполнения каждой инструкции (т.е. входа на ступень EX) – для трёх первых итераций цикла. Сколько циклов требуется для выполнения одной итерации цикла. Распишите ваш ответ в форме таблицы – по типу таблицы 3.25 из Хеннеси и Паттерсона (приведена ниже в файле). (10 баллов)
Предположим, что используется спекулятивный алгоритм Томасуло, как на рис. 3.29 из Хеннеси и Паттерсона (приведен в конце файла). Временные параметры работы конвейера представлены на рис. 3.63 [в электронной версии 3.64] из Хеннеси и Паттерсон. Примем, что существуют раздельные функциональные устройства для вычисления эффективного адреса, арифметико-логических операций и оценки условия исполнения перехода. Создайте таблицу, такую как таблица 3.34 из Хеннеси и Паттерсона (приведена ниже в файле), в которой распишите выполнение первых трёх итераций цикла. (10 баллов)

Варианты заданий:

Примерное распределение времени по выполнению ДЗ-2:
Задание
За листом бумаги, мин
За компьютером, мин
Макс. Баллы

1
20

5

2
25

21

3
15 – 20

9

4
25

17

5
15

15

6
20

15

7
40

35

8
25

20

9
25-30

15

10
30-40

28

Итого
240 – 280

180


Итого, примерное время выполнения домашнего задания – 4-5 часов. Дополнительные материалы







FU type
Cycles in EX
Numbers of FUs
Number of reservation stations

Integer
1
1
5

FP adder
4
1
3

FP multiplier
15
1
2

Figure 3.62. Information about pipeline function units.

Внимание! Для экономии места рисунки А.6, A.14 и A.22 из книги Хеннеси и Паттерсона размещены во внешнем файле (приложение А), ссылка на который будет дана преподавателем.
Heading 1 Heading 2Default Paragraph Font Table Normal
No List Table GridTimes New Roman+Интел Студия – Архитектура микропроцессоровDmitry Ragozindragozin

Приложенные файлы

  • doc 19087096
    Размер файла: 442 kB Загрузок: 0

Добавить комментарий