Scan Chain Optimization: Heuristic and Optimal Solutions

[[abstract]]We present new methods for scan chain ordering under the minimum wirelength objective. We have adapted the standard 2-opt and 3-opt heuristics for the symmetric traveling salesman problem (TSP) to scan chain ordering, which can be formulated as an asymmetric TSP. We show that our method is superior to a previous approach, which transformed the scan chain problem so that symmetric TSP heuristics could be applied directly. Our implementation is very efficient, requiring only O(n 2 ) time, and allows a number of user-specified options, including grouping of scan cells, priority assignment, and a preferred wiring direction. We also present an new optimal scan chain algorithm for the special case when one wiring direction is infinitely preferred over the other (for example, if feedthroughs must be minimized). This algorithm is based on dynamic programming and can also be implemented in O(n 2 ) time. 1 Introduction One of the primary objectives for design-for-test is to minimize the hard.[[fileno]]2030222010007[[department]]資訊工程學