Многие начинающие разработчики ПЛИС (и ASIC) не до конца понимают влияние временных ограничений (constraints – далее констрейнты) на результаты синтеза; то, каким образом констрейнты используются в статическом временном анализе. Большая часть литературы по этой тематике сводится к рассмотрению всевозможных видов констрейнтов, но ничего не говорит о внутренней “кухне” и используемых алгоритмах. Рассмотрению констрейнтов посвящен и недавний пост по данной тематике на ГТ (geektimes.ru/post/254932/ [1]). Между тем, констрейнты — лишь вершина айсберга. Их использование должно опираться на фундаментальные знания о статическом временном анализе, которые дают, к примеру, в американских университетах, но ничего не рассказывают у нас. Поэтому, собственно, поговорим о фундаменте.
В современных маршрутах проектирования синхронных схем используется два основных вида анализа: временное моделирование, и статический временной анализ.
Временное моделирование используется по большей части для функциональной верификации, и опирается на verilog-модели логических элементов, с использованием подключаемых задержек (файлы в стандартах sdf, tlf, и т.д.). Преимущество временного моделирования – точность, и способность моделировать большие схемы. Точность конечно ниже, чем при моделировании на уровне транзисторов (spice-моделирование), но вместе с тем вполне приемлемая, и что главное – на порядки более быстрая. Недостаток временного моделирования – огромная ресурсоемкость проверки полного покрытия тестами логики схемы. И чаще всего, 100%-ого покрытия логики тестами достичь не удается.
Статический временной анализ не моделирует поведение схемы в динамике, и не использует verilog-модели элементов. Так же, статический анализ не занимается рассмотрением функций схемы и составляющих ее элементов. Основной задачей статического анализа является рассмотрение всех (под 100% возможных комбинаций) задержек сигналов в схеме, и поиск нарушений в соответствии с заданными правилами проверок (констрейнтами). Статическим анализ назван потому, что производится в статике, по построенному в соответствии со схемой графу соединений. Или, точнее, по ациклическому орграфу.
Не влезая в теорию графов достаточно сказать, что орграф – это ориентированный граф, т.е. дуги графа имеют направление (так же как сигнал в проводе “бежит” в одном направлении — от источника к приемнику). Дуги графа – это провода между элементами, и “виртуальные” пути сигнала (arcs — арки) внутри элементов. К примеру, у элемента 2ИЛИ-НЕ всего две арки: от каждого из входов до выхода. Вершинами графа являются входы и выходы элементов, а так же входы и выходы схемы. В результате, по полученному графу можно строить пути сигналов (signal path), проходящие по дугам графа, через его вершины. Если все возможные пути сигналов конечны, то граф называется ациклическим. Статический временной анализ работает только с ациклическими орграфами, и как следствие, только с конечными траекториями сигналов. К примеру, если схема содержит обратную связь, часть путей сигналов окажется закольцованной, и не может анализироваться. Для борьбы с обратными связями используют костыль – САПР может попытаться сделать граф ациклическим, выкинув из него одну или несколько дуг (как правило, это арки внутри элементов). В результате получится граф без обратных связей, но выкинутые дуги более не участвуют в анализе – их задержка не учитывается в расчетах.
Для лучшего понимания сказанного, прокомментирую выборочные слайды из лекций по статическому временному анализу, которые читают студентам Техасского Университета в Остине.
Верхний левый угол – схема, состоящая из D-триггера (флопа), элемента выключения тактового импульса (clock-gate), и логического элемента на входе флопа. Правый верхний угол — правила построения графа:
• кружками обозначены входы и выходы элементов, а так же входы и выходы схемы,
• стрелками показаны ребра графа: соединения проводами, и арками (внутри элементов)
• двойными стрелками с пунктиром обозначены так называемые контрольные арки: они не содержат задержку, и в статическом анализе используются не для расчета задержек сигналов, а для контроля – к примеру, установки и удержания сигналов (setup/hold).
В нижней части рисунка показан получившийся граф. Все вершины подписаны (легко найти соответствие со схемой). Все дуги помечены как инвертирующие или неинвертирующие: к примеру, “r-r” и “f-f” расшифровывается как rise-rise и fall-fall, и означает, что показанная дуга не несет в себе инверсии сигнала. Если бы дуга (к примеру, арка в элементе ИЛИ-НЕ) была инвертирующей, то пометка бы была “r-f” и “f-r”, что означает rise-fall и fall-rise, или, другими словами, смену положительного фронта сигнала при прохождении через дугу на отрицательный, и наоборот. Как уже было сказано, функция элементов в статическом анализе не рассматривается, важно только – изотонная (неинвертирующая) функция у элемента, или антитонная (инвертирующая).
На что следует обратить внимание. Начальная точка пути сигнала (суть – переходного процесса) в синхронных схемах – это всегда либо интерфейсный сигнал, либо тактовый импульс. Если бы схема в приведенном примере была больше, то из тактового входа (clk) выходил бы целый пучок дуг на графе. А конечная точка пути сигнала в синхронной схеме – это опять же интерфейс, либо – вход данных триггера, или разрешение у clock-gate. При этом конечная точка пути сигнала завершается одной или несколькими контрольными арками, говорящими о том, какие проверки для полученного сигнала необходимо провести. В приведенном примере проверяется установка и удержание (setup и hold) сигнала на информационном входе триггера по отношению к тактовому входу (FF1:D — FF1:clock), и аналогичная проверка сигнала разрешения у элемента clock-gate.
Как констрейнты отражаются на графе. Констрейнты, влияющие на задержку интерфейса (set_input_delay, set_output_delay, set_drive, set_load и т.д.) просто изменяют значение задержки у внешних дуг графа. Существуют констрейнты, меняющие граф, к примеру: set_disable_timing или set_false_path. Многие констрейнты берутся автоматически из библиотеки элементов: к примеру, для контрольных арок — проверки на setup/hold. Я не хочу концентрироваться на констрейнтах, для их понимания достаточно прочитать описание в документации того же Synopsys DC [2], или образовательные стать в инстрнете, к примеру — на edacafe или semiwiki.
Теперь об алгоритмах расчета задержек. Статический временной анализ рассматривает только две крайних точки разброса задержек в элементах и схеме: наихудший случай, используемый для проверок ограничения на время установки сигнала (setup) по отношению к тактовому импульсу, и наилучший случай, используемый для проверок времени удержания (hold). Существует еще т.н. статистический статический временной анализ (SSTA), подходящий к вопросу более интеллектуально, но о нем как-нибудь в другой раз (тем более что разработчикам ПЛИС этот вид анализа вообще не актуален).
При расчете задержек используется две стратегии – расчет фактического времени прихода сигнала (AT – Arrival Time), и расчет исходя из требуемого времени прихода сигнала (RAT – Required Arrival Time). Для начала, как считается AT:
Для простоты, будем считать, что задержки переднего и заднего фронта одинаковы (хотя обычно ведется раздельный расчет для обоих вариантов). И вместо графа будем рисовать задержки прямо на схеме, поскольку это нагляднее. Итого, на приведенном рисунке задержки проводов учтены в задержках элементов, и обозначены двумя цифрами через запятую: первая цифра означает самый ранний приход сигнала, а вторая цифра означает самый поздний момент его прихода. К примеру, “1,2” на входе означает, что сигнал придет не раньше 1нс, и не позже 2нс, а “2.3” внутри логического элемента означает его задержку в диапазоне от 2 до 3нс. Откуда в расчете могла взять задержка на входном сигнале? К примеру, она может быть задана констрейнтами set_input_delay с ключами -min и -max. Задержка элемента берется из библиотеки элементов (измеряется разработчиком библиотеки). Зелеными цифрами показан ход расчета. Для верхнего левого элемента – при собственной задержке 2-3нс, сигнал на выходе может быть получен в момент 2-4нс (если элемент сработает по первому входу), и 3-5нс, если по второму. Оба диапазона попросту складываются (поскольку функция элементов не учитывается), и получается результат: “2,5” или от 2 до 5нс (т.е. не раньше 2нс, и не позже 5нс).
Далее, о расчете требуемого времени:
Теперь расчет осуществляется в обратном направлении. Предположим, что констрейнтами приход выходных сигналов ограничен в диапазоне “5,10” и “4,10” соотв. Эти ограничения можно задать с помощью set_output_delay с ключами -min и –max. Затем идет расчет в обратную сторону, к примеру если из диапазона 4-10 вычесть задержку элемента 2-4, то это будет означать, что сигнал может попасть на входы элемента не раньше 2нс и не позже 6нс. При этом выход инвертора, который имел ограничения 5-10 автоматически ограничивается более жестким диапазоном 5-6 (получается пересечением 5-10 и 2-6).
В завершении, когда получено требуемое время распространения сигналов, и фактическое, можно посчитать нарушения (slack).
Зеленым показано фактическое время, синим требуемое. Разница (slack) рассчитана, и показана на схеме черным шрифтом. При этом, отрицательное значение разницы считается нарушением, положительное — запасом. В любом репорте результатов статического анализа Вы увидите две таблицы – расчет фактического времени, расчет требуемого, вычисление разницы, и подведение итога — MET или NOT MET.
В заключении хотелось бы добавить, что успешные результаты статического временного анализа вовсе не являются гарантией работоспособности дизайна. На это указывает тот простой факт, что граф строится при активном участии разработчика (посредством констрейнтов), и может быть построен с ошибкой. Ошибка в графе выливается в неконтролируемые пути в схеме, которые можно выловить только временным моделированием с проверками временных ограничений (т.е. с использованием задержек на интерфейсах). Нарушение временного моделирования часто указывает на наличие ошибки в констрейнтах. Отсюда простой вывод – статический временной анализ не заменяет функциональное моделирование, а дополняет.
Надеюсь, изложенный материал позволит лучше разобраться со статическим временным анализом, увидеть его “изнутри”, и более осмысленно писать констрейнты для своего дизайна. Для тех, кто захочет копать дальше, могу посоветовать прочитать книгу “Static Timing Analysis for Nanometer Designs: A Practical Approach” [3] на английском языке.
[1] geektimes.ru/post/254932/
[2] www.synopsys.com
[3] www.springer.com/us/book/9780387938196
В современных маршрутах проектирования синхронных схем используется два основных вида анализа: временное моделирование, и статический временной анализ.
Временное моделирование используется по большей части для функциональной верификации, и опирается на verilog-модели логических элементов, с использованием подключаемых задержек (файлы в стандартах sdf, tlf, и т.д.). Преимущество временного моделирования – точность, и способность моделировать большие схемы. Точность конечно ниже, чем при моделировании на уровне транзисторов (spice-моделирование), но вместе с тем вполне приемлемая, и что главное – на порядки более быстрая. Недостаток временного моделирования – огромная ресурсоемкость проверки полного покрытия тестами логики схемы. И чаще всего, 100%-ого покрытия логики тестами достичь не удается.
Статический временной анализ не моделирует поведение схемы в динамике, и не использует verilog-модели элементов. Так же, статический анализ не занимается рассмотрением функций схемы и составляющих ее элементов. Основной задачей статического анализа является рассмотрение всех (под 100% возможных комбинаций) задержек сигналов в схеме, и поиск нарушений в соответствии с заданными правилами проверок (констрейнтами). Статическим анализ назван потому, что производится в статике, по построенному в соответствии со схемой графу соединений. Или, точнее, по ациклическому орграфу.
Не влезая в теорию графов достаточно сказать, что орграф – это ориентированный граф, т.е. дуги графа имеют направление (так же как сигнал в проводе “бежит” в одном направлении — от источника к приемнику). Дуги графа – это провода между элементами, и “виртуальные” пути сигнала (arcs — арки) внутри элементов. К примеру, у элемента 2ИЛИ-НЕ всего две арки: от каждого из входов до выхода. Вершинами графа являются входы и выходы элементов, а так же входы и выходы схемы. В результате, по полученному графу можно строить пути сигналов (signal path), проходящие по дугам графа, через его вершины. Если все возможные пути сигналов конечны, то граф называется ациклическим. Статический временной анализ работает только с ациклическими орграфами, и как следствие, только с конечными траекториями сигналов. К примеру, если схема содержит обратную связь, часть путей сигналов окажется закольцованной, и не может анализироваться. Для борьбы с обратными связями используют костыль – САПР может попытаться сделать граф ациклическим, выкинув из него одну или несколько дуг (как правило, это арки внутри элементов). В результате получится граф без обратных связей, но выкинутые дуги более не участвуют в анализе – их задержка не учитывается в расчетах.
Для лучшего понимания сказанного, прокомментирую выборочные слайды из лекций по статическому временному анализу, которые читают студентам Техасского Университета в Остине.
Верхний левый угол – схема, состоящая из D-триггера (флопа), элемента выключения тактового импульса (clock-gate), и логического элемента на входе флопа. Правый верхний угол — правила построения графа:
• кружками обозначены входы и выходы элементов, а так же входы и выходы схемы,
• стрелками показаны ребра графа: соединения проводами, и арками (внутри элементов)
• двойными стрелками с пунктиром обозначены так называемые контрольные арки: они не содержат задержку, и в статическом анализе используются не для расчета задержек сигналов, а для контроля – к примеру, установки и удержания сигналов (setup/hold).
В нижней части рисунка показан получившийся граф. Все вершины подписаны (легко найти соответствие со схемой). Все дуги помечены как инвертирующие или неинвертирующие: к примеру, “r-r” и “f-f” расшифровывается как rise-rise и fall-fall, и означает, что показанная дуга не несет в себе инверсии сигнала. Если бы дуга (к примеру, арка в элементе ИЛИ-НЕ) была инвертирующей, то пометка бы была “r-f” и “f-r”, что означает rise-fall и fall-rise, или, другими словами, смену положительного фронта сигнала при прохождении через дугу на отрицательный, и наоборот. Как уже было сказано, функция элементов в статическом анализе не рассматривается, важно только – изотонная (неинвертирующая) функция у элемента, или антитонная (инвертирующая).
На что следует обратить внимание. Начальная точка пути сигнала (суть – переходного процесса) в синхронных схемах – это всегда либо интерфейсный сигнал, либо тактовый импульс. Если бы схема в приведенном примере была больше, то из тактового входа (clk) выходил бы целый пучок дуг на графе. А конечная точка пути сигнала в синхронной схеме – это опять же интерфейс, либо – вход данных триггера, или разрешение у clock-gate. При этом конечная точка пути сигнала завершается одной или несколькими контрольными арками, говорящими о том, какие проверки для полученного сигнала необходимо провести. В приведенном примере проверяется установка и удержание (setup и hold) сигнала на информационном входе триггера по отношению к тактовому входу (FF1:D — FF1:clock), и аналогичная проверка сигнала разрешения у элемента clock-gate.
Как констрейнты отражаются на графе. Констрейнты, влияющие на задержку интерфейса (set_input_delay, set_output_delay, set_drive, set_load и т.д.) просто изменяют значение задержки у внешних дуг графа. Существуют констрейнты, меняющие граф, к примеру: set_disable_timing или set_false_path. Многие констрейнты берутся автоматически из библиотеки элементов: к примеру, для контрольных арок — проверки на setup/hold. Я не хочу концентрироваться на констрейнтах, для их понимания достаточно прочитать описание в документации того же Synopsys DC [2], или образовательные стать в инстрнете, к примеру — на edacafe или semiwiki.
Теперь об алгоритмах расчета задержек. Статический временной анализ рассматривает только две крайних точки разброса задержек в элементах и схеме: наихудший случай, используемый для проверок ограничения на время установки сигнала (setup) по отношению к тактовому импульсу, и наилучший случай, используемый для проверок времени удержания (hold). Существует еще т.н. статистический статический временной анализ (SSTA), подходящий к вопросу более интеллектуально, но о нем как-нибудь в другой раз (тем более что разработчикам ПЛИС этот вид анализа вообще не актуален).
При расчете задержек используется две стратегии – расчет фактического времени прихода сигнала (AT – Arrival Time), и расчет исходя из требуемого времени прихода сигнала (RAT – Required Arrival Time). Для начала, как считается AT:
Для простоты, будем считать, что задержки переднего и заднего фронта одинаковы (хотя обычно ведется раздельный расчет для обоих вариантов). И вместо графа будем рисовать задержки прямо на схеме, поскольку это нагляднее. Итого, на приведенном рисунке задержки проводов учтены в задержках элементов, и обозначены двумя цифрами через запятую: первая цифра означает самый ранний приход сигнала, а вторая цифра означает самый поздний момент его прихода. К примеру, “1,2” на входе означает, что сигнал придет не раньше 1нс, и не позже 2нс, а “2.3” внутри логического элемента означает его задержку в диапазоне от 2 до 3нс. Откуда в расчете могла взять задержка на входном сигнале? К примеру, она может быть задана констрейнтами set_input_delay с ключами -min и -max. Задержка элемента берется из библиотеки элементов (измеряется разработчиком библиотеки). Зелеными цифрами показан ход расчета. Для верхнего левого элемента – при собственной задержке 2-3нс, сигнал на выходе может быть получен в момент 2-4нс (если элемент сработает по первому входу), и 3-5нс, если по второму. Оба диапазона попросту складываются (поскольку функция элементов не учитывается), и получается результат: “2,5” или от 2 до 5нс (т.е. не раньше 2нс, и не позже 5нс).
Далее, о расчете требуемого времени:
Теперь расчет осуществляется в обратном направлении. Предположим, что констрейнтами приход выходных сигналов ограничен в диапазоне “5,10” и “4,10” соотв. Эти ограничения можно задать с помощью set_output_delay с ключами -min и –max. Затем идет расчет в обратную сторону, к примеру если из диапазона 4-10 вычесть задержку элемента 2-4, то это будет означать, что сигнал может попасть на входы элемента не раньше 2нс и не позже 6нс. При этом выход инвертора, который имел ограничения 5-10 автоматически ограничивается более жестким диапазоном 5-6 (получается пересечением 5-10 и 2-6).
В завершении, когда получено требуемое время распространения сигналов, и фактическое, можно посчитать нарушения (slack).
Зеленым показано фактическое время, синим требуемое. Разница (slack) рассчитана, и показана на схеме черным шрифтом. При этом, отрицательное значение разницы считается нарушением, положительное — запасом. В любом репорте результатов статического анализа Вы увидите две таблицы – расчет фактического времени, расчет требуемого, вычисление разницы, и подведение итога — MET или NOT MET.
В заключении хотелось бы добавить, что успешные результаты статического временного анализа вовсе не являются гарантией работоспособности дизайна. На это указывает тот простой факт, что граф строится при активном участии разработчика (посредством констрейнтов), и может быть построен с ошибкой. Ошибка в графе выливается в неконтролируемые пути в схеме, которые можно выловить только временным моделированием с проверками временных ограничений (т.е. с использованием задержек на интерфейсах). Нарушение временного моделирования часто указывает на наличие ошибки в констрейнтах. Отсюда простой вывод – статический временной анализ не заменяет функциональное моделирование, а дополняет.
Надеюсь, изложенный материал позволит лучше разобраться со статическим временным анализом, увидеть его “изнутри”, и более осмысленно писать констрейнты для своего дизайна. Для тех, кто захочет копать дальше, могу посоветовать прочитать книгу “Static Timing Analysis for Nanometer Designs: A Practical Approach” [3] на английском языке.
[1] geektimes.ru/post/254932/
[2] www.synopsys.com
[3] www.springer.com/us/book/9780387938196
Комментарии (4)
nerudo
21.10.2015 17:19> Многие начинающие разработчики… не до конца понимают влияние временных ограничений… на результаты синтеза
Потому что хрен производители тулзов об это рассказывают. Ну то есть общие слова и понятия на уровне учебника — да, а вот конкретные критерии оптимизации и внутреннее устройство алгоритмов — за семью замками.Khort
21.10.2015 18:17Эти знания точно есть у саппорта/консультантов коммерческих САПР (в Cadence и Synopsys, как минимум), поскольку их готовят на Западе, и регулярно посылают на тренинги для повышения квалификации. Но делятся они этими знаниями очень неохотно, поскольку информация об алгоритмах САПР действительно закрыта, по большей части. Есть еще специалисты в МИЭТ (Зеленоград), которые пишут свои тулы для синтеза БМК. А в остальном да, доступной информации мало, и хороших учебников (на русском) видимо нет. Да и на английском тоже.
Но в принципе, никакого секрета и нет, на самом деле, поскольку все эти алгоритмы выросли из научных публикаций 30-40 летней давности. К примеру, упоминание DAG (Directed Acyclic Graph — ациклический орграф) я видел в какой то статье IEEE начала 80х. Потом уже, все эти фундаментальные наработки собрали в кучу, и направили в прикладное/коммерческое русло. Т.е. когда в 90х годах появлялись первые тулы Synopsys, Cadence, Altera и т.д., вся теория уже давно была разработана.
covsh
спасибо за публикацию.
от себя хочу порекомендовать мануал для пользователей timequest от altera. советую начать с главы 2, там самые основы основ очень хорошо разжевываются.
Khort
Старался, спасибо.
К сожалению, пост получился достаточно поверхностный, поскольку чтобы рассказать в подробностях, к примеру, о об одних только разновидностях арок (синхронные, асинхронные, setup, hold, recovery, removal, и т.д. и т.п.), пришлось бы давать подробный обзор формата Liberty (Synopsys). А это уже уходит далеко за рамки FPGA, и получился бы уже не пост, а целая статья страниц на н-цать. Впрочем, в книге по третьей ссылке из моего поста это все есть.