Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
На первый взгляд кажется, что в асинхронном дизайне обработки данных изобрести что-либо новое маловероятно. Действительно, все возможные приемы и компоненты синтеза уже давно известны: и кодирование, и многофазность, и индикация, и хэндшейк, и С-элементы, и пороговые элементы… Но, в отношении практически любого метода асинхронной обработки данных можно достаточно уверенно утверждать: все они заведомо избыточны. Причина такого положения видится в несколько поверхностном понимании различий между асинхронными и синхронными схемами. Принято считать, что асинхронной является такая схема, в которой отсутствует тактовый сигнал. Отсюда вытекает и решение: достаточно взять за основу архитектуру синхронного дизайна (комбинационную логику, регистры), а тактовый сигнал заменить какой-то управляющей схемой. Таким подходом в той или иной мере грешит практически любой метод. Блочный синтез — идея более оригинальная, но от этого не менее избыточная.
Однако различие меду синхронными и асинхронными схемами носит более существенный характер. Синхронные схемы отличаются наличием временных интервалов, маскируемых тактовым сигналом. И эти временные интервалы включают все переходные процессы. То есть синхронные схемы не рассматривают переходные процессы и имеют дело только с результатами переходных процессов. Таким образом синхронная схема по сути представляет собой причинно-следственные отношения на множестве состояний. Асинхронные же схемы рассматривают как результат переходного процесса, так и сам процесс. Говорить в этом случае о состояниях можно лишь с большой долей условности. Переходный процесс и его результат описываются таким явлением, как событие (переключение сигнала). И асинхронная схема представляет собой те же причинно-следственные отношения только на множестве событий.
Подводя черту под сказанным, целью данной работы является создание метода синтеза асинхронных схем обработки данных, опирающегося на выше выявленные характерные свойства асинхронных схем и не связанного какими-либо заранее выбранными архитектурными решениями. При этом синтезированные схемы как минимум не должны зависеть от задержек элементов, а еще лучше и от задержек проводов.
Итак, у нас есть средство реализации: причинно-следственные отношения на множестве событий. И есть цель: реализация обработки данных. Обработка данных — это реализация функций. Функция — это однозначное соответствие между значениями аргументов и значениями функции. По сути это причинно-следственные отношения, где причины — значения аргументов, а следствия — значения функции. Отсюда напрашивается простое и естественное решение: надо интерпретировать события значениями аргументов и функции.
Предположим переключение сигнала 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 (в частности в пайплайнах).
Отказ от использования заранее предопределенной схемной архитектуры естественно приводит к модульно-иерархическому принципу построения схем. Модуль представляет собой законченную полноценную схему. При этом не предполагается какого-либо внешнего межмодульного управления. Модули соединяются друг с другом проводами через соответствующие входные-выходные порты. Таким образом, модуль решает две задачи: собственно вычисление функции и взаимодействие с другими модулями. Естественный механизм межмодульного взаимодействия — хэндшейк. Суть хэндшейка заключается в том, что модуль-источник, после переключения выходного сигнала, удерживает его в неизменном состоянии до тех пор, пока модуль-приемник переключением своего выходного сигнала не разрешит переключить первый. В свою очередь, модуль-приемник также, после переключения своего выходного сигнала, удерживает его в неизменном состоянии до разрешения от модуля-источника. Именно механизм хэндшейка гарантирует соблюдение свойства OP для обоих взаимодействующих схем. Межмодульный интерфейс передачи данных изображен на рис. 1б, а соответствующий протокол (поведение) хэндшейка показан на рис. 2.
После того как были определены основные компоненты, из которых должен состоять модуль, попробуем реализовать булевскую функцию тождество (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. Все остальные провода модуля, а также межмодульные провода к задержке не чувствительны. Нечувствительность к задержкам межмодульных проводов обусловлена тем, что модуль ожидает параллельного прихода входных событий, не разделенных выходными событиями (параллельный интерфейс).
Наличие в составе модуля встроенных сигналов ответа компенсируется тем, что такой модуль не нуждается во внешних схемах управления и регистрах. Регистр обычно состоит из защелок и многовходового 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 (то есть без синхронизации в фазе спейсера).
Теперь сформулируем правила соединения модулей.
Осталось убедиться, что построенная таким образом схема будет функционировать корректно. Для этого достаточно доказать, что любой произвольный модуль схемы будет функционировать корректно совместно со своей внешней средой, которую составляют все иные модули схемы. Рассмотрим такой произвольный модуль (рис. 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 и его внешней среды. Следовательно произвольный модуль будет корректно функционировать вместе со своей произвольной внешней средой. Таким образом любая схема, синтезированная с учетом пяти выше приведенных правил, будет функционировать корректно.
Собственно сам метод синтеза (как он представлен на данный момент), никаких сложностей не вызывает. Достаточно составить таблицу истинности для реализуемой функции и по ней определить логические функции элементов синтезируемого модуля. Для примера синтезируем разряд сумматора. Входными данными для него являются: 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-. Такое решение не всегда гарантирует корректный результат. Но всегда можно прибегнуть к заведомо корректному решению: все выходные сигналы ответа объединяются в один, а непосредственными причинами последнего становятся значения выходных функций.
Еще одной проблемой может стать количество переменных, от которых зависит выходной сигнал ответа. В этом случае надо прибегнуть к декомпозиции проблемного сигнала (как на третьем этапе синтеза модуля). Результат при этом будет гарантированно корректным.
Использование пороговых элементов в соответствии с протоколами с неполной индикацией входных событий открывает дополнительные возможности в оптимизации схем. Характерной чертой протоколов с неполной индикацией является подача внешней средой (схемой) на входы порогового элемента большего количества «единиц», чем это необходимо для переключения выхода в 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»).
Однако различие меду синхронными и асинхронными схемами носит более существенный характер. Синхронные схемы отличаются наличием временных интервалов, маскируемых тактовым сигналом. И эти временные интервалы включают все переходные процессы. То есть синхронные схемы не рассматривают переходные процессы и имеют дело только с результатами переходных процессов. Таким образом синхронная схема по сути представляет собой причинно-следственные отношения на множестве состояний. Асинхронные же схемы рассматривают как результат переходного процесса, так и сам процесс. Говорить в этом случае о состояниях можно лишь с большой долей условности. Переходный процесс и его результат описываются таким явлением, как событие (переключение сигнала). И асинхронная схема представляет собой те же причинно-следственные отношения только на множестве событий.
Подводя черту под сказанным, целью данной работы является создание метода синтеза асинхронных схем обработки данных, опирающегося на выше выявленные характерные свойства асинхронных схем и не связанного какими-либо заранее выбранными архитектурными решениями. При этом синтезированные схемы как минимум не должны зависеть от задержек элементов, а еще лучше и от задержек проводов.
Раздел 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 (то есть без синхронизации в фазе спейсера).
Теперь сформулируем правила соединения модулей.
- Модуль не может передавать данные сам себе.
- При соединении двух модулей данные могут передаваться только в одном направлении. То же самое касается соединения модуля с внешней средой.
- Входной порт данных может быть соединен с выходным портом данных только одного модуля. Выходной порт данных может быть соединен с входными портами данных нескольких модулей.
- Если несколько модулей (более двух) образуют замкнутую структуру, то трое из этих модулей должны иметь не стандартную начальную маркировку, а подобную, изображенной на рис. 22. Соответственно при соединении таких модулей с не стандартной начальной маркировкой с иными модулями надо обращать внимание на соответствие начальных маркировок.
- Если модуль отправляет данные в адрес нескольких иных модулей, то он должен дожидаться сигнала ответа от всех адресатов (протокол хэндшейка показан на рис. 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»).
