DEVELOPMENT OF THE DETAILED PLACEMENT ALGORITHM FOR FPGAS

Abstract

Hierarchical field-programmable gate arrays (FPGAs) consist of an array of programmable
logic blocks arranged into groups. Successful routing requires optimal placement of logic elements
within the groups, considering the architectural features of the local interconnections. Classical
algorithms are not able to consider these features. That’s why, the development of new algorithms
is required. In this paper, we present a detailed placement algorithm with a new metric that
allows us to estimate the number of available local interconnections inside the groups of logic
blocks, considering the architectural features of the local interconnections. The detailed placement
algorithm consists of several stages. At the first stage, the group of logic elements is transformed
into a directed graph. Then, the placement order of logic elements in the group is determined using
the breadth-first search algorithm. At the final stage, for each element, according to the obtained
order, the optimal placement in the group is determined, considering the new metric.
If there is no optimal position in the group among the free ones, the occupied positions are
checked. The current element is placed in the occupied position, and a new position is searched
for the replaced element. Such replacements can be performed repeatedly, increasing the probability
of finding the optimal placement configuration. The proposed algorithm was verified on a set
of benchmark circuits ISCAS’85, ISCAS’89, Cpu8080 and VGA. Experimental results show that
the developed algorithm reduces the number of global interconnections used for global routing by
10% on average and increases the number of local interconnections used for detailed routing by
30% on average compared to the sequential placement algorithm. The average routing time remained
unchanged.