An efficient algorithm for 3D-IC TSV assignment

In this work we solve the 3D-IC TSV assignment which is formulated as an Integer Minimum Cost Multi Commodity (IMCMC) problem. We propose a multi-level algorithm including graph coarsening and un-coarsening, to greatly reduce the IMCMC problem size; benefiting from it, we transform the IMCMC problem into a mixed single and multi commodity problem and partially solved it using min-cost flow method. Further, we extend the layer by layer method for TSV assignment optimization. The experimental results shows that the our proposal generates initial solutions with 2.8% wire length reduction compared to the existing work, and our extended layer by layer method achieves another 1.7% improvement with slight time overhead.