A fast eigenvector technique for obtaining good initial node partitions of netlists for use in interchange heuristics is described. The method is based on approximating the netlist or hypergraph by a weighted graph G, such that the sum of the cut edges in G tightly underestimates the number of cut nets in any netlist partition. An eigenvector technique is used to partition the graph G into k blocks of fixed module size. Another feature of this graph underestimation model of the netlist is that it allows one to obtain lower bounds on the actual number of cut nets. A multiblock node interchange heuristic is tested on the one resulting netlist partition obtained by this eigenvector approach on a variety of small to large sized benchmark netlist partitioning problems (between 300 to 12000 modules and nets). Test results on the larger netlists show that in most cases this eigenvector-node interchange approach yields netlist partitions with comparable or fewer cut nets than the best netlist partitions obtained by using node interchange heuristics alone on many random initial netlist partitions.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Partitioning of circuit netlists in VLSI design is considered. It is shown that the second smallest eigenvalue of a matrix derived from the netlist gives a provably good approxi...
Let a k-partition of a graph be a division of the vertices into k disjoint subsets containing m <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.or...
A signal space code C is defined as geometrically uniform if, for any two code sequences in C, there exists an isometry that maps one sequence into the other while leaving the c...
Starts with a brief review of the history and the application areas considered in the literature. The author then proceeds with introductory modeling examples, behavioral and st...
Computing graph separators is an important step in many graph algorithms. A popular technique for finding separators involves spectral methods. However, there has not been much ...
Social media, news, blog, policy document mentions