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

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

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

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

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

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

Заметим, что синхронные схемы практически любого уровня сложности могут быть реализованы на относительно дешевых ПЛИС. Напротив, асинхронные схемы предъявляют очень жесткие требования к внутренней структуре ПЛИС [1] и практически единственным решением является изготовление ПЛИС на заказ. Однако, попытки реализации асинхронных схем на стандартных ПЛИС непрерывно предпринимаются [2] [3].

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

Two speed-independent circuits. (a) non-semi-modular (b) semi-modular

Асинхронная схема может рассматриваться как аппаратная реализация параллельной распределенной программы [4]. Для выполнения такой программы во времени обычно необходим какой-либо механизм, в то время как асинхронной схеме этот механизм не нужен. Аналогами операторов и команд в асинхронной схеме являются логические элементы, триггеры или сложные иерархические модули. Роль данных, которыми обмениваются компоненты схемы играют переключения сигналов на соединительных линиях. Таким образом, асинхронная система как правило, определяется как набор асинхронных модулей, которые взаимодействуют через асинхронные протоколы. Все события на системном уровне упорядочены во времени через причинно-следственные связи между действиями модулей. Порядок, установленный разработчиком должен быть сохранен в схеме, т.е. фактически сгенерирован, что в конечном счете обеспечивает правильное функционирование. В зависимости от предположений о задержке в элементах, в проводах и их соединениях, модели асинхронных схем делятся на две группы [5] [6]:

  1. Mодель с ограниченной задержкой (Huffman model), в которой предполагается максимальная задержка расространения сигналов в схеме (наихудший случай). Для построения таких схем нужно вводить задержку в цепь обратной связи либо использовать локальную синхронизацию. Таким образом, схемы построенные в соответствии с моделью Хаффмана фактически являются квазисамосинхронными. Пример использования модели Хаффмана в очень крупном масштабе - это асинхронные микропроцессорные комплекты [7] [8], использующие микропрограммное управление [9] [10] [11]. Подобные комплекты представлены сериями К587 [12] [13], К588 [14] и К1883 (U83x в ГДР) [15]. Пример использования модели Хаффмана в очень мелком масштабе - это различные варианты микроконвейеров (micropipelines) [16] [17] [18].
  2. Mодель с неограниченной задержкой до точки разветвления (Muller model) [19], в которой предполагается, что разница в задержке проводов после разветвления меньше, чем минимальная задержка элемента. Схемы построенные в соответствии с моделью Маллера делятся на несколько классов:
    • схемы не зависящие от скорости (speed-independent, SI circuits)
    • полумодулярные или/и дистрибутивные (semi-modular or/and distributive) схемы
    • схемы квази-нечувствительные к задержкам (quasi-delay-insensitive, QDI circuits)

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

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

Timing diagram of inclusive OR gate

На интуитивном уровне, обусловленность (причинная связь) в асинхронных схемах - это порядок появления нарастающего и спадающего фронта сигналов. Независимое от скорости поведение характеризуется двумя основными видами обусловленности между переходами сигналов: сильной (И) и слабой (ИЛИ) [20]. Предположим, что некоторое событие имеет две причины: x_1 и x_2. И-обусловленность предполагает, что оба события x_1 и x_2 должны иметь место, прежде чем может произойти событие y. Таким образом, в случае И, каждая причина сильно предшествует результату. В случае ИЛИ-обусловленности событие z может произойти после того, как любое из событий x_1 или x_2 произошло. Таким образом, в случае ИЛИ, результат появляется если по крайней мере одно событие из набора слабых причин произошло. Чтобы определить как ведет себя событие z после того, как обе его слабые причины x_1 и x_2 произошли, вводятся понятия совместной и несовместной обусловленности [21]. Для двух входных сигналов И-обусловленность моделируется с помощью гистерезисного триггера (Muller C-element), заданного уравнением y=x_1x_2+(x_1+x_2)y. Модель совместной ИЛИ-обусловленности - это элемент "включающее ИЛИ" (inclusive OR, EDLINCOR) [22], который использует выход y гистерезисного триггера и задается уравнением z=x_1x_2+(x_1+x_2)\overline{y}.

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

При проектировании асинхронной схемы необходимо сделать предположение о задержках. Для схем независимых от скорости Д. Е. Маллер предложил использовать диаграммы состояний, где можно указать параллельность переключения компонентов схемы с помощью механизма возбуждения. Подавляющее большинство современных методологий проектирования исходят из предположений для схем независимых от скорости или квази-нечувствительных к задержкам [23] [24]. Основная задача синтеза асинхронных схем формулируется так [25]. Задается спецификация, моделирующая реальный процесс. Затем она анализируется чтобы выявить как полезные, так и аномальные свойства процесса. По результатам анализа исходная спецификация модифицируется с целью предотвращения или/и устранения аномалий. По новой, модифицированной спецификации синтезируется схема, поведение которой совпадает с исходной спецификацией. Краткий список методов анализа и синтеза асинхронных схем на основе моделей событийного типа приведен в [26].

Графы сигнальных переходов[править | править вики-текст]

Brailovsky speed-independent RS flip-flop from SU785961
Signal transition graph for the Brailovsky flip-flop [27]

Графы сигнальных переходов (Signal Transition Graphs, STG) [28] [29] [30] основаны на сетях Петри, переходы в которых помечены именами сигналов. Самый простой главный класс STG - STG/MG он соответствует классу маркированных графов сетей Петри. Это сети Петри, где каждая позиция имеет максимум один входной переход и один выходной переход. В таком графе позиция может иметь только маркеры, удаленные из него через одиночный переход, ведущий от него и переход, однажды разрешенный, может быть запрещен только при фактическом запуске, поэтому не может быть обработана ситуация, где могут происходить А или B, но не оба. Отметим, что графически 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) [31] [32] [33] подобно STG имеют узлы, маркированные у переходов, и дуги между переходами, которые определяют разрешенные последовательности запуска переходов. CD имеют дуги трех типов: сильного предшествования, слабого предшествования и несвязанного сильного предшествования, а также начальную маркировку, хотя маркеры помещаются в переходы CD вместо позиций. Дуги сильного предшествования подобны дугам в STG и их можно считать дугами AND, так как переход не может запускаться, пока все дуги, указывающие на него, не отмечены маркером. Дуги слабого предшествования являются дугами OR, где переход может запускаться всякий раз, когда какой-либо переход с дугой слабого предшествования к нему отмечен маркером. Заметим, что переход не может иметь сильные и слабые дуги одновременно. Когда дуги сильного или слабого предшествования заставляют переход запускаться, на всех дугах, указывающих на этот переход, маркер удаляется и помещается на все дуги, разрешающие запуск перехода. Поскольку переход с дугами слабого предшествования, ведущими к нему, может запускаться раньше всех дуг, имеющих маркеры, дуги без маркеров имеют открытые циклы, добавленные к ним для индикации "долга" одного маркера. Когда маркер достигает дуги с долгом, маркер и долг взаимно уничтожаются. Таким образом, если маркер приходит на каждую входную дугу слабого предшествования к узлу (если ни одна из этих дуг изначально не отмечена маркерами или открытыми циклами), он будет запускаться только однажды, и может делать это, как только прибудет первый маркер. Наконец, освобождаемые дуги сильного предшествования идентичны дугам сильного предшествования, за исключением того, что после перехода, ведущего к запуску, дуга больше не сдерживает систему (считается удаляемой из CD). Таким образом, эти дуги могут использоваться для связи начального, неповторяющегося набора переходов с бесконечно повторяющимся циклом.

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

  1. P. S. K. Siegel, Automatic Technology Mapping for Asynchronous Designs. PhD dissertation, Stanford University, 1995, 159p.
  2. D. Shang, F. Xia, A. Yakovlev, "Asynchronous FPGA architecture with distributed control," IEEE International Symposium on Circuits and Systems (ISCAS) 2010, pp. 1436-1439.
  3. M. M. Kim, P. Beckett, "Design techniques for NCL-based asynchronous circuits on commercial FPGA," Euromicro Conference on Digital System Design (DSD) 2014, pp. 451-458.
  4. A. V. Yakovlev, A. M. Koelmans, "Petri nets and digital hardware design," Lectures on Petri Nets II: Applications, vol. 1492, pp 154-236, 1998.
  5. A. V. Yakovlev, A. M. Koelmans, L. Lavagno, "High level modelling and design of asynchronous interface logic," preprint, 1995.
  6. J. A. Brzozowski, "Topics in asynchronous circuit theory," Recent Advances in Formal Languages and Applications, vol. 25, pp. 11-42, 2006.
  7. H. W. Lawson, B. Malm, "A flexible asynchronous microprocessor," BIT Numerical Mathematics, vol. 13, no. 2, pp. 165-176, 1973.
  8. А. А. Васенков и др., "Микропроцессорная вычислительная система," Авторское свидетельсво SU674025, 15/07/1979.
  9. B. J. Nordmann, B. H. McCormick, "Modular asynchronous control design," IEEE Transactions on Computers, vol. C-26, no. 3, pp. 196-207, 1977.
  10. H. Lawson, An Asynchronous Approach to Microprogramming. Chapter in "Microprogramming and Firmware Engineering Methods" (ed. S. Habib), Wiley, 1988.
  11. R. Tinder, R. I. Klaus, "Microprogrammable asynchronous controllers for digital electronic systems," Patent US5063536, Nov. 5, 1991.
  12. Глава 4.5.3 в биографии Д. И. Юдицкого
  13. Серия 587
  14. Серия 588
  15. Серия 1883/U830
  16. I. E. Sutherland, "Micropipelines," Communications of the ACM, vol. 32, no. 6, pp. 720-738, 1989.
  17. M. Singh, S. M. Nowick, "MOUSETRAP: ultra-high-speed transition-signaling asynchronous pipelines," International Conference on Computer Design (ICCD) 2001, pp. 9-17.
  18. I. Sutherland and S. Fairbanks, "GasP: A minimal FIFO control," International Symposium on Asynchronous Circuits and Systems (ASYNC) 2001, pp. 46-53.
  19. Р. Миллер, Теория переключательных схем, не зависящих от скорости, Гл. 10 в кн. "Теория переключательных схем. Том 2: Последовательностные схемы и машины," стр. 242-298. Изд. Наука, 1971.
  20. A. Yakovlev, Asynchronous Design: Quo Vadis? DDECS, Vienna 2010
  21. 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"
  22. 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.
  23. S. Hauck, "Asynchronous design methodologies: an overview," Proceedings of the IEEE, vol. 83, no. 1, pp. 69-93, 1995. Translated to Russian as "Методологии асинхронных проектов: краткий обзор"
  24. A. Davis and S. M. Nowick, "An introduction to asynchronous circuit design," Report UUCS-97-013, University of Utah, 1997.
  25. В. И .Варшавский, В. Б. Мараховский, Л. Я. Розенблюм, А. В. Яковлев, § 4.3 Апериодическая схемотехника, в кн. Искусственный интеллект, Том 3: Программные и аппаратные средства. Под ред. В. Н. Захарова и В. Ф. Хорошевского. М.: Радио и связь, 1990.
  26. 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.
  27. В. И .Варшавский, В. Б. Мараховский, Л. Я. Розенблюм, А. В. Яковлев, "Асинхронные параллельные процессы и самосинхронные схемы," Электронная техника. Сер. Упр. кач-вом, стандартизация, метрология, испытания, Вып. 5. №4, стр. 3-33, 1988.
  28. 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.
  29. J. Cortadella, M. Kishinevsky, Tutorial: Synthesis of control circuits from STG specifications. Summer school. Lyngby 1997
  30. C. Piguet, J. Zahnd, "STG-based synthesis of speed-independent CMOS cells," Workshop on Exploitation of STG-based Design Technology, 1998, pp. 1-23.
  31. В. И. Варшавский, М. А. Кишиневский, А. Ю. Кондратьев, "Модели для спецификации и анализа процессов в асинхронных схемах," Изв. АН СССР. Техническая кибернетика, 1988, №2, стр. 171-190.
  32. M. A. Kishinevsky, A.Y. Kondratyev, A. R. Taubin, "Formal method for self-timed design," European Conference on Design Automation (EDAC) 1991, pp. 197-201.
  33. A. Kondratyev, A. Taubin, V. Varshavsky, M. Kishinevsky, E. E. Pissaloux, "Change Diagram : A behavioural model for very speed VLSI circuit/highly parallel systems," Euromicro Workshop on Parallel and Distributed Processing, 1994, pp. 220-226.

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

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

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

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