Markov Clustering-Based Placement Algorithm for Hierarchical FPGAs

【摘要】 Divide-and-conquer methods for FPGA placement algorithms including partition-based and cluster-based algorithms have shown the importance of good quality-runtime trade-off.This paper describes a cluster-based FPGA placement algorithm targeted to a new commercial hierarchical FPGA device.The algorithm is based on a Markov clustering algorithm that defines a sequence of stochastic matrices operating on a generating matrix from the input FPGA circuit netlist.The core of the algorithm tightly couples a Markov clustering process with a multilevel placement process.Tests show its excellent adaptability to hierarchical FPGAs.The average wirelength results produced by the algorithm are 22.3% shorter than the results produced by the current hierarchical FPGA placer.更多还原

【Abstract】 Divide-and-conquer methods for FPGA placement algorithms including partition-based and cluster-based algorithms have shown the importance of good quality-runtime trade-off.This paper describes a cluster-based FPGA placement algorithm targeted to a new commercial hierarchical FPGA device.The algorithm is based on a Markov clustering algorithm that defines a sequence of stochastic matrices operating on a generating matrix from the input FPGA circuit netlist.The core of the algorithm tightly couples a Markov clustering process with a multilevel placement process.Tests show its excellent adaptability to hierarchical FPGAs.The average wirelength results produced by the algorithm are 22.3% shorter than the results produced by the current hierarchical FPGA placer.更多还原