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

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

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

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

В асинхронной науке центральное место занимает свойство схем, называемое независимостью от скорости, по английски speed independent (далее SI). Считается, что это свойство является аналогом независимости асинхронных схем от задержек логических элементов. Неудивительно, что термин SI упоминается практически в каждой работе по асинхронике. Но периодически по части этого термина возникают какие-то смутные сомнения. Не случайно, что все чаще этот термин заменяется другим термином, именуемом самосинхронностью. Прояснить эту ситуацию поможет обращение к первоисточнику. Речь идет о втором томе книги Р. Миллера «Теория переключательных схем», а если точнее, о главе 10, именуемой «Теория переключательных схем, не зависящих от скорости».

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

1)

$$

где a*b*...*c — это импликанта, состоящая из одной или более переменных. g+h+...+i — это возможно пустое множество импликант, состоящих из одной переменной. x*f — это импликанта из 2 переменных, наличие которой в минимальной форме не обязательно. Все переменные, кроме x, могут входить в формулу как в прямом, так и в инверсном виде, в зависимости от расстановки знаков соответствующих событий. Все переменные входят в формулу в качестве аргументов строго по одному разу.

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

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

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



Задача состояла в том, чтобы импликанта покрыла точку 2 (то есть была равна 1 на этом состоянии) и не выходила за пределы обозначенные точками 1 и 3… При этом положение левой границы импликанты (левее точки 2) безразлично. Правая граница (правее точки 2) должна быть максимально сдвинута вправо. Невозможность вычисления импликанты означает наличие CSC конфликта. То есть существует непрерывная последовательность событий (но не все поведение целиком), в которой каждый сигнал переключается четное число раз.

Приступим теперь к вычислению минимальной логической функции (ДНФ) для сигнала x.

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

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


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

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

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

Данное определение подразумевает гипотезу о задержках Маллера. Второй пункт есть следствие первого. А первый пункт не что иное, как определение давно устоявшегося термина speed-independent (SI). То есть получается, что самосинхронные схемы это не отдельный класс схем, а схемы, синтезированные определенным методом, который гарантирует свойство SI. Таким образом «самосинхронный» это не характеристика класса схем, а характеристика метода синтеза.

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

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

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

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

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

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

Полистал недавно книжку (не всю, только то, что позволили):



Нашел пример, как делать схемы с помощью Petrify. Исходное задание выглядит так:

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

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

В чем причина этих неудач? Я бы назвал 3 основные:

1. Увлеченность STG. Да, это красивая, забавная модель, очень интересно играть маркерами и т.п. Но, подумайте, процесс переключения сигналов схемы это такой же процесс как выполнение какой-либо программы. Мы используем для описания программы сети Петри? Для чего тогда они нужны при описании процессов, происходящих в схеме? В результате разработчики Petrify львиную долю своих усилий потратили на изучение свойств сетей Петри. А собственно задачи синтеза схем так и не были решены.

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

3. Неспособность разобраться в причинах возникающих проблем. Но об этом ниже.