This paper presents a partitioning-based, timing-driven placement algorithm. The partitioning step itself is timing-driven and based on solving a quadratic programming problem iteratively. The placement algorithm does not rely on interleaved timing calculations, which tend to be inaccurate. Instead, it achieves the desired result by controlling the number of times that a path in the circuit can be cut. In addition to the cutting constraint, a pre-locking mechanism and timing-aware terminal propagation are developed and integrated into the flow. The detailed placement step is formulated as a constrained quadratic program and solved efficiently. Results show improvements of 23.41% on average compared to another timingdriven placement system Timing-QUAD and significant improvements over Eisenmann's placement algorithm. Steady advances in semiconductor technology have resulted in significant improvements in the performance of CMOS devices. For these improvements to translate to the VLSI circuit and system designs, one must resort to powerful, timing-aware computer aided design techniques and tools at all levels of design abstraction, including architecture logic and physical level. A good placement tool must be capable of minimizing the maximum circuit delay by reducing the delays of interconnects along the timing critical paths. This is a challenging task because of the large number of paths that must be considered and the complex inter-dependence among the various paths. Timing-driven placement schemes have been classified as either net-based . Net-based algorithms seek to control the delay on a signal path by imposing a delay upper-bound or by assigning a weight to each net. The netbased approach usually overconstrains the placement algorithm. Path-based approaches model the problem correctly, but are only applicable to small circuits since explicit enumeration of all paths is an intractable task. As a result, most of the timing-driven placement algorithms proposed to-date are net-based [8] [9] [10]. More precisely, they perform circuit placement by interleaving a timinganalysis step with a placement step. The timing-analysis step is responsible for identifying the critical nets. The weights of the circuit nets are updated based on their timing criticality. The placement step then determines the relative locations of gates according to the net weights. These two steps are interleaved until the target delay is achieved or the current result cannot be further improved. The timing analysis techniques used in this two-step flow are standard. The methods used for identifying the critical nets and the placement technique that vary from one implementation to next. The authors of [8] adopt a quadratic objective function formulation for minimizing the wire length. They also perform a longest path calculation during each timing analysis step. The weights of nets along the critical path are updated by adding a constant to the corresponding edge weights. This approach however suffers from some major weaknesses. The first drawback is the so-called oscillation problem. This is a commonly-encountered problem in circuits where many paths have nearly the same negative slack. In addition to the oscillation problem, quadratic formulation does not minimize the length of nets, instead, it minimizes the square of edge lengths. As a result, it may result in a number of medium-length nets in order to eliminate one long net. Sometimes however a long net may be a better solution than a number of medium-length nets, for example, when the paths which share this long net have very small intrinsic delays.
Recently, Ou and Pedram REF gave a timing-driven placement algorithm for gate arrays based on a mixture of partitioning and quadratic placement.
Timing-driven placement based on partitioning with dynamic cut-net control
DAC
Computer Science