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.