Browse Theses

In this dissertation we address the System Partitioning problem under various hardware constraints. The objective of System partitioning is to minimize the amount of signal interconnection among different partitions and to assess the physical feasibility of implementing a system on a particular hardware package. A system partitioning problem is similar to a circuit partitioning problem except that each component in the system partitioning problem can be a high level functional block instead of just low level gates. A constrained system partitioning problem emphasizes the fact that a feasible partitioning solution must satisfy certain Capacity, Timing and/or I/O Constraints. Capacity Constraints require that the total size of all components assigned to the same partition be no larger than the capacity of that partition. Timing Constraints require that the signal routing delay plus total gate delay between any pair of adjacent registers be no larger than the given system cycle time. I/O Constraints require that the total number of I/O pins consumed on each partition (for connecting system components) not exceed the number of available pins.

Our overall approach is to formulate the Constrained System Partitioning Problem as an Integer Programming Problem and apply/invent various techniques to solve this problem. We analyzed the problem structure and discovered this general problem (as well as two special cases) have special structure that can be exploited to obtain efficient and effective solutions. We studied the relationship of this problem and other similar, existing problems and identified some good heuristics (e.g. Martello & Toth, Burkard & Bonniger) which inspired us to derive our own solution.

We also describe the innovative data structure/implementation we used for handling large scale problems. Several industrial test cases are used to demonstrate the effectiveness of our approach compared to the well known Fiduccia & Mattheyses heuristic. Test results showed that our approach achieved high quality solutions and are able to handle simultaneous Capacity, Timing, and I/O Constraints.

We conclude this dissertation by indicating possible direction for future work, which includes application to chip/module level placement/floorplanning and pin assignment problems.