Digital systems continue to increase in size and complexity, and the associated design process has grown lengthy and expensive. A method for partitioning these designs into smaller sub-units is required for board and integrated circuit levels of implementation. In addition, rapid checks of the functionality of a particular design will require a digital system to be partitioned into the set of programmable logic devices that form a system emulator. A merge algorithm for circuit partitioning is presented in this thesis. Results are presented illustrating the performance of a software implementation of this algorithm. These results show that successful circuit partition can be efficiently achieved. The merge algorithm is based on the simple concept that cells having the maximum number of connections should be the first to be merged. Merging starts with a predefined initial size constraint on circuit groups, and it is implemented in several stages. In each stage, the size constraint on groups is enlarged to keep the merge operation active. A free competitive merge strategy followed by a leading groups merge strategy is used to ensure a good size balance between the finally partitioned groups. A pseudo-parallel merge algorithm is presented to reduce the processing time when the design to be partitioned is large. This facilitates rapid exploration of possible partition solutions. A data parallelism approach is adopted which distributes data to a number of processors. Each processor contains the same merge algorithm program operating on a different segment of the circuit netlist. Results are presented showing that the pseudo-parallel merge algorithm reduces the time to partition a circuit while maintaining the same quality of result. The predicted performance of a fully parallel implementation of the merge algorithm is also investigated. Practical and computer generated netlist are used to investigate the performance of the experimental partitioning software system.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:660953 |
| Date | January 1995 |
| Creators | Rau, Go-An |
| Publisher | University of Edinburgh |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://hdl.handle.net/1842/14257 |
Page generated in 0.0023 seconds