Такты для разработчиков

в 9:13, , рубрики: aes, hdl, Анализ и проектирование систем, аппаратная разработка, Блог компании Mail.Ru Group, криптография, программирование микроконтроллеров

Такты для разработчиков - 1

Если у вас есть опыт создания ПО и вы хотите познакомиться с проектированием цифровых логических схем (digital design), то одна из первых вещей, которые вам нужно понять, — это концепция тактов. Она раздражает многих программных инженеров, начинающих HDL-проектирование. Без использования тактов они могут превратить HDL в язык программирования с $display, if и циклами for, как в любом другом языке. Но при этом такты, которые новички игнорируют, — зачастую один из основополагающих элементов при проектировании любых цифровых логических схем.

Ярче всего эта проблема проявляется именно при рассмотрении первых схем, созданных начинающими HDL-разработчиками. Я недавно общался с некоторыми из них. Новички опубликовали свои вопросы на форумах, которые я читаю. Когда я проанализировал то, что они делают, от увиденного волосы встали дыбом.

Например, один из студентов попросил объяснить, почему никого в сети не заинтересовала его HDL-реализация AES. Не стану смущать его, приводить ссылку на проект или имя его создателя. Вместо этого я буду называть его студентом. (Нет, я не профессор.) Так вот, этот студент создал Verilog-схему, в которой AES-шифрование выполняется в течение не одного раунда, а каждый раунд, с комбинаторной логикой без тактов. Не помню, какой именно AES он применил, 128, 192 или 256, но AES требует от 10 до 14 раундов. В симуляторе его движок шифрования работал идеально, при этом на шифрование/дешифрование своих данных он использовал только один такт. Студент гордился своей работой, но не мог понять, почему те, кто её смотрел, говорили ему, что он мыслит как программный инженер, а не аппаратный.

Иллюстрация 1. Программное обеспечение последовательно

Такты для разработчиков - 2

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

Иногда эти программисты находят симулятор вроде Verilator, iverilog или EDA playground. Тогда они используют в своей логике кучу команд $display, обращаясь с ними, как с последовательными printf, заставляя код работать без применения тактов. Затем их схемы «работают» в симуляторе с использованием одной лишь комбинаторной логики.

И потом эти студенты описывают мне свои схемы и объясняют, что они «без тактов».

Знаете что?

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

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

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

Давайте пока обсудим такт и важность постройки и проектирования вашей логики вокруг него.

Урок № 1: аппаратная архитектура — это параллельная архитектура

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

Иллюстрация 2. Аппаратная логика работает параллельно

Такты для разработчиков - 3

Это многое меняет.

Иллюстрация 3. Программный цикл

Такты для разработчиков - 4

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

Хороший пример, иллюстрирующий это различие, — аппаратный цикл.

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

Аппаратные циклы на базе HDL работают совсем не так. Средство синтеза (synthesis tool) HDL использует описание цикла для создания нескольких копий логики, все они выполняются параллельно. Нет нужды синтезировать логику, используемую для создания цикла, — например индекс, инкрементирование этого индекса, сравнение индекса с финальным состоянием и т. д., — поэтому её обычно убирают. Более того, поскольку средство синтеза создаёт физические соединения и логические блоки, количество прохождений цикла не может изменяться после завершения синтеза.

Получающаяся структура показана на иллюстрации 4. Она очень отличается от структуры программного цикла на иллюстрации 3.

Иллюстрация 4. Цикл, сгенерированный HDL

Такты для разработчиков - 5

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

Но… теперь мы снова вернулись к концепции цикла.

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

Почему важен такт

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

Эта мысль изображена на графике. Давайте поместим сверху входные данные для нашего алгоритма, в середине — логику, а внизу — выходные данные. Ось времени отложим сверху вниз, от одного такта до другого.

Иллюстрация 5. Выполнение логики занимает время, три операции

Такты для разработчиков - 6

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

Посмотрите на розовые блоки.

Они отражают потери активности вашей аппаратной схемы (hardware circuit) — время, которое можно было бы потратить на выполнение каких-то операций. Но поскольку вы решили дождаться завершения такта или ждёте, чтобы сначала обработать входные данные, то вы ничего не можете делать. Например, на этом графике умножение длится не больше одного раунда применения AES, как и сложение. Однако вы не можете ничего сделать с результатами этих двух операций, пока выполняются вычисления AES, потому что для получения их следующих входных данных нужно дождаться следующего такта. То есть розовые блоки — это время простоя электронной схемы. Причём в данном случае оно увеличено из-за того, что раунды применения AES отдаляют следующий такт. Так что такая схема не сможет использовать всех возможностей оборудования.

Если бы нам нужен был лишь конвейер применения AES-алгоритма, чтобы один раунд мог быть вычислен в каждом такте, то схема могла бы работать быстрее, тратя меньше времени на ожидания.

Иллюстрация 6. Разбиение операций для ускорения тактов

Такты для разработчиков - 7

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

Это следствие более качественной архитектуры.

Можно ли сделать ещё лучше? Да! Если вы знакомы с AES, то знаете, что каждый раунд состоит из дискретных шагов. Их тоже можно раскидать, ещё больше увеличив скорость такта, пока выполнение логики AES-раунда не станет занимать меньше времени, чем умножение. Это увеличит количество сложений и умножений, которые вы можете выполнить, так что разложение движка шифрования на микроконвейеры позволит пропускать за такт ещё больше данных.

Неплохо.

Также на иллюстрации 6 показана парочка других вещей.

Во-первых, будем считать стрелки задержками при маршрутизации (routing delays). График не масштабный, это лишь иллюстрация для отвлечённой дискуссии. Каждая часть логики должна получать результат предыдущей части логики. Это означает, что даже если какой-то части логики не требуется времени для выполнения — как если бы просто менялся порядок проводов, — то переход логики с одного конца микросхемы к другому всё же займёт время. Следовательно, даже если вы максимально упрощаете свои операции, всё равно будут задержки на перемещение данных.

Во-вторых, вы могли заметить, что ни одна стрелка не начинается с начала такта. И ни одна не доходит до следующего такта. Это сделано для иллюстрирования концепции времени установки и удержания (setup and hold timing). Триггеры — это структуры, которые удерживают и синхронизируют ваши данные в такте. Им нужно время до начала такта, чтобы данные стали постоянны и определены. Хотя многие считают, что такт начинается мгновенно, на самом деле это не так. В разных частях микросхемы он начинается в разное время. И это тоже требует буфера между операциями.

К каким заключениям можно прийти в результате этого урока?

  1. Выполнение логики требует времени.
  2. Чем больше логики, тем больше нужно времени.
  3. Скорость такта ограничена количеством времени, которое нужно для выполнения логики, находящейся между тиками тактов (плюс задержки при маршрутизации, время установки и удержания, неопределённость начала такта и т. д.).
    Чем больше логики в тактах, тем ниже тактовая частота.
  4. Скорость быстрейшей операции будет ограничена скоростью такта, необходимой для выполнения самой медленной операции.
    Например, вышеописанная операция сложения. Она могла выполняться быстрее умножения и любого одиночного раунда применения AES, однако ей приходилось ждать выполнения остальной логики в схеме.
  5. Существует аппаратное ограничение скорости такта. Какое-то время уходит даже на операции, не требующие логики.

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

Сколько логики помещать в тактах?

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

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

Сделав это, вы освоите ряд эвристических правил, которые потом будете использовать для вычисления количества логики в тактах применительно к оборудованию, с которым вы работаете.

Например, я хочу построить схему с тактовой частотой 100 МГц с деталями серии Xilinx 7. Эти схемы потом обычно работают на 80 МГц и на Spartan-6 либо на 50 МГц и на iCE40 — хотя это и не строгие сочетания. На одном чипе пойдёт нормально, другой чип окажется избыточно мощным, на третьем появятся проблемы с проверкой синхронизации (timing check).

Вот несколько примерных эвристических правил, относящихся к тактам. Поскольку это эвристика, вряд ли она применима для всех видов схем:

  1. Обычно я могу в рамках такта выполнять 32-битное сложение с мультиплексированием 4—8 элементов.
    Если будете использовать более быстрые такты, например 200 МГц, то вам может понадобиться отделить сложение от мультиплексора.
    Самый длинный путь ZipCPU начинается с выходных данных ALU и заканчивается входными данными ALU.
    Звучит просто. Даже соответствует вышеописанной эвристике.
    Проблема, с которой борется ZipCPU на более высоких скоростях, заключается в маршрутизации выходных данных обратно в ALU.
    Давайте разберём маршрут: после ALU логический путь сначала идёт через четырёхсторонний мультиплексор, чтобы решить, чьи выходные данные нужно записать обратно — из ALU, памяти или операции деления. Затем записанный результат передаётся в схему обхода (bypass circuit), чтобы определить, нужно ли немедленно передавать его в ALU в качестве одних из двух входных данных. Только в конце этого мультиплексора и обхода наконец-то выполняется ALU-операция и мультиплексор. То есть на каждом этапе логический путь может пройти через ALU. Но благодаря конструкции ZipCPU любые такты, вставленные в логический путь, пропорционально замедлят выполнение ZipCPU. Это означает, что самый длинный путь наверняка на время останется самым длинным путём ZipCPU.
    Если бы меня интересовало выполнение ZipCPU с более высокой скоростью, то это был бы первый логический путь, который я попытался бы разбить и оптимизировать.
  2. 16×16-битное умножение занимает только один такт.
    Иногда на каком-нибудь оборудовании я могу реализовать в одном такте 32×32-битные умножения. А на другом оборудовании придётся разбивать на части. Так что если мне когда-нибудь понадобится знаковое (signed) 32×32-битное умножение, я воспользуюсь конвейерной подпрограммой (pipelined routine), которую я сделал для таких случаев. Она содержит несколько вариантов умножения, что позволяет мне выбирать подходящие для текущего оборудования опции.
    Ваше оборудование также может изначально поддерживать 18×18-битные умножения. Некоторые FPGA поддерживают умножение и накапливание в рамках одного оптимизированного аппаратного такта. Изучите своё оборудование, чтобы узнать, какие возможности вам доступны.
  3. Любое блочное обращение к оперативной памяти (block RAM access) занимает один такт. Старайтесь не подстраивать индекс в ходе этого такта. Также избегайте в это время любых операций с выходным данными.
    Хотя я утверждаю, что это хорошее правило, но мне приходилось успешно нарушать обе его части без (серьёзных) последствий при работе на 100 МГц на устройстве Xilinx 7 (у iCE40 с этим проблемы).
    Например, ZipCPU считывает из своих регистров, добавляет непосредственный операнд к результату, а затем выбирает, должен ли результат быть регистр плюс константа, PC плюс константа либо регистр кода условия (condition code register) плюс константа — всё в одном такте.
    Другой пример: долгое время Wishbone Scope определял адрес для считывания из своего буфера на основе того, выполняется ли чтение из памяти в ходе текущего такта. Разрыв этой зависимости потребовал добавления ещё одного такта задержки, так что текущая версия больше не нарушает это правило.

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

Следующие шаги

Возможно, лучший совет, что я могу напоследок дать новичкам-разработчикам FPGA, — это изучать HDL, параллельно практикуясь на реальном оборудовании, а не на одних лишь симуляторах. Инструменты, связанные с реальными аппаратными компонентами, позволят вам проверять код и необходимые тайминги. Кроме того, разрабатывать схемы для быстрых тактов — хорошо, но в аппаратном проектировании на этом свет клином не сошёлся.

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

Автор: Barrayar

Источник

Поделиться

* - обязательные к заполнению поля