A synthesis methodology for multiple scan trees that considers output pin limitation, scan chain routing length, test application time and test data compression rate simultaneously is proposed in this thesis. Multiple scan trees, also known as a scan forest, greatly reduce test data volume and test application time in SOC testing. However, previous research on scan tree synthesis rarely considered issues such as routing length and output port limitation, and hence created scan trees with a large number of scan output ports and excessively long routing paths. The proposed algorithm provides a mechanism that effectively reduces test time and test data volume, and routing length under output port constraint. As a result, no output compressors are required, which significantly reduce the hardware overhead.

An interconnect-driven layout-aware multiple scan tree synthesis methodology is proposed in this paper. Multiple scan trees, also known as a scan forest, greatly reduce test data volume and test application time in SOC testing. However, previous researches on scan tree synthesis rarely considered routing length issues, and hence create scan trees with excessively long routing paths. The proposed algorithm effectively considers both test compression rate and routing length and hence produces better results than all previous known methods in both regards. In this method, a density-driven dynamic clustering algorithm is applied to determine scan cells in each scan tree. A compatibility based clique partition algorithm is used to determine tree topology, and then a Voronoi diagram is used to establish physical connections. Compared with previous works on scan tree synthesis, the proposed method reduces test data volume by 1.4X to 2.1X, while the reduction in test application time ranges from 15.9X to 24.6X. The significant improvement in test application time is mainly due to the multiple scan trees architecture. The final routing structure is also better, as 1.3X to 3.2X reduction in routing length is achieved.