New insights into hypergraph layout

In this work, we represent cells as vertices and signal nets as edges that connect two or more vertices. Collectively, the set of vertices and multi-point edges is known as a hypergraph. Our work deals with the hypergraph layout problem which consists of the partitioning problem and the vertex ordering problem. The goal is to order the rows and columns of the sparse matrix to put them in a form where the non-zero entries are packed as tightly along the (geometric) diagonal as possible. This ordering corresponds to a one-dimensional placement of vertices.; Our first contribution is a new analytical model for one-dimensional vertex placement as a minimization of a quadratic connectivity matrix over a hyperellipse with principal axes scaled by vertex weights. We show that this formulation yields superior results compared to two other analytic formulations when applied to the bipartitioning problem. The solution of our optimization problem is a one-dimensional vertex placement that results in both a reduced wiring cost and improved spacing between cells due to our minimizing over a hyperellipse.; Our next contribution is a multilevel implementation of the ordering technique that yields high-quality matrix ordering results when compared to two other well-known matrix ordering methods. Furthermore, since our technique works with rectangular matrices, it can also be used on problems from other domains that require the ordering of rectangular matrices directly. The potential applications of this technique to problems in many domains is perhaps its most salient feature.; Our final contribution is an integer linear program formulation of hypergraph partitioning into k blocks that incorporates fixed vertices and adjustable vertex-degree balance constraints. We prove that by removing constraints that place an equal number of vertices in each block in the bipartitioning problem, the maximum number of uncut nets can be obtained in polynomial time. We show how by intelligently assigning the fixed vertices to blocks, we can simplify the problem considerably. We then solve the model using two blocks for test problems up to 15000 vertices, thereby obtaining globally optimal bipartitioning solutions with fixed vertices for the first time. In the process, we confirm that multilevel methods do indeed produce high-quality solutions. (Abstract shortened by UMI.)...