High Speed Pipeline Method and Apparatus

A pipeline processor system is disclosed. More particularly an asynchronous pipeline incorporating very high speed, event-driven control elements is disclosed.

In digital signal processing, arithmetic computation, and instruction interpretation applications it is common to process data in stages where the processing result of one stage is passed to a subsequent stage for further processing by connecting a number of processors together as a series of stages with the stages operating on data as the data passes along from one stage to the next. A pipeline processor (also referred to simply as a pipeline) is one of these devices having a series of interconnected processing stages, where the stages may operate concurrently. For purposes of this discussion it will be assumed that a pipeline has a beginning and ending stage with at least one intermediate stage therebetween.

There are a variety of distinctions among pipeline processors. One distinction concerns whether the processor stages act in unison based on an external clock (a "synchronous" pipeline) or whether they may act independently based on local events (an "asynchronous" or "event-driven" pipeline).

In an event-driven pipeline an intermediate stage takes in new data whenever the stage has processed its data, the stage which follows it has taken the processed data, and the stage which precedes it has new data ready. Thus, in this type of pipeline, once the pipeline has been initialized an intermediate stage may be controlled solely with information from adjacent stages.

It is well known to use control elements known as Muller C-elements for pipeline control. See, e.g., Sutherland, Micropipelines, 32 Communications of the ACM 720 (1989). The operation of a Muller C-element is relatively simple. It is commonly understood by the person of ordinary skill in the art that more complicated control elements may be designed. See, e.g. Sutherland, Asynchronous Pipelined Data Processing System, U.S. Pat. No. 5,187,800 (1993). The output of a two input Muller C-element changes state, regardless of its previous state, only after both inputs have changed state. Otherwise, the Muller C-element retains its previous state. A configuration of Boolean logic gates which provides a two-input Muller C-element is shown in the FIG. 1 and is stated in the following Boolean algebra terms:

where Q.sub.n refers to the output state at a time t.sub.n, and Q.sub.n-1 refers to the output state immediately preceding the state at time t.sub.n.

It can be seen by inspection that the configuration of FIG. 1 provides an output which changes state only after both inputs have changed. That is, if both A and B are high then the output is high, and if both A and B are low then the output is low. Thereafter, if either A or B changes state, so that one, but not both, are high, the output remains unchanged at Q.sub.n-1. when both A and B have changed from high to low, or from low to high, the output also changes from high to low, or from low to high, as the case may be. A typical circuit diagram for the Muller C-element of FIG. 1 is shown in FIG. 2A.

The Muller C-element has quite a number of components. This tends to slow down operation of the device. In the circuit of FIG. 2 the "acknowledge" input switches four field effect transistors, Q1, Q4, Q7 and Q10, the "request" input switches four other FET's, Q2, Q3, Q5 and Q6. These input FET's switch two output FET's, Q11 and Q12, which in turn switch two holding FET's, Q8 and Q9.

Also, the particular type of transistor tends to slow down operation of the Muller C-element. In order to cause the output FET's to switch, each input signal must switch four FET's consisting of two complementary pairs of FET's, an n-type and a p-type FET in each pair. P-type FET's generally switch much slower than the n-type due to the requirement that for a given conductance a p-type FET must be approximately twice as large as an n-type FET.

Finally the configuration of the components tends to slow down operation of the Muller C-element. That is, in order to switch the output FET's, the particular input FET's that must switch include a FET that is in series with other FET's. For example, with the output low in the control element in FIG. 2A, and with the acknowledge signal high and request signal low, in order to switch the output FET's, Q11 and Q12, the acknowledge signal must switch Q1 on and Q10 off. The switching of Q10 is especially slow not only because it is a p-type FET, but also because it is stacked in series with a number of other FET's.

Thus, although a Muller C-element is relatively simple, the speed of a pipeline controlled by a Muller C-element may be somewhat impaired by the relatively slow operation of the control element.

A data processing apparatus has a number of data processors connected by data lines in a series so that data signals are processed in a preceding processor and communicated to a succeeding processor in the series. The term "processor" and the term "stage" may be used interchangeably herein, so that a processor having a series of stages may also be referred to as a series of processors. Furthermore the term "processor" as used herein should be understood to include buffers which merely perform a storage function, so that reference to a series of processors may include a shift register or series of shift registers. The apparatus has a number of reduced-state control elements, where a control element has first and second inputs receiving processor status signals and an output sending a signal to enable processing. The output assumes a certain output state only if both inputs assume that same state. The output, having assumed the state, remains in that state, despite a specified one of the inputs switching states, only if the other one of the inputs remains in the state.

In accordance with another aspect of the invention, the control element has a number of input FET's switched by the input signals, including a single PET providing the first input, and has a pair of output FET's connected to, and switched by, the input FET's providing the control element output. The output state of the control element may be changed by an input signal switching just the first input FET, and the first input FET switching just the output FET pair.

In a further aspect of the invention, the data lines include data input lines and data output lines for communicating input data signals and output data signals. A processor has an active interval. During the active interval the data signals are processed in a preceding processor and communicated to a succeeding processor. Only signals on the processor data output lines during the processor active interval and after completion of processing represent active output data. The control element first input indicates whether the data output lines of one processor have active data. The control element second input indicates whether the data output lines of another processor have active data. The control element enables processing in still another processor when the control element first input indicates active data, and the control element second input indicates no active data. Once the control element has enabled the processing, the control element continues to enable the processing until the control element second input indicates active data.

A further aspect of the invention, is repeatedly processing data during a number of processor active intervals, where the active interval of one processor is asynchronous with the active interval of another processor.

An object of the invention is to process data at a very high speed in a series of processors under control of a reduced state, event-driven control element.

Still other objects and advantages of the present invention will become readily apparent to those skilled in this art from the following detailed description, The preferred embodiment of the invention is shown simply by way of illustration of the best mode contemplated of carrying out the invention. Other embodiments are possible and the details may be modified in various respects without departing from the invention. Accordingly the drawing and description are to be regarded as illustrative in nature, and not restrictive.

FIG. 1 is a two input Muller C-element logic representation (prior art).

FIG. 2A is a circuit diagram for the Muller C-element of FIG. 1 (prior art).

FIG. 2B is a circuit diagram for the Muller C-element with a "clear" input.

FIG. 3 is a block diagram of the pipeline of the present invention.

FIG. 4 is a typical processor block of FIG. 3.

FIG. 5 is a typical controller of FIG. 3, which includes the control element of the present invention.

FIG. 6 is a logic representation of the control element.

FIG. 7 is a circuit diagram for the eval.sub.-- tree circuit of the processor block of FIG. 4.

FIG. 8 is a circuit diagram for the preferred embodiment of control element of the controller of FIG. 5, wherein the control element has a "clear" input.

FIG. 9 is a current diagram for an alternative embodiment of the control element, wherein the control element does not have a "clear" input.

FIG. 10 is a timing diagram for the pipeline of the present invention (FIG. 3) where the Muller C-element is used instead of the control element of (FIG. 8) the present invention in controllers C.sub.b, C.sub.c and C.sub.d of FIG. 5.

FIG. 11 is a timing diagram for the present pipeline (FIG. 3) where the control element of the present invention is used in the controllers C.sub.b, C.sub.c and C.sub.d of FIG. 5.

FIG. 12 provides an expanded portion of the timing diagram of FIG. 10, which focuses on the switching of the Muller C-element output triggered by the request input.

FIG. 13 provides an expanded portion of the timing diagram of FIG. 11 which focuses on the switching of the output of the present invention triggered by the request input.

In FIG. 3 the pipeline of the preferred embodiment of the present invention is shown with a first, second, third and fourth processor, P.sub.a, P.sub.b, P.sub.c and P.sub.d, each with one or more data input and data output lines. P.sub.a is typical of the processors and is shown in detail in FIG. 4. The processor P.sub.a has a subprocessor eval.sub.-- tree.sub.a, with a data input S1, a data input S1n (the logical complement of the input S1), and a control input pc.sub.-- a. The subprocessor has an output S and a complementary output Sn. When the subprocessor control input pc.sub.-- a is low, the subprocessor eval.sub.-- tree.sub.a is forced into a precharge'state wherein the subprocessor does not evaluate data and the outputs S and Sn are both low. If the outputs S and Sn are both high this indicates a fault condition. When the control input pc.sub.-- a goes high, the processor becomes active and processes the data at its inputs and then puts the result on its output S and puts the complement on its output Sn provided that the inputs S1 and S1n must be complements. It is well known by those skilled in the art to design processors which will provide a complemented output so that it is not necessary to impose the condition that a signal and its complement must both be supplied as inputs to the processor; however, the processor shown in the preferred embodiment does require that a signal and its complement are both provided. Also included in the processor P.sub.a is a NOR gate having two inputs and an output. One of the NOR gate inputs is connected to output S of eval.sub.-- tree.sub.a, and the other input of the NOR gate is connected to output Sn, so that when eval.sub.-- tree.sub.a is in a precharge state with both outputs S and Sn low, the NOR output is high, and otherwise the NOR output is low. The NOR output is labeled "ackn.sub.-- a".

P.sub.a, P.sub.b, etc. receive and process data, hold the processed data, and then send the data to the next processor in the pipeline or to a receiving device (not shown) at the end of the pipeline. Controllers C.sub.b, C.sub.c and C.sub.d receive timing signals for controlling the processors. Controller C.sub.b forces processor P.sub.b into its active interval, controller C.sub.c forces P.sub.c into its active interval, and so on. In the control scheme of the preferred embodiment of the present invention, since control of a processor active interval generally depends on the status of a preceding and a succeeding processor, the processors P.sub.a, P.sub.b, etc. may be considered as belonging to functional groups, with three processors in a group. The controllers associated with a group of processors likewise may be considered as a functional group. For example, in FIG. 3 a first group of processors would be processors P.sub.a, P.sub.b and P.sub.c, and a second group would be processors P.sub.b, P.sub.c and P.sub.d. The first group intermediate controller would be controller C.sub.b, since controller C.sub.b is in communication with the processors in the first processor group, and since it controls the active interval of the intermediate processor of the group, processor P.sub.b. Likewise, the second group intermediate controller would be C.sub.c, since controller C.sub.c is in communication with the processors in the second processor group, and controls the active interval of the intermediate processor P.sub.c of the group. Controller C.sub.d may be considered an end controller, since it controls the last processor in the pipeline, processor P.sub.d. In the embodiment presented here, the first processor in the pipeline is controlled by signals provided external to the pipeline, such as from a controller (not shown), which may be considered on initial controller, receiving signals from a device feeding the pipeline and from some of the pipeline processors.

Controller C.sub.b is generally typical of the controllers and is shown in detail in FIG. 5. The controller C.sub.b has three inputs. One input goes directly to an "acknowledge" input of a control element CE.sub.b. A second input goes to an inverter. The output of the inverter goes to a "request" input of the control element CE.sub.b. A third input provides a clear signal to the control element CE.sub.b. Controller C.sub.b has a primary output labelled "pc.sub.-- b". Controllers C.sub.c and C.sub.d also have primary outputs, but unlike controller C.sub.c and C.sub.d, controller C.sub.b has a secondary output from the output "req.sub.-- b" of the second input inverter. Also, in another embodiment of the present invention the controllers such as C.sub.b, C.sub.c and C.sub.d do not have a clear input. When the present invention is practiced using controllers without a clear input, initialization may require that some predetermined sequence of data be presented to the processors.

The control element of the present invention provides a logic function as shown in the following table, which indicates the binary logical states of the inputs and the primary output of the control element. The logic states of the Muller C-element of FIG. 1 are also shown for comparison purposes.

A configuration of Boolean logic gates which provide the two input, one output control element of the present invention is shown as FIG. 6 and is stated in the following Boolean algebra terms:

It can be seen by inspection that the configuration of FIG. 6 provides an output which assumes a logical "1" state when both inputs are a logical "1" state; and a logical "0" state when the inputs are a logical "0" state. Also, once the output has assumed a logical "1" state it will maintain that state as long as input B maintains the logical "1" state regardless of whether input A changes to logical state "0"; or, stated more generally, the output will maintain its previous state as long as the input A has a logical "0" state and the input B has a logical "1" state.

The control element of the present invention has a reduced set of logical states in comparison with the states of the Muller C-element. Expressing the state of a control element as a three digit binary number where the first digit indicates the A input, the second digit indicates the B input and the third digit indicates the output state, the Muller C-element may assume the six states 000, 010, 011, 100, 101 and 111, whereas the present control element may assume only the five states 000, 010, 011, 100, and 111.

The general operation of the pipeline of the present invention is as follows. Referring again to FIG. 3, and ignoring, for now, the initialization steps, once the first processor P.sub.a has received and processed data, the processor puts the data on its output data lines, which are the data input lines for the second processor P.sub.b. Then the first processor P.sub.a changes the state of the signal on control line ackn.sub.-- d between it and control element C.sub.b to indicate that the first processor P.sub.a is ready to pass data to the second processor P.sub.b.

The terminology used herein for labelling of the signal lines, functional blocks, and device inputs and outputs is as follows. A typical signal line in FIG. 3 is interchangeably referred to, for example, as "n.sub.-- pc.sub.-- a", "pc.sub.-- a" or simply "pc". The "n" indicates that the signal "pc" is active low. The "a" indicates that the signal is associated with a device labeled "a". The lines carrying the status signal from processor P.sub.a to controller C.sub.b and C.sub.d in FIG. 3 are labelled "ackn.sub.-- d" because one of the lines carries the status signal directly to the acknowledge input on control element CE.sub.d on controller C.sub.d (see FIG. 4). The other line labeled "ackn.sub.-- d" carries the status signal from processor P.sub.a to the input of the inverter in the control element, C.sub.b, which controls the second stage processor, P.sub.b. The C.sub.b inverter output is the req.sub.-- b signal to the C.sub.b control element (see FIG. 4).

If the third stage processor P.sub.c is ready to accept data from processor P.sub.b, so that processor P.sub.b can send any data which it already has to the third stage processor P.sub.c, the ackn.sub.-- b signal from P.sub.c will indicate such. The req.sub.-- b signal, derived from the ackn.sub.-- d signal from processor P.sub.a, and the ackn.sub.-- b signal from processor P.sub.c trigger control element CE.sub.b to provide a signal pc.sub.-- b, to processor P.sub.b, causing processor P.sub.b to begin processing the data on its data input lines.

The initialization and detailed sequence of the control signals in the pipeline of the preferred embodiment of the present invention is as follows. To initialize the pipeline, the clear signal and the pc.sub.-- a signal from a controller (not shown) preceding the pipeline both are set low and the control element CE.sub.b, CE.sub.c and CE.sub.d outputs go to a low state. These outputs being low set the eval.sub.-- tree circuits to their precharge state so that the eval.sub.-- tree outputs are both low and the NOR gate outputs in the processors P.sub.a, P.sub.b, P.sub.c and P.sub.a are all high. With all the processor NOR gate outputs high the acknowledge inputs to the control elements are high, while the request inputs are low.

To begin operation of the pipeline the clear signal is set high and remains high during normal operation. Signal pc.sub.-- a is set high, causing the eval.sub.-- tree.sub.a circuit to begin evaluating the complemented data pair on its input lines S1 and S1n.

Once the data into eval.sub.-- tree.sub.a has been evaluated, one of the complementary outputs S and Sn goes high, and the other goes low, depending on the data. The change in state in S or Sn of eval.sub.-- tree.sub.a causes the P.sub.a NOR gate output ackn.sub.-- d to go low, causing the req.sub.-- b input to control element CE.sub.b to go high. At this point the state of eval.sub.-- tree.sub.c remains unchanged from its precharge state so that ackn.sub.-- b remains high.

Thus, with both ackn.sub.-- b and req.sub.-- b now high, the output pc.sub.-- b of control element CE.sub.b changes to a high state. This causes eval.sub.-- tree.sub.b to begin evaluating the data which eval.sub.-- tree.sub.a has now placed on the eval.sub.-- tree.sub.a output lines and eval.sub.-- tree.sub.b input lines. Meanwhile, the output req.sub.-- b of the P.sub.a NOR gate going low has provided a clear signal to a controller (not shown) preceding the pipeline. This controller sets pc.sub.-- a low again.

Once eval.sub.-- tree.sub.b finishes processing it puts a complemented data pair on its outputs S and Sn, causing the NOR gate output ackn.sub.-- a to go low and the C.sub.c inverter output req.sub.-- c to go high. At this point the state of eval.sub.-- tree.sub.d remains unchanged from its precharge state so that ackn.sub.-- c remains high.

Thus, with both ackn.sub.-- c and req.sub.-- c now high, the output pc.sub.-- c of control element CE.sub.c changes to a high state. This causes eval.sub.-- tree.sub.c to begin evaluating the data which eval.sub.-- tree.sub.b has now placed on the eval.sub.-- tree.sub.b output lines and eval.sub.-- tree.sub.c input lines. Meanwhile, eval.sub.-- tree.sub.a has been put into the precharge state again by pc.sub.-- a going low, so that the ackn.sub.-- d input to CE.sub.d is now high and the req.sub.-- b input to CE.sub.b is now low.

Once eval.sub.-- tree.sub.c finishes processing, it puts a complemented data pair on its outputs S and Sn, causing the NOR gate output ackn.sub.-- b to go low and the C.sub.d inverter output req.sub.-- d to go high. As just described, eval.sub.-- tree.sub.a is now in its precharge state, so that ackn.sub.-- d is high.

Thus, with both ackn.sub.-- d and req.sub.-- d now high, the output pc.sub.-- d of control element CE.sub.d changes to a high state. This causes eval.sub.-- tree.sub.d to begin evaluating the data which eval.sub.-- tree.sub.c has now placed on the eval.sub.-- tree.sub.c output lines and eval.sub.-- tree.sub.d input lines. Meanwhile, with ackn.sub.-- b going low due to completion of eval.sub.-- tree.sub.c processing, and with req.sub.-- b already low due to eval.sub.-- tree.sub.a having been put into precharge, the output of control element CE.sub.b goes low, which puts eval.sub.-- tree.sub.b into precharge and causes ackn.sub.-- a to go high and req.sub.-- c to go low.

Once eval.sub.-- tree.sub.d finishes processing, it puts a complemented data pair on its outputs S and Sn, causing the NOR gate output ackn.sub.-- c to control element C.sub.c. With signal ackn.sub.-- c going low due to completion of eval.sub.-- tree.sub.a processing, and with signal req.sub.-- c already low due to eval.sub.-- tree.sub.a having been put into precharge, the output of control element CE.sub.c goes low, which puts eval.sub.-- tree.sub.c into precharge and causes ackn.sub.-- b to go high and req.sub.-- d to go low. Meanwhile, the req.sub.-- a low signal has gone to the controller (not shown) which precedes, the pipeline. This controller causes pc.sub.-- a to go high, which launches eval.sub.-- tree.sub.a to begin a new processing cycle. When eval.sub.-- tree.sub.a completes processing its data, ackn.sub.-- d goes low, which, together with req.sub.-- d low, puts eval.sub.-- tree.sub.d into precharge so that eval.sub.-- tree.sub.d is set for a new cycle.

As described above, in the initial cycle the acknowledge signals to the control elements CE.sub.b, CE.sub.c and CE.sub.d are initially high, the request signals are initially low and the control elements outputs are initially low, so that the control element outputs are forced high by the request signals going high, where the acknowledge signals are already high due to initialization. In later cycles, since propagation of the acknowledge signals is slower than that of the request signals, a control element's output is forced high by the acknowledge signal going high, where the request signal is already high. Therefore, the timing diagrams of FIG's 10 through 13 indicate that the request signals go high before the acknowledge signals during a timing cycle. It is also possible to arrange the control signals so that in cycles after the initial cycle the acknowledge signals go high before the request signals.

For the purpose of illustrating the performance of the control element of the present invention, an "eval.sub.-- tree" circuit was used for the typical eval.sub.-- tree.sub.a subprocessor of FIG. 4. This circuit provides a buffer, so that the pipeline of the embodiment of the present invention illustrated herein functions as a first-in-first-out shift register. Other subprocessors could be substituted in order to provide a variety of functions such as computation or instruction interpretation.

The eval.sub.-- tree circuit is shown in FIG. 7. In this circuit a control input pc is connected to the gates of two p-type field effect transistors ("FET's"), Q11 and Q14. The sources of Q11 and Q14 are connected to a power supply. Data inputs S1 and S1n are connected to the gates of n-type FET's Q1 and Q2 respectively. The sources of Q1 and Q2 are connected to the drain of QR. The source of QR is connected to ground. The drains of Q1 and Q2 are connected to the drains of Q11 and Q14 respectively. The drain of Q1 is also connected to the gates of a p-type FET Q17 and an n-type FET Q15 as well as the drain of a p-type FET Q12. Likewise the source of Q2 is connected to the gate of a p-type FET Q18 and the gate of an n-type FET Q16, as well as the drain of a p-type FET QS21. The sources of Q12, Q17, QS21 and Q18 are connected to the power supply. The drain of Q17 is connected to the source of Q15 and the gate of Q12. The source of Q15 is connected to ground. Likewise the drain of Q18 is connected to the drain of Q16 and the gate of QS21. The source of Q16 is connected to ground. Output S is provided by a connection to the drain of Q17. Likewise output S.sub.n is provided by a connection to the drain of Q18.

The eval.sub.-- tree circuit operates as follows. With pc in a low state Q11 and Q14 are turned on and QR is turned off. With QR off, inputs S1 and S1n do not affect operation of the eval.sub.-- tree outputs. Q11 on turns off Q17 and turns on Q15. Likewise, Q14 on turns off Q18 and turns on Q16. Q15 on brings S low and turns on Q12. Likewise, Q14 on brings Sn low and turns on QS21. With both S and Sn low the NOR output (see FIG. 4) is high.

When pc.sub.-- a goes high the eval.sub.-- tree begins processing data at its inputs S1 and S1n. The inputs S1 and S1n are provided by an external circuit as complements to the eval.sub.-- tree circuit. When pc.sub.-- a goes high, this turns off Q11 and Q14, and turns on QR, so that S1 and S1n can affect the eval.sub.-- tree outputs.

If S1 is high, S1n will be low. When processing begins with these inputs, Q1 is turned on and Q2 is turned off. Q1 and QR on turns on Q17 and turns off Q15. Q17 on turns off Q12 and brings S high. Since Q2 is off, QR does not affect Q16 or Q18, so that the feedback loop through QS21 continues to hold Q16 and Q18 in their previous state, and thereby holds Sn in its previous low state. With S high and Sn low, the NOR output (see FIG. 4) is low.

Alternatively, if S1 is low, S1n will be high. When processing begins with these inputs, Q1 is turned off and Q2 is turned on. Q2 and QR on turns on Q18 and turns off Q16. Q18 on turns off QS21 and brings Sn high. Since Q1 is off, QR does not affect Q15 or Q17, so that the feedback loop through Q12 continues to hold Q15 and Q17 in their previous state, and thereby holds S in its previous low state. With S low and Sn high, the NOR output (see FIG. 4) is low.

For the preferred embodiment of the present invention, FIG. 8 shows the circuit of the control element used as the typical CE (shown as CE.sub.b in FIG. 5). The acknowledge input is connected to the gates of a p-type FET, Q5, and an n-type FET, Q1. The source of the FET Q5 is connected to a power supply. The drain of Q5 is connected to the drain of an n-type FET, Q3, which has a gate that serves as the request input. The source Q3 is connected to the drain of an n-type FET, Q2, which has a gate that serves as a clear input. The source of Q2 is connected to the drain of Q1. The source of Q1 is connected to ground.

Also connected to the drains of Q3 and Q5 is the drain of a p-type FET, Q6, having a gate that is connected to the same clear signal connected to the gate of Q2. The source of Q6 is connected to the power supply.

Also connected to the drains of Q3 and Q5 are the gates of a p-type FET, Q9, and an n-type FET, Q8. The source of Q9 is connected to the power supply. The source of Q8 is grounded. The drains of Q9 and Q8 are connected together and provide the output, pc.sub.-- b.

Also connected to the drains of Q3 and Q5 are the drains of a p-type FET, Q7, and an n-type FET, Q4. Both Q4 and Q7 have gates connected to the pc output line. The source of Q7 is connected to the power supply. The source of Q4 is connected to the drain of Q2 and the source of Q3.

The control element of FIG. 8 operates as follows. Initially clear is asserted low to force pc.sub.-- b low by turning on Q6, which turns off Q9 and turns on Q8. By turning on Q8, pc is forced low. Once pc is low, Q7 is turned on and Q4 is turned off.

Referring now to FIG. 5, as described above in the overview of operation, input ackn.sub.-- b is initially high and input req.sub.-- b is initially low, as set during the precharge state of the processor P.sub.a. After initialization, the clear signal is returned to its normal, high state. Referring again to FIG. 8, with clear high, Q6 turns off and Q2 turns on. The pc.sub.-- b signal is held high by Q7. Ackn.sub.-- b high turns on Q1 and turns off Q5.

Then, when req.sub.-- b goes high, Q3 is turned on, which turns on Q9 and turns off Q8. Turning on Q9 forces pc.sub.-- .sub.-- b high, which turns off Q7 and turns on Q4. Thus, by req.sub.-- b going high after ackn.sub.-- b, output pc is forced high by the req.sub.-- b input switching solely Q3, and by Q3 switching solely Q9 and Q8.

Now pc.sub.-- b will be held high if req.sub.-- b goes low and ackn.sub.-- b remains high. That is, if only req.sub.-- b goes low, Q3 will turn off, but pc.sub.-- b will still be held high through Q4, Q2 and Q1 holding Q9 on.

When ackn.sub.-- b goes low, and with req.sub.-- b low, pc.sub.-- b will be forced low again through Q5 turning on, which will turn on Q8 and turn off Q9. In the pipeline configuration of FIG. 3, during later cycles req.sub.-- b will go high before ackn.sub.-- b. With ackn.sub.-- b low, when req.sub.-- b goes high Q3 is turned on, but does not cause any other FET's to switch due to Q1 begin off. Then, when ackn.sub.-- b goes high this switches Q1 on and Q5 off so that Q9 is switched on and Q8 is switched off through Q1, Q2 and Q3. Q9 switching on forces output pc high. Thus, by ackn.sub.-- b going high after req.sub.-- b, output pc is forced high by the ackn.sub.-- b input switching solely Q1 and Q5, and by Q1 and switching solely Q8 and Q9.

In the embodiment of the invention presented here a Muller C-element may be substituted for the control element in controllers C.sub.b, C.sub.c and C.sub.d. For other embodiments of the present invention, the Muller C-element may not be suitable. With this substitution, in the present embodiment, the pipeline will function properly but will operate slower than with the present, reduced-state control element. This may be demonstrated by replacing the control element of the present invention with a Muller-C element and comparing the timing of certain steps in the pipeline operation. The timing diagram of FIG. 10 shows timing of pipeline transitions where the Muller C-element is used instead of the control element of the present invention in controllers C.sub.b, C.sub.c and C.sub.d of FIG. 3. The timing diagram of FIG. 11 shows timing where the control element of the present invention is used in controllers C.sub.b, C.sub.c and C.sub.d.

These timing diagrams show that when a request signal req.sub.-- b, req.sub.-- c or req.sub.-- d to a control element CE.sub.b, CE.sub.c or CEd goes high, this more quickly causes the output pc.sub.-- b, pc.sub.-- c or pc.sub.-- d to go high in the control element of the present invention than in the Muller C-element. FIGS. 12 and 13 provide an expanded portion of these timing diagrams which more clearly shows the increase in speed of the present invention. For a Muller C-element as shown in FIG. 12, it takes about 342 picoseconds for the output pc.sub.-- b to rise to a level of 1.12 v after the request signal req.sub.-- b does. For the control element of the present invention as shown in FIG. 13, it takes about 189 picoseconds for the same response. In this example, the control elements of the present invention reduce the time for data to process through the pipeline by 153 picoseconds for each of the four stages in the pipeline, or a total of 612 picoseconds.

The increase in speed is due to the smaller number of gates in the control element of the present invention, and due to the nature of the gates required. In general terms, there are fewer gates for the request signal to propagate through in order to switch the output of the control element in the present invention than in the Muller C-element. Also, for the circuit of the present invention, the request signal merely pulls down n-type FET, Q3, in order to initiate the switch of the output of the control element. In contrast, for the Muller C-element, the request signal switches both p-type FET, Q3, and n-type FET, Q2, on the front end, and p-type FET, Q6, and n-type FET, Q5, on the back end. Since an n-type FET inherently switches faster than a p-type FET having the same conductance, it is faster to switch the one n-type FET, Q3, in the present invention than to switch the two pairs of FET's Q2/Q3 and Q5/Q6, which include the p-type FET's, Q3 and Q6, in that of the traditional Muller C-element circuit. Also, in the Muller C-element circuit, the FET's Q2/Q3 and Q5/Q6 being switched by the request signal are located disadvantageously in the circuit, in that these FET's are stacked in series with a number of other FET's.