Back to results
US 5,999,961 AGranted
Parallel prefix operations in asynchronous processors
AssigneeCalifornia Institute of Technology
InventorsRajit Manohar, Alain J. Martin
Life of this patent
Estimating the term…
Abstract
A circuit for performing prefix computation in an asynchronous digital processor by implementing a serial process and a tree process for the same prefix computation in parallel. The first output from either processes is selected and used for the subsequent operation. For a prefix computation with N inputs, an average-case latency of O(loglog N) can be achieved. Buffering can be used for a full-throughout operation.
Claims29
An asynchronous circuit for performing a prefix computation, comprising:
- a first prefix computation circuit having a plurality of input terminals to receive input data and a first circuit configuration to perform prefix computation based on said input data with a first latency, without a synchronizing clock signal;
- a second prefix computation circuit interconnected with said first prefix computation circuit and configured to have a second circuit configuration different from said first circuit configuration and to perform the prefix computation at least partly in parallel with said first prefix computation circuit based on said input data with a second latency, without a synchronizing click signal;
- at least one data link interconnecting said first and second prefix computation circuits to provide data exchange therebetween and to produce an averaged latency of O(loglogN) in completing the prefix computation, where N is the number of said inputs, wherein each prefix computation is carried out based on first-generated results from any of said first and second circuits, without an external control signal.
A method of performing a prefix computation, comprising:
- providing a circuit having at least first and second computation mechanisms which are operable to perform the prefix computation in parallel and without synchronizing to each other;
- performing the prefix computation with the first computation mechanism based on a set of input signals without a synchronizing clock signal;
- simultaneously performing the prefix computation with the second mechanism base on the input signals without a synchronizing clock signal;
- and
- selecting a first-generated result from any of the first and second mechanism, without an external control signal, to achieve an average-case latency O(log log N) of the first and second mechanism, where N is the number of inputs.
2 more elements
An asynchronous circuit, comprising:
- a first set of processing blocks connected with one another in series to form a serial processing circuit and configurated to operate on a plurality of input signals to produce an output with a first latency, wherein each processing block communicates with another processing block without synchronizing to a clock signal;
- and
- a second set of processing blocks connected with one another and with said first set of processing blocks to form a pipelined processing tree circuits with at least two levels, said pipelined processing tree circuit operable to process said input signals and to produce said output with a second latency, wherein said second set of processing blocks communicate with one another and said first set of processing blocks without synchronizing to a clock signal,
- wherein at least one processing block in each of said serial processing circuit and said pipelined processing tree circuit has a first input to receive a signal from another processing block in said serial processing circuit and a second input to receive the same signal from one processing block of said pipelined processing tree circuit, said at least one processing block operable to use one of said first and second inputs that first produces said signal to produce an output, without relying on a control signal,
- wherein all processing blocks in at least one level of said pipelined tree circuit are connected by said serial processing circuit so as to produce an average latency of O(log log N), where N is the number of inputs.
2 more elements
An asynchronous circuit, comprising:
- a plurality of input terminals to receive input signals;
- a plurality of processing blocks connected with one another to form a tree processing circuit with at least two levels a with respect to said input terminals, said tree processing circuits operable to process said input signals and to produce an output with a first latency, wherein said processing blocks are interconnected in a way to communicate with one another without synchronization to a clock signal;
- and
- a plurality of communication channels to connect all processing blocks in at least one level of said tree processing circuit to form a serial processing circuit which operates without synchronization to a clock signal and has a second latency,
- wherein at least one processing block in said serial processing circuit has a first input to receive a signal from another processing block in said serial processing circuit and a second input to receive the same signal from one processing block of another level of said tree processing circuit, said at least one processing block operable to use one of said first and second inputs that first produces said signal to produce an output,
- wherein said tree processing circuit and said serial processing circuit operate in combination to produce an average latency of O(log log N), where N is the number of inputs.
3 more elements
A method for processing input signal in an asynchronous manner, comprising:
- connecting a plurality of processing blocks to form a tree processing circuit which has at least two levels and operates without synchronization to a clock signal;
- processing the input signals by using the tree circuit to produce an output with a first latency;
- connecting all processing blocks in at least one level of the tree processing circuit to form a serial processing circuit which operates without synchronization to a clock signal and has a second latency;
- in at least one processing block in said serial processing circuit, selecting a first-generated signal between a signal from another processing block in said serial processing circuit and the same signal generated from another level of said tree processing circuit, to produce an output;
- and
- combining said tree processing circuit and said serial processing circuit to produce an average latency of O(log log N), where N is the number of inputs.
3 more elements
Dependencies are inferred from the claim text.