B4 Конвейерный процессор

Мы повысили способность NPC обеспечивать подачу инструкций, добавив icache. Хотя бюджет площади очень ограничен, добавление icache явно улучшило общую производительность NPC. Оставшиеся направления оптимизации включают улучшение способности подачи данных и вычислительной эффективности.

Оцените идеальный прирост производительности от dcache

Эффективный способ улучшить способность подачи данных — добавить dcache. В предыдущем разделе мы уже просили вас оценить идеальный прирост производительности от dcache с помощью счётчиков производительности. После оптимизации icache ускорение, которое dcache даёт в идеальных условиях, может измениться. Попробуйте заново оценить идеальный прирост производительности от dcache.

Оцените ожидаемую производительность dcache с помощью cachesim

Попробуйте улучшить свой cachesim так, чтобы он мог читать mtrace, а затем оцените ожидаемую производительность dcache определённого размера.

Вы должны обнаружить, что в рамках оставшегося бюджета площади трудно эффективно улучшить способность NPC подавать данные с помощью dcache. Поэтому более научным решением будет использовать оставшуюся площадь для повышения вычислительной эффективности. Текущий NPC является многотактным, то есть он может выполнить одну инструкцию только за несколько тактов. Если мы сможем увеличить пропускную способность выполнения инструкций NPC, то сможем повысить его вычислительную эффективность. Конвейеризация, являясь техникой параллелизма на уровне инструкций, может эффективно повысить пропускную способность выполнения инструкций NPC.

Оцените идеальный прирост вычислительной эффективности

Мы ещё не представили конкретную реализацию конвейера, но вы уже можете оценить идеальный выигрыш от конвейеризации на основе счётчиков производительности. Предполагая, что NPC может выполнять одну инструкцию за такт, кроме инструкций доступа к памяти, попробуйте оценить идеальное ускорение NPC при текущих условиях промахов icache.

Оценивайте прирост производительности с точки зрения всей системы

Эта оценка может вас удивить.

Помните пример с ускорением в 5000 раз из закона Амдала? Прирост производительности, который технология даёт сама по себе, и прирост, который она даёт в сценарии всей системы, могут быть совершенно разными. Если вы реализуете внеочередное выполнение и множественную выдачу инструкций, но подача инструкций и данных не успевает за ними, то в реальном кристалле это будет всего лишь куча логических вентилей, которые занимают площадь и потребляют энергию, но почти не улучшают производительность выполнения программ.

Основы конвейера

Конвейер на фабрике

Идея конвейеризации существует и в повседневной жизни; самый распространённый пример — производственный конвейер на фабрике. Например, изготовление продукта на фабрике требует прохождения 5 процессов: сборка, наклеивание этикетки, упаковка в пакет, упаковка в коробку и внешний контроль. Если обозначить эти процессы числами 1~5, а различные продукты — A, B, C......, то пространственно-временная диаграмма без конвейеризации будет выглядеть следующим образом:

          ----> Time
 | Product
 | +---+---+---+---+---+
 V |A.1|A.2|A.3|A.4|A.5|
   +---+---+---+---+---+
                       +---+---+---+---+---+
                       |B.1|B.2|B.3|B.4|B.5|
                       +---+---+---+---+---+
                                           +---+---+---+---+---+
                                           |C.1|C.2|C.3|C.4|C.5|
                                           +---+---+---+---+---+
================================================================
          ----> Time
 | Employee
 | +---+               +---+                +---+
 V |A.1|               |B.1|                |C.1|
   +---+               +---+                +---+
       +---+               +---+                +---+
       |A.2|               |B.2|                |C.2|
       +---+               +---+                +---+
           +---+               +---+                +---+
           |A.3|               |B.3|                |C.3|
           +---+               +---+                +---+
               +---+               +---+                +---+
               |A.4|               |B.4|                |C.4|
               +---+               +---+                +---+
                   +---+                +---+                +---+
                   |A.5|                |B.5|                |C.5|
                   +---+                +---+                +---+

Пространственно-временная диаграмма при использовании конвейера выглядит следующим образом:

          ----> Time
 | Product
 | +---+---+---+---+---+
 V |A.1|A.2|A.3|A.4|A.5|
   +---+---+---+---+---+
       +---+---+---+---+---+
       |B.1|B.2|B.3|B.4|B.5|
       +---+---+---+---+---+
           +---+---+---+---+---+
           |C.1|C.2|C.3|C.4|C.5|
           +---+---+---+---+---+
               +---+---+---+---+---+
               |D.1|D.2|D.3|D.4|D.5|
               +---+---+---+---+---+
                   +---+---+---+---+---+
                   |E.1|E.2|E.3|E.4|E.5|
                   +---+---+---+---+---+
================================================================
          ----> Time
 | Employee
 | +---+---+---+---+---+
 V |A.1|B.1|C.1|D.1|E.1|
   +---+---+---+---+---+
       +---+---+---+---+---+
       |A.2|B.2|C.2|D.2|E.2|
       +---+---+---+---+---+
           +---+---+---+---+---+
           |A.3|B.3|C.3|D.3|E.3|
           +---+---+---+---+---+
               +---+---+---+---+---+
               |A.4|B.4|C.4|D.4|E.4|
               +---+---+---+---+---+
                   +---+---+---+---+---+
                   |A.5|B.5|C.5|D.5|E.5|
                   +---+---+---+---+---+

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

Конвейер(pipeline) инструкций

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

При изучении шин мы уже просили вас модернизировать NPC до многотактного процессора с распределённым управлением. У многотактных процессоров уже существует понятие стадий, и их рабочий процесс очень похож на неконвейерный подход из приведённого выше примера с фабрикой. Поэтому понять, как работает конвейер инструкций, несложно.

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

1. Однотактный процессор: между стадиями нет регистров, поэтому критический путь составляет 5 нс, а частота — 200 МГц. Одна инструкция выполняется за 1 такт, то есть за 5 нс; каждые 1 такт выполняется 1 инструкция, то есть IPC = 1.
2. Многотактный процессор: между стадиями есть регистры, поэтому критический путь составляет 1 нс, а частота — 1000 МГц. Одна инструкция выполняется за 5 тактов, то есть за 5 нс; каждые 5 тактов выполняется 1 инструкция, то есть IPC = 0.2.
3. Конвейерный процессор: между стадиями есть регистры, поэтому критический путь составляет 1 нс, а частота — 1000 МГц. Одна инструкция выполняется за 5 тактов, то есть за 5 нс; каждые 1 такт завершается 1 инструкция, то есть IPC = 1.

Процессор	Частота	Задержка выполнения инструкции	IPC
Однотактный	200 МГц	5 нс	1
Многотактный	1000 МГц	5 нс	0.2
Конвейерный	1000 МГц	5 нс	1

Как видно, хотя задержка выполнения инструкции всё ещё составляет 5 нс, конвейер обладает преимуществами высокой частоты и высокого IPC. Эти преимущества по сути возникают благодаря параллелизму на уровне инструкций: каждый такт конвейерный процессор обрабатывает 5 разных инструкций.

Разумеется, приведённые выше данные получены только из анализа в идеальных условиях. Если учитывать доступ к памяти в SoC, IPC будет значительно ниже; кроме того, конвейерный процессор не может постоянно выполнять 5 инструкций каждый такт, что мы подробнее проанализируем ниже.

Более длинные конвейеры

В приведённом выше примере конвейер разделён только на 5 стадий. На самом деле мы можем разделить его на большее количество стадий, сделав логику каждой стадии проще и тем самым повысив общую частоту процессора. Такой конвейер называется «суперконвейером». Например, если конвейер можно разделить на 30 стадий, то согласно приведённой выше оценке частота теоретически может достигнуть 6 ГГц.

Однако современные высокопроизводительные процессоры обычно имеют конвейер примерно из 15 стадий. Какие факторы, по вашему мнению, могут делать слишком большое количество стадий нецелесообразным?

Простая реализация конвейера

Реализовать конвейер на основе многотактного процессора с handshake-механизмом несложно. Для входа in и выхода out каждой стадии нам нужно лишь корректно обрабатывать следующие сигналы (bits означает полезные данные, которые требуется передавать между стадиями):

• out.bits, формируется текущей стадией
• out.valid, формируется текущей стадией и обычно также связан с in.valid
• in.ready, формируется текущей стадией, устанавливается в неактивное состояние, когда стадия занята, и в активное после завершения обработки текущей инструкции
• out.ready, совпадает с in.ready следующей стадии
• in.bits, обновляется значением out.bits предыдущей стадии, когда одновременно активны in.ready текущей стадии и out.valid предыдущей стадии
• in.valid, оставляется вам в качестве упражнения

На основании вышесказанного мы можем упаковать обработку последних трёх сигналов в функцию, а затем использовать её для соединения стадий:

def pipelineConnect[T <: Data, T2 <: Data](prevOut: DecoupledIO[T],
  thisIn: DecoupledIO[T], thisOut: DecoupledIO[T2]) = {
    prevOut.ready := thisIn.ready
    thisIn.bits := RegEnable(prevOut.bits, prevOut.valid && thisIn.ready)
    thisIn.valid := ???
  }

pipelineConnect(ifu.io.out, idu.io.in, idu.io.out)
pipelineConnect(idu.io.out, exu.io.in, exu.io.out)
pipelineConnect(exu.io.out, lsu.io.in, lsu.io.out)
// ...

В частности, IFU может немедленно начать выборку следующей инструкции, не ожидая завершения выполнения текущей. Приведённый выше RegEnable играет роль «регистра стадии конвейера» из традиционных учебников, но с точки зрения шины его также можно понимать как буфер, в котором нижестоящий модуль принимает сообщения: после успешного handshake между вышестоящим и нижестоящим модулями вышестоящий модуль считает, что сообщение успешно принято нижестоящим, и больше не хранит его; поэтому нижестоящему модулю необходимо записать полученное сообщение в буфер, чтобы предотвратить его потерю. Что касается первых трёх сигналов, поскольку их конкретная логика связана с поведением текущей стадии, их необходимо реализовать в модуле, соответствующем этой стадии.

В конвейерном процессоре существуют ситуации, в которых текущая инструкция не может продолжить выполнение; они называются «конфликтами» (hazards). Конфликты в основном делятся на 3 категории: структурные конфликты, конфликты данных и конфликты управления. Если игнорировать конфликты и принудительно продолжать выполнение, результат перехода автомата состояний CPU будет несовместим с автоматом состояний ISA, что проявится в результатах выполнения инструкций, не соответствующих их семантике. Поэтому при проектировании конвейера необходимо обнаруживать конфликты и либо устранять их аппаратным проектированием, либо ожидать во времени, пока конфликт не исчезнет. Во втором случае этого можно добиться добавлением условий ожидания к in.ready и out.valid.

Структурный конфликт

Структурный конфликт возникает, когда разные стадии конвейера должны одновременно обращаться к одному и тому же компоненту, но этот компонент не поддерживает одновременный доступ из нескольких стадий. Например, в последовательности инструкций на рисунке ниже в момент T4 I1 читает данные в LSU, а I4 выбирает инструкцию в IFU; обеим требуется чтение памяти. В момент T5 I1 записывает регистры в WBU, а I4 читает регистры в IDU; обеим необходимо обращаться к регистровому файлу.

           T1   T2   T3   T4   T5   T6   T7   T8
         +----+----+----+----+----+
I1: lw   | IF | ID | EX | LS | WB |
         +----+----+----+----+----+
              +----+----+----+----+----+
I2: add       | IF | ID | EX | LS | WB |
              +----+----+----+----+----+
                   +----+----+----+----+----+
I3: sub            | IF | ID | EX | LS | WB |
                   +----+----+----+----+----+
                        +----+----+----+----+----+
I4: xor                 | IF | ID | EX | LS | WB |
                        +----+----+----+----+----+

Некоторые структурные конфликты можно полностью устранить аппаратным проектированием, чтобы они вообще не возникали во время работы CPU: достаточно спроектировать аппаратную часть так, чтобы эти компоненты поддерживали одновременный доступ из нескольких стадий. В частности:

• Для регистрового файла достаточно реализовать независимые порты чтения и записи, позволив IDU обращаться к регистровому файлу через порт чтения, а WBU — через порт записи
• Для памяти существует несколько решений
  • Разделить порт чтения и порт записи, как в регистровом файле, реализовав настоящую двухпортовую память
  • Разделить память на память инструкций и память данных, работающие независимо
  • Ввести кэш; если происходит попадание в кэш, обращаться к памяти не требуется

Различия между учебниками и реальными системами

Большинство решений в учебниках основаны на некоторых упрощённых предположениях, которые, вероятно, уже не выполняются в реальных процессорах, поэтому они не обязательно подходят для сценария OSOC («One Student One Chip»).

Например, микросхемы SDRAM не могут разделить порт чтения и порт записи. И команда READ, и команда WRITE передаются микросхемам SDRAM через шину памяти SDRAM. Разделение памяти на память инструкций и память данных поместило бы инструкции и данные в разные адресные пространства, что нарушает модель памяти ISA с единым адресным пространством для инструкций и данных. С одной стороны, современные компиляторы не могут компилировать программы, адаптированные к такой схеме; с другой стороны, даже если разрабатывать программы на ассемблере, функции загрузки программ, например bootloader, также не смогут работать корректно.

На самом деле OSOC предъявляет к вам более высокие требования: научитесь оценивать решение с точки зрения всей системы. Упрощённые предположения в учебниках могут помочь сосредоточиться на изучении текущего вопроса, но в будущем вам предстоит работать с реальными проектами; только научившись связывать различные факторы системы, вы сможете принимать разумные и эффективные решения в будущей работе.

Существуют и структурные конфликты, которых нельзя полностью избежать, например:

• При промахе кэша IFU и LSU всё ещё могут одновременно обращаться к памяти
• Очередь контроллера SDRAM заполнена и не может принимать новые запросы
• Вычисление в делителе занимает десятки тактов, и новое вычисление нельзя начать до завершения текущего

Для обработки таких ситуаций простой способ — ожидание: если IFU и LSU одновременно обращаются к памяти, пусть один ждёт другого; подождать, пока в очереди контроллера SDRAM освободится место; подождать, пока делитель завершит текущее вычисление. Хорошая новость заключается в том, что шина изначально обладает механизмом ожидания, поэтому если slave-устройство, нижестоящий модуль или арбитр устанавливает ready в неактивное состояние, обнаружение и обработку структурных конфликтов можно свести к автомату состояний шины, не реализуя отдельную логику обнаружения и обработки структурных конфликтов.

Кто кого ждёт?

Во время ожидания должен ли IFU ждать LSU, или LSU должен ждать IFU? Или допустимы оба варианта? Почему?

Конфликт данных

Конфликт данных возникает, когда инструкции на разных стадиях зависят от данных одного и того же регистра и по крайней мере одна инструкция записывает в этот регистр. Например, в последовательности инструкций на рисунке ниже I1 записывает регистр a0, но запись завершается только в конце момента T5. До этого I2 в момент T3 читает старое значение a0, I3 в T4 читает старое значение a0, I4 в T5 читает старое значение a0, и только I5 в T6 может прочитать новое значение a0.

                    T1   T2   T3   T4   T5   T6   T7   T8   T9
                  +----+----+----+----+----+
I1: add a0,t0,s0  | IF | ID | EX | LS | WB |
                  +----+----+----+----+----+
                       +----+----+----+----+----+
I2: sub a1,a0,t0       | IF | ID | EX | LS | WB |
                       +----+----+----+----+----+
                            +----+----+----+----+----+
I3: and a2,a0,s0            | IF | ID | EX | LS | WB |
                            +----+----+----+----+----+
                                 +----+----+----+----+----+
I4: xor a3,a0,t1                 | IF | ID | EX | LS | WB |
                                 +----+----+----+----+----+
                                      +----+----+----+----+----+
I5: sll a4,a0,1                       | IF | ID | EX | LS | WB |
                                      +----+----+----+----+----+

Приведённый выше конфликт данных называется конфликтом read-after-write (RAW, чтение после записи). Его характерная особенность состоит в том, что одна инструкция должна записать регистр, а другая, более молодая инструкция — прочитать этот же регистр. Очевидно, если такой конфликт не обработать, инструкции I2, I3 и I4 вычислят неверные результаты, поскольку прочитают старое значение a0, нарушая семантику выполнения инструкций.

Существует несколько способов устранить RAW-конфликт. С точки зрения программного обеспечения инструкции генерирует компилятор, поэтому один из способов — позволить компилятору обнаруживать RAW-конфликты и вставлять пустые инструкции (nop), ожидая завершения записи регистром-производителем, как показано ниже:

                    T1   T2   T3   T4   T5   T6   T7   T8   T9   T10  T11  T12
                  +----+----+----+----+----+
I1: add a0,t0,s0  | IF | ID | EX | LS | WB |
                  +----+----+----+----+----+
                       +----+----+----+----+----+
    nop                | IF | ID | EX | LS | WB |
                       +----+----+----+----+----+
                            +----+----+----+----+----+
    nop                     | IF | ID | EX | LS | WB |
                            +----+----+----+----+----+
                                 +----+----+----+----+----+
    nop                          | IF | ID | EX | LS | WB |
                                 +----+----+----+----+----+
                                      +----+----+----+----+----+
I2: sub a1,a0,t0                      | IF | ID | EX | LS | WB |
                                      +----+----+----+----+----+
                                           +----+----+----+----+----+
I3: and a2,a0,s0                           | IF | ID | EX | LS | WB |
                                           +----+----+----+----+----+
                                                +----+----+----+----+----+
I4: xor a3,a0,t1                                | IF | ID | EX | LS | WB |
                                                +----+----+----+----+----+
                                                     +----+----+----+----+----+
I5: sll a4,a0,1                                      | IF | ID | EX | LS | WB |
                                                     +----+----+----+----+----+

По сути вставка пустых инструкций всё равно означает ожидание, но компилятор способен сделать лучше: вместо ожидания лучше выполнять какие-либо полезные инструкции. Этого можно добиться с помощью планирования инструкций: компилятор пытается найти инструкции без зависимостей по данным и изменить их порядок, не влияя на поведение программы. В следующем примере I6, I7 и I8 не имеют зависимости по данным от I1, поэтому их можно переставить сразу после I1:

I1: add a0,t0,s0          I1: add a0,t0,s0
I2: sub a1,a0,t0          I6: add t5,t4,t3
I3: and a2,a0,s0          I7: add s5,s4,s3
I4: xor a3,a0,t1   --->   I8: sub s6,t4,t2
I5: sll a4,a0,1           I2: sub a1,a0,t0
I6: add t5,t4,t3          I3: and a2,a0,s0
I7: add s5,s4,s3          I4: xor a3,a0,t1
I8: sub s6,t4,t2          I5: sll a4,a0,1

Компиляторы и процессоры с внеочередным выполнением

Если перенести работу компилятора по планированию инструкций в аппаратное обеспечение, мы получим процессор с внеочередным выполнением. Разумеется, для аппаратного планирования инструкций требуется добавить немало аппаратных модулей. Но по сути обе технологии направлены на повышение эффективности выполнения инструкций процессором.

Однако при планировании инструкций компилятор может только стараться и не всегда способен найти подходящие инструкции. Например, инструкция деления может выполняться десятки тактов, и обычно компилятору трудно найти настолько много подходящих независимых инструкций. В таких случаях, если RAW-конфликт должен обрабатываться компилятором, ему всё равно остаётся только вставлять пустые инструкции.

Ещё хуже то, что некоторые RAW-конфликты невозможно устранить только средствами компилятора. Рассмотрим случай, когда инструкция, от которой есть зависимость, является инструкцией загрузки; такой RAW-конфликт называется load-use hazard:

                    T1   T2   T3  ....  T?   T?   T?   T?   T?   T?   T?
                  +----+----+----+--------------+----+
I1: lw  a0,t0,s0  | IF | ID | EX |      LS      | WB |
                  +----+----+----+--------------+----+
                       +----+----+----+----+----+
    nop X ?            | IF | ID | EX | LS | WB |
                       +----+----+----+----+----+
                                                +----+----+----+----+----+
I2: sub a1,a0,t0                                | IF | ID | EX | LS | WB |
                                                +----+----+----+----+----+

На самом деле в реальном SoC программное обеспечение почти никогда не может заранее предсказать задержку инструкции доступа к памяти, которая будет выполняться в будущем:

• При попадании в кэш данные могут вернуться через 3 такта
• При промахе кэша требуется обратиться к SDRAM, и данные могут вернуться через 30 тактов
• Если это совпадает с операцией зарядки/refresh SDRAM, данные могут вернуться через 30+? тактов
• Если частоту CPU увеличить с 500 МГц до 600 МГц, количество тактов, необходимых для возврата данных, возрастёт

Поэтому почти все современные процессоры обнаруживают и обрабатывают RAW-конфликты аппаратно. Поскольку запись в регистр выполняется в WBU, номер записываемого регистра также передаётся по конвейеру до WBU; то есть на каждой стадии можно определить, в какой регистр собирается записать соответствующая инструкция. Если регистр, который инструкция в IDU хочет прочитать, совпадает с регистром, который будет записан инструкцией на более поздней стадии конвейера, возникает RAW-конфликт:

def conflict(rs: UInt, rd: UInt) = (rs === rd)
def conflictWithStage[T <: Stage](rs1: UInt, rs2: UInt, stage: T) = {
  conflict(rs1, stage.rd) || conflict(rs2, stage.rd)
}
val isRAW = conflictWithStage(IDU.rs1, IDU.rs2, EXU) ||
            conflictWithStage(IDU.rs1, IDU.rs2, LSU) ||
            conflictWithStage(IDU.rs1, IDU.rs2, WBU)

Приведённый выше псевдокод показывает только общую идею; на практике необходимо учитывать и другие вопросы: не все инструкции записывают регистры, не все стадии в данный момент выполняют инструкции, не всем инструкциям нужно читать rs2 (например, инструкциям U-типа), значение нулевого регистра всегда равно 0 и т. д. Как написать корректный код обнаружения RAW, оставляется вам для самостоятельного размышления.

После обнаружения RAW-конфликта самый простой способ его обработки — всё то же ожидание: достаточно установить in.ready и out.valid в неактивное состояние. Как видно, эта аппаратная схема обнаружения и обработки RAW-конфликтов не требует заранее знать, когда завершится выполнение инструкции, поскольку все ожидания в ходе выполнения инструкций распространяются в конвейер через handshake-сигналы шины. Поэтому она применимее описанной выше программной схемы.

                    T1   T2   T3   T4   T5   T6   T7   T8   T9   T10  T11  T12
                  +----+----+----+----+----+
I1: add a0,t0,s0  | IF | ID | EX | LS | WB |
                  +----+----+----+----+----+
                       +----+-------------------+----+----+----+
I2: sub a1,a0,t0       | IF |         ID        | EX | LS | WB |
                       +----+-------------------+----+----+----+
                            +-------------------+----+----+----+----+
I3: and a2,a0,s0            |         IF        | ID | EX | LS | WB |
                            +-------------------+----+----+----+----+
                                                +----+----+----+----+----+
I4  xor a3,a0,t1                                | IF | ID | EX | LS | WB |
                                                +----+----+----+----+----+
                                                     +----+----+----+----+----+
I5: sll a4,a0,1                                      | IF | ID | EX | LS | WB |
                                                     +----+----+----+----+----+

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

Конфликт управления возникает, когда инструкция перехода изменяет порядок выполнения инструкций, из-за чего IFU может выбрать инструкции, которые не должны выполняться. Например, в последовательности ниже определить, какую инструкцию IFU должен выбрать в T4, можно только после того, как I3 вычислит результат перехода в T5.

                 T1   T2   T3   T4   T5   T6   T7   T8
               +----+----+----+----+----+
I1: 100   add  | IF | ID | EX | LS | WB |
               +----+----+----+----+----+
                    +----+----+----+----+----+
I2: 104   lw        | IF | ID | EX | LS | WB |
                    +----+----+----+----+----+
                         +----+----+----+----+----+
I3: 108   beq 200        | IF | ID | EX | LS | WB |
                         +----+----+----+----+----+
                              +----+----+----+----+----+
I4: ???   ???                 | IF | ID | EX | LS | WB |
                              +----+----+----+----+----+

Помимо приведённой выше branch-инструкции, jal и jalr вызывают похожие проблемы. Предположим, что I3 на рисунке выше является инструкцией перехода. Мы хотим выбрать инструкцию по адресу перехода уже в T4, а в T4 IDU как раз декодирует I3; в принципе кажется, что этого должно хватить, однако современные процессоры обычно считают, что это всё равно слишком поздно, и поэтому рассматривают ситуацию как конфликт управления.

Почему современные процессоры обрабатывают это именно так?

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

Даже исключения, генерируемые CPU, могут приводить к конфликтам управления. Когда возникает исключение, выборка инструкций должна немедленно возобновиться с адреса памяти, на который указывает mtvec, однако в общем случае в момент выборки процессор ещё не знает, вызовет ли выполнение этой инструкции исключение.

Все описанные выше проблемы возникают потому, что на стадии выборки невозможно определить, какая инструкция действительно должна быть выбрана следующей. Если выбрать ожидание, нужно ждать, пока предыдущая инструкция почти полностью завершится, прежде чем станет известен истинный адрес следующей инструкции. Например, инструкция доступа к памяти должна дождаться завершения доступа к памяти и через сигнал resp шины подтвердить, что во время доступа исключение не возникло. Очевидно, такая схема не позволит конвейеру инструкций нормально течь и значительно уменьшит пропускную способность выполнения инструкций. Если же не ждать, можно выбрать некоторые инструкции, которые не должны выполняться; без дополнительной обработки переход состояния процессора станет несовместимым с автоматом состояний ISA, что приведёт к неверному выполнению.

Для обработки конфликтов управления современные процессоры обычно используют технологию «спекулятивного выполнения». По сути спекулятивное выполнение — это техника предсказания. Основная идея состоит в том, чтобы во время ожидания заранее предположить один из вариантов; если предположение верно, это равносильно тому, что правильный выбор был сделан заранее, и тем самым удаётся сэкономить время ожидания. Спекулятивное выполнение включает три части:

• Стратегия выбора — до получения правильного результата предположить некоторый вариант по определённой стратегии
• Механизм проверки — после получения правильного результата проверить, совпадает ли сделанное ранее предположение с правильным результатом
• Восстановление после ошибки — если проверка обнаруживает несовпадение, откатиться к состоянию на момент применения стратегии выбора и сделать правильный выбор на основе полученного результата

Для конфликтов управления простейшая стратегия спекулятивного выполнения — «всегда предполагать, что следующей будет выполнена следующая статическая инструкция». Рассмотрим реализацию этой стратегии с точки зрения трёх частей выше:

• Стратегия выбора — очень проста: позволить IFU постоянно выбирать инструкцию по адресу PC + 4.
• Механизм проверки — согласно семантике инструкций только branch- и jump-инструкции, а также исключения могут изменить поток выполнения CPU; во всех остальных случаях выполнение идёт последовательно. Поэтому в остальных случаях предположение всегда верно и дополнительная проверка не нужна. Только при branch/jump или исключении нужно проверить, совпадает ли результат перехода с предположением, то есть равен ли он PC + 4.
• Восстановление после ошибки — если обнаружено, что результат перехода не равен PC + 4, значит предыдущее предположение было неверным; инструкции, выбранные на основе этого предположения, не должны выполняться и должны быть удалены из конвейера. Это действие называется «flushing»; одновременно IFU должен начать выборку с правильного адреса перехода.

Прирост производительности от спекулятивного выполнения связан с точностью предположения. При высокой точности IFU с большой вероятностью заранее выбирает правильную инструкцию, экономя ожидание; при низкой точности IFU часто выбирает инструкции, которые не должны выполняться, а затем они сбрасываются. В это время конвейер ведёт себя так, словно полезных инструкций не выполнялось, что снижает пропускную способность. В частности:

• Поскольку исключения при работе процессора происходят редко, подавляющее большинство инструкций не вызывают исключения, поэтому точность такой стратегии для исключений близка к 100%
• Результат branch-инструкции либо «taken», либо «not taken»; приведённая стратегия эквивалентна постоянному предсказанию «not taken», поэтому статистически её точность для branch-инструкций близка к 50%
• Jump-инструкция безусловно переходит на целевой адрес, причём возможных целевых адресов много; вероятность перехода точно на PC + 4 очень мала, поэтому точность этой стратегии для jump-инструкций близка к 0%

Согласно анализу выше, спекулятивное выполнение, с одной стороны, позволяет корректно обрабатывать конфликты управления; с другой стороны, по сравнению с пассивным ожиданием оно также может дать некоторый прирост производительности. Однако для branch- и jump-инструкций у описанной схемы остаётся большой потенциал для улучшения, который мы рассмотрим далее.

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

• С точки зрения требований flush должен восстановить состояние процессора к моменту до возникновения конфликта управления; поэтому детали реализации можно вывести из модели автомата состояний. Она говорит нам, что состояние процессора определяется последовательностными схемами, а обновления состояния управляются управляющими сигналами. Следовательно, для реализации flush достаточно сделать соответствующие управляющие сигналы неактивными. Например, установив valid в неактивное состояние, можно непосредственно сбросить инструкции, выполняемые большинством компонентов.
• Однако если компоненты всё ещё содержат состояние, влияющее на управляющие сигналы, требуется дополнительное внимание, например к автомату состояний в icache. В частности, уже отправленные AXI-запросы нельзя отозвать, поэтому необходимо дождаться их завершения.
• Спекулятивное выполнение означает, что выполняемая сейчас операция может оказаться не той, которая действительно нужна в будущем; если предположение неверно, связанные операции должны быть отменены. Но некоторые операции трудно отменить: обновление регистрового файла, обновление CSR, запись в память, доступ к периферии и т. д. После изменения состояния этих модулей восстановить старое состояние трудно. Поэтому состояние таких модулей можно обновлять только после подтверждения правильности предположения.

Реализовать простой конвейерный процессор

Обработайте различные конфликты самым простым способом, чтобы реализовать базовую структуру конвейера. После имплементации попробуйте запустить microbench и проверить корректность реализации.

Подсказка:

• Чтобы DiffTest работал корректно, возможно, потребуется изменить сигналы, передаваемые в среду симуляции
• Пока можно игнорировать реализацию, связанную с обработкой исключений; её мы реализуем далее

Вложенное спекулятивное выполнение

Подумайте: если встретятся несколько branch- или jump-инструкций подряд, сможет ли ваша реализация по-прежнему работать корректно?

При реализации исключений в конвейерном процессоре необходимо учитывать следующие детали:

• При возникновении исключения mepc должен быть установлен в значение PC инструкции, на которой произошло исключение; это свойство называется «точным исключением» (precise exception). Если оно не выполняется, то при возврате из обработчика исключения через mret мы не сможем точно вернуться к инструкции, где произошло исключение, и состояния до и после исключения будут несовместимы. Это может помешать системному ПО использовать механизм исключений для реализации ключевых механизмов современных ОС, таких как переключение процессов и demand paging. Но в конвейерном процессоре PC в IFU постоянно меняется; к моменту, когда инструкция вызывает исключение, PC в IFU уже не соответствует этой инструкции. Чтобы получить PC, соответствующий инструкции, при выборке в IFU необходимо передавать соответствующий PC вниз по конвейеру вместе с инструкцией.
• Инструкция может вызвать исключение во время спекулятивного выполнения, но если спекуляция оказалась неверной, эта инструкция вообще не должна была выполняться, и выброшенное ею исключение не должно обрабатываться. Поэтому все операции, обновляющие состояние процессора при обработке исключения, должны вступать в силу только после подтверждения правильности спекуляции, включая запись mepc и mcause, переход по адресу из mtvec и т. д.
• Обновление mcause зависит от типа исключения; в RISC-V разные номера исключений формируются разными компонентами. Сформированный номер исключения также необходимо передавать вниз по конвейеру, и mcause можно записывать только после подтверждения правильности спекуляции.

Номер исключения	Описание исключения	Компонент, в котором исключение впервые возникло
0	Невыровненный адрес инструкции	IFU
1	Ошибка доступа к инструкции	IFU
2	Недопустимая инструкция	IDU
3	Точка остановки(Breakpoint)	IDU
4	Невыровненный адрес загрузки	LSU
5	Ошибка доступа при загрузке	LSU
6	Невыровненный адрес Store/AMO	LSU
7	Ошибка доступа Store/AMO	LSU
8	Вызов окружения из U-mode	IDU
9	Вызов окружения из S-mode	IDU
11	Вызов окружения из M-mode	IDU
12	Ошибка страницы инструкции	IFU
13	Ошибка страницы загрузки	LSU
15	Ошибка страницы Store/AMO	LSU

Реализовать конвейер с поддержкой обработки исключений

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

Одновременное возникновение нескольких исключений

В конвейерном процессоре разные стадии выполняют разные инструкции, а это означает, что разные стадии могут одновременно породить разные исключения. Например, IFU обнаруживает невыровненный адрес инструкции, IDU — недопустимую инструкцию, а LSU — ошибку доступа к памяти при загрузке. Как это следует обрабатывать?

Хотя сейчас мы не требуем реализовать все исключения, вы всё равно можете подумать, способен ли ваш дизайн корректно обработать такую ситуацию.

Суперконвейерная архитектура Intel

До 2005 года Intel некоторое время использовала суперконвейерную технологию в погоне за экстремально высокими частотами. В феврале 2004 года Intel выпустила процессор с кодовым названием архитектуры Prescott, глубина конвейера которого достигала беспрецедентных 31 стадии; даже на тогдашнем техпроцессе 90 нм его тактовая частота достигала 3,8 ГГц. Однако измерения показали, что по сравнению с предыдущим поколением Northwood с 20 стадиями производительность этого процессора почти не выросла; вместо этого он стал самым горячим и самым энергозатратным одноядерным процессором в истории x86. Более того, если бы не проблемы с тепловыделением и энергопотреблением, его частота могла быть ещё выше 3,8 ГГц: за год до выпуска Intel заявляла, что процессор сможет достигнуть 5 ГГц.

На уровне микроархитектуры эффективность выполнения 31-стадийного конвейера также оказалась неудовлетворительной. С одной стороны, конвейер был насыщен конфликтами данных; множество инструкций вынуждены были ждать из-за RAW-конфликтов. С другой стороны, цена flush конвейера при неверной спекуляции branch-инструкции была очень высокой. Предположим, что процессор вычисляет, взята ли ветвь, на 26-й стадии; при неверной спекуляции нужно сбросить все инструкции, выбранные за предыдущие 25 тактов. В частности, Prescott является процессором с множественной выдачей, способным выполнять 4 простые ALU-операции за такт; если оценивать его как 4-issue, то при неверной спекуляции потребуется сбросить 25 * 4 = 100 инструкций! Хотя Prescott применял некоторые продвинутые технологии повышения точности спекуляции, согласно измерениям производительность довольно многих программ всё равно снизилась из-за чрезмерно длинного конвейера.

Позже Intel отказалась от этого агрессивного суперконвейерного направления, и глубина конвейера последующих архитектур обычно составляет около 15 стадий и максимум не превышает 20.

Тестирование и верификация конвейерных процессоров

Объект обработки конвейера — инструкции, а значит разные последовательности инструкций по-разному влияют на поведение конвейера. Поэтому верификация конвейера должна использовать последовательности инструкций в качестве тестовых входов и охватывать как можно больше различных ситуаций. По поведению инструкций в конвейере их можно грубо разделить на следующие 10 типов:

• Инструкции, вычисление которых ALU может завершить за один такт: сложение, вычитание, логические операции и сдвиги
• Инструкции передачи потока управления, разделённые на 3 типа: условные ветвления, jal, jalr
• Инструкции доступа к памяти, разделённые на 2 типа: load, store
• CSR-инструкции
• ecall, mret
• fence.i

Даже если рассматривать только комбинации этих 10 типов инструкций в традиционном 5-стадийном конвейере, уже получается вариантов. На самом деле необходимо также учитывать различные конфликты: доступ к памяти может требовать ожидания, между инструкциями существуют зависимости по данным, инструкции передачи управления вызывают flush конвейера...... Короче говоря, возможных последовательностей инструкций, образованных комбинациями разных ситуаций, слишком много. Даже разработка генератора инструкций не позволяет легко гарантировать покрытие всех случаев, а вручную спроектировать столько тестов ещё сложнее.

Корректность процессора нельзя доказать традиционными наборами тестов инструкций

Если вы знакомы с наборами тестов инструкций вроде riscv-tests, нужно понимать, что прохождение riscv-tests не означает, что конвейерный NPC корректен. На самом деле число тестов в riscv-tests намного меньше приблизительно рассчитанных выше 100000, что уже показывает: существуют последовательности инструкций, которые riscv-tests не покрывает. Более фундаментально, riscv-tests проверяет поведение отдельных инструкций, тогда как полноценное тестирование конвейерного процессора требует перебора различных последовательностей инструкций. Поэтому если ваш конвейерный NPC проходит только традиционные наборы вроде riscv-tests, не следует быть на 100% уверенным в корректности его реализации.

Поскольку вручную проектировать тесты сложно, попробуем поручить это инструментам! Вспомните средство формальной верификации, которое мы использовали при проверке кэша: оно автоматически ищет тестовые случаи, нарушающие assert; если таких случаев не найдено, корректность дизайна считается доказанной. Если применить формальную верификацию к конвейерному NPC, инструмент сможет автоматически находить ошибочные последовательности инструкций!

Для формальной верификации нам также нужен REF и подходящие условия проверки (то есть assert). В качестве REF требуется другая реализация, способная корректно выполнять последовательности инструкций. Поскольку используемый инструмент формальной верификации может работать только на уровне RTL, сейчас невозможно интегрировать эмуляторы наборов инструкций вроде NEMU и Spike. Однако можно использовать разработанный ранее однотактный NPC: как другая микроархитектурная реализация ISA RISC-V он должен корректно выполнять последовательности инструкций.

Что касается условий верификации, одна идея — подобно DiffTest, после выполнения одинаковых инструкций DUT и REF проверять согласованность состояний GPR. В C проверка равенства всех GPR — это всего один вызов memcmp(), который стоит недорого; но в формальной верификации проверка равенства всех GPR становится ограничением для «решения уравнений» и создаёт значительные накладные расходы для процесса решения BMC. Поэтому необходимо найти более простой метод сравнения.

Вспоминая модель автомата состояний, новое состояние зависит от текущего состояния и перехода состояния. Поэтому вместо непосредственного сравнения новых состояний можно сравнить с другой стороны: если текущие состояния согласованы и переходы состояний также согласованы, то новые состояния также должны быть согласованы. В общем случае описание перехода состояния значительно меньше описания самого состояния (то есть пространства состояний), поэтому проверка согласованности переходов обычно проще. Возьмём в качестве примера состояние GPR: хотя пространство состояний GPR составляет бит, одна инструкция RISC-V записывает максимум один GPR. Достаточно записывать, какой GPR и каким значением обновляет инструкция, и сравнивать записи DUT и REF; нет необходимости напрямую сравнивать 512-битные пространства состояний GPR, что значительно уменьшает накладные расходы сравнения.

На основании приведённого анализа легко написать псевдокод верхнего модуля верификации. Здесь Chisel используется как псевдокод; если вы разрабатываете на Verilog, можно использовать те же идеи.

class PipelineTest extends Module {
  val io = IO(new Bundle {
    val inst = Input(UInt(32.W))
    val rdata = Input(UInt(XLEN.W))
  })

  val dut = Module(new PipelineNPC)
  val ref = Module(new SingleCycleNPC)

  dut.io.imem.inst  := io.inst
  dut.io.imem.valid := ...
  dut.io.dmem.rdata := io.rdata
  dut.io.dmem.valid := ...
  // ...

  ref.io.imem.inst := dut.io.wb.inst
  // ...

  when (dut.io.wb.valid) {
    assert(dut.io.wb.rd  === ref.io.wb.rd)
    assert(dut.io.wb.res === ref.io.wb.res)
  }
}

Приведённый псевдокод даёт лишь приблизительный каркас; существует ещё много деталей, которые необходимо учитывать и дополнить:

• Чтобы уменьшить пространство решения BMC, DUT содержит только сам конвейер, без кэша и различных периферийных модулей; задержку доступа к памяти из-за промахов кэша можно реализовать через handshake-сигналы
• Инструкции являются одним из входов верхнего модуля верификации, то есть BMC будет перебирать различные инструкции; под действием bound BMC будет перебирать различные комбинации инструкций в разных тактах, фактически перебирая все последовательности инструкций заданной длины
• Сгенерированная последовательность инструкций по порядку подаётся в IFU DUT, но поскольку в конвейерном NPC инструкция выполняется несколько тактов, а в однотактном NPC — только один такт, DUT и REF необходимо синхронизировать: инструкция должна подаваться в REF только после завершения её выполнения DUT. Поэтому завершённую в данный момент инструкцию нужно получать из WBU DUT
• Помимо сравнения номера записываемого GPR rd и его значения res, необходимо сравнивать PC, чтобы проверить корректность передачи потока управления. При этом можно сравнивать новое значение PC, что позволит обнаружить рассогласование PC на один такт раньше
• Некоторые инструкции не записывают GPR; для них сравнивать rd и res не требуется
• Для load-инструкций результат доступа к памяти также является одним из входов конвейера, поэтому его нужно вывести на порты верхнего модуля верификации. Чтобы после выполнения одной и той же load-инструкции DUT и REF оказались в одинаковом состоянии, необходимо также гарантировать, что они прочитали одинаковые данные
• Мы отдельно не сравниваем результаты выполнения store-инструкций по двум основным причинам:
  1. Записываемые данные и адрес записи берутся из GPR; если они неверны, значит какая-то более старая инструкция до store записала неправильное значение в GPR, и это будет обнаружено механизмом выше
  2. Если данные и адрес записи верны, но сигналы AXI write channel неверны, эта проблема относится к реализации AXI-шины, а не к верификации конвейера. В принципе, проверку AXI-сигналов можно добавить в framework верификации конвейера, но это увеличит ограничения BMC и накладные расходы решения
• Handshake-сигналы IFU и LSU должны обрабатываться корректно
• Запись CSR также отдельно не сравнивается, потому что при неправильной записи CSR можно использовать дополнительную инструкцию, чтобы прочитать значение CSR в GPR и тем самым проявить ошибку; так сравнение записи CSR сводится к сравнению записи GPR
• Необходимо также обеспечить одинаковое начальное состояние GPR и CSR в DUT и REF, поэтому GPR и CSR нужно инициализировать. Обратите внимание: это требование только формальной верификации; при симуляции и tape-out не все GPR и CSR обязаны быть инициализированы
• Поскольку последовательность инструкций генерируется BMC, без ограничений она может содержать недопустимые инструкции. Если NPC не поддерживает обработку исключения illegal instruction, поведение NPC при таких инструкциях не определено, что мешает сравнению результатов. Один из способов решения — разрешить BMC генерировать только допустимые инструкции. Для этого можно использовать assume, предоставляемый Chisel и SystemVerilog и задающий предусловия верификации. Например, если isIllegal означает «результат декодирования — недопустимая инструкция», то assume(!isIllegal) задаёт предусловие «инструкция не является недопустимой»; тогда BMC решает задачу с этим предусловием и исключает недопустимые инструкции из последовательности
• Необходимо учитывать адреса CSR-регистров в CSR-инструкциях; аналогично assume можно использовать, чтобы ограничить адреса CSR диапазоном реализованных CSR
• Также нужно учитывать невыровненный доступ к памяти; без ограничений адреса, вычисленные сгенерированными инструкциями доступа к памяти, могут быть невыровненными. Эту проблему также можно решить с помощью assume

Перейти на более эффективный инструмент model checking

20.08.2024 в 02:30:00 мы изменили способ вызова инструмента формальной верификации, заменив вызов solver Z3 на model checker BtorMC для повышения эффективности формальной верификации. Если вы разрабатываете на Chisel, обратитесь к подразделу «Простой пример формальной верификации» в разделе о кэше.

Протестировать реализацию конвейера с помощью формальной верификации

Хотя это необязательно, мы настоятельно рекомендуем протестировать конвейер с помощью формальной верификации. Однако нужно внимательно продумать условия верификации вроде assert и assume; если они записаны неправильно, возможны ложноположительные или ложноотрицательные результаты: ложноположительные можно обнаружить при отладке и исправить соответствующие условия, а ложноотрицательные обнаружить трудно. Поэтому эта задача фактически также проверяет глубину вашего понимания деталей конвейера.

Кроме того, для bound BMC можно выбрать подходящий параметр, чтобы инструмент формальной верификации перебрал достаточное количество последовательностей инструкций и охватил разные комбинации конфликтов. Обычно bound может потребоваться больше 10, из-за чего решение может занять несколько часов или даже десятки часов; но с точки зрения удобства инструмента это всё равно очень выгодно, поскольку даже несколько дней ручного написания тестов могут не дать случаев, покрывающих некоторые крайние ситуации. Чтобы быстро найти некоторые контрпримеры, можно начать с малого bound и постепенно увеличивать его.

Использование формальной верификации для тестирования более сложных процессоров

Исследовательская группа Института программного обеспечения Китайской академии наук разработала framework тестирования RISC-V-процессоров на основе формальной верификации; с его помощью они даже нашли некоторые очень скрытые ошибки в процессоре NutShell, способном загружать Linux. Подробности см. в их проекте nutshell-fv. Этот пример также показывает преимущества формальной верификации. Однако функциональность текущего NPC сильно упрощена, поэтому для интеграции с этим framework, возможно, потребуется изменить и ваш код, и код самого framework. Если вам интересно, прочитайте README проекта, чтобы узнать, как им пользоваться, и изучите код, чтобы понять детали framework.

Заставляем конвейер течь

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

Оценить производительность простого конвейера

Перед оптимизацией необходимо оценить производительность описанного выше простого конвейера. По сравнению с многотактным процессором до внедрения конвейера насколько выросла производительность? Если производительность, наоборот, снизилась, рекомендуем использовать счётчики производительности и глубоко разобраться в причинах.

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

• Недостаточная способность подачи инструкций; в конвейер поступает недостаточно инструкций
• Недостаточная способность подачи данных; выполнение инструкций доступа к памяти останавливается
• Недостаточная вычислительная эффективность; из-за существования трёх перечисленных выше типов конфликтов конвейер приходится останавливать

Найти уязвимое место производительности

Чтобы повысить эффективность конвейера, сначала нужно определить уязвимое место производительности. Попробуйте добавить больше счётчиков производительности в конвейерный процессор и проанализировать текущие узкие места по различным причинам остановки.

Решайте, применять ли следующие оптимизации, исходя из своего дизайна

Ниже представлены некоторые потенциально полезные оптимизации. Стоит ли внедрять их в RTL, зависит от многих факторов: вашего предыдущего дизайна, анализа текущих счётчиков производительности и оставшейся доступной площади. Однако перед RTL-реализацией мы всё равно требуем оценить ожидаемый прирост производительности соответствующей техники; это очень важная тренировка архитектурного проектирования: вы можете решить не реализовывать некоторую оптимизацию, но должны обосновать решение количественными данными.

Однако оптимизация, соответствующая «снижению остановок из-за конфликтов данных», является важной темой, поэтому мы считаем её обязательной.

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

Повышение способности подачи инструкций

В предыдущем многотактном процессоре, если каждая инструкция выполнялась за 5 тактов, достаточно было способности подачи инструкций 0,2 инструкции/такт, чтобы удовлетворить потребление многотактного процессора. Но в конвейерном процессоре идеальная потребность возрастает до 1 инструкции/такт; если способность подачи инструкций не достигает соответствующего уровня, преимущества конвейера невозможно реализовать. Однако при промахе icache необходимо обращаться к памяти, и указанной способности подачи в этом случае заведомо достичь нельзя; поэтому мы сосредоточимся на способности icache подавать инструкции при попадании. Нужно ли оптимизировать icache здесь, зависит от конкретной реализации icache.

Если ваш icache способен за 1 такт определить попадание и при попадании вернуть инструкцию IFU, его способность подачи уже близка к 1 инструкции/такт и в целом удовлетворяет потребности конвейерного процессора. В таком случае дополнительно повышать способность подачи инструкций практически не требуется, но цена может состоять в более низкой частоте, поскольку icache должен выполнять довольно много операций за один такт, что мешает конвейеру работать на более высокой частоте.

Если же даже при попадании icache требуется несколько тактов, чтобы вернуть инструкцию IFU, способность подачи icache составляет максимум 0,5 инструкции/такт или ещё меньше. При такой способности производительность конвейера значительно ограничивается. Предположим, icache требуется 3 такта, чтобы при попадании вернуть инструкцию IFU. Тогда пространственно-временная диаграмма выглядит следующим образом. Поскольку cache произносится так же, как cash, в англоязычной литературе $ иногда используют для обозначения cache; ниже для простоты I$ обозначает icache, заменяя прежнее IF, поскольку теперь время ожидания IF совпадает со временем доступа к icache:

       T1   T2   T3   T4   T5   T6   T7   T8   T9   T10  T11  T12  T13
     +--------------+----+----+----+----+
 I1  |      I$      | ID | EX | LS | WB |
     +--------------+----+----+----+----+
                    +--------------+----+----+----+----+
 I2                 |      I$      | ID | EX | LS | WB |
                    +--------------+----+----+----+----+
                                   +--------------+----+----+----+----+
 I3                                |      I$      | ID | EX | LS | WB |
                                   +--------------+----+----+----+----+

Чтобы повысить способность icache подавать инструкции, в некотором смысле нужно повысить и пропускную способность самого icache. Это требование очень похоже на упомянутое ранее «повышение пропускной способности выполнения инструкций», поэтому естественно попробовать конвейеризировать доступ к icache!

       T1   T2   T3   T4   T5   T6   T7   T8   T9
     +----+----+----+----+----+----+----+
 I1  | I$1| I$2| I$3| ID | EX | LS | WB |
     +----+----+----+----+----+----+----+
          +----+----+----+----+----+----+----+
 I2       | I$1| I$2| I$3| ID | EX | LS | WB |
          +----+----+----+----+----+----+----+
               +----+----+----+----+----+----+----+
 I3            | I$1| I$2| I$3| ID | EX | LS | WB |
               +----+----+----+----+----+----+----+

Оценить прирост производительности от конвейеризации icache

Попробуйте приблизительно оценить прирост производительности от конвейеризации icache на основе счётчиков производительности.

На рисунке выше доступ к icache дополнительно разделён на 3 стадии, а эти стадии перекрываются во времени с помощью конвейеризации, так что пропускная способность icache при попаданиях приближается к 1 инструкции/такт. Для реализации конвейерного icache можно спроектировать эти стадии в соответствии с процессом переходов автомата состояний icache при попадании. Это очень похоже на превращение процессора в конвейер и даже проще, поскольку в работе icache нет понятия конфликтов управления. Разумеется, при промахе конвейер icache всё равно должен останавливаться, а доступ к памяти и обновление icache должны управляться автоматом состояний. Поскольку промах приводит к обновлению icache, это может создавать проблемы, похожие на конфликты данных; корректный способ обработки зависит от конкретной реализации.

Реализовать конвейерный icache

Если вашему icache требуется несколько тактов для возврата инструкции IFU даже при попадании, попробуйте использовать идею конвейера инструкций и конвейеризировать доступ к icache, тем самым повысив его способность подавать инструкции. После реализации попробуйте с помощью счётчиков производительности и benchmark проверить, соответствует ли улучшение подачи инструкций ожиданиям.

Разделение доступа icache на 3 стадии выше — лишь пример; количество и границы стадий следует определить по собственному дизайну. Если ранее вы реализовали конвейер с помощью чего-то вроде PipelineConnect(), то обнаружите, что конвейеризация icache реализуется легко: нужно лишь определить информацию, передаваемую между стадиями, и около 90% работы уже сделано.

После реализации сравните результат с ранее оценённым приростом производительности, чтобы проверить соответствие ожиданиям.

Снижение остановок из-за конфликтов данных

В простом конвейере выше RAW-конфликты обрабатывались остановкой и ожиданием. Такой подход требует ожидания, пока зависимый регистр получит новое значение, прежде чем остановленная инструкция сможет продолжить выполнение; очевидно, это уменьшает пропускную способность конвейера.

Можно заметить, что новое значение зависимого регистра записывается на стадии WB, но фактически оно вычисляется уже на стадии EX и затем передаётся по конвейеру в LS и WB. Поэтому можно заранее брать вычисленное новое значение с этих стадий для последующих инструкций, позволяя им получить правильный исходный операнд и начать выполнение, не дожидаясь обновления самого регистра. Эта техника называется «forwarding» или «bypass».

                    T1   T2   T3   T4   T5   T6   T7   T8
                  +----+----+----+----+----+
I1: add a0,t0,s0  | IF | ID | EX | LS | WB |
                  +----+----+----+----+----+
                                |    |    |
                                V    |    |
                       +----+----+----+----+----+
I2: sub a1,a0,t0       | IF | ID | EX | LS | WB |
                       +----+----+----+----+----+
                                     |    |
                                     V    |
                            +----+----+----+----+----+
I3: and a2,a0,s0            | IF | ID | EX | LS | WB |
                            +----+----+----+----+----+
                                          |
                                          V
                                 +----+----+----+----+----+
I4  xor a3,a0,t1                 | IF | ID | EX | LS | WB |
                                 +----+----+----+----+----+

Оценить идеальный прирост производительности от forwarding

Как видно, forwarding позволяет хорошо устранить RAW-остановки, кроме load-use hazard. Для load-use hazard инструкция load должна дождаться чтения данных прежде, чем их можно будет перенаправить, поэтому до этого конвейер всё равно приходится останавливать.

Попробуйте оценить идеальный прирост производительности от forwarding на основе счётчиков производительности.

Сначала рассмотрим изменения data path при forwarding. В описанном конвейере существуют 3 источника forwarding: стадии EX, LS и WB; каждая из них может нести данные, пригодные для перенаправления. Но forwarding нельзя выполнять безусловно: источник должен удовлетворять следующим условиям — он действительно будет записывать регистр, номер записываемого регистра совпадает с номером зависимого регистра, а данные уже готовы. Первые два условия совпадают с условиями обнаружения RAW, поэтому эту логику можно переиспользовать; последнее условие зависит от поведения инструкции. Большинство вычислительных инструкций получают результат на стадии EX, поэтому результат EX можно перенаправить в ID; но load-инструкция на EX вычисляет только адрес доступа к памяти, поэтому её нельзя перенаправлять на EX, а на LS она должна дождаться handshake R-канала шины и получения возвращённых данных, поэтому до этого момента перенаправлять её также нельзя.

Помимо изменений data path необходимо учитывать изменения control path. Раньше в простом конвейере при обнаружении RAW конвейер всегда останавливался. При forwarding условия остановки становятся следующими:

• Если стадия ID не обнаруживает RAW-конфликт, конвейер останавливать не нужно — как и раньше
• Если стадия ID обнаруживает RAW-конфликт и какая-либо стадия удовлетворяет условиям forwarding, конвейер останавливать не нужно, а перенаправленные данные используются как выход стадии ID
• Если стадия ID обнаруживает RAW-конфликт, но ни одна стадия не удовлетворяет условиям forwarding, конвейер необходимо остановить

Особое внимание требуется, если условиям forwarding одновременно соответствуют несколько инструкций. Рассмотрим следующую последовательность:

                      T1   T2   T3   T4   T5   T6   T7   T8
                    +----+----+----+----+----+
I1: add a0, a0, a1  | IF | ID | EX | LS | WB |
                    +----+----+----+----+----+
                         +----+----+----+----+----+
I2: add a0, a0, a1       | IF | ID | EX | LS | WB |
                         +----+----+----+----+----+
                              +----+----+----+----+----+
I3: add a0, a0, a1            | IF | ID | EX | LS | WB |
                              +----+----+----+----+----+
                                   +----+----+----+----+----+
I4: add a0, a0, a1                 | IF | ID | EX | LS | WB |
                                   +----+----+----+----+----+

Предположим, I1 не зависит от более старых инструкций, поэтому её выполнение не нужно останавливать. I2 зависит от результата I1, но forwarding позволяет в T3 перенаправить результат I1 со стадии EX в I2 на стадии ID, поэтому I2 также не останавливается. Для I3 в T4 условиям forwarding соответствуют и I2 на EX, и I1 на LS; однако с точки зрения автомата состояний ISA инструкции выполняются последовательно, поэтому a0, читаемый I3, должен быть результатом самой последней записи в a0, а значит forwarding должен идти от I2 на EX. Аналогично для I4 в T5 одновременно подходят I3 на EX, I2 на LS и I1 на WB, но нужно выбрать I3 на EX. То есть если условиям forwarding соответствуют несколько инструкций, следует выбирать самую молодую.

Реализовать forwarding

Согласно описанию выше имплементируйте forwarding в конвейере, чтобы устранить большинство RAW-конфликтов. После реализации сравните результат с ранее оценённым приростом производительности и проверьте соответствие ожиданиям.

Схема forwarding из учебников

В схеме выше результаты вычислений других стадий перенаправляются в стадию ID, а затем правильный операнд выбирается перед помещением в регистр стадии конвейера; большинство учебников, напротив, перенаправляют данные на стадии EX и LS, а правильный операнд выбирают непосредственно перед вычислением.

Попробуйте сравнить эти две схемы. Если не можете определить различия теоретически, можно реализовать обе и сравнить IPC, частоту, площадь и другие показатели.

Снижение остановок из-за конфликтов управления

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

Оценить прирост производительности от оптимизации остановок, связанных с конфликтами управления

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

Для снижения отрицательного влияния очистки конвейера на эффективность выполнения процессора можно рассмотреть два направления:

1. Уменьшить стоимость одного flush конвейера. Для этого нужно как можно раньше вычислять результат branch-инструкции. В некоторых учебниках предлагается вычислять результат ветвления на стадии ID, что очевидно повышает IPC конвейера, однако такую схему необходимо всесторонне оценить также с точки зрения частоты и площади.
2. Уменьшить количество flush конвейера. Для этого необходимо повысить точность спекуляции. Согласно предыдущему анализу, точность предположения «исключение не произойдёт» уже близка к 100%, поэтому основной вопрос — точность спекуляции для branch- и jump-инструкций.

Точность спекуляции branch-инструкций обычно повышают с помощью технологии «предсказания ветвлений»; модуль, выполняющий такое предсказание, называется branch predictor. Результат branch-инструкции может быть только «taken» или «not taken», поэтому предсказание ветвления сводится к выбору одного из двух вариантов; способ формирования предсказания называется алгоритмом предсказания ветвлений. В зависимости от того, используется ли информация времени выполнения, алгоритмы делятся на статические и динамические. Здесь сначала рассмотрим статические алгоритмы; динамические будут рассмотрены на этапе A.

Почувствовать важность branch predictor в современных процессорах

Попробуйте подсчитать долю branch-инструкций среди динамически выполненных инструкций, то есть найти x, если в среднем на каждые x инструкций приходится одна branch-инструкция.

Предположим, что в идеальном пятистадийном конвейерном процессоре способность подачи инструкций составляет 1 инструкция/такт, отсутствуют структурные конфликты и конфликты данных, задержка всех обращений к памяти равна 0 тактов, jump-инструкции всегда предсказываются правильно, но branch-инструкции могут быть предсказаны неверно, а результат ветвления вычисляется на стадии EX. На основе полученного x вычислите IPC процессора при разной точности предсказания branch: 100%, 99.5%, 99%, 95%, 90%, 80%.

Улучшите этот процессор до 15-стадийного внеочередного конвейера с single-issue, в котором branch-инструкция вычисляет результат на 13-й стадии; остальные предположения оставьте прежними и снова вычислите IPC для разных точностей предсказания.

Затем улучшите процессор до 15-стадийного внеочередного quad-issue конвейера; остальные предположения оставьте прежними и ещё раз вычислите IPC при разных точностях предсказания.

Статическое предсказание использует только саму branch-инструкцию. Поскольку сама инструкция не меняется во время выполнения программы, для заданной branch-инструкции и заданного статического алгоритма результат предсказания всегда одинаков. Описанная выше стратегия «всегда предполагать выполнение следующей статической инструкции» с точки зрения branch prediction является алгоритмом «always not taken». Другой статический алгоритм — «always taken».

На самом деле результат branch-инструкции имеет статистическую зависимость от направления целевого адреса ветвления. Это связано с поведением циклов в программах: например, когда цель ветвления направлена вперёд (к более молодой инструкции), это может быть выход из цикла, поэтому чаще ветвление не принимается; когда цель направлена назад (к более старой инструкции), это может быть возврат к телу цикла, поэтому чаще ветвление принимается. Статический алгоритм, использующий это свойство, называется BTFN (Backward Taken, Forward Not-taken): если цель ветвления направлена назад — предсказывать taken, иначе — not taken. Для реализации достаточно посмотреть на знаковый бит смещения B-type инструкции. В руководстве RISC-V также рекомендуется, чтобы компиляторы генерировали код в соответствии с BTFN:

Software should also assume that backward branches will be predicted taken and
forward branches as not taken, at least the first time they are encountered.

Важный показатель алгоритма branch prediction — точность предсказания. Подобно случаю с icache, для заданной программы набор выполняемых branch-инструкций и результат каждой из них фиксированы. Достаточно получить itrace программы, чтобы быстро вычислить точность алгоритма предсказания без RTL-симуляции. Более того, itrace уже содержит полный поток инструкций; трассы не-branch инструкций не влияют на результаты выполнения branch-инструкций. Поэтому на самом деле нужен только trace branch-инструкций, который мы называем btrace (branch trace).

Согласно этому анализу, достаточно реализовать функциональный симулятор branch predictor, который мы называем branchsim. branchsim получает btrace, предсказывает taken/not taken для каждой branch-инструкции согласно алгоритму, затем сравнивает предсказание с результатом из btrace и вычисляет точность алгоритма. btrace можно быстро генерировать с помощью NEMU.

Реализовать branchsim

Согласно описанию выше реализуйте простой симулятор branch prediction — branchsim, затем оцените точность перечисленных статических алгоритмов и на основе этой точности оцените прирост производительности от алгоритма предсказания.

Если вам интересны динамические алгоритмы, можете сначала изучить соответствующие материалы, затем реализовать эти алгоритмы в branchsim и оценить их точность.

Подобно cachesim, branchsim также может служить REF для производительности branch prediction. Например, простой конвейер выше использует статическую стратегию «always not taken», и соответствующие счётчики производительности должны полностью совпадать со статистикой branchsim.

После выбора с помощью branchsim алгоритма branch prediction с хорошей производительностью можно рассмотреть реализацию branch predictor в процессоре. Обычно результат предсказания нужно передать IFU: если предсказано taken, IFU должен выбирать инструкцию с целевого адреса branch; иначе — с PC + 4. Но определить, является ли инструкция branch-инструкцией, можно только на стадии ID, и её целевой адрес также становится известен только на стадии ID. На стадии IF имеется лишь значение PC, и получить эти данные для предсказания трудно.

Проблему решают таблицей соответствия PC и целевых адресов ветвлений; эта таблица называется BTB (Branch Target Buffer). BTB можно рассматривать как специальный кэш, индексируемый значением PC. Если происходит попадание, это означает, что PC соответствует branch-инструкции, и из BTB можно прочитать её целевой адрес; если промах — считается, что инструкция по этому PC не является branch-инструкцией, и IFU выбирает PC + 4. Кроме того, BTB необходимо заполнять и обновлять в ходе выполнения процессора; в принципе BTB можно обновить уже тогда, когда branch-инструкция декодируется на стадии ID. Число записей BTB обычно ограничено; если свободной записи при обновлении нет, согласно принципу локальности следует заменить старую запись. При сбросе процессора все записи BTB невалидны, и корректный target branch получить нельзя. Но branch prediction является спекулятивной техникой, поэтому неправильное предсказание не влияет на корректность выполнения программы процессором; после записи правильных данных в BTB можно выполнять эффективное предсказание.

              tag     target
           +-------+----------+   Branch Target Buffer
+----+     +-------+----------+
| PC |---> +-------+----------+
+-+--+     +-------+----------+
  |        +-------+----------+
  |            |         | branch               predicted
  |            v         | target +-----------+  next PC  +-----+
  |          +----+      +------->|  branch   |---------->| IFU |
  +--------->| == |-------------->| predictor |           +-----+
             +----+    is branch  +-----------+

Реализовать branch predictor

Поскольку в BTB с ограниченным количеством записей информация о разных ветвлениях может вытеснять друг друга, при branch prediction целевой адрес branch-инструкции, соответствующей текущему PC, доступен не всегда. Это влияет на точность предсказания, поэтому в branchsim необходимо добавить BTB, чтобы откалибровать точность предсказания.

Конкретно, сначала реализуйте простой BTB в RTL без ограничений на организацию: можно выбрать direct-mapped, fully associative или set-associative по необходимости. При необходимости можно добавить дополнительные поля в BTB. После реализации оцените его площадь, выберите подходящее количество записей BTB исходя из оставшейся площади, затем измените branchsim под это число записей и заново оцените точность алгоритма branch prediction.

После повторной оценки всесторонне учтите все факторы и решите, как реализовать branch predictor. После реализации сравните точность предсказания RTL с точностью, вычисленной branchsim.

Выше описано предсказание branch-инструкций. Jump-инструкции также требуют спекулятивного выполнения. Все jump-инструкции безусловны, но могут иметь разные результаты перехода, поэтому их предсказание в основном означает предсказание целевого адреса. Jump-инструкции делятся на прямые переходы jal и косвенные jalr. Для конкретной инструкции jal целевой адрес фиксирован, поэтому если сохранить его в BTB и соответствующая запись не будет вытеснена, при следующем выполнении этой jal можно со 100% точностью выбирать инструкцию по правильному target. Для jalr целевой адрес определяется значением исходного регистра во время выполнения и плохо предсказывается только статическими алгоритмами; здесь нужны соответствующие динамические алгоритмы. Для простоты пока можно использовать для jalr стратегию «always not taken».

Оценить прирост производительности при правильной спекуляции jump-инструкций

На основе счётчиков производительности оцените идеальный прирост производительности при правильной спекуляции для инструкций jal и jalr соответственно.

Если вы хотите предсказывать targets jal, можно позволить jal использовать тот же BTB, что и branch-инструкции, либо выделить для jal отдельный BTB. Первый вариант экономит площадь, но записи разных инструкций могут вытеснять друг друга и снижать точность; второй — наоборот. Решение можно принять на основе оценки branchsim.

Реализовать предсказание цели перехода для jal

Согласно описанной выше схеме реализуйте предсказание целевого адреса для инструкций jal.

Реализовать предсказание цели перехода для инструкции ret

В общем случае целевой адрес jalr трудно предсказать правильно, однако ret, являющийся особым видом jalr, предсказывать сравнительно легко. Если вам интересно и осталось достаточно площади, изучите материалы по «Return Address Stack» и реализуйте в процессоре предсказание целевого адреса для ret.

Оптимизировать конвейер

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

Ещё раз переосмыслите оптимизацию производительности процессора

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

Что ещё важнее, у вас должно появиться смутное чувство бессилия: конвейер — вершина того, чему учат учебники по организации компьютеров, и неужели это вся производительность, которую он даёт? На самом деле иллюзия «вершины» возникает потому, что учебники сильно ослабляют проблему подачи инструкций и данных, заставляя ошибочно считать вычислительную эффективность всем содержанием проектирования процессора, а out-of-order multi-issue — конечной целью процессорного дизайна.

В действительности этот опыт как раз отражает знаменитую «стену памяти» в компьютерных системах: производительность памяти серьёзно ограничивает реализацию производительности CPU. Теоретически улучшение многотактного процессора до конвейерного должно давать ускорение, близкое к 5 разам, но в системе с современной памятью итоговая производительность тесно связана и с производительностью памяти. Закон Амдала фактически заранее предсказал это бессилие: если доступ к памяти не успевает за процессором, сколько бы ни ускорялась вычислительная часть CPU, это бесполезно.

Поэтому нужно избавиться от иллюзии «если я изучил конвейер, у меня уже есть навыки архитектурного проектирования», понять значение счётчиков производительности, закона Амдала, симуляторов и т. д. для архитектурного проектирования, научиться делать разумные компромиссы между площадью, частотой и IPC и даже находить решения, хорошо выглядящие по всем параметрам. Именно это требуется от квалифицированного архитектора.

Эти навыки нельзя получить, просто переводя архитектурные диаграммы из книг в RTL-код. Если вы только копируете код из каких-то книг — забудьте об этом. Напротив, мы специально организовали лекционный материал в текущем порядке, чтобы вы как можно раньше избавились от этой иллюзии, столкнулись с реальностью memory wall в SoC и затем шаг за шагом научились научно искать разумные способы оптимизации процессора.

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

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

Обработка fence.i

Наконец, выполнение инструкции fence.i в конвейере также требует дополнительной обработки. Вспомните семантику fence.i: она гарантирует, что операции выборки инструкций после неё увидят данные, изменённые store-инструкциями до неё. При реализации icache мы уже специальным образом обрабатывали icache, чтобы последующие выборки не получали устаревшие инструкции из кэша.

В конвейерном процессоре устаревшие инструкции могут уже находиться внутри конвейера. Рассмотрим пример: предположим, fence.i вступает в силу на стадии EX, но более молодые I3 и I4 уже были выбраны и находятся в конвейере; они могут быть устаревшими. Если продолжить их выполнение, результат перехода автомата состояний CPU может перестать соответствовать автомату состояний ISA, что приведёт к ошибкам.

                 T1   T2   T3   T4   T5   T6   T7
               +----+----+----+----+----+
I1: add        | IF | ID | EX | LS | WB |
               +----+----+----+----+----+
                    +----+----+----+----+----+
I2: fence.i         | IF | ID | EX | LS | WB |
                    +----+----+----+----+----+
                         +----+----+
I3: ??? may be stale     | IF | ID |
                         +----+----+
                              +----+
I4: ??? may be stale          | IF |
                              +----+
                                   +----+----+----+----+----+
I5: sub                            | IF | ID | EX | LS | WB |
                                   +----+----+----+----+----+

Спроектировать контрпример

Согласно анализу выше спроектируйте тест, связанный с fence.i, который корректно выполняется на предыдущем многотактном процессоре, но завершается ошибкой на конвейерном процессоре.

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

Корректно реализовать fence.i в конвейере

При выполнении fence.i очищайте конвейер, затем снова запустите приведённый выше тест. Если реализация корректна, тест завершится успешно.

SA