A hardware/software co-design of the Fiduccia-Mattheyses partitioning algorithm.

摘要

The Fiduccia-Mattheyses (F-M) algorithm has proved to be an efficient algorithm for circuit partitioning, and it is widely used for several physical design automation applications. As digital circuits are becoming larger and more complex, algorithms such as the F-M algorithm are becoming slower and less efficient.;The goal of this research is to accelerate the performance of the F-M algorithm by using a hardware/software codesign approach on a Field Programmable Gate Array (FPGA) chip. The thesis investigates the tradeoffs between the flexibility and the performance of the hardware/software codesign approach; it also investigates the application of the codesign approach to the algorithms that require intense memory access operations such as pointer-related and linked-list based operations.;To accelerate the F-M algorithm, an embedded computing system based on an FPGA chip was proposed, where a speedup hardware module handles the computationally intensive functions while an embedded processor (MicroBlaze) handles intense memory access operations that cannot be implemented efficiently on the dedicated hardware.;The F-M algorithm was implemented using two approaches: (i) a pure-software implementation based on the MicroBlaze, (ii) a hardware/software codesign approach based on the MicroBlaze and a dedicated hardware module. To further identify the performance of the two above mentioned approaches, a Local Search algorithm similar to the F-M algorithm was implemented using a pure-hardware based approach. (Abstract shortened by UMI.)