This work is dedicated to the mathematical modelling of routing problems in VLSI design in the form of combinatorial, Euclidean combinatorial and nonlinear continuous optimization problems. The offered Euclidean models are tested on randomly generated samples by nonlinear IPOPT and APOPT optimization solvers implemented in Python.
The process of manufacturing a computer chip includes several stages, each of which is associated with some constraints such as economic, realizability, performance, power, signal integrity, reliability, and yield ones [1], [2], [3], [4]- [6], [7]. Solving placement, routing, timing, and many other problems are associated with the stages [6]. For instance, placement and routing problems, where placing modules on a chip is implemented, and a task of routing by connecting these modules into certain networks are considered, arise in economic, realizability, performance, reliability, and yield steps of VLSI design [6], [8], [9], [10].
This paper attacks the actual problem of routing in chip design. Normally, problems of this class are formulated as combinatorial optimization ones aiming to minimize the total length of routes between connected modules. In this case, combinatoriality arises from the natural constraints that the route cannot be arbitrarily laid on the chip, passing along some discrete grid plotted on it [2], [3], [6], [11][12][13].
In turn, combinatorial optimization problems exist in two fundamentally different formulationscombinatorial and Euclidean combinatorial [14][15][16][17]. In the first case (further combinatorial statements), the problem is formulated as an optimization problem over a combinatorial set, such as a set of permutations, partial permutations, or combinations [14], [17], [18]. In the late case (further Euclidean combinatorial statements), the problem is formulated as a discrete optimization problem, that is, an optimization program over a set of vectors in Euclidean space [15], [16].
Depending on the formulation chosen, the methods for solving routing problems differ significantly [4]. These are various approximate and heuristic methods utilizing combinatorial statements, including evolutionary and genetic algorithms [17], [20], [21], which provide a good solution in a reasonable time but does not guarantee its optimality [20].
When a Euclidean combinatorial statement is utilized, it becomes possible to accurately solve routing problems by discrete optimization methods, such as branch-and-bound and the cutting plane techniques [15], [18]. VLSI design is an expensive process that deserves appending time and other machine resources to obtain an accurate solution. That is why the second group of methods is gaining more and more attention [18]. In this regard, there is also a need in developing new approaches to expanding the class of real-world problems for which Euclidean combinatorial statements are known. Among them is the theory of Euclidean combinatorial configurations [6], [15], [22][23][24]. There exist combinatorial and continuous Euclidean formulations of real problems. The latter formulate the optimization problem as a classical optimization problem with an objective function and analytic constraints. In this statement, methods of continuous nonlinear, sometimes even convex, programming can be applied to solve the problems under consideration [14], [25].
The theory of continuous functional representations (f-representations) of combinatorial sets is a new direction in Euclidean combinatorial optimization intended to construct analytic representations of combinatorial sets embedded in Euclidean space [16], [24]. This research area makes it possible to formulate combinatorial optimization problems, i.e., routing ones, as continuous programs, thus opening a possibility to solve them using previously inaccessible tools on nonlinear continuous optimization [14], [25]. This work is dedicated to the mathematical modelling of routing problems in the three indicated formulationscombinatorial, Euclidean combinatorial and Euclidean continuous, and verifying their validity and comparative analysis of the last two by nonlinear optimization tools implemented in Python.
We solve the following routing problem arising in chip design [4][5][6], [22]. There is a chip of length n and width m , where n , m are natural numbers. The chip contains modules forming a set of M including modules A and B . It is required to construct the shortest path between A and B , satisfying the following constraints:
• the path begins and ends at the metal wires' connection points of the modules A and B , while the metal wires' connection points of all the modules are placed at the nodes of the integer lattice:
• the path can pass only through nodes of the integer lattice;
• the path is formed from vertical and horizontal segments;
• the path does not cross the modules
Let us construct a mathematical model of the problem (further referred to as Model 1).
In order to define the path, it is sufficient to set its beginning ( )
where A P is a set of coordinates of the metal wires' connection points of A , as well as ternary vectors:
x, y : x = x ; y = y ;
x , y B = 0, 1,1 ,i J ;
k is the maximum route length between A and B .
In addition, for the route end, it should be:
x , y P P,
where B P is a set of the metal wires' connection points of B Points that form the path AB on the plane are
x , y = x x , y y = x x , y y ;
x , y = x x x , y y y ;
x , y = x x ... x , y y ... y .
On the whole, ( )
Condition 3) is represented as follows:
which in conjunction with (2) will guarantee movement toward B only in the vertical and horizontal directions.
Condition 4) now can be represented as ( )
where ( ) ii x , y satisfy the condition (4), where M AB P is the set of coordinates of points through which the path can be constructed. As a result, we obtain a combinatorial formulation of the problem in the form: find a set of points ( ) ( )
such that ( )
x y min +→ (8) subject to constraints (1)-( 3), ( 5), ( 6), (8),
where ( )
x , y is determined by the formula (6).
The objective function (8) expresses the route length, and our goal is to minimize it.
Note that taking into account (2), the condition (5) can be replaced by linear inequality:
As a result, a new mathematical model (further referred to as Model 1') of the following form is formed: find the set (7) that is a solution to the optimization problem (8) under the constraints (1)-( 3), ( 6)- (9).
From this combinatorial formulation, let us move to the construction of its Euclidean combinatorial formulation allowing its solution by means of partial integer nonlinear programming [25], [26][27][28].
We start with an analytic formalization of the condition (1) and represent it as follows:
The expression in parentheses is (11) is satisfied, then (1) holds and vice versa. Condition (3) can be represented analytically in a similar way:
Finally, the expression ( 6) is rewritten as follows:
As a result, we get a mathematical model of our problem of the form ( 2), ( 4)-( 9), ( 11)-( 13) (further referred to as Model 2). Similarly to Model 1', Model 2' is formed from Model 2 by replacing condition (5) with the inequality (10), that is the problem (2), ( 4),( 6)-(13). Models 2, 2.1 are, in fact, polynomial partial integer programming problems, to which the corresponding nonlinear optimization methods are applicable, [14], [24], [25], [28], [29].
Finally, these models can be easily transferred into a continuous nonlinear optimization problem by replacing condition (2) with the following expressions:
which simplification results in:
Model 3this will be a problem ( 4)-( 9), ( 11)-( 14), Model 3'this will be a problem ( 4), ( 6)-( 14).
Let us generalize the designed mathematical models to the case if the modules A and B as well as other pairs of modules need pairwise interconnection, while our task is to find the shortest total path connecting the modules. In this case, in addition to the above Constraints 1-4, the condition of nonintersection of the connection paths (further referred to as Condition 5) need to be added.
We add an index L lJ to the model to reflect the order number of a pair of connected modules.
As a result, we have a generalization of Model 1 (further referred to as Model 1.1).
A ,B be pairs of connected modules,
•
where
Here, l D expresses the set of way-nodes between l A and l B , excluding its starting and ending points.
Let us proceed to the formation of a generalization of Model 2 to the case of connecting several modules. It is required to find a set (15), such that the minimum function ( 16) is attained and the constraints (19), (20) hold,
)
)
Here, the condition ( 29) is an analytic expression of the constraints (22), while ( 26)-( 28) are a direct generalization of conditions ( 11)- (13).
Finally, replacing condition (19) with the following expression, ( ) ( )
we get Model 3.1 as a generalization of Model 3.
Like ( 5), (10), the linear analogue of ( 10) is the condition:
Taking into account (10), the condition (29) can be replaced by a linear constraint:
as a result, we get another version of the model (further referred to as Model 3.1').
Remark 1 In the constructed models, the number k expresses the upper bound on the path length between two connected modules. For reducing the dimension of the problem, it is advisable to conduct a preliminary study to estimate the value of k for specific pairs of modules and replace k with the corresponding found values l kk , L lJ for the pairs.
Remark 2 In the constructed models, it is easy to find the lower bound for the value of the objective function using the distance in the space L . Thus, the objective function ( 8) can be estimated as follows:
Models 2.1, 3.1, 2.1', 3.1' were implemented in the Python software environment, using the nonlinear optimization package GEKKO [30], all models were tested using the APOPT nonlinear partial integer programming solver (Advanced Process OPTimizer) [31], while Models 2.1', 3.1', were also were solved using the IPOPT nonlinear partial integer programming solver (Interior Point OPTimizer) [23]. On average, IPOPT showed a certain advantage over the results of APOPT on randomly generated problems of dimension 10 m,n,L J , where the area under the modules is 60 %- 80 %. x , y = ( 1,1 , 1,2 , 1,3 , 2,3 , 3,3 , 3,4 , 4,4 , 4,4 , 4,4 ).
According to (33), the objective function reaches its lower bound, respectively, I is the optimal solution to the problem.
New routing models of practical problems of VLSI design are offered constructed by means of theories of Euclidean combinatorial configurations and f-representations of combinatorial sets mapped into Euclidean space. The models are validated by IPOPT and APOPT solvers, and an illustrative example is given.