Про команды переходов. И про out-of-order.
(я не буду рассказывать про технику предсказания переходов вообще, я лучше про выгоды предпросмотра - и out-of-order выполнения, - расскажу)
Итак, есть у нас процессор, который выполняет команды последовательно, друг за другом.
Вот встретилась ему последовательность:
ld t1, 4(t2)
j t1
Загрузить в регистр адрес и перейти. Что плохого может произойти с процессором? В принципе, при достижении команды j он должен остановить конвейер до момента поступления значения t1 в счётчик команд (PC). То есть, команда дойдёт, как минимум, до этапа чтения операндов и мы потеряем один или два такта. Далее мы можем потерять время на ожидание данных из общей памяти, если в кэше их не оказалось.
В MIPS эта потеря снижена командой сразу после перехода, которая выполняется вне зависимости от перехода. Так что мы потеряем всего один такт, а можем и меньше.
Однако, запуск t1 произойдёт только после записи в t1, а команда загрузки может выполняться довольно долго. Поэтому мы потеряем 3 и более тактов на ожиданиях.
Представим себе, что мы можем заглядывать в будущее и выбирать команды.
Если ни одна из предыдущих команд не задействовала t2 в качестве приёмника, то мы можем запустить загрузку пораньше, как только t2 будет заполнен.
После получения адреса в t1 мы можем запустить на выполнение команду перехода. Команда перехода сможет быть выполнена, если повезёт, ранее, чем команды до загрузки t1. А если мы следим за командами перехода и считаем их приоритетными, то можно это гарантировать.
В результате, пока выполняются команды, у процессора есть время подкачать команды в кэш.
Это мы рассмотрели самый сложный случай. Обычно случаи попроще. Типа такого:
beqz r1,label
Если регистр r1 равен 0, то перейти. Если не равен - продолжить.
Здесь, о чудо, вычисление адреса перехода не зависит ни от какого регистра общего назначения. Нам надо знать только адрес самой команды перехода, чтобы вычислить адрес перехода и попросить систему подкачать данные в кэш команд. А как только будет вычислено значение r1, мы сразу сможем запустить вычисление условия. Опять же, если повезёт, то заметно раньше окончания выполнения предыдущих команд.
Что интересно, для загрузок и сохранений вычисление адреса можно проводить заранее и проверять его на TLB. Если исключений нет, то загрузку или сохранение можно выполнять и смотреть на команды за ней, в противном случае надо вставить вместо плохой команды вызов исключительной ситуации. Если мы запоминаем вычисленные адреса, прошедшие проверку, то мы можем запустить загрузки параллельно с основным конвейером. Ориентируясь на адреса, мы можем даже частично менять порядок команд.
Случаи с многими командами обращения к памяти встречаются часто: это, например, раскрученные циклы или сохранение или восстановление регистров в стековый фрейм.
В случае такого использования окна предпросмотра команды подкачки данных в кэша программисту вставлять не обязательно. Это сделает сам процессор.
Такая система, по известным мне сведениям, была в процессоре Alpha - где была выдача нескольких команд за такт, но ещё не было переименования регистров. Там был предпросмотр команд, вычисление адресов перехода и подкачка кэша команд, вычисление адресов и установка исключений, а также переупорядочение сохранений и загрузок, если они были в разные области памяти (это выполнялось блоком обращений к памяти).
Наша модель MIPS имела весьма похожий алгоритм работы.
PS
Branch delay slot - ненавижу! ;)
Итак, есть у нас процессор, который выполняет команды последовательно, друг за другом.
Вот встретилась ему последовательность:
ld t1, 4(t2)
j t1
Загрузить в регистр адрес и перейти. Что плохого может произойти с процессором? В принципе, при достижении команды j он должен остановить конвейер до момента поступления значения t1 в счётчик команд (PC). То есть, команда дойдёт, как минимум, до этапа чтения операндов и мы потеряем один или два такта. Далее мы можем потерять время на ожидание данных из общей памяти, если в кэше их не оказалось.
В MIPS эта потеря снижена командой сразу после перехода, которая выполняется вне зависимости от перехода. Так что мы потеряем всего один такт, а можем и меньше.
Однако, запуск t1 произойдёт только после записи в t1, а команда загрузки может выполняться довольно долго. Поэтому мы потеряем 3 и более тактов на ожиданиях.
Представим себе, что мы можем заглядывать в будущее и выбирать команды.
Если ни одна из предыдущих команд не задействовала t2 в качестве приёмника, то мы можем запустить загрузку пораньше, как только t2 будет заполнен.
После получения адреса в t1 мы можем запустить на выполнение команду перехода. Команда перехода сможет быть выполнена, если повезёт, ранее, чем команды до загрузки t1. А если мы следим за командами перехода и считаем их приоритетными, то можно это гарантировать.
В результате, пока выполняются команды, у процессора есть время подкачать команды в кэш.
Это мы рассмотрели самый сложный случай. Обычно случаи попроще. Типа такого:
beqz r1,label
Если регистр r1 равен 0, то перейти. Если не равен - продолжить.
Здесь, о чудо, вычисление адреса перехода не зависит ни от какого регистра общего назначения. Нам надо знать только адрес самой команды перехода, чтобы вычислить адрес перехода и попросить систему подкачать данные в кэш команд. А как только будет вычислено значение r1, мы сразу сможем запустить вычисление условия. Опять же, если повезёт, то заметно раньше окончания выполнения предыдущих команд.
Что интересно, для загрузок и сохранений вычисление адреса можно проводить заранее и проверять его на TLB. Если исключений нет, то загрузку или сохранение можно выполнять и смотреть на команды за ней, в противном случае надо вставить вместо плохой команды вызов исключительной ситуации. Если мы запоминаем вычисленные адреса, прошедшие проверку, то мы можем запустить загрузки параллельно с основным конвейером. Ориентируясь на адреса, мы можем даже частично менять порядок команд.
Случаи с многими командами обращения к памяти встречаются часто: это, например, раскрученные циклы или сохранение или восстановление регистров в стековый фрейм.
В случае такого использования окна предпросмотра команды подкачки данных в кэша программисту вставлять не обязательно. Это сделает сам процессор.
Такая система, по известным мне сведениям, была в процессоре Alpha - где была выдача нескольких команд за такт, но ещё не было переименования регистров. Там был предпросмотр команд, вычисление адресов перехода и подкачка кэша команд, вычисление адресов и установка исключений, а также переупорядочение сохранений и загрузок, если они были в разные области памяти (это выполнялось блоком обращений к памяти).
Наша модель MIPS имела весьма похожий алгоритм работы.
PS
Branch delay slot - ненавижу! ;)