Повышение производительности процессора

Атака в лоб: повышение тактовой частоты

Физическое устройство процессора и памяти таково, что любые действия могут происходить не быстрее, чем с определённой частотой, задаваемой специальным генератором (в виде всплесков напряжения с данной частотой или ещё как-то, неважно). Частота «500 мегагерц» означает полмиллиарда колебаний генератора в секунду, соответственно один такт, за который хоть что-то может выполниться, составляет одну полумиллиардную долю секунды.

При этом

• Резко возрастает энергопоребление
• Резко возрастает тепловыделение
• Надо снижать время срабатывания ключей на микросхеме

Для этого (а также для того, чтобы расстояния между элементами были короче, ибо скорость распространения электрического импульса, оказывается, тоже не бесконечна) постоянно уменьшают толщину полупроводниковых слоёв. Толщина эта измеряется уже в нанометрах, т. е. скоро достигнет размеров в несколько молекул.

Кроме того

• Сложные однотактные команды: время срабатывания суммируется
• «стена памяти» при сложении
• несколько функциональных частей процессора участвуют в операции
• некоторые из этих частей принципиально небыстрые

Одновременное выполнение инструкций

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

Зависимость по данным: Если в одной операции используется результат работы другой, первая должна выполняться строго после второй.

• выражения с регистрами и условная загрузка
  

     1 addiu $t6, $t5, $t4
     2 sll   $v0, $t6, 2
  

• пересылка в память и обратно (напоминаем, что это псевдоинструкции, использующие регистр $at)

     1 sw    $t2, 0x10010000
     2 lw    $t3, 0x10010000
  

• косвенная адресация
  

     1 addiu $t4, $t4, 4
     2 sw    $t2, ($t4)
  

• …

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

• Условный переход

     1 ble    $t2, $t3, Label
     2 # продолжение здесь?
     3 …
     4 Label:
     5 # …или здесь?
  

• Переход по косвенному адресу

     1 jr     $ra        # какой адрес сейчас в регистре?
  

• …

Обратим внимание: разные случаи зависимости если и можно обойти, то по-разному

Масштабирование

Об увеличении количества процессоров (или вычислительных ядер) в ЭВМ см. последующие лекции. Здесь поговорим о масштабировании элементов внутри одного процессора.

Микропрограммный уровень — рассмотрение устройства с точки зрения работы отдельных его узлов (как правило, на каждом такте). Имеет смысл, когда одна машинная инструкция приводит к выполнению различных нескольких нескольких узлов процессора — то есть почти всегда.

Векторные операции — выполнение однотипных действий над несколькими элементами данных одновременно.

• Несложно реализовать, масштабировав АЛУ и/или математический сопроцессор

• Данные представлены в виде массивов (векторов), загружаемых в векторные регистры соответствующего размера

• Наиболее эффективна полная загрузка вектора данными
  • ⇒ Эффективность чувствительна к зависимости по данным
  • ⇒ Переупорядочивание вычислений — задача программиста или проргаммы-оптимизатора
• Требуются для эффективной обработки потоков данных, в первую очередь — мультимедийных
  • Современные расширения системы команд: MMX/XMM, SSE
  • Различные GPU и APU
  • АЦП/ЦАП и т. п.
• В 80-е/90-е выпускались векторные суперкомпьютеры, требующие специальной организацией вычислений, сейчас проще (хотя и не так эффективно) переупорядочивать имеющийся код «на лету»

Суперскалярные вычисления — одновременное выполнение нескольких инструкций и/или миркопрограммных инструкций

• Требуют дублирования не только АЛУ, но и других узлов процессора

• Очевидно, чувствительны к зависимостям по данным и по управлению

  • ⇒ требуют качественной оптимизации кода (например, переупорядочивания по зависимостям)

Проблема эффективной загрузки

• VLIW (very long instruction word) — явная программа для всех параллельно работающих вычислительных узлов
  • Простота аппаратной реализации ⇒ возможность дальнейшего наращивания частоты/количества узлов
  • Высокая сложность написания компиляторов и реализации традиционных алгоритмов
  • Пример: Эльбрус, некоторые GPU
• Аппаратные методы
  • Упреждающие вычисления
    • вычисление инструкций «не вовремя», если они независимы по данным и управлению
    • вычисление инструкций «впрок», в надежде, что дол них дойдёт дело
    • предсказание, какую из нескольких веток потока управления надо вычислять старательней (на основании статистики)
    • чёрная магия
  • Оптимизация кода «на лету»
    • Определение блоков независимых по данным инструкций
    • Переименование регистров для ослабления зависимости по данным
    • Переупорядочивание инструкций внутри блока
    • Переупорядочивание зависимых инструкций при упреждающих вычислениях
• Конвейер

  Пример: предсказание перехода (BHT Simulator) в MARS (TODO показать)

• Держать небольшую таблицу с адресами команд условного перехода (большую смыысла не имет, локальность)
• Хранить историю того, произошёл ли переход (чем длиннее, тем неэффективнее; лучше всего — одно последнее решение (цикл) или два (условный оператор + решение по умолчанию)

Конвейер

Конвейерная архитектура процессора — разбиение процессора на несколько узлов, которые могут работать параллельно в рамках одной или нескольких команд. Таким образом на каждом такте могут одновременно выполняться несколько микроинструкций, соответствующих различным стадиям конвейера инструкций основной программы.

Однако это требует особой аппаратной организации и не исключает ситуации неэффективной загрузки конвейера

Пример: такт работы модельной машины

1. Чтение в РК команды из памяти по адресу, находящемуся в СК
2. Интерпретация команды в РК (для УМ3 это просто)
3. Чтение операндов из памяти (от 0 до 2)
4. Вычисление результата (если необходимо)
5. Запись результата в память (от 0 до 1)
6. Вычисление адреса следующей команды в СК

Независимые группы: 1, 2-3, 4, 5-6 можно представить в виде конвейера

1. Чтение из памяти команд
2. Декодирование команды и чтение из памяти данных (адреса находятся в известных местах прочтённой команды, поэтому их выделение делается мгновенно)
3. Вычисление
4. Запись результата в память и вычисление следующего адреса (зависит от предыдущей стадии, например, при условном переходе)

При идеальной загрузке конвейера в течение одного такта:

1. N+3-я команда только считывается из памяти
2. N+4-я команда декодируется и параллельно считываются из памяти операнды
3. N+1-я команда вычисляется

4. N-я команда записывает результат в память, и параллельно вычисляется адрес … N+1-й команды

=> В случае зависимости по управлению наш примитивный конвейер полностью неэффективен, т. к. последняя стадия N-й команды следует строго перед первой стадией N+1-й!

Однако если команда не предполагает зависимости по управлению, вычисление следующего адреса можно объединить непосредственно с 1-й стадией!

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

Современные процессоры intel/AMD, по слухам, на микропрограммном конвейерном RISC-ядре, а доступные программисту CISC-инструкции преобразуются в них путём применения всего вышеперечисленного, включая чёрную магию.

Конвейер MIPS

Подробное описание в книге «Цифровая схемотехника и архитектура компьютера» (глава 7.5 КОНВЕЙЕРНЫЙ ПРОЦЕССОР, стр 1007). Можно почитать весь раздел 7.

Вот несколько упрощённая схема узлов процессора MIPS

Замечания:

• Обмен с памятью (чтение и запись) на самом деле является обменом с кеш-памятью. и считается достаточно быстрым

• Узел Reg File на схеме — т. н. регистровый блок, узел процессора, аккумулирующий данные из регистров-операндов инструкции

• Передача данных из регистров в регистровый блок и запись обратно в регистр — однотактные операции

• Если согласно логике работы очередной инструкции требуется значение какого-то регистра, и оно уже вычислено, но не записано непосредственно в регистр, в процессоре предусмотрены пути: «перетекания» соответствующих данных в обход регистрового блока (см. стрелки от стадий E, M, W к стадии D)

• Целочисленные умножение и деление — очень медленные команды (17 тактов и 33 такта), они существенно задерживают конвейер

• Курсивом выделены действия, относящиеся к работе кеша и системы виртуальной памяти

1. Instruction fetch — выборка команды из кеша команд

2. Instruction Decode — декодирование команды
   

   • Операнды выбираются из регистрового блока.
   • Операнды передаются в обход регистрового блока со стадий E, M и W.
   • ALU определяет, выполняется ли условие перехода и вычисляет адрес перехода для команд перехода.

   • Осуществляется преобразование виртуального адреса в физический.

   • Производится поиск адреса команды по TLB и вырабатывается признак hit/miss.

   • Командная логика выбирает адрес команды.

3. Execution — исполнение

   • ALU выполняет арифметические или логические операции для команд типа регистр-регистр.

   • Производится преобразование виртуального адреса в физический для данных, используемых командами загрузки и сохранения.

   • Производится поиск данных по TLB и вырабатывается признак hit/miss.

   • Все операции умножения и деления выполняются на этой стадии.

4. Memory fetch — выборка из памяти данных и выравнивание в границах слова

5. Writeback — «обратная» запись в регистр результата инструкции типа регистр-регистр или загрузки из памяти; обновление регистрового блока

Пример:

   1 lui   $at, 0x1001      # это раскрытие псевдоинстркуции lw $t2, 0x10010000
   2 lw    $t2, 0($at)
   3 sll   $t3, $t3, 2
   4 add   $t2, $t2, $t3
   5 lui   $at, 0x1004      # это раскрытие псевдоинстркуции sw $t2, 0x10040000
   6 sw    $t2, 0($at)

• I «lui $at, 0x1004» — считывается из памяти

• D «add $t2, $t2, $t3» — декодируется, значение $t2 приехало в обход регистрового блока со стадии M инструкции lw, значение $t3 приедет сразу после вычисления со стадии E инструкции sll

• E «sll $t3, $t3, 2» — вычисляется

• M «lw $t2, 0($at)» — считывает из памяти содержимое ячейки по адресу 0x10010000

• W «lui $at, 0x1001» — записывает содержимое ячейки в регистр $at и обновляет регистровый блок

Пример: упрощённый HTML-эмулятор MIPS с конвейером (код на GitHub)

Конфликты конвейера

Конфликты по данным

• Если соответствующие данные уже получены на других стадиях, их можно получить в обход регистрового блока, тем самым сняв конфликт

• Загрузка из памяти в регистр происходит на стадии M, а содержимое регистра нужно на стадии D, поэтому при встрече двух таких команд обходного пути недостаточно. В приведённом примере данных, которые должны попасть в регистр $t2, в момент декодирования операции add просто нет в процессоре
  

     1 lw    $t2, 0($at)
     2 add   $t1, $t3, $t2
  

• В ранних версиях MIPS программист (или транслятор) вставлял между этими командами т. н. «пузырёк» (нулевая ячейка, соответствует команде «sll $zero, $zero, 0», иначе называется NOP). Это давало конвейеру необходимую задержку: в момент декодирования инструкции add, инструкция lw проходит стадию обращения к памяти и значение $t2 попадёт в неё обходным путём
  

     1 lw    $t2, 0($at)
     2 nop
     3 add   $t1, $t3, $t2
  

• В современных версиях MIPS добавление пузырька происходит аппаратно (всегда можно распознать совпадение регистра-приёмника и регистра источника), причём сразу в стадию E конвейера и после неё

  • Это приводит к частичной блокировке конвейера (т. н. slip) — стадии I и D «подвисают» на один такт, а стадии E, M и W продолжают работу

• Возможна также полная блокировка конвейера (stall), при которой все стадии пропускают такт (например, в ожидании завершения одной из них), но условия полной блокировки не так очевидны (сложные ситуации с кешем, исключениями и пр.)

Конфликт по управлению

• Несмотря на что, что MIPS принимает решение о переходе очень рано (на стадии D), команда из физически следующей ячейки к этому времени уже входит в стадию I, независимо от того, была ли предыдущая команда командой перехода (даже безусловного!). В MIPS принято решение для сохранения оптимальности конвейера это команду всегда выполнять.

  Слот задержки перехода (delay slot) — команда или группа команд, выполняющихся независимо от того, сработал ли предшествующий им переход или нет.

  • В MIPS слот задержки присутствует для всех команд перехода и равен одной инструкции

• Самое простое решение — вставлять пузырёк сразу после команды перехода.

• Для повышения эффективности можно менять местами инструкцию перехода и предшествующую ей инструкцию, если они в свою очередь не конфликтуют по конвейеру

  addi $ra, $ra, 4    |     addi $t2, $t2, 4
  jr   $ra            |     jr   $ra
                      |     nop

  • или

  addi $ra, $ra, 4    |     jr $ra
  jr   $ra            |     addi $t2, $t2, 4

• Команды слева конфликтуют по данным, команды справа — нет, поэтому оба фрагмента кода справа работают одинаково, но второй — эффективнее. Что? Да-да, команда addi в примере справа выполнится!

• Для удобства программирования в современных MIPS можно включить режим аппаратной вставки пузырька (slip delay), при котором эффективность слегка падает
• Эмулятор MARS умеет работать в двух режимах — и использование слота задержки (режим «delayed branch»), и с использованием неявной вставки пузырька (по умолчанию)

Оказывается, проект WebMIPS свободный (?), по крайне мере, он доступен в исходниках. Написан он на ASP.NET, но можно попробовать затолкать

Д/З

TODO