APPLYING A QUADRATIC ASSIGNMENT MODEL FOR MULTIPARAMETER PLACEMENT OF THE INTEGRATED CIRCUIT ELEMENTS

Abstract

The problem of multi-parameter placement of elements in integrated circuits (ICs) is considered. It is shown that as ICs become increasingly integrated, the physical design stage has an increasingly significant impact on the quality of the IC, and placement becomes a key task in the IC physical design cycle. Since most modern highly integrated ICs are designed using standard library cells or programmable logic arrays with regular physical structures, the model of a discrete switching field is used as the basis for the placement space model. By applying the discrete switching field model, the placement problem is reduced to the well-known quadratic assignment problem in combinatorics. This allows the placement problem to be transformed into a matrix transformation mechanism, and the calculation of quality criteria values to be reduced to matrix calculations. The general form of the placement criterion based on the quadratic assignment problem, as well as its multi-parameter representation, is presented. This form of the criterion allows the calculations to be reduced to the scalar product of the matrices of element connectivity and their placement distances. Furthermore, arbitrary element placement positions correspond to a permutation of the corresponding rows and columns of the connectivity matrix. From an engineering perspective, this means that pairs of elements with stronger connectivity will be placed closer together and vice versa. This makes it possible to estimate the minimum value of the quality criterion without knowledge of the placement structure, which can serve as a measure of the quality of a particular placement option. A multiparameter approach to the placement problem is considered, where only the connectivity matrix of the elements changes to reflect connectivity in one or more parameters. The calculation procedures of the placement algorithm remain unchanged. The main approaches to solving multi-parameter placement problems are outlined, and a simple example is provided to demonstrate the mechanism for applying the quadratic assignment model for multi-parameter element placement.