Асинхронная логика

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание[править | править вики-текст]

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

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

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

Модели и классификация[править | править вики-текст]

Г-триггеры на мажоритарных элементах[21][22]. (a) двухвходовый Г-триггер (C-элемент). (b) трехвходовый Г-триггер используемый в методологии NCL.
Схемы, не зависящие от скорости[23]:
(a) неполумодулярная[24][25],
полумодулярные: (b) дистрибутивная, (c) недистрибутивная[26].

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

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

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

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

Сильная (И) и слабая (ИЛИ) обусловленность[править | править вики-текст]

Временна́я диаграмма схемы «включающее ИЛИ».

На интуитивном уровне, обусловленность (причинная связь) в асинхронных схемах — это порядок появления нарастающего и спадающего фронта сигналов. Независимое от скорости поведение характеризуется двумя основными видами обусловленности между переходами сигналов: сильной (И) и слабой (ИЛИ)[51].

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

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

Оба типа обусловленности приводят к SI-схемам. Однако, в случае И-обусловленности эти схемы являются дистрибутивными, а в случае ИЛИ недистрибутивными. Методология DIMS использует гистерезные триггеры и поэтому моделирует только И-обусловленность. Графы сигнальных переходов в своем наиболее простом варианте также моделируют только И-обусловленность. Диаграммы изменений позволяют моделировать как И-, так и совместную ИЛИ-обусловленность, но не могут напрямую представлять процессы с конфликтами или выбором.

Методологии проектирования[править | править вики-текст]

Double-line delay (WCHB)
Ячейка Давида
Файл:Async toggle.png
Свободный выбор (toggle)[54]
S-element[55]
Автомат повторного вхождения

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

Двухпроводная линия связи[править | править вики-текст]

Простые синхронные схемы можно соединять между собой практически без проблем. Если в полученной сложной схеме отсутствуют критические гонки сигналов, она будет работоспособной. Соединение асинхронных схем гораздо сложнее, в полученной сложной схеме свойство асинхронности может быть утеряно. Результатом этого будет остановка работы или наоборот, генерация пачки импульсов. Если не рассматривать общий провод, то тактовый сигнал на синхронную схему подается по одному проводу. Связать асинхронные схемы можно также по одному проводу, но для этого нужно использовать однофазный самосинхронный код. В таком коде разделитель (спейсер), который состоит, как правило, из двух бит должен передаваться последовательно[70]. По сравнению с параллельным кодом, это означает более низкое быстродействие и дополнительные расходы оборудования. Однако, перспектива сэкономить на проводах очень заманчива, поскольку в современных системах на кристалле провода занимают больше половины площади. Так например, в[71][72] оборудование для спейсера использует третье состояние. Два провода позволяют использовать парафазный[73][74][75] протокол связи. Впервые такой подход был использован Д. Е. Маллером для построения строго самосинхронного микроконвейера[74]. Близким к этому способу является Delay Insensitive Minterm Synthesis (DIMS)[76]. Методология Null Convention Logic (NCL)[77][78][79] также предназначена для синтеза строго самосинхронных микроконвейеров. В отличие от DIMS, где используются C-элементы, NCL использует многовходовые Г-триггеры, которые называются пороговыми элементами и самосинхронный код М-из-N. В некоторых случаях это позволяет строить более простые схемы. Заметим, что в силу использования Г-триггеров, микроконвейеры DIMS и NCL реализуют только И-обусловленность[80][81]. Один из способов построения микроконвейеров с ИЛИ-обусловленностью предложен в[82]. Строго самосинхронные микроконвейерные схемы также могут быть синтезированны при компиляции программ с языков высокого уровня. Следует однако, ожидать, что полученные таким образом схемы не всегда будут оптимальными. Например, сумматор синтезированный в[83] сложнее, чем предложенный в[84].

Асинхронные примитивы[править | править вики-текст]

Идея использования примитивов для построения асинхронной схемы аналогична идее конструктора. Детали такого конструктора должны быть по возможности, универсальными[85]. Как правило, они описываются фрагментами сети Петри[86]. Наиболее известные асинхронные примитивы — это:

  • Double-line delay[74][75] (weak condition half buffer, WCHB[87])
  • Ячейка Давида[1][2][3][43][88] и её обобщения[89][90][91]
  • Синхронизатор, бифуркатор, свободный выбор (toggle), решатель, сборка (merge)
  • Автомат повторного вхождения[2][3] (Multiple use circuit, D-element[92][93][94])
  • Q-element[92] (S-element[22]), T-element

Сигнальные графы[править | править вики-текст]

Независимый от скорости RS-триггер Брайловского[95]
STG для триггера Брайловского[3][96]

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

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

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

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

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

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

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

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

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

Диаграммы изменений[править | править вики-текст]

Соответствие между диаграммами переходов (диаграммами Маллера) (b) и диаграммами изменений (c) для простой схемы Г-триггера (a)

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

Основные факты и результаты[править | править вики-текст]

  • Асинхронные схемы могут рассматриваться как обобщение кольцевого осциллятора. То есть если выходы схемы соединить непосредственно или через набор инвертеров со входами, схема должна возбудиться и начать осциллировать. Этот базовый принцип лежит в основе подхода Flow Computation
  • Реализация логических функций. До сих пор наилучшим универсальным подходом является перекрестная реализация[60][106]. Любая логическая функция от двух и более переменных обладает функциональными состязаниями, с которыми в принципе невозможно бороться. Однако, на сравнимых наборах монотонная функция свободна от функциональных состязаний. Поэтому удваиваем число входных переменных и заменяем инверсию переменной независимой переменной. Для того чтобы входные наборы стали сравнимыми нужна двухфазная дисциплина, в которой каждый рабочий набор перемежается спейсером (разделителем, состоящим либо из всех нулей, либо из всех единиц). Поскольку спейсер сравним с любым рабочим набором, получаем, что в двухфазной последовательности входов все соседние наборы являются сравнимыми, что необходимо для отсутствия функциональных состязаний. Остаются логические состязания (атрибут реализации). В этом случае помогает перекрестная реализация. Добавляется второй канал реализации, который реализует инверсную функцию (первый канал реализует саму функцию). Причем реализация этого канала должна быть двойственной реализации основного канала. При такой реализации все чистые инверторы в каждом канале заменяются перекрестными связями, так как каждому выходу элемента некоторого яруса соответствует выход элемента в том же ярусе инверсного канала. Эти два выхода образуют пару парафазного кода, что существенно облегчает построение индикатора для логики. В случае использования двухфазной дисциплины со спейсером парафазная реализация в КМОП-технологии не приводит к увеличению числа транзисторов по сравнению с тактируемой однофазной логикой. Это связано с тем, что КМОП-схемы в случае однофазной реализации coдержат прямой и инверсный каналы. Анализ избыточности самосинхронизирующихся кодов позволяет преположить, что для синхронной комбинационной схемы с h входами и q выходами должна существовать асинхронная схема с h+log_2(h) входами и q+log_2(q) выходами. Эта оценка соответствует гипотетической реализации с минимальными дополнительным оборудованием, то есть на практике нижний предел недостижим.
  • Реализация индикаторов. Каналы индикации моментов окончания переходных процессов строятся на основе Г-триггеров. Поскольку Г-триггер содержит компоненту И, число его входов ограничено. Таким образом, нужно использовать либо пирамиды из Г-триггеров, либо системы параллельного сжатия, что приводит к затратам оборудования и увеличению задержки в схеме индикации, что может резко снизить быстродействие за счет работы по реальным задержкам. Использование свойства двусторонней проводимости МОП-транзистора позволяет построить схему двухкаскадного индикатора с практически неограниченным числом входов и расходом оборудования 4 транзистора на индицируемый вход[106].
  • Некоторые самосинхронные устройства могут быть реализованны с пренебрежимо малым увеличением оборудования по сравнению с синхронной реализацией. Например счетчики (1974) и память (1986)[107][108].
  • Схемы не зависящие от задержки (DI[109], foam-rubber wrapper[110]), которые состоят из элементов с одним выходом могут содержать только инверторы и С-элементы, что не позволяет строить практические схемы достаточно гибко[56][111]. Невозможно построить полностью независимые от задержек Г-триггер, RS-триггер, Т-триггер[60].
  • Использование датчиков потрябляемого тока КМОП элементов для индикации моментов окончания переходных процессов в самом общем случае не выгодно и не практично. Примером удачного использования этой техники является метод самосинхронной передачи данных, где каждый бит передается по одному проводу[112]. При этом запрос передается напряжением, а ответ — током. Для параллельной передачи n разрядного двоичного кода этому методу требуется лишь n+2 проводов, а его производительность не хуже, чем при передачи данных по двухпроводному коду.
  • Невозможно построить декодер самосинхронного кода на основе сравнения, который имеет избыточность меньше, чем в случае двухбитового кода. Иначе говоря, закодированное слово должно содержать по крайней мере в два раза больше битов данных[113].

Использованные источники[править | править вики-текст]

  1. 1 2 3 А. Г. Астановский, В. И. Варшавский, В. Б. Мараховский и др. Апериодические автоматы. М. Наука, 1976, 423 с.
  2. 1 2 3 4 В. И. Варшавский, М. А. Кишиневский, В. Б. Мараховский и др. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах. М.: Наука, 1986. Translated to English as Self-Timed Control of Concurrent Processes: The Design of Aperiodic Logical Circuits in Computers and Discrete Systems.
  3. 1 2 3 4 В. И. Варшавский, В. Б. Мараховский, Л. Я. Розенблюм, А. В. Яковлев, "Асинхронные параллельные процессы и самосинхронные схемы, " Электронная техника. Сер. Упр. кач-вом, стандартизация, метрология, испытания, Вып. 5. № 4, стр. 3-33, 1988.
  4. C. H. van Berkel, M. B. Josephs, S. M. Nowick, "Applications of asynchronous circuits, " Proceedings of the IEEE, vol. 87, no. 2, pp. 223—233, 1999.
  5. P. S. K. Siegel, Automatic Technology Mapping for Asynchronous Designs. PhD dissertation, Stanford University, 1995, 159 p.
  6. P. Franklin, D. Winkel, and E. Brunvand, "A comparison of modular self-timed design styles," Report UUCS-95-025, University of Utah, 1995.
  7. C. G. Wong, A. J. Martin and P. Thomas, "An architecture for asynchronous FPGAs," IEEE Int. Conference on Field-Programmable Technology (FPT) 2003, pp. 170-177.
  8. http://www.eecs.ucf.edu/~mingjie/ECM6308/papers/Asynchronous%20FPGA%20architecture%20with%20distributed%20control%20.pdf D. Shang, F. Xia, A. Yakovlev, "Asynchronous FPGA architecture with distributed control," IEEE Int. Symposium on Circuits and Systems (ISCAS) 2010, pp. 1436—1439.]
  9. M. Courvoisier, "An asynchronous logic array for the realisation of logic systems with concurrency," Electronics Letters, vol. 14, no. 4, pp. 119-121, 1978.
  10. R. W. Hartenstein, A. Hirschbiel and M. Weber, "Patil array — A Petri net hardware implementation, " CompEuro 1988, pp. 26-33.
  11. F. Aghdasi, "Survey of self-clocked controllers," Microelectronics Journal, vol. 26, no. 7, pp. 659-682, 1995.
  12. W. Eisele, G. Eckstein, J. Beister, "VMEbus controller synthesis by communicating asynchronous sequential circuits," Kaiserslautern University, 1994.
  13. L. Lloyd, K. Heron, A. M. Koelmans, A. V. Yakovlev, "Asynchronous microprocessors: From high level model to FPGA implementation," Journal of Systems Architecture, vol. 45, no. 12-13, pp. 975-1000, 1999.
  14. 1 2 S. W. Moore and P. Robinson, "Rapid prototyping of self-timed circuits," IEEE Int. Conference on Computer Design (ICCD) 1998, pp. 360—365.
  15. 1 2 K. Meekins, D. Ferguson and M. Basta, "Delay insensitive NCL reconfigurable logic," IEEE Aerospace Conference 2002, vol. 4, pp. 1961-1966.
  16. I. Lemberski, "LUT-oriented dual-rail quasi-delay-insensitive logic synthesis," Electronics Letters, vol. 50, no. 7, pp. 503-505, 2014.
  17. V. B. Marakhovsky, A. V. Surkov, "Globally asynchronous systems of interactive Moore state-machines," IET Computers, 2016
  18. R. Payne, "Asynchronous FPGA architectures," IEE Proceedings, Computers and Digital Techniques, vol. 143, no. 5, pp. 282-286, 1996.
  19. M. B. Gokhale, P. S. Graham, Field-Programmable Gate Arrays, §2.1 in Reconfigurable Computing: Accelerating Computation with Field-Programmable Gate Arrays. Springer, 2005, 238 p.
  20. H. Kaeslin, Field-programmable logic, Ch. 2 in Top-Down Digital VLSI Design: From Architectures to Gate-Level Circuits and FPGAs, pp. 41-61, Elsevier, 2014.
  21. Трехвходовые мажоритарные элементы — 561ЛП13, 1554ЛП3 и 1564ЛП23. Пятивходовый мажоритарный элемент — MC14530B. Радиолюбительские схемы использующие Г-триггер: А.Самойленко, "Подавитель импульсов «дребезга» контактов, " Радио, 1998, no. 6, стр. 63., А.Самойленко, "Варианты построения RS-триггера, " Радио, 1998, no. 9, стр 53-56.
  22. 1 2 C. H. van Berkel, "Beware the isochronic fork, " Report UR 003/91, Philips Research Laboratories, 1991.
  23. R. E. Miller, "An introduction to speed independent circuit theory, " Symposium on Switching Circuit Theory and Logical Design, 1961, pp. 87-93.
  24. S. J. Silver, J. A. Brzozowski, "True concurrency in models of asynchronous circuit behavior, " Formal Methods in System Design, vol. 22, no. 3, pp. 183—203, 2003.
  25. J.-H. R. Jiang, A. Mishchenko, R. K. Brayton, "On breakable cyclic definitions, " IEEE/ACM Int. Conference on Computer Aided Design (ICCAD) 2004, pp. 411—418.
  26. M. Kishinevsky, A. Kondratyev, A. Taubin, V. Varshavsky, "Analysis and identification of speed-independent circuits on an event model, " Formal Methods in System Design, vol. 4, no. 1, pp. 33-75, 1994. Translated to Russian as «Анализ и идентификация схем, независимых от скорости, на модели события»
  27. A. V. Yakovlev, A. M. Koelmans, "Petri nets and digital hardware design, " Lectures on Petri Nets II: Applications, vol. 1492, pp 154—236, 1998.
  28. G. J. Zalmai, Multivariable Control Systems, Finite-State Linear Sequential Machines, and Projective Geometries: Some Explicit Interconnections, PhD thesis, Georgia Institute of Technology, 1977, 369 p.
  29. S. H. Unger, "Self-synchronizing circuits and nonfundamental mode operation, " IEEE Transactions on Computers, vol. C-26, no. 3, pp. 278—281, 1977.
  30. A. V. Yakovlev, A. M. Koelmans, L. Lavagno, "High level modelling and design of asynchronous interface logic, " preprint, 1995.
  31. J. A. Brzozowski, "Topics in asynchronous circuit theory, " Recent Advances in Formal Languages and Applications, vol. 25, pp. 11-42, 2006.
  32. M. Shams, J. C. Ebergen, M. I. Elmasry, "Asynchronous Circuits, " in Wiley Encyclopedia of Electrical and Electronics Engineering, pp. 1-23, 1999.
  33. I. E. Sutherland, "Micropipelines, " Communications of the ACM, vol. 32, no. 6, pp. 720—738, 1989.
  34. G. Cornetta, J. Cortadella, "Asynchronous pipelined datapaths design techniques. A survey, " pp. 1-31, 1997.
  35. M. Singh, S. M. Nowick, "MOUSETRAP: ultra-high-speed transition-signaling asynchronous pipelines, " International Conference on Computer Design (ICCD) 2001, pp. 9-17.
  36. I. Sutherland and S. Fairbanks, "GasP: A minimal FIFO control, " International Symposium on Asynchronous Circuits and Systems (ASYNC) 2001, pp. 46-53.
  37. V. Varshavsky, "System time and system timing, " Int. Conf. on Semigroups & Algebraic Engineering 1997, pp. 1-25.
  38. V. Varshavsky, "Time, timing and clock in massively parallel computing systems, " Int. Conf. on Massively Parallel Computing Systems 1998, pp. 100—106.
  39. R. F. Tinder, Engineering Digital Design, 2nd Ed., Academic Press, 2000, 884 p.
  40. R. F. Tinder, Asynchronous Sequential Machine Design and Analysis: A Comprehensive Development of the Design and Analysis of Clock-Independent State Machines and Systems, Morgan & Claypool, 2009, 235 p.
  41. H. W. Lawson, B. Malm, "A flexible asynchronous microprocessor, " BIT Numerical Mathematics, vol. 13, no. 2, pp. 165—176, 1973.
  42. А. А. Васенков и др., "Микропроцессорная вычислительная система, " Авторское свидетельство SU674025, 15/07/1979.
  43. 1 2 B. J. Nordmann, B. H. McCormick, "Modular asynchronous control design, " IEEE Transactions on Computers, vol. C-26, no. 3, pp. 196—207, 1977.
  44. H. Lawson, An Asynchronous Approach to Microprogramming. Chapter 3 in Microprogramming and Firmware Engineering Methods. (ed. S. Habib), Wiley, 1988.
  45. R. Tinder, R. I. Klaus, "Microprogrammable asynchronous controllers for digital electronic systems, " Patent US5063536, Nov. 5, 1991.
  46. R. F. Tinder, R. I. Klaus, J. A. Snodderley, "High-speed microprogrammable asynchronous controller modules, " IEEE Transactions on Computers, vol. 43, no. 10, pp. 1226—1232, 1994.
  47. Глава 4.5.3 в биографии Д. И. Юдицкого
  48. Серия 587
  49. С. Т. Хвощ, Н. Н. Варлинский и Е. А. Попов, Микропроцессоры и микроЭВМ в системах автоматического управления. Справочник. Л. Машиностроение, 1987, 638 с.
  50. Серия 1883/U830
  51. A. Yakovlev, Asynchronous Design: Quo Vadis? DDECS, Vienna 2010
  52. A. Yakovlev, M. Kishinevsky, A. Kondratyev, L. Lavagno, M. Pietkiewicz-Koutny, "On the models for asynchronous circuit behaviour with OR causality, " Formal Methods in System Design, vol. 9, no. 3, pp. 189—233. 1996. Translated to Russian as «О моделях для асинхронного режима схемы с причинной связью OR»
  53. D. A. Pucknell, "Event-driven logic (EDL) approach to digital systems representation and related design processes, " IEE Proceedings E, Computers and Digital Techniques, vol. 140, no. 2, pp. 119—126, 1993.
  54. D. Sokolov, J. Murphy, A. Bystrov, A. Yakovlev, "Improving the security of dual-rail circuits," Technical report NCL-EECE-MSD-TR-2004-101, University of Newcastle upon Tyne, 2004.
  55. M. B. Josephs, A. M. Bailey, "The use of SI-algebra in the design of sequencer circuits," Formal Aspects of Computing, vol. 9, no. 4, pp 395-408, 1997.
  56. 1 2 A. J. Martin, "The limitations to delay-insensitivity in asynchronous circuits, " Advanced Research in VLSI, 1990, pp. 263—278.
  57. K. van Berkel, F. Huberts, A. Peeters, "Stretching quasi delay insensitivity by means of extended isochronic forks, " Asynchronous Design Methodologies, 1995, pp. 99-106.
  58. Y. Li, Redressing Timing Issues for Speed-Independent Circuits in Deep Sub-micron Age. PhD thesis, Newcastle University, 2012, 153 p.
  59. V. I. Varshavsky, Circuits insensitive to delays in transistors and wires. Technical report no. 7, Helsinki University of Technology, 1989, 42 p.
  60. 1 2 3 M. Kishinevsky, A. Kondratyev, A. Taubin and V. Varshavsky, Review of the State-of-the-Art in Self-timing, Ch. 8 in Concurrent Hardware: The Theory and Practice of Self-Timed Design, Wiley, 1993, 388 p.
  61. S. Hauck, "Asynchronous design methodologies: an overview, " Proceedings of the IEEE, vol. 83, no. 1, pp. 69-93, 1995. Translated to Russian as «Методологии асинхронных проектов: краткий обзор»
  62. A. Davis and S. M. Nowick, "An introduction to asynchronous circuit design, " Report UUCS-97-013, University of Utah, 1997.
  63. В. И. Варшавский, В. Б. Мараховский, Л. Я. Розенблюм, А. В. Яковлев, § 4.3 Апериодическая схемотехника, в кн. Искусственный интеллект, Том 3: Программные и аппаратные средства. Под ред. В. Н. Захарова и В. Ф. Хорошевского. М.: Радио и связь, 1990.
  64. M. B. Josephs, S. M. Nowick, C. H. van Berkel, "Modeling and design of asynchronous circuits, " Proceedings of the IEEE , vol. 87, no. 2, pp. 234—242, 1999.
  65. A. Yakovlev, "Use of partial orders for analysis and synthesis of asynchronous circuits, " Workshop on unfolding and partial order techniques (UFO) 2007, pp. 12-16.
  66. D. Sokolov, A. Yakovlev, "Clockless circuits and system synthesis, " IEE Proceedings, Computers and Digital Techniques, vol. 152, no. 3, pp. 298—316, 2005.
  67. J. A. Brzozowski, C.-J. H. Seger, "Design of Asynchronous Circuits, " Chapter 15 in Asynchronous Circuits. Springer, 1995, 404 p.
  68. R. Puri, Asynchronous Logic Design. Chapter in Wiley Encyclopedia of Electrical and Electronics Engineering, pp. 726—741, 2001.
  69. ACiD-WG report on «Design, Automation and Test for Asynchronous Circuits and Systems», edited by D. Edwards and W. Toms, 2004.
  70. K. van Berkel and A. Bink, "Single-track handshake signaling with application to micropipelines and handshake circuits," IEEE Int. Symposium on Advanced Research in Asynchronous Circuits and Systems, 1996, pp. 122-133.
  71. A. S. Wojcik, K. Y. Fang, "On the design of three-valued asynchronous modules, " IEEE Transactions on Computers, vol. C-29, no.10, pp. 889—898, 1980.
  72. J. Tse, B. Hill, R. Manohar, "A bit of analysis on self-timed single-bit on-chip links, " IEEE Int. Symposium on Asynchronous Circuits and Systems (ASYNC) 2013, pp. 124—133.
  73. J. C. Sims and H. J. Gray, "Design criteria for autosynchronous circuits, " IEE Eastern Joint Computer Conference (AFIPS) 1958, vol. 14,pp. 94-99.
  74. 1 2 3 D. E. Muller, "Asynchronous logics and application to information processing, " Symposium on the Application of Switching Theory in Space Technology, pp. 289—297, 1963.
  75. 1 2 Г. Цеманек, "Последовательная асинхронная логика, " Mеждународный симпозиум ИФАК Теория конечных и вероятностных автоматов 1962, стр. 232—245. также (H. Zemanek, "Sequentielle asynchrone Logik, " Elektronische Rechenanlagen, vol. 4, no. 6, pp. 248—253, 1962.)
  76. J. Sparsø, J. Staunstrup, M. Dantzer-Sørenson, "Design of delay insensitive circuits using multi-ring structures, " European Design Automation Conference, 1992, pp. 15-20.
  77. K. M. Fant, S. A. Brandt, "NULL Convention LogicTM: a complete and consistent logic for asynchronous digital circuit synthesis, " IEEE Int. Conference on Application Specific Systems, Architectures and Processors (ASAP) 1996, pp. 261—273.
  78. A. Kondratyev, K. Lwin, "Design of asynchronous circuits using synchronous CAD tools, " IEEE Design & Test of Computers, vol. 19, no. 4, pp. 107—117, 2002.
  79. M. T. Moreira, C. H. M. Oliveira, R. C. Porto, N. L. V. Calazans, "NCL+: Return-to-one Null Convention Logic, " IEEE Int. Midwest Symposium on Circuits and Systems (MWSCAS) 2013, pp. 836—839.
  80. G. Gopalakrishnan, "Some unusual micropipeline circuits, " Report UUCS-93-015, University of Utah, pp. 1-16, 1993.
  81. A. Smirnov, A. Taubin, "Synthesizing asynchronous micropipelines with design compiler, " Synopsys Users Group Conference, pp. 1-33, 2006.
  82. A. Bystrov, D. Sokolov, A. Yakovlev, "Low-latency control structures with slack, " IEEE Int. Symposium on Asynchronous Circuits and Systems (ASYNC) 2003, pp. 164—173.
  83. A. M. Lines, "Pipelined asynchronous circuits, " Report CS-TR-95-21, California Institute of Technology, 1998.
  84. В. И. Варшавский, А. Ю. Кондратьев и В. А. Романовский и Б. С. Цирлин, "Одноразрядный сумматор на КМОП-транзисторах, " Авторское свидетельство SU1439578, 23/11/1988.
  85. S. H. Unger, "A building block approach to unlocked systems," IEEE Int. Conference on System Sciences 1993, vol. 1, pp. 339-348.
  86. S. S. Patil and J. B. Dennis, "The description and realization of digital systerns, " IEEE Computer Society Int. Conference (COMPCON) 1972, pp. 223—226.
  87. M. T. Moreira, J. J. H. Pontes, N. L. V. Calazans, "Tradeoffs between RTO and RTZ in WCHB QDI asynchronous design, " IEEE Int. Symposium on Quality Electronic Design (ISQED) 2014, pp. 692—699.
  88. M. Courvoisier and P. Azema, "Asynchronous sequential machines with request/acknowledge operating mode, " Electronics Letters, vol. 10, no. 1, pp. 8-10, 1974.
  89. V. Varshavsky and V. Marakhovsky, "Hardware support of discrete event coordination, " IEE Int. Workshop on Discrete Event Systems (WoDES) 1996, p. 332—339.
  90. A. Yakovlev, F. Burns, A. Bystrov, D. Shang, D. Sokolov, «Is the die cast for the token game?» Int. Conference on Application and Theory of Petri Nets (ICATPN) 2002
  91. D. Shang, Asynchronous Communication Circuits: Design, Test, and Synthesis, PhD thesis, Newcastle University, 2003, 248 p.
  92. 1 2 A. J. Martin, Programming in VLSI: From communicating processes to delay-insensitive circuits. Report CS-TR-89-1, California Institute of Technology, 1989, 66 p.
  93. A. Bystrov, D. Shang, F. Xia, and A. Yakovlev, "Self-timed and speed independent latch circuits, " UK Asynchronous Forum, 1999.
  94. A. J. Martin and M. Nystrom, "Asynchronous techniques for system-on-chip design," Proceedings of the IEEE, vol. 94, no. 6, pp. 1089-1120, 2006.
  95. Г. С. Брайловский, "Триггер, " Авторское свидетельство SU785961, 07/12/1980.
  96. Workcraft tool, synthesis and verification of asynchronous circuits
  97. Л. Я. Розенблюм, "Язык сигнальных графов и его использование для моделирования протоколов информационного обмена и апериодических схем, " Всесоюзный семинар Моделирование дискретных управляющих и вычислительных систем, стр. 22-24, 1981.
  98. Л. Я. Розенблюм и А. В. Яковлев, "О новой графической форме иллюстрации сущности изобретения, " Вопросы изобретательства, no. 11, стр. 36-40, 1988.
  99. L. Ya. Rosenblum and A. V. Yakovlev, "Signal graphs: from self-timed to timed ones," IEEE Int. Workshop on Timed Petri Nets, 1985, pp. 199—207.
  100. T.-A. Chu, C. K. C. Leung, and T. S. Wanuga, "A design methodology for concurrent VLSI systems," IEEE Int. Conference on Computer Design (ICCD) 1985, pp. 407-410.
  101. A. V. Yakovlev, "On limitations and extensions of STG model for designing asynchronous control circuits," IEEE Int. Conference on Computer Design (ICCD) 1992, pp. 396-400.
  102. A. V. Yakovlev, A. M. Koelmans, A. Semenov, D. J. Kinniment, "Modelling, analysis and synthesis of asynchronous control circuits using Petri nets, " Integration, the VLSI Journal, vol. 21, no. 3, pp. 143—170, 1996.
  103. В. И. Варшавский, М. А. Кишиневский, А. Ю. Кондратьев, "Модели для спецификации и анализа процессов в асинхронных схемах, " Изв. АН СССР. Техническая кибернетика, 1988, № 2, стр. 171—190.
  104. M. A. Kishinevsky, A. Yu. Kondratyev, A. R. Taubin, "Specification and analysis of self-timed circuits, " Journal of VLSI Signal Processing, vol. 7, no. 1, pp. 117—135, 1994.
  105. U. Schwiegelshohn, L. Thiele, "Properties of Change Diagrams, " Chap. 4 in Hardware Design and Petri Nets, pp. 77-92, 2000.
  106. 1 2 В. Б. Мараховский, Логическое проектирование асинхронных схем. Слайды по курсу, Кафедра АиВТ СПбГПУ.
  107. В. И. Варшавский, Н. М. Кравченко, В. Б. Мараховский и Б. С. Цирлин, "Запоминающее устройство на КМОП-транзисторах, " Авторское свидетельство SU1365129, 07/01/1988.
  108. A. J. Martin, "Tomorrow’s digital hardware will be asynchronous and verified, " IFIP Congress, vol. 1, pp. 684—695, 1992.
  109. J. T. Udding, Classification and Composition of Delay-Insensitive Circuits, PhD thesis, Eindhoven University of Technology, 1984.
  110. C.E. Molnar, T.P. Fang, and F.U. Rosenberger, "Synthesis of delay-insensitive modules, " Chapel Hill Conference on VLSI, 1985.
  111. H. Saito, A. Kondratyev, J. Cortadella, L. Lavagno, A. Yakovlev, «What is the cost of delay insensitivity?,» IEEE/ACM Int. Conference on Computer-Aided Design 1999, pp. 316—323.
  112. V. I. Varshavsky, V. B. Marakhovsky, R. A. Lashevsky, "Self-timed data transmission in massively parallel computing systems, " Integrated Computer-Aided Engineering, vol. 4, no. 1, pp. 47-65, 1997.
  113. V. Akella, N. F. Vaidya, G. R. Redinbo, "Limitations of VLSI implementation of delay-insensitive codes, " IEEE Int. Symposium on Fault Tolerant Computing, 1996, pp. 208—217.

Дополнительная литература[править | править вики-текст]

Отчёты и книги[править | править вики-текст]

  1. D. E. Muller, Theory of asynchronous circuits. Report no. 66, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1955.
  2. J. C. Nelson, Speed-independent counting circuits. Report no. 71, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1956.
  3. D. E. Muller, W. S. Bartky, A theory of asynchronous circuits I. Report no. 75, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1956.
  4. D. E. Muller, W. S. Bartky, A theory of asynchronous circuits II. Report no. 78, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1957.
  5. J. H. Shelly, The decision and synthesis problems in semimodular switching theory, PhD thesis, University of Illinois at Urbana-Champaign, 1959, 93 p.
  6. W. S. Bartky, A theory of asynchronous circuits III. Report no. 96, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1960.
  7. A. M. Bush, A method for sensing the completion of operations in speed-independent asynchronous computer circuits. MSc thesis, Georgia Institute of Technology, 1961, 67 p.
  8. W. D. Frazer, A switching theory for bilateral nets of threshold elements. PhD thesis, University of Illinois at Urbana-Champaign, 1963, 69 p.
  9. Р. Миллер, Теория переключательных схем, не зависящих от скорости, Гл. 10 в кн. Теория переключательных схем. Том 2: Последовательностные схемы и машины. Наука, 1971, стр. 242—298.
  10. А. Г. Астановский, В. И. Варшавский, В. Б. Мараховский и др. Апериодические автоматы. М. Наука, 1976, 423 с.
  11. С. Ангер, Схемы вырабатывающие сигналы завершения, § 6.1 в кн. Асинхронные последовательностные схемы, Наука, 1977, 400с.
  12. А. Фридман и П. Менон, Логические элементы с неограниченными задержками, § 4.9 в кн. Теория и проектирование переключательных схем, М. Мир, 1978, стр. 275—282.
  13. C. L. Seitz, "System timing, " Ch. 7 in Introduction to VLSI Systems, C. A Mead and L. A Conway, pp. 218—262, Addison-Wesley, 1980.
  14. Н. А. Стародубцев, Синтез схем управления параллельных вычислительных систем. Л. Наука, 1984, 191 с.
  15. В. И. Варшавский, М. А. Кишиневский, В. Б. Мараховский и др. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах. М.: Наука, 1986. Translated to English as Self-Timed Control of Concurrent Processes: The Design of Aperiodic Logical Circuits in Computers and Discrete Systems.
  16. V. I. Varshavsky (ed.), Hardware Support of Parallel Asynchronous Processes, Technical Report, Helsinki University of Technology, 1987
  17. V. I. Varshavsky, Circuits insensitive to delays in transistors and wires. Technical report no. 7, Helsinki University of Technology, 1989, 42 p.
  18. L. Lavagno, Synthesis and Testing of Bounded Wire Delay Asynchronous Circuits from Signal Transition Graphs. PhD thesis, University of California at Berkeley, 1992, 306 p.
  19. M. Kishinevsky, A. Kondratyev, A. Taubin and V. Varshavsky, Concurrent Hardware: The Theory and Practice of Self-Timed Design, Wiley, 1993, 388 p.
  20. K. van Berkel, Handshake Circuits: An Asynchronous Architecture for VLSI Programming. Cambridge, 225 p.
  21. J. A. Brzozowski, C.-J. H. Seger, Asynchronous Circuits. Springer, 1995, 404 p.
  22. S. S. Appleton, Performance-directed design of asynchronous VLSI systems. PhD thesis, University of Adelaide, 1997, 285p.
  23. S. P. Wilcox, Synthesis of asynchronous circuits. PhD dissertation, University of Cambridge, 1999, 250 p.
  24. C. J. Myers, Asynchronous Circuit Design. Wiley, 2001, 392 p.
  25. J. Sparsø, "Asynchronous circuit design — a tutorial, " Chapters 1-8 in Principles of asynchronous circuit design: A systems perspective. Kluwer, 2001, 152p. Translated to Russian as «Проектирование асинхронных схем — вводное руководство»
  26. A. Yakovlev, Theory and Practice of Using Models of Concurrency in Hardware Design. DSc. thesis based on publications, University of Newcastle upon Tyne, 2005, 27 p.
  27. K. M. Fant, Logically Determined Design: Clockless System Design with NULL Convention Logic. Wiley, 2005, 292 p.
  28. P. A. Beerel, R. O. Ozdag, M. Ferretti, A Designer’s Guide to Asynchronous VLSI. Cambridge, 2010, 339 p.
  29. Л. П. Плеханов, Основы самосинхронных электронных схем. Бином, 2013, 208 с.
  30. В. Б. Мараховский, Л. Я. Розенблюм, А. В. Яковлев, Моделирование параллельных процессов. Сети Петри. Курс для системных архитекторов, программистов, системных аналитиков, проектировщиков сложных систем управления. СПб: Профессиональная литература, АйТи-Подготовка, 2014, 400 с.

Статьи[править | править вики-текст]

Патенты[править | править вики-текст]