Placement Problems

Pascal Francq

December 19, 2011 (June 20, 2001)


The placement problems are a class of optimization problems where the goal is to place a set of objects with different shapes. Each object has multiple terminals, each terminal may have several connectors. Several connections exist, each connection being defined by the set of terminals to connect.

1 Description

The placement problem is the task to place a set of objects with a given rectangular polygonal shape [A]  [A] A rectangle polygon is a polygon where each edge is parallel or perpendicular to all other edges. that are connected together through nets. Each object may have multiple orientations and has a number of terminals, each of them may have multiple positions on the object (called connectors). The objects are connected through nets which determine links between given connectors of given objects, a weight is associated with a connection to specify its importance with respect to the other ones. A set of constraints is also associated to the objects. To solve the problem, the position and the orientation of each object must be fixed and the connections configuration must be computed.
The rigorous definition of the problem begins with a set of objects to place:
Each object has a shape , a set of arrangements of possible orientations and a set of terminals:
All the terminals also included in the set :
where also include some fixed terminals not assigned to an object.
Each terminal has a set of possible connectors (positions) on the corresponding element:
The positions are relative to a given orientation of an element, i.e. an unique variable represents all the possible coordinates for the different orientations of the corresponding element.
A set of nets are given, where each net is defined by a weight and by a sub-set from of terminals:
The global layout has to fit in given size limits . A set of constraints between the elements exists also:
To problem is to fix a set of variables for the objects and the nets. Concerning the elements, the variables to be determined are the position and the orientation (the stands for variable):
For the nets, it is necessary to determine the configuration, i.e. the pairs of terminals and their connector which minimize the length of the corresponding net. This amounts to determine a set of pairs of terminal connectors (the stands for variable), each pair is defined by two terminals, and each terminal is defined by a given connector:
We suppose that all the positions and the sizes are integers. In practice, with a good scale choice, this condition can always be respected. The fact that integer values are used, i.a. that the positions and the sizes only take a finite set of distinct values, makes the 2D Problem a combinatorial optimization problem.

2 Objects

Objects have two parameters, the and coordinates, to be determined during the resolution process. Each object has a given shape, which is a rectangle polygon. The placement problem refers always to problems involving objects, which in the “real” world always are rectangular polygons or rectangles [B]  [B] It is very complicated to design and fabricate objects that may have general polygonal shape.. Furthermore, this type of shapes allows some crucial speed improvement in all the algorithms which makes them usable on real problems in comparison to general polygonal shapes.
Each object may have multiple orientations obtained by rotations and flips. The different possible orientations are showed at Figure 1↓. As explained, the number of the orientations allowed has to be fixed for all the objects to place.
Figure 1 Different orientations for an object.
The limitation to these orientations is justified by the fact that the union of a given set of rectangular polygons with one of these orientations is also a rectangular polygon (Figure 2↓a), which makes it easy to consider it as an object itself. In comparison, the union of two rectangular polygons where one of them was obtained by a rotation (Figure 2↓b) is not a rectangular polygon.
Figure 2 Union of rectangular and non-rectangular polygons.

3 Terminals

The terminals represent physical points inside an object, used to evaluate the length of a portion of a net. A terminal may have a real existence, like in the VLSI problem where it represents an electronic terminal, but it can also be imaginary.
A terminal can be localized in a single point or have different positions called connectors, as in the VLSI problem.
When the instance defines terminals, every object involved must have at least one terminal with one connector. By default, when an object defines no terminals, an imaginary one is created at a “central” position of the corresponding object. When the object is a rectangle, the “central” position is the mass point of the rectangle (Figure 3↓a), else the “central” position corresponds to the nearest vertex to the mass point of the bounding rectangle (Figure 3↓b).
Figure 3 Imaginary connectors.
Furthermore, terminals may also be fixed and representing links between the layout that have to be produced and “others layouts”. By example, for the VLSI problem, when the layout is representing a macro-cell with terminals needed for external connectivity (Figure 4↓).
Figure 4 Example of placement with fixed connectors

4 Nets

A net represents a connection between terminals of objects. A net can be a “cabling net” like in the VLSI problem with many objects associated, but it can also represents the fact that two objects have to be placed as near as possible.
When a net links more than two objects, it does not mean that all terminals involved have to be connected together directly. This means that there are different orientations possible for a single net. The Figure 5↓ shows the different configuration for a net between three objects. Of course, the number of possibilities increases when some terminals may have multiple connectors.
Figure 5 Different configurations for a net.
The “closeness” between two objects is not only given by their geometrical information, but also by length of the nets. It is thus necessary to evaluate the length of a given net, which means that a specific configuration for that net must be fixed. The length of the net is then the product of the weight of this net with the sum of the geometric distance between the different connectors of the terminals used.
To evaluate the geometric distance of two positions, the Manhattan distance is used. Figure 6↓ shows the Manhattan distance between two positions A and B, which is the length of the two lines.
Figure 6 Manhattan distance.
The problem with the nets is that a given net can have multiple configurations for the position of the terminals involved and the different parts that will be used. To solve this problem, it is necessary to briefly introduces some concepts from the graph theory. There are complete dedicated books to the graph theory [1, 2].

4.1 Graphs and Minimum Spanning Trees

A graph is a mathematical structure that describes a set of elements that are connected together. A graph is defined by two sets: a set of vertices , which represent the elements, and a set of edges , which represent the connections, and is noted
When removing edges and/or vertices from a given graph , a subgraph of is obtained. During the construction of a graph, when a vertex is removed, all the edges connected to it must also be removed.
Two vertices and are connected if there is an edge starting from vertex and finishing at vertex . If all pairs of vertices in a graph are connected, the graph is called a connected graph. When a direction is associated with the edges of the graph, the graph is called a directed graph, otherwise it is called an undirected graph.
A path is a sequence of alternating vertices and edges which starts and finishes with a vertex. The length of the path is the number of edges it contains. Note that a given graph can have a length of zero. When a path starts and finishes with the same vertex with a length greater than zero, it is called a cycle. A path or a cycle not containing two or more occurrences of the same vertex is called a simple path or cycle.
A tree is a connected graph without cycles. A spanning tree of a connected graph is a subgraph which is a tree and that contains all vertices of the corresponding graph. In the case of edge-weighted undirected graphs, there is a spanning tree with the least total edge weight, which is the minimum spanning tree. Figure 7↓ shows a graph and the corresponding minimum spanning tree.
Figure 7 An edge-weighted undirected graph (a) and its minimum spanning tree (b).
One of the algorithm proposed to solve the minimum spanning tree problem is described in [3]. The algorithm starts with an arbitrary vertex which is considered the initial tree. Besides it is assumed that a vertex has the attribute and . The first one is used to register the shortest distance from a vertex not yet in the tree to a vertex already selected. The second one represents the edge through which this shortest connection is made. In each iteration, the vertex with the minimal value is added to the tree together with the edge of its attribute. Then the values of the and attributes are updated for the vertices not yet in the tree. Of course, the algorithm stops when all vertices are in the tree.

4.2 Computing the Net Lengths

The problem of computing the net lengths can be considered as a minimum spanning tree problem. In fact, the different objects involved in the net are the vertices of the graph. The edges of the graph are the different possible parts of the net. The weight of a given edge is the minimum possible distance for the corresponding part.
Figure 8 Correspondence between a net and a graph.
An example of the correspondence is shown at Figure 8↑. Suppose we have three objects with a single terminal, each terminal has two possible positions. To construct the graph which corresponds to the net involving the terminals , and , we create a vertex for each terminal and an edge between all these vertices. The weight of a given edge, for example between the vertices et , is the minimum distance of all possible distances between the positions of these two terminals, in this example, it is the distance between the positions and .
Once the corresponding graph is constructed, the minimum spanning tree is searched. In the above example, if we suppose that the greatest distance is , the result is shown at Figure 9↓ (the distance used is the Manhattan distance).
Figure 9 Resulting minimum spanning tree.
The length of the net is then given by :
Sometimes, it is necessary to compute the partial length of a given net, i.a. the length of the net where only the already placed objects are considered. To compute this partial net, a subgraph is constructed with only the already placed objects, and the same method is then used.

5 Constraints

The placement problems introduce several constraints concerning the placement, but it is always possible to define them as a member of one of the three constraints classes, namely the “fixed constraints” class, the “maximum constraints” class and the “minimum constraints” class.
The “fixed constraints” constitute the first class, where a set of objects must be placed in fixed relative positions and orientations. A typical example of such a constraint in the VLSI problem is the amplificator, which is constructed by using two transistors, the relative positions and orientations of these transistors depends directly from the characteristics of the amplificator.
The “maximum constraints” are the second class, where a set of objects has to be place at a maximal distance of another set of objects. In the case of the VLSI problem, some nets are critical and cannot exceed some length, meaning that the objects involved have to be close.
The “minimum constraints” are the last class, where a set of objects has to be place at a minimal distance of another set of objects. Again to take the VLSI problem as example, objects that release heavy heat must be placed far from each other to balance the heat repartition of the resulting placement.

6 Algorithm evaluation

To evaluate the performance of an algorithm, it is necessary to have an “ideal” solution for a given instant and some measures to compare the “computed” solution provided by the algorithm with this “ideal” solution.
In fact, this is not a simple task since the quality of a solution relies on two criteria: the area occupied and the connection lengths. One algorithm can outperform the “ideal” solution with regard to one of the criteria by producing a bad solution regarding the second criteria. So, if it is possible to compare the value of both criteria for the “ideal” and the “computed” solution, the evaluation depends on the preferences of the particular instance of a given problem.

7 Related


[1] Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.

[2] James A. McHugh, Algorithmic Graph Theory, Prentice Hall International, 1990.

[3] Robert C. Prim, “Shortest Connection Networks and Some Generalizations”, Bell System Technical Journal, (36)6, pp. 1389—1401, 1957.