a01 Hypergraph Partitioning via Geometric Embeddings

Abstract Hypergraph partitioning has been used in many VLSI domains such as floor-planning, placement, and logic synthesis. Circuits are modeled as hypergraphs in which nodes represent the pins of the circuit and hyperedges represent nets from the output pin of a gate to the input pins of other gates, and the nodes are partitioned into a desired number of clusters so that a metric such as the number of cut hyperedges is minimized. Existing hypergraph partitioning techniques consider only the topology of the hypergraph (connectivity between nodes) and ignore its geometry (positions of nodes in 2D or 3D space). This can lead to sub-optimal partitioning. In this paper, we describe an embedding-based approach for hypergraph partitioning that considers the geometry of circuits, which leads to better quality partitions, while ensuring strong determinism. Authors Sepideh Maleki [email protected] (University of Texas at Austin) Udit Agarwal [email protected] (UT Austin) Keshav Pingali [email protected] (The University of Texas at Austin)