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

Обновите ysyxSoC

Команда SoC предоставила 32-битный SoC для tape-out, а 2024/07/26 в 13:00:00 мы также перевели ysyxSoC на 32 бита, чтобы помочь всем проводить локальное тестирование перед подключением к SoC для tape-out. Если вы получили код ysyxSoC до указанного выше времени, выполните следующие действия:

1. Выполните следующую команду, чтобы получить новый 32-битный ysyxSoC:

   cd ysyxSoC
   git pull origin master # Возможно, вам потребуется разрешить некоторые конфликты кода
   

2. Измените ширину данных AXI верхнего уровня NPC на 32 бита и удалите связанный код преобразования ширины данных.
3. Повторно запустите симуляции, используя 32-битное окружение ysyxSoC.

После подключения к ysyxSoC разработанный вами NPC теперь может корректно взаимодействовать с различными устройствами, что означает, что с функциональной точки зрения он уже готов участвовать в tape-out. Следуя принципу системного проектирования «сначала завершить, потом доводить до совершенства», теперь мы можем обсудить оптимизацию производительности.

Хотя мы называем это оптимизацией производительности, на самом деле это лишь конечная цель. В сложной системе нам предстоит столкнуться со множеством выборов, например: какие части стоит оптимизировать? Какие методы оптимизации следует использовать? Какой выигрыш ожидается? Какова стоимость этих методов? Если мы вложим много усилий и получим лишь 0,01% прироста производительности, это определённо не то, чего мы хотим. Поэтому вместо того, чтобы вслепую писать код, нам нужен научный подход, который поможет ответить на приведённые выше вопросы:

1. Оценить текущую производительность
2. Найти уязвимые места производительности
3. Применить подходящие методы оптимизации
4. Оценить производительность после оптимизации и сравнить полученный прирост с ожидаемым

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

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

В нашем понимании «высокая производительность» по сути означает «быстро работает». Поэтому непосредственным показателем производительности является время выполнения программы. Следовательно, оценить производительность системы — значит оценить время выполнения программ на этой системе.

Выбор benchmark-программ

Какие же программы следует использовать для оценки? Существует множество программ, и оценивать их все нереалистично, поэтому необходимо выбрать несколько репрезентативных программ. «Репрезентативность» означает, что прирост производительности от методов оптимизации на этих программах должен соответствовать тому, что наблюдается в реальных сценариях применения.

Здесь мы упоминаем «сценарии применения», а это означает, что тенденции прироста производительности могут различаться в разных сценариях. Следовательно, для разных сценариев применения требуются разные репрезентативные программы, что и приводит к появлению различных benchmark-наборов. Например, Linpack представляет сценарий суперкомпьютерных вычислений, MLPerf — обучение моделей машинного обучения, CloudSuite — облачные вычисления, а Embench — встраиваемые системы. Для сценариев вычислений общего назначения самым известным benchmark является SPEC CPU, который оценивает общую вычислительную производительность CPU. SPEC (Standard Performance Evaluation Corporation) — организация, определяющая и поддерживающая benchmark-наборы для оценки компьютерных систем; ею опубликованы различные benchmark-наборы для разных сценариев. Помимо SPEC CPU существуют benchmark-наборы для графики, рабочих станций, высокопроизводительных вычислений, систем хранения, энергопотребления, виртуализации и т. д.

Обычно benchmark состоит из нескольких подтестов. Например, целочисленный тест SPEC CPU 2006 включает следующие подтесты:

Подтест	Описание
400.perlbench	Обнаружение спама с помощью Perl
401.bzip2	Алгоритм сжатия bzip
403.gcc	Компилятор gcc
429.mcf	Комбинаторная оптимизация расписания транспорта на отдельных остановках крупной системы общественного транспорта
445.gobmk	Игра Go, задача поиска ИИ
456.hmmer	Поиск последовательностей генов с использованием распознавания генов на основе скрытых марковских моделей
458.sjeng	Шахматы, задача поиска ИИ
462.libquantum	Моделирование квантовых вычислений для факторизации простых чисел
464.h264ref	Кодирование видео H.264 из исходных файлов формата YUV
471.omnetpp	Крупномасштабное моделирование Ethernet с протоколом CSMA/CD
473.astar	Алгоритм поиска пути A*
483.xalancbmk	Преобразование XML в формат HTML

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

Разумеется, benchmark-наборы должны развиваться вместе со временем, чтобы представлять программы новой эпохи. По состоянию на 2024 год SPEC CPU прошёл через шесть версий: 1989, 1992, 1995, 2000, 2006 и, наконец, последнюю версию 2017 года. SPEC CPU 2017 добавил новые программы, представляющие новые сценарии применения, такие как биомедицинская визуализация, 3D-рендеринг и анимация, а также программы ИИ для игры Go, использующие поиск по дереву Монте-Карло (весьма вероятно, под влиянием AlphaGo 2016 года).

CoreMark и Dhrystone — плохие benchmark-наборы

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

Основная проблема синтетических программ как benchmark-наборов заключается в их слабой репрезентативности: какие сценарии применения представляют CoreMark и Dhrystone? По сравнению с различными реальными приложениями в SPEC CPU 2006 фрагменты кода CoreMark едва дотягивают до уровня домашних заданий по C; Dhrystone ещё дальше от реальных приложений — его код очень прост (используются короткие строковые литералы), а современные компиляторы, вероятно, глубоко оптимизируют код внутри цикла (вспомните pattern_decode() в NEMU), из-за чего результаты оценки завышаются и не позволяют объективно отражать производительность системы. В этой статье подробно анализируются недостатки Dhrystone как benchmark.

Иронично, что многие производители CPU до сих пор используют результаты CoreMark или Dhrystone для демонстрации производительности своих продуктов, даже если эти продукты якобы предназначены для высокопроизводительных сценариев. Лауреат премии Тьюринга и один из пионеров компьютерной архитектуры Дэвид Паттерсон, комментируя Embench, заявил, что Dhrystone давно устарел и должен быть отправлен в отставку. Первая версия Dhrystone была выпущена ещё в 1984 году, и с 1988 года он не поддерживался и не обновлялся. По сравнению с 1980-ми годами область вычислительной техники сильно изменилась: появились новые приложения, технологии компиляторов стали зрелыми, а аппаратное обеспечение стало значительно мощнее. Использовать 40-летний benchmark для оценки современных компьютеров, безусловно, сомнительно.

Для учебного сценария «One Student One Chip» программы SPEC CPU немного слишком реалистичны: с одной стороны, они очень крупные и требуют нескольких часов даже при запуске на реальной x86-машине; с другой стороны, они требуют среды Linux, то есть сначала нам необходимо разработать CPU, способный корректно загрузить Linux, и только после этого можно запускать benchmark SPEC CPU.

Вместо этого нам нужен benchmark, подходящий для учебного сценария и удовлетворяющий следующим условиям:

• Не слишком большой по масштабу, чтобы время выполнения в симуляторах или RTL-средах моделирования не превышало 2 часов
• Может работать в bare-metal-среде без Linux
• Программа является репрезентативной, в отличие от синтетических CoreMark и Dhrystone

На самом деле microbench, встроенный в am-kernels, является хорошим выбором. С одной стороны, microbench предоставляет тестовые наборы разного размера: симуляторы могут использовать размер ref, а RTL-среды моделирования — размер train; с другой стороны, microbench является AM-программой, поэтому может работать без Linux; кроме того, microbench содержит 10 подтестов, охватывающих сортировку, битовые операции, интерпретаторы языков, матричные вычисления, генерацию простых чисел, алгоритм A*, максимальный поток в сети, сжатие данных, контрольную сумму MD5 и т. д. Поэтому в дальнейшем, если в лекциях говорится об оценке производительности без указания конкретного benchmark, по умолчанию будет подразумеваться microbench размера train.

Если сценарий применения процессора заранее ясен, например запуск игр NES, то можно непосредственно использовать игру NES как benchmark, считая игровой опыт критерием «работает хорошо». В отличие от microbench, игра NES никогда не завершает выполнение, поэтому вместо времени выполнения для количественной оценки можно использовать FPS.

Поиск узких мест производительности

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

Мы можем измерить время выполнения benchmark и тем самым получить показатель производительности системы. Но время выполнения — это всего одна величина, и непосредственно по ней трудно определить уязвимые места производительности, поэтому нам нужны более подробные данные.

На самом деле время выполнения программы можно разложить на следующие три множителя:

        time      inst     cycle     time
perf = ------- = ------ * ------- * -------
        prog      prog      inst     cycle

Цель оптимизации производительности — уменьшить время выполнения программы, то есть минимизировать каждый из этих множителей. Отсюда следуют три направления оптимизации.

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

1. Изменить программу, используя более оптимальные алгоритмы.
2. Использовать лучшие стратегии оптимизации компилятора. Например, в gcc помимо распространённых флагов оптимизации вроде -O3, -Ofast, можно также тонко настроить параметры компиляции для целевой программы. В gcc существует около 600 параметров компилятора, связанных с качеством кода, и правильный их выбор может значительно уменьшить динамическое число инструкций. Например, работая над одним проектом, yzh скомпилировал CoreMark только с -O3, и динамическое число инструкций за 10 запусков составляло около 3,12 млн; после включения некоторых целевых параметров компилятора оно снизилось примерно до 2,25 млн, что существенно улучшило производительность.
3. Проектировать и использовать более сложные наборы инструкций. Мы знаем, что наборы инструкций CISC содержат сложные инструкции, и если компилятор использует их, это может уменьшить динамическое число инструкций. Кроме того, в процессор можно добавлять специализированные пользовательские инструкции и использовать их в программе.

Второе направление оптимизации — уменьшить среднее число тактов на инструкцию (CPI). Иначе говоря, увеличить IPC (Instructions Per Cycle), то есть среднее число инструкций, выполняемых за один такт. Этот показатель отражает качество микроархитектуры процессора: мощный процессор выполняет больше инструкций за такт. Поэтому оптимизация микроархитектуры обычно направлена на увеличение IPC и ускорение выполнения программы. У микроархитектурной оптимизации есть различные направления, которые мы кратко обсудим далее.

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

1. Оптимизировать front-end-проектирование цифровой схемы, чтобы уменьшить логические задержки критического пути.
2. Оптимизировать back-end-проектирование цифровой схемы, чтобы уменьшить задержки межсоединений на критическом пути.

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

• Динамическое число инструкций можно напрямую подсчитать в среде моделирования.
• Имея динамическое число инструкций, можно вычислить IPC, подсчитав число тактов.
• Частоту схемы можно узнать из отчёта синтезатора.

Подсчитайте IPC

Попробуйте подсчитать IPC в среде моделирования.

На самом деле, когда мы реализовывали шину, мы уже просили вас оценить время выполнения программы по приведённой выше формуле производительности. Однако тогда мы вычисляли его как такты программы / частота, а приведённая выше формула производительности просто раскладывает такты программы на два множителя. Тем не менее это разложение всё равно даёт нам более подробную информацию, поскольку такты программы зависят и от программы, и от процессора, тогда как среднее число тактов на инструкцию зависит только от возможностей процессора.

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

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

       /--- frontend ---\    /-------- backend --------\
                                  +-----+ <--- 2. эффективность вычислений
                             +--> | FU  | --+
       +-----+     +-----+   |    +-----+   |    +-----+
       | IFU | --> | IDU | --+              +--> | WBU |
       +-----+     +-----+   |    +-----+   |    +-----+
          ^                  +--> | LSU | --+
          |                       +-----+
1. подача инструкций                  ^
                    3. подача данных --+

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

Чтобы повысить эффективность выполнения инструкций процессором, необходимо обеспечить следующее:

1. Front-end гарантирует подачу инструкций. Если front-end не может получать достаточное количество инструкций, вычислительные возможности процессора нельзя использовать полностью. Поскольку выполнение каждой инструкции требует её выборки, способность front-end подавать инструкции влияет на эффективность выполнения всех инструкций.
2. Back-end гарантирует эффективность вычислений и подачу данных.
   • Для большинства вычислительных инструкций эффективность выполнения зависит от эффективности соответствующего функционального блока. Например, эффективность выполнения инструкций умножения и деления также зависит от эффективности умножителя/делителя. Аналогично это относится к вычислениям с плавающей точкой и блокам FPU.
   • Для инструкций доступа к памяти эффективность выполнения зависит от эффективности LSU. В частности, для инструкций load процессор должен дождаться данных из памяти, прежде чем записать их обратно в регистровый файл. Это означает, что эффективность выполнения load зависит от способности LSU и памяти предоставлять данные. Инструкции store отличаются тем, что им не требуется запись в регистровый файл, поэтому в принципе процессору не нужно ждать, пока данные полностью запишутся в память. В высокопроизводительных процессорах часто проектируют store buffer: процессор считает инструкцию store завершённой после записи информации о ней в store buffer, а фактическую запись в память store buffer выполняет позднее. Однако это повышает сложность конструкции процессора, например необходимо гарантировать, что инструкции load проверяют, не находятся ли самые новые данные в store buffer.

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

События производительности и счётчики производительности

Чтобы количественно оценить подачу инструкций, эффективность вычислений и подачу данных, необходимо подробнее понять факторы, которые на них влияют. В качестве примера рассмотрим подачу инструкций. Как определить, насколько сильна способность процессора подавать инструкции? Самый прямой показатель — удалось ли IFU получить инструкцию. Поэтому можно считать «IFU получил инструкцию» событием и подсчитывать частоту его возникновения. Если это событие возникает часто, способность подавать инструкции высока; в противном случае — низка.

Такие события называются событиями производительности. С их помощью можно преобразовать некоторые более абстрактные показатели модели производительности в конкретные события внутри схемы. Аналогично можно подсчитывать частоту события «LSU загрузил данные», чтобы измерять способность подачи данных; и частоту события «EXU завершил вычисление», чтобы измерять эффективность вычислений.

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

Обнаружить возникновение события производительности в схеме несложно: можно использовать handshake-сигналы шинного механизма. Например, когда при выборке инструкции IFU происходит handshake канала R, это означает, что IFU получил данные, возвращённые по AXI-шине, и тем самым завершил операцию выборки инструкции. Поэтому при handshake канала R можно увеличивать соответствующий счётчик производительности на 1.

Добавьте счётчики производительности

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

• IFU получает инструкцию
• LSU загружает данные
• EXU завершает вычисление
• Декодируются различные типы инструкций, например вычислительные инструкции, инструкции доступа к памяти, CSR-инструкции и т. д.

Счётчики производительности по своей сути реализуются аппаратной схемой. По мере увеличения количества счётчиков они будут занимать всё большую площадь и потенциально влиять на критические пути схемы. Поэтому мы не требуем включать счётчики производительности в tape-out. Их можно использовать только в среде моделирования: можно реализовать счётчики на RTL и вывести их значения в конце симуляции с помощью, например, $display(), а затем настроить процесс синтеза так, чтобы они не инстанцировались; либо можно передать сигналы обнаружения событий производительности в среду моделирования через DPI-C и реализовать сами счётчики уже там. Таким образом, вы сможете свободно добавлять счётчики производительности, не беспокоясь о влиянии на площадь и частоту схемы.

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

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

Добавьте счётчики производительности (2)

Добавьте в NPC больше счётчиков производительности и попробуйте проанализировать следующие вопросы:

• Какой процент инструкций приходится на каждую категорию? Сколько тактов в среднем требуется для выполнения каждой категории?
• По каким причинам IFU не может получать инструкции? Какова вероятность того, что каждая из этих причин приводит к невозможности получить инструкцию?
• Какова средняя задержка доступа LSU к памяти?

Трассировка счётчиков производительности

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

Закон Амдала

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

Закон Амдала был сформулирован компьютерным учёным Джином Амдалом в 1967 году и гласит:

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

Предположим, что доля времени, в течение которой определённая часть системы действительно используется, равна p, а ускорение этой части после оптимизации равно s. Тогда ускорение всей системы равно f(s) = 1 / (1 - p + p / s), что и является формулой закона Амдала.

Например, процесс выполнения программы разделён на две независимые части A и B, где A занимает 80%, а B — 20% времени.

• Если ускорить B в 5 раз, общее ускорение программы будет 1 / (0.8 + 0.2 / 5) = 1.1905;
• Если ускорить B в 5000 раз, общее ускорение программы будет 1 / (0.8 + 0.2 / 5000) = 1.2499;
• Если ускорить A в 2 раза, общее ускорение программы будет 1 / (0.2 + 0.8 / 2) = 1.6667.

<------- A --------><-B->
++++++++++++++++++++ooooo   Исходная программа

++++++++++++++++++++o       Ускорить B в 5 раз

++++++++++++++++++++        Ускорить B в 5000 раз, в результате время выполнения оптимизированной B становится очень коротким

++++++++++ooooo             Ускорить A в 2 раза

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

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

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

Профессиональная этика в компьютерной архитектуре

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

Обсуждать оптимизацию без учёта workload — безответственно.

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

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

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

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

Метод отладки сверху вниз

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

На самом деле отладка функциональных ошибок и ошибок производительности тоже во многом похожи. При отладке функциональной ошибки сначала мы видим сообщение об ошибке или падении программы, но по одному такому сообщению трудно локализовать проблему; поэтому мы используем различные уровни trace-инструментов, чтобы понять поведение программы и определить конкретные проявления ошибки; затем с помощью GDB или waveform выполняем подробный анализ на уровне переменных/сигналов.

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

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

Калибровка задержки доступа к памяти

После подключения NPC к ysyxSoC такие модули, как контроллер SDRAM, обеспечивают более реалистичный процесс доступа к памяти. Представьте, что мы собрали статистику счётчиков производительности до подключения к ysyxSoC; из-за различий в задержке доступа к памяти результаты сильно отличались бы от результатов после подключения. Разная статистика направила бы нас к разным вариантам оптимизации, но если наша цель — получить ожидаемую производительность, эти различные направления могут не дать ожидаемого результата. Поэтому чем ближе поведение среды моделирования к поведению реального чипа, тем меньше ошибка в результатах оценки и тем реалистичнее будет прирост производительности от оптимизаций, выполненных на основе счётчиков производительности.

На самом деле прежнее окружение ysyxSoC предполагало, что процессор и различные периферийные устройства работают на одной частоте: один такт в симуляции Verilator соответствовал одному такту и процессора, и периферии. Однако в реальности это не так. Из-за электрических характеристик периферийные устройства обычно работают на более низких частотах, например микросхемы SDRAM обычно работают примерно на 100 МГц. Более высокая частота может вызвать нарушения timing и привести к некорректной работе SDRAM. С другой стороны, процессоры, реализованные на более современных техпроцессах, обычно способны работать на более высоких частотах. Например, в одной из версий многоциклового NPC yzh частота достигает примерно 1,2 ГГц на техпроцессе nangate45, который по умолчанию предоставляется проектом yosys-sta. При такой конфигурации за один такт контроллера SDRAM NPC должен выполнить 12 тактов, однако Verilator не учитывает различие частот и моделирует их так, словно они одинаковы. В результате симуляция оказывается гораздо более оптимистичной, чем реальный чип, и некоторые оптимизации могут не дать ожидаемого эффекта на настоящем кристалле.

Обновите yosys-sta

2024/04/09 в 08:30:00 мы обновили проект yosys-sta, добавив инструмент оптимизации netlist, разработанный командой iEDA. Он значительно оптимизирует синтезированный netlist, генерируемый yosys, благодаря чему результаты оценки timing становятся ближе к результатам коммерческих инструментов. Если вы получили код yosys-sta до указанного времени, удалите существующий проект yosys-sta и клонируйте его заново.

Чтобы получать более точные результаты моделирования и использовать их для более эффективной оптимизации, необходимо откалибровать задержку доступа к памяти. Существует два способа. Первый — использовать симулятор, поддерживающий несколько тактовых доменов, например VCS или ICARUS Verilog. В отличие от Verilator, реализующего cycle-accurate-модель, эти симуляторы используют модель очереди событий: каждое вычисление в Verilog рассматривается как событие, а задержки событий сохраняются, что позволяет корректно поддерживать порядок вычислений между модулями в разных тактовых доменах, работающих на разных частотах. Однако поддержка модели очереди событий обычно делает такие симуляторы медленнее Verilator.

Второй способ калибровки заключается в изменении RTL-кода и добавлении модуля задержки в ysyxSoC. Этот модуль задерживает запросы на определённое количество тактов, имитируя работу устройства на низкой частоте и гарантируя, что число тактов ожидания NPC близко к тому, которое он ожидал бы при работе на высокой частоте. Этот метод не слишком сложен и может моделироваться более быстрым Verilator, поэтому мы выбрали именно его. Кроме того, этот метод также применим к FPGA.

Естественно, для реализации модуля задержки достаточно после получения ответа от устройства не сразу отвечать вышестоящему модулю, а задержать ответ. Однако вычислить число тактов ожидания непросто. Рассмотрим приведённый ранее пример yzh: если запрос занимает 6 тактов в контроллере SDRAM, NPC должен ждать в сумме 6 * 12 = 72 такта; если контроллер SDRAM выполняет refresh и запрос занимает 10 тактов, NPC должен ждать 10 * 12 = 120 тактов; если запрос отправлен во flash и занимает 150 тактов SPI-master, NPC должен ждать 150 * 12 = 1800 тактов. Как видно, число тактов, которое должен ждать модуль задержки, связано с временем обработки запроса устройством и не является фиксированной константой, поэтому его необходимо вычислять динамически внутри модуля. Предположим, что запрос занимает k тактов устройства, а отношение частоты процессора к частоте устройства равно r (r >= 1). Тогда модуль задержки должен вычислить число тактов ожидания процессора c = k * r. Для такого динамического вычисления необходимо решить две задачи:

1. Как реализовать умножение с небольшими затратами?
2. Если r является дробным числом, как реализовать умножение на дробное число? Например, частота, указанная проектом yosys-sta, составляет 550 МГц, поэтому r = 550 / 100 = 5.5, но если считать 5,5 как 5, запрос, занимающий 6 тактов на стороне устройства, внесёт ошибку в 3 такта на стороне процессора. Для высокочастотного CPU такая ошибка слишком велика, а накопление ошибок заметно повлияет на значения счётчиков производительности и, следовательно, на решения по оптимизации.

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

Сначала рассмотрим умножение, когда r — целое число. Поскольку сам модуль задержки также должен ждать ответа устройства, время ожидания уже равно числу тактов k, которое запрос проводит в устройстве. Поэтому достаточно, пока мы ждём, каждый такт увеличивать счётчик на r. При заданных частотах процессора и устройства r является константой, поэтому его можно напрямую жёстко задать в RTL. После получения ответа устройства модуль задержки переходит в состояние ожидания, каждый такт уменьшая счётчик на 1, и когда он достигнет 0, возвращает ответ на запрос вышестоящему модулю.

Теперь рассмотрим случай, когда r — дробное число. Поскольку дробную часть неудобно обрабатывать, а простое усечение создаёт большую ошибку, можно включить дробную часть в целую для накопления. Для этого введём масштабный коэффициент s и во время накопления каждый такт будем добавлять в счётчик r * s. Тогда к завершению накопления значение счётчика станет y = r * s * k, а перед переходом в состояние ожидания счётчик обновится до y / s. Поскольку s — константа, результат r * s также можно жёстко задать в RTL. Конечно, r * s всё ещё может быть нецелым, поэтому мы усекаем его до целого. Теоретически это всё равно вносит ошибку, но можно доказать, что она значительно меньше прежней. Однако y вычисляется динамически и не может быть жёстко задан в RTL. Следовательно, для произвольного s вычисление y / s требует деления. Вы наверняка быстро поймёте, что можно выбрать специальные значения s, которые упростят это вычисление! Таким способом можно уменьшить ошибку до 1/s от исходной: в новой схеме ошибка, накопленная в фазе суммирования, должна достичь s, прежде чем итоговая ошибка увеличится на 1.

В текущем ysyxSoC SDRAM использует интерфейс APB, поэтому нам необходимо имплементировать APB-модуль задержки. В ysyxSoC уже имеется каркас APB-модуля задержки, встроенный перед APB Xbar и перехватывающий все запросы APB, включая обращения к SDRAM. Однако конкретная реализация задержки в этом каркасе отсутствует, поэтому по умолчанию никакой задержки нет. Для калибровки задержки доступа к SDRAM в ysyxSoC вам также необходимо реализовать функциональность APB-модуля задержки.

Откалибруйте задержку доступа к памяти

Как описано выше, реализуйте APB-модуль задержки в ysyxSoC для калибровки задержки доступа к памяти в среде моделирования. Если вы используете Verilog, необходимо реализовать соответствующий код в ysyxSoC/perip/amba/apb_delayer.v; если вы используете Chisel, необходимо реализовать соответствующий код в модуле APBDelayerChisel в ysyxSoC/src/amba/APBDelayer.scala и изменить Module(new apb_delayer) в ysyxSoC/src/amba/APBDelayer.scala, чтобы инстанцировать модуль APBDelayerChisel.

Чтобы реализовать APB-модуль задержки, необходимо определить начало и конец APB-транзакции на основе определения протокола APB. Предположим, APB-транзакция начинается в момент t0, устройство возвращает APB-ответ в момент t1, а APB-модуль задержки возвращает APB-ответ вышестоящему модулю в момент t1'. Тогда должно выполняться уравнение (t1 - t0) * r = t1' - t0.

Что касается значения r, предполагается, что устройство работает в окружении 100 МГц. r можно вычислить по отчёту синтеза yosys-sta. Что касается s, теоретически чем оно больше, тем лучше, но достаточно выбрать такое s, которого хватает на практике. Насколько именно его хватает — вам предстоит определить наблюдением; по сути, это тоже форма профилирования.

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

Найдите максимальную частоту синтеза

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

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

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

1. Задержка чтения регистрового файла. Обычно операция чтения регистрового файла должна завершаться за один такт и не может быть разделена на несколько тактов, поэтому частота процессора не может превышать максимальную рабочую частоту регистрового файла.
2. Задержка сумматора с разрядностью, равной длине слова процессора. Обычно операция сложения в EXU должна завершаться за один такт; если сложение занимает несколько тактов, это значительно снижает эффективность выполнения всех инструкций, содержащих операции сложения, включая сложение, вычитание, инструкции доступа к памяти (нужно вычислять адрес), инструкции перехода (нужно вычислять целевой адрес), и даже вычисление PC + 4, тем самым заметно снижая IPC программы. Поэтому частота процессора не может превышать максимальную рабочую частоту этого сумматора.
3. Задержка чтения/записи SRAM. Поскольку SRAM является полностью кастомным блоком, её задержку чтения/записи нельзя оптимизировать логическим проектированием, поэтому при использовании SRAM частота процессора не может превышать максимальную рабочую частоту SRAM.

Можно написать несколько небольших простых модулей и отдельно оценить максимальную рабочую частоту этих компонентов. Чтобы исключить влияние I/O-портов, необходимо добавить flip-flop на входах и выходах этих компонентов. Максимальная рабочая частота SRAM как полностью кастомного блока обычно указана в соответствующем руководстве, а поскольку сейчас мы SRAM не используем, её оценку можно временно пропустить.

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

Программируемый шаг счётчика

Упомянутое выше r является константой для RTL-проектирования, но для сложных процессоров с динамической регулировкой частоты это уже не так. В таких процессорах r необходимо сделать программируемым и хранить в регистре устройства; после того как программное обеспечение изменит частоту, новое r записывается в регистр устройства. Поэтому этот регистр также необходимо отобразить в адресное пространство процессора, чтобы процессор мог обращаться к нему через SoC. Разумеется, s тоже можно сделать программируемым.

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

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

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

Оцените производительность NPC

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

После калибровки задержки доступа к памяти выполнение microbench размера train в ysyxSoC, вероятно, займёт несколько часов, но мы получим показатели производительности, очень близкие к среде tape-out. В дальнейшем после добавления каждой функции вы можете повторно оценивать и записывать показатели производительности, чтобы анализировать прирост, который приносит каждая новая функция.

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

Далее мы требуем записывать данные производительности после каждой оценки. Если вы подаёте заявку на tape-out, эту запись необходимо будет предоставить. Если записанные данные не соответствуют фактическому процессу разработки, вы можете потерять право участвовать в tape-out. Этим требованием мы надеемся заставить вас замечать и понимать изменения производительности NPC и развивать базовые навыки, необходимые для проектирования архитектуры процессора, а не просто переводить архитектурные схемы из справочных книг в RTL-код.

Конкретно, данные можно записывать следующим образом:

Commit	Описание	Такты симуляции	Инструкции	IPC	Частота синтеза	Площадь синтеза	Счётчик производительности 1	Счётчик производительности 2	...
0123456789abcdef	Пример, реализован кэш	200000	10000	0.05	750MHz	16000	3527	8573	...

При этом:

• Мы требуем добавить правило make perf в Makefile каталога проекта NPC, чтобы при выполнении

  git checkout коммит из таблицы
  make perf
  

  воспроизводились данные производительности из соответствующей строки таблицы. Если воспроизведённые результаты значительно отличаются от записанных в таблице и это невозможно разумно объяснить, это может рассматриваться как нарушение академической честности.
  • Можно считать, что вы выполняете научно-исследовательский проект и несёте ответственность за экспериментальные данные на протяжении всей работы: экспериментальные данные должны быть воспроизводимыми и выдерживать публичную проверку.
• В своих учебных записях можно создать новый worksheet с названием NPC Performance Evaluation Results для записи этих данных.
• Performance Counter 1 и Performance Counter 2 можно заменить реальными названиями соответствующих счётчиков.
• При необходимости можно записывать дополнительные счётчики производительности.
• В столбце описания также можно записывать свой анализ данных производительности.
• Мы рекомендуем записывать как можно больше результатов оценки, чтобы количественно анализировать изменения производительности NPC.

Стоит ли оптимизировать тактовую частоту CPU?

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

Калибровка задержки доступа к памяти на FPGA

Современные FPGA обычно включают контроллеры памяти DDR. Однако из-за принципов реализации FPGA частота CPU в части PL заметно отличается от частоты в ASIC-процессе, а иногда частота CPU даже ниже частоты контроллера памяти. Например, контроллер памяти может работать на 200 МГц, тогда как CPU на FPGA может работать лишь на сотнях или даже десятках мегагерц; в реальных чипах CPU обычно работает выше 1 ГГц (например, целевая тактовая частота Xiangshan третьего поколения составляет 3 ГГц). Очевидно, что данные производительности, полученные в такой среде оценки, сильно искажены для тестирования CPU, нацеленного на tape-out. Решение описанной выше проблемы инверсии частот памяти посредством калибровки задержки доступа — задача, которую производители процессоров должны решить перед использованием FPGA для оценки производительности CPU.

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

• Из-за различий в аналоговых компонентах PHY-модуль контроллера памяти на FPGA отличается от PHY контроллера памяти ASIC, что может влиять на задержку доступа к памяти.
• Из-за принципов реализации FPGA и ограниченного диапазона настройки PLL на FPGA рабочая частота DDR-контроллера ниже частоты DDR-контроллера ASIC, однако сами DDR-чипы нельзя пропорционально снизить по частоте, из-за чего задержка доступа оказывается неточной.
• После снижения частоты DDR-контроллера его частота refresh и другие параметры также отличаются от параметров ASIC-контроллера памяти.

Поэтому эффективное решение проблемы инверсии частот памяти на FPGA остаётся серьёзной отраслевой задачей. Например, команда Xiangshan создала отдельную инженерную группу для решения этой проблемы.

Необходимость калибровки задержки памяти FPGA зависит от сценария и цели использования FPGA:

• Образование: FPGA используется только как среда функционального тестирования. В этом случае FPGA служит для ускорения моделирования, и теоретически отношение частот процессора и контроллера памяти не влияет на результаты функционального тестирования.
• Соревнования или исследовательские проекты: FPGA используется и как среда тестирования производительности, и как целевая платформа. В этом случае, поскольку tape-out не является целью, калибровать задержку доступа к памяти не нужно.
• Разработка коммерческого продукта: FPGA используется как среда тестирования производительности, но конечной целью также является tape-out. Тогда мы хотим, чтобы данные производительности с FPGA максимально соответствовали реальному чипу. В этом случае калибровка задержки доступа к памяти FPGA становится необходимой.

Хотя «One Student One Chip» во многом упрощён, мы всё же хотим, чтобы все получили общее представление о процессе разработки продукта в компании. При этом, учитывая множество инженерных сложностей калибровки реального DDR-контроллера, мы не требуем от всех использовать FPGA. В отличие от FPGA, калибровка задержки памяти в среде моделирования значительно проще, поэтому мы по-прежнему рекомендуем выполнять оценку и оптимизацию производительности именно в среде моделирования.

Повышение эффективности функционального тестирования

Использование среды моделирования ysyxSoC с откалиброванной задержкой памяти подходит для оценки производительности, но вы также заметите, что эффективность моделирования в этой среде значительно ниже, чем в прежней riscv32e-npc: судя по времени выполнения microbench размера train, эффективность riscv32e-npc в десятки или даже сотни раз выше, чем riscv32e-ysyxsoc. Это отражает компромисс: чтобы получить более точные данные производительности, необходимо моделировать больше деталей (например, контроллер SDRAM и сами SDRAM-чипы), а значит, моделирование одного такта занимает больше времени, и общая эффективность симуляции снижается. Соответственно, более быстрый riscv32e-npc даёт неточные данные производительности.

Значит ли это, что riscv32e-npc бесполезен? Нет. Его можно использовать как среду функционального тестирования. Если функциональная ошибка существует в riscv32e-npc, весьма вероятно, что она существует и в riscv32e-ysyxsoc, но очевидно, что отлаживать её в более эффективной среде riscv32e-npc разумнее. Таким образом, можно использовать сильные стороны обеих сред, компенсируя их недостатки и повышая общую эффективность разработки и тестирования.

Попробуйте изменить соответствующий процесс моделирования так, чтобы поддерживать симуляцию NPC и в riscv32e-npc, и в riscv32e-ysyxsoc. При этом riscv32e-npc продолжает использовать 0x8000_0000 как значение PC после reset.

Четыре метода оптимизации классической компьютерной архитектуры

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

1. Локальность — использование характера доступа к данным для улучшения подачи инструкций и данных. Представительная технология — кэширование.
2. Параллелизм — несколько экземпляров работают одновременно, повышая общую вычислительную способность системы. Параллелизм далее делится на:
   • Параллелизм уровня инструкций — одновременно выполняются несколько инструкций. Связанные технологии включают конвейеризацию, множественную выдачу, VLIW и out-of-order-выполнение.
   • Параллелизм уровня данных — одновременно обрабатываются несколько элементов данных. Связанные технологии включают SIMD, векторные инструкции/векторные машины.
   • Параллелизм уровня задач — одновременно выполняются несколько задач. Связанные технологии включают многопоточность, многоядерность, мультипроцессорные системы и multiprocessing; GPU относятся к SIMT — методу параллелизма, находящемуся между параллелизмом уровня данных и параллелизмом уровня задач.
3. Предсказание — когда правильный выбор неизвестен, один вариант сначала выполняется спекулятивно, а затем на последующих шагах проверяется, был ли выбор правильным. Если предсказание верно, уменьшается задержка ожидания и повышается производительность. Если предсказание неверно, требуются дополнительные механизмы восстановления. Представительные технологии — предсказание переходов(branch prediction) и prefetch кэша.
4. Ускорители — специализированные аппаратные блоки выполняют конкретные задачи, повышая эффективность их выполнения. Примеры:
   • AI-ускорители — ускоряют вычисления AI-workload, обычно через доступ по шине
   • Пользовательские расширенные инструкции — интегрируют ускоритель в CPU и обращаются к нему через новые пользовательские инструкции
   • Умножитель-делитель — его можно рассматривать как разновидность ускорителя, считая RVM расширением RVI, а специализированные аппаратные модули умножения/деления управляются соответствующими инструкциями для ускорения вычислений

Переосмыслите проектирование архитектуры процессора

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

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

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

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

На самом деле эти способности требуют целенаправленного развития. Мы видели немало студентов, которые способны перенести блок-схему конвейерного процессора из справочных материалов в RTL-код, но не умеют оценить, соответствует ли время выполнения программы ожиданиям, и не знают, как дальше оптимизировать систему или реализовывать новые требования; некоторые студенты проектируют out-of-order superscalar-процессор, производительность которого оказывается ниже, чем у пятистадийного конвейера из учебника. Это показывает, что способность проектировать архитектуру не эквивалентна способности писать RTL. Возможно, эти студенты поняли базовые идеи конвейеров и out-of-order superscalar-обработки, но им не хватает целостного взгляда: они сосредотачиваются только на повышении вычислительной эффективности back-end, почти не обращая внимания на подачу инструкций и данных, из-за чего пропускная способность памяти процессора оказывается намного ниже его вычислительной способности, и общая производительность становится плохой. Поэтому даже корректно работающий out-of-order superscalar-процессор не обязательно является хорошим процессором, и в определённом смысле такие студенты всё ещё не обладают навыками архитектурного проектирования процессоров.

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

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

Иерархия памяти и принцип локальности

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

Иерархия памяти

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

время доступа     /\        ёмкость    цена
                 /  \
    ~1ns        / рег\        ~1KB     $$$$$$
               +------+
    ~10ns     /  DRAM  \      ~10GB     $$$$
             +----------+
    ~10ms   /   диск     \    ~1TB       $$
           +--------------+
    ~10s  /    лента       \  >10TB       $
         +------------------+

• Регистры. Время доступа к регистрам очень мало и по сути соответствует тактовой частоте CPU. Современные коммерческие высокопроизводительные CPU работают примерно на 3 ГГц, поэтому время доступа к регистрам составляет менее 1 нс. Ёмкость регистров очень мала, обычно менее 1 КБ. Например, RV32E имеет 16 32-битных регистров, что в сумме составляет 512 бит. Кроме того, стоимость реализации регистров относительно высока, а использование большого количества регистров занимает значительную площадь кристалла.
• DRAM. Время доступа к DRAM составляет примерно 10 нс, а её ёмкость значительно больше, чем у регистров, поэтому она обычно используется как оперативная память. Её стоимость также намного ниже: модуль памяти объёмом 16 ГБ на одной из платформ электронной коммерции стоит 329 CNY, то есть примерно 20 CNY за ГБ.
• Механические жёсткие диски. Время доступа механических дисков ограничено их механическими компонентами, например необходимостью вращения пластин, поэтому обычно оно составляет около 10 мс. При этом механические диски обладают гораздо большей ёмкостью, обычно в несколько ТБ; их стоимость также ниже: жёсткий диск на 4 ТБ на одной из платформ электронной коммерции стоит 569 CNY, то есть примерно 0,139 CNY за ГБ.
• Твердотельные накопители (SSD). SSD также являются популярным сегодня носителем и используют ячейки NAND flash, работающие на основе электрических свойств, поэтому скорость доступа у них значительно выше, чем у механических дисков, а задержка чтения приближается к DRAM, однако задержка записи из-за особенностей flash-памяти всё ещё значительно выше, чем у DRAM. Их стоимость немного выше механических дисков. На одной из платформ электронной коммерции SSD объёмом 1 ТБ стоит 699 CNY, то есть примерно 0,683 CNY за ГБ.
• Магнитная лента. Магнитная лента обладает очень большой ёмкостью и очень низкой стоимостью, но время доступа у неё очень большое — примерно 10 секунд, поэтому сегодня она используется редко и в основном применяется для резервного копирования. На одной из платформ электронной коммерции ленточный накопитель на 30 ТБ стоит 1000 CNY, то есть примерно 0,033 CNY за ГБ.

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

Принцип локальности

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

• Временная локальность — после обращения к ячейке памяти к ней вскоре могут обратиться снова
• Пространственная локальность — после обращения к ячейке памяти вскоре могут обратиться к соседним ячейкам

Эти явления связаны со структурой и поведением программ:

• Программы обычно выполняются последовательно или в циклах: последовательное выполнение проявляет пространственную локальность, а циклы — временную локальность
• При написании программы связанные переменные часто располагаются рядом в исходном коде или объединяются в структуры, а компиляторы также выделяют для них соседние области памяти, тем самым создавая пространственную локальность
• Во время выполнения программы число обращений к переменным обычно не меньше числа самих переменных (иначе существовали бы неиспользуемые переменные), поэтому некоторые переменные обязательно используются многократно, что создаёт временную локальность
• Для массивов программы обычно используют циклы для последовательного обхода элементов, тем самым создавая пространственную локальность

Наблюдение локальности программы

Локальность программы связана с обращениями к памяти, поэтому естественно наблюдать её с помощью mtrace! Запустите несколько программ в NEMU и получите mtrace. После этого дополнительно обработайте вывод mtrace и попробуйте визуализировать результаты с помощью каких-либо средств построения графиков.

Локальность связанных списков

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

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

Именно в этом заключается ключ к организации различных типов памяти в иерархии: память организуется уровнями, где верхние уровни быстрее, но меньше по объёму, а нижние — больше, но медленнее; при обращении к данным сначала проверяется более быстрая память верхнего уровня; если данные найдены на текущем уровне (это называется hit), обращение выполняется непосредственно здесь; иначе (это называется miss) поиск продолжается на следующем нижнем уровне, который передаёт целевые данные и соседние с ними данные на верхний уровень. Здесь «передача целевых данных на верхний уровень» использует временную локальность и рассчитана на hit при повторном обращении к тем же данным; а «передача соседних данных на верхний уровень» использует пространственную локальность и рассчитана на hit при последующем обращении к соседним данным.

Например, при обращении к DRAM, если данных в ней нет, можно обратиться к механическому диску и переместить целевые данные вместе с соседними данными в DRAM. При повторном обращении эти данные уже можно получить из DRAM, то есть доступ будет выполняться непосредственно из неё. Такой подход позволяет приблизиться к памяти со скоростью доступа, близкой к DRAM, и ёмкостью, близкой к механическому диску! Что касается стоимости, используя пример цен выше, суммарная стоимость модуля памяти 16 ГБ и жёсткого диска 4 ТБ составляет менее 900 CNY, тогда как покупка 4 ТБ оперативной памяти стоила бы 329 * (4TB / 16GB) = 84224 CNY!

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

Простой кэш

Введение в кэш

Возвращаясь к упомянутому ранее узкому месту, чтобы оптимизировать подачу инструкций, нам фактически нужно повысить эффективность доступа к DRAM. Для этого достаточно в соответствии с принципами иерархии памяти добавить промежуточный уровень хранения между регистрами и DRAM. Это и есть идея кэша. То есть перед обращением к DRAM сначала обращаемся к кэшу; если происходит hit, данные получаем напрямую; если miss — сначала читаем данные из DRAM в кэш, а затем обращаемся к ним в кэше.

Упомянутый выше кэш относится к узкому определению и означает именно процессорный кэш (CPU cache). В более широком смысле понятие кэша выходит далеко за пределы аппаратного блока на пути доступа к памяти. Кэши повсеместно встречаются в компьютерных системах: контроллеры дисков также имеют кэш для хранения прочитанных данных; row buffer в SDRAM, который мы обсуждали ранее, по сути тоже является кэшем массива памяти SDRAM; операционные системы программно поддерживают кэш для устройств хранения вроде дисков, чтобы хранить недавно использованные данные. Такой кэш по сути представляет собой большой массив структур, размещённый в памяти, а операционная система отвечает за перенос данных между диском и памятью; кэш также критически важен в распределённых системах. Если нужных данных нет в локальном кэше, за ними приходится обращаться удалённо. Кэш веб-страниц браузера и кэш видеоконтента относятся к этой категории.

Возвращаясь к CPU cache: кто читает данные из DRAM в кэш? На самом деле тот, кто выполняет передачу между двумя уровнями памяти, зависит от того, кто имеет доступ к обоим уровням. В компьютере существуют лишь программные программы и аппаратные схемы, а сущность программ — это последовательность инструкций. Хотя инструкции могут обращаться к DRAM, модель программирования, определённая спецификацией набора инструкций, обычно не включает кэш. То есть функционально кэш невидим для программы, поэтому упомянутое чтение должна выполнять аппаратная схема (как мы увидим позже, по сути это конечный автомат). Для уровней DRAM и диска инструкции могут обращаться и к DRAM, и к диску как к устройству через MMIO, поэтому программное обеспечение может отвечать за чтение данных с диска в DRAM, как это делает операционная система. Разумеется, теоретически можно разработать специализированный аппаратный модуль для переноса данных между DRAM и диском, однако такой модуль обычно поддерживал бы лишь один тип диска и не обладал бы гибкостью драйвера операционной системы.

Кэш, видимый программному обеспечению

В некоторых процессорах кэш видим программам. Например, shared memory в модели программирования CUDA GPU организована на том же уровне, что и CPU cache, и служит промежуточным уровнем хранения между регистрами и DRAM; однако, в отличие от CPU cache, GPU предоставляет специальные инструкции доступа к памяти для shared memory, позволяя GPU-программам с помощью инструкций считывать данные из памяти в конкретные места shared memory.

Для удобства данные, считываемые из DRAM, будем называть блоками данных, а блоки данных, хранящиеся в кэше, — cache blocks (в некоторых учебниках их также называют cache lines). Естественно, проектирование кэша должно решить следующие вопросы:

• Какого размера должен быть блок данных?
• Как определить, является ли запрос доступа к памяти cache hit?
• Поскольку ёмкость кэша обычно меньше DRAM, как поддерживать отображение между cache blocks и блоками данных DRAM? Что происходит, когда кэш заполнен?
• CPU может выполнять операции записи и обновлять данные в блоках; как в таком случае поддерживать кэш?

Простой кэш инструкций

Сначала рассмотрим кэш инструкций (icache). Поскольку процесс выборки инструкций IFU не требует записи в память, icache является read-only, и пока можно не рассматривать, как обрабатывать записи CPU в блоки данных. Что касается размера блока, сначала будем использовать длину одной инструкции — 4B. Возможно, это не лучший вариант, однако для icache блок меньше 4B точно плох, потому что выборка одной новой инструкции потребует нескольких обращений к памяти. Лучше ли блок больше 4B — оценим позже.

Чтобы определить, является ли запрос к памяти cache hit, естественно, помимо самого блока данных кэш должен хранить некоторые его атрибуты. Самый прямой способ — хранить уникальный идентификатор блока, но при этом хочется, чтобы способ его вычисления был достаточно простым. Поскольку блок данных приходит из памяти, можно пронумеровать память на основе размера блока. Тогда идентификатор блока данных, соответствующего адресу памяти addr, равен addr / 4; он называется tag блока. Поэтому достаточно вычислить tag адреса обращения и сравнить его с tag каждого cache block, чтобы определить, присутствует ли целевой блок в кэше.

Далее рассмотрим организацию cache blocks. Согласно иерархии памяти, ёмкость кэша не может быть такой же большой, как DRAM, но и вряд ли будет равна одному cache block. Поэтому при чтении нового блока в кэш необходимо решить, в какой cache block его помещать. Поскольку cache blocks несколько, их также можно пронумеровать. Самый простой способ организации — помещать новый блок в фиксированный cache block; это называется direct-mapped. Для этого необходимо чётко определить отображение между адресом памяти addr и номером cache block. Предположим, кэш может хранить k cache blocks. Простое отображение имеет вид номер cache block = (addr / 4) % k, то есть блок данных по адресу addr будет помещён в cache block с номером (addr / 4) % k.

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

Все cache blocks можно рассматривать как массив, где номер cache block является индексом массива (index), поэтому номер cache block также называется block index. Для direct-mapped cache с размером блока b байт и k cache blocks имеем tag = addr / b и index = (addr / b) % k. Для удобства вычислений b и k обычно выбирают степенями двойки: пусть b = 2^m и k = 2^n. Если addr имеет 32 бита, тогда tag = addr / 2^m = addr[31:m], а index = (addr / 2^m) % 2^n = addr[m+n-1:m]. Видно, что index фактически представляет собой младшие n бит tag. В direct-mapped cache блоки данных с разными index всегда отображаются в разные cache blocks, даже если их старшие биты tag (то есть addr[31:m+n]) совпадают. Поэтому при хранении tag достаточно сохранять только addr[31:m+n].

Адрес памяти можно разделить на три части: tag, index и offset. Часть tag служит уникальным идентификатором блока данных в кэше, index используется как индекс блока в кэше, а offset обозначает смещение внутри блока, то есть какую именно часть блока данных нужно получить.

 31    m+n m+n-1   m m-1    0
+---------+---------+--------+
|   tag   |  index  | offset |
+---------+---------+--------+

Наконец, после reset в кэше нет данных, и все cache blocks недействительны. Чтобы определять действительность блока, к каждому cache block необходимо добавить бит valid. Бит valid и tag вместе называются metadata cache block, то есть данными, используемыми для управления данными; в данном случае управляемыми данными является сам cache block.

Итак, рабочий процесс icache выглядит следующим образом:

1. IFU отправляет запрос выборки инструкции в icache.
2. Получив адрес запроса, icache использует часть index для выбора cache block, проверяет совпадение его tag с tag запрошенного адреса и проверяет valid блока. Если все условия выполняются, происходит hit, и процесс переходит к шагу 5.
3. Запрошенный блок данных считывается из DRAM через шину.
4. Блок данных помещается в соответствующий cache block, а metadata обновляется.
5. Полученная инструкция возвращается в IFU.

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

Реализуйте icache

На основе приведённого выше рабочего процесса реализуйте простой icache с размером блока 4B и общим количеством 16 cache blocks. Обычно массив хранения кэша (включая данные и metadata) реализуется с помощью SRAM, однако использование SRAM в ASIC-процессе требует выбора и инстанцирования, причём выбор SRAM может влиять на способ хранения данных и metadata. Поскольку это первое упражнение по кэшу, для простоты сначала реализуйте массив хранения на flip-flops, чтобы повысить гибкость реализации.

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

Адресные пространства, подходящие для кэширования

Не все адресные пространства подходят для кэширования; для кэширования подходят только адресные пространства типа memory. Кроме того, задержка доступа к SRAM составляет всего 1 такт, поэтому кэшировать её не нужно. Лучше использовать cache blocks для других адресных пространств.

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

Обычно LSU используется вместе с кэшем, называемым data cache (dcache). Прежде чем реализовывать dcache, можно оценить его прирост в идеальных условиях. Предположим, что dcache имеет бесконечную ёмкость, 100% hit rate и задержку 1 такт. На основе счётчиков производительности попробуйте оценить прирост от добавления такого dcache.

Если оценка верна, вы должны обнаружить, что на данном этапе добавлять dcache невыгодно. Мы продолжим обсуждать этот вопрос далее.

Формальная верификация

С помощью DiffTest вы должны легко убедиться, что после интеграции icache заданная программа всё ещё работает правильно. Но как гарантировать, что icache работает правильно для любой программы?

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

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

Основные принципы формальной верификации

Могут ли инструменты автоматически помочь нам находить тестовые случаи? Да, такие инструменты существуют! Solver — это математический инструмент, который ищет допустимое решение при заданных ограничениях; по сути, это похоже на решение системы уравнений или задачи линейного программирования. Например, Z3 — solver для задач Satisfiability Modulo Theories (SMT), способный определять выполнимость выражений, содержащих вещественные числа, целые числа, биты, символы, массивы, строки и т. д. На самом деле любую задачу, которую можно выразить как подмножество логики первого порядка, можно решать SMT-solver, поэтому такие solver применяются даже к сложным задачам вроде Sudoku. SMT-solver широко используются в автоматическом доказательстве теорем, анализе программ, верификации программ и тестировании ПО. Ниже приведён пример использования Z3 для решения системы уравнений на Python.

#!/usr/bin/python
from z3 import *

x = Real('x')  # Определить переменную
y = Real('y')
z = Real('z')
s = Solver()
s.add(3*x + 2*y - z == 1)    # Определите ограничения
s.add(2*x - 2*y - 4*z == -2)
s.add(-x + 0.5*y - z == 0)
print(s.check())  # Проверить, существует ли допустимое решение: sat
print(s.model())  # Вывод допустимого решения: [y = 14/25, x = 1/25, z = 6/25]

В области тестирования и верификации существует метод, называемый формальной верификацией. Один из технических подходов к нему — model checking. Соответствующий инструмент называется model checker. В основе model checking лежит solver. Конкретно model checker рассматривает конструкцию как набор ограничений, входы как переменные, а условие «не выполнено хотя бы одно условие верификации» — как цель поиска решения. Всё это выражается в логике первого порядка и преобразуется в язык, понятный solver, после чего solver пытается найти допустимое решение. Например, если конструкция содержит условия assert(cond1) и assert(cond2), solver будет искать такие входы, при которых выполняется !cond1 || !cond2. Если допустимое решение найдено, значит найден тест, нарушающий условие верификации, и этот контрпример можно использовать для отладки и улучшения конструкции; если допустимого решения нет, значит ни один вход не нарушает условие, и тем самым корректность конструкции доказана! Как видно, независимо от того, найдёт solver решение или нет, для разработчика это отличная новость.

Вообще говоря, состояние системы также зависит от времени. Например, состояние процессора может изменяться каждый такт. Если условие можно проверить на всех временных интервалах, метод называется unbounded model checking. Однако из-за высокой вычислительной стоимости unbounded model checking на практике чаще используется bounded model checking (BMC). BMC обычно требует параметр k, задающий проверку условия только на максимум k временных единиц вперёд. Этот параметр называется bound BMC.

Не доверяйте слепо отчётам UVM о 100% coverage

Если вы знакомы с UVM, то знаете, что одна из его целей — повышение coverage. Однако если вы считаете, что максимизация coverage является конечной целью тестирования и верификации, вы, вероятно, понимаете тестирование не полностью.

На самом деле конечная цель тестирования и верификации — доказать корректность конструкции или обнаружить все ошибки. Но опытные инженеры знают, что даже при 100% coverage в конструкции могут оставаться необнаруженные ошибки, и оценить их количество невозможно.

Причина, по которой компании широко используют coverage как цель, с одной стороны, заключается в том, что это удобный количественный и статистический показатель. Если строго описать «событие покрыто», это означает:

Существует тестовый случай, который успешно выполняется и во время выполнения вызывает это событие.

Здесь событием может быть выполнение конкретной строки кода (line coverage), переключение сигнала (toggle coverage), переход состояния конечного автомата (state machine coverage), выполнение пользовательского условия (functional coverage) и т. д. В то же время «coverage достигло 100%» означает:

Для каждого события существует тестовый случай, который успешно выполняется и во время выполнения вызывает это событие.

Обратите внимание: разные события можно покрывать разными тестами. Согласно этому определению, для подсчёта coverage достаточно добавить некоторые флаги в симуляцию. Большинство RTL-симуляторов (включая Verilator) даже имеют автоматические средства статистики coverage. Если хотите узнать, как считать coverage, просто RTFM.

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

Все тестовые случаи выполняются успешно.

По сравнению с этим «coverage достигло 100%» является только необходимым, но недостаточным условием «корректной конструкции» и на самом деле очень слабым. Простой контрпример: модуль имеет две функции, и каждая функция покрыта отдельным тестом, в результате functional coverage равен 100%; однако тест, требующий взаимодействия двух функций, приводит к ошибке.

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

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

Процесс формальной верификации на основе Chisel

Тестовый framework Chisel chiseltest интегрирует функциональность формальной верификации. Он может преобразовывать FIRRTL-код в язык, понятный BMC, и позволять BMC доказывать корректность заданного assert(). Если найден контрпример, генерируется waveform, воспроизводящая его, что очень удобно для отладки. С инструментами формальной верификации больше не нужно беспокоиться о неполном покрытии тестами, а иногда вообще не требуется писать тестовые случаи. Одним словом — замечательно!

Ниже приведён пример формальной верификации Chisel-модуля:

import chisel3._
import chisel3.util._
import chiseltest._
import chiseltest.formal._
import org.scalatest.flatspec.AnyFlatSpec

class Sub extends Module {
  val io = IO(new Bundle {
    val a = Input(UInt(4.W))
    val b = Input(UInt(4.W))
    val c = Output(UInt(4.W))
  })
  io.c := io.a + ~io.b + Mux(io.a === 2.U, 0.U, 1.U)

  val ref = io.a - io.b
  assert(io.c === ref)
}

class FormalTest extends AnyFlatSpec with ChiselScalatestTester with Formal {
  "Test" should "pass" in {
    verify(new Sub, Seq(BoundedCheck(1), BtormcEngineAnnotation))
  }
}

Больше не используйте Utest

С развитием версий Chisel Utest больше не поддерживается, поэтому мы также рекомендуем больше его не использовать. Если вы получили код chisel-playground до 2024/04/11 01:00:00, обратитесь к разделу object test в новой версии build.sc, чтобы изменить свой build.sc.

Модуль Sub в приведённом примере реализует вычитание в дополнительном коде методом «инвертировать и прибавить 1». Для проверки корректности реализации Sub код сравнивает результат «инвертировать и прибавить 1» с результатом оператора вычитания. Мы ожидаем, что assert() будет истинным для любых входов. Чтобы продемонстрировать эффективность формальной верификации, в реализацию Sub намеренно добавлена ошибка: когда io.a равно 2, операция «прибавить 1» не выполняется, из-за чего результат вычитания в дополнительном коде становится неверным.

При вызове формальной верификации chiseltest в приведённый код также передаётся параметр BoundedCheck(1) как bound BMC, то есть число тактов, которые необходимо доказать. Например, BoundedCheck(4) означает, что BMC должен попытаться доказать, что при любых входных сигналах модуль не нарушает assert() в течение 4 тактов после reset. Для комбинационных схем достаточно, чтобы BMC решал задачу в пределах 1 такта.

Кроме того, в код передаётся параметр BtormcEngineAnnotation, означающий использование model checker BtorMC. BtorMC основан на SMT-solver Boolector, отличающемся от Z3. Базовый принцип у него похож на Z3, но по результатам практического тестирования его скорость решения обычно в несколько раз выше. Перед запуском теста необходимо получить инструмент BtorMC. Для этого скачайте соответствующий пакет по этой ссылке. После распаковки добавьте path-to-oss-cad-suite/bin в переменную окружения PATH, чтобы можно было запускать BtorMC.

После завершения настройки запустите тест командой mill -i __.test; вывод будет следующим:

Assertion failed
    at SubTest.scala:16 assert(io.c === ref)
- should pass *** FAILED ***
  chiseltest.formal.FailedBoundedCheckException: [Sub] found an assertion violation 0 steps after reset!
  at chiseltest.formal.FailedBoundedCheckException$.apply(Formal.scala:26)
  at chiseltest.formal.backends.Maltese$.bmc(Maltese.scala:92)
  at chiseltest.formal.Formal$.executeOp(Formal.scala:81)
  at chiseltest.formal.Formal$.$anonfun$verify$2(Formal.scala:61)
  at chiseltest.formal.Formal$.$anonfun$verify$2$adapted(Formal.scala:61)
  at scala.collection.immutable.List.foreach(List.scala:333)
  at chiseltest.formal.Formal$.verify(Formal.scala:61)
  at chiseltest.formal.Formal.verify(Formal.scala:34)
  at chiseltest.formal.Formal.verify$(Formal.scala:32)
  at FormalTest.verify(SubTest.scala:19)
  ...

Эта информация показывает, что BMC нашёл тестовый случай, нарушающий assert(), на 0-м такте после reset. Кроме того, разработчик может использовать waveform-файл test_and_run/Test_should_pass/Sub.vcd для отладки. После исправления ошибки в модуле Sub повторный запуск теста больше не будет выводить сообщения об ошибке, что означает: BMC не может найти контрпример, а значит корректность кода доказана.

Процесс формальной верификации на основе Verilog

Процесс формальной верификации chiseltest преобразует FIRRTL-код в язык, понятный BMC. Verilog в этом процессе не участвует, поэтому описанный выше подход не поддерживает проекты, разработанные непосредственно на Verilog. Если вы используете Verilog, можно применить процесс формальной верификации на основе Yosys, где SymbiYosys является front-end-инструментом.

Ниже приведён пример формальной верификации Verilog-модуля:

// Sub.sv
`define FORMAL

module Sub(
  input [3:0] a,
  input [3:0] b,
  output [3:0] c
);

  assign c = a + ~b + (a == 4'd2 ? 1'b0 : 1'b1);

`ifdef FORMAL
  always @(*) begin
    c_assert: assert(c == a - b);
  end
`endif  // FORMAL

endmodule

Модуль Sub в приведённом примере реализует вычитание в дополнительном коде методом «инвертировать и прибавить 1». Для проверки корректности реализации код сравнивает результат «инвертировать и прибавить 1» с результатом оператора вычитания. Ожидается, что assert() будет истинным для любых входов. Чтобы продемонстрировать эффективность формальной верификации, в Sub намеренно добавлена ошибка: когда a равно 2, операция «прибавить 1» не выполняется, из-за чего результат вычитания в дополнительном коде становится неверным.

После создания файла Sub.sv также необходимо написать конфигурационный файл SymbiYosys *.sby, который обычно содержит следующие части:

• task: необязательно, используется для указания выполняемых задач
• options: обязательно, используется для отображения выражений вроде assert и cover из кода в модель
• engines: обязательно, используется для указания модели, которую необходимо решить
• script: обязательно, содержит Yosys-скрипт, необходимый для тестирования
• files: обязательно, используется для указания файлов тестирования

Ниже приведён пример конфигурационного файла Sub.sby:

[tasks]
basic bmc
basic: default

[options]
bmc:
mode bmc
depth 1

[engines]
smtbmc

[script]
read -formal Sub.sv
prep -top Sub

[files]
Sub.sv

Параметр depth в приведённой конфигурации является bound BMC и задаёт количество тактов, которые необходимо доказать. Например, depth 4 означает, что BMC попытается доказать, что тестируемый модуль не нарушает assert() при любых входных сигналах в течение 4 тактов после reset. Для комбинационных схем достаточно решения в пределах 1 такта.

Перед формальной верификацией необходимо скачать соответствующие инструменты по этой ссылке. После распаковки выполните команду path-to-oss-cad-suite/bin/sby -f Sub.sby; вывод будет следующим:

SBY 16:52:19 [Sub_basic] engine_0: ##   0:00:00  Checking assumptions in step 0..
SBY 16:52:19 [Sub_basic] engine_0: ##   0:00:00  Checking assertions in step 0..
SBY 16:52:19 [Sub_basic] engine_0: ##   0:00:00  BMC failed!
SBY 16:52:19 [Sub_basic] engine_0: ##   0:00:00  Assert failed in Sub: c_assert
SBY 16:52:19 [Sub_basic] engine_0: Status returned by engine: FAIL
SBY 16:52:19 [Sub_basic] summary: Elapsed clock time [H:MM:SS (secs)]: 0:00:00 (0)
SBY 16:52:19 [Sub_basic] summary: Elapsed process time [H:MM:SS (secs)]: 0:00:00 (0)
SBY 16:52:19 [Sub_basic] summary: engine_0 (smtbmc) returned FAIL
SBY 16:52:19 [Sub_basic] summary: counterexample trace: Sub_basic/engine_0/trace.vcd
SBY 16:52:19 [Sub_basic] summary:   failed assertion Sub.c_assert at Sub.sv:11.9-11.37 in step 0
SBY 16:52:19 [Sub_basic] DONE (FAIL, rc=2)
SBY 16:52:19 The following tasks failed: ['basic']

Эта информация показывает, что BMC нашёл тестовый случай, нарушающий assert(), на 0-м такте после reset. Кроме того, разработчики могут использовать waveform-файл Sub_basic/engine_0/trace.vcd для отладки. После исправления ошибки в модуле Sub повторный запуск команды выдаст информацию об успехе, то есть BMC не сможет найти контрпример, тем самым доказав корректность кода.

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

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

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

class CacheTest extends Module {
  val io = IO(new Bundle {
    val req = new ...
    val block = Input(Bool())
  })

  val memSize = 128  // byte
  val mem = Mem(memSize / 4, UInt(32.W))
  val dut = Module(new Cache)

  dut.io.req <> io.req

  val dutData = dut.io.rdata
  val refRData = mem(io.req.addr)
  when (dut.io.resp.valid) {
    assert(dutData === refData)
  }
}

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

• Заблокировать операции записи, установив write enable в 0
• При cache miss читать данные из mem. Поскольку тестовый объект не генерирует операции записи, DUT и REF могут использовать одну и ту же память
• Поскольку REF читает данные напрямую из mem без задержки, а DUT читает через кэш и тратит на это несколько тактов, timing assert() необходимо синхронизировать: после чтения данных REF нужно дождаться, пока DUT вернёт результат, и только после этого выполнять проверку. Это легко реализовать с помощью конечного автомата.
• Поскольку инструменты формальной верификации перебирают все входные условия для каждого такта, входные сигналы изменяются каждый такт. Возможно, потребуется использовать регистры для временного хранения некоторых результатов.
• Используя свойство «инструмент формальной верификации перебирает все входные условия для каждого такта», можно определить на верхнем уровне теста несколько сигналов block, чтобы проверять работу AXI-кода при случайных задержках, например dut.io.axi.ar.ready := arready_ok & ~block1, dut.io.axi.r.valid := rvalid_ok & ~block2

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

Хотя это необязательно, мы настоятельно рекомендуем попробовать этот современный метод тестирования и верификации и испытать удовольствие от «решения задач правильными инструментами». Что касается bound BMC (BoundedCheck() или depth), выберите подходящее значение, чтобы за проверяемое число тактов кэш успевал обработать 3–4 запроса; таким образом можно проверить корректную обработку произвольной последовательности запросов.

На первый взгляд формальная верификация имеет только преимущества, однако у неё есть смертельный недостаток — проблема взрыва пространства состояний. По мере увеличения размера конструкции и bound пространство, которое должен перебрать solver, также растёт. На самом деле языки логики первого порядка теоретически неразрешимы; даже разрешимые подмножества обычно являются NP-Hard по алгоритмической сложности. Это означает, что время работы solver, вероятно, экспоненциально растёт с размером конструкции. Поэтому формальную верификацию обычно применяют для unit testing.

Оптимизация кэша

Поскольку технология кэширования в первую очередь используется для повышения эффективности доступа к памяти, естественно оценивать производительность кэша с помощью показателей, связанных с доступом к памяти. Обычно для оценки кэша используется AMAT (Average Memory Access Time, среднее время доступа к памяти). Предположим, что hit rate кэша равен p:

AMAT = p * access_time + (1 - p) * (access_time + miss_penalty)
     = access_time + (1 - p) * miss_penalty

где access_time — время доступа к кэшу, то есть время от получения запроса памяти до определения hit, а miss_penalty — стоимость cache miss, которая в данном случае равна времени доступа к DRAM.

Эта формула подсказывает направления оптимизации производительности кэша: уменьшить access_time, увеличить hit rate p либо уменьшить miss_penalty. В текущем NPC возможности архитектурной оптимизации access time ограничены, поскольку на него сильнее влияют детали реализации, такие как количество тактов и критический путь. Поэтому далее мы сосредоточимся на оптимизации hit rate и miss penalty.

Соберите статистику AMAT

Добавьте в NPC подходящие счётчики производительности для измерения AMAT icache.

Оптимизация hit rate

Чтобы повысить hit rate, необходимо уменьшить miss rate. Для этого сначала нужно понять причины cache miss.

Модель 3C для cache miss

Компьютерный учёный Марк Хилл предложил модель 3C в своей докторской диссертации 1987 года. Она описывает три типа cache miss:

1. Compulsory miss — промах, который происходит даже в кэше бесконечной ёмкости, то есть miss при первом обращении к блоку данных
2. Capacity miss — miss, который невозможно устранить без увеличения ёмкости кэша, возникающий из-за того, что кэш не может вместить все необходимые данные
3. Conflict miss — miss, вызванный причинами, отличными от двух предыдущих, проявляющийся из-за взаимного вытеснения нескольких cache blocks

С помощью модели 3C можно предложить целевые решения для каждого типа miss и тем самым уменьшить соответствующую долю промахов.

Уменьшение compulsory miss

Чтобы уменьшить compulsory miss, в идеале блок данных следует загрузить в кэш ещё до первого обращения к нему. Однако описанный выше рабочий процесс кэша такой возможности не поддерживает, поэтому необходим новый механизм. Этот механизм называется prefetching. Тем не менее по определению compulsory miss относится только к первому обращению к блоку данных. В сценариях с большим количеством обращений к памяти доля compulsory miss обычно невелика. Поэтому здесь мы не будем подробно разбирать способы их уменьшения. Заинтересованные читатели могут самостоятельно найти материалы о prefetching.

Уменьшение capacity miss

Согласно определению, единственный способ уменьшить capacity miss — увеличить ёмкость кэша, чтобы лучше использовать временную локальность. Однако больший кэш не всегда лучше. С одной стороны, большая ёмкость означает большую площадь кристалла и, следовательно, более высокую стоимость производства; с другой стороны, более крупный массив хранения означает большую задержку доступа, что увеличивает access time кэша и снижает его производительность. Поэтому в реальных проектах простое неограниченное увеличение ёмкости не является разумным решением; необходимо принимать сбалансированное решение с учётом всех факторов.

Уменьшение conflict miss

Для уменьшения conflict miss необходимо подумать, как сократить взаимное вытеснение cache blocks. Как говорилось ранее, direct-mapped-организация означает, что каждый блок данных может быть помещён только в cache block с фиксированным index. Если несколько блоков имеют одинаковый index, более поздний блок вытеснит более ранний. Поэтому один из способов уменьшить количество замен — использовать новую организацию кэша, позволяющую помещать блок данных в несколько возможных cache blocks.

Крайний случай — каждый блок данных может храниться в любом cache block. Такая организация называется fully-associative. Сначала выбирается недействительный cache block; если все блоки valid, место назначения определяется алгоритмом замещения. Разные алгоритмы замещения по-разному влияют на hit rate. В общем случае алгоритм должен выбирать block, к которому с наименьшей вероятностью обратятся в будущем. Для заранее известной последовательности обращений к памяти можно разработать оптимальный алгоритм, минимизирующий conflict miss; но в реальности будущую последовательность обращений заранее знать нельзя, поэтому задача замещения превращается в «предсказание будущего по прошлому» — нужно по истории доступа предсказать cache block, который с наименьшей вероятностью потребуется в будущем. Распространённые алгоритмы:

• FIFO (First-In, First-Out): заменить cache block, загруженный раньше остальных
• LRU (Least Recently Used): заменить cache block, к которому реже всего обращались в последнее время
• Random: случайным образом выбрать cache block для замещения

При использовании подходящего алгоритма замещения fully-associative-организация с более высокой вероятностью вытесняет block, который не потребуется в ближайшем будущем, и тем самым максимально уменьшает conflict miss. Однако возможность поместить блок данных в любой cache block имеет две стоимости. Во-первых, адрес памяти больше не нужно делить на index, поэтому всё, кроме offset, становится частью tag. Следовательно, в массиве хранения требуется больше места для tag каждого cache block.

 31                m m-1    0
+-------------------+--------+
|        tag        | offset |
+-------------------+--------+

Во-вторых, для определения hit необходимо сравнить tag со всеми cache blocks, что требует большого количества компараторов и увеличивает площадь. Из-за этих затрат fully-associative обычно используется только там, где число cache blocks невелико.

Set-associative — компромисс между direct-mapped и fully-associative. Идея заключается в том, чтобы разделить все cache blocks на группы, сначала выбрать группу посредством direct mapping, а затем выбрать cache block внутри этой группы посредством fully-associative mapping. То есть каждый блок данных может храниться в любом cache block группы с номером tag % количество групп. Если каждая группа содержит w cache blocks, такую организацию называют w-way set-associative.

   +----------------------+-------------------------+
   |                      |                         |
+--+--+-------+--------+  |                         |
| tag | index | offset |  |                         |
+-----+---+---+--------+  |                         |
          |               |                         |
+---------+               |                         |
|                         |                         |
|  V   tag      data      |   V   tag      data     |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
+>+-+-------+----------+  |  +-+-------+----------+ |
  +++-----+-+----------+  |  +++-----+-+----------+ |
   |      |               |   |      |              |
 +-v-+  +-v--+            | +-v-+  +-v--+           |
 | & |<-+ == |<-----------+ | & |<-+ == |<----------+
 +-+-+  +----+              +-+-+  +----+
   |                          |
   +------------+--------------+
                |
                v
             hit way

В set-associative-организации адрес памяти также делится на tag, index и offset. Часть index используется как индекс набора, поэтому её ширина равна n = log2(общее число cache blocks/w).

 31    m+n m+n-1   m m-1    0
+---------+---------+--------+
|   tag   |  index  | offset |
+---------+---------+--------+

При определении hit достаточно сравнивать tag только со всеми cache blocks внутри выбранной группы. Пока w не слишком велико, площадь компараторов остаётся приемлемой.

На самом деле fully-associative и direct-mapped можно рассматривать как частные случаи set-associative: при w=1 получаем direct-mapped; при w=общее число cache blocks — fully-associative. Современные CPU обычно используют 8- или 16-way set-associative.

Выбор размера блока

Размер блока — особый параметр. Если cache block больше, то, с одной стороны, уменьшаются затраты на хранение tags, а с другой — в один block помещается больше соседних данных, что позволяет лучше использовать пространственную локальность программы и уменьшать conflict miss. Однако чтение большего количества соседних данных увеличивает miss penalty; кроме того, при фиксированной общей ёмкости кэша более крупные blocks означают меньшее количество cache blocks. Если пространственная локальность программы выражена слабо и ей выгоднее иметь больше мелких blocks, увеличение размера block может, наоборот, повысить число conflict miss.

// Программа с плохой пространственной локальностью
// 2 cache blocks размером 4
               1111       2222        cache
|--------------oooo-------oooo-----|  memory, `o` обозначает горячие данные программы

// 1 cache block размером 8
               11111111               cache
|--------------oooo-------oooo-----|  memory



// Программа с хорошей пространственной локальностью
// 2 cache blocks размером 4
               11112222               cache
|--------------oooooooo------------|  memory

// 1 cache block размером 8
               11111111               cache
|--------------oooooooo------------|  memory

Исследование пространства проектирования

Выше было упомянуто множество параметров кэша. Выбор подходящего набора параметров для достижения хорошей производительности при заданных ресурсах относится к задаче исследования пространства проектирования кэша — DSE (Design Space Exploration). Сейчас нас интересуют такие показатели, как IPC, тактовая частота и площадь. Частоту и площадь можно быстро оценить с помощью проекта yosys-sta, тогда как для получения IPC обычно необходимо полностью запускать программу в среде ysyxSoC с откалиброванной задержкой памяти.

Однако возможных комбинаций параметров слишком много. Если тратить несколько часов на оценку каждой комбинации, эффективность DSE будет крайне низкой. Как уже говорилось, точность данных и скорость моделирования находятся в компромиссе. Поэтому один из способов ускорить DSE — пожертвовать точностью оценки IPC и использовать вместо него показатель, который отражает тенденцию изменения IPC, но требует гораздо меньших вычислительных затрат.

При изменении параметров кэша непосредственное влияние оказывается на AMAT, поэтому можно предположить, что стоимость выполнения остальных частей CPU остаётся постоянной. Согласно определению AMAT, изменение рассмотренных параметров не влияет на access time кэша, поэтому его можно считать константой. Следовательно, нас в действительности интересует суммарное время, которое программа вынуждена ждать из-за cache miss; назовём его total miss time (TMT). TMT способен отражать тенденцию изменения IPC: чем меньше TMT, тем меньше тактов доступа к памяти приходится на инструкцию и тем выше IPC.

Когда ранее вы использовали счётчики производительности для измерения AMAT, вы, вероятно, также измеряли TMT, однако это требовало запуска программы в ysyxSoC. Чтобы измерять TMT с малыми затратами, рассмотрим его как число miss * miss penalty и подумаем, как дешёво оценивать число miss и miss penalty.

Для подсчёта количества miss имеются следующие наблюдения:

• Для заданной программы количество обращений к кэшу фиксировано. Получив трассировку инструкций программы (itrace) и подавая её в icache, можно смоделировать работу icache и подсчитать количество miss, не моделируя весь ysyxSoC и даже NPC.
• При выполнении программы NPC должен определять следующую инструкцию по результату текущей. Однако itrace уже содержит полный поток инструкций, поэтому для подсчёта TMT нужен только PC последовательности, а сами инструкции не нужны.
• Часть данных icache используется для возврата инструкций в IFU NPC, но поскольку для подсчёта TMT NPC не нужен, data-часть icache тоже не нужна; достаточно оставить только metadata. На самом деле для фиксированной последовательности адресов количество cache miss не зависит от содержимого памяти, и корректное число miss можно получить, поддерживая только metadata.

Следовательно, для подсчёта miss icache нет необходимости каждый раз полностью запускать программу. На самом деле нам нужен простой функциональный симулятор кэша, который будем называть cachesim. Cachesim получает последовательность PC потока инструкций (упрощённый itrace) и, поддерживая metadata, подсчитывает число miss для этой последовательности. Саму последовательность PC можно быстро получить с помощью NEMU.

Что касается miss penalty, поскольку cachesim не включает детали обращения к памяти из ysyxSoC, точно получить это значение принципиально невозможно. Однако, как обсуждалось выше, на miss penalty влияет только размер блока, поэтому можно вычислить средний miss penalty в ysyxSoC и затем использовать его как константу для оценки TMT.

Имплементируйте cachesim

На основе описания выше реализуйте простой симулятор кэша.

С помощью cachesim можно выполнять своего рода performance DiffTest для icache. Конкретно cachesim можно использовать как референс для тестирования производительности, и результаты счётчиков производительности, полученные при выполнении программы в NPC, должны полностью совпадать с количеством miss и другой статистикой, полученной cachesim при обработке соответствующей последовательности PC. Если есть расхождение, возможно, в RTL-реализации присутствует ошибка производительности, которую нельзя обнаружить функциональным DiffTest с NEMU или формальной верификацией. Например, даже если icache всегда выдаёт miss, программа всё равно может корректно работать на NPC. Конечно, возможно и то, что ошибка находится в самом cachesim, используемом как REF. Но независимо от причины наличие REF для сравнения всегда полезно.

Однако для получения согласованного itrace вам, возможно, потребуется изменить NEMU, чтобы он мог запускать image-файл riscv32e-ysyxsoc.

Сжатие trace

Если полученный itrace очень большой, можно сжать его следующими способами:

• Хранить itrace в бинарном формате вместо текстового
• Большую часть времени инструкции выполняются последовательно. Для непрерывной последовательности PC можно хранить только первый PC и число последовательно выполненных инструкций
• Дополнительно сжать полученный itrace с помощью инструментов bzip2, а затем получить читаемый file pointer в коде cachesim через popen("bzcat путь к сжатому файлу", "r"). Как использовать popen(), пожалуйста, RTFM

Используйте cachesim для исследования пространства проектирования

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

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

Попробуйте построить такой быстрый процесс оценки и исследовать несколько комбинаций параметров. Однако мы пока не оптимизировали miss penalty, поэтому TMT ещё нельзя оценивать достаточно разумно; кроме того, мы ещё не ввели ограничение площади. Эти факторы повлияют на финальное решение, поэтому на данном этапе окончательный выбор делать не нужно.

Оптимизация miss penalty

При cache miss необходимо обращаться к следующему уровню памяти, поэтому miss penalty равен времени доступа к следующему уровню. Существует множество методов уменьшения miss penalty; сначала рассмотрим один из них — burst access по шине. Если размер cache block совпадает с шириной данных шины, для чтения блока требуется только одна шинная транзакция, поэтому оптимизировать почти нечего. Но если block больше ширины шины, для чтения блока теоретически требуется несколько транзакций, что создаёт пространство для оптимизации.

Размер блока и miss penalty

В текущей конструкции кэша следующим уровнем памяти является SDRAM. Для дальнейшего анализа введём простую модель времени доступа к SDRAM: время доступа состоит из четырёх участков, поэтому одна независимая шинная транзакция имеет стоимость a+b+c+d. Предположим, ширина данных шины равна 4 байтам, а cache block — 16 байтам. Тогда при использовании четырёх независимых транзакций суммарная стоимость составит 4(a+b+c+d).

+------------------------ arvalid valid
|   +-------------------- handshake канала AR, получение запроса чтения
|   |       +------------ конечный автомат переходит в состояние READ и отправляет команду READ в SDRAM die
|   |       |     +------ SDRAM die возвращает данные чтения
|   |       |     |   +-- handshake канала R, возврат данных чтения
V a V   b   V  c  V d V
|---|-------|-----|---|

Добавьте поддержку большего размера блока

Измените размер блока в cachesim так, чтобы он был в четыре раза больше ширины данных шины, и оцените miss penalty при использовании независимых шинных транзакций.

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

Добавьте поддержку большего размера блока (2)

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

Burst-передачи по шине

Подобно SDRAM-чипам, AXI-шина также поддерживает «burst transfer» — несколько последовательных передач данных в рамках одной шинной транзакции, причём каждая отдельная передача называется beat. В протоколе AXI сигнал arburst канала AR указывает, является ли передача burst, а сигнал arlen указывает число beats.

Разумеется, одной поддержки со стороны протокола недостаточно: AXI master должен инициировать burst-транзакцию, а slave должен уметь её обработать. Как master, мы оставим инициирование burst-транзакций вам как экспериментальную задачу. С другой стороны, SDRAM-контроллер, предоставленный ysyxSoC, действительно поддерживает burst transfer, поэтому четыре упомянутые выше шинные передачи можно объединить в одну транзакцию и существенно уменьшить стоимость чтения полного блока. Во-первых, благодаря burst transfer канал AR выполняет handshake только один раз, что экономит 3a относительно прежней схемы. Во-вторых, SDRAM-контроллер может разделить одну burst-транзакцию на несколько команд READ, отправляемых SDRAM-чипам. Когда SDRAM возвращает данные, если остаются команды READ с последовательными адресами, конечный автомат контроллера напрямую возвращается в состояние READ и продолжает отправку команд, экономя 3b. Наконец, контроллер SDRAM может отвечать по каналу R одновременно с отправкой следующей READ-команды, тем самым скрывая задержку handshake канала R; относительно прежней схемы это экономит 3d.

  a     b      c    d
|---|-------|-----|---| <-------------------- 1-й beat
                  |-----|---| <-------------- 2-й beat
                        |-----|---| <-------- 3-й beat
                              |-----|---| <-- 4-й beat

Таким образом, стоимость burst transfer составляет a+b+4c+d, что экономит 3(a+b+d) по сравнению с прежней схемой. В общем случае, если размер cache block в n раз больше ширины шины, burst transfer способен сэкономить n(a+b+d) затрат. Хотя a, b и d на первый взгляд малы, помните, что это задержки с точки зрения SDRAM-контроллера. После калибровки задержки памяти для CPU экономия может составлять десятки или даже сотни тактов.

Реализация burst transfer

Как видно, чтобы получить преимущество burst transfer, кэш сначала должен использовать более крупные blocks. Однако, как обсуждалось выше, увеличение blocks может повысить conflict miss и привести даже к отрицательному эффекту — всё зависит от пространственной локальности программы. Чтобы определить лучший вариант, необходимо benchmark-тестирование. Для оценки TMT в cachesim нам также необходимо знать miss penalty при использовании burst transfer. Поэтому сначала нужно реализовать burst transfer в среде ysyxSoC. Это изменение затрагивает множество деталей, поэтому будем выполнять его поэтапно.

Ранее для удобства тестирования мы интегрировали SDRAM-контроллер с APB-интерфейсом. Однако APB не поддерживает burst transfer. Чтобы использовать burst, сначала необходимо заменить SDRAM-контроллер на версию с интерфейсом AXI.

Перейдите на 32-битный ysyxSoC

Команда SoC предоставила 32-битный SoC для tape-out. 2024/07/26 в 13:00:00 мы также обновили ysyxSoC до 32 бит, чтобы помочь всем проводить локальное тестирование перед подключением к tape-out SoC. Если вы получили код ysyxSoC до этого времени, обратитесь к инструкциям в начале этой страницы.

Интегрируйте SDRAM-контроллер с интерфейсом AXI

Измените переменную sdramUseAXI в объекте Config файла ysyxSoC/src/Top.scala на true. После изменения повторно сгенерируйте ysySoCFull.v и попробуйте запустить несколько тестовых программ.

Включите burst transfer для icache

Измените реализацию icache так, чтобы он использовал burst transfer для доступа к блокам данных в SDRAM.

После того как реализация станет корректной, запишите waveform burst transfer и сравните её с waveform без burst. Вы должны увидеть, что burst действительно повышает эффективность.

Калибровка задержки доступа к памяти SDRAM с AXI-интерфейсом

Хотя режим burst transfer уже работает, соответствующая задержка доступа к памяти пока не откалибрована, поэтому данные производительности неточны. Аналогично реализованному ранее APB delay module нам необходим AXI delay module для калибровки задержки.

Поскольку протокол AXI сложнее APB, при реализации AXI delay module нужно дополнительно учитывать следующее:

• Каналы чтения и записи AXI независимы, поэтому в принципе следует использовать отдельные счётчики задержки для read- и write-транзакций. Однако текущий NPC многоцикловый и не отправляет запросы чтения и записи одновременно, поэтому пока можно использовать общий счётчик для обоих типов. Но после реализации конвейера всё равно понадобятся два независимых счётчика.
• AXI имеет полноценные handshake-сигналы, а ожидание handshake также зависит от состояния устройства, поэтому этот период тоже должен входить в диапазон калибровки: момент активации valid следует считать началом транзакции.
• AXI поддерживает burst transfer, поэтому режим передачи отличается от APB.
  • Рассмотрим read-транзакцию: burst может включать несколько приёмов данных, каждый из которых необходимо калибровать отдельно. Предположим, burst read AXI начинается в момент t0, устройство возвращает данные в моменты t1 и t2, а AXI delay module возвращает данные наверх в моменты t1' и t2'. Тогда должны выполняться уравнения (t1 - t0) * r = t1' - t0 и (t2 - t0) * r = t2' - t0.
  • Burst write включает несколько передач данных. Поскольку устройству требуется минимум один такт, чтобы принять данные, что для CPU уже соответствует r тактам, моменты передачи данных тоже необходимо калибровать. Однако dcache пока не реализован и LSU не инициирует burst write, поэтому калибровку burst write можно временно пропустить. Но single write всё равно необходимо калибровать.

Реализуйте AXI delay module

На основе описанного выше реализуйте AXI delay module в ysyxSoC. Если вы используете Verilog, соответствующий код необходимо реализовать в ysyxSoC/perip/amba/axi4_delayer.v; если Chisel — в модуле AXI4DelayerChisel файла ysyxSoC/src/amba/AXI4Delayer.scala, а Module(new axi4_delayer) в ysyxSoC/src/amba/AXI4Delayer.scala следует изменить так, чтобы инстанцировался AXI4DelayerChisel.

Для упрощения реализации пока можно предположить, что число beats в burst не превышает 8. После реализации попробуйте разные значения r и проверьте по waveform выполнение приведённых уравнений.

Оцените производительность метода burst transfer

После калибровки задержки памяти для burst transfer запустите microbench размера train и сравните результаты с предыдущими записями.

Быстрая оценка miss penalty

Согласно предыдущему обсуждению, текущий miss penalty icache зависит только от размера блока и режима передачи по шине и не зависит от остальных параметров кэша. Поэтому можно заранее измерить miss penalty для разных комбинаций размера блока и режима шины и напрямую подставлять этот miss penalty в формулу TMT, оценивая ожидаемый эффект разных конфигураций. Однако из анализа выше очевидно, что burst transfer всегда лучше независимых передач. Поэтому на практике достаточно заранее оценить miss penalty для различных размеров блока при использовании burst transfer.

Есть два способа предварительной оценки miss penalty:

1. Моделирование. На основе работы конечного автомата SDRAM-контроллера вывести формулу времени доступа к SDRAM. Затем подставить размер блока и вычислить соответствующий miss penalty. Этот метод относительно прямолинеен, но проблема заключается в точности модели. Например, row buffer и refresh SDRAM также влияют на время доступа, однако количественно оценить вклад этих факторов в одно обращение к SDRAM трудно.
2. Статистический анализ. С помощью подходящих счётчиков производительности измерить TMT обращений к SDRAM при icache miss и затем вычислить средний miss penalty. Как статистический метод, он способен учитывать факторы, которые трудно смоделировать, например row buffer и refresh SDRAM, посредством выборки и усреднения. Однако row buffer по сути тоже является кэшем, и его производительность зависит от локальности программы, поэтому тестовая программа должна быть репрезентативной: непосредственный запуск microbench размера train обеспечивает лучшую репрезентативность; хотя это занимает больше времени, запустить его нужно только один раз, чтобы вычислить средний miss penalty; поведение размера test не полностью совпадает с train, но всё же обладает некоторой репрезентативностью и позволяет быстро вычислить средний miss penalty; hello-программа, напротив, слабо репрезентативна, поэтому оценка среднего miss penalty по ней может содержать большую ошибку.

В реальных проектах из-за сложности системы моделирование по формуле используется редко. Поэтому мы также рекомендуем статистический метод предварительной оценки miss penalty.

Быстро оцените miss penalty

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

Размещение программы в памяти

Расположение программы в памяти также может значительно влиять на производительность кэша. Рассмотрим icache. Когда размер блока icache превышает 4 байта, некоторые горячие циклы программы могут оказаться не выровнены по границам cache blocks, из-за чего инструкции цикла займут дополнительные blocks. Например, пусть горячий цикл расположен в диапазоне [0x1c, 0x34), а размер блока icache равен 16 байтам. Тогда для хранения всех инструкций этого цикла требуется три cache blocks.

         [0x1c, 0x34)           + 0x4   =   [0x20, 0x38)
+------+------+------+------+      +------+------+------+------+
|      |      |      | 0x1c |      | 0x20 | 0x24 | 0x28 | 0x2c |
+------+------+------+------+      +------+------+------+------+
| 0x20 | 0x24 | 0x28 | 0x2c |      | 0x30 | 0x34 |      |      |
+------+------+------+------+      +------+------+------+------+
| 0x30 |      |      |      |
+------+------+------+------+

Однако если добавить несколько пустых байтов перед кодом программы, можно изменить положение горячего цикла так, чтобы его инструкции занимали меньше cache blocks. В приведённом примере достаточно добавить 4 байта пустого содержимого перед кодом, чтобы сдвинуть цикл в диапазон [0x20, 0x38). Тогда его инструкции занимают только 2 cache blocks, а освободившийся block можно использовать для других инструкций, повышая общую производительность программы.

Оптимизируйте размещение программы в памяти

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

В приведённом примере ёмкость кэша очень мала, поэтому экономия одного block составляет значительную долю всего кэша. Однако современные процессоры имеют относительно большие кэши, поэтому экономия одного cache block может почти не повлиять на производительность. Тем не менее мы хотим подчеркнуть, что оптимизация программы — важное направление использования принципа локальности. Некоторые программы после такой оптимизации могут ускоряться в несколько раз.

В компаниях для ключевых приложений целевых сценариев инженерные команды обычно используют различные методы повышения производительности. Если компания сама проектирует процессоры, она не только улучшает аппаратную часть, но и настраивает компилятор под параметры своего процессора. По сравнению с executable-файлами, собранными публичными версиями компиляторов (например, gcc из open-source-сообщества), файлы, собранные кастомизированным компилятором, могут работать быстрее на целевом процессоре. В частности, SPEC CPU определяет два показателя, base и peak, причём peak разрешает компилировать разные подтесты с разными параметрами оптимизации, благодаря чему весь benchmark может работать на целевой платформе лучше, чем при base. Если вы хотите получить более высокий результат peak, без оптимизации на программном уровне не обойтись.

Исследование пространства проектирования (2)

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

Ограничение площади

Ваш NPC должен синтезироваться на техпроцессе nangate45, который по умолчанию предоставляется проектом yosys-sta, при общей площади не более 25000 (в единицах площади, сообщаемых инструментом синтеза). Это также ограничение площади для tape-out этапа B. Поскольку последующие задачи потребуют реализации конвейера, на данном этапе мы рекомендуем, чтобы общая площадь синтеза NPC не превышала 23000.

Эта площадь не особенно велика. С одной стороны, такое ограничение помогает подчеркнуть вклад других параметров в DSE; иначе можно было бы просто постоянно увеличивать ёмкость кэша и получать хорошую производительность, а влияние других параметров было бы трудно увидеть. С другой стороны, команда проекта ожидает, что многие студенты будут участвовать в tape-out этапа B, и меньшая площадь помогает снизить стоимость tape-out.

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

Стоимость производства можно приблизительно, хотя и не очень строго, оценить следующим образом. Предположим, foundry предоставляет tape-out на nangate45, где каждый блок размером 2mm X 3mm стоит 500 000 RMB. Тогда стоимость квадратного микрометра равна 500000 / (2 * 3 * 1000000) = 0.0834 RMB. Межсоединения между standard cells также занимают площадь, а для предотвращения чрезмерной плотности между ячейками оставляют дополнительное пространство. Поэтому итоговая площадь чипа обычно больше площади синтеза. По опыту площадь синтеза составляет примерно 70% конечной площади. Согласно этой оценке, дизайн с площадью синтеза 25000 будет стоить примерно 25000 / 0.7 * 0.0834 = 2978 RMB.

Главное, что следует понять из этой оценки: добавление функций в CPU не бесплатно. Это сильно отличается от проектирования под FPGA: в некоторых соревнованиях участники стараются преобразовать как можно больше ресурсов FPGA в производительность CPU, не неся при этом экономических затрат.

Но настоящий tape-out устроен иначе. Цель этапа B можно рассматривать как разработку дешёвого embedded-процессора (rv32e является базовым набором инструкций для embedded-сценариев). Представьте, что вы архитектор производителя embedded CPU. Необходимо улучшить производительность при ограниченном бюджете площади. Если площадь превышает ожидания, стоимость чипа растёт и его конкурентоспособность снижается. В этих условиях нужно оценивать экономическую эффективность каждой функции: если определённая функция повышает производительность на 10%, стоит ли платить за неё дополнительные 500 RMB?

Исследуйте пространство проектирования icache

На основе описанного выше исследуйте design space icache и выберите проектное решение, обеспечивающее хорошую производительность при заданных ограничениях. После выбора реализуйте его на RTL и оцените производительность в ysyxSoC.

Некоторые идеи по оптимизации площади

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

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

Для большинства людей выполнить приведённое ограничение площади с первой быстрой реализацией маловероятно, но это возможно. Эталонная конструкция yzh после добавления icache имеет площадь 22730 при частоте 1081 МГц, а Total time при выполнении microbench равен 4,49 с. Мы ввели это ограничение, с одной стороны, чтобы научить всех оптимизировать собственные конструкции: новичку нужна возможность начать такую работу, и через постоянные эксперименты вы постепенно сформируете понимание связи каждой строки RTL с её стоимостью по площади.

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

Не придирайтесь к параметрам синтеза

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

Оцените экономическую эффективность dcache

В предыдущем разделе вы оценили прирост производительности dcache в идеальных условиях. Теперь продолжите и оцените его cost-effectiveness. Предположим, площадь dcache равна площади icache. Сколько такой dcache будет стоить в RMB?

Хотя dcache вы ещё не проектировали, ему необходимо поддерживать операции записи, поэтому его конструкция должна быть сложнее icache и, следовательно, при одинаковой ёмкости занимать большую площадь. Поэтому оценка cost-effectiveness dcache при этих допущениях очень оптимистична. Если учесть реальный прирост производительности и фактическую площадь dcache, его экономическая эффективность будет ещё ниже.

Можно рассмотреть и другое направление: если площадь, предназначенная для dcache, использовать для увеличения ёмкости icache, какой прирост производительности это даст?

Настоящее проектирование компьютерной архитектуры

Хотя приведённая задача DSE для icache значительно упрощена по сравнению с исследованием пространства проектирования настоящих процессоров, для большинства студентов это всё равно первый опыт реального архитектурного проектирования процессора. Более того, вероятно, впервые большинство студентов проходит полный цикл проектирования модуля: от анализа требований, структурного проектирования и логического проектирования до функциональной верификации, верификации производительности, оптимизации производительности и, наконец, оценки площади и timing analysis на уровне схемы. Логическое проектирование среди этих этапов — это то, что обычно называют написанием RTL.

Эта задача ещё раз показывает, что проектирование компьютерной архитектуры не эквивалентно RTL coding. Работа архитектора заключается в том, чтобы найти в design space набор параметров с хорошей производительностью, удовлетворяющий ограничениям. Однако пространство проектирования обычно очень велико, а тщательная оценка одной комбинации параметров может занимать много времени. Поэтому возможность быстро оценивать производительность разных наборов параметров — критически важная задача архитектурного проектирования.

Именно поэтому симуляторы являются важнейшим инструментом проектирования компьютерной архитектуры. С симулятором не нужно моделировать поведение на уровне схемы (можно запускать cachesim вместо verilator), можно моделировать только необходимые модули (не моделировать data кэша, а только metadata) и не требуется выполнение, управляемое процессором (не запускать полную программу, а лишь воспроизводить соответствующий itrace). Эти различия делают симуляторы на порядки эффективнее RTL-моделирования, позволяют быстро оценивать ожидаемую производительность разных параметров и быстро отбрасывать явно неподходящие варианты.

По опыту команды Xiangshan выполнение программы в verilator занимает одну неделю, тогда как та же программа в full-system simulator gem5 выполняется всего за 2 часа. Это означает, что за время, необходимое для оценки одного набора параметров в RTL-среде, на симуляторе можно исследовать влияние 84 различных комбинаций параметров.

В архитектурных исследованиях симуляторы также являются распространённой платформой. Конференция ISCA проводила несколько соревнований на основе симулятора ChampSim, включая соревнование алгоритмов замещения кэша и соревнование алгоритмов prefetch данных. Исследователи оценивают различные алгоритмы в симуляторе, быстро изменяют общую реализацию и тонко настраивают параметры. Хотя пригодный алгоритм в конечном счёте всё равно требует RTL-реализации и верификации, исследовать все варианты сразу на RTL крайне неэффективно.

Поэтому только когда вы действительно поймёте, что проектирование компьютерной архитектуры != RTL coding, можно сказать, что вы по-настоящему начали путь в область проектирования компьютерной архитектуры.

Когерентность кэша

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

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

// smc.c
int main() {
  asm volatile("li a0, 0;"
               "li a1, UART_TX;"     // change UART_TX to the correct address
               "li t1, 0x41;"        // 0x41 = 'A'
               "la a2, again;"
               "li t2, 0x00008067;"  // 0x00008067 = ret
               "again:"
               "sb t1, (a1);"
               "sw t2, (a2);"
               "j again;"
              );
  return 0;
}

Программа сначала инициализирует несколько регистров, затем по метке again выводит символ A в последовательный порт, после чего переписывает инструкцию по адресу again на ret и наконец снова переходит к again для повторного выполнения. Согласно семантике программы она должна вывести один символ A, а затем вернуться из main() через записанную инструкцию ret. Код, который изменяет сам себя во время выполнения, называется self-modifying code.

Self-modifying code в истории развития компьютеров

Раньше, когда адресное пространство памяти было крайне ограничено, self-modifying code часто использовался для повышения эффективности использования памяти и позволял программам реализовывать больше функций при малом объёме памяти. Например, игровая приставка FC Family Computer 1980-х годов имела адресное пространство всего 64 КБ, из которых 32 КБ занимал ROM на картридже. Некоторые картриджи также имели 8 КБ RAM, но если RAM на картридже отсутствовала, программа могла использовать только 2 КБ RAM, встроенных в CPU. Чтобы создавать замечательные игры с такими ограниченными ресурсами, разработчики применяли множество хитроумных приёмов, включая self-modifying code.

С развитием памяти её ёмкость перестала быть настолько ограниченной, а self-modifying code трудно читать и поддерживать, поэтому сегодня в современных программах он встречается редко.

Воспроизведите проблему когерентности кэша

Скомпилируйте приведённую программу для AM и запустите её на NPC. Какие проблемы вы обнаружили? Попробуйте проанализировать их и проверить свои предположения по waveform.

Если вы не нашли проблему, попробуйте увеличить ёмкость icache.

Прямой способ решить проблему — гарантировать, что все копии в системе всегда согласованы. Например, при каждом выполнении store немедленно проверять наличие других копий и, если они есть, обновлять или инвалидировать их. Тогда последующая операция, независимо от места обращения, либо напрямую прочитает новые данные из обновлённой копии, либо получит miss после invalidation и прочитает новые данные со следующего уровня. Набор инструкций x86 использует такое решение. Однако оно явно увеличивает сложность CPU. Особенно в высокопроизводительных процессорах во время store другие компоненты одновременно обращаются к различным кэшам системы. Гарантировать, что никакой компонент не прочитает устаревшие данные до завершения обновления или invalidation всех копий, очень сложно.

Другое решение более мягкое: разрешить копиям временно быть несогласованными, но перед тем как программа снова обратится к соответствующему блоку данных, необходимо выполнить специальную инструкцию, которая заставит аппаратную часть обработать устаревшие копии. Тогда программа всё равно будет получать правильные данные и результат останется согласованным с её семантикой. Набор инструкций RISC-V использует именно этот подход. В RISC-V есть инструкция fence.i, семантика которой гарантирует, что все последующие выборки инструкций будут видеть данные, изменённые store-инструкциями, выполненными до неё. Здесь fence.i действует как барьер и не позволяет последующей выборке инструкций пересечь его и прочитать старые данные до применения store. Кроме того, спецификация RISC-V утверждает:

RISC-V does not guarantee that stores to instruction memory will be made
visible to instruction fetches on a RISC-V hart until that hart executes
a FENCE.I instruction.

Иными словами, RISC-V допускает, что копия в icache в некоторые моменты может не совпадать с памятью, что соответствует обсуждению выше. Дополнительную информацию о fence.i — RTFM.

RISC-V определяет только семантику fence.i на уровне ISA, однако на уровне микроархитектуры существует несколько способов реализации этой функциональности:

Схема	При выполнении store	При выполнении fence.i	При обращении к icache
(1)	Обновить соответствующий block в icache	nop	Hit
(2)	Инвалидировать соответствующий block в icache	nop	Miss, обратиться к памяти
(3)	-	Очистить весь icache	Miss, обратиться к памяти

На самом деле схемы (1) и (2) являются вариантом подхода «всегда поддерживать все копии системы согласованными», о котором говорилось выше, и представляют частный случай подхода «разрешать копиям временно быть несогласованными»: поскольку копии уже приводятся в согласованное состояние при выполнении store, fence.i можно реализовать как nop. В схеме (3) при выполнении store копии в icache не обрабатываются и остаются несогласованными. Поэтому при выполнении fence.i необходимо очистить icache, обеспечив обязательный miss при последующих обращениях, чтобы новые данные были прочитаны из памяти. Но независимо от выбранной схемы программа должна содержать инструкцию fence.i, чтобы соответствовать требованиям спецификации RISC-V; иначе она может некорректно работать на процессорах, использующих схему (3).

Различие этих схем фактически сводится к тому, где обеспечивается согласованность копий — аппаратно или программно. Если ISA требует, чтобы процессор аппаратно поддерживал согласованность копий, проблема прозрачна для программного обеспечения и программисту не нужно думать, где вставлять инструкции вроде fence.i, но аппаратная часть становится сложнее. Если ISA возлагает обеспечение согласованности на программное обеспечение, аппаратная часть упрощается, но нагрузка на программиста возрастает. Следовательно, по сути это компромисс между сложностью аппаратуры и сложностью разработки программ.

Имплементируйте инструкцию `fence.i`

На основе вашего понимания fence.i выберите разумную схему и реализуйте эту инструкцию в NPC. После реализации добавьте fence.i в подходящее место приведённого выше smc.c и снова запустите его на NPC. Если имплементация правильна, программа выведет символ A и затем успешно завершится.

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

В современных компьютерных системах self-modifying code вроде smc.c встречается редко, однако существует один модуль, который «часто изменяет другой код»: loader.

Вы уже знаете, что задача bootloader — переместить код и данные программы в целевую область памяти, а затем перейти к коду программы и продолжить выполнение. Для перемещения необходимы store-инструкции, и даже при копировании программного кода всё равно используются store. Это означает, что без добавления fence.i при переходе из bootloader к коду программы процессор RISC-V не гарантирует выборку правильных инструкций.

Для loader внутри операционной системы проблема ещё очевиднее. Операционная система может сначала загрузить программу A в определённую область памяти и перейти к её выполнению; после завершения A система решает загрузить программу B в ту же область. Без fence.i при выполнении программы B процессор может ошибочно получать инструкции старой программы A.

Воспроизведите проблему когерентности, вызванную loader, в bootloader

Измените поведение bootloader следующим образом:

1. Перед загрузкой целевой программы в нужную область памяти сначала поместите туда последовательность инструкций nop, завершающуюся инструкцией ret
2. Перейдите к началу этой последовательности nop через вызов функции; завершающая инструкция ret вернёт управление bootloader
3. Загрузите целевую программу и перейдите к её выполнению

В этих изменениях последовательность nop играет роль программы A из предыдущего обсуждения, а целевая программа — программы B.

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

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

Добавьте инструкцию `fence.i` в bootloader

После воспроизведения проблемы добавьте fence.i в подходящее место bootloader, скомпилируйте и повторно запустите. Если всё реализовано правильно, программа dummy успешно запустится даже с icache большой ёмкости.

После завершения можно удалить из bootloader код, связанный с последовательностью nop, и вернуть icache к прежней ёмкости.

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

SA