Hierarchical Krylov subspace based reduction of large interconnects

In this paper, we propose a new model order reduction approach for large interconnect circuits using hierarchical decomposition and the Krylov subspace projection-based model order reduction methods. The new approach, called hiePrimor, first partitions a large interconnect circuit into a number of smaller subcircuits and then performs the projection-based model order reduction on each of subcircuits in isolation and on the top-level circuit thereafter. The new approach is very amenable for exploiting the multi-core based parallel computing platforms to significantly speed up the reduction process. Theoretically we show that hiePrimor can deliver the same accuracy as the flat reduction method given the same reduction order and it can also preserve the passivity of the reduced models as well. We also show that partitioning has large impacts on the performance of hierarchical reduction and the minimum-span objective should be required to attain the best performance for hierarchical reduction. The proposed method is suitable for reducing large global interconnects like coupled bus, transmission lines, large clock nets in the post-layout stage. Experimental results demonstrate that hiePrimor can be significantly faster and more scalable than the flat projection methods like PRIMA and be order of magnitude faster than PRIMA with parallel computing without loss of accuracy. Interconnect circuits with up to 4 million nodes can be analyzed in a few minutes even in Matlab by the new method.