Source: http://www.google.com/patents/US6038656?dq=6181294
Timestamp: 2014-03-16 06:28:59
Document Index: 104223007

Matched Legal Cases: ['art 112', 'art 114', 'art 112', 'art 114', 'art 122', 'art 112', 'art 122', 'art 124']

Patent US6038656 - Pipelined completion for asynchronous communication - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsAn asynchronous circuit having a pipelined completion mechanism to achieve improved throughput....http://www.google.com/patents/US6038656?utm_source=gb-gplus-sharePatent US6038656 - Pipelined completion for asynchronous communicationAdvanced Patent SearchPublication numberUS6038656 APublication typeGrantApplication numberUS 09/151,334Publication dateMar 14, 2000Filing dateSep 11, 1998Priority dateSep 12, 1997Fee statusPaidPublication number09151334, 151334, US 6038656 A, US 6038656A, US-A-6038656, US6038656 A, US6038656AInventorsUri V. Cummings, Andrew M. Lines, Alain J. MartinOriginal AssigneeCalifornia Institute Of TechnologyExport CitationBiBTeX, EndNote, RefManPatent Citations (4), Non-Patent Citations (29), Referenced by (30), Classifications (8), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetPipelined completion for asynchronous communicationUS 6038656 AAbstract An asynchronous circuit having a pipelined completion mechanism to achieve improved throughput.
More specifically, one way to reduce the delay in the completion tree uses asynchronous pipelining to decompose a long critical cycle in a datapath into two or more short cycles. One or more decoupling buffers may be disposed in the datapath between two pipelined stages. Another way to reduce the delay in the completion tree is to reduce the delay caused by distribution of a signal to all N bits in an N-bit datapath. Such delay can be significant when N is large. The N-bit datapath can also be partitioned into m small datapaths of n bits (N=m parallel to one another. These m small datapaths can transmit data simultaneously. Accordingly, each N-bit processing stage can also be replaced by m small processing blocks of n bits.
The first stage 110 includes a register part R.sub.A, 112, and a control part "C.sub.A ", 114. The register part 112 stores data to be sent to the second stage 120. The control part 114 generates an internal control parameter "x" 116 to control the register part 112 and the data channels 130, e.g., triggering sending data or resetting the data channels 130. The control part 114 also controls data processing in the first stage 110 which generates the data to be sent to the second stage 120. The second stage 120 includes a register part 122 that stores received data from register part 112, a control part "C.sub.B ", 124, that generates the request/acknowledgment signal ra over the channel 140 and controls data processing in the second stage, 120 and a completion tree 126 that connects the register part 122 and the control part 124.
Consider an N-bit datum, D that is transmitted from the first stage 110 to the second stage 120. The completion signal y is generated when all the bits encoded into D have been written into the register 122 from the register 112. For each bit b.sub.k (k=0, 1, . . . , N-1), a write-acknowledgment signal, wack.sub.k, is generated. When all write-acknowledgment signals are raised, y can be raised to produce the completion signal y. Similarly, wack.sub.k is lowered when the corresponding bit b.sub.x is reset to its neutral value according to a chosen delay-insensitive protocol. Hence, y can be reset to zero when all write-acknowledgment signals are reset to zero (the neutral value). This can be expressed as the following: ##EQU2## where the notation "" represents negation, thus if wack.sub.o represents a "high", wack.sub.0 represents a "low".
The above technique of decomposing a long cycle into two or more pipelined short cycles can reduce the delay along the datapath of a pipeline. However, this does not address another delay caused by distribution of a signal to all N bits in an N-bit datapath, e.g., controlling bits in a 32-bit register that sends out data (e.g., the register 112 in the stage 110). Such delay can also be significant, specially when N is large (e.g., 32 or 64 or even 128). Hence, in addition to adding additional pipelined stages along a datapath, an N-bit datapath can also be partitioned into m small datapaths of n bits (N=m delay. These m small datapaths are connected parallel to one another and can transmit data simultaneously relative to one another. Accordingly, the N-bit register of a stage in the N-bit datapath can also be replaced by m small registers of n bits. The number m and thereby n are determined by the processing tasks of the two communicating stages. A 32-bit datapath, for example, can be decomposed into four 8-bit blocks, or eight 4-bit blocks, or sixteen 2-bit blocks, or even thirty-two 1-bit blocks to achieve a desired performance.
FIG. 6 shows one embodiment of a copy tree for a stage that has k data cells. This copy tree is used for both distributing k control signals from the control part (e.g., 114 in FIG. 4) to all data cells and merging k signals from all data cells to the control part. The signals r.sub.1, s.sub.i, are signals going to data cells, (l≦i≦k), as requests to receive or send. The completion signal ct.sub.i comes from data cell i, as a request/acknowledgment signal. One advantage of this copy tree is that only one completion tree is needed to perform the functions of the two completion trees 410 and 420 in FIG. 4.
The copy tree shown in FIG. 6 is only an example. Other configurations are possible. In general, a program specification of a copy tree for both sending and receiving is as follows: ##EQU4## where C is the channel shared with the control, D.sub.1 . . . D.sub.x are the channels to each data cell, and c is the value encoding the request (receive, send, etc.). The different alternatives for the buffer correspond to the different implementations of the semicolon.
In the above circuits, each data cell i contains a control part that communicates with a respective copy tree through the channel D.sub.i. In certain applications, the copy tree and the control for each data cell may be eliminated.
Consider a data cell i that receives data from a channel L.sup.i, and sends out data to a channel R.sup.i. Assuming that the requests from the copy tree to the data cells are just receive ("r") or send ("s"), a program specification of data cell i is: ##EQU5##
The program generalizes obviously to any number of requests. Again, we have the choice among all possible implementations of the semicolon (the buffer between channel D.sub.i and channel Li or Ri). If the sequence of requests is entirely deterministic, like in the case of a buffer: r,s,r,s, . . . , there is no need for each data cell to communicate with a central control process through the copy tree. The fixed sequence of requests can be directly encoded in the control of each data cell, thereby eliminating the central control and the copy tree. Hence, the control is entirely distributed among the data cells. A central control process is usually kept when the sequence of send and receive actions in the data cells is data dependent.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3290511 *Aug 19, 1960Dec 6, 1966Sperry Rand CorpHigh speed asynchronous computerUS5574925 *May 27, 1992Nov 12, 1996The Victoria University Of ManchesterAsynchronous pipeline having condition detection among stages in the pipelineUS5732233 *Jan 23, 1995Mar 24, 1998International Business Machines CorporationHigh speed pipeline method and apparatusUS5752070 *Jul 8, 1994May 12, 1998California Institute Of TechnologyAsynchronous processors* Cited by examinerNon-Patent CitationsReference1Burns et al., "Syntax-directed Translation of Concurrent programs into Self-timed Circuits", Advanced Research in VLSI. Proceedings of the 50th MIT Conference. MIT Press, pp. 35-50, 1988.2Burns et al., "Synthesis of self-timed Circuits by Program Translation", The Fusion of hardware Design and Verification, pp. 1-18, 1988.3 *Burns et al., Syntax directed Translation of Concurrent programs into Self timed Circuits , Advanced Research in VLSI. Proceedings of the 50th MIT Conference. MIT Press, pp. 35 50, 1988.4 *Burns et al., Syntax directed Translation of Concurrent Programs into Self timed Circuits, 1988, Advanced Research in VLSI. Proceedings of the 5th MIT Conference.5Burns et al., Syntax-directed Translation of Concurrent Programs into Self-timed Circuits, 1988, Advanced Research in VLSI. Proceedings of the 5th MIT Conference.6 *Burns et al., Synthesis of Self Timed Circuits by Program Transformation, 1988, The Fusion of Hardware Design and Verification.7 *Burns et al., Synthesis of self timed Circuits by Program Translation , The Fusion of hardware Design and Verification, pp. 1 18, 1988.8Burns et al., Synthesis of Self-Timed Circuits by Program Transformation, 1988, The Fusion of Hardware Design and Verification.9Cho et al., "Design of a 32-bit fully asynchronous microprocessor (FAM)", Proceedings of the 35th Midwest Symposium on Circuits and Systems, pp. 1500-1503, vol. 2, Aug. 1992.10 *Cho et al., Design of a 32 bit fully asynchronous microprocessor (FAM) , Proceedings of the 35th Midwest Symposium on Circuits and Systems, pp. 1500 1503, vol. 2, Aug. 1992.11 *Cho et al., Design of a 32 bit Fully Asynchronous Microprocessor (FAM), Aug. 1992, Proceedings of the 35th Midwest Symposium on Circuits and Systems.12Cho et al., Design of a 32-bit Fully Asynchronous Microprocessor (FAM), Aug. 1992, Proceedings of the 35th Midwest Symposium on Circuits and Systems.13Endecott, "Superscalar instruction issue in an asynchronous microprocessor", IEEE Proceedings on Computers and Design Techniques, pp. 266-272, Sep. 1996.14 *Endecott, Superscalar instruction issue in an asynchronous microprocessor , IEEE Proceedings on Computers and Design Techniques, pp. 266 272, Sep. 1996.15 *Endecott, Superscalar Instruction Issue in an Asynchronous Microprocessor, Jun. 1996, Computers and Digital Techniques, IEEE Proceedings.16Furber et al., "Dynamic logic in four-phase micropipelines", Proceedings, 2nd International Symposium on Advances Research in Asynchronous Circuits and systems., pp. 11-16, Mar. 1996.17 *Furber et al., Dynamic logic in four phase micropipelines , Proceedings, 2nd International Symposium on Advances Research in Asynchronous Circuits and systems., pp. 11 16, Mar. 1996.18 *Furber et al., Dynamic Logic in Four Phase Micropipelines, Mar. 1996, 2nd International Symposium on Advanced Research in Asynchronous Circuits and Systems.19Furber et al., Dynamic Logic in Four-Phase Micropipelines, Mar. 1996, 2nd International Symposium on Advanced Research in Asynchronous Circuits and Systems.20 *Furber et al., Four Phase Micropipeline Latch Control Circuits, Jun. 1996, IEEE Transactions on VLSI Systems.21Furber et al., Four-Phase Micropipeline Latch Control Circuits, Jun. 1996, IEEE Transactions on VLSI Systems.22Furber, "Four-phase micropipeline latch control circuits", IEEE Transactions on VLSI systems, pp. 247-253, Jun. 1996.23 *Furber, Four phase micropipeline latch control circuits , IEEE Transactions on VLSI systems, pp. 247 253, Jun. 1996.24 *Kearney et al., Performance Evaluation of Asynchronous Logic Pipelines with Data Dependent Processing Delays, May 1995, Proceedings, 2nd Working Conference on Asynchronous Design Methodologies.25Kearney, "Performance evaluation of asynchronous logic pipelines with data dependent processing", proceedings., 2nd Working Conference on Asynchronous Design methodologies, 4-13, May 1995.26 *Kearney, Performance evaluation of asynchronous logic pipelines with data dependent processing , proceedings., 2nd Working Conference on Asynchronous Design methodologies, 4 13, May 1995.27 *Martin, Asynchronous Datapaths and the Design of an Asynchronous Adder, Jun. 1991, Department of Computer Science, California Institute of Technology.28Martin., "Asynchronous datapaths and the design of an asynchronous adder", Dept. of Computer Science, California Institute of Technology. p. 1-23, Jun. 1996.29 *Martin., Asynchronous datapaths and the design of an asynchronous adder , Dept. of Computer Science, California Institute of Technology. p. 1 23, Jun. 1996.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS6148392 *Sep 8, 1998Nov 14, 2000Cogency Technology IncorporatedLow power implementation of an asynchronous stock having a constant response timeUS6369614 *May 25, 2000Apr 9, 2002Sun Microsystems, Inc.Asynchronous completion predictionUS6732336Oct 11, 2002May 4, 2004California Institute Of TechnologyMethod and apparatus for an asynchronous pulse logic circuitUS6854096Jul 14, 2003Feb 8, 2005Fulcrum Microsystems, Inc.Optimization of cell subtypes in a hierarchical design flowUS6950959Aug 1, 2002Sep 27, 2005Fulcrum Microystems Inc.Techniques for facilitating conversion between asynchronous and synchronous domainsUS6961863Oct 25, 2002Nov 1, 2005Fulcrum Microsystems Inc.Techniques for facilitating conversion between asynchronous and synchronous domainsUS7028107Oct 7, 2002Apr 11, 2006Pact Xpp Technologies AgProcess for automatic dynamic reloading of data flow processors (DFPS) and units with two- or three- dimensional programmable cell architectures (FPGAS, DPGAS, and the like)US7050324Jul 13, 2004May 23, 2006Fulcrum Microsystems, Inc.Asynchronous static random access memoryUS7124280 *Apr 13, 2001Oct 17, 2006Sharp Kabushiki KaishaExecution control apparatus of data driven information processor for instruction inputsUS7161828Aug 9, 2005Jan 9, 2007Fulcrum Microsystems, Inc.Asynchronous static random access memoryUS7239669Aug 4, 2003Jul 3, 2007Fulcrum Microsystems, Inc.Asynchronous system-on-a-chip interconnectUS7260753Jul 25, 2003Aug 21, 2007Fulcrum Microsystems, Inc.Methods and apparatus for providing test access to asynchronous circuits and systemsUS7274709Sep 6, 2002Sep 25, 2007Fulcrum Microsystems, Inc.Asynchronous crossbar with deterministic or arbitrated controlUS7274710Sep 6, 2002Sep 25, 2007Fulcrum Microsystems, Inc.Asynchronous crossbar with deterministic or arbitrated controlUS7283557Apr 30, 2002Oct 16, 2007Fulcrum Microsystems, Inc.Asynchronous crossbar with deterministic or arbitrated controlUS7584449Nov 10, 2005Sep 1, 2009Fulcrum Microsystems, Inc.Logic synthesis of multi-level domino asynchronous pipelinesUS7698535 *Sep 16, 2003Apr 13, 2010Fulcrum Microsystems, Inc.Asynchronous multiple-order issue system architectureUS7814280Aug 18, 2005Oct 12, 2010Fulcrum Microsystems Inc.Shared-memory switch fabric architectureUS7934031May 11, 2006Apr 26, 2011California Institute Of TechnologyReshuffled communications processes in pipelined asynchronous circuitsUS7971038 *Sep 4, 2006Jun 28, 2011Nxp B.V.Asynchronous ripple pipelineUS8051396May 4, 2009Nov 1, 2011Fulcrum Microsystems, Inc.Logic synthesis of multi-level domino asynchronous pipelinesUS8370557Dec 19, 2008Feb 5, 2013Intel CorporationPseudo dual-port SRAM and a shared memory switch using multiple memory banks and a sideband memoryUS8467342Jan 6, 2011Jun 18, 2013Intel CorporationFlow and congestion control in switch architectures for multi-hop, memory efficient fabricsEP1647030A2 *Jul 13, 2004Apr 19, 2006Fulcrum Microsystems Inc.Asynchronous static random access memoryWO2000005644A1 *Jul 22, 1999Feb 3, 2000California Inst Of TechnReshuffled communications processes in pipelined asynchronous circuitsWO2002069164A2 *Feb 20, 2002Sep 6, 2002IbmSynchronous to asynchronous to synchronous interfaceWO2002071249A2 *Mar 5, 2002Sep 12, 2002Pact Inf Tech GmbhMethod and devices for treating and/or processing dataWO2003065236A1Jan 21, 2003Aug 7, 2003Fulcrum Microsystems IncAsynchronous crossbar with deterministic or arbitrated controlWO2004070781A2Jan 26, 2004Aug 19, 2004Uri CummingsAsynchronous system-on-a-chip interconnectWO2005008672A2Jul 13, 2004Jan 27, 2005Uri CummingsAsynchronous static random access memory* Cited by examinerClassifications U.S. Classification712/211, 712/18, 712/25, 712/201, 712/200International ClassificationG06F15/78Cooperative ClassificationG06F15/8053European ClassificationG06F15/80VLegal EventsDateCodeEventDescriptionAug 18, 2011FPAYFee paymentYear of fee payment: 12Aug 17, 2007FPAYFee paymentYear of fee payment: 8May 16, 2005ASAssignmentOwner name: ADD INC., CALIFORNIAFree format text: LICENSE;ASSIGNOR:CALIFORNIA INSTITUTE OF TECHNOLOGY;REEL/FRAME:016216/0334Effective date: 20010801Aug 19, 2003FPAYFee paymentYear of fee payment: 4Nov 10, 1998ASAssignmentOwner name: CALIFORNIA INSTITUTE OF TECHNOLOGY, CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:MARTIN, ALAIN J.;LINES, ANDREW M.;CUMMINGS, URI V.;REEL/FRAME:009595/0699;SIGNING DATES FROM 19981104 TO 19981109RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google