Performance optimization of pipeline circuits with latches and wave pipelining.

The use of level-sensitive latches and wave-pipelining techniques are two aggressive methods to increase the performance of pipelined circuits. However, they do present difficult analysis and design problems that heretofore have prevented active use and full exploration of these techniques. To tackle these barriers, this dissertation solves three related problems: finding the optimal single-phase clock schedule for latch-based closed pipelines, designing stopping and restarting mechanisms for wave-pipelined circuits, and achieving a desired clock rate by inserting latches to balance the delays of a wave-pipelined circuit. The optimal single-phase clocking problem for latch-based closed pipelines has been difficult to solve because the general latch timing model generates a nonconvex solution space. The best prior approach uses a linear program to solve an overconstrained problem. We present an efficient (cubic complexity) algorithm, Gpipe, that solves the general problem by exploiting the geometric characteristics of the full nonconvex solution space to determine the maximum single-phase clocking rate for a closed pipeline with a specified degree of wave-pipelining. The Long path and Short path timing constraints are examined to prove that a further clock speedup may be obtained by permanently enabling some latches and increasing the degree of wave pipelining. Sufficient conditions are also found to identify which latches can be removed in this fashion while guaranteeing no decrease and permitting a possible increase in the clock rate. Wave pipelining is often avoided in design due, in part, to the difficulty of stopping and restarting a wave-pipelined circuit without losing data. The ability to stop and start a circuit is essential for pipeline stalls and reduced rate testing; however, this problem had not previously been addressed. We have solved this problem by developing a redundant latch mechanism to store the wave-pipelined data. A formal characterization of stoppability and startability indicates where these redundant latches may be inserted within the pipeline and how to sequence the shut down and restart of the clock. Two improved stopping and restarting mechanisms, Pitcher and Catcher, have been developed which place a FIFO queue alongside the beginning or end of each wave-pipelined stage. Chains of delay elements are typically used to increase performance by balancing the min/max path difference of wave-pipelined stages. However, better performance and cost economy can be achieved by inserting latches instead, resulting in an efficient blend of physical stages and wave pipelining to achieve the desired clock rate. A mathematical programming model and efficient heuristics are developed to insert latches with single phase, two phase, or random phase clocks. Experimental results clearly show the performance and cost advantages of using latches.PhDComputer Science and EngineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/104927/1/9624585.pdfDescription of 9624585.pdf : Restricted to UM users only