Optimizing large multiphase level-clocked circuits

Retiming is a powerful technique for optimizing sequential circuits. The tr ansparent nature of level sensitive latches enables level-clocked circuits to operate faster and require fewer memory elements than edge-triggered cir cuits. However, this transparency makes the operation of level-clocked circ uits very complex, and optimization of level-clocked circuits is a difficul t task. This work presents efficient algorithms for retiming large level-cl ocked circuits. To provide us with a simpler view of the operation of level -clocked circuits, we present the relationship between retiming and clock s kew optimization. We then utilize this relationship to develop efficient re timing algorithms for period and area optimization. For period optimization, We present an algorithm which produces near-optima l results, but is significantly faster than the traditional algorithms. In this approach, we first calculate the best possible clock period and the am ount of motion required for each latch, The latches are then relocated in a n attempt to achieve this period. Area, as measured by the number of latche s in the circuit can be optimized by solving a linear program. We apply eff icient pruning techniques to reduce the size of this linear program, while preserving optimality. Since generating the linear program is a major part of the computational requirements of minarea retiming, we present technique s for efficient generation of the reduced linear program. This enables us t o perform area optimization of large circuits clocked by symmetric multipha se clocks in very reasonable time, without sacrificing optimality, We prese nt results on circuits with up to 56000 gates, performing period optimizati on in under 20 s and area optimization in under 1.5 h.