SPECTRAL-BASED MULTIWAY FPGA PARTITIONING

Recent research on FPGA partitioning has focused on finding minimum cu ts between partitions without regard to the routability of the partiti oned subcircuits. In this paper, we develop a spectral approach to mul tiway partitioning in which the primary goal is to produce routable su bcircuits while maximizing FPGA device utilization. To assist the part itioner in assessing the routability of the partitioned subcircuits, w e have developed a theory to predict the routability of the partitione d subcircuits prior to partitioning. Advancement over previous work is evidenced by results of experiments on standard MCNC benchmarks.