Signal transition graphs for asynchronous data path circuits

A. Kushnerov ; S. Bystrov

Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 2, pp. 170-186.

Résumé

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.

Détail

Keywords: arithmetic, delay in wires, handshake, pipeline, verification, weak causality.
Mots-clés : conformation, decomposition

Bibliographie

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

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

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

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

[5] S. Bystrov and A. Kushnerov, Asynchronous data processing. Behavior analysis, Preprint, 2022 https://www.researchgate.net/publication/362910934_Asynchronous_Data_Processing_Behavior_Analysis | DOI

[6] A. Kushnerov, M. Medina, and A. Yakovlev, “Towards hazard-free multiplexer based implementation of self-timed circuits”, 27th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC), 2021, 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, 5:2 (1971), 129–162 | DOI | MR | Zbl

[8] L. Y. Rosenblum and A. V. Yakovlev, “Signal graphs: from self-timed to timed ones”, International Workshop on Timed Petri Nets, 1985, 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 | Zbl

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

[11] V. Khomenko, M. Schaefer, and W. Vogler, “Output-determinacy and asynchronous circuit synthesis”, Fundamenta Informaticae, 88:4 (2008), 541–579 | MR | Zbl

[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, 9 (1996), 189–233 | DOI

[14] V. Khomenko, M. Koutny, and A. Yakovlev, “Slimming down Petri boxes: Compact Petri net models of control flows”, 33rd International Conference on Concurrency Theory (CONCUR 2022), Leibniz International Proceedings in Informatics (LIPIcs), 243, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2022, 8:1–8:16 | MR

[15] A. Kushnerov and S. Bystrov, On Minimal Realization and Behavior of NCL Gates, Preprint, 2022 https://www.researchgate.net/publication/363918158_On_Minimal_Realization_and_Behavior_of_NCL_Gates | DOI

[16] A. Yakovlev and A. I. Petrov, Symbolic Signal Transition Graphs and Asynchronous Circuit Design, Technical Report Series 395, Tech. Rep., Department of Computing Science, 1992, 40 pp.

[17] O. Coudert, “Two-level logic minimization: an overview”, Integration, 17:2 (1994), 97–140 | DOI | MR | Zbl

[18] V. I. Varshavsky (Ed.), Aperiodic Automata, Nauka, 1976 | MR | Zbl

[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, 28:10 (2009), 1437–1455 | DOI

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

[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 | Zbl

[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, 11:2 (1994), 50–63 | DOI

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

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

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

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

[28] L. P. Plekhanov, “Synthesis of self-timed combinational sections using the functional method”, Systems and Means of Informatics, 27:2 (2017), 85–97

[29] D. A. Duncan, G. E. Sobelman, and K. M. Fant, Null convention adder, US Patent 5,793,662, 1998

[30] V. I. Varshavsky, A. Y. Kondratyev, V. A. Romanovsky, and B. S. Tsirlin, Combinational adder, USSR author's certificate SU1596321, 1988 | Zbl

[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, 15:6 (2007), 672–683 | DOI

[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, 64:3 (2016), 314–318 | DOI

[34] M. Kim, Null convention logic circuits for asynchronous computer architecture, PhD thesis, RMIT University, 2019 | Zbl

[35] B. S. Tsirlin, “An algebra of asynchronous logic networks”, Cybernetics, 20:1 (1984), 23–29 | DOI | MR | Zbl

[36] A. I. Bukhshtab et al., Universal logic module, USSR author's certificate SU561182, 1977

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