Generic ILP-based approaches for time-multiplexed FPGA partitioning
Resource
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 20 (10): 1266-1274
Journal
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Journal Volume
20
Journal Issue
10
Pages
1266-1274
Date Issued
2001
Author(s)
Abstract
Due to the precedence constraints among vertices, the partitioning problem for time-multiplexed field-programmable gate arrays (TMFPGAs) 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 TMFPGA architecture show that our approach outperforms the list-scheduling (List), the network-flow-based (FBB-m) (Liu and Wong, 1998), and the probability-based (PAT) (Chao, 1999) 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 TMFPGA partitioning problems.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
08.pdf
Size
346.13 KB
Format
Adobe PDF
Checksum
(MD5):bdb943b20e5a051b3f486963b8911c3e