maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2023-2-170-186FPTYFCmais-1778Research ArticleComputing Methodologies and ApplicationsГрафы сигнальных переходов для схем асинхронного тракта данныхSignal Transition Graphs for Asynchronous Data Path Circuitshttps://orcid.org/0000-0003-3953-1995КушнеровАлександрKushnerovAlex

Беэр-Шева

Beer-Sheva

kushnero@gmail.comhttps://orcid.org/0009-0008-6525-0517БыстровСергейBystrovSergey

Сочи

Sochi

bsa1969@yandex.ruНезависимый исследовательIsraelНезависимый исследовательРоссияIndependent researcherRussian Federation202314062023302170186Copyright © Кушнеров А., Быстров С., 20232023Кушнеров А., Быстров С.Kushnerov A., Bystrov S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1778

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

The paper proposes a method for constructing signal transition graphs (STGs), which are directly mapped into asynchronous circuits for data processing. The advantage of the proposed method is that the resulting circuits are not only output-persistent, but also conformant to the environment. In other approaches, the environment is specified implicitly and/or inexactly and therefore they guarantee only output persistence. The conformation can be verified if both the circuit and its environment are specified by STGs. As an example, we consider a module realizing the function AND2. This module can either wait for both 1s or evaluate the function as soon as at least one 0 arrives. For each case, we draw up a separate STG (scenario) and map it into NCL gates. To provide such a mapping, we specify the behaviors of NCL gates by STG protocols. For data path, such an STG always contains alternative branches with the so-called garbage transitions at the gate inputs. The garbage transitions on a certain wire mean that the circuit is sensitive to the delay in this wire. Ignoring the garbage may lead to a violation of conformation or/and output persistence. For example, in the combinational part of the NCL circuits, the garbage appears on the inputs of NCL gates, and therefore these circuits are not delay insensitive.

арифметикаверификациядекомпозициязадержка в проводахконформностьпайплайнслабая причинностьхэндшейкarithmeticconformationdecompositiondelay in wireshandshakepipelineverificationweak causalityReferencesC. 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.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.D. E. Muller, “Asynchronous logics and application to information processing,” Switching Theory in Space Technology, vol. 4, pp. 289–297, 1963.D. E. Muller, “Asynchronous logics and application to information processing,” Switching Theory in Space Technology, vol. 4, pp. 289–297, 1963.A. Yakovlev, “Designing self-timed systems,” VLSI systems design, no. 9, pp. 70–90, 1985.A. Yakovlev, “Designing self-timed systems,” VLSI systems design, no. 9, pp. 70–90, 1985.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.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.S. Bystrov and A. Kushnerov, “Asynchronous data processing. Behavior analysis.” 2022, doi: 10.13140/RG.2.2.14748.26248.S. Bystrov and A. Kushnerov, “Asynchronous data processing. Behavior analysis.” 2022, doi: 10.13140/RG.2.2.14748.26248.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.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.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.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.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.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.J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev, Logic Synthesis for Asynchronous Controllers and Interfaces. Springer Science & Business Media, 2002.J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev, Logic Synthesis for Asynchronous Controllers and Interfaces. Springer Science & Business Media, 2002.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.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.V. Khomenko, M. Schaefer, and W. Vogler, “Output-determinacy and asynchronous circuit synthesis,” Fundamenta Informaticae, vol. 88, no. 4, pp. 541–579, 2008.V. Khomenko, M. Schaefer, and W. Vogler, “Output-determinacy and asynchronous circuit synthesis,” Fundamenta Informaticae, vol. 88, no. 4, pp. 541–579, 2008.K. M. Fant, Logically determined design: clockless system design with NULL convention logic. John Wiley & Sons, 2005.K. M. Fant, Logically determined design: clockless system design with NULL convention logic. John Wiley & Sons, 2005.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.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.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.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.A. Kushnerov and S. Bystrov, “On Minimal Realization and Behavior of NCL Gates.” 2022, doi: 10.13140/RG.2.2.31525.47847.A. Kushnerov and S. Bystrov, “On Minimal Realization and Behavior of NCL Gates.” 2022, doi: 10.13140/RG.2.2.31525.47847.A. Yakovlev and A. I. Petrov, “Symbolic Signal Transition Graphs and Asynchronous Circuit Design,” Newcastle University, 1992.A. Yakovlev and A. I. Petrov, “Symbolic Signal Transition Graphs and Asynchronous Circuit Design,” Newcastle University, 1992.O. Coudert, “Two-level logic minimization: an overview,” Integration, vol. 17, no. 2, pp. 97–140, 1994.O. Coudert, “Two-level logic minimization: an overview,” Integration, vol. 17, no. 2, pp. 97–140, 1994.V. I. Varshavsky, Ed., Aperiodic Automata. Nauka, 1976.V. I. Varshavsky, Ed., Aperiodic Automata. Nauka, 1976.D. Sokolov, “Automated synthesis of asynchronous circuits using direct mapping for control and data paths,” PhD thesis, University of Newcastle upon Tyne, 2006.D. Sokolov, “Automated synthesis of asynchronous circuits using direct mapping for control and data paths,” PhD thesis, University of Newcastle upon Tyne, 2006.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.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.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.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.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.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.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.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.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.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.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.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.C. L. Seitz, “System timing,” Introduction to VLSI systems, pp. 218–262, 1980.C. L. Seitz, “System timing,” Introduction to VLSI systems, pp. 218–262, 1980.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.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.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.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.D. A. Duncan, G. E. Sobelman, and K. M. Fant, “Null convention adder.” 1998.D. A. Duncan, G. E. Sobelman, and K. M. Fant, “Null convention adder.” 1998.V. I. Varshavsky, A. Y. Kondratyev, V. A. Romanovsky, and B. S. Tsirlin, “Combinational adder.” 1988.V. I. Varshavsky, A. Y. Kondratyev, V. A. Romanovsky, and B. S. Tsirlin, “Combinational adder.” 1988.Y. Zhou, “Automatic synthesis and optimisation of asynchronous data paths using partial acknowledgement,” PhD thesis, University of Newcastle upon Tyne, 2008.Y. Zhou, “Automatic synthesis and optimisation of asynchronous data paths using partial acknowledgement,” PhD thesis, University of Newcastle upon Tyne, 2008.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.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.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.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.M. Kim, “Null convention logic circuits for asynchronous computer architecture,” PhD thesis, RMIT University, 2019.M. Kim, “Null convention logic circuits for asynchronous computer architecture,” PhD thesis, RMIT University, 2019.B. S. Tsirlin, “An algebra of asynchronous logic networks,” Cybernetics, vol. 20, no. 1, pp. 23–29, 1984.B. S. Tsirlin, “An algebra of asynchronous logic networks,” Cybernetics, vol. 20, no. 1, pp. 23–29, 1984.A. I. Bukhshtab et al., “Universal logic module.” 1977.A. I. Bukhshtab et al., “Universal logic module.” 1977.Y. Li, “Redressing Timing Issues for Speed-Independent Circuits in Deep Sub-micron Age,” PhD thesis, University of Newcastle upon Tyne, 2012.Y. Li, “Redressing Timing Issues for Speed-Independent Circuits in Deep Sub-micron Age,” PhD thesis, University of Newcastle upon Tyne, 2012.

The authors declare that there are no conflicts of interest present.