Layout-driven chaining of scan flip-flops

In an era of submicron technology, routing is becoming a dominant factor in area, timing and power consumption. The problem of scan flip-flops chaining with the objective of achieving minimum routing area overhead is studied. The first attempt is to chain the flip-flops at the logic level. To make more accurate decisions on chaining flip-flops, the second attempt is to perform the chaining of scan flip-flops taking layout information into consideration. Specifically, the authors show that the chaining problem is a travelling salesman problem (TSP). Then, two heuristics, greedy and matching-based algorithms, are proposed to solve the TSP problem. Various cost functions are defined which take layout information into account. Benchmarking results show that the cost function achieves the best results when it considers placement and routing information and is dynamically updated