PEETERS, Adrianus, M., G. (AE Eindhoven, NL-5656, NL)
MALLON, Willem, C. (AE Eindhoven, NL-5656, NL)
PEETERS, Adrianus, M., G. (AE Eindhoven, NL-5656, NL)
CLAIMS:
1. An asynchronous control device (100') for controlling a stage of an asynchronous pipeline (10), the control device (100') comprising control logic (104') and a non-transparent memory element (102'), wherein the control logic (104') is adapted to: - receive a request signal (108); receive an acknowledgement signal (110); receive an output signal (112) from the non-transparent memory element; and generate an enable signal (114) for the non-transparent memory element (102'), wherein the non-transparent memory element (102') is adapted to: receive one of the request signal (108) and the output signal from the non- transparent memory element (102') as an input signal; and receive the enable signal (114) generated by the control logic (104'), thereby allowing for the input signal received by the non-transparent memory element (102') to be provided as the output signal from the non-transparent memory element (102').
2. Asynchronous control device (100') according to claim 1, wherein the enable signal (114) is generated subsequent to the reception of the acknowledgement signal (110).
3. Asynchronous control device (100') according to claim 1 or 2, wherein the enable signal (114) is also provided to a data holding element (150) associated with the control device (100').
4. Asynchronous control device (100') according to any one of the preceding claims, wherein the non-transparent memory element (102') is a flip-flop.
5. Asynchronous control device (100') according to any one of the preceding claims, wherein the non-transparent memory element (102') is adapted to be set to a predetermined initialization value.
6. An asynchronous pipeline (10), comprising: a plurality of data holding elements (150); and a plurality of asynchronous control devices (100') according to any one of claims 1 to 5 for each controlling a respective one of the plurality of data holding elements (150).
7. Asynchronous pipeline (10) according to claim 6, wherein the plurality of control devices (100') are sequentially connected, and the output signal from a non- transparent memory element of one of the plurality of control devices (100') is provided as a request signal (112) for a subsequent control device (100') and as an acknowledgement signal (106) for a preceding control device (100').
8. Asynchronous pipeline (10) according to claim 6 or 7, further comprising at least one data processing module (152) arranged between two of said plurality of data holding elements (150).
9. A microprocessor, comprising an asynchronous pipeline (10) according to any one of claims 6 to 8. |
ASYNCHRONOUS PIPELINE CONTROLLER
FIELD OF THE INVENTION
The present invention relates to an asynchronous control device for controlling an asynchronous pipeline.
BACKGROUND OF THE INVENTION
In large scale circuitry, for example comprising both combinational and sequential logic, a global clock signal is used for progressing a functional process provided by the circuitry. This global clock signal is generally provided as a single input to the circuitry, thereafter divided and/or multiplied and provided to the different blocks/modules of the circuitry. Such a circuitry is said to be clocked in a synchronous manner, i.e. every logic transition of the clock controlling the circuitry potentially leads to a change of the logic state of the circuitry.
Even though synchronous clocking of a circuitry in many ways is advantageous, especially in relation to the development and testing of the circuitry, synchronous circuitries use a large amount of electrical power as all of the blocks/modules of the circuitry continuously are affected by the global clock signal. One way of solving the power consumption problem is by adapting the logical blocks/modules of the circuitry to communicate with each other in an asynchronous manner. An asynchronous circuitry is not governed by a clock circuit or global clock signal, but instead need only wait for signals that indicate completion of instructions and operations, and thus only the blocks/modules really needing to advance forward are affected when that block/module receives an activation signal. These activation signals are specified by simple data transfer protocols, sometimes referred to as handshake signals, for example comprising a request signal and an acknowledgement signal. A crucial part in high performance logic processing is the use of circuits for buffering and flow control for improving the performance of processors, similar computational devices and computer memories. The classic FIFO memory is an example of such a buffering solution, sometime referred to as a pipeline. As in relation to the above discussed large scale circuitry, pipelines can be implemented as both synchronous and
asynchronous pipelines, providing similar advantages and disadvantages as discussed above. However, recent development indicates that asynchronous pipelines use less power and cause less interference in the electromagnetic spectrum, thus making them well-suited to low-power embedded and mobile systems. An example of an asynchronous pipeline is disclosed in US 5,937,177, focusing specifically on a plurality of apparatuses for controlling a respective plurality of memory elements comprised in the pipeline. Each of the control apparatuses uses a set-reset latch for state holding in the control apparatus, where the stages alternately provide synchronization with their right neighbor (set empty) and left neighbor (set full).
SUMMARY OF THE INVENTION
The control apparatus disclosed in US 5,937,177 introduces problems in relation to design- for-test (DFT) due to the use of latches in the control apparatus. DFT is a design technique that adds certain testability features to an electronic hardware design, facilitating development and manufacturing tests. Furthermore, if wanting to adapt the disclosed control apparatus for DFT, this would lead to extra expenses in relation to the introduction of additional circuitry, and thus causing performance degradation and introducing complex timing constraints for the final pipeline.
There is therefore a need for a novel asynchronous control device for controlling an asynchronous pipeline, and more specifically a control device that at least alleviates the problems with the introduction of additional circuitry leading to complex timing constraints for the final pipeline.
According to an aspect of the invention, the above object is met by an asynchronous control device for controlling a stage of an asynchronous pipeline, the control device comprising control logic and a non-transparent memory element, wherein the control logic is adapted to receive a request signal, receive an acknowledgement signal, receive an output signal from the non-transparent memory element, and generate an enable signal for the non-transparent memory element, wherein the non-transparent memory element is adapted to receive one of the request signal and the output signal from the non-transparent memory element as an input signal, and receive the enable signal generated by the control logic, thereby allowing for the input signal received by the non-transparent memory element to be provided as the output signal from the non-transparent memory element.
A difference with prior art solutions is the use of a non-transparent memory element in the control device for controlling the asynchronous pipeline, conversely to the use
of transparent memory elements (e.g. C-elements and latches) in the prior art. The novel features make it possible to utilize standard-cell technologies when designing the control device. Generally, technology libraries are optimized for non-transparent memory elements and not for latches and/or C-elements. An advantage with the invention is thus that it is possible to use the inbuilt design- for-test technology that is available through the use of standard-cell technologies. This also reduces the constraints set on the design environment, and thus reduces the design- for-test overhead. Using less design- for-test overhead thus leads to a less expensive pipeline having less complex timing constraints. Furthermore, the control device according to the present invention allows for less technology based restrictions that eventually result in fewer layout restrictions and a higher layout density, and thus a smaller end circuit.
According to a preferred embodiment of the invention, the non-transparent memory element is a flip-flop. A flip-flop is generally defined as a kind of bi-stable multivibrator which has two stable states and thereby is capable of serving as one bit of memory. The flip-flop is generally clocked or edge-triggered, thereby "non-transparent" in the sense that it "does not let data pass straight through". A flip-flop in the meaning of the present invention usually uses two (level sensitive) elements for storage (a master and a slave latch), whereas the traditional control device for a pipeline (e.g. disclosed in "Micropipelines", I.E. Sutherland, Communications of the ACM,32(6) 720-738, June 1989) uses one C-element to control a single stage.
In another preferred embodiment, the non-transparent memory element used in the asynchronous control device according to the present invention is adapted to be set to a predetermined initialization value. The possibility to set the non-transparent memory elements to a predetermined value allows for the pipeline to be initialized to a preset sequence, for example all zeros, all ones, or any other predefined sequence. This possibility is for example advantageous in the case where the data stored in the pipeline is provided directly to a processing algorithm, in which case the use of a predefined data pattern for example improves the time it takes for the algorithm to produce a stable output. This feature is not as easy to implement using for example latches or C-elements as this would introduce additional logic, and thereby once again introduce complex timing constraints. As an example, a stage holds a data-item if the flip-flop in the control device holds a bit that is different from the bit held in the right hand side neighbor, i.e. subsequent control device. Thus, a control sequence for three stages in a pipeline could look like this: OOO' no data elements (no different signals), ' 100' one data element (1 different from 0 (also denoted by 1
≠ 0, 0 = 0), '110' one data element (1 = 1, 1 ≠ 0) → second stage holds data, '010' two data elements (0 ≠ 1, 1 ≠ 0) — > both stage one and two hold data. In a three-stage pipeline, if the three controller bits are set to '010', the pipeline initially holds two data elements, one in the first stage (because 0 ≠ 1) and one in the second stage (because 1 ≠ 0). As discussed above, the asynchronous control device according to the present invention is preferably, but not exclusively, used as a component in an asynchronous pipeline. In such an embodiment, the asynchronous pipeline preferably comprises a plurality of data holding elements, and a plurality of asynchronous control devices as discussed above for each controlling a respective one of the plurality of data holding elements. The data holding elements are also preferably non-transparent memory elements, such as flip-flops. In any case, the enable signal generated by the control logic of the asynchronous control device is preferably used for controlling the respective data holding element. Furthermore, there are various modifications possible and within the scope of the invention wherein the control device uses a flip-flop. Preferably, the pipeline comprises a plurality of sequentially connected data holding elements and asynchronous control devices according to the present invention. In such an embodiment, the output signal from a non-transparent memory element of one of the plurality of control devices is provided as a request signal for a subsequent control device and as an acknowledgement signal for a preceding control device. The data stored by the data holding element is thereby allowed to advance forward in an asynchronous manner, wherein the stepping forward is obtained using activation signals, as mentioned above sometimes referred to as handshake signals, for example comprising a request signal and an acknowledgement signal. The asynchronous pipeline can further comprise at least one data processing module arranged between two of said plurality of data holding elements. The data processing module, for example a computational logic block, can be used for arbitrary computation (e.g. as a general data processing block), such as for executing a portion of an algorithm, or just for delaying the data being passed through the pipeline.
Also, the asynchronous pipeline as discussed above can possibly, but not exclusively, be used as a component in a microprocessor, or any other similar programmable electronic device. The use of an asynchronous pipeline according to the present invention consumes less power and causes less interference in the electromagnetic spectrum, thus making it extra useful in relation to for example mobile phones and similar hand held devices.
These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter.
BRIEF DESCRIPTION OF THE DRAWINGS Fig. 1 is a block diagram schematically illustrating an exemplary three-stage asynchronous pipeline;
Fig. 2 is a block diagram illustrating a prior art asynchronous control device for controlling an asynchronous pipeline;
Fig. 3a is a block diagram illustrating an asynchronous control device for controlling an asynchronous pipeline according to an embodiment of the present invention; Fig. 3b illustrates an alternative embodiment for providing an input signal to the non-transparent memory element comprised in the asynchronous control device;
Fig. 3c illustrates a gate level implementation of control logic according to an embodiment of the present invention; and Fig. 4 is a timing diagram illustrating the operation of the control logic in Fig.
3c.
DETAILED DESCRIPTION OF EMBODIMENTS
The present invention will now be described more fully hereinafter with reference to the accompanying drawings, in which currently preferred embodiments of the invention are shown. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided for thoroughness and completeness, and fully convey the scope of the invention to the skilled addressee. Like reference characters refer to like elements throughout.
The present invention finds application in the area of asynchronous circuits, and more particularly, in the area of self-timed data pipelines. The present invention can be utilized in any context where data is pipelined including, for example, in a network interface controller within a parallel processing system. In accordance with the present invention, a self-timed data pipeline is comprised of a plurality of sequential pipeline stages, where the pipeline stages can advantageously communicate with one another, and pass data in an asynchronous fashion through the use of handshake signals, for example in the form of REQUEST and ACKNOWLEDGE signals.
Fig. 1 illustrates a schematic overview of such an exemplary asynchronous
pipeline 10, there comprising three-stages. The pipeline 100 comprises data holding elements 150, for example flip-flops, that each is individually controlled by a corresponding control device 100. The data holding elements 150 have in between each other arranged a computational logic block 152. The computational logic block 152 can be used for arbitrary computation (e.g. as a general data processing block), such as for executing a portion of an algorithm, or just for delaying the data being passed through the pipeline 10. As mentioned above, the control devices communicate with each other using handshake signals. For synchronizing the REQUEST and ACKNOWLEDGE signals with each other, there is arranged a delay matching module 154 on the REQUEST signal path. It is understood by the skilled addressee that it of course can be possible to have more than three stages in the pipeline 10.
For the complete understanding of the novel concept according to the present invention, a quick review is made of a prior art asynchronous control device used for controlling an asynchronous pipeline. Such a control device is illustrated in Fig. 2, wherein the control device 100 comprises a latch 102 and control logic in the form of a control unit 104. As illustrated from Fig. 1, the control device 100 forms a part in a sequence of a plurality of control devices adapted for controlling an equal plurality of data holding elements 150 in the pipeline 10. In relation to the handshake signals between the control devices 100, each control device 100 is adapted for providing an ACKNOWLEDGE signal 106 to and for receiving a REQUEST signal 108 from a preceding control device. The control device 100 is also adapted for receiving an ACKNOWLEDGE signal 110 from and for providing a REQUEST signal 112 to a subsequent control device. Also, an enable signal 114 is provided from the control device 100 for controlling the associated data holding elements. As is illustrated in Fig. 2, the control unit 104 is adapted to receive both the ACKNOWLEDGE signal 110 provided by the subsequent control device, and an output from the latch 102 which also is provided as the REQUEST signal 112 to the subsequent control device and the ACKNOWLEDGE signal 106 to the preceding control device. The latch 102 is in turn adapted to receive the enable signal 114 from the control unit 104 and the REQUEST signal 108, and as mentioned above, for generating the ACKNOWLEDGE signal 106 and the REQUEST signal 112.
During operation, the prior art pipeline control device 100 is in an initial state transparent. An incoming request, i.e. in the form of REQUEST signal 108, propagates through the latch 102. It then triggers the control unit 104 and the latch 102 turns opaque. It also propagates to the right hand side of the latch 102, i.e. thereby generating the REQUEST
signal 112 and the ACKNOWLEDGE signal 106. A new request must thus wait (since the latch 102 is opaque) until the right hand side acknowledges, i.e. in the form of the ACKNOWLEDGE signal 110, which triggers the control unit 104 which causes the latch 102 to become transparent again. After this, the operation is back in the initial state. Turning now to Fig. 3a, providing a conceptual block diagram illustrating an asynchronous control device 100' for controlling the asynchronous pipeline 10 according to an embodiment of the present invention. A difference of the control device 100' in regards to the prior art control device 100 shown in Fig. 2 is the use of a non-transparent memory element, i.e. here a flip-flop 102', in the control device 100'. The introduction of a flip-flop 102' on the control path reduces the constraints on the logic environment, and also reduces potential design- for-test overhead. This also results in the possibility to use conventional logic optimizers, thereby obtaining faster and/or smaller circuits. Thus as is noted, the control device 100' according to the present invention is an exchangeable component in the asynchronous pipeline 10 in Fig. 1. Furthermore, the control unit 104' is different to the prior art control unit 104 illustrated in Fig. 2. Instead of only depending on signals present "after" the latch, the control unit 104' depends also on the REQUEST signal 108 provided from the preceding control device.
An alternative for providing an input signal to the non-transparent memory element comprised in the asynchronous control device 100' is illustrated in Fig. 3b. In this case, the communication path between the REQUEST signal 108 and the flip-flip 102' is broken, and the output from the flip-flop 102' (which also is the ACKNOWLEDGE signal 106 to the preceding control device) is instead used as a feedback to the input of the flip-flop 102'. Thereto, the feedback signal provided as an input to the flip-flop 102' is first inverted using an inverter 116 before it reaches the flip-flop 102'. An advantage of this alternative using the local inverter 116 is that the design can be easier to route (in placement and routing).
For the complete description of the control unit 104' comprised in the control device 100', Fig. 3c illustrates a gate level implementation of control unit 104' according to an exemplary embodiment of the present invention. Fig. 4 will be used for explaining the functionality of the control unit 104' illustrated in Fig. 3c.
The control unit 104' comprises two three input AND gates 118, 120 and one two input OR gate 122 having internal communication and adapted to receive and generate signals in accordance to input and output signal to and from the control unit 104'. The first
AND gate 118 is adapted to receive an inverted version of the REQUEST signal 112, an inverted version of the ACKNOWLEDGE signal 110, and the REQUEST signal 108, and to generate a therefrom dependant output signal which is provided as a first input signal to the OR gate 122. The second AND gate 120 is adapted to receive an inverted version of the REQUEST signal 108, the ACKNOWLEDGE signal 110, and the REQUEST signal 112, and to generate a therefrom dependant output signal which is provided as a second input signal to the OR gate 122.
It may be observed that this control unit 104' will generate the control signal for the flip-flop 102' in such a way that it copies new data from its preceding stage precisely when that preceding stage has new data available (indicated by REQUEST signal 108 differing from ACKNOWLEDGE signal 106) and the subsequent stage has accepted the previous data item (indicated by REQUEST signal 112 being equal to ACKNOWLEDGE signal 110). The implementation of Fig. 3c comprises a logic representation of this forwarding condition. Fig. 4 illustrates a timing diagram describing an exemplary scenario when using the in Fig. 3c illustrated version of the control unit 104'. The description below provides an interpretation of the timing diagram. At to, all signals are low. This is the initial state for the control unit 104'. At t ls a request, i.e. REQUEST signal 108, is received from the preceding control device. Thus the REQUEST signal 108 becomes high. After that, at t 2 , the output signal from the first AND gate 118 goes high (as the other two input signals at this point are an inverted version of a low input signal), thus resulting in a high first input signal to the OR gate 122. As a result, at t3, the output from the OR gate 122 goes high. The enable signal to the flip-flop 102' thus goes high, and the flip-flop 102' copies, at U, data from its input to its output. At t 5 , the output of the flip-flop 102' goes high resulting in a high
ACKNOWLEDGE signal 106 to the preceding control device, and a high REQUEST signal 112 to the subsequent control device. Consequently, at t 6 , the output from the first AND gate 118 goes low as a result of the REQUEST signal 112 going high. After the output of the AND gate 118 goes low the output of the OR gate 122 also goes low, at t 7 , and thus the enable signal to the flip-flop 102 goes low. At this point a data copy in the pipeline is completed and one full stage operation.
Also at tη, resulting from the REQUEST signal 112 going high, the
ACKNOWLEDGE signal 110 goes high as data reaches the subsequent control device, and the REQUEST signal 108 from the preceding control device goes low. At t 8 , the output from
second AND gate 120 goes high resulting in, at tg, the output from the OR gate 122 to go high and thus, the event/flank controlled flip-flop 102' copies data from its input to its output.
The data copying results in that, at t 10 , the output from the second AND gate 120 goes low, resulting in, at t l ls the OR gate 122 going low and a low REQUEST signal 112 and a low ACKNOWLEDGE signal 106. At the same time the ACKNOWLEDGE signal 110 from the subsequent control device generates a low level. At this point, the logic levels of the different gates 118, 120, 122 are all low, and the operation is back to the initial state. The enable signal which is provided to flip-flop 102 has thus gone through two complete cycles, and two data elements have been passed through the pipeline. In conclusion, it is according to the present invention possible to provide a new asynchronous control device for controlling an asynchronous pipeline, wherein the control device comprises control logic and a non-transparent memory element. By using a non-transparent memory element in the control device it is possible to utilize standard cell technologies having inbuilt design- for-test technology, thus reducing the design- for-test overhead. Using less design- for-test overhead leads to a less expensive pipeline having less complex timing constraints.
While the invention has been illustrated and described in detail in the drawings and foregoing description, such illustration and description are to be considered illustrative or exemplary and not restrictive; the invention is not limited to the disclosed embodiments. For example, it is possible to operate the invention in an embodiment wherein a pipeline also has so-called join or fork stages. In a join stage, multiple request signals come in from the preceding stage and can be combined in the control unit 104' as a generalization of Fig. 3c. In a fork stage, the data from a stage flows to multiple subsequent stages, which each generate their own acknowledge, which are then combined in the control unit 104'. An additional advantage of the invention is that such generalization gives rise to only a more complex combinational function in the control unit 104', whereas in prior art approaches the control device 100 as a whole is complicated or an additional control device is needed to implement the synchronization of multiple incoming request or acknowledge signals.
Furthermore, it is to be noted that it is possible, and within the scope of the invention, to design computational processes that are based on both a previous and the current stage in the pipeline, i.e. for data present before and after a data holding element. Such an approach was complicated using prior art solutions, but is straight forward using a pipeline according to the present invention.
Other variations to the disclosed embodiments can be understood and effected by those skilled in the art in practicing the claimed invention, from a study of the drawings, the disclosure, and the appended claims. In the claims, the word "comprising" does not exclude other elements or steps, and the indefinite article "a" or "an" does not exclude a plurality. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measured cannot be used to advantage. Any reference signs in the claims should not be construed as limiting the scope.
Next Patent: SYSTEM AND METHOD FOR GENERATING INDIVIDUALIZED EXERCISE MOVIES