WikiSort.ru - Не сортированное

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

Асинхро́нная ло́гика — разновидность взаимодействия логических элементов цифровых устройств. Отличается от синхронной тем, что её элементы действуют асинхронно, не подчиняясь глобальному генератору тактовых импульсов.

Описание

Асинхронные схемы управляются двумя сигналами: запрос, который выдается после установки входов и ответ. Относительно пары этих сигналов переходной процесс в асинхронной схеме моделируется элементом задержки, величина которой конечна и заранее неизвестна. В синхронных схемах аномалии динамического поведения (состязания и риски) маскируются с помощью тактового генератора. Для борьбы с аномалиями в асинхронных схемах используется механизм индикации^[1], который фиксирует моменты окончания переходных процессов. Готовность сигналов индикации определяется величинами реальных задержек, которые могут изменяться и зависят от условий функционирования схемы (например от температуры). Физически, индикатор окончания переходных процессов в схеме может отсутствовать, тогда его роль выполняют специальные самосинхронные коды^[2][3]. Таким образом, по сравнению с синхронными схемами, асинхронные в общем случае, содержат больше логических элементов. Основные преимущества асинхронных схем по сравнению с синхронными это^[4]:

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

Синхронные схемы практически любого уровня сложности могут быть реализованы на относительно дешевых ПЛИС. Напротив, строго-самосинхронные схемы предъявляют очень жесткие требования к внутренней структуре ПЛИС^[5][6] и практически единственным решением является изготовление ПЛИС на заказ^[7][8][9]. Однако, стоит отметить попытки реализации асинхронных схем на биполярных ПЗУ^[10][11], стандартных PAL (CPLD)^[12][13] и FPGA^[14][15][16]. Поскольку стандартные FPGA являются синхронными устройствами, на них относительно легко построить схемы с согласованной задержкой^[17][18][19] и, сложнее, локально-синхронные (GALS) схемы^[20][21]. В большинстве стандартных FPGA отсутствуют средства реализации арбитров. Один из способов обойти это ограничение представлен в^[14]. В статье^[15] для реализации строго-самосинхронной схемы предлагается модифицировать FPGA Atmel AT40K с очень мелким размером элементарной ячейки (fine grained)^[22][23].

Модели и классификация

Асинхронная схема может рассматриваться как аппаратная реализация параллельной распределенной программы^[30]. Для выполнения такой программы во времени обычно необходим какой-либо механизм, в то время как асинхронной схеме этот механизм не нужен. Аналогами операторов и команд в асинхронной схеме являются логические элементы, триггеры или сложные иерархические модули. Роль данных, которыми обмениваются компоненты схемы играют переключения сигналов на соединительных линиях. Таким образом, асинхронная система как правило, определяется как набор асинхронных модулей, которые взаимодействуют через асинхронные протоколы. Все события на системном уровне упорядочены во времени через причинно-следственные связи между действиями модулей. Порядок, установленный разработчиком должен быть сохранен в схеме, то есть фактически сгенерирован, что в конечном счете обеспечивает правильное функционирование. В общем случае, классификация самосинхронных схем довольно сложна и неоднозначна^[1][31][32]. Однако, существуют по крайней мере две достаточно общие модели таких схем с разными предположениями о задержке в элементах, проводах и их соединениях^[33][34]:

1. Mодель с ограниченной задержкой (модель Хаффмана, Huffman model^[35]), в которой предполагается максимальная задержка распространения сигналов в схеме (наихудший случай). Для построения таких схем нужно вводить задержку в цепь обратной связи либо использовать локальную синхронизацию. Таким образом, схемы построенные в соответствии с моделью Хаффмана не являются строго самосинхронными. Пример использования модели Хаффмана — это различные варианты микроконвейеров (micropipelines) с согласованной задержкой^{[36][37][38][39]}. В общем случае нехаффменовские модели — это модели, использующие динамические языки спецификации, для формального анализа или синтеза. Операционные устройства таким образом представить затруднительно.
2. Mодель с неограниченной задержкой до точки разветвления (модель Маллера, Muller model^[40][41]), в которой предполагается, что разница в задержке проводов после разветвления меньше, чем минимальная задержка элемента. Схемы построенные в соответствии с моделью Маллера делятся на несколько классов:
   • схемы, не зависящие от скорости (speed-independent, SI circuits);
   • полумодулярные или/и дистрибутивные (semi-modular or/and distributive) схемы;
   • схемы квазинечувствительные к задержкам (quasi-delay-insensitive, QDI circuits).

Дистрибутивные схемы являются подмножеством полумодулярных, которые в свою очередь, являются подмножеством SI-схем. На практике, класс SI-схем эквивалентен классу QDI. Теория и методы проектирования QDI-схем хорошо развиты и, поэтому, такие схемы наиболее популярны для реализации.

Сложные асинхронные системы нельзя однозначно представить ни моделью Хаффмана ни моделью Маллера. Такие системы могут быть построены как асинхронные конечные автоматы^[42][43] или, в очень крупном масштабе, как асинхронные микропроцессорные комплекты^[44][45], использующие микропрограммное управление^{[46][47][48][49]}. Подобные комплекты представлены сериями К587^[50][51], К588^[52] и К1883 (U83x в ГДР)^[53]. Обучение проектированию сложных последовательных самосинхронных схем целесообразно начинать с реализации простого одноразрядного процессора MC14500B и объединения таких процессоров в вычислительную структуру^[54].

Сильная (И) и слабая (ИЛИ) обусловленность

На интуитивном уровне, обусловленность (причинная-следственная связь, causality) в асинхронных схемах — это зависимость порядка появления выходных сигналов от порядка появления входных. Эта зависимость может быть сильной (И) и слабой (ИЛИ), что соответствует схемам с полной индикацией (full indication) и досрочным получением результата (early evaluation)^[55].

Предположим, что некоторое событие имеет две причины: ${\displaystyle x_{1}}$ и ${\displaystyle x_{2}}$ . И-обусловленность предполагает, что оба события ${\displaystyle x_{1}}$ и ${\displaystyle x_{2}}$ должны иметь место, прежде чем может произойти событие ${\displaystyle y}$ . Таким образом, в случае И, каждая причина сильно предшествует результату. Аналогом такого поведения в социологии является коллективизм и товарищество. В случае ИЛИ-обусловленности событие ${\displaystyle z}$ может произойти после того, как любое из событий ${\displaystyle x_{1}}$ или ${\displaystyle x_{2}}$ произошло (здоровый индивидуализм).

Таким образом, в случае ИЛИ, результат появляется если по крайней мере одно событие из набора слабых причин произошло. Чтобы определить как ведет себя событие ${\displaystyle z}$ после того, как обе его слабые причины ${\displaystyle x_{1}}$ и ${\displaystyle x_{2}}$ произошли, вводятся понятия совместной и несовместной обусловленности^[56] (соответственно управляемый и неуправляемый индивидуализм). Для двух входных сигналов И-обусловленность моделируется с помощью гистерезисного триггера (Г-триггер, Muller C-element), заданного уравнением ${\displaystyle y_{n}=x_{1}\cdot x_{2}+(x_{1}+x_{2})\cdot y_{n-1}}$ . Модель совместной ИЛИ-обусловленности — это элемент «включающее ИЛИ» (inclusive OR, EDLINCOR)^[57], который использует выход ${\displaystyle y_{n}}$ гистерезисного триггера и задается уравнением ${\displaystyle z_{n}=x_{1}\cdot x_{2}+(x_{1}+x_{2})\cdot {\overline {y_{n}}}}$ . Модель полностью несовместной ИЛИ-обусловленности — это схемы, основанные на арбитрах.

Рассмотрим асинхронную схему, в которой есть двухвходовый элемент ИЛИ (двухвходовый элемент И). В фазе гашения на входе элемента ИЛИ установлен код 00, а на входе элемента И — код 11. В рабочей фазе сначала один из входов переключится в 1 (0), а затем второй. Необходимо индицировать оба изменения, но в случае OR-causality процесс будет развиваться по одному входу, а затем второй вход где-то индицируется. Иными словами процесс начинает ветвиться по первому изменению входа, без ожидания второго то есть без синхронизации со вторым сигналом. Чем больше таких элементов, тем больше параллельность в схеме. Синхронизация входов возможна, но нежелательна, так как это будет другой процесс с меньшей параллельностью. OR-causality описывается либо небезопасной, но устойчивой сетью Петри, либо безопасной, но неустойчивой.

Оба типа обусловленности приводят к полумодулярным схемам. Однако, в случае И-обусловленности эти схемы являются дистрибутивными, а в случае ИЛИ — недистрибутивными. Дистрибутивные схемы могут быть построены из элементов только одного типа (например, И-НЕ или ИЛИ-НЕ), а недистрибутивные требуют использования обоих типов элементов. В случае небезопасной, но устойчивой сети Петри необходимо также бороться с накоплением точек в вершинах OR-causality. Методологии DIMS и NCL, как и любые другие методологии с полной индикацией, имеют все преимущества и недостатки И-обусловленности. Графы сигнальных переходов в своем наиболее простом варианте также реализуют полную индикацию. Диаграммы изменений позволяют моделировать как И-, так и совместную ИЛИ-обусловленность, но не могут напрямую представлять процессы с конфликтами или выбором.

Методологии проектирования

При проектировании асинхронной схемы необходимо сделать предположение о задержках. Методология самосинхронизации использует гипотезу Маллера относительно задержек в проводах — вся задержка провода приведена к выходу элемента, а разбросом задержек в проводах после разветвления можно пренебречь. В этом случае провода вообще исключаются из рассмотрения. Нарушение гипотезы Маллера приводит к нарушению причинной обусловленности поведения, являющейся логической основой самосинхронизации. Причинная обусловленность требует, чтобы каждое событие в системе являлось причиной, по крайней мере, одного другого события (свойство индицируемости самосинхронных систем^[2]). В логических структурах, в отличие от систем передачи, изменение состояния отрезка провода после разветвления может не приводить к переключению логического элемента и, следовательно, не индицироваться. При этом отрезок провода начинает выступать как элемент памяти. Для борьбы с этим, то есть для построения схем, не зависящих от задержек в проводах, необходимо использование либо специальных дисциплин переключения (что сужает класс реализуемых схем^[59]), либо использование специальных логических или топологических конструкции, как, например, изохронные разветвления^[60][61] или разветвления полем (field forks^[62][63]), требующих введения новых гипотез или/и приемов проектирования, зависящих от технологии. Эта проблема усугубляется с ростом влияния задержек в проводах и дисперсии этих задержек. Подавляющее большинство современных методологий проектирования приводят к схемам квази-нечувствительным к задержкам, то есть к схемам где все разветвления являются достаточно короткими и поэтому изохронными^[64][65]. Основная задача синтеза асинхронных схем формулируется так^[66][67]. Задается спецификация, моделирующая реальный процесс. Затем она анализируется чтобы выявить как полезные, так и аномальные свойства процесса. По результатам анализа исходная спецификация модифицируется с целью предотвращения или/и устранения аномалий. По новой, модифицированной спецификации синтезируется схема, поведение которой совпадает с исходной спецификацией. Краткий список методов анализа и синтеза асинхронных схем на основе моделей событийного типа приведен в^[68]. Полный цикл использования этих моделей в современных средствах разработки обсуждается в^[69]. Методы синтеза основанные на компиляции программ с языков высокого уровня, а также на теории трейсов рассмотрены в^[70][71][72].

Сигнальные графы

Сигнальные графы^[100][101] (сиграфы, англ. Signal Graphs^[102], англ. Signal Transition Graphs, STG^[103][104])основаны на сетях Петри, переходы в которых помечены именами сигналов.

Самый простой класс STG — STG/MG соответствует классу маркированных графов сетей Петри. Это сети Петри, где каждая позиция имеет максимум один входной переход и один выходной переход. В таком графе позиция может иметь только маркеры, удалённые из него через одиночный переход, ведущий от него и переход, однажды разрешённый, может быть запрещен только при фактическом запуске, поэтому не может быть обработана ситуация, где могут происходить А или B, но не оба^[105] . Отметим, что графически STG заменяет помеченный переход его меткой, и позиции с одним входом и одним выходом опускаются. Маркеры в этих опущенных положениях просто помещаются на соответствующую дугу. В STG метки переходов содержат не только имя сигнала, но также и определенный тип перехода, растущего («+») или падающего («-»).

Таким образом, когда запускается переход, помеченный «а+», сигнал «a» идет из 0 в 1; когда запускается переход, помеченный «а-», сигнал «a» идет из 1 в 0. Переходы на входных сигналах также различаются подчеркиванием. Чтобы создавать схемы по STG, часто требуются выполнения одного или нескольких ограничений: живучести, надежности, постоянства, непротиворечивого назначения состояния, уникального назначения состояния, одноцикловых переходов.

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

STG надёжен, если никакая позиция или дуга никогда не могут содержать больше одного маркера.

STG постоянен, если для всех дуг а* → b* (где t* означает переход t+ или t-) имеются другие дуги, гарантирующие, что b* запустится перед противоположным переходом a*.

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

STG имеет уникальное назначение состояния, если никакие две различных маркировки STG не имеют идентичных значений для всех сигналов. Наконец,

STG имеет одноцикловые переходы, если каждое имя сигнала в STG появляется в точно одном растущем и одном падающем переходе.

Диаграммы изменений

Диаграммы изменений (англ. Change Diagrams, CD)^{[106][107][108]} подобно STG имеют узлы, маркированные у переходов, и дуги между переходами, которые определяют разрешённые последовательности запуска переходов. CD имеют дуги трех типов: сильного предшествования, слабого предшествования и несвязанного сильного предшествования, а также начальную маркировку, хотя маркеры помещаются в переходы CD вместо позиций. Дуги сильного предшествования подобны дугам в STG и их можно считать дугами AND, так как переход не может запускаться, пока все дуги, указывающие на него, не отмечены маркером. Дуги слабого предшествования являются дугами OR, где переход может запускаться всякий раз, когда какой-либо переход с дугой слабого предшествования к нему отмечен маркером. Заметим, что переход не может иметь сильные и слабые дуги одновременно. Когда дуги сильного или слабого предшествования заставляют переход запускаться, на всех дугах, указывающих на этот переход, маркер удаляется и помещается на все дуги, разрешающие запуск перехода. Поскольку переход с дугами слабого предшествования, ведущими к нему, может запускаться раньше всех дуг, имеющих маркеры, дуги без маркеров имеют открытые циклы, добавленные к ним для индикации «долга» одного маркера. Когда маркер достигает дуги с долгом, маркер и долг взаимно уничтожаются. Таким образом, если маркер приходит на каждую входную дугу слабого предшествования к узлу (если ни одна из этих дуг изначально не отмечена маркерами или открытыми циклами), он будет запускаться только однажды, и может делать это, как только прибудет первый маркер. Наконец, освобождаемые дуги сильного предшествования идентичны дугам сильного предшествования, за исключением того, что после перехода, ведущего к запуску, дуга больше не сдерживает систему (считается удаляемой из CD). Таким образом, эти дуги могут использоваться для связи начального, неповторяющегося набора переходов с бесконечно повторяющимся циклом.

Основные факты и результаты

• Асинхронные схемы могут рассматриваться как обобщение кольцевого осциллятора. То есть если выходы схемы соединить непосредственно или через набор инвертеров со входами, схема должна возбудиться и начать осциллировать. Этот базовый принцип лежит в основе подхода Flow Computation.
• Разделитель (spacer) присутствует только в двухфазных самосинхронныx (СС) кодах. Однофазный СС код — это код с прямыми переходами. Других однофазных СС кодов не существует.
• Реализация логических функций. До сих пор наилучшим универсальным подходом является перекрестная реализация^[63][109]. Любая логическая функция от двух и более переменных обладает функциональными состязаниями, с которыми в принципе невозможно бороться. Однако, на сравнимых наборах монотонная (unate) функция свободна от функциональных состязаний. Поэтому удваиваем число входных переменных и заменяем инверсию переменной независимой переменной. Для того чтобы входные наборы стали сравнимыми нужна двухфазная дисциплина, в которой каждый рабочий набор перемежается спейсером (разделителем, состоящим либо из всех нулей, либо из всех единиц). Поскольку спейсер сравним с любым рабочим набором, получаем, что в двухфазной последовательности входов все соседние наборы являются сравнимыми, что необходимо для отсутствия функциональных состязаний. Остаются логические состязания (атрибут реализации). В этом случае помогает перекрестная реализация. Добавляется второй канал реализации, который реализует инверсную функцию (первый канал реализует саму функцию). Причем реализация этого канала должна быть двойственной реализации основного канала. При такой реализации все чистые инверторы в каждом канале заменяются перекрестными связями, так как каждому выходу элемента некоторого яруса соответствует выход элемента в том же ярусе инверсного канала. Эти два выхода образуют пару парафазного кода, что существенно облегчает построение индикатора для логики. В случае использования двухфазной дисциплины со спейсером парафазная реализация в КМОП-технологии не приводит к увеличению числа транзисторов по сравнению с тактируемой однофазной логикой. Это связано с тем, что КМОП-схемы в случае однофазной реализации coдержат прямой и инверсный каналы. Анализ избыточности самосинхронизирующихся кодов позволяет предположить, что для синхронной комбинационной схемы с ${\displaystyle h}$ входами и ${\displaystyle q}$ выходами должна существовать асинхронная схема с ${\displaystyle h+log_{2}(h)}$ входами и ${\displaystyle q+log_{2}(q)}$ выходами. Эта оценка соответствует гипотетической реализации с минимальными дополнительным оборудованием, то есть на практике нижний предел недостижим.
• Реализация индикаторов. Каналы индикации моментов окончания переходных процессов строятся на основе Г-триггеров. Поскольку Г-триггер содержит компоненту И, число его входов ограничено. Таким образом, нужно использовать либо пирамиды из Г-триггеров, либо системы параллельного сжатия, что приводит к затратам оборудования и увеличению задержки в схеме индикации, что может резко снизить быстродействие за счет работы по реальным задержкам. Использование свойства двусторонней проводимости МОП-транзистора позволяет построить схему двухкаскадного индикатора с практически неограниченным числом входов и расходом оборудования 4 транзистора на индицируемый вход^{[110][111][109]}.
• Некоторые самосинхронные устройства могут быть реализованы с пренебрежимо малым увеличением оборудования по сравнению с синхронной реализацией. Например счетчики (1974) и память (1986)^{[112][113][114]}.
• Схемы не зависящие от задержки (DI^[115], foam-rubber wrapper^[116]), которые состоят из элементов с одним выходом могут содержать только инверторы и С-элементы, что не позволяет строить практические схемы достаточно гибко^[59][117]. Невозможно построить полностью независимые от задержек Г-триггер, RS-триггер, Т-триггер^[63].
• Любая дистрибутивная схема может быть корректно реализована на двухвходовых элементах И-НЕ (ИЛИ-НЕ) с нагрузочной способностью не больше двух. Любая полумодулярная схема может быть корректно реализована только при совместном использовании этих элементов или при использовании трехвходовых элементов И-ИЛИ-НЕ. Вопрос о корректной реализации полумодулярных схем только на элементах И-НЕ (ИЛИ-НЕ) остается открытым^{[2][118][119]}. На практике однако, минимальный базис не имеет особого смысла ввиду высокой сложности получающихся схем. С ростом значений коэффициентов разветвления и с увеличением функциональных возможностей схемы становятся компактней. В современной КМОП технологии целесообразно использовать элементы сложность которых не превышает 4И-4ИЛИ-НЕ. Всё вышесказанное справедливо только для парафазной реализации, частным случаем которой является реализация на RS триггерах. Пример проектирования схем на двух типах трехвходовых элементов И-ИЛИ-НЕ плюс ИЛИ-И-НЕ приведен в^[120], а пример для двухвходовых 2И-НЕ плюс 2ИЛИ-НЕ — в^[121]. Не существует полумодулярной схемы из элементов И-НЕ, не чувствительной к задержкам хотя бы в двух ветвях провода, подключенного к выходу элемента, для которого состояния этой схемы живые^[122]. Если провод разветвляется, то это функция ИЛИ, поэтому где-то нужно индицировать сигналы в ветвящихся проводах (ИЛИ-обусловленность). Вопрос о реализации дистрибутивных схем на элементах И-НЕ с однофазным выходом остается открытым. Частным случаем этого является построение однофазного С-элемента только на элементах И-НЕ. Действительно, диаграмма Маллера для С-элемента является изотонной, поэтому ее можно реализовать на элементах одного типа. Такая реализация существует для парафазного представления сигналов, но не существует для однофазного представления. В этом случае требуются элементы обеих типов поскольку возникает проблема ИЛИ-обусловленности.
• По одному и тому же проводу запрос можно передавать напряжением, а подтверждение — током. В этом случае для индикации моментов окончания переходных процессов необходимо использовать датчики потребляемого тока КМОП элементов. Однако такие датчики сложны в реализации, а их быстродействие недостаточно. Таким образом, идея комбинированной индикации на практике не ведет к упрощению оборудования. Примером удачного использования этой идеи является метод самосинхронной передачи данных, где каждый бит передается по одному проводу^[123]. Для параллельной передачи ${\displaystyle n}$ разрядного двоичного кода этому методу требуется лишь ${\displaystyle n+2}$ проводов, а его производительность не хуже, чем при передачи данных по двум проводам.
• Индикаторы завершения переходных процессов могут быть построены на основе пороговых схем с несколькими выходами^[124].

Примечания

Дополнительная литература