In this thesis, we consider the role of topological and timing parameters to optimize performance-oriented partitioning heuristics while still satisfying realistic device size and terminal constraints.
Problem formulation requires a relatively large set of well-defined parameters.
To the extent possible, we rely on simple examples to motivate and illustrate the use of all definitions as they are being introduced. We begin our discussion by representing the logic circuit as a hypergraph, consisting of the set of nodes and the set of hyperedges. Hypergraph partitioning problems representing VLSI design problems usually involve separating the set of the hypergraph nodes into disjoint subsets while optimizing interconnects between subsets. In such cases, the signal flow directions can be disregarded. On a contrary, minimization of critical delays requires the knowledge of signal flow directions, the intrinsic signal delays through the nodes and edges, as well as the knowledge of the existence of critical paths in the circuit.