Алгоритмы на кристалле: быстродействие элементарных схем19.05.2022 00:31

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

Примерное оглавление будущей книги.
Предыдущая статья

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

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

Приятного чтения.

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


Уже после того, как предыдущая часть была мной опубликована, я осознал, что некоторые выбранные мной термины и понятия не вполне удобны. Прийти к этому пониманию мне помогли в том числе и здоровая критика моих читателей, в частности пользователей СВЕТ_ТЬМЫ и karambaso. Я считаю, будет правильным внести небольшие правки прямо сейчас, тем более, что эти статьи являются черновиком и их предназначение как раз и состоит в том, чтобы в процессе своего написания улучшаться и становиться удобнее для восприятия читателем.

Логическая схема и диаграмма значений


Первая правка будет касаться самого понятия логической схемы. Изначально в понятие схемы была включена и ее конструкция и то, какие именно значения ее компоненты (шины, порты и блоки) принимают на каждом такте. Ожидаемо, в какой-то момент повествования пришлось говорить о конструкции отдельно от значений. Как назвать конструкцию? Скелетом или остовом схемы? Хорошо, а если есть похожая конструкция из логических блоков портов и шин, но элементам которой нельзя приписать на каждый такт значения таким образом, чтобы они удовлетворяли аксиомам схемы, тогда вся эта конструкция уже не скелет?

В общем поломав немного голову, я решил поступить так.

Впредь под термином логическая схема мы будем понимать любое множество правильно соединенных между собой портов, логических блоков и шин. Под правильностью соединения подразумевается соответствие всей конструкции аксиомам P1 — P3, B1 — B3 и до тех пор, пока мы говорим об элементарных схемах — аксиомам C*. Отдельно мы будем выделять логические схемы, удовлетворяющие конструкционной аксиоме A* и называть последние схемами без циклов функциональной зависимости, или коротко: функционально ациклическими схемами.

В свою очередь логическую схему (в ее новом понимании), вместе с приписанными на каждый такт значениями ее портам, шинам, и состояниям регистров, мы будем называть допустимой диаграммой значений, если и только если совокупность этих значений удовлетворяет всем оставшимся аксиомам, а именно: T, P4-P7, S1, S2, B4, B5, E1-E11. Таким образом выходит, что старое понятие логической схемы мы, по сути, приравняли новому понятию допустимой диаграммы значений.

С изменением названий терминов поменяется звучание теоремы о функциональной ацикличности. Новая ее формулировка ставится проще и звучит теперь так:

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

Пояснения, касающиеся понятия внешних входных и внешних выходных портов на схеме


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

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

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

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

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

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

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

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

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

Замена термина «фронт распространения сигнала» на «фронт распространения данных»


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

Далее. Немного изменен смысл и алгоритм построения фронтов распространения данных. Теперь каждый порт входа, если тот единственный порт выхода, с которым он соединен общей шиной, принадлежит фронту $F_{i-1}$, то сам этот порт входа будет включен во фронт $F_i$. Из-за нового этого упростились определения и доказанные результаты (доказательство теоремы о функциональной ацикличности теперь можно понять не запутавшись в нем). Все изменения уже внесены в текст.

Статическая дисциплина


Изменения там, где их нет.

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

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

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

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

Гидродинамическая аналогия


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

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

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

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

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

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

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

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

Работу входных портов можно сравнить с работой механического поплавкового уровнемера с двумя главными значениями: «канал полон» и » канал пуст». Если напряжения в той точке провода, где расположен входной порт, выше некоторой отметки a, то этот порт приобретает логическое значение »1», если же уровень напряжения в этой точке падает ниже, чем некоторая отметка b < a, то логическим значением будет "0”. Уровни напряжения, которые выше a, либо ниже b, условимся называть регулярными. Логическое значения порта входа в моменты, кода уровень напряжения находится где-то между b и a, считается не определенным.

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

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

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


(рисунок, объясняющий, почему в предыдущих предложениях так много «вообще говоря»).

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

Переходные процессы, происходящие в продолжение одного физического такта


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

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

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

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

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

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

И так, претендентами на роль затравок изменений напряжений в схеме остаются только внешние выходные порты и выходные порты регистров, другими словами, те порты, из них которых по определению состоит нулевой фронт распространения данных $F_0$. Следовательно, первыми претерпят изменения уровни напряжения в тех шинах, началом которых служат порты из $F_0$.

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

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

Пусть $p_{in}$ — какой-нибудь выходной порт, относящийся к фронту $F_i, i>0$» />. В таком случае тот выходной порт <img src=, с которым общей шиной соединен $p_{in}$, обязательно входит во фронт $F_{i-1}$ (смотрите алгоритм построения фронтов). Следовательно, значение $p_{in}$, стабилизируется никак не раньше, чем перестанет меняться значение, то есть, режим, в котором работает порт $p'_{out}$.

Пусть теперь $p_{out}$ — это какой-нибудь выходной порт, относящийся к фронту $F_i, i>0$» />. Из правила построения фронта <img src= следует, что блок, которому принадлежит $p$, обязательно является функциональным, более того: среди входных портов этого блока есть по крайней мере один такой, который соединен общей шиной с некоторым выходным портом $p'_{out}$, принадлежащим фронту$F_{i-1}$. Поскольку логика работы блоков остается для нас тайной, то мы не сможем гарантировать, что значение порта $p$на этом такте больше не изменится, раньше, чем мы сможем гарантировать то же самое для порта $p'_{out}$.

Объединяя две последних цепочки рассуждений в одну, получаем следующее утверждение:
Если логика работы блоков остается для нас тайной, то мы не сможем гарантировать, что значения всех портов фронта $F_i$ пришли к стабильным значениям, раньше, чем мы сможем гарантировать, что стабилизировались значения во всех шинах, находящихся в соединении с выходными портами фронта$F_{i-1}$.

Латентность логической схемы


Главный вопрос и декомпозиция проблемы


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

Как выбор того или иного микроархитектурного решения влияет на максимально возможную тактовую частоту схемы, изготовленной в соответствии с этим решением?

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

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

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

Упрощенная модель релаксации


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

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

Далее, пусть для каждого функционального блока $B$ известно то максимальное время $∆t_B$, которое может пройти между моментом, когда последний раз менялись и с тех пор являются определёнными значений всех его входных портов, и моментом, когда после этого перестанет меняться и станет определенным значения каждого его выходного порта. Величину этого времени назовем задержкой функционального блока. Будем считать, что блоки, относящиеся к одному и тому же элементарному типу, имеют одинаковое время задержки.
Регистры отличаются от функциональных блоков тем, что значения, принимаемые на текущем такте их портами входа, никак не влияют на значения, которые примет в этот такт их порт выхода, однако первые должны определить то, каково будет внутреннее состояние регистра в следующий такт времени. В свою очередь стабильное значение порта выхода регистра на каждом такте должно совпадать со значением внутреннего состояния, в котором в тот момент находится регистр. Достижение равенства в обоих случаях может требовать времени, поэтому для каждого типа регистров определим задержку стабилизации состояния и задержку стабилизации данных.

Задержка стабилизации состояния регистра $R$, $∆ts_R$— это время которое должно пройти с момента, когда последний раз изменились и с тех пор остаются определенными значения всех входных портов регистра, до начала следующего такта, чтобы можно было гарантировать, что смена внутреннего состояния регистра между этими тактами произойдет правильно. Величина задержки стабилизации состояния $∆ts_R$ одинакова для всех регистров одного типа.

Задержка стабилизации данных $∆td_R$ равна времени, которое должно пройти с момента начала следующего такта, чтобы можно было гарантировать, что значение выходного порта регистра R правильно соответствует его внутреннему состоянию. Величина задержки стабилизации данных $∆td_R$ одинакова для всех регистров одного типа.

Пусть имеется некоторая элементарная логическая схема без циклов функционального влияния. Будем отсчитывать время с того момента $t_0$ очередного такта ее работы, когда значения всех внешних выходных портов схемы только что стали определенными и до конца такта уже не изменятся. Оценим сверху время, необходимое на то, чтобы каждый порт схемы успел принять окончательные для этого такта значения. Оценку $t(P)$ этого времени для конкретного порта $P$ назовем оценкой запаздывания (стабилизации) $P$.

Каждому внешнему выходному порту схемы по условию для этого понадобится дополнительно 0 единиц времени.

У блоков констант нет портов входа, поэтому даже на нулевом такте значение выходных портов блока-константы $C$ станет определенным и стабильным спустя не более, чем время задержки $∆t_C$.

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

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

Рассмотрим на схеме любой функциональный блок $B$. Пусть $p_1,…p_n$ — все его входные порты. Предположим, что для каждого входного порта $p_i$ нам уже известна оценка его запаздывания ${t(p)}_i$), то есть время, когда значение этого порта гарантированно станет определенным и стабильным. В таком случае, мы можем утверждать, что в момент времени $max⁡(t(p)_1),…t(p)_n))+∆t_B$ значения всех выходных портов этого блока также гарантированно будут иметь определенные и стабильные значения.

Примем число $max⁡(t(p)_1),…t(p)_n))+∆t_B$ за оценку запаздывания каждого из выходных портов блока B, а также за оценку запаздывания всех тех входных портов схемы, с которыми любой их выходных портов блока B связан общей шиной. Сможем ли мы, систематически повторяя только что использованный прием, приписать оценку запаздывания каждому порту схемы?

Будем рассуждать по индукции. Моменты, когда каждый порт фронта $F_0$ гарантированно будет иметь стабильное определенное значение, мы уже оценили.

Каждый входной порт, принадлежащий фронту $F_i, i>0$» /> примет определенное и окончательное для этого такта значение в тот же самый момент, что и единственный выходной порт фронта <img src=, с которым он соединен общей шиной.

Предположим, что для всех портов, принадлежащих фронтам $F_0…F_{i-1}$, моменты времени, когда их значения гарантированно окажутся определенными и стабильными, уже оценены. Согласно алгоритму построения фронта $F_i$ каждый включенный в него входной порт соединен общей шиной с каким-либо выходным портом фронта $F_{i-1}$. В таком случае мы автоматически получаем оценку запаздывания и для каждый входного порта из фронта$F_i$.

Пусть теперь $p’$ — какой-нибудь выходной порт фронта $F_i, i>0$» />. В таком случае <img src= принадлежит некоторому функциональному блоку B, каждый входной порт $p_1,…p_n$ которого содержится в одном из фронтов © Habrahabr.ru