Hierarchical Partitioning for Field-Programmable Systems

This paper presents a new recursive bipartitioning algorithms targeted for a hierarchical field-programmable system. It draws new insights into relating the quality of bipartitioning algorithm to circuit structures by the use of the partitioning tree [11]. The final algorithm proposed not only forms the basis for the partitioning solution of a 1-million gate Field Programmable System [1] but can also be applied to general VLSI or multiple-FPGA parti-tioning problems. The reprogrammability of FPGAs has made possible a number of systems for rapid prototyping and emulation. These multiple-FPGA designs, primarily aimed at ASIC applications, tend to be severely pin limited. Since the pi