Title :
Markov clustering based placement algorithm for island-style FPGAs
Author :
Dai, Hui ; Zhou, Qiang ; He, Ou ; Bian, Jinian
Author_Institution :
Dept. of Sci. & Technol., Tsinghua Univ., Beijing, China
Abstract :
Previous divide-and-conquer methods including partition-based and cluster-based placement algorithms have shown the effectiveness of good quality-runtime trade off. This paper proposes a new cluster-based FPGA placement algorithm called CAP, which is based on a Markov clustering algorithm that defines a sequence of stochastic matrices by operating on a generating matrix from the input FPGA circuit netlist. The core of the proposed CAP algorithm is the approach that tightly couples a Markov clustering process with an deterministic placement process. Experimental results demonstrate CAP´s excellent adaptability to island-style FPGAs. The average wirelength results produced by CAP are 11.1% shorter than the wirelength results of VPR.
Keywords :
Markov processes; divide and conquer methods; field programmable gate arrays; matrix algebra; pattern clustering; CAP algorithm; FPGA circuit netlist; Markov clustering based placement algorithm; divide-and-conquer methods; island-style FPGA; partition-based algorithms; stochastic matrices; Clustering algorithms; Coupling circuits; Design methodology; Electronic design automation and methodology; Field programmable gate arrays; Helium; Integrated circuit interconnections; Partitioning algorithms; Stochastic processes; Very large scale integration;
Conference_Titel :
Green Circuits and Systems (ICGCS), 2010 International Conference on
Conference_Location :
Shanghai
Print_ISBN :
978-1-4244-6876-8
Electronic_ISBN :
978-1-4244-6877-5
DOI :
10.1109/ICGCS.2010.5543084