The statement of one problem of optimum accommodation of modules on a chip as a linear Euclidean combinatorial problem on poly- partial permutations and its special classes are presented. The software for the problem based on investigated polyhedral and combinatorial properties is considered. VLSI, module, chip, placement, linear combinatorial optimization, partially Let us consider the issue of optimizing microcircuits, which are the main components of modern technology, which is relevant to the rapid growth of the capabilities of technical devices and the requirements for them. In particular, consider one problem of placing rectangular modules on a microcircuit. Such a problem in various settings and depending on the optimization criterion appeared COLINS-2022: 6th International Conference on Computational Linguistics and Intelligent Systems, May 12-13, 2022, Gliwice, Poland
in many sources [1], [2], [3]. Traditionally it is considered very difficult [1], [4], [5], [6], because it can always be considered as a two-dimensional packing problem, which is NP-hard [1], [2], [6].
techniques [17].
In recent years, a number of methods have been proposed to solve this problem: based on search adaptation [7], [8], linear and quadratic programming [4], [9], [10], simulated annealing [11], based on evolutionary modeling
methods [12], polyhedral approaches [5], [13]-[16], graph-theoretical
Since theses problems mostly NP-hard optimization problems [4], [9], [10], the development of algorithms are highly relevant, especially those that use specifics of all components of the models targets function, search domain, feasible domain, properties of the corresponding combinatorial polytopes [5], [6], [18]-[19]. We propose a Euclidean Combinatorial Optimization [15], [20]. the approach that explores and utilizes algebraic-topological and geometric properties of the combinatorial set, on which optimization is carried out and subproblems are singled out that can be solved more efficiently due to the specifics.
2020 Copyright for this paper by its authors.
It is necessary to build mathematical models of one problem of the optimal arrangement of modules on a chip in the form of an optimization program over a finite point configuration belonging to a set of Boolean vectors (the Boolean set) and develop a polyhedral approach to solve this problem essentially used explored specifics of the problem and its special cases. Then we aim to build a software package for solving problems of this class implementing our specific approach, from a field of cutting plane methods [13], [21]-[25], to its solution based on the investigated properties of the corresponding combinatorial set embedded in Euclidean space and the corresponding polytope [14].
On a rectangular microcircuit with length L and height H , it is necessary to arrange n modules M i with length li > 0 and height hi > 0 , respectively, in order to minimize the degree of chaos placements of modules, if it is possible to return modules by 900 ( i Jn , Jn = 1,2,...,n ).
Remark 1 By the measure of the randomness of the placement: a) of a module, we will mean the number of other modules that are located diagonally from it; b) of all modules, it is implied the total number of modules situated diagonally from each other.
So, x, y,T Rn , Z R4 N , where N = C2 , need to be found such that:
n x, y 0,T Bn ,Z A' K ( G ),
ms z = n uij → min i, j=1i< j xi − x j − hi ti + L zi1j L'i , x j − xi − hj t j + L zi2j L' j , yi − y j − li ti + H zi3j Hi' , y j − yi − l j t j + H zi4j H 'j , i, j J n , i < j ,
4
uij = zikj − 1,
k=1
(
x = ( xi )iJn , y = ( yi )iJn are vectors of coordinates of all left-bottom corners of modules M i ( i J n ) (the coordinate system origin is located at a left-bottom corner of the module); where where and the following constraints hold: • • placement of the chip: non-overlapping the modules:
' ' xi − hi ti Li , yi − li ti H i , i Jn ; perimeter of M i ( i J n );
T = (t )
i iJn Z = ( Z ) ij i, jJn ,i< j , Zij = ( z k )
ij kJ4 M ,M j (i, j Jn ,i < j ) , namely: i
is a vector of module's orientation parameters: 1,if M i does not rotate ti = 0,if M i rotates 900 degrees , i J ;
n is a vector that determines the relative position of the modules zi1j = 1 , if M i is left from M j ( xi + li xj ), otherwise zi1j = 0 ; zi2j = 1 , if M i is right from M j ( x j + l j xi ), otherwise zi2j = 0 ; zi3j = 1 , if M i is lower than M j ( yi + hi y j ), otherwise zi3j = 0 ; zi4j = 1 , if M i is higher than M j ( y j + hj yi ), otherwise zi4j = 0 ; Bn is Boolean n -vector set [12], [19]; A'4 (G ) is a subsets of a set A4 (G ) of 4 -partial multipermutations [18] induced by 52 52
are vector of additional parameters; pi = hi + li is a semia multiset G = 0,0,0,1,1 , where the sums of the first two and of the last two coordinates of the elements does not exceed one;
A' K ( G ) = A5'42( G ) ms
A5'42( G ) is a poly-4-partial multipermutation set that is a
Cartesian product of N sets of type A5'42 (G ) [10].
Here are two particular cases of the problem simplifying the main problem (
Suppose that some of the modules have a square shape that is Without loss of generality, we can assume that square modules have the first indexes, i.e., i J n : li = hi . 0 n n J
: li = hi i J n = I ; li hi j I = Jn \ J = J {0}).
n 0 n ( J 0 n
In this case, reorientation of Mi (i Jn ) is inexpedient. Therefore the introduction of the variables
ti (i Jn ) of the form (
So, after simplifying the constraints (
x, y Rn ,T Rnn ,Z R4 N
of the form of
that minimize (
x, y 0,T = ( ti )iI Bn ,Z Am'Ks ( G ), • • of placing on the modules (placement constraints):
' ' xi Li , yi H i , i I ,
' '
xi − hi ti Li , yi − li ti H i , i I ;
nonoverlapping constraints:
xi − x j + L zi1j L'i ,
x j − xi + L zi2j L' j ,
yi − y j + H zi3j Hi' ,
y j − yi + H zi4j H 'j ,
i, j I , i < j;
xi − x j + L zi1j L'i ,
x j − xi − hj t j + L zi2j L' j ,
yi − y j + H zi3j Hi' ,
y j − yi − l j t j + H zi4j H 'j ,
i I , j I ,i < j;
xi − x j − hi ti + L zi1j L'i ,
x j − xi + L zi2j L' j ,
yi − y j − li ti + H zi3j Hi' ,
y j − yi + H zi4j H 'j ,
i I , j I ,i < j;
xi − x j − hi ti + L zi1j L'i ,
x j − xi − hj t j + L zi2j L' j ,
yi − y j − li ti + H zi3j Hi' ,
y j − yi − l j t j + H zi4j H 'j ,
i, j I , i < j.
(
As you can see, the dimension of Problem 2 as compared to Problem 1 is slightly less, but its
advantage is that some of the constraints (
Remark 2 If all modules are square, i.e., I = Jn I = { } , we get a problem of finding
0 x L',0 y H',Z A' K ( G ),
ms
which delivers the minimum of (
Let all modules are oriented along the boundaries of the microcircuit, then, as in Problem 2, it is
unnecessary to introduce additional variables (
Remark 2 A certain simplification of the problem (
It is seen that the problem (
To implement the above approach to solving the (
The block for generating the system of constraints and auxiliary information is based on the implemented class Matrix with its methods, operators, indexers and properties.
Further, capital letters A,.., D denote matrices, and lowercase letters a,...,d denote vectors,
A( m,n ) = ( aij )iJm; jJn , A( n ) = ( aij )i, jJn , a( n ) = ( ai )iJn , E,e are unit matrix and a vector of units.
To solve the problem, a system of constraints (
The following functions are implemented in the Matrix class: • static methods that implement matrix concatenation: ( A( m,n1 + n2) = Matrix.ExtendMatrix( A1( m,n1), A2( m,n2)), B( m1 + m2,n ) = Matrix.ExtendMatrixInDown( ;
B1( m1,n ), B2( m2,n ))
E( n ) is generated using the static method of the class operator ( A( m,n ),a( n )) multiplies matrix columns by elements of a given vector methods
MultiplyColsForX ( n, N ,a( n )) ,
MultiplyColsForY ( n, N ,a( n )) are used to generate the matrices B1-B4. Input parameters are: n, N is matrix dimension and a (n) is data array, arranged in columns;
• generation of the specific matrix is carried out using the constructor of the Matrixclass( iRows,iCols,iColValues ) , where iRows,iCols define the dimension of the matrix, iColValues is an array of elements.
Also, matrix multiplication and matrix-scalar multiplication are implemented.
The constraint system is generated using combinations of the above methods and operators of the Matrix class.
Matrices D1, D2 are generated using the operator ( D1( n ) = ( −E( n ),h( n )), D2( n ) = ( −E( n ),l( n )) .
We form matrix A by combining matrices of lower dimension using the static functions ExtendMatrix and ExtendMatrixInDown. We generate matrices of lower dimensions utilizing the constructor of zero arrays of type Matrixclass( n, N ) , with the last unit component and the operator * ( E,( −1)) . We form the matrix B1 using the MultiplyColsForX ( n, N , h ) ( h = h( n ) ) function.
Similarly, a matrix B2 is created using the MultiplyColsForY ( n, N , h ) function. We form matrices B3 and B4 utilizing the functions MultiplyColsForY and MultiplyColsForX with the parameters ( n, N , l ) ( l = l( n ) ).
We form the right side vector of the system using the GetB( H , L,h,l ,n ) function, which uses some auxiliary methods, which outputs are combined with the help of ExtendMatrixInDown into a column matrix. The additional methods perform the following operations: generation ( e = e( n ),h,l ); generation of vectors c1,c2,c3,c4 .
The resulting system of constraints along with auxiliary information is displayed in a spreadsheet for further analysis. In orfer to find the optimal solution to the problem, the GPL.AlgLib library is integrated into the service. It is adapted to solve problems of this type using the proposed combinatorial cutting plane methods [14].
The work presents a mathematical model of a problem of systematized placement of rectangular modules on a microcircuit. For it solution, a service was developed based utilizing ASP.NET technology and the C # programming language. The approach underlying the offered algorithm the problem solution is the preliminary study of geometric and extremal properties of point configurations being a search domain and its convex hulls [20] with further application in the combinatorial cuttingplane method [21].
[17] S. Held, D. Muller, D. Rotter, R. Scheifele, V. Traub, and J. Vygen, Global Routing with Timing Constraints, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, Pp. 1–14. doi: 10.1109/TCAD.2017.2697964. [18] O. Pichugina, Placement problems in chip design: Modeling and optimization, 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), 2017, Pp. 465–473. doi: 10.1109/infocommst.2017.8246440. [19] S. V. Yakovlev O. A. Valuiskaya, Optimization of linear functions at the vertices of a permutation polyhedron with additional linear constraints. Ukr. Math. J., 2001, 53, Pp. 1535-1545. [20] P. Pardalos, D.-Z. Du, and R. L. Graham, Eds., Handbook of Combinatorial Optimization, 2nd ed.
New York: Springer-Verlag, 2013. [21] J. Williams and D. Thomas, Digital VLSI Design with Verilog: A Textbook from Silicon Valley
Technical Institute, 2008 edition. New York: Springer, 2008. [22] J. Nocedal and S. Wright, Numerical Optimization, 2nd ed. New York: Springer-Verlag, 2006. [23] Teofilo F. Gonzalez, Ed., Handbook of Approximation Algorithms and Metaheuristics, Second
Edition. Routledge Handbooks Online, 2018. [24] K. Kawarabayashi and Y. Kobayashi, The Induced Disjoint Paths Problem, in Integer Programming and Combinatorial Optimization, A. Lodi, A. Panconesi, and G. Rinaldi, Eds.
Springer Berlin Heidelberg, 2008, Pp. 47–61. [25] V. A. Yemelichev, M. M. Kovalev, M. K. Kravtsov, Polytopes, graphs and optimisation.
Cambridge University Press, Cambridge, 1984.