Layout Driven Selection and Chaining of Partial Scan Flip-Flops

In an era of sub-micron technology, routing is becoming a dominant factor in area, timing, and power consumption. In this paper, we study the problem of selection and chaining of scan flip-flops with the objective of achieving minimum routing area overhead. Most of previous work on partial scan has put emphasis on selecting as few scan flip-flops as possible to break all cycles in S-graph. However, the flip-flops that break more cycles are often the ones that have more fanins and fanouts. The area adjacent to these nodes is often crowded in layout. Such selections will cause layout congestion and increase the number of tracks to chain the scan flip-flops. To take layout information into consideration, we propose a matching-based algorithm to solve the problem. First, an initial placement will be performed before scan flip-flops are selected. Then, iteratively, a matching-based algorithm taking the current layout into account is proposed to select and chain the scan flip-flops. Experimental results show that, on the average, our algorithm can reduce 8.1% area overhead as compared with the previously proposed methods that do not utilize the layout information in flip-flop selection.