Асинхронная обработка данных (асинхронные вычисления). Анализ поведения

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

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

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

Раздел 1. Кодирование событиями

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

Предположим переключение сигнала X1 из 0 в 1 интерпретировано значением «1» переменной x. Если переключение сигнала X1 из 1 в 0 будет интерпретировано каким-либо значением какой-либо переменной, то тем самым будет создана определенная очередность в смене вышеуказанных значений, что заранее гарантировать невозможно. Поэтому переключение сигнала X1 из 1 в 0 не может быть интерпретировано каким-либо значением какой-либо переменной. По аналогии такое событие назовем спейсер. В дальнейшем будем считать, что спейсер это переключение из 1 в 0. Хотя, при желании, даже для разных значений одной переменной спейсер может быть выбран произвольно. Такое кодирование, напоминающее традиционное «1 из N», позволяет одинаково легко оперировать данными в двоичной, троичной, в любой произвольной системе счисления. Более того, значениями могут быть предметы, явления, действия (например команды операционной системы). Таким образом могут быть также реализованы схемы управления.

Для того, чтобы оценить преимущества кодирования событиями, обратимся к работе К. Фанта и С. Брандта «NULL Convention Logic». В ее основание положено утверждение, что булева логика не представляет собой символически законченную логическую систему, поскольку она не включает в себя условие завершения выполнения функции. И в качестве решения этой проблемы булева логика дополняется третьим и даже четвертым значениями (соответственно NULL и INTERMEDIATE). Справедливость данного утверждения сомнений не вызывает. Действительно, при кодировании данных состояниями схема без дополнительной информации не может определить: то ли данные обработаны и их обрабатывать не надо, то ли данные не обработаны и их нужно обработать.

Однако, кодирование данных событиями устраняет это противоречие без дополнения булевой логики новыми значениями. Действительно, асинхронный дизайн оперирует исключительно только полумодулярными схемами (или точнее схемами, удовлетворяющими свойству Output Persistency (OP) (J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Yakovlev «Logic Synthesis for Asynchronous Controllers and Interfaces»). Это свойство — аналог свойства полумодулярности, расширенного на не автономные схемы. Если кратко, в OP схемах возбуждение может быть снято (без переключения) только лишь для входного сигнала и посредством переключения только лишь другого входного сигнала. Для таких схем вызванное очередным событием возбуждение логического элемента не может быть снято иначе, чем посредством переключения данного логического элемента. Таким образом схема без дополнительной информации всегда знает, что делать с данными (которые закодированы событиями). Если возбуждений соответствующих элементов нет, значит данные уже обработаны. Если возбуждения есть — данные предстоит обработать. То есть событие одновременно является и передачей информации, и условием завершения выполнения функции. Сигнал, с помощью которого закодирована переменная, одновременно является и информационным, и управляющим.

Различие интерфейса передачи данных для разных способов кодирования информации изображено на рис. 1. Помимо ускорения передачи данных (за счет устранения переключений сигнала req), кодирование событиями привносит свою специфику в сам процесс передачи данных. При кодировании состояниями передача данных носит пассивный характер: любой приемник, подсоединенный к источнику, может считать данные в любой момент. При кодировании событиями передача данных — активная: источник сам отправляет данные, причем только тому приемнику, которому они предназначены в данный момент. Следует заметить, что ускоренный обмен данными (рис. 1б) используется и в NCL (в частности в пайплайнах).

Раздел 2. Хэндшейк

Отказ от использования заранее предопределенной схемной архитектуры естественно приводит к модульно-иерархическому принципу построения схем. Модуль представляет собой законченную полноценную схему. При этом не предполагается какого-либо внешнего межмодульного управления. Модули соединяются друг с другом проводами через соответствующие входные-выходные порты. Таким образом, модуль решает две задачи: собственно вычисление функции и взаимодействие с другими модулями. Естественный механизм межмодульного взаимодействия — хэндшейк. Суть хэндшейка заключается в том, что модуль-источник, после переключения выходного сигнала, удерживает его в неизменном состоянии до тех пор, пока модуль-приемник переключением своего выходного сигнала не разрешит переключить первый. В свою очередь, модуль-приемник также, после переключения своего выходного сигнала, удерживает его в неизменном состоянии до разрешения от модуля-источника. Именно механизм хэндшейка гарантирует соблюдение свойства OP для обоих взаимодействующих схем. Межмодульный интерфейс передачи данных изображен на рис. 1б, а соответствующий протокол (поведение) хэндшейка показан на рис. 2.

Раздел 3. Пример синтеза простой функции

После того как были определены основные компоненты, из которых должен состоять модуль, попробуем реализовать булевскую функцию тождество (y=x). Сначала составим описание исходного задания. На рис. 3 изображены компоненты исходного поведения и интерфейс модуля. Поведение модуля со сведенными в единое целое компонентами показано на рис. 4. Как видно это поведение не является безопасным. Но эта проблема может быть решена с помощью ограничения параллелизма (рис. 5). Полученное поведение безопасно, но содержит неразрешенные CSC конфликты. CSC конфликт это ситуация, когда логическая функция сигнала (выходного или внутреннего) принимает разные значения на одинаковых состояниях. Обычный способ разрешения CSC конфликтов — добавление новых сигналов. В данном случае требуется добавление минимум 12 новых событий (поведение представлено на рис. 6). Логические функции сигналов для данного поведения следующие:

Y1=f1*h1
Y0=f0*h0
Xack=!(g1*h1+g0*h0)
f1=Yack*f1+g1*!h1
f0=Yack*f0+g0*!h0
g1=X1*g1+!h1
g0=X0*g0+!h0
h1=!X1+!Yack+f0+g1*h1+f1
h0=!X0+!Yack+f1+g0*h0+f0.









Признать такое решение удовлетворительным нельзя. К тому же для избавления от входных инверторов и от многовходовых элементов потребуется добавление еще большего количества новых сигналов. В данном случае единственный путь для оптимизации это корректировка исходного задания за счет ограничения параллелизма. Начнем с минимальных изменений. В поведении, изображенном на рис. 5, события Y1+ и Y0+ сделаем последовательными относительно соответствующих событий Xack- (рис. 7). События Y1+, Y0+, Xack- являются выходными, так что это не нарушит логику поведения. В полученном поведении также содержатся неразрешенные CSC конфликты. Для их разрешения требуется минимум 4 дополнительных сигнала. Скорректированное поведение без CSC конфликтов изображено на рис. 8. Логические функции сигналов для этого поведения следующие:

Y1=(f1+Y1)*g1
Y0=(f0+Y0)*g0
Xack=!((f1+f0)*(Y1+!g1)*(Y0+!g0))
f1=X1*(g1+f1)
f0=X0*(g0+f0)
g1=Yack*!g0*(X1+g1)*(!f1+g1)
g0=Yack*!g1*(X0+g0)*(!f0+g0).





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

Y1=Yack*Y1+f1
Y0=Yack*Y0+f0
Xack=f1*Y1+f0*Y0
f1=X1*(Yack+f1)*(!Y1+f1)*!Y0
f0=X0*(Yack+f0)*(!Y0+f0)*!Y1.





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

Y1=f1*Y1+X1*f1*Yack
Y0=f0*Y0+X0*f0*Yack
Xack=!Y1*f1*!Y0*f0
f1=(!X1+f1)*(!Y1+Yack)
f0=(!X0+f0)*(!Y0+Yack).





И наконец последний вариант синхронизации фазы спейсера представлен на рис. 13. В данном случае поведение не содержит CSC конфликтов и логические функции сигналов выглядят так:

Y1=X1*Y1+Yack*Y1+X1*Yack (C-элемент)
Y0=X0*Y0+Yack*Y0+X0*Yack (C-элемент)
Xack=!(Y1+Y0).



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

а) Все полученные схемы (поведения) обладают свойством OP, поскольку свободный выбор в них определяется исключительно входными сигналами.

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

в) Лучшим решением (и по площади, и по быстродействию) является схема (поведение), представленная на рис. 13 (известна как пайплайн Д. Маллера). Некоторые заведомо проигрышные варианты ограничения параллелизма здесь не представлены.

г) Поведения модулей, реализующих более сложные функции, принципиально не отличаются от исследованных поведений. К двум альтернативным ветвям добавляются другие подобные альтернативные ветви. Внутри каждой альтернативной ветви к двум параллельным ветвям добавляются другие подобные параллельные ветви. Поэтому все выше сделанные выводы (пункты а, б, в) распространяются и на модули, реализующие более сложные функции. Таким образом оптимальное решение следует искать на пути максимального ограничения параллелизма и использования пороговых элементов. В общем виде поведение модуля, реализующего функцию f= F(x, y, ..., z), показано на рис. 14. События X1+, X0+, Y1+, Y0+, ..., Z1+, Z0+ интерпретированы соответствующими значениями аргументов функции F. Aack — сигнал ответа для модулей-источников. События F1+, F0+ интерпретированы соответствующими значениями функции F. Fack — сигнал ответа от модуля-приемника. cn, ..., c1, c0 — дополнительные сигналы. Логические функции сигналов следующие:

F0, F1 — суммы соответствующих сигналов из списка c0, c1, ..., cn;
Aack — отрицание суммы сигналов c0, c1, ..., cn;
c0, c1, ..., cn — C-элементы, отлавливающие соответствующие комбинации значений аргументов (X0+, Y0+, ..., Z0+ к примеру), а также событие Fack+.

Такая схема напоминает комбинационную схему DIMS-архитектуры NCL. Отличие состоит в наличии встроенных сигналов ответа (Aack, Fack). Опираясь на опыт NCL схему можно оптимизировать, заменяя по возможности C-элементы пороговыми элементами. Например 2 трехвходовых C-элемента, различающиеся одним входом, можно заменить одним четырехвходовым пороговым элементом.

д) Если хотя бы один аргумент функции принимает более, чем одно значение, то модуль, реализующий такую функцию, обязательно содержит провод, задержка которого может влиять на правильность работы схемы. Такими чувствительными к задержке проводами могут быть только провода, соединяющие какой-либо вход модуля с входом какого-либо C-элемента. Если функция зависит хотя бы от двух аргументов, принимающих более чем одно значение, то все подобные провода (соединяющие вход модуля с входом C-элемента) являются чувствительными к задержке. Такая ситуация является следствием того, что переключение входа C-элемента из 0 в 1 и обратно в 0 может не вызывать переключения выхода C-элемента (в данном случае переключается выход другого C-элемента). В результате этого не индицированная «1» может быть воспринята C-элементом при подаче следующего набора входных значений, что может привести к ошибке. Для правильной работы модуля необходимо, чтобы сброс не индицированной «1» (переключение в 0) был воспринят C-элементом раньше, чем «1» следующего набора входных данных. То есть, к примеру (рис. 14), задержка чувствительного провода (X0, c0) (при передаче «0») должна быть меньше суммарной задержки пути (X0- -> c1- -> Aack+ -> Z0+) и задержки провода (Z0, c0) (при передаче «1»). Подобная ситуация является аналогом wire orphan в NCL. Все остальные провода модуля, а также межмодульные провода к задержке не чувствительны. Нечувствительность к задержкам межмодульных проводов обусловлена тем, что модуль ожидает параллельного прихода входных событий, не разделенных выходными событиями (параллельный интерфейс).

Раздел 4. Взаимодействие модулей друг с другом

Наличие в составе модуля встроенных сигналов ответа компенсируется тем, что такой модуль не нуждается во внешних схемах управления и регистрах. Регистр обычно состоит из защелок и многовходового C-элемента. Защелки используются для сохранения данных. Но у вычисляющей схемы нет задачи хранения информации. Она лишь должна преобразовать информацию и передать ее дальше. Другое дело, что вновь выставленные данные должны удерживаться в неизменном состоянии покуда не будут восприняты модулем-приемником. А с этой задачей справляется межмодульный хэндшейк (рис. 2): сигнал ответа ack играет роль своеобразной памяти. Многовходовый C-элемент традиционно используется для синхронизации разрядов регистра и индикации межразрядных переносов (как при сложении). При модульном устройстве схемы межразрядный перенос организуется с помощью все того же хэндшейка (об этом речь пойдет ниже). Поразрядная синхронизация же носит искусственный характер, это скорее дань синхронному дизайну. Если уж делать схему асинхронной, то надо до конца использовать преимущества такого подхода. Разряды должны жить независимо друг от друга. Синхронизация должна происходить естественным образом, например для соседних разрядов, как при переносе при сложении, или для всех разрядов при выводе данных на внешний носитель.

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

Рассмотрим два модуля M1 и M2. Так как поведения модулей, реализующих функции произвольной сложности, подобны друг другу, для ясности ограничимся рассмотрением модулей, реализующих функции от одного аргумента в однозначной системе счисления. Интерфейс и поведение обоих модулей изображены на рис. 15. X1, X2 — значения аргументов. X1ack, X2ack — ответы на значения аргументов. Y1, Y2 — значения функций. Y1ack, Y2ack — ответы на значения функций. Эти два модуля могут быть соединены 2 способами: передавать данные в одном направлении или в обоих (рис. 16).





Рассмотрим первый вариант соединения модулей (рис. 16а). Исследуем взаимное влияние модулей друг на друга или, точнее, межмодульный интерфейс (сигналы Y1, X2, Y1ack, X2ack). Поведение модуля M1 содержит в том числе и ожидание модуля M1 по отношению к поведению модуля M2. Таким ожиданием является проекция (назовем ее P1) поведения модуля M1 на сигналы межмодульного интерфейса (Y1 и Y1ack). В свою очередь модуль M2 реализует протокол межмодульного интерфейса, которым является проекция (назовем ее P2) поведения модуля M2 на сигналы межмодульного интерфейса (X2ack и X2). Если поведения P1 и P2 идентичны (то есть генерируют одни и те же последовательности событий) с точностью до имен сигналов, то этого достаточно для корректного (в соответствии с описанием) функционирования модуля M1. Оговорка «с точностью до имен сигналов» означает, что имена одного и того же провода (сигнала), соединяющего модули, могут различаться в описаниях этих модулей. Из аналогичных рассуждений в отношении модуля M2 вытекает, что для корректного совместного функционирования модулей M1 и M2 достаточно идентичности (с точностью до имен сигналов) проекций их поведений (P1 и P2) на сигналы интерфейса. При этом всегда следует помнить о том, что для сохранения корректности интерфейса всякая причинная связь проекции, в которой следствием является входное событие, должна иметь место и в исходном поведении модуля. То есть проекция, как и добавление новых сигналов, не должна изменять список непосредственных причин для любого входного события.

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

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

Замечание. Редукция параллелизма не является средством синтеза схем. Она — средство анализа на совместимость модулей.

Таким образом, для корректного совместного функционирования модулей M1 и M2 достаточно того, чтобы существовали какие-то поведения P1' и P2' (проекции на сигналы межмодульного интерфейса, к которым применена редукция параллелизма), идентичные друг другу.

Проекции поведений модулей M1 и M2 на сигналы интерфейса показаны на рис. 17. Как видно P1 и P2 идентичны, достаточно в P2 (рис. 17б) заменить имена, соответствующие одному проводу: X2 на Y1, X2ack на Y1ack. Таким образом, корректное совместное функционирование любых двух модулей, соединенных так, как показано на рис. 16а, гарантируется стандартным протоколом межмодульного хэндшейка: после переключения из 0 в 1 сигнала, кодирующего данные (в данном примере Y1, X2), сигнал ответа (Y1ack, X2ack) должен переключаться из 1 в 0.



Перейдем ко второму типу соединения модулей (рис. 16б). Проекциями поведений модулей на сигналы интерфейса в данном случае будут сами эти поведения. На рис. 18 изображены эти проекции, причем в проекции поведения модуля M2 имена сигналов заменены на соответствующие имена сигналов модуля M1 (X2 на Y1, Y2 на X1, Y2ack на X1ack, X2ack на Y1ack). Для обеих проекций достижимы по 12 состояний. Из них только 10 совпадают для обеих проекций. Только эти 10 состояний, приведенных в таб. 1, могут быть выбраны в качестве начальной маркировки. И для всякой такой начальной маркировки оба модуля останавливаются в ожидании входных событий. Например, для приведенной на рис. 18 маркировки (строка 4 в таб. 1) модуль M1 ожидает входного события X1+, а модуль M2 ожидает входного события Y1+. В то же время оба модуля сами никаких событий не генерируют. Очевидно, что при таком соединении модули функционировать корректно не могут. Таким образом при соединении двух модулей передача данных может происходить только в одном направлении.





В связи с последним установленным фактом необходимо выяснить: можно ли из модулей конструировать замкнутые структуры в виде кольца? Рассмотрим три модуля M1, M2, M3, соединенные как показано на рис. 19. Их поведения изображены на рис. 20. Для удобства сразу же унифицируем имена сигналов (проводов), чьи имена различаются в описаниях поведений для различных модулей (рис. 21). При приведенной начальной маркировке модулей схема не работоспособна: все три модуля ожидают переключения входного сигнала. На рис. 22 приведены поведения модулей с начальными маркировками, при которых схема может быть работоспособной.









Теперь выясним: корректно ли функционируют эти три модуля совместно? Рассмотрим сначала модуль M1. Модули M2 и M3 для него являются внешней средой (ее поведение показано на рис. 23). Корректность функционирования модуля M1 совместно с его внешней средой выясним путем сравнения проекций их поведений на сигналы интерфейса (Y3, Y3ack, Y1, Y1ack). Эти проекции представлены на рис. 24. Внешняя среда ожидает параллельного наступления входных событий Y1+ и Y3ack- (рис.24б), но модуль M1 генерирует эти события последовательно. Поэтому в проекцию поведения внешней среды можно ввести дополнительную причинную связь (редукция параллелизма) Y1+ -> Y3ack- (рис. 25а). Точно также внешняя среда ожидает параллельного наступления входных событий Y1- и Y3ack+ (рис.25а), но модуль M1 генерирует эти события последовательно. Поэтому вводим в проекцию поведения внешней среды еще одну дополнительную причинную связь Y1- -> Y3ack+ (рис. 25б). В свою очередь модуль M1 ожидает параллельного наступления входных событий Y3- и Y1ack-, а также Y3+ и Y1ack+, но внешняя среда генерирует их последовательно. Поэтому редуцируем параллелизм в проекции поведения модуля M1 (рис. 24а), добавив дополнительные причинные связи: Y3 -> Y1ack- и Y3+ -> Y1ack+. Результат представлен на рис. 25в. Как видно редуцированные проекции поведений модуля M1 и его внешней среды одинаковы. Следовательно модуль M1 и его внешняя среда совместно функционируют корректно.







Аналогичные рассуждения относительно модулей M2 и M3 приводят к выводу, что три модуля, соединенные как показано на рис. 19, функционируют корректно. Не трудно также убедиться, что четыре и более модулей, соединенные в замкнутую структуру, будут функционировать корректно. Необходимо только для трех из этих модулей установить не стандартную начальную маркировку, а такую, которая показана на рис. 22. Вообще, оптимальное количество модулей, из которых состоит замкнутая структура, кратно 4. Такое количество модулей позволяет избегать неоправданных простоев. К слову, замкнутую структуру можно было бы составить из двух модулей, если бы они реализовывали поведения, подобные изображенному на рис. 7 (то есть без синхронизации в фазе спейсера).

Теперь сформулируем правила соединения модулей.

1. Модуль не может передавать данные сам себе.
2. При соединении двух модулей данные могут передаваться только в одном направлении. То же самое касается соединения модуля с внешней средой.
3. Входной порт данных может быть соединен с выходным портом данных только одного модуля. Выходной порт данных может быть соединен с входными портами данных нескольких модулей.
4. Если несколько модулей (более двух) образуют замкнутую структуру, то трое из этих модулей должны иметь не стандартную начальную маркировку, а подобную, изображенной на рис. 22. Соответственно при соединении таких модулей с не стандартной начальной маркировкой с иными модулями надо обращать внимание на соответствие начальных маркировок.
5. Если модуль отправляет данные в адрес нескольких иных модулей, то он должен дожидаться сигнала ответа от всех адресатов (протокол хэндшейка показан на рис. 26). Если модуль получает данные от нескольких модулей (количество аргументов функции более одного), ответного сигнала достаточно одного.

Осталось убедиться, что построенная таким образом схема будет функционировать корректно. Для этого достаточно доказать, что любой произвольный модуль схемы будет функционировать корректно совместно со своей внешней средой, которую составляют все иные модули схемы. Рассмотрим такой произвольный модуль (рис. 27). i — количество аргументов функции, реализуемой модулем M. j — количество модулей, которым отправляется значение функции, реализуемой модулем M. Множество модулей {K1, ..., Ki} не пересекается с множеством {L1, ..., Lj}. Для простоты не будем рассматривать соединения модуля M с внешней средой схемы, поскольку такое соединение может быть смоделировано соединением с каким-то модулем. Проекция поведения модуля M на сигналы интерфейса показана на рис. 28 (для простоты примем, что начальная маркировка — стандартная). На рис. 29 показаны проекции поведений модулей, присоединенных к модулю M, на сигналы интерфейса модуля M. Если бы модули K1, ..., Ki, L1, ..., Lj не были связаны между собой ни на прямую, ни через иные модули (исключая модуль M), то проекция поведения внешней среды модуля M на сигналы интерфейса выглядела бы так, как изображено на рис. 30. Как видно поведение состоит из двух не связанных (параллельных) частей. Но редукция параллелизма путем добавления в проекцию поведения внешней среды дополнительных причинных связей, показанных на рис. 31, приводит к тому, что полученное поведение становится идентичным проекции поведения модуля M (рис. 28).











Теперь исследуем, как на проекцию поведения внешней среды повлияют соединения модулей K1, ..., Ki, L1, ..., Lj друг с другом и с иными модулями. Для начала рассмотрим поведение произвольного модуля. Оно состоит из трех частей. Один или более входных хэндшейков, выходной хэндшейк, причинные связи между входными хэндшейками и выходным хэндшейком. Хэндшейк это всегда последовательность событий: данные (D), ответ на данные (AD), спейсер (S), ответ на спейсер (AS). Причинные связи между входными и выходным хэндшейками это всегда две пары: Din -> Dout -> ADin, Sin -> Sout -> ASin (рис. 32). Суффиксы в именах in и out обозначают принадлежность события к входному или выходному хэндшейкам модуля соответственно. Соединение двух модулей с точки зрения поведения это слияние выходного хэндшейка первого модуля с одним из входных хэндшейков второго модуля в один общий хэндшейк. Таким образом, поведение всей схемы это множество хэндшейков, соединенных причинными связями, как это показано на рис. 32.



Рассмотрим два произвольных хэндшейка схемы. В отношении их можно предположить только две возможности. Либо между ними существует путь данных, как это показано на рис. 33. Либо такого пути нет. На уровне схемы путь данных это ряд последовательно соединенных модулей, где данные передаются от предыдущего модуля к последующему. Очевидно, если между двумя хэндшейками не существует пути данных, то между событиями этих хэндшейков нет причинных связей при любой проекции. Теперь определим причинные связи между событиями двух хэндшейков при проекции на них, если путь данных между этими хэндшейками существует. Снова обратимся к рис. 33. Сделаем проекцию на хэндшейки in и out. Но сделаем ее поэтапно: сначала исключим хэндшейк 1, а затем хэндшейк 2. Результаты такой поэтапной проекции показаны на рис. 34. Вывод из полученных результатов следующий. Вид причинных связей между событиями хэндшейков, на которые сделана проекция, зависит от длины пути данных между этими хэндшейками. Если путь данных состоит из четного количества событий, то вид причинных связей такой, как показано на рис. 34б. Если путь данных состоит из нечетного количества событий, то вид причинных связей такой, как показано на рис. 35.







Теперь вернемся к проекции поведения внешней среды модуля M (модуль M изображен на рис. 27) на сигналы интерфейса модуля M. Основания для редукции параллелизма (причинные связи в проекции поведения модуля M) сохранятся при любом окружении модуля M. Поэтому удобнее рассматривать проекцию поведения внешней среды уже с редуцированным параллелизмом (рис. 28). Как выяснено выше любое усложнение окружения модуля M (добавление новых модулей, установление новых связей между модулями) приведет только к дополнению проекции поведения внешней среды причинными связями между событиями хэндшейков так, как это показано на рис. 34б и рис. 35. Проекция поведения внешней среды состоит из i+1 хэндшейка: i входных хэндшейков модуля M и один выходной хэндшейк модуля M. Не трудно убедиться, что любое усложнение окружения модуля M приведет только к дополнению проекции поведения внешней среды новыми причинными связями между событиями A1s+, ..., Ais+, а также соответствующими причинными связями между событиями A1s-, ..., Ais-, то есть к ограничению параллелизма. Так как сигналы A1s, ..., Ais для модуля M входные, к проекции поведения модуля M можно применить соответствующую редукцию параллелизма. В результате получим идентичные редуцированные проекции поведений модуля M и его внешней среды. Следовательно произвольный модуль будет корректно функционировать вместе со своей произвольной внешней средой. Таким образом любая схема, синтезированная с учетом пяти выше приведенных правил, будет функционировать корректно.

Раздел 5. Расширение функциональных возможностей модуля

Собственно сам метод синтеза (как он представлен на данный момент), никаких сложностей не вызывает. Достаточно составить таблицу истинности для реализуемой функции и по ней определить логические функции элементов синтезируемого модуля. Для примера синтезируем разряд сумматора. Входными данными для него являются: A и B — значения соответствующих разрядов операндов, Cin — перенос из младшего разряда суммы. Выходные данные: S — сумма, Cout — перенос в старший разряд суммы. Поскольку реализовать предстоит две функции, и синтезировать необходимо два модуля. Интерфейсы обоих модулей представлены на рис. 36. Таблица истинности для обеих реализуемых функций представлена в таб. 2. В соответствии с таблицей истинности составляем логические функции элементов. Для модуля CARRY:

f0=C-element(A0,B0,C0in,AckCoutS,AckCoutC)
f1=C-element(A0,B0,C1in,AckCoutS,AckCoutC)
f2=C-element(A0,B1,C0in,AckCoutS,AckCoutC)
f3=C-element(A0,B1,C1in,AckCoutS,AckCoutC)
f4=C-element(A1,B0,C0in,AckCoutS,AckCoutC)
f5=C-element(A1,B0,C1in,AckCoutS,AckCoutC)
f6=C-element(A1,B1,C0in,AckCoutS,AckCoutC)
f7=C-element(A1,B1,C1in,AckCoutS,AckCoutC)
C0out=AND(f0,f1,f2,f4)
C1out=AND(f3,f5,f6,f7)
AckMC=NAND(C0out,C1out).

Для модуля SUM:

g0=C-element(A0,B0,C0in,AckS)
g1=C-element(A0,B0,C1in,AckS)
g2=C-element(A0,B1,C0in,AckS)
g3=C-element(A0,B1,C1in,AckS)
g4=C-element(A1,B0,C0in,AckS)
g5=C-element(A1,B0,C1in,AckS)
g6=C-element(A1,B1,C0in,AckS)
g7=C-element(A1,B1,C1in,AckS)
S0=AND(g0,g3,g5,g6)
S1=AND(g1,g2,g4,g7)
AckMS=NAND(S0,S1).





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

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



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



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

Рассмотрим применение вышеизложенных трех принципов на примере синтеза разряда сумматора. Интерфейс синтезируемого модуля представлен на рис. 39. Процесс синтеза модуля состоит в составлении описания его поведения. Описывать поведение модуля полностью нет необходимости. Достаточно описать поведение для какого-то одного набора входных данных. Если модуль реализует несколько сценариев, то описывать необходимо каждый из них. При описании поведения следует опираться на три фактора. Первый из них это собственно задача, решаемая модулем. Выбор решения определяется проектировщиком и именно он во многом определяет конечный результат. Два других фактора носят формальный характер. Второй фактор это соблюдение стандарта протоколов интерфейса. Третий фактор определяется базисом реализации. Здесь будем рассматривать реализацию на пороговых элементах NCL.



Воспользуемся библиотекой пороговых элементов NCL, представленной в таб. 3. Пороговый элемент (как и всякий другой) может быть использован с различными протоколами. Ограничимся пока протоколами с полной индикацией входов. То есть будем рассматривать только такие описания поведения порогового элемента, в которых выходное переключение индицирует все переключения входов (здесь и далее под термином «индикация» не подразумевается использование отдельного элемента в качестве индикатора). В этом случае описание поведения порогового элемента представляет собой совокупность альтернативных ветвей, каждая из которых соответствует конъюнкции в записи пороговой функции элемента в форме ДНФ (представлены в таб. 3). А каждая альтернативная ветвь представляет собой поведение C-элемента, входы которого это сигналы перечисленные в соответствующей конъюнкции. На рис. 40 как пример представлено поведение элемента TH23. Такой протокол позволяет реализовывать функции. При этом событие X+ интерпретируется каким-то значением функции, а события A+, B+, C+ интерпретируются какими-то значениями каких-то аргументов данной функции. Таким образом, поведение модуля представляет собой совокупность узлов синхронизации (последовательных или параллельных относительно друг друга), у которых причины это значения аргументов, а следствия — значения функций (выходных или промежуточных). Также надо помнить, что фаза спейсера (вследствие использования протоколов с полной индикацией) является зеркальным отражением фазы данных (с точностью до знаков событий).





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

Таким образом, первый этап синтеза это составление алгоритма вычисления. Этот этап носит неформальный характер и от него во многом зависит конечный результат. В первом сценарии на основании значений обоих слагаемых (As+, Bs+) получаем значение выходного переноса (Csout+). Значение суммы (Ss+) получаем на основании значений обоих слагаемых и значении входного переноса (Csin+). Символ «s» в именах сигналов обозначает «1» или «0». Во втором сценарии на основании значений обоих слагаемых и значении входного переноса одновременно получаем значения выходного переноса и суммы. Алгоритмы вычисления для обоих сценариев показаны на рис. 41.



На втором этапе в поведение добавляются входные сигналы ответа (события AckS+, AckCout+). При этом надо учитывать требования к стандарту протоколов хэндшейка: добавляемые события должны предшествовать соответствующим выходным событиям, которые интерпретированы значениями функций (соответственно Ss+, Csout+). Результат на рис. 42.



Поскольку сигналы модуля реализуются в соответствии с протоколами с полной индикацией (рис. 40), негативная фаза поведения модуля полностью определяется позитивной фазой. Поэтому полученных на втором этапе фрагментов поведения модуля достаточно для вычисления логических функций сигналов (в данном случае пороговых функций элементов NCL, таб. 3). Сначала надо составить таблицу соответствия входных и выходных данных (таб. 4). Каждая строка таблицы соответствует какому-то набору входных данных. Значения выходных данных устанавливаются исходя из логики задачи, решаемой модулем. Пользуясь таб. 4 и рис. 42 можно составить пороговые функции сигналов:

Tr(S1)=AckS*A1*B1*C1in+AckS*A0*B0*C1in+AckS*A1*B0*C0in+AckS*A0*B1*C0in
Tr(S0)=AckS*A1*B1*C0in+AckS*A0*B0*C0in+AckS*A1*B0*C1in+AckS*A0*B1*C1in
Tr(C1out)=AckCout*A1*B1+AckCout*A1*B0*C1in+AckCout*A0*B1*C1in
Tr(C0out)=AckCout*A0*B0+AckCout*A1*B0*C0in+AckCout*A0*B1*C0in.



Полученные функции зависят от 7 или 6 переменных и не могут быть реализованы элементами NCL. Поэтому третий этап — декомпозиция. Он заключается в добавлении "+"-переключений новых сигналов. Цель — уменьшение количества непосредственных причин для выходных и новых (внутренних) событий. В сценарии 1 добавляется событие F+, в сценарии 2 — H101+, H100+, H011+, H010+, G1+, G0+. Результат декомпозиции на рис. 43. Таблица соответствия данных после третьего этапа показана в таб. 5. На ее основании и поведении модуля (рис. 43) получаем пороговые функции сигналов (после выражения пороговой функции в скобках следует имя соответствующего NCL элемента):

Tr(F)=A1*B1+A0*B0 (THxor0)
Tr(H101)=A1*B0*C1in (TH33)
Tr(H100)=A1*B0*C0in (TH33)
Tr(H011)=A0*B1*C1in (TH33)
Tr(H010)=A0*B1*C0in (TH33)
Tr(G1)=H101+H011 (TH12)
Tr(G0)=H100+H010 (TH12)
Tr(C1out)=AckCout*G1+AckCout*A1*B1 (TH54w32)
Tr(C0out)=AckCout*G0+AckCout*A0*B0 (TH54w32)
Tr(S1)=AckS*G0+AckS*F*C1in (TH54w32)
Tr(S0)=AckS*G1+AckS*F*C0in (TH54w32).





Дальнейшие манипуляции с поведением на реализацию вышеперечисленных сигналов уже не повлияют. Четвертый этап синтеза поведения: дополнение поведения негативной фазой и формирование выходных хэндшейков. Так как все сигналы модуля реализуются в соответствии с протоколами с полной индикацией (пример на рис. 40), негативная фаза поведения модуля является зеркальным отражением позитивной фазы с точностью до знаков событий. Также следует заметить, что переключение сигнала входного ответа является непосредственным следствием соответствующего значения выходной функции (Ss+ -> AckS-, Ss- -> AckS+, Csout+ -> AckCout-, Csout- -> AckCout+). Дополнив поведение этими причинными связями, мы сформируем выходные хэндшейки (рис. 44).



Цель пятого этапа — обеспечение протоколов с полной индикацией для всех невходных сигналов. Для этого необходимо обеспечить непосредственные или опосредованные причинные связи между всяким переключением невходного сигнала и всякой непосредственной причиной противоположного переключения того же невходного сигнала (опосредованные причинные связи могут устанавливаться только для не параллельных событий). Например, для сигнала Ss в первом сценарии такими причинными связями являются Ss+ -> F-, Ss+ -> Csin-, Ss+ -> AckS-, а также зеркальные — Ss- -> F+, Ss- -> Csin+, Ss- -> AckS+. Зеркальные связи можно не рассматривать, так как решения для них тоже будут зеркальные. Также можно заметить, что причинная связь Ss+ -> AckS- уже обеспечена. Для обеспечения остальных причинных связей нельзя просто установить какую-то произвольную причинную связь. Сделать это можно следующим образом. Непосредственной причиной сброса значения входного аргумента (As-, Bs-, Csin-) может быть только "-"-переключение выходного сигнала ответа (соответственно AckA-, AckB-, AckCin-). А последнее в свою очередь может быть непосредственным следствием одного или нескольких значений внутренних или выходных функций (например Hs+, Csout+). Также следует заметить, что обеспечение протоколов с полной индикацией для всех невходных сигналов одновременно гарантирует стандартный протокол для входных хэндшейков.

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

(F+, Ss+) -> (As-)
(F+, Ss+) -> (Bs-)
(Csout+) -> (As-)
(Csout+) -> (Bs-)
(Ss+) -> (Csin-)
(Ss+) -> (As-, Bs-).

Для сценария 2:

(Hs+, Gs+, Csout+, Ss+) -> (As-)
(Hs+, Gs+, Csout+, Ss+) -> (Bs-)
(Hs+, Gs+, Csout+, Ss+) -> (Csin-)
(Gs+, Csout+, Ss+) -> (As-, Bs-, Csin-)
(Csout+) -> (As-, Bs-, Csin-)
(Ss+) -> (As-, Bs-, Csin-).

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

Csout+ -> As-
Ss+ -> As-
Csout+ -> Bs-
Ss+ -> Bs-
Ss+ -> Csin-.

Для сценария 2:

Ss+ -> As-
Csout+ -> Bs-
Ss+ -> Csin-.

Теперь нужно учесть, что каждая приведенная выше причинная связь является опосредованной, где транзитным событием является переключение соответствующего выходного ответа (AckA-, AckB-, AckCin-). Таким образом поведение необходимо дополнить следующими непосредственными причинными связями. В сценарии 1:

Csout+ -> AckA-
Ss+ -> AckA-
AckA- -> As-
Csout+ -> AckB-
Ss+ -> AckB-
AckB- -> Bs-
Ss+ -> AckCin-
AckCin- -> Csin-.

В сценарии 2:

Ss+ -> AckA-
AckA- -> As-
Csout+ -> AckB-
AckB- -> Bs-
Ss+ -> AckCin-
AckCin- -> Csin-.

Для полученного таким образом поведения пороговая функция сигнала AckA (C1out*S1+C1out*S0+C0out*S1+C0out*S0+S0+S1) содержит поглощаемые конъюнкции (C1out*S1, C1out*S0, C0out*S1, C0out*S0), что является недопустимым. Для исправления этого второй сценарий надо дополнить причинной связью Csout+ -> AckA-. Для устранения аналогичной проблемы в отношении сигнала AckB второй сценарий надо дополнить связью Ss+ -> AckB-. Так как пороговые функции сигналов AckA и AckB стали одинаковыми (C1out*S1+C1out*S0+C0out*S1+C0out*S0, элемент TH24comp), сигнал ответа для слагаемых (As, Bs) можно сделать общим. Также, дополнив оба сценария причинной связью Csout+ -> AckCin-, можно сделать сигнал ответа общим для всех трех аргументов (Ack). В итоге оба сценария дополняем следующими причинными связями (не забыв про зеркальные):

Csout+ -> Ack-
Ss+ -> Ack-
Ack- -> As-
Ack- -> Bs-
Ack- -> Csin-.

Итоговое поведение модуля показано на рис. 45.



Перечень элементов схемы, реализующей поведение, изображенное на рис. 45, ниже:

F=THxor0(A1, B1, A0, B0)
H101=TH33(A1, B0, C1in)
H100=TH33(A1, B0, C0in)
H011=TH33(A0, B1, C1in)
H010=TH33(A0, B1, C0in)
G1=TH12(H101, H011)
G0=TH12(H100, H010)
C1out=TH54w32(AckCout, G1, A1, B1)
C0out=TH54w32(AckCout, G0, A0, B0)
S1=TH54w32(AckS, G0, F, C1in)
S0=TH54w32(AckS, G1, F, C0in)
Ack=!TH24comp(C1out, C0out, S1, S0).

Как видно из рис. 45, сигнал Ack удовлетворяет требованиям к протоколам с полной индикацией. Но встает вопрос: а всегда ли выходной сигнал ответа удовлетворяет этим требованиям? Для начала рассмотрим ситуацию, когда причинные связи, добавляемые в поведение на пятом этапе синтеза модуля, обусловлены лишь только требованиями к протоколам с полной индикацией. На рис. 46 показаны переключения сигнала ответа (Ack+, Ack-) и их непосредственные причины и следствия. У каждого переключения сигнала ответа только одно следствие (соответственно значение Din+ и сброс Din- входного аргумента), поскольку изначально каждому аргументу соответствует свой выходной сигнал ответа. Выходные сигналы ответа объединяются по мере возможности. События Dout1+, ..., Doutm+ являются значениями внутренних или выходных функций. Для того, чтобы сигнал Ack соответствовал протоколу с полной индикацией достаточно, чтобы для каждого события Douti- существовала опосредованная причинная связь Ack- -> Douti-. В силу правила введения дополнительных причинных связей на пятом этапе синтеза для всякого сигнала Douti всегда найдется сигнал H (внутренний или выходной), возможно совпадающий с сигналом Douti, со следующими существующими опосредованными причинными связями: H+ -> Douti+, Din- -> H- и соответствующими зеркальными. Из рис. 47 видно, что сигнал Douti удовлетворяет вышеизложенному требованию. А это в свою очередь доказывает, что сигнал Ack удовлетворяет требованиям к протоколам с полной индикацией.





Теперь рассмотрим проблему добавления причинных связей, обусловленных поглощением конъюнкций в ДНФ пороговой функции сигнала ответа. Такая ситуация может иметь место только тогда, когда список непосредственных причин (например Fs+, Gs+) события Ack- в одном сценарии является подмножеством такого же списка (например Fs+, Gs+, Hs+, Js+) для того же события (Ack-) во втором сценарии. Простым решением может быть добавление в первый сценарий причинных связей Hs+ -> Ack- и Js+ -> Ack-. Такое решение не всегда гарантирует корректный результат. Но всегда можно прибегнуть к заведомо корректному решению: все выходные сигналы ответа объединяются в один, а непосредственными причинами последнего становятся значения выходных функций.

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

Раздел 6. Слабая причинность

Использование пороговых элементов в соответствии с протоколами с неполной индикацией входных событий открывает дополнительные возможности в оптимизации схем. Характерной чертой протоколов с неполной индикацией является подача внешней средой (схемой) на входы порогового элемента большего количества «единиц», чем это необходимо для переключения выхода в 1. Пример такого протокола показан на рис. 48. Неиндицированные события C+ и B+ должны быть проверены до того, как внешняя среда (схема) начнет сбрасывать входы в 0.



Такие протоколы с неполной индикацией входов позволяют реализовывать слабые причинные связи. Обычно при описании поведений используются только сильные причинные связи: событие срабатывает исключительно только при срабатывании всех его непосредственных причин. В противоположность этому слабая причинная связь это срабатывание события при срабатывании хотя бы одной из нескольких его непосредственных причин. А между двумя этими крайностями лежит пространство причинных отношений разной степени слабости. Приведенный выше пример (рис. 48) демонстрирует такую слабую причинную связь: сигнал X переключится в 1 при переключении в 1 сигнала A и одного из двух сигналов B или C.

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

В первом сценарии (когда значения всех аргументов одинаковы) сигнал выходного переноса Csout реализует протокол с неполной индикацией, а соответственно и слабую причинность. Неиндицированное событие проверяется событием Ss+ (значением суммы). Так как не известно, какой аргумент придет последним (и следовательно не будет индицирован), проверять необходимо все аргументы. Вообще, неиндицированные события можно было бы проверить выходным сигналом ответа, но это неоправданно бы усложнило последний. Алгоритм вычисления для сценария 1 представлен на рис. 49а. ArAs, ArBs, ArCs — номинальные имена. Они подразумевают под собой имя одного из аргументов (As, Bs, Csin). Сделано это для сокращения количества сценариев. Под именем ArCs подразумевается аргумент, пришедший последним. Символ «s» в именах подразумевает под собой «1» или «0». Соответствие данных для первого сценария представлено в таб. 6.





Во втором сценарии (в котором значения всех трех аргументов не совпадают) для получения значения выходного переноса (Csout+) достаточно двух аргументов, значения которых одинаковы (ArAs+, ArBs+). Сигнал Csout (в этом сценарии) реализует протокол с полной индикацией. Для получения значения суммы (Ss+) можно было бы использовать значения трех аргументов, но использование значения выходного переноса и аргумента, чье значение отличается от значений двух других аргументов (ArCs+), дает более простую пороговую функцию сигнала Ss. Алгоритм вычисления и таблица соответствия данных для второго сценария представлены соответственно на рис. 49б и в таб. 6.

Поведение модуля после его дополнения переключениями входных сигналов ответа (AckS+, AckCout+) показано на рис. 50. На основании этого поведения и таблицы соответствия данных (таб. 5) можно получить пороговые функции выходных сигналов:

Tr(S1)=AckS*A1*B1*C1in+AckS*C0out*A1+AckS*C0out*B1+AckS*C0out*C1in
Tr(S0)=AckS*A0*B0*C0in+AckS*C1out*A0+AckS*C1out*B0+AckS*C1out*C0in
Tr(C1out)=AckCout*A1*B1+AckCout*A1*C1in+AckCout*B1*C1in
Tr(C0out)=AckCout*A0*B0+AckCout*A0*C0in+AckCout*B0*C0in.



Сигналы S1, S0 зависят от 5 переменных и их необходимо декомпозировать (в оба сценария добавляется событие Fs+). Результат представлен на рис. 51. Соответствие входных, выходных и внутренних данных отражено в таб. 7. Пороговые функции выходных и внутренних сигналов следующие:

Tr(F1)=A1*B1*C1in+C0out*A1+C0out*B1+C0out*C1in
Tr(F0)=A0*B0*C0in+C1out*A0+C1out*B0+C1out*C0in
Tr(S1)=AckS*F1
Tr(S0)=AckS*F0
Tr(C1out)=AckCout*A1*B1+AckCout*A1*C1in+AckCout*B1*C1in
Tr(C0out)=AckCout*A0*B0+AckCout*A0*C0in+AckCout*B0*C0in.





Следующий этап синтеза — дополнение сценариев негативными фазами и создание выходных хэндшейков (рис. 52). При дополнении негативной фазы в первом сценарии необходимо учесть, что сигнал Csout реализует протокол с неполной индикацией. Поэтому негативную фазу следует дополнить причинной связью ArCs- -> Csout- (сигнал ArCs в позитивной фазе не индицировался).



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

(Fs+, Ss+) -> (ArAs-)
(Fs+, Ss+) -> (ArBs-)
(Fs+, Ss+) -> (ArCs-)
(Ss+) -> (ArAs-, ArBs-, ArCs-).

Элемент Csout реализуется с протоколом с неполной индикацией. Индицируемые входные его переключения (ArAs+, ArBs+) требуют реализации следующих опосредованных причинных связей (а также зеркальных им):

(Csout+) -> (ArAs-)
(Csout+) -> (ArBs-).

Неиндицируемое событие ArCs+, в соответствии с протоколом, должно предшествовать событию ArCs-, а также одному из двух событий ArAs- или ArBs-. Это порождает необходимость реализации следующих опосредованных причинных связей (но не зеркальных им):

(ArCs+, Fs+, Ss+) -> (ArCs-)
(ArCs+, Fs+, Ss+) -> (ArAs-, ArBs-).

Также, в соответствии с протоколом, событию ArCs+ должно предшествовать событие Csout-. Это требует реализации опосредованной причинной связи (но не зеркальной ей):

(Csout-) -> (ArCs+).

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

(Fs+, Ss+) -> (ArAs-, ArBs-)
(Fs+, Ss+) -> (ArCs-)
(Ss+) -> (ArAs-, ArBs-, ArCs-)
(Csout+, Fs+, Ss+) -> (ArAs-)
(Csout+, Fs+, Ss+) -> (ArBs-).

Так как имена аргументов (ArAs, ArBs, ArCs) являются номинальными, сигнал ответа для любого из номинальных аргументов в действительности является сигналом ответа для всех реальных аргументов (As, Bs, Csin). Следовательно, для данной реализации сигнал выходного ответа Ack может быть только общим для всех аргументов. Поэтому оба сценария дополняются причинными связями Ack- -> ArAs-, Ack- -> ArBs-, Ack- -> ArCs-, а также зеркальными к ним. А вышеприведенный перечень опосредованных причинных связей, требуемых к реализации, преобразуется в следующий список непосредственных причинных связей. В первом сценарии необходимо реализовать следующие причинные связи (а также зеркальные им):

(Fs+, Ss+) -> (Ack-)
(Ss+) -> (Ack-)
(Csout+) -> (Ack-).

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

(ArCs+, Fs+, Ss+) -> (Ack-)
(Csout-) -> (Ack+).

Во втором сценарии требуют реализации такие причинные связи (а также зеркальные им):

(Fs+, Ss+) -> (Ack-)
(Ss+) -> (Ack-)
(Csout+, Fs+, Ss+) -> (Ack-).

Минимальным решением этой задачи является добавление в оба сценария причинной связи Ss+ -> Ack-, а только в первый сценарий — причинной связи Csout+ -> Ack- (также добавляются и зеркальные причинные связи Ss- -> Ack+ и Csout- -> Ack+). Для полученного поведения пороговая функция сигнала Ack (C1out*S1+C0out*S0+S1+S0) содержит поглощаемые конъюнкции. Для исправления этого второй сценарий дополняется причинными связями Csout+ -> Ack- и Csout- -> Ack+. После этого пороговая функция сигнала Ack становится равной C1out*S1+C0out*S0+C0out*S1+C1out*S0. Решение, когда выходной сигнал ответа является общим для всех аргументов, а его непосредственными причинами являются значения (или сбросы) всех выходных функций, — универсальное и при использовании протоколов с неполной индикацией. Итоговое поведение модуля показано на рис. 53.



Синтезированная схема состоит из следующих элементов:

F1=TH34w2(C0out,A1,B1,C1in)
F0=TH34w2(C1out,A0,B0,C0in)
S1=TH22(F1,AckS)
S0=TH22(F0,AckS)
C1out=TH44w2(AckCout,A1,B1,C1in)
C0out=TH44w2(AckCout,A0,B0,C0in)
Ack=!TH24comp(C1out,C0out,S1,S0).

Сама схема изображена на рис. 54.



Аналогичная NCL схема полного сумматора (Karl M. Fant, Scott A. Brandt, «NULL Convention Logic») показана на рис. 55. Как видно, синтезированная схема модуля отличается от NCL схемы наличием встроенных сигналов ответа. Но это с лихвой компенсируется тем, что NCL схема нуждается в окружении в виде управления и регистров.



Стоит заметить, что использование протоколов с неполной индикацией накладывает дополнительный вид ограничений на задержки внутримодульных проводов (также, как и в NCL схемах). В протоколах с полной индикацией переключение входа элемента из 1 в 0 должно быть воспринято самим элементом (сохраняющим на выходе 0) раньше, чем переключение другого его входа (в следующей итерации) из 0 в 1 (см. раздел 3). В протоколах с неполной индикацией, дополнительно к этому, неиндицированное переключение входа элемента из 0 в 1 должно быть воспринято самим элементом раньше, чем переключение другого его входа из 1 в 0 (в той же итерации). К примеру (рис. 53а), задержка провода от входа схемы ArCs до элемента Csout (при передаче «1») должна быть меньше, чем сумма задержки пути (ArCs+ -> Fs+ -> Ss+ -> Ack- -> ArAs-) и задержки провода от входа схемы ArAs до элемента Csout (при передаче «0»).

Раздел 7. Реализация самозависимых функций

До сих пор рассматривались только функции, не зависящие от самих себя. В качестве примера самозависимой функции рассмотрим C-элемент. Его логическая функция: x=a*b+a*x+b*x. Проблема реализации самозависимой функции заключается в том, что значение функции, вычисленное на предыдущей итерации, невозможно перенести через спейсер. К следующей итерации оно будет потеряно. То есть у модуля нет памяти. Путь решения проблемы это создание памяти для хранения последнего вычисленного значения функции. Видится два способа решения этой задачи. Первый — создание памяти внутри модуля. Второй — создание памяти вне модуля путем замыкания обратной связи передачи данных от выхода модуля к его входу.

Рассмотрим первый способ на примере реализации C-элемента (то есть его логической функции). Так как значение функции x хранится в памяти модуля, у модуля только два входных информационных канала: a и b. Интерфейс модуля представлен на рис. 56. Исходное поведение модуля изображено на рис. 57. Плэйсы p1 и p0 описывают память модуля. Нахождение маркера в плэйсе p1 означает, что последним вычисленным значением функции является 1. Нахождение маркера в плэйсе p0 означает, что последним вычисленным значением функции является 0.





Память модуля реализуется добавлением новых сигналов f и g. Они представляют собой триггер, плечи которого переключаются при переходе из одного состояния памяти в другое. Также добавление этих сигналов устраняет CSC-конфликты исходного поведения. Новые сигналы i2, i1, i0 реализуют функцию перехода между состояниями памяти. Событие i1+ означает поступление только одной единицы на вход модуля (входные наборы 10 и 01). В этом случае память остается в прежнем состоянии. Событие i2+ означает поступление двух единиц на вход модуля (входной набор 11). В этом случае память переходит в состояние, соответствующее плэйсу p1 (или же остается в этом состоянии). Событие i0+ означает поступление двух нулей на вход модуля (входной набор 00). В этом случае память переходит в состояние, соответствующее плэйсу p0 (или же остается в этом состоянии). Сигнал h — результат декомпозиции сигнала i1 с целью реализации обоих в ограниченном базисе (на элементах библиотеки NCL). Итоговое поведение модуля представлено на рис. 58.



На основании синтезированного поведения вычисляются логические элементы схемы:

h=THxor0(A1,B0,A0,B1)
i2=TH33(A1,B1,AckX)
i1=TH22(h,AckX)
i0=TH33(A0,B0,AckX)
f=!(i0+g)
g=!(i2+f)
X1=f*(i2+i1)
X0=g*(i0+i1)
AckAB=!(X1+X0).

Теперь на все том же примере (C-элемента) рассмотрим реализацию памяти в виде внешнего контура модуля. Передать данные напрямую с выхода модуля на его вход нельзя: замкнутый контур должен состоять как минимум из трех модулей. Поэтому обратную связь образуют два модуля, реализующие функцию y=x. Таким образом, модуль, реализующий самозависимую функцию, состоит из трех модулей: собственно из модуля C, реализующего уже не самозависимую функцию, и двух модулей (I1 и I2), реализующих передачу данных с выхода модуля C на его же вход (рис. 59).



Теперь реализуем модуль C, как не самозависимую функцию x=a*b+a*xt+b*xt (она же функция переноса сумматора). Как видно, x равен 1, если хотя бы два аргумента из трех равны 1. И x равен 0, если хотя бы два аргумента равны 0. Это дает возможность использовать протоколы с неполной индикацией для реализации функции (что подразумевает использование слабой причинности). Таким образом поведение модуля разбивается на два сценария. Сценарий 1 реализуется, если все три аргумента имеют одинаковое значение (в этом сценарии реализуется слабая причинность). Сценарий 2 реализуется, если значения аргументов различаются. В целях сокращения количества сценариев входные переменные описываются номинальными именами: aAs, aBs, aCs. Символ «s» (как и в других именах) подразумевает «1» или «0», в зависимости от значения, которым интерпретировано переключение данного сигнала. Под номинальным именем может скрываться любой реальный аргумент (As, Bs, Xts). Под именем aCs в первом сценарии скрывается аргумент, чье значение пришло последним. Во втором сценарии под именем aCs скрывается аргумент, чье значение отличается от значений двух других аргументов. На рис. 60 представлен результат первого этапа синтеза модуля (составления алгоритма вычислений). Различие между сценариями заключается в том, что в первом из них сигнал Xs описывается протоколом с неполной индикацией, а во втором сценарии — протоколом с полной индикацией. Это различие проявится при добавлении в поведение негативной фазы. Событие aCs+ в обоих сценариях в дальнейшем будет проверено выходным сигналом ответа. Соответствие входных и выходных данных для различных входных наборов представлено в таб. 8.





На втором этапе в поведение добавляются входные сигналы ответа AckXr и AckXf (рис. 61). На основании полученного поведения и таблицы соответствия данных (таб. 8) можно получить пороговые функции выходных сигналов:

Tr(X1)=AckXr*AckXf*(A1*B1+A1*Xt1+B1*Xt1)
Tr(X0)=AckXr*AckXf*(A0*B0+A0*Xt0+B0*Xt0).



Полученные функции не могут быть реализованы элементами библиотеки NCL, так как зависят более чем от четырех переменных. Для декомпозиции сигналов X1 и X0 в поведение вводится новый сигнал F (рис. 62). Теперь пороговые функции выглядят следующим образом:

Tr(F)=AckXr*AckXf
Tr(X1)=F*(A1*B1+A1*Xt1+B1*Xt1)
Tr(X0)=F*(A0*B0+A0*Xt0+B0*Xt0).



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



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

(Xs+) -> (aAs-)
(Xs+) -> (aBs-).

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

(aCs+) -> (aAs-, aBs-)
(aCs+) -> (aCs-)
(Xs-) -> (aCs+).

Во втором сценарии для реализации протокола с полной индикацией необходимо обеспечить следующие причинные связи (а также зеркальные им):

(Xs+) -> (aAs-)
(Xs+) -> (aBs-).

Для соблюдения знакочередуемости сигнала aCs необходимо обеспечить причинную связь (а также зеркальную ей)

(aCs+) -> (aCs-).

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

Xs+ -> Ack-
Ack- -> aAs-
Ack- -> aBs-
Ack- -> aCs-.

Также оба сценария дополняются причинной связью

aCs+ -> Ack-.

Но второй сценарий (в отличие от первого) дополняется и зеркальной ей связью.

В обоих сценариях сигнала Ack проверяет переключения номинального сигнала aCs. Но под именем aCs может скрываться любой реальный аргумент. Следовательно сигнал Ack должен проверять переключения всех номинальных сигналов (aAs, aBs, aCs). Поэтому оба сценария необходимо дополнить причинными связями:

aAs+ -> Ack-
aBs+ -> Ack-.

А второй сценарий (в отличие от первого) — и зеркальными им связями.

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

aAs- -> Ack+
aBs- -> Ack+
aCs- -> Ack+.

Полученное поведение изображено на рис. 64.



Для данного поведения пороговая функция инверсии сигнала Ack (X1*A1*B1*Xt1+X1*A1*B1*Xt0+X1*A1*B0*Xt1+X1*A0*B1*Xt1+X0*A1*B0*Xt0+X0*A0*B1*Xt0+X0*A0*B0*Xt1+X0*A0*B0*Xt0) зависит от 8 переменных и не может быть реализована NCL элементом. Поэтому, для декомпозиции сигнала Ack, в поведение вводятся новые сигналы: X, aA, aB, aC (рис. 65). При этом имена aA, aB, aC являются номинальными и под каждым из них может скрываться любой из трех новых реальных сигналов (A, B, Xt). Соответствие номинальных и реальных имен приведено в таб. 9.





По поведению (рис. 65) и таблице соответствия данных (таб. 9) вычисляются оставшиеся сигналы модуля C. Пороговая функция:

Tr(Ack)=X*A*B*Xt.

И логические функции:

X=!(X1+X0)
A=!(A1+A0)
B=!(B1+B0)
Xt=!(Xt1+Xt0).

Модули I1 и I2 реализуют функцию тождество. Поведение модуля, реализующего такую функцию, представлено на рис. 13. Такой модуль состоит из двух C-элементов и элемента ИЛИ-НЕ. Теперь можно привести полный перечень элементов модуля, реализующего парафазный C-элемент (рис. 59):

X1=TH44w2(F,A1,B1,Xt1)
X0=TH44w2(F,A0,B0,Xt0)
F=TH22(AckXr,AckXf)
Ack=TH44(X,A,B,Xt)
X=!(X1+X0)
A=!(A1+A0)
B=!(B1+B0)
Xt=!(Xt1+Xt0)
Xo1=TH22(X1,AckXo)
Xo0=TH22(X0,AckXo)
AckXf=!(Xo1+Xo0)
Xt1=TH22(Xo1,Ack)
Xt0=TH22(Xo0,Ack)
AckXo=!(Xt1+Xt0).

А теперь исследуем влияние реализации самозависимой функции с внутренней или внешней памятью на скорость обработки данных. Рассмотрим реализацию с внешней памятью: вносит ли контур обратной связи дополнительную задержку в работу модуля? Рассмотрим цепочку последовательно соединенных модулей. Данные первому модулю такой цепочки поставляются без задержки. Также без задержки считываются данные с выхода последнего модуля цепочки. В этом случае переключение выходов модулей (смена спейсера на данные и наоборот) происходит по условным тактам. После каждого такта выходы модулей цепочки представляют последовательность: D D S S D D S S ... (D — данные, S — спейсер, начало цепочки слева). После каждого такта последовательность сдвигается на один шаг вправо (S D D S S D D S ...). То есть новые данные подаются на вход модуля с интервалом в 4 такта. В то же время контур обратной связи передает данные за 3 такта. Таким образом, контур обратной связи не влияет ни на быстродействие, ни на производительность. Внутренняя же память, очевидно, вносит дополнительную задержку, особенно при смене состояний памяти. Для рассмотренного примера скорость обработки данных модуля с внешней памятью выше в 2.75 раза, чем модуля с внутренней памятью (2 транзисторных переключения против 5.5). С другой стороны площадь, занимаемая модулем с внутренней памятью, меньше в 1.63 раза (92 транзистора против 150).

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

В общем случае (при реализации памяти внутри модуля) количество состояний памяти может быть больше двух. Оно соответствует количеству различных сочетаний значений тех выходных переменных, которые подаются на вход модуля. При двух двузначных переменных, возвращаемых на вход, количество состояний памяти равно четырем. Для реализации памяти каждому ее состоянию сопоставляется один сигнал. Значение 1 такого сигнала означает нахождение памяти в соответствующем состоянии. Сигналы, соответствующие иным состояниям памяти, в это время находятся в 0. При поступлении команды перехода в другое состояние памяти сначала сигнал, соответствующий предыдущему состоянию, переключается в 0, а затем сигнал, соответствующий новому состоянию памяти, переключается в 1. На рис. 66 представлено поведение памяти с тремя состояниями (на вход модуля подается одна трехзначная выходная переменная x). Плэйсы p1, p2, p3 соответствуют состояниям памяти (соответственно состояния 1, 2 и 3). "+"-переключения сигналов A1, A2, A3 — значения функции переходов между состояниями памяти (команды «перейти в состояние 1», «перейти в состояние 2», «перейти в состояние 3» соответственно). Сигналы f1, f2, f3 реализуют память. Значение 1 какого-то из этих сигналов означает нахождение в состоянии памяти 1, 2, 3 соответственно. События X1+, X2+, X3+ интерпретированы значениями выходной переменной x.



Переменная x реализуется следующими логическими функциями:

X1=f1*A1
X2=f2*A2
X3=f3*A3.

В случае наличия в поведении команды «остаться в прежнем состоянии» (событие B+), логические выражения для переменной x дополняются еще одной буквой B (например X1=f1*(A1+B)). Сложность реализации выходной переменной не зависит от размерности памяти.

Сама память реализуется следующими логическими функциями:

f1=!(A2+A3+f2+f3)
f2=!(A1+A3+f1+f3)
f3=!(A1+A2+f1+f2).

В общем случае сигнал, соответствующий состоянию памяти, реализуется элементом ИЛИ-НЕ с 2*(n-1) входами, где n — количество состояний памяти. Входами этого элемента являются все иные сигналы, соответствующие состояниям памяти, а также сигналы, чьи переключения интерпретированы командами перехода между состояниями памяти, за исключением команды перехода в состояние, соответствующее реализуемому сигналу. При четырех состояниях памяти количество входов таких элементов возрастает до 6. Реализация такого рода поведений в ограниченном базисе связана с неадекватно большим расходованием ресурсов (быстродействие, площадь). Поэтому внутреннею память разумно использовать при небольшом количестве ее состояний. Количество состояний памяти можно уменьшить, разделив ее на не зависимые блоки. Так память двух самозависимых функций, не зависящих друг от друга, можно реализовать раздельно. Вместо общей памяти на 4 состояния (функции двузначные) получаются два отдельных блока по 2 состояния на каждый.

Значениями функции перехода между состояниями памяти в общем случае являются безусловные и условные команды. Безусловные команды это «перейти в состояние памяти N (или же остаться в нем)» и «остаться в прежнем состоянии памяти». Условные команды это те же безусловные, только выполняемые при нахождении памяти в одном или нескольких определенных состояниях. Например: «перейти в состояние памяти N при условии нахождения в состоянии памяти M». Напрямую при реализации памяти условные команды использовать нельзя. Но они легко преобразуются в безусловные команды с помощью добавления одного сигнала (рис. 67). На рисунке плэйсы p1 и p2 соответствуют состояниям памяти 1 и 2. Событие C21+ — условная команда «перейти в состояние 2, если текущее состояние 1». Событие A2+ — добавленное событие, являющееся безусловной командой «перейти в состояние 2». Сигналы f1 и f2 реализуют память и соответствуют ее состояниям 1 и 2. X2 — выходной сигнал модуля. Логическая функция добавленного сигнала: A2=C21*(f1+A2).



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