Generic ILP-based approaches for dynamically reconfigurable FPGA partitioning

Guang Ming Wu, Jai Ming Lin, Chia-Tso Chao, Yao Wen Chang

Research output: Contribution to journalArticlepeer-review


Due to the precedence constraints among vertices, the partitioning problem for dynamically reconfigurable FPGAs (DRFPGAs) is different from the traditional one. In this paper, we first derive logic formulations for the precedence-constrained partitioning problems, and then transform the formulations into integer linear programs (ILPs). The ILPs can handle the precedence constraints and minimize cut sizes simultaneously. To enhance performance, we also propose a clustering method to reduce the problem size. Experimental results based on the Xilinx DRFPGA architecture show that our approach outperforms the list scheduling (List), the network flow based (FBB-m), and the probability based (PAT) methods by respective average improvements of 46.6%, 32.3%, and 21.5% in cut sizes. Our approach is practical and scales well to larger problems; the empirical runtime grows close to linearly in the circuit size. More importantly, our approach is very flexible and can readily extend to the partitioning problems with various objectives and constraints, which makes the ILP formulations superior alternatives to the DRFPGA partitioning problems.

Original languageEnglish
Article number50
Pages (from-to)335-341
Number of pages7
JournalProceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors
StatePublished - 1 Jan 2001


Dive into the research topics of 'Generic ILP-based approaches for dynamically reconfigurable FPGA partitioning'. Together they form a unique fingerprint.

Cite this