Хабрахабр

Мои замечания о книге Л.П. Плеханова «Основы самосинхронных электронных схем»

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

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

Самосинхронной схемой (СС-схемой) называется схема, обладающая
двумя свойствами безошибочной работы:

  • отсутствием гонок при любых конечных задержках элементов;
  • отказобезопасностью.

Данное определение подразумевает гипотезу о задержках Маллера. Второй пункт есть следствие первого. А первый пункт не что иное, как определение давно устоявшегося термина speed-independent (SI). То есть получается, что самосинхронные схемы это не отдельный класс схем, а схемы, синтезированные определенным методом, который гарантирует свойство SI. Таким образом «самосинхронный» это не характеристика класса схем, а характеристика метода синтеза.
Рассмотрим подробнее особенности самосинхронного метода синтеза. Начну со способа описания работы схемы. Самосинхронным методом взят на вооружение функциональный подход. Обосновывается это тем, что событийный подход предполагает обязательное замыкание схемы (симуляцию внешней среды). Отсюда трудности с иерархическим описанием. Я бы назвал это древними нелепыми предрассудками. Взяты они по всей видимости из работ Варшавского 30-летней давности. Причем без какого-то осмысления. То что Варшавский рассматривал упрощенную модель, автономные схемы, это понятно и вполне разумно. Но нельзя же промежуточные результаты возводить в ранг догмы. К тому же функциональный подход вторичен по отношению к событийному подходу. Функциональное описание есть не что иное, как результат применения метода Маллера к событийному описанию. Действительно, по диаграмме изменений получаем таблицу истинности, по ней вычисляем логические функции. В итоге получаем функциональное описание. Фактически получается, что самосинхронный метод является надстройкой над методом Маллера. За исключением комбинационных схем, для которых функциональное описание вполне естественно. К тому же функциональное описание ущербно по отношению к событийному. Во-первых, если событийное описание содержит CSC-противоречия, то функциональное описание вообще не может быть составлено. Конечно, проблема легко решается добавлением сигналов, но самосинхронный метод это не предусматривает. Во-вторых, событийное описание это описание работы как самой схемы, так одновременно и внешней среды. Функциональное же описание описывает только схему. Схема без описания дисциплины изменений входных сигналов смысла не имеет. Действительно, в книге полно примеров, но в лучшем случае присутствует только словесное описание работы внешней среды. В конце концов автор вынужден ввести чисто событийные понятия: инициатор и континуатор (для сигналов).

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

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

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

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

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

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

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

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

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

В свое время Стародубцев, когда он работал в группе Варшавского, предлагал подобный алгоритм. Но идея была зарублена на корню. Действительно, алгоритм был неудачный и не эффективный, так сказать вывернутый на изнанку. Предлагалось при построении импликант расширять зону «1» (для функции И). Начать с минимальной импликанты (состояния) и постепенно ее увеличивать путем объединения с соседними состояниями, по мере возможности. В действительности надо расширять зону «0», то есть уменьшать импликанту до тех пор, пока она не поместится в нужную область. Еще одним достоинством этого алгоритма является то, что он позволяет полностью отказаться от понятия «состояние». Алгоритм оперирует только событиями и причинно-следственными связями между ними.

Но сам по себе алгоритм не избавляет от перебора. Поэтому надо использовать еще одно направление для снижения объемов вычислений: вычисление логических функций заранее известного вида. Для этого нужна предварительная коррекция поведения. Такая коррекция проводится в 3 этапа. Сначала устраняются кратные сигналы, то есть сигналы, переключения которых в описании встречаются более двух раз. Об этом подробнее мной написано в первой статье. Затем устраняются ситуации вида:

И наконец дополним каждый сигнал x дуальным сигналом y.

Пара сигналов x и y представляют собой простейший триггер. Функции возбуждения такого триггера это одна импликанта. Теперь сложность вычисления логической функции становится линейной относительно количества событий. Сложность предварительной коррекции также линейная.

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

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

$x=OR(a,AND(b,NOT(c))) $

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

Событие c- является непосредственной причиной события a-, хотя эта причинно-следственная связь могла бы быть опосредованной. Почему так сделано, поясню позже. Данное поведение содержит два перехвата (состязания). Первое: между событиями c- и a-. Второе: между событиями c+ и b+. Вообще, для каждого логического элемента (в соответствии с его поведением) может быть составлен исчерпывающий список перехватов. Рассмотрим подробнее первый. Перехват заключается в том, что для поддержания на выходе логического элемента x значения 1 необходимо, чтобы событие c- было воспринято на элементе OR (составной части элемента x) раньше чем событие a-.

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

$Tcx+Tnot+Tand< Tca+Ta+Tax,$

где $Tcx$ — задержка провода от выхода элемента c до входа элемента x,
$Tnot$ — задержка элемента NOT, составной части элемента x,
$Tand$ — задержка элемента AND, составной части элемента x,
$Tca$ — задержка провода от выхода элемента c до входа элемента x,
$Ta$ — задержка элемента a,
$Tax$ — задержка провода от выхода элемента a до входа элемента x.

Такое соотношение задержек является критическим для базиса НЕ-И-ИЛИ-НЕ, то есть вероятность ошибки является максимальной. Вообще можно составить для схемы полный перечень таких соотношений задержек, при выполнении которых схема будет работать правильно.

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

$Tcx+Tand< Tca+Ta+Tax$

Синтез в базисе И-НЕ, ИЛИ-НЕ приводит к такому соотношению задержек:

$Tcx< Tca+Ta+Tax$

Частный случай такого синтеза, синтез в базисе 2И-НЕ, 2ИЛИ-НЕ, мной упоминался выше. Следующий шаг это увеличение правой части неравенства. Для этого необходимо увеличить «длину» перехвата, то есть в нашем примере разнести события c- и a- дальше друг от друга. Сделать это можно вставив между этими событиями переключения новых сигналов.

Рассмотрим в кчестве примера схему в базисе 2И-НЕ, 2ИЛИ-НЕ. Пусть элемент схемы $x=NAND(a,b)$ имеет «короткий» перехват (между событиями b- и a+). То есть событие b- является непосредственной причиной события a+. Фрагмент схемы выглядит так:

Поведение этого фрагмента такое:

Следствия выбранного базиса реализации и «короткого» перехвата на элементе x следующие: 1) элемент a имеет вид 2И-НЕ; 2) сигнал c (второй вход элемента a) может переключаться единственным образом (как это показано на рисунке выше).

Задача состоит в том, чтобы скорректировать схему (путем коррекции поведения) таким образом, чтобы: 1) схема сохранила работоспособность; 2) базис реализации остался прежним; 3) не появилось новых элементов с «коротким» перехватом; 4) перехват на элементе x перестал бы быть «коротким». Скорректированное поведение выглядит таким образом (добавлены сигналы f, g, h):

Скорректированный фрагмент схемы теперь выглядит так:

Корректировка затронула только сигналы x и a, только для переключений этих сигналов были изменены события-причины. Следовательно все остальные сигналы схемы свои логические функции сохранили. Длина перехвата для остальных сигналов схемы как минимум не уменьшилась. Для элемента x перехват осуществляется событиями f+ и h-, для элемента a — событиями c- и g+, для элемента f — событиями g- и b+, для элемента g — событиями f- и h+, для элемента h — событиями b- и a+. Ни один из перехватов не является «коротким». применив эту процедуру ко всем (по необходимости) элементам схемы, получим схему, для которой наихудшее соотношение задержек будет таким:

$Tпр< Tпр+Tэл+Tпр+Tэл+Tпр,$

где $Tпр$ — задержка провода,
$Tэл$ — задержка элемента.

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

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

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

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

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

Теги
Показать больше

Похожие статьи

Кнопка «Наверх»
Закрыть