A ready supply of high quality Known Good Die (KGD) is essential for obtaining acceptable Multi-Chip Module (MCM) yields and reducing costs. Unfortunately, the testers needed for testing and screening VLSI chips to supply high quality KGD are quite expensive, especially for high speed or high pin count ICs. In addition, there are issues connected with testing accuracy-the tester environment may limit performance testing because of interconnect length and capacitance, and with burn-in-which may require temporary packaging of die. Building special test equipment is only cost effective if production volumes are large. Hence, a low cost alternative for at-speed testing that yields high quality die is needed to drive down the cost of low volume or prototype MCMs. This paper describes a double-blind experiment devised to prove the viability of a KGD methodology based upon wafer level test-using embedded performance testing circuits-and wafer level burn-in.

The authors analyze the computational complexity of the constrained via minimization problem. Given an already routed circuit, the problem is to find a minimum cardinality set of vias for which a valid layer assignment exists using only two layers. The authors first prove that the corresponding decision problem is NP-complete. They then show that it remains NP-complete even if one or more of the following restrictions are imposed: (1) the input layout must conform to a rectangular grid; (2) vias are restricted to lie at junctions which existed in the input layout; and (3) the maximum junction degree is limited to six or more.>

This paper describes a graph theoretic algorithm which, given a particular layout, finds a layer assignment that requires the minimum number of vias. The time complexity of the algorithm is Ο(n3) where n is the number of routing segments in the given layout. Unlike previous algorithms, this algorithm does not require the layout to be grid based and places no constraints on the location of vias or the number of wires that may be joined at a single junction. The algorithm yields globally optimum results when the maximum junction degree is limited to three and has been fully implemented.