Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Development and Comparative Analysis of Initial Placement Methods for FPGA
Authors
	Frolova P.I.
	Chochaev R.
Date of publication
	2021
DOI
	10.31114/2078-7707-2021-3-57-64
Abstract
	n this paper, we analyze different ways of generating initial placement for island-style FPGAs. In this work we consider five algorithms: random, force-directed, input/output ranking, and line-by-line. After each initial placement we performed optimization using a simulated annealing followed by routing. In the random algorithm, for each logic element random legal coordinates are iteratively generated. In the force-directed algorithm, the legal placement areas for flip-flops are determined firstly, and then each logic element is placed to the placement site closest to its center of mass. Line-by-line placement is done sequentially in each line from left to right starting from the top. In the ranking algorithm the position of the element on the paths, rank, from inputs to outputs and vice versa is considered. An element rank is calculated using breadth first search. The ranking algorithm is performed separately from input and output cells. The elements are placed starting with the lowest rank using a force-directed algorithm. The obtained results showed that the initial placement can affect the runtime of simulated annealing, placement quality, and, as a result, the performance of circuits. On average, the input ranking algorithm generated placement with the smallest delays, followed by the random and the force-directed algorithms. Placements generated by the force-directed and ranked algorithms have better wirelength. However, the line-by-line and random algorithms did not generate a routable placement for some case.
Keywords
	FPGA, initial placement, electronic design automation (EDA)
Library reference
	Frolova P.I., Chochaev R. Development and Comparative Analysis of Initial Placement Methods for FPGA // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2021. Issue 3. P. 57-64. doi:10.31114/2078-7707-2021-3-57-64
URL of paper
	http://www.mes-conference.ru/data/year2021/pdf/D066.pdf