Architecture driven k-way partitioning for multichip modules

A new k-way partitioning approach for multichip modules (MCM) is described. We apply an analytical technique combined with a problem-specific multi-way ratio cut method. Our method considers fired MCM pad positions on the substrate border and assigns the cells to regularly arranged chips on the substrate. For the first time, k-way partitioning results of benchmark circuits with up to 100,000 cells are presented. They show an excellent solution quality in terms of cut nets as well as a low maximum and average number of required chip-level pads for each chip. The average improvement of the number of cut nets compared to a recently published eigenvector-tabu-search approach is about 25%