Content deleted Content added
No edit summary |
No edit summary |
||
Line 3:
[[Image:Timing diagram of inclusive OR.png|thumb|upright=1.5|Timing diagram of a C-element and inclusive OR gate]]
[[Image:Join_element_stg.png|thumb|upright=1.5|Behavior of the environment with multiple input transitions <ref name="Kim71">I. Kimura, "[https://www.sciencedirect.com/science/article/pii/S0022000071800314?via%3Dihub 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.</ref> (garbage branches <ref>A. Kushnerov and S. Bystrov, "[https://www.researchgate.net/profile/Alexander-Kushnerov/publication/371584542_Signal_Transition_Graphs_for_Asynchronous_Data_Path_Circuits/links/64918e63c41fb852dd1a1021/Signal-Transition-Graphs-for-Asynchronous-Data-Path-Circuits.pdf Signal transition graphs for asynchronous data path circuits]," Modeling and Analysis of Information Systems, vol. 30, no. 2, pp. 170-186, 2023.</ref>) admissible for C-element and inadmissible for Join element]]
[[Image:Realizations_of_C_element.png|thumb|upright=1.8|Majority-gate realization of C-element and inclusive OR gate (a); Realizations proposed by Maevsky (b), Tsirlin (c) and Murphy (d)]]▼
[[Image:Single_gate_C_elements.png|thumb|upright=2.2|Static implementations of two- and three-input C-element<ref>I. E. Sutherland, [http://f-cpu.seul.org/new/micropipelines.pdf "Micropipelines]", Communications of the ACM, vol. 32, no. 6, pp. 720–738, 1989.</ref><ref>C. H. van Berkel, [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=380B231B55BB4F45F6E4B72D4D273D44?doi=10.1.1.72.3108&rep=rep1&type=pdf "Beware the isochronic fork"], Report UR 003/91, Philips Research Laboratories, 1991.</ref>,<ref name="Mar10">V. B. Marakhovsky, [http://elib.spbstu.ru/dl/1945.pdf/download/1945.pdf Logic design of asynchronous circuits]. Slides on the course. CS&SE Department, SPbPU.</ref>]]▼
[[Image:Dual-rail C-element.png|thumb|upright=1.5|An STG of dual-rail C-element with 00 transit and its circuit realized only on NAND2 as a particular case of<ref name="Varsh85" /> considered by V.B. Marakhovsky.]]▼
[[Image:David cell graph.png|thumb|upright=1.7|David cell (a) and its fast implementations: gate-level (b) and transistor-level (c)<ref>A. Bystrov, A. Yakovlev, [http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=9FB34454CF987BC939FF0377A3EAD0BB?doi=10.1.1.16.5667&rep=rep1&type=pdf Asynchronous circuit synthesis by direct mapping: Interfacing to environment]. Technical Report, CS Department, University of Newcastle upon Tyne, October 2001.</ref>]]▼
In [[Logic gate|digital computing]], the Muller '''C-element''' ('''C-gate''', '''hysteresis flip-flop''', '''coincident flip-flop''', or '''two-hand safety circuit''') is a small binary [[sequential logic|logic circuit]] widely used in design of [[asynchronous circuit]]s and systems. It outputs 0 when all inputs are 0, it outputs 1 when all inputs are 1, and it retains its output state otherwise. It was specified formally in 1955 by [[David E. Muller]]<ref name="Mull55">D. E. Muller, [https://archive.org/stream/theoryofasynchro66mull#page/n3/mode/2up Theory of asynchronous circuits]. Report no. 66, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1955.</ref> and first used in [[ILLIAC II]] computer.<ref>H. C. Breadley, [http://bitsavers.informatik.uni-stuttgart.de/pdf/univOfIllinoisUrbana/illiac/ILLIAC_II/Brearley_ILLIAC_II_A_Short_Description_and_Annotated_Bibliography_Jun65.pdf "ILLIAC II — A short description and annotated bibliography"], IEEE Transactions on Electronic Computers, vol. EC-14, no. 3, pp. 399–403, 1965.</ref> In terms of the theory of [[Lattice (order)|lattices]], the C-element is a semimodular distributive circuit, whose operation in time is described by a [[Hasse diagram]].<ref name="Mul59">D. E. Muller and W. S. Bartky, [http://www.ee.bgu.ac.il/~kushnero/asynchronous/Muller_Bartky_1959.pdf "A theory of asynchronous circuits"], Int. Symposium on the Switching Theory in Harvard University, pp. 204–243, 1959.</ref><ref>W. J. Poppelbaum, [http://bitsavers.informatik.uni-stuttgart.de/pdf/univOfIllinoisUrbana/Poppelbaum_Introduction_to_the_Theory_of_Digital_Machines.pdf Introduction to the Theory of Digital Machines]. Math., E.E. 294 Lecture Notes, University of Illinois at Urbana-Champaign.</ref><ref name="Kim69">I. Kimura, "[https://www.jstor.org/stable/43698723 A comparison between two mathematical models of asynchronous circuits]," Science Reports of the Tokyo Kyoiku Daigaku, Section A 10, no. 232/248, 1969, pp. 109-123.</ref><ref>J. Gunawardena, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.3534&rep=rep1&type=pdf "A generalized event structure for the Muller unfolding of a safe net"], Int. Conference on Concurrency Theory (CONCUR) 1993, pp. 278–292.</ref> The C-element is closely related to the ''rendezvous''<ref>M. J. Stucki, S. M. Ornstein, W. A. Clark, [http://dl.acm.org/citation.cfm?doid=1465482.1465538 "Logical design of macromodules"], in Proceedings of AFIPS 1967, pp. 357–364.</ref> and ''join''<ref>J. C. Ebergen, J. Segers, I. Benko, [https://cs.uwaterloo.ca/research/tr/1994/10/CS94-10.pdf "Parallel Program and Asynchronous Circuit Design"], Workshops in Computing, pp. 50–103, 1995.</ref> elements, where an input is not allowed to change twice in succession. In some cases, when relations between delays are known, the C-element can be realized as a sum-of-product (SOP) circuit.<ref>[https://link.springer.com/article/10.1023%2FA%3A1008666605437?LI=true P.A. Beerel, J.R. Burch and T.H. Meng,"Checking combinational equivalence of speed-independent circuits," Formal Methods in System Design, vol. 13, no. 1, pp. 37-85, 1998.]</ref><ref>H. Park, A. He, M. Roncken and X. Song, [http://pdxscholar.library.pdx.edu/cgi/viewcontent.cgi?article=1306&context=ece_fac "Semi-modular delay model revisited in context of relative timing"], IET Electronics Letters, vol. 51, no. 4, pp. 332–334, 2015.</ref> Earlier techniques for implementing the C-element<ref>[https://archive.org/stream/quarterlytechnic1959univ#page/n5/mode/2up Technical Progress Report, Jan. 1959], University of Illinois at Urbana-Champaign.</ref><ref name="Pop59">W . J. Poppellbaum, N. E. Wiseman, [https://archive.org/stream/circuitdesignfor90popp#page/n5/mode/2up "Circuit design for the new Illinois computer"], Report no. 90, University of Illinois at Urbana-Champaign, 1959.</ref> include [[Schmitt trigger]],<ref>N. P. Singh, [http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-258.pdf A design methodology for self-timed systems]. MSc thesis, MIT, 1981, 98 p.</ref> Eccles-Jordan flip-flop and last moving point flip-flop.
Line 65 ⟶ 61:
===Gate-level implementations===
▲[[Image:Realizations_of_C_element.png|thumb|upright=1.8|Majority-gate realization of C-element and inclusive OR gate (a); Realizations proposed by Maevsky (b), Tsirlin (c) and Murphy (d)]]
▲[[Image:Single_gate_C_elements.png|thumb|upright=2.2|Static implementations of two- and three-input C-element<ref>I. E. Sutherland, [http://f-cpu.seul.org/new/micropipelines.pdf "Micropipelines]", Communications of the ACM, vol. 32, no. 6, pp. 720–738, 1989.</ref><ref>C. H. van Berkel, [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=380B231B55BB4F45F6E4B72D4D273D44?doi=10.1.1.72.3108&rep=rep1&type=pdf "Beware the isochronic fork"], Report UR 003/91, Philips Research Laboratories, 1991.</ref>,<ref name="Mar10">V. B. Marakhovsky, [http://elib.spbstu.ru/dl/1945.pdf/download/1945.pdf Logic design of asynchronous circuits]. Slides on the course. CS&SE Department, SPbPU.</ref>]]
▲[[Image:Dual-rail C-element.png|thumb|upright=1.5|An STG of dual-rail C-element with 00 transit and its circuit realized only on NAND2 as a particular case of<ref name="Varsh85" /> considered by V.B. Marakhovsky.]]
▲[[Image:David cell graph.png|thumb|upright=1.7|David cell (a) and its fast implementations: gate-level (b) and transistor-level (c)<ref>A. Bystrov, A. Yakovlev, [http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=9FB34454CF987BC939FF0377A3EAD0BB?doi=10.1.1.16.5667&rep=rep1&type=pdf Asynchronous circuit synthesis by direct mapping: Interfacing to environment]. Technical Report, CS Department, University of Newcastle upon Tyne, October 2001.</ref>]]
There is a number of different single-output circuits of C-element built on logic gates.<ref>B. S. Tsirlin, [https://patentimages.storage.googleapis.com/bd/d8/4b/81b12c002a0615/SU1096759A1.pdf "H flip-flop"], USSR author's certificate SU1096759, Jun. 7, 1984.</ref><ref>B. S. Tsirlin, [https://patentimages.storage.googleapis.com/b1/bf/92/42303ee73cf5ac/SU1162019A1.pdf "Multiple input H flip-flop"], USSR author's certificate SU1162019, Jun. 15, 1985.</ref> In particular, the so-called Maevsky's implementation <ref name="Kuwa94">M. Kuwako, T. Nanya, [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=656283 "Timing-reliability evaluation of asynchronous circuits based on different delay models"], IEEE Int. Symposium on Advanced Research in Asynchronous Circuits and Systems (ASYNC) 1994, pp. 22–31.</ref><ref name="Brz95">J. A. Brzozowski, K. Raahemifar, [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=514652 "Testing C-elements is not elementary"], Working Conference on Asynchronous Design Methodologies (ASYNC) 1995, pp. 150–159.</ref><ref>P. A. Beerel, J. R. Burch, T. H. Meng, [https://link.springer.com/article/10.1023/A:1008666605437 "Checking combinational equivalence of speed-independent circuits"], Formal Methods in System Design, vol. 13, no. 1, 1998, pp. 37–85.</ref> is a semimodular, but non-distributive (OR-causal) circuit loosely based on.<ref>V. I. Varshavsky, O. V. Maevsky, Yu. V. Mamrukov, B. S. Tsirlin, [https://patentimages.storage.googleapis.com/fb/81/d2/fa3a9d86aa6917/SU1081801A1.pdf "H flip-flop"], USSR author's certificate SU1081801, Mar. 23, 1984</ref> The NAND3 gate in this circuit can be replaced by two NAND2 gates. Note that Maevsky's C-element is actually a Join element, whose input signals cannot switch twice.<ref name="Kuwa94"/> Yet another circuit with OR-causality, which operates as a Join element.<ref>G. S. Brailovsky, L. Ya. Rozenblyum, B. S. Tsirlin, [https://patentimages.storage.googleapis.com/41/1a/f8/394838c3c7d619/SU1432733A1.pdf "H-flip-flop"], USSR author's certificate SU1432733, Oct. 23, 1988.</ref> A realization of C-element on two-input gates only has been proposed by Tsirlin <ref>B. S. Tsirlin, [https://patentimages.storage.googleapis.com/d0/78/f9/43bc147866ddb5/SU1324106A1.pdf "H-flip-flop"], USSR author's certificate SU1324106, Jul. 15, 1987.</ref> and then synthesized by Starodoubtsev et al. using Taxogram language<ref name="Star04">N. A. Starodoubtsev, S. A. Bystrov, [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1354042&matchBoolean=true&searchWithin%5B%5D=%22Last+Name%22%3Astarodoubtsev&newsearch=true "Monotonic behavior refinement for synthesis of two-input-gate asynchronous circuits"], IEEE Int. Midwest Symposium on Circuits and Systems (MWSCAS) 2004, vol. I, pp. I-521–524.</ref> This circuit coincides with that attributed to Bartky
<ref name="Kim71" />,<ref name="Kuwa94" /> and can operate without the input latch. Yet another version of the C-element built on two [[RS latch#Simple set-reset latches|SR-latches]] has been synthesized by Murphy<ref>J. P. Murphy, [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6317230 "Design of latch-based C-element"], Electronics Letters, vol. 48, no. 19, 2012, pp. 1190–1191.</ref> using Petrify tool. However, this circuit includes inverter connected to one of the inputs. This inverter should have small delay. However, there are realizations of RS latches that already have one inverted input, for example.<ref>V. A. Maksimov and Ya. Ya. Petrichkovich [https://yandex.ru/patents/doc/SU1164867A1_19850630 "RS flip-flop,"] USSR author's certificate SU1164867, Jun. 30, 1985.</ref> Some speed-independent approaches<ref>P. Beerel and T. H.-Y. Meng. [http://dl.acm.org/citation.cfm?id=304171 "Automatic gate-level synthesis of speed-independent circuits"], IEEE/ACM Int. Conference on Computer-Aided Design (ICCAD) 1992, pp. 581–587.</ref><ref>A. Kondratyev, M. Kishinevsky, B. Lin, P. Vanbekbergen, and A. Yakovlev, [http://dl.acm.org/citation.cfm?id=196275 "Basic gate implementation of speed-independent circuits"], ACM Design Automation Conference (DAC) 1994, pp. 56–62.</ref> assume that zero-delay input inverters are available on all gates, which is a violation of true speed-independence but is fairly safe in practice. Other examples of using this assumption also exist.<ref>A. V. Yakovlev, A. M. Koelmans, A. Semenov, D. J. Kinniment, [http://www.sciencedirect.com/science/article/pii/S0167926096000107 "Modelling, analysis and synthesis of asynchronous control circuits using Petri nets"], Integration, the VLSI Journal, vol. 21, no. 3, pp. 143—170, 1996.</ref>
| |||