Конвейер команд

Конвейеризация вычислений Наиболее важный архитектурный прием повышения производительности – конвейеризация вычислений. Конвейерная обработка в общем случае основана на разделении подлежащей исполнению функции на более мелкие части, называемые ступенями (стадиями) конвейера и выделении для каждой из них отдельного блока аппаратуры. Конвейеризацию используют для повышения производительности таких устройств как операционные устройства, оперативная память. Наибольший эффект достигается при конвейеризации машинного цикла – этапов выполнения команд. Ступени разделяются с помощью буферных регистров или буферной памяти.

First pipelined processor – IBM Stretch (1962). Potential overlap among instructions is called instruction-level parallelism (ILP). Потенциальное совмещение этапов выполнения различных команд называется параллелизмом уровня команд – Instruction Level Parallelism (ILP). There are two largely separable approaches to exploiting of ILP. Dynamic scheduling: hardware-intensive approaches, dominates in superscalar processors. Static scheduling: compiler-intensive approaches, dominate in VLIW-processors (Itanium, Transmeta Crusoe). Процесс выполнения команд состоит из k последовательных стадий (например: IF, D, OA, OF,EX, S).

IFD OAOFEX S IFD OAOFEX S Pipelining allows to overlap different instructions at different stages. I I+1 I+2 I+3 I+4 IF D OAOFEX S D D D D OA OF EX S S S S Unpipelined:

Определение эффективности конвейеров. Для характеристики эффективности используют три метрики: ускорение, эффективность и производительность. Ускорение S – отношение времени обработки без конвейера к времени обработки с конвейером. Наилучшее время T KOН обработки N команд входного потока на конвейере из K стадий и тактовым периодом можно определить следующим способом: T KOН =(K + (N-1)). В процессоре без конвейера общее время выполнения T БЕЗ КОН = NK. S = NK/(K + (N-1)). При N ускорение S K.

Метрики конвейера Эффективность E – доля ускорения, приходящаяся на одну ступень конвейера. E = S/K = N/(K+(N-1)). Третьей метрикой является пропускная способность или производительность P. P = E/ = N/(K+(N-1) ). При N эффективность стремится к 1, а производительность – к частоте тактирования.

Проблемы, возникающие на конвейере CPI – Cycles Per Instructions Pipeline CPI = Ideal pipeline CPI + Structural stalls + + Data hazards stalls + Control hazards stalls By reducing each of the term of the right-hand side, we can minimize the overall pipeline CPI and thus increase IPC (Instruction Per Clock). Структурные конфликты возникают из-за недостатка ресурсов: например, операционных устройств, при одновременном обращении в ОП за командами и данными и др.

Конфликты по данным RAW ( Read After Write ). Рассмотрим команды i и j (i предшествует j). j пытается прочитать операнд-источник раньше, чем i его запишет. WAR ( Write After Read ). j пытается записать результат в приемник прежде, чем i его прочитает. WAW ( Write After Write ). j пытается записать операнд прежде, чем он будет записан командой i.

Устранение конфликтов по данным 1.Программные методы Оптимизирующий компилятор пытается создать такой код, чтобы между командами, которые могут конфликтовать друг с другом, находилось достаточное количество нейтральных команд. В простейшем алгоритме компилятор планирует распределение команд в одном и том же базовом блоке. Базовый блок – это линейный участок последовательности программного кода, в котором отсутствуют команды перехода – за исключением начала и конца блока (переходы внутрь этого участка также должны отсутствовать). Компилятор строит граф зависимости этих команд (потока операндов) и упорядочивает их таким образом, чтобы приостановок было меньше. Для простых конвейеров стратегия планирования на основе базовых блоков вполне приемлема. Однако для сложных конвейеров требуются более сложные алгоритмы.

Аппаратные методы Фактическое разрешение конфликтов возлагается на аппаратные методы (суперскалярные процессоры). Очевидный метод – приостановка. Но он снижает производительность. Применяется переименование регистров для конфликтов типа WAR и WAW. Для конфликтов типа RAW используют прием ускоренного продвижения информации – data forwarding. Применяют тракты опережения и тракты обхода со средствами мультиплексирования. АЛУ с цепями обхода (data bypassing) и ускоренной пересылки (data forwarding) показано ниже.

Bypassing k+1 команда Память данных АЛУ MUXMUX MUXMUX k-команда k команда

Переименование регистров (Registers Renaming) Существенной зависимостью является только RAW. Зависимости WAR и WAW являются несущественными. Причины появления несущественных зависимостей: неоптимизированный программный код, ограниченное количество регистров, стремление к экономии памяти. Пример: L2: mover3, r7 lwr8,(r3) addr3, r3,4 lwr9,(r3) blezr8, r9,L3

Переименование регистров Для преодоления несущественных WAR и WAW зависимостей используется механизм динамического отображения определяемых текстом программы логических ресурсов (ячеек памяти, регистров) на файл внутренних регистров. При этом подходе с одним логическим регистром может быть связано несколько значений в различных физических регистрах. Число физических регистров обычно больше, чем логических. Физические регистры используются для временного хранения результатов до момента разрешения конфликтов по данным, после чего значение из внутреннего физического регистра переписывается в логический регистр.

K1:moveax,17 K2:addeax,ecx K3:movmem1, eax K4:moveax, edx K5:subeax, ecx K6:movmem2, eax После переименования K1:movr2, 17 K2:addr2, r3 K3:movmem1, r2Можно совместить выполнение K4:movr4, r5 К1, К4 K5:subr4, r3 К2, К5 K6:movmem2, r4 К3, К6 WAW RAW WAR ro r1 r2 r3 r4 r5 r39 eax K1 ecx K2 eax K4 ecx K5

Пример конвейера RISC – processor. Basic instructions: LOAD Instruction fetch - IF stage 1. PC Mem, Read 2. Memory[PC] IR 3. PC +4 PC Decoding D stage Operands Addressing OAstage (rb)+disp addr addr Mem, Read OF (EX) stage Mem[addr] rd Write Back

Пример конвейера STORE Instruction fetch IF stage 1. PC Mem, Read 2. Memory[PC] IR 3. PC +4 PC DecodingD stage Operands Addressing OA stage (rb)+disp addr (rs) Mem [addr], Write S (EX) stage

Пример конвейера ADD/SUB Instruction fetch IF stage 1. PC Mem, Read 2. Memory[PC] IR 3. PC +4 PC DecodingD stage (rs), (rt) ALU, ADD EX stage Result rdWB

BR.Z Instruction fetch IF stage PC Mem, Read Memory[PC] IR PC +4 PC Decoding EX stage (PC) + disp Branch address If Branch is taken then Branch address PC,

JMP IF stage Instruction fetch PC Mem, Read Memory[PC] IR PC +4 PC Decoding (PC) + disp Branch address EX stage Branch address PC Load instruction is executed for 5 cycles.

Пример конвейера IF DEX/OA MEM WB MUX PC +4 ICache Reg file DCache MUX PC ALU F/D D/X X/M M/W

Пример конвейера Stages divided by pipeline registers/latches. Pipeline registers Reg. PC contains PC Reg. F/D contains PC, undecoded instruction Reg. D/X contains PC, opcode, regfile[rs1], regfile[rs2], rd Reg. X/M contains opcode, regfile[rs], ALUOUT (result), rd Reg M/W contains ALUOUT (result), MEMOUT (ValM), rd

Data Hazards Pipelines Limitations Structural hazards Data hazards Control hazards Data Hazards Two different instructions use the same storage location. add R1, R2, R3add R1, R2, R3add R1, R2, R3 sub R2, R4, R1sub R2, R4, R1sub R2, R4, R1 or R1, R6, R3or R1, R6, R3or R1, R6, R3 read-after-writewrite-after-read write-after-write (RAW)(WAR)(WAW) true dependence anti-dependence output dependence (real) (artificial) (artificial)

Конфликты по управлению Методы решения проблемы условного перехода Наибольшие проблемы при создании эффективного конвейера обусловлены командами, изменяющими последовательность вычислений: условный и безусловный переход, вызов процедуры, возврат из процедуры. Используется несколько подходов при решении проблемы условного перехода. Самый простой способ – метод выжидания. В этом случае происходит подавление операций на конвейере после того, как будет обнаружена команда условного перехода.

На стадии декодирования команды K3 обнаружено, что K3 - команда условного перехода. После этого команда К4 (уже выбранная) снимается с конвейера. Конвейер приостанавливается (stalls). Новая команда будет загружена на конвейер только после того, как K3 пройдет стадию выполнения EX. Предположим, что происходит переход на команду K15. Тогда на стадии 8 произойдет ее выборка и конвейер будет загружен следующими после нее командами. stall stall stall K1 K2 K3 K15 K16 K K1 K2 K3 K15 K16 K17 IF D OA OF EX S (K4) IF IF D OA OF EX S stall stall stall IF D OA OF EX S

Если конвейер будет приостановлен на три такта на каждой команде условного перехода, то это существенно снижает производительность процессора. При частоте команд условного перехода, равной 30% и идеальном CPI, равном единице, процессор с приостановками условных переходов достигает примерно только половины ускорения, получаемого за счет конвейеризации команд. Снижение потерь от условных переходов является критическим вопросом. Число тактов, теряемых при приостановках из-за условных переходов может быть снижено двумя способами: 1. Обнаружением, является ли переход выполняемым или невыполняемым на более ранних стадиях конвейера. 2. Более ранним вычислением значения адреса перехода.

Метод возврата IF D OA OF EX S IF D OA OF IF D OA IF D IF IF D OA OF EX S K1 K2 K3 K4 K5 K6 K7 K15 K16 K17 Штраф за нарушение естественного порядка выполнения команд Условный переход прогнозируется как невыполняемый. Выполнение программы на конвейере продолжается, как если бы переход вовсе не выполнялся.

Рассмотрим, что происходит, когда на конвейер попадает команда условного перехода. Предположим, что команда K3 оказалась командой условного перехода, передающей управление команде K15. До тех пор, пока команда K3 не пройдет стадию EX, никакой информацией о том, будет переход или нет, устройство управления конвейером не располагает. Предполагается, что переход не происходит. Поэтому после K3 на конвейер подается команда К4, К5, К6 и К7. В случае, показанном на рисунке, после прохождения командой К3 стадии EX (на 7-м такте) выяснилось, что будет переход на K15. На 8-м такте в конвейер была загружена команда K15. На интервале от 9-го до12-го такта ни одна команда с конвейера не сошла. Это и есть штраф за изменение естественной последовательности команд. Этот метод использован в VAX/11.

Предсказание переходов Предсказание переходов является одним из наиболее эффективных способов борьбы с конфликтами по управлению. Идея заключается в том, что еще до момента выполнения команды условного перехода или же сразу после ее поступления делается предположение о наиболее вероятном результате выполнения такой команды (переход произойдет или нет). Последующие команды подаются на конвейер в соответствии с предсказанием. При ошибочном предсказании конвейер необходимо вернуть к состоянию, с которого началась выборка ненужных команд, т.е. очистить конвейер, что эквивалентно приостановке конвейера. Цена ошибки может быть достаточно высокой, но при правильном предсказании имеем большой выигрыш – конвейер функционирует ритмично, без остановок. Выигрыш тем больше, чем выше точность предсказания.

Предсказание переходов (Prediction) Точность предсказания – процентное отношение числа правильных предсказаний к их общему количеству. Доказано, что для того, чтобы снижение производительности конвейера из-за приостановок по управлению не превысило 10%, точность предсказания должна быть выше 97,7%. В зависимости от того, когда и на основе какой информации делается предсказание, используют два подхода: статический и динамический.

Статическое предсказание Статическое предсказание делается на этапе компиляции программы. Используют следующие стратегии: Переход происходит всегда (ПВ); Переход не происходит никогда (ПН); Предсказание определяется по результатам профилирования; Предсказание определяется кодом операции команды перехода; Предсказание зависит от направления перехода; При первом выполнении команды переход имеет место всегда.

При предсказании на основе кода операции предполагается, что для одних команд переход произойдет, а для других – нет. Стратегия ПВ – для команд перехода по условию =0,=0, a ПН – всем остальным командам. Стратегия приводит к успеху более, чем в 75% (по Смиту – 86%). Эффективность предсказания зависит от характера программы. Исходя из направления перехода – переходу назад назначается стратегия ПВ, а переходу вперед – ПН. Для перехода назад фактический переход имеет место в 85% случаев, а для перехода вперед – 65%. В последней стратегии при первом выполнении команды перехода предсказывается, что переход обязательно будет. Точность выше, чем у всех предшествующих. Но этот метод практически нереализуем при больших объемах программ.

Branch Prediction Ветвления бывают случайные и регулярные. Регулярные ветвления довольно хорошо предсказываются на основе предыдущей статистики их выполнения. Случайные ветвления в принципе невозможно предсказать на основании сбора предыдущей статистики их выполнения.

Динамическое предсказание Идея динамического предсказания ветвлений предполагает накопление информации о предшествующих переходах. Решение о наиболее вероятном исходе команды условного перехода принимается, исходя из этой информации. Динамические стратегии по сравнению со статическими, обеспечивают более высокую точность предсказания. Динамические предсказатели ветвления производят анализ предыстории выполнения перехода. Каждой команде перехода ставится в соответствие один или несколько битов прогноза. В самом простом случае рассматривается результат самого последнего выполнения команды (однобитовая схема предсказания ветвлений). Бит предсказания ветвлений в однобитовой схеме называют переключателем – принято/не принято (taken /not taken).

1-битная схема прогноза 01 ПВ (неверно) ПНВ (неверно) ПВ (верно) ПНВ (верно) Состояние 0 – предсказывается, что перехода не будет; Состояние 1 – предсказывается, что переход будет. Сигналы ПВ ( переход выполняется) и ПНВ (переход не выполняется) поступают на вход автомата из блока выполнения команды ветвления (Branch unit) – обратная связь. С их помощью осуществляется коррекция прогноза. Точность прогноза недостаточная – направление перехода в цикле дважды будет предсказываться неверно.

Двухбитная схема прогноза (предиктор Смита) ПВ (верно) 1011 ПНВ (неверно) ПНВ (верно) 0100 ПНВ (верно) ПВ (неверно) ПНВ (неверно) ПВ (верно) 00 – очень малая вероятность перехода (сильное предсказание) 01 – малая вероятность перехода (слабое предсказание) 10 – очень большая вероятность перехода (сильное предсказание) 11 – большая вероятность перехода (слабое предсказание)

Когда автомат находится в состоянии 00, то предсказывается, что перехода не будет not taken). Если же в действительности переход будет выполнен, то автомат перейдет в состояние 01. Это означает, что когда данная команда перехода встретится в очередной раз, блок выборки команд снова предскажет невыполнение перехода. Если и в этот раз переход был предсказан неверно, т.е. произошел, то автомат перейдет в состояние 10. После этого будет предсказываться выполнение перехода (taken). Таким образом, прежде, чем предсказатель изменит значение предсказания, он должен подряд два раза дать неверное предсказание. Для выбора правильного состояния автомата при входе в цикл можно использовать статический прогноз с установкой начального состояния автомата 11. В этом случае предсказание всегда будет верным, за исключением последней итерации цикла. Последнего неверного предсказания не избежать. Точность предсказания для рассмотренного выше цикла с 10-ю итерациями будет 90%.

Двухуровневые схемы предсказаний Одноуровневые схемы предсказания ориентированы на те команды условного перехода, исход которых существенно зависит от их собственных предыдущих исходов. В то же время для многих команд наблюдается сильная зависимость не от собственных исходов, а от результов выполнения других, предшествующих им команд ветвления. Это обстоятельство учитывают двухуровневые адаптивные предикторы. Их называют коррелированными, т.к. oни отражают взаимозависимости между командами переходов.

Двухуровневые схемы предсказаний Рассмотрим небольшой фрагмент из текста программы тестового пакета SPEC92 (наихудший случай для двухбитной схемы). if (a= = 2) a=0; if (b= = 2) b=0; if (a !=b) { …

Двухуровневые схемы предсказаний a=2? b=2 ? a=0 да нет b=0 a b? да нет B1 B2 B3 cmpeax, 2 jne l1;B1 xoreax, eax l1:cmpebx, 2 jnel2;B2 xorebx,ebx l2:cmpeax,ebx jel3;B3 Если оба перехода B1 и B2 были выполняемыми, значит переход B3 будет невыполняемым. Одноуровневая схема прогнозирования никогда этого не учтет.

Двухуровневые схемы предсказаний Можно проследить, были ли совершены k последних команд переходов, независимо от того, какие это были команды переходов. Для этого используется k-битное число, которое хранится в k-битном сдвигающем регистре глобальной предыстории. Каждой комбинации k битов глобальной предыстории соответствует таблица n битов прогноза. Схема прогнозирования называется прогнозом (k,n), если она использует поведение последних k команд условного перехода для выбора одной из 2 k схем прогнозирования, каждая из которых представляет собой n- битную схему предсказания для каждого отдельного перехода. Схема двухуровневого предсказания дает более высокий процент успешного прогнозирования и использует небольшое количество дополнительной аппаратуры.

Двухуровневые схемы предсказаний Представлена BHT предиктора (2,2) – 2бита глобальной истории и 2 бита локальной истории (например, по счетчику). После выполнения команды содержимое счетчика одной ветви обновляется. Адрес команды перехода Биты прогноза From branch unit

Branch Target Buffer IP Comparators Tags IP 1 IP 2 IP 3 IP k = = = Branch Address Return Address Stack Predict BHT IP on instr. to fetch 1 Branch Prediction BTB является ассоциативным FIFO буфером.

Predicted PC PC = Branch Target Address Prediction bits Tag 1 Tag 2 Tag 3 Tag n Branch Predictor Taken Not Taken Alternative PC +4 Predict? History update (from branch unit)

Form signals to correct misprediction Taken branch, first executed PC D_icode Predicted PC PD ICache F/D IF +4 BTB PC M_icode Target Predicted PC PD X/M Misprediction Predicted Direction (tkn/ntk) Correction history = Misprediction Not predicted taken branch, first executed Predicted PC PC Select PC +4

Гибридные схемы предсказания Характерна сильная зависимость точности предсказания от особенностей программ, в которых эти стратегии реализуются. Схема предсказания, прекрасно проявляя себя с одними программными продуктами, с другими может давать совершенно неудовлетворительные результаты. Точность предсказания улучшается с увеличением глубины предыстории переходов, но это происходит лишь после накопления определенной информации (этот период принято называть временем разогрева). Чтобы уменьшить зависимость точности предсказания от особенностей программ, в которых эти стратегии реализуются, используют гибридные схемы предсказания.

IP Predictor 1 Predictor 2 Selector Prediction Multiplexor 0 1

Селектор Обычно для выбора селектора используют 2-битный счетчик с насыщением. Граф переходов автомата Мура, описывающего поведение селектора:

Селектор 00 – оба предиктора предсказали неправильно. 11 – оба предиктора предсказали правильно. 10 – предсказание первого верно, второго – неверно. 01 – предсказание первого предиктора неверно, второго – верно. Выбор предиктора осуществляется старшим разрядом счетчика, который поступает на управляющий вход мультиплексора. Если состояния – выбирается первый предиктор, если – выбирается второй предиктор. По имеющимся оценкам, точность предсказания гибридных схем повышается по сравнению с бимодальными до 97%.