Графы сигнальных переходов для схем асинхронного тракта данных

В статье предлагается метод построения графов сигнальных переходов (STG), которые напрямую отображаются в схемы асинхронной обработки данных. Преимуществом предлагаемого метода является то, что полученные схемы не только неизменны по выходу (output-persistent), но и конформны внешней среде. В других подходах среда задаётся неявно и/или неточно, и поэтому они гарантируют только неизменность по выходу. Конформность можно проверить, если как схема, так и её внешняя среда заданы STG. В качестве примера мы рассматриваем модуль, реализующий функцию 2И. Этот модуль может либо ожидать лог. 1 на обоих входах, либо вычислить функцию, как только придёт хотя бы один 0. Для каждого случая мы составляем отдельный STG (сценарий) и отображаем его в элементы NCL. Чтобы обеспечить такое отображение, мы задаём поведение NCL элементов STG протоколами . Для тракта данных такой STG всегда содержит альтернативные ветви с так называемыми мусорными переключениями на входах элементов. Мусорные переключения на определенном проводе означают, что схема чувствительна к задержке в этом проводе. Игнорирование мусора может привести к нарушению конформности и/или неизменности по выходу. Например, в комбинационной части NCL схем мусор появляется на входах NCL элементов, поэтому эти схемы чувствительны к задержкам.

1. C. Jeong and S. M. Nowick, “Optimization of Robust Asynchronous Circuits by Local Input Completeness Relaxation,” in IEEE Asia and South Pacific Design Automation Conference, 2007, pp. 622–627.

2. D. E. Muller, “Asynchronous logics and application to information processing,” Switching Theory in Space Technology, vol. 4, pp. 289–297, 1963.

3. A. Yakovlev, “Designing self-timed systems,” VLSI systems design, no. 9, pp. 70–90, 1985.

4. H. Saito, A. Kondratyev, J. Cortadella, L. Labagno, and A. Yakovlev, “What is the cost of delay insensitivity?,” in IEEE/ACM International Conference on Computer-Aided Design, 1999, pp. 316–323.

5. S. Bystrov and A. Kushnerov, “Asynchronous data processing. Behavior analysis.” 2022, doi: 10.13140/RG.2.2.14748.26248.

6. A. Kushnerov, M. Medina, and A. Yakovlev, “Towards hazard-free multiplexer based implementation of self-timed circuits,” in 27th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC), 2021, pp. 17–24.

7. I. Kimura, “Extensions of asynchronous circuits and the delay problem. Part II: Spike-free extensions and the delay problem of the second kind,” Journal of Computer and System Sciences, vol. 5, no. 2, pp. 129–162, 1971.

8. L. Y. Rosenblum and A. V. Yakovlev, “Signal graphs: from self-timed to timed ones,” in International Workshop on Timed Petri Nets, 1985, pp. 199–206.

9. J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev, Logic Synthesis for Asynchronous Controllers and Interfaces. Springer Science & Business Media, 2002.

10. I. Poliakov, A. Mokhov, A. Rafiev, D. Sokolov, and A. Yakovlev, “Automated verification of asynchronous circuits using circuit Petri nets,” in 14th IEEE International Symposium on Asynchronous Circuits and Systems, 2008, pp. 161–170.

11. V. Khomenko, M. Schaefer, and W. Vogler, “Output-determinacy and asynchronous circuit synthesis,” Fundamenta Informaticae, vol. 88, no. 4, pp. 541–579, 2008.

12. K. M. Fant, Logically determined design: clockless system design with NULL convention logic. John Wiley & Sons, 2005.

13. A. Yakovlev, M. Kishinevsky, A. Kondratyev, L. Lavagno, and M. Pietkiewicz-Koutny, “On the models for asynchronous circuit behaviour with OR causality,” Formal Methods in System Design, vol. 9, pp. 189–233, 1996.

14. V. Khomenko, M. Koutny, and A. Yakovlev, “Slimming down Petri boxes: Compact Petri net models of control flows,” in 33rd International Conference on Concurrency Theory (CONCUR 2022), 2022, vol. 243, pp. 8:1–8:16.

15. A. Kushnerov and S. Bystrov, “On Minimal Realization and Behavior of NCL Gates.” 2022, doi: 10.13140/RG.2.2.31525.47847.

16. A. Yakovlev and A. I. Petrov, “Symbolic Signal Transition Graphs and Asynchronous Circuit Design,” Newcastle University, 1992.

17. O. Coudert, “Two-level logic minimization: an overview,” Integration, vol. 17, no. 2, pp. 97–140, 1994.

18. V. I. Varshavsky, Ed., Aperiodic Automata. Nauka, 1976.

19. D. Sokolov, “Automated synthesis of asynchronous circuits using direct mapping for control and data paths,” PhD thesis, University of Newcastle upon Tyne, 2006.

20. J. Carmona, J. Cortadella, M. Kishinevsky, and A. Taubin, “Elastic circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 10, pp. 1437–1455, 2009.

21. D. Hammel, “Ideas of asynchronous feedback networks,” in Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, 1964, pp. 4–11.

22. V. I. Varshavsky, Ed., Self-timed control of concurrent processes. The design of aperiodic logical circuits in computers and discrete systems. Kluwer Academic Publishers, 1990.

23. T. Nanya, Y. Ueno, H. Kagotani, M. Kuwako, and A. Takamura, “TITAC: Design of a quasi-delay-insensitive microprocessor,” IEEE Design & Test of Computers, vol. 11, no. 2, pp. 50–63, 1994.

24. A. Mokhov, D. Sokolov, and A. Yakovlev, “Completion detection optimisation based on relative timing,” in Proceedings of the Eighteenth UK Asynchronous Forum, 2006, pp. 73–76.

25. B. Folco, V. Br'egier, L. Fesquet, and M. Renaudin, “Technology mapping for area optimized quasi delay insensitive circuits,” in Vlsi-Soc: From Systems To Silicon. IFIP International Federation for Information Proc, 2007, vol. 240, pp. 55–69.

26. C. L. Seitz, “System timing,” Introduction to VLSI systems, pp. 218–262, 1980.

27. W. Toms and D. Edwards, “Prime Indicants: a synthesis method for indicating combinational logic blocks,” in 15th IEEE Symposium on Asynchronous Circuits and Systems, 2009, pp. 139–150.

28. L. P. Plekhanov, “Synthesis of self-timed combinational sections using the functional method,” Systems and Means of Informatics, vol. 27, no. 2, pp. 85–97, 2017.

29. D. A. Duncan, G. E. Sobelman, and K. M. Fant, “Null convention adder.” 1998.

30. V. I. Varshavsky, A. Y. Kondratyev, V. A. Romanovsky, and B. S. Tsirlin, “Combinational adder.” 1988.

31. Y. Zhou, “Automatic synthesis and optimisation of asynchronous data paths using partial acknowledgement,” PhD thesis, University of Newcastle upon Tyne, 2008.

32. S. C. Smith, “Design of an FPGA logic element for implementing asynchronous NULL convention logic circuits,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 15, no. 6, pp. 672–683, 2007.

33. M.-C. Chang, P.-H. Yang, and Z.-G. Pan, “Register-less NULL convention logic,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 64, no. 3, pp. 314–318, 2016.

34. M. Kim, “Null convention logic circuits for asynchronous computer architecture,” PhD thesis, RMIT University, 2019.

35. B. S. Tsirlin, “An algebra of asynchronous logic networks,” Cybernetics, vol. 20, no. 1, pp. 23–29, 1984.

36. A. I. Bukhshtab et al., “Universal logic module.” 1977.

37. Y. Li, “Redressing Timing Issues for Speed-Independent Circuits in Deep Sub-micron Age,” PhD thesis, University of Newcastle upon Tyne, 2012.