Title: A Hardware/Software Co-design of Fiducia/Mattheus Partitioning Algorithm

By Fujina Li, December 2005

Abstract:
The rapidly increasing size and complexity of digital circuits place a stressing demand for faster and more
efficient techniques for VLSI physical design automation. Circuit partitioning is the first stage in the VLSI
physical design automation, significantly affecting the results of other stages. F-M algorithm has proved to be an
efficient approximate-solution algorithm for circuit partitioning, but digital circuits are becoming larger and
larger. There is a need to speed up the F-M algorithm.

Although Application Specific Integrated Circuits (ASICs) can achieve speedup over general-purpose processors, its
major disadvantage is inflexibility.
Reconfigurable computing is a relatively new area of computing. Reconfigurable Computing Systems (RCSs) are filling
the gap between performance (ASICs) and flexibility (general-purpose processors). Today the capacity of FPGAs has
increased to the point where both an embedded processor and dedicated hardware can be built on a single FPGA chip.
This provides an excellent platform for hardware/software co-design approach to design a system using both software
and speedup hardware. To accelerate the F-M algorithm, an embedded computing system consisting a MicroBlaze
processor and speedup hardware on an FPGA chip is proposed, where the computationally intensive modules are
implemented in reconfigurable hardware while the MicroBlaze performs the operations that cannot be executed
efficiently in hardware. The Xilinx MicroBlaze processor is the industry's fastest soft processor built on FPGAs.