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

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

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

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

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

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

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

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

Две схемы, не зависящие от скорости[4]. (a) неполумодулярная; (b) полумодулярная

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

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

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

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

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

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

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

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

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

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

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

Первым и, возможно, самым популярным сегодня протоколом связи для организации взаимодействия асинхронных блоков является двухпроводной протокол. Он был предложен Д. Е. Маллером в[29] и сейчас известен как DIMS (англ. Delay Insensitive Minterm Synthesis). В частности, методология NCL (англ. Null Convention Logic) основывается на DIMS.

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

Независимый от скорости RS-триггер Брайловского SU785961 (патент СССР 07.12.1980)
Граф сигнальных переходов триггера Брайловского[30]

Графы сигнальных переходов (англ. Signal Transition Graphs, STG) [31] [32] [33] основаны на сетях Петри, переходы в которых помечены именами сигналов.

Самый простой класс 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)[34] [35] [36] подобно 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. R. E. Miller, "An introduction to speed independent circuit theory, " Symposium on Switching Circuit Theory and Logical Design, 1961, pp. 87-93.
  5. A. V. Yakovlev, A. M. Koelmans, "Petri nets and digital hardware design, " Lectures on Petri Nets II: Applications, vol. 1492, pp 154—236, 1998.
  6. S. H. Unger, "Self-synchronizing circuits and nonfundamental mode operation, " IEEE Transactions on Computers, vol. C-26, no. 3, pp. 278—281, 1977.
  7. A. V. Yakovlev, A. M. Koelmans, L. Lavagno, "High level modelling and design of asynchronous interface logic, " preprint, 1995.
  8. J. A. Brzozowski, "Topics in asynchronous circuit theory, " Recent Advances in Formal Languages and Applications, vol. 25, pp. 11-42, 2006.
  9. H. W. Lawson, B. Malm, "A flexible asynchronous microprocessor, " BIT Numerical Mathematics, vol. 13, no. 2, pp. 165—176, 1973.
  10. А. А. Васенков и др., "Микропроцессорная вычислительная система, " Авторское свидетельсво SU674025, 15/07/1979.
  11. B. J. Nordmann, B. H. McCormick, "Modular asynchronous control design, " IEEE Transactions on Computers, vol. C-26, no. 3, pp. 196—207, 1977.
  12. H. Lawson, An Asynchronous Approach to Microprogramming. Chapter 3 in «Microprogramming and Firmware Engineering Methods» (ed. S. Habib), Wiley, 1988.
  13. R. Tinder, R. I. Klaus, "Microprogrammable asynchronous controllers for digital electronic systems, " Patent US5063536, Nov. 5, 1991.
  14. Глава 4.5.3 в биографии Д. И. Юдицкого
  15. Серия 587
  16. Серия 588
  17. Серия 1883/U830
  18. I. E. Sutherland, "Micropipelines, " Communications of the ACM, vol. 32, no. 6, pp. 720—738, 1989.
  19. M. Singh, S. M. Nowick, "MOUSETRAP: ultra-high-speed transition-signaling asynchronous pipelines, " International Conference on Computer Design (ICCD) 2001, pp. 9-17.
  20. I. Sutherland and S. Fairbanks, "GasP: A minimal FIFO control, " International Symposium on Asynchronous Circuits and Systems (ASYNC) 2001, pp. 46-53.
  21. A. Yakovlev, Asynchronous Design: Quo Vadis? DDECS, Vienna 2010
  22. 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»
  23. 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.
  24. S. Hauck, "Asynchronous design methodologies: an overview, " Proceedings of the IEEE, vol. 83, no. 1, pp. 69-93, 1995. Translated to Russian as «Методологии асинхронных проектов: краткий обзор»
  25. A. Davis and S. M. Nowick, "An introduction to asynchronous circuit design, " Report UUCS-97-013, University of Utah, 1997.
  26. В. И .Варшавский, В. Б. Мараховский, Л. Я. Розенблюм, А. В. Яковлев, § 4.3 Апериодическая схемотехника, в кн. Искусственный интеллект, Том 3: Программные и аппаратные средства. Под ред. В. Н. Захарова и В. Ф. Хорошевского. М.: Радио и связь, 1990.
  27. 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.
  28. R. Puri, Asynchronous Logic Design. Chapter in Wiley Encyclopedia of Electrical and Electronics Engineering, pp. 726—741, 2001.
  29. D. E. Muller, "Asynchronous logics and application to information processing, " Symposium on the Application of Switching Theory in Space Technology (eds. H. Aiken and W. F. Main), pp. 289—297, 1963.
  30. В. И. Варшавский, В. Б. Мараховский, Л. Я. Розенблюм, А. В. Яковлев, "Асинхронные параллельные процессы и самосинхронные схемы," Электронная техника. Сер. Упр. кач-вом, стандартизация, метрология, испытания, Вып. 5. № 4, стр. 3-33, 1988.
  31. L. Ya. Rosenblum and A. V. Yakovlev, "Signal graphs: from self-timed to timed ones," IEEE International Workshop on Timed Petri Nets, 1985, pp. 199-207.
  32. T.-A. Chu, C. K. C. Leung, and T. S. Wanuga, "A design methodology for concurrent VLSI systems," IEEE International Conference on Computer Design (ICCD) 1985, pp. 407-410.
  33. 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.
  34. В. И. Варшавский, М. А. Кишиневский, А. Ю. Кондратьев, "Модели для спецификации и анализа процессов в асинхронных схемах, " Изв. АН СССР. Техническая кибернетика, 1988, № 2, стр. 171—190.
  35. 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.
  36. 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.

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

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

  1. Р. Миллер, Теория переключательных схем, не зависящих от скорости, Гл. 10 в кн. Теория переключательных схем. Том 2: Последовательностные схемы и машины. Наука, 1971, стр. 242—298.
  2. А. Г. Астановский, В. И. Варшавский, В. Б. Мараховский и др. Апериодические автоматы. М. Наука, 1976, 423 с.
  3. Н. А. Стародубцев, Синтез схем управления параллельных вычислительных систем. Л. Наука, 1984, 191 с.
  4. В. И. Варшавский, М. А. Кишиневский, В. Б. Мараховский и др. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах. М.: Наука, 1986. Translated to English as Self-Timed Control of Concurrent Processes: The Design of Aperiodic Logical Circuits in Computers and Discrete Systems
  5. M. Kishinevsky, A. Kondratyev, A. Taubin and V. Varshavsky, Concurrent Hardware: The Theory and Practice of Self-Timed Design, Wiley, 1993, 388 p.
  6. S. S. Appleton, Performance-directed design of asynchronous VLSI systems. PhD thesis, University of Adelaide, 1997, 285p.
  7. S. P. Wilcox, Synthesis of asynchronous circuits. PhD dissertation, University of Cambridge, 1999, 250 p.
  8. C. J. Myers, Asynchronous Circuit Design. Wiley, 2001, 392 p.
  9. 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 «Проектирование асинхронных схем — вводное руководство»
  10. В. Б. Мараховский, Логическое проектирование асинхронных схем. Слайды по курсу, Кафедра АиВТ СПбГПУ.
  11. Л. П. Плеханов, Основы самосинхронных электронных схем. Бином, 2013, 208 с.
  12. В. Б. Мараховский, Л. Я. Розенблюм, А. В. Яковлев, Моделирование параллельных процессов. Сети Петри. Курс для системных архитекторов, программистов, системных аналитиков, проектировщиков сложных систем управления. СПб: Профессиональная литература, АйТи-Подготовка, 2014, 400 с.

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

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