Asynchronous completion prediction

• US 6,369,614 B1
• Filed: 05/25/2000
• Issued: 04/09/2002
• Est. Priority Date: 05/25/2000
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Ridgway, Stuart Alexander
• Primary Examiner(s): Tokar, Michael
• Assistant Examiner(s): Tan, Vibol
• Application Number:
  US09/579,855
• Time in Patent Office: 684 Days
• Field of Search: 326/93, 326/95, 326/98
• US Class Current: 326/93
• CPC Class Codes: G06F 7/5052 using carry completion detection, either over all stages or at sample stages only
• CPC Class Codes: G06F 9/3869 Implementation aspects, e.g. pipeline latches; pipeline synchronisation and clocking
• CPC Class Codes: G06F 9/3871 Asynchronous instruction pipeline, e.g. using handshake signals between stages

Abstract

A stage of a multi-stage, self-timed datapath circuit calculates one or more data outputs as a function of one or more data inputs. Data outputs are calculated by multiple logical elements that operate simultaneously and produce internal results as inputs to other logical elements within a stage. An internal completion signal generator detects completion of a predetermined set of the internal results calculation and, in response, generates an completion signal for each internal result detected. A done signal generator receives the completion signals and, in response to one or more preselected combinations of the completion signals, provides a done signal. The done signal is generated with a predetermined delay such that the delay is at least as long as a time it takes for the stage to calculate a final result.

Claims

1. A stage in a multi-stage, self-timed datapath circuit that calculates one or more data outputs as a function of one or more data inputs, the stage comprising:

digital logic having multiple logical elements that calculate both internal results for use as inputs to other logical elements within the stage and final results for use as inputs to logical elements in a next stage;

an internal completion signal generator, coupled with the digital logic, that detects completion by the digital logic of calculation of the internal results, and in response generates completion signals for at least one detected internal result; and

a done signal generator that receives the completion signals, and in response, generates a done signal with a predetermined delay after at least one predetermined combination of the completion signals has been received, wherein the predetermined delay is at least as long as a maximum delay until the one or more data outputs are calculated.

2. The stage according to claim 1, wherein the completion signals are voltage levels designated as “

true” and

generated by the internal completion signal generator to indicate that the result is complete, and the done signal generator calculates the AND of the completion signals.

3. The stage according to claim 1, wherein the completion signal is a transition signal generated by the completion signal generator to indicate that the result is complete, and the done signal generator includes one or more C-elements.

4. A stage in a multi-stage, self-timed datapath circuit, comprising:

digital logic having multiple logical elements that receive one or more data inputs and calculate both internal results for use as inputs to other logical elements within the stage and final results for use as inputs to logical elements in a next stage;

an internal completion signal generator, coupled with the digital logic, that detects completion by the digital logic of an internal result, and in response generates a completion signal for the internal result detected; and

a done signal generator that receives the completion signals, and in response to a preselected one of the completion signals, generates a done signal with a predetermined delay, wherein the predetermined delay is at least as long as a maximum delay until the one or more data outputs are calculated.

5. The stage according to claim 4, wherein the do ne signal generator further comprises:

a plurality of join elements, wherein each join element receives one of the completion signals and in response provides an intermediate done signal, there being a plurality of intermediate done signals;

a first-of element, responsive to one of the plurality of intermediate done signals, that generates said done signal.

6. The stage according to claim 5 wherein the first-of element is an OR gate.

7. The stage according to claim 5 wherein the first-of element is a one-all gate.

8. The stage according to claim 4, wherein each completion signal includes a delay.

9. The stage according to claim 4 wherein each completion signal includes a plurality of intermediate data signals.

10. In a stage in a multi-stage, self-timed datapath circuit, wherein a datapath output is a function of one or more datapath inputs, a control circuit comprising:

an internal completion signal generator, coupled with the digital logic, that detects completion by the digital logic of an intermediate result of the multi-step calculation, and in response generates a completion signal; and

a done signal generator, responsive to the completion signal, that generates a done signal with a predetermined delay, said predetermined delaying being at least as long as a maximum time for the data logic to calculate the datapath output.

11. In a stage of a multi-stage, self-timed datapath circuit, wherein the stage includes logical elements that calculate both internal results for use as inputs to other logical elements within the stage and final results for use as inputs to other logical elements in a next stage, a method of predicting a total stage calculation comprising the steps of:

dividing the logic elements into multiple sections, each section performing a part of the total stage calculation to generate an internal result;

selecting at least one section;

monitoring the at least one selected section for the internal result; and

in response to the internal result, generating a completion signal with a delay that is at least as long as a maximum time for the logic elements to calculate a complete set of final results.