Dynamic pipelining approach for high performance circuit design

Details Dynamic pipelining approach for high performance circuit design Dynamic pipelining approach for high performance circuit design

1999-12-29

2003-07-15

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

06594814

ABSTRACT:

FIELD OF THE INVENTION
The invention presents a new method for high performance hardware circuit pipelining; by using the said dynamic pipelining method, it is capable of enabling variant-iteration-execution-time circuits in run-time determined latencies to achieve the optimal pipeline speed.
BACKGROUND OF THE INVENTION
Getting a higher performance is one of the most important goals of designing Application Specific Integrated Circuits (ASIC's). The action of an ASIC often contains the time-consuming loops. To optimize the performance efficiently, the parallelism hidden in the repetitive loops must be located, and then pipelined. In the past, many pipelining techniques have been developed to explore the parallelism of loops in an ASIC. Functional pipelining, proposed by many people such as E. M. Circzyc (in the
Proc. of the International Symposium Circuits and Systems
(ISCAS), pp. 382-385, in 1987.), is used to pipeline the execution of the loop with acyclic iterations. On the other hand, loop pipelining or software pipelining, such as the methods revealed by A. Aiken et. al. (in
Proc. ACM SIGPLAN
'88
Conf.
on Prog. Lang. Design and Implementation, 1988.) and by M. Lam (in
Proc. ACM SIGPLAN
'88
Conf
on Prog. Lang. Design and Implementation, pp.318-328, 1988.), is applied to explore the parallelism across iterations of the loop with cyclic iterations. Structured pipeline uses the pipelined functional units to prompt the ASIC performance. Other approaches such as that proposed by J. P. Sheu, et. al. (in
IEEE Trans. on Parallel and Distributed Systems,
Vol. 2, No. 3, July 1991.) have been proposed to find the potential parallelism of nested loops. In addition, many patents have proposed different pipelining methods for enhancing circuit performance such as U.S. Pat. Nos: 4,677,549, 4,742,453, 5,079,736, 5,428,756, and 5,684,422. However, these approaches might handle only nested loops with constant loop-iteration numbers and the execution time of each iteration in them is fixed.
DESCRIPTION OF THE PRIOR ART
For a pipeline design, consecutive two iterations of a loop are initiated at a time interval called latency. In existing pipelining techniques, the latencies of a pipeline are all set as a fixed value or some fixed values. However, in the loops of many ASICs, variant iteration execution time and time-relative data dependencies between different iterations make them to be impossibly or inefficiently pipelined, because the values of the pipeline latencies cannot be fixed and be known in advance. To solve such problems, the fixed latency assumption must be removed and more flexibility is needed. Here, a new pipeline design approach for high performance ASICs, called dynamic pipelining, is invented to pipelinely designing those ASIC loops using variant latencies efficiently.
The invention is even more suitable for the circuit's loops with the factor of inconsistent execution time for each iteration and/or the number of iterations unfixed. The traditional pipelining approach cannot resolve such problems, while by using the variant latencies pipeline of the invention, the pipelining of time-variant loops and then time-efficiency of the circuit can be successfully achieved.
Moreover, the cost of hardware using the proposed design method is at the same class as that of the traditional pipelining design: it would increase the quantity of state registers, certain hardware components as well as the complexity of its control circuit. The amount of these increased hardware components varies according to the different designs, and cannot be quantitatively explained. Despite which, it is generally acceptable just as the design of conventional pipelining has been, which could be seen from the results of our empirical study.
SUMMARY OF THE INVENTION
The object of the invention is to expose a new type of pipelining method applicable for high performance digital circuits. By using the said dynamic pipelining method, it can effectively pipeline circuits of time-variant loops in run-time determined latencies to achieve the goal the optimal pipeline speed.
In addition, the invention further proposes a coordinated type of controller for the dynamic pipelined circuit, which consists of two coordinated finite state machines and enables the dynamic pipelined datapath to execute at variant latencies.
All those acquainted with the skill of pipelining will undoubtedly be very clear of the objective and advantages revealed by the invention after the going over the explanation and the examples cited in the following along with the drawings.


REFERENCES:
patent: 5778250 (1998-07-01), Dye
patent: 5918042 (1999-06-01), Furber
patent: 6275969 (2001-08-01), Lakshminarayana et al.
patent: 6298472 (2001-10-01), Phillips et al.
Jou et al, “A New Pipelined Architecture for Fuzzy Color Correction,” IEEE, Jan. 1999, pp. 209-212.*
Tseng et al, “A New Tru-Single-Phase-Clocking BiCMOS Dynamic Pipelined Logic Family For High-Speed Low-Voltage Pipelined System Applications,” IEEE, Jan. 1999, pp. 68-79.*
Jou et al., “Pass: A Package For Automatic Scheduling And Sharing Pipelined Data Paths,” p. 4, 1991.
Adam et al., “A Comparison of List Schedules For Parallel Processing Systems,” Communications of the ACM, University of Texas at Austin (Austin, Texas), vol. 17 (No. 12), p. 6, (Dec. 29, 1974).
E.F. Girczyc, “Loop Winding--A Data Flow Approach to Functional Pipelining,” (Dec. 29, 1987).
Potasman et al., “Percolation Based Synthesis,” 27th ACM/IEEE Design Automation Conference, vol. 25 (No. 1), p. 6, (Dec. 29, 1990).
Jun, et al., “Automatic Synthesis of Dynamically Configured Pipelines Supporting Variable Data Initiation Intervals,” IEEE Transactions on Very Large Scale Integrations (VLSI) Systems, Sogang University (Seoul, Korea), vol. 4 (No. 2), p. 7, (Dec. 29, 1996).
Rim et al., “Valid Transformations: A New Class of Loop Transformations for High-Level Synthesis and Pipelined Scheduling Applications,” IEEE Transactions on Parallel And Distributed Systems, vol. 7 (No. 4), p. 12, (Dec. 29, 1996).

Affiliated with

Also associated with

Rating

Dynamic pipelining approach for high performance circuit design does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic pipelining approach for high performance circuit design, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic pipelining approach for high performance circuit design will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3049280