Fast Scan-Chain Ordering for 3-D-IC Designs Under Through-Silicon-Via (TSV) Constraints

This brief addresses the problem of scan-chain ordering under a limited number of through-silicon vias (TSVs), and proposes a fast two-stage algorithm to compute a final order of scan flip-flops. To enable 3-D optimization, a greedy algorithm, multiple fragment heuristic, is modified and combined with a dynamic closest-pair data structure, FastPair, to derive a good initial solution in stage one. Stage two initiates two local refinement techniques, 3-D planarization and 3-D relaxation, to reduce the wire (and/or power) cost and to relax the number of TSVs in use to meet TSV constraints, respectively. Experimental results show that the proposed algorithm results in comparable performance (in terms of wire cost only, power cost only, and both wire-and-power cost) to a genetic-algorithm method but runs two-order faster, which makes it practical for TSV-constrained scan-chain ordering for 3-D-IC designs.