Constraints

На Хабре уже было несколько статей упоминающих deferred constraints.

• Postgres: bloat, pg_repack и deferred constraints
  
• Ограничения (сonstraints) PostgreSQL: exclude, частичный unique, отложенные ограничения и др
  

Но хочется рассказать о них подробнее.






Одна из сильных сторон реляционных СУБД это постоянная бдительность за согласованностью данных (ACID, C Согласованность). Разработчик может задать ограничения данным, а СУБД будет следить за их исполнением. Это позволяется избежать многих потенциальных ошибок.

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

Гранулярность проверки ограничений

В PostgreSQL есть 3 уровня проверки ограничений

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

В PostgreSQL уровень всех ограничений по умолчанию NOT DEFERRABLE.


Чтобы изменить гранулярность проверки ограничения мы должны явно объявить ограничение как отложенное. При этом некоторые ограничения нельзя отложить. CHECK и NOT NULL всегда будут проверяться для каждой строки. Это поведение PostgreSQL нарушает SQL-стандарт.



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

ALTER TABLE foo  ADD CONSTRAINT foo_bar_fk  FOREIGN KEY (bar_id) REFERENCES bar (id)  DEFERRABLE INITIALLY IMMEDIATE; -- магия, объявляющая ограничение с возможностью быть отложенным, но по умолчанию оно будет проверяться сразу.

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

BEGIN;-- Отложить проверку ограниченияSET CONSTRAINTS foo_bar_fk DEFERRED;-- ...-- Производим операции над bar_id-- ...COMMIT; -- В данном месте произойдёт проверка ограничения

Кроме того, мы можем использовать другой подход и объявить ограничение при создании как DEFERRABLE INITIALLY DEFERRED. Если транзакция не хочет откладывать проверку такого ограничения, то она может выполнить SET CONSTRAINTS constraint_name IMMEDIATE.

Без явного начала транзакции через BEGIN каждый запрос выполняется в своей неявной транзакции из одного запроса, поэтому нет разницы между IMMEDIATE и DEFERRED для одного запроса.
Попытка отложить ограничения вне транзакции не работает и приведёт к предупреждению WARNING: 25P01: SET CONSTRAINTS can only be used in transaction blocks.

Ещё одно важно замечание. Ограничения UNIQUE и PRIMARY KEY, объявленные как DEFERRABLE INITIALLY IMMEDIATE будут проверяться не на уровне строки, а на уровне запроса. Даже если транзакция не откладывает проверку ограничения, гранулярность всё равно изменится.

Давайте рассмотрим отличие гранулярности проверки на уровне строки и запроса на следующем примере.

CREATE TABLE snowflakes ( i int UNIQUE NOT DEFERRABLE);INSERT INTO snowflakes VALUES (1), (2), (3);UPDATE snowflakes SET i = i + 1;

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

ERROR:  23505: duplicate key value violates unique constraint "snowflakes_i_key"DETAIL:  Key (i)=(2) already exists.

Если бы PostgreSQL дождался обновления всех строк (как в проверке на уровне по запросу), то проблем бы не было. Значение i в строках будет последовательно увеличиваться и в итоге они все станут уникальными. Так как PostgreSQL проверяет ограничения сразу, то после обновления первой строки с i=1 на i=2 состояние таблицы будет 2, 2, 3.

Построчная проверка ограничений хрупка и зависит от физического расположения строк. Например, если бы мы заполнили таблицу в обратном порядке INSERT INTO snowflakes VALUES (3), (2), (1)), то UPDATE сработал бы.

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

CREATE TABLE snowflakes ( i int UNIQUE DEFERRABLE INITIALLY IMMEDIATE);INSERT INTO snowflakes VALUES (1), (2), (3);UPDATE snowflakes SET i = i + 1;

Зачем нужны отложенные ограничения?

Циклические внешние ключи

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

CREATE TABLE husbands (  id int PRIMARY KEY,  wife_id int NOT NULL);CREATE TABLE wives (  id int PRIMARY KEY,  husband_id int NOT NULL);ALTER TABLE husbands ADD CONSTRAINT h_w_fk  FOREIGN KEY (wife_id) REFERENCES Wives;ALTER TABLE wives ADD CONSTRAINT w_h_fk  FOREIGN KEY (husband_id) REFERENCES husbands;

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

ALTER TABLE husbands ALTER CONSTRAINT h_w_fk  DEFERRABLE INITIALLY DEFERRED;ALTER TABLE wives ALTER CONSTRAINT w_h_fk  DEFERRABLE INITIALLY DEFERRED;

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

BEGIN;INSERT INTO husbands (id, wife_id) values (1, 1);INSERT INTO wives (id, husband_id) values (1, 1);COMMIT;-- и жили они долго и счастливо :)

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

-- Сделаем ограничения вновь проверяемыми сразу ALTER TABLE husbands ALTER CONSTRAINT h_w_fk  NOT DEFERRABLE;ALTER TABLE wives ALTER CONSTRAINT w_h_fk  NOT DEFERRABLE;-- Вместо двух INSERT выполним один SQL-запросWITH wife AS (    INSERT INTO wives (id, husband_id)      VALUES (2, 2)  )  INSERT INTO husbands (id, wife_id)    VALUES (2, 2);

Общие табличные выражения (CTEs) позволяют выполнить несколько SQL-запросов, которые будут считаться одним при проверке ограничений, так как внешние ключи проверяются на уровне запроса.

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

Перестановка элементов, по одному на группу

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

CREATE TABLE classes (  id int PRIMARY KEY,  teacher_id int UNIQUE NOT NULL);INSERT INTO classes VALUES (1, 1), (2, 2);

Трюк с CTE не получится так как не отложенное ограничение UNIQUE проверяется на уровне строки, а не запроса.

WITH swap AS (    UPDATE classes       SET teacher_id = 2     WHERE id = 1  )UPDATE classes   SET teacher_id = 1 WHERE id = 2;ERROR:  23505: duplicate key value violates unique constraint "classes_teacher_id_key"DETAIL:  Key (teacher_id)=(1) already exists.

Чтобы переставить учителей без отложенного ограничения на teacher_id, мы можем
использовать временного учителя.

-- Временный учитель 999, позволит произвести перестановкуUPDATE classes SET teacher_id = 999 WHERE id = 1;UPDATE classes SET teacher_id = 1   WHERE id = 2;UPDATE classes SET teacher_id = 2   WHERE id = 1;

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

CREATE TABLE classes (  id int PRIMARY KEY,  teacher_id int NOT NULL UNIQUE    DEFERRABLE INITIALLY IMMEDIATE);

Это позволит произвести обмен намного проще:

BEGIN;SET CONSTRAINTS classes_teacher_id_key DEFERRED;UPDATE classes SET teacher_id = 1 WHERE id = 2;UPDATE classes SET teacher_id = 2 WHERE id = 1;COMMIT;

Теперь будет работать подход CTE с неявной транзакцией, так как ограничение проверяется на уровне запроса, а не строки.

Перенумерация списка

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

CREATE TABLE todos (  list_id int,  position int,  task text,  PRIMARY KEY (list_id, position));INSERT INTO todos VALUES  (1, 1, 'write grocery list'),  (1, 2, 'go to store'),  (1, 3, 'buy items');

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

Допустим мы вспомнили, что забыли добавить элемент в начало списка составить меню. Если мы хотим установить данному элементу позицию 1, то нужно сместить все остальные элементы на +1. Это такая же задача как и в прошлом примере про снежинки.

Объявив первичный ключ как отложенный, мы исправим данную проблему:

CREATE TABLE todos (  list_id int,  position int,  task text,  PRIMARY KEY (list_id, position)    DEFERRABLE INITIALLY IMMEDIATE);

В данном случае PostgreSQL будет проверять ограничение на уровне запроса, и нам не нужно дополнительного запроса в транзакции, чтобы отложить проверку ограничения SET DEFERRED.

UPDATE todosSET position = position + 1WHERE list_id = 1;INSERT INTO todos VALUES  (1, 1, 'plan menus');

Но отложенные ограничения не лучшее решение в данном случае. Изменяемую позицию лучше хранить как дробь (рациональное число), вместо целого. Данный подход всегда позволит найти позицию между двумя существующими элементами. Посмотрите мою статью User-defined Order in SQL. Такой подход позволит не использовать отложенные ограничения.

Загрузка данных в таблицы

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

В некоторых интернет статьях утверждают, что отложенные ограничения позволяют быстрее выполнять массовые вставки (bulk INSERTs). По моим оценкам, это миф. Во время фиксации транзакции такое же кол-во проверок будет выполнено для отложенных и не отложенных ограничений. Для проверки:

CREATE TABLE parent (  id int PRIMARY KEY,  name text NOT NULL);CREATE TABLE child (  id int PRIMARY KEY,  parent_id int REFERENCES parent    DEFERRABLE INITIALLY IMMEDIATE,  name text);INSERT INTO parentSELECT  generate_series(1,1000000) AS id,  md5(random()::text) as name;

Теперь вставим 5 миллион строк в таблицу child и замерим время вставки и проверки внешнего ключа. Запуск был на моём ноутбуке с PostgreSQL 9.6.3:

INSERT INTO childSELECT  generate_series(1,5000000) AS id,  generate_series(1,1000000) AS parent_id,  md5(random()::text) as name;---- Time: 89064.987 ms

Попробуем ещё раз, но теперь отложим проверку ограничения:

BEGIN;SET CONSTRAINTS child_parent_id_fkey DEFERRED;INSERT INTO childSELECT  generate_series(1,5000000) AS id,  generate_series(1,1000000) AS parent_id,  md5(random()::text) as name;---- Time: 40828.810 msCOMMIT;---- Time: 47211.533 ms-- Total: 88040.343 ms

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

Причины не использовать отложенные ограничения

Кажется что отложенные ограничения это круто! Объявление ограничений отложенными даёт нам большую гибкость, но почему не стоит откладывать все ограничения?

Планировщик запросов и штраф производительности

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

Чтобы узнать больше, я спросил Andrew Gierth, RhodiumToad, в IRC, и получил следующий ответ: Планировщик может определить, что набор условий в таблице гарантирует уникальность результата. Если существует уникальный, неотложный индекс, он может исключить этап сортировки/уникальности или хеширования. Но при отложенных ограничениях могут присутствовать повторяющиеся значения.

Он обрисовал в общих чертах две оптимизации: одну в PostgreSQL 9 и одну в 10ой версии. Старый функционал это удаление JOIN'a из запроса:

CREATE TABLE foo (  a integer UNIQUE,  b integer UNIQUE DEFERRABLE);EXPLAINSELECT t1.*FROM foo t1LEFT JOIN foo t2  ON (t1.a = t2.a);

Заметьте JOIN исчез, и используется обычный Seq Scan:

                       QUERY PLAN---------------------------------------------------------- Seq Scan on foo t1  (cost=0.00..32.60 rows=2260 width=8)

Но если использовать JOIN по b, с отложенным ограничением, то JOIN останется:

EXPLAINSELECT t1.*FROM foo t1LEFT JOIN foo t2  ON (t1.b = t2.b);                              QUERY PLAN---------------------------------------------------------------------- Hash Left Join  (cost=60.85..124.53 rows=2260 width=8)   Hash Cond: (t1.b = t2.b)   -> Seq Scan on foo t1  (cost=0.00..32.60 rows=2260 width=8)   -> Hash  (cost=32.60..32.60 rows=2260 width=4)       -> Seq Scan on foo t2  (cost=0.00..32.60 rows=2260 width=4)

В PostgreSQL 10 есть другая оптимизация, которая превращает semi-JOIN из подзапроса IN в обычный JOIN, когда столбец подзапроса гарантировано уникален.

EXPLAINSELECT *FROM fooWHERE a IN (  SELECT a FROM foo);-- Планировщик понял, что столбец а уникальный                               QUERY PLAN------------------------------------------------------------------------- Hash Join  (cost=60.85..121.97 rows=2260 width=8)   Hash Cond: (foo.a = foo_1.a)   ->  Seq Scan on foo  (cost=0.00..32.60 rows=2260 width=8)   ->  Hash  (cost=32.60..32.60 rows=2260 width=4)         ->  Seq Scan on foo foo_1  (cost=0.00..32.60 rows=2260 width=4)

В случае с b, отложенное ограничение помешает оптимизации

EXPLAINSELECT *FROM fooWHERE b IN (  SELECT b FROM foo);                               QUERY PLAN------------------------------------------------------------------------- Hash Semi Join  (cost=60.85..124.53 rows=2260 width=8)   Hash Cond: (foo.b = foo_1.b)   ->  Seq Scan on foo  (cost=0.00..32.60 rows=2260 width=8)   ->  Hash  (cost=32.60..32.60 rows=2260 width=4)         ->  Seq Scan on foo foo_1  (cost=0.00..32.60 rows=2260 width=4)

Усложнение отладки

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

CREATE TABLE u (  i int UNIQUE DEFERRABLE INITIALLY IMMEDIATE);BEGIN;SET CONSTRAINTS u_i_key DEFERRED;INSERT INTO u (i) VALUES (1), (2);-- ... другие SQL-запросыINSERT intu u (i) VALUES (2), (3);-- ... другие SQL-запросыINSERT intu u (i) VALUES (3), (4);COMMIT;ERROR:  23505: duplicate key value violates unique constraint "u_i_key"DETAIL:  Key (i)=(2) already exists.

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

Ошибки во время фиксации транзакции могут не только сбить с толку, но и внести погрешность в ORM. DataMapper предназначены для упрощенного доступа к СУБД и не все могут правильно обработать ошибки ограничений на уровне транзакций.

Так же любая работа выполненная после отложенного ограничения может быть в итоге потеряна, после отката транзакции. Отложенные ограничения могут тратить CPU впустую.

Откладывание ограничения по столбцу

Последний трюк для развлечения.

Команда SET CONSTRAINTS принимает имя ограничения. Но может быть удобнее отложить ограничения по столбцам. PostgreSQL information_schema позволяет искать ограничения по столбцам.

CREATE VIEW deferrables ASSELECT table_schema, table_name, column_name,       conname, contypeFROM  pg_constraint,  information_schema.constraint_column_usageWHERE constraint_name = conname  AND condeferrable = TRUE;-- Отложить все ограничения для столбцаCREATE FUNCTION defer_col_constraints(    t_name information_schema.sql_identifier,    c_name name  ) RETURNS void AS $$DECLARE  names text;BEGIN  names := (    SELECT array_to_string(array_agg(conname), ', ')    FROM deferrables    WHERE table_name = $1    AND column_name = $2  );  EXECUTE format(    'SET CONSTRAINTS %s DEFERRED',    names  );END;$$ LANGUAGE plpgsql;

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

BEGIN;SELECT defer_col_constraints('child', 'parent_id');-- ...COMMIT;

Здравствуйте. Эта статья написана для самых-самых новичков в мире ПЛИС. В ней я попытаюсь максимально просто и понятно рассказать что такое временные ограничения (timing constraints), накладываемые на проекты под ПЛИС.

Статья создана на основе собственного опыта попыток объяснить тему самому себе, студентам-практикантам и любопытным коллегам так, чтобы не погружаться в заумные академические дебри, а максимально просто, прозрачно, на пальцах. Я учился работать с ПЛИС без учебы и подготовки и знаю по своему опыту как трудно что-то понять не имея теоретического базиса в этой теме и в схемотехнике. Если на данную статью наткнется некий мэтр и воскликнет, что описанное элементарно, то посмею не согласиться. Для какого-нибудь студента четвертого курса статья будет полезной и поможет разобраться во всех этих слэках, сетапах и холдах.

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

Введение

Проведу короткое введение на языке простых понятий.

Для того, чтобы в ПЛИС что-то работало, в нее нужно загрузить (залить, зашить) файл прошивки, с помощью программатора и утилиты прошивания. Файл прошивки является продуктом компиляции САПРом некоторого проекта папки с файлами, каждый из которых описывает какую-либо сторону проекта. В простых случаях пользователь описывает сам лишь файлы с исходным кодом, файл с распиновкой и файл с временными ограничениями. Из этой триады только файл временных ограничений является формально необязательной частью проекта. Собственно, если ваш проект не содержит частот выше 30-50 МГц, то вполне вероятно, что этот файл и не пригодится. Однако, если проект содержит высокие тактовые частоты и не укомплектован файлом временных ограничений, то вы не узнаете о том, что ваш проект не будет успевать обрабатывать данные.

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

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

Таким образом, синхронные схемы состоят из межрегистровых передач данных (RTL, register transfer logic, r2r transfer). И ключевой аспект временного анализа состоит в измерении слэка (slack). Это слово буквально переводится как провисание, запас по времени, но в русскоязычной среде чаще употребляют кальку с английского слэк. В рамках межрегистровой передачи речь идет о слэках предустановки (Setup) и слэках удержания (Hold).

Межрегистровая передача

Межрегистровая передача (рис. 1) рассматривается как система из двух последовательно включенных регистров, которые работают на синхронных в общем случае клоках. В простом случае на одном клоке. Один регистр является источником (source), а другой является получателем данных (destination). Между ними на пути данных находится некая произвольно определенная пользователем комбинационная логика. Она несинхронная так как не имеет в себе элементов памяти с синхронизирующим сигналом, наподобие регистров. Эта логика и есть то поведение, те логические операции, которые пользователь описывает своим кодом. Регистры это те однобитные переменные, которым пользователь дает имена в коде и оперирует по отдельности, либо объединяя в вектора и массивы.


Рис. 1. Схема передачи данных от регистра к регистру

Существует два понятия, связанные с приемом данных регистром-получателем: Setup time и Hold time. Они очерчивают собой диапазон времени, в течение которого сигнал на входе получателя должен быть стабильным и актуальным. Стабильным по существу означает, что его напряжение должно быть очень близко к одному из двух логических состояний 0 или 1, а не болтаться между ними с вероятностью перепутывания. Актуальным означает, что этот бит информации должен по смыслу относиться к этому такту клока, который его захватит, а не запоздавший бит от предыдущего такта.

Setup time время предустановки, минимальное время, за которое до прихода фронта клока сигнал данных уже должен установиться в стабильное состояние.

Hold time время удержания, минимальное время, которое после прихода фронта клока сигнал данных должен всё ещё удерживаться в стабильном состоянии.

То есть данные на входе получателя должны быть стабильными и актуальными не только в момент прихода фронта клока, но и на протяжении некоторого защитного интервала времени вокруг него (рис.2), длительностью не менее (Setup_time + Hold_time).


Рис. 2. Смысл Setup Time и Hold time как защитного интервала

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

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

Слэков, соответственно, тоже два Setup Slack и Hold Slack (рис.3).

Setup Slack характеризует собой запас по времени, который имеют данные от момента стабилизации до начала интервала Setup time.

Hold Slack характеризует собой запас по времени, который имеют данные от окончания интервала Hold time до потери данными стабильности.

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


Рис. 3. Положение слэков во времени

Расчет слэков

Теперь перейдем к тому, как эти слэки рассчитываются. Начнем с Setup Slack.
Рассмотрим схему передачи данных на рис. 4.


Рис. 4. Схема передачи данных

Здесь мы вводим такие понятия как фронт запуска, фронт захвата, момент прибытия данных, момент ожидания данных и момент прибытия клока.

Фронт запуска (Launch Edge) это фронт клока, пришедший на вход регистра-источника и запустивший процесс передачи данных.

Фронт захвата (Latch Edge) это фронт клока, следующий после Launch Edge через один период клока, который приходит на регистр-получатель и заставляет его захватить данные на входе.

Момент прибытия данных (Data Arrival Time) определяется как время фактического прибытия данных на регистр-получатель.

Момент ожидания данных (Data Required Time) определяется как время, за которое данные должны дойти до получателя до наступления времени предустановки на регистре-получателе.

Момент прибытия клока (Clock Arrival Time) определяется как время прохождения фронта захвата от тактового входа всей схемы к тактовому входу получателя.
Под тактовым входом всей системы обычно понимается выход глобального клокового буфера или выход PLL, то есть единая точка, из которой тактовый сигнал расходится до всех регистров своего тактового домена. В самом примитивном случае это ножка ПЛИС, к которой подведен тактовый генератор.

Как соотносится момент прибытия данных с фронтом запуска?

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

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

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

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

Слагаемое это время срабатывания регистра (clock-to-output time), которое регистр тратит на то, чтобы увидев фронт на тактовом входе поменять данные на своем выходе. Анализатор считает эту величину равной для всех регистров на кристалле. Эта величина не зависит от пользователя.

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

Момент прибытия клока на получатель рассчитывается проще:

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

Момент ожидания данных определяется как время, за которое данные должны дойти к получателю до наступления времени предустановки на регистре-получателе:

Слагаемое это уже известное нам Setup time, которое считается одинаковым для каждого регистра на кристалле. Это время не зависит от пользователя.

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

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

Теперь раскроем эти слагаемые и немного переставим местами:

Здесь появились новые слагаемые.

Про период понятно, это период тактовой частоты, т.е. время между Launch Edge и Latch Edge.
Слагаемое это растекание клока (clock skew) минимальная величина разброса времени прихода одного фронта клока от тактового входа системы до разные синхронные регистры. Минимальное растекание клока определяется как разница между наименьшей задержкой клока к получателю и наибольшей задержкой клока к источнику . Анализатор не делает разницы в оценке этого времени для разных регистров на кристалле.

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

На рисунке 5 показано как формулу слэка можно представить графически:


Рис. 5. Графическое представление выражения Setup Slack

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

Теперь похожим образом рассчитаем слэк удержания.

Его тоже можно представить выражением, в котором слагаемые поменялись знаками:

Вот только эти слагаемые теперь рассматриваются с другой стороны.

Теперь здесь рассматривается самый быстрый вариант прохода данных и там, где было max стало min.

Момент прибытия фронта клока также рассматривается в ином ключе, как самый поздний из возможных:

Важно отметить, что в случае рассмотрения Hold Slack фронты Launch Edge и Latch Edge это один и тот же фронт, а не два разных фронта, разделенных периодом клока. Регистру-получателю в данной ситуации нужно успеть удержать данные на входе в течение времени удержания от прихода фронта клока. Но данные меняет на его входе этот же фронт, пришедший где-то в другом месте на регистр-источник. Поэтому в анализе слэка удержания разница равна нулю, а не периоду.

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

Слагаемое это уже известное нам Hold time, время удержания. Оно считается одинаковым для каждого регистра на кристалле и не зависит от пользователя.
Слагаемое это Clock Hold Uncertainty, неопределенность времени удержания. Оно несет в общем тот же смысл, что и CSU, да и как правило берётся равным ему.

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

Ура, мы узнали как рассчитываются слэки. Как использовать эти знания?
Давайте посмотрим на выражения слэков еще раз:

Если какие-то слэки проекта стали отрицательными, то поменять их мы можем поменяв их слагаемые.

Мы видим слагаемые, которые не зависят от пользователя, а зависят только от технологии кристалла. Это .
Мы видим слагаемые CSU и CHU, которые анализатор как правило берет равными параметру CU Clock Uncertainty, нестабильность тактовой частоты. Этот параметр вообще говоря невелик, десятки пикосекунд. Он указывается пользователем в файле ограничений. А пользователь его в свою очередь берет из спецификации на тактовый генератор. Считается что клоковый буфер или внутренняя PLL ПЛИС, которые принимают внешний клок от генератора и преобразуют во внутренний клок на тактовый вход системы, сохраняют величину CU той же, что получена от генератора. Если CU не указать, то анализатор выставит ей некоторое значение по умолчанию, например Quartus ставит 20 пс. В общем случае это слагаемое говорит нам о том, что лучше использовать для тактирования высокостабильные генераторы с величиной нестабильности порядка 20-60 пс.

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

И, наконец, слагаемое характеризует по сути эффективность написанного кода. Отсюда следует и основной способ решения проблем со слэками переписать как следует. Большое время появляется у слишком сложных аппаратных конструкции, требующих слишком много комбинационной логики. Если такие сложные конструкции появились у вас в проекте, то классический способ решения проблемы разбить одну сложную r2r передачу на несколько простых, вставив еще 1-2 регистра в последовательность операций. При этом вырастет задержка в тактах на выполнение операции, но зато увеличится быстродействие операции. Например, сложение за один такт нескольких векторов это не очень хорошая идея. Складывать несколько векторов лучше по очереди, с промежуточными суммами. Некоторые сложные конструкции бывает невозможно разбить на конвейер из нескольких простых тогда такую логику нужно переписывать как-нибудь принципиально иначе.

Дополнение

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

Анализатор группирует слагаемые иначе, исходя из своих машинных резонов.
Он оперирует понятиями Clock Setup Relationship (SR) и
Clock Hold Relationship (HR) которые можно перевести как соотношение времени между инициирующим фронтами для предустановки и удержания соответственно.

На рисунке 6 можно увидеть о каких фронтах идет речь:


Рис. 6. Фронты, используемые в расчетах слэков.

Можно сразу преобразовать полученные выражения в более понятный вид:

Наибольшее межрегистровое время (Largest r2r Required) это максимальное время, имеющееся для того, чтобы данные дошли к получателю до начала интервала предустановки:

Самая длинная межрегистровая задержка (longest r2r Delay) это время, необходимое для передачи данных из исходного регистра в регистр назначения по самому длинному пути:

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

Раскрытие слагаемых этой формулы даст нам уже знакомое представление слэка предустановки:

Теперь про слэк удержания. Наименьшее межрегистровое требование (smallest r2r Requirement) это время, необходимое для удержания данных на входе регистра назначения:

Кратчайшая межрегистровая задержка:

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

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

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

Здравствуйте. В данной статье я хочу по возможности максимально просто и понятно рассказать о том, как рассчитываются временные ограничения (timing constraints) на синхронные интерфейсы ПЛИС. Просто не значит коротко, но зато простыми словами, которые вы сможете легко понять. Если вы новичок и перед вами стоит задача описать свой первый SPI, то данная статья должна вам помочь понять для чего нужны ограничения и как их рассчитать.

Введение

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

В предыдущей статье (ссылка) я рассказал о том, что из себя представляет передача данных между двумя регистрами и как рассчитывается выполнение временных соотношений в случае передачи данных внутри ПЛИС, когда оба рассматриваемых регистра, пути прохождения тактовых сигналов и сигналов данных лежат внутри ПЛИС. Из той статьи нужно вынести понимание концепции синхронной логики как сети, сплетенной из множества межрегистровых передач (рис.1), и термина слэк (рис.2).
В этой статье мы рассмотрим случаи передачи данных, в которых один из двух регистров передачи находится вне ПЛИС это регистр внешнего устройства микроконтроллера, АЦП и т.п.


Рис. 1. Схема межрегистровой передачи данных от регистра-источника (source) к регистру-получателю (destination).


Рис. 2. Смысл слэков относительно фронта захвата на входе регистра-получателя.

Общие формулы расчета слэков, выведенные в предыдущей статье:

Пробежимся по терминам.
Слэк (slack) это запас по времени. Он должен быть положительным.
Время предустановки (setup time, ) минимальное время, которое данные должны уже находиться на входе регистра-получателя на момент прихода фронта клока на тактовый вход получателя.
Время удержания (hold time, ) минимальное время, которое данные должны всё ещё держаться на входе получателя после момента прихода фронта клока на тактовый вход получателя.
Время срабатывания регистра (clock-to-output time, ) время от прихода фронта клока на тактовый вход регистра-источника до появления на его выходе новых стабильных данных.
Нестабильность тактовой частоты по предустановке/удержанию (CSU/CHU) мера нестабильности тактового сигнала. В расчетах несет смысл запаса на всякий случай для учтения явлений, вызванных неидеальной периодичностью клока.
это время прохождения сигналом данных пути между регистрами.
это время, за которое фронт тактового сигнала доходит от источника тактового сигнала до тактового входа регистра-источника. А от источника тактового сигнала до регистра-получателя соответственно .
Пути прохождения сигналов проиллюстрированы на рисунке 3.


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

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

Виды анализируемых передач

Давайте проведем классификацию случаев для временного анализа. Анализ проводится отдельно для каждой ножки ПЛИС относительно некоторого клока. В результате анализа оценивается возможность ножки корректно отдать или принять данные. Внешний интерфейс синхронного обмена данными ПЛИС с внешним устройством представляет собой несколько линий, подведенных к ножкам. Из них одна линия это линия клока. Он должен быть общим для регистров на обеих сторонах. Остальные линии, одна или множество, это однонаправленные линии ввода или вывода. То, что для ПЛИС является линией ввода, для внешнего устройства является линией вывода, и наоборот. В данной статье мы рассматриваем только простейшие случаи временного анализа, поэтому не касаемся асинхронных и самосинхронных интерфейсов, а также использования двунаправленных линий ввода-вывода.
Случаи анализа можно классифицировать по направлению данных относительно ПЛИС (Input/Output) и по направлению клока относительно ПЛИС (System/Source Synchronous). Для каждого случая есть два типа анализа (Setup/Hold). Итого, четыре случая для анализа и восемь уравнений, которые нам надо вывести.

Sytem Synchronous Output / Вывод данных, тактированных внутренним клоком ПЛИС

Рассмотрим случай, когда нам нужно отдать что-то наружу на своем клоке (рис.4). Принципиально схема передачи данных не изменилась. Вот только регистры теперь принадлежат двум разным микросхемам, а на пути данных между ними не комбинационная логика, а просто дорожки на плате. И наша задача состоит в том, чтобы адаптировать известные нам формулы слэков к немного иной ситуации.

Рис. 4. Передача данных наружу по собственному клоку ПЛИС.

На рисунке 4 мы видим схему межрегистровой передачи. На ней показаны времена процессов, относящиеся к каждому из регистров, и времена, за которые сигналы проходят пути.
Я задал следующую индексацию: время, относящееся к данным, помечено буквой D. Время, относящееся к клоку, помечено буквой C. Если событие происходит внутри ПЛИС, то его время помечено индексом int, а если во внешнем устройстве, то ext. Время на путь клока от источника клока до выходной клоковой ножки имеет самый длинный индекс Cintout. DataTrace и ClkTrace это времена на проход соответствующих дорожек на печатной плате. Блок CLK символизирует собой некий внутренний источник клока.
Главная черта упомянутых на рисунке величин все они положительные. Все они равны абсолютной длительности каких-либо физических процессов, а значит физически могут быть только положительными величинами. Это важно для дальнейших рассуждений.

Теперь мы максимально подробно рассмотрим анализ слэка предустановки. Глядя на рисунок 4 мы легко соотносим увиденные величины со слагаемыми формул слэков:

Теперь подставим эти равенства в формулу слэка предустановки:

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

Теперь переставим слагаемые местами так, чтобы сгруппировать в скобках слагаемые процессов внутри ПЛИС и процессов внутри внешнего устройства:

Что же мы видим в скобках? Если присмотреться и еще раз вспомнить про то, что все указанные величины больше нуля, то можно сказать, что мы видим выражение некого эквивалентного (со звездочкой) времени срабатывания регистра ПЛИС и эквивалентного времени предустановки регистра внешнего устройства:

Почему бы нам не пользоваться эквивалентными величинами, если производители микросхем уже посчитали их за нас с учетом своих внутренних задержек? Эквивалентные значения на стороне ПЛИС рассчитает компилятор без участия пользователя, а эквивалентные значения внешнего устройства указываются в явном виде в даташите на устройство.
Теперь вглядимся внимательно еще раз в последнее выражение. В нем первые три слагаемых уже известны анализатору, ведь мы уже указали ему рабочую частоту и величину нестабильности. Компилятор произвел трассировку и анализатор знает эквивалентное время срабатывания своего регистра. Значит анализатору известна длительность всех процессов внутри ПЛИС. А вот последние три слагаемых уникальны для каждой ножки и пользователю необходимо самому их посчитать и указать анализатору в виде числа. Что же это за число? Рассмотрев внимательнее три последних слагаемых мы увидим, что их можно интерпретировать как отрицательный максимум некой величины:

И эта величина по смыслу равна задержке всего, что происходит снаружи ПЛИС, относительно всего, что происходит внутри. Ее так и называют выходная задержка, Output Delay.
Подытожим:

Теперь выведем аналогичное уравнение для слэка удержания. Вспомним общее уравнение и подставим в него новые слагаемые:

Раскроем скобки и сразу же сгруппируем слагаемые вокруг каждого из регистров:

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

И последние три слагаемых можно понимать как минимальную внешнюю задержку:

Подытожим:

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

Source Synchronous Output / Вывод данных, тактированных внешним клоком

Теперь перейдем к случаю, когда нам нужно отдать что-то наружу, но по внешнему относительно ПЛИС клоку (рис.5). В общем случае источник клока находится снаружи ПЛИС, в частности он может быть внутри внешнего устройства.

Рис. 5. Передача данных наружу по внешнему клоку.

На рисунке 5 мы видим источник клока снаружи. Соответственно исчезла величина и появилось время прохода клока до внешнего устройства Clk Trace Ext.
Глядя на рисунок 5 соотнесём увиденные величины со слагаемыми общих формул слэков:

С помощью этих выражений раскроем слагаемые в формуле слэка предустановки, сразу сгруппируем их по регистрам и получим эквивалентный вид:

Аналогично разбираем слэк удержания:

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

System Synchronous Input / Ввод данных, тактированных внутренним клоком ПЛИС

Теперь переходим к рассмотрению входных ног синхронного интерфейса. ПЛИС и внешнее устройство на рисунке 6 поменялись местами.

Рис. 6. Прием данных по собственному клоку ПЛИС.

Анализ такой схемы ничуть не сложнее предыдущих.

Раскрываем, группируем

И получаем величину внешней задержки, которую на этот раз уже мы назовем входной:

Теперь слэк удержания:

Source Synchronous Input / Ввод данных, тактированных внешним клоком

Также, по накатанной, смотрим на схему передачи данных и раскрываем слагаемые общей формулы.

Рис. 7. Прием данных по внешнему клоку.

Формула слэка предустановки:

Формула слэка удержания:

Опять же, если источник клока находится внутри внешнего устройства то просто приравниваем ClkTraceExt нулю.

Как пользоваться полученными формулами

Мы получили формулы внешних задержек и можем рассчитать конкретные числа задержек, чтобы вписать их в файл временных ограничений. Эти формулы глобально состоят из двух видов слагаемых это временные характеристики портов внешнего устройства и задержка на дорожках платы.
Характеристики портов обычно находятся в даташитах в разделах под названиями вроде Electrical Characteristics / AC Specifications / Timing Requirements. Порой эти характеристики названы другими именами и придется проявить смекалку, чтобы найти их. Но таблицы с числами как правило сопровождаются временными диаграммами, которые позволят вам идентифицировать нужный параметр.

С дорожками несколько сложнее. Точный расчет задержки на плате вопрос нетривиальный. Задержка зависит от длины, ширины, толщины и углов поворота дорожки, от толщины и материала платы, от расстояния до разных земляных слоев, от близости дорожек друг к другу и от множества иных факторов. Впрочем влияние каждого из этих факторов довольно невелико и на низких частотах интерфейсов, до десятков мегагерц, этими сложностями можно пренебречь. Упрощенный расчет задержки на дорожке выглядит так: скорость распространения волны в фольге считается равной половине скорости света в вакууме. В пересчете это дает примерно 0.007 нс/мм. Погрешность такой оценки нивелируется широким диапазоном оценки задержки. Для максимальной задержки считаем удельную задержку равной 0.010 нс/мм, а для минимальной 0.005 нс/мм.
Есть еще один нюанс. Схемотехники, проектируя печатные платы, стараются протягивать дорожки синхронных интерфейсов примерно одинаковым путем и соблюсти их равные длины. Проверьте длины дорожек данных и клока на своей целевой плате. Скорее всего они почти равны и компонент выражений (DataTrace ClkTrace) на практике можно считать нулевым.
Если на пути данных или клока стоит элемент вносящий задержку ее тоже нужно учесть. Это может быть буфер, инвертор, преобразователь уровня или гальваноразвязка. Такие элементы способны вносить очень большую задержку, десятки наносекунд, поэтому к ним нужно отнестись очень внимательно.

Заключение

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