Geometric embeddings for faster and better multi-way netlist partitioning

摘要: We give new, effective algorithms for k-way circuit partitioning in the two regimes of k ≪ n and = ⊝(n), where is number modules circuit. show that an appropriately designed geometric embedding netlist, rather than a traditional graph representation, yields improved results as well large speedups. derive d-dimensional embeddings netlist via (i) new "partitioning-specific" net model constructing Laplacian (ii) computation d eigenvectors Laplacian; we then apply (iii) fast top-down bottom-up clustering methods.