Irregular Module Layout Algorithm for Integrated Circuits Based on SS Sequence

The SS sequence (Single-Sequence) is a sequence of non-repeating natural numbers. The SS decoding rule in reference [1] decodes the SS sequence as the corresponding unit distribution map, and uses the simulated annealing algorithm [2] to randomly change the module placement order, rotation degree and SS sequence in the unit with a certain probability. The horizontal/vertical constraint map of each unit module is obtained through the SS decoding rule, and the area of ​​the final chip is calculated using the critical path algorithm [3]. However, so far, SS has only solved the layout problem of rectangular hard modules, and there is no good solution for the layout of non-rectangular modules or irregular modules. With the rapid development of integrated circuit technology, modules will not be limited to appearing in rectangular form, but may appear more flexibly in a variety of shapes on the integrated circuit layout. However, if they are still processed in a rectangular mode, it will inevitably lead to low utilization of chip area and a lot of idle space. Therefore, it is of great significance to find a simple and easy method to solve the problem of irregular module placement.

1. Module Division

The preliminary processing of irregular modules is to divide them into many small rectangles, thus avoiding the waste of area caused by the traditional algorithm that considers the entire irregular module as one large rectangle. As shown in Figure 1, it is formed by merging two rectangles. The traditional segmentation method regards it as a whole rectangle, and then uses the SS sequence algorithm to put it into the layout, as shown in Figure 1(a), resulting in a waste of bottom area. The SS sequence cannot distinguish the blank area of ​​the module, but regards it as a whole and puts it into the layout, resulting in the lower blank area can never be occupied by other modules, resulting in a large waste. As the module area increases and the number of irregular modules increases, the area waste phenomenon will become more serious. Therefore, the module should be divided before inputting the module data. For the convenience of program calculation, it is stipulated that the module is divided from top to bottom and based on the left side. As shown in Figure 1(b), the irregular module is divided into two small rectangles A and B for input data. In the SS algorithm processing process, it is regarded as two different modules connected together. The regional module connection algorithm is used to keep it tightly connected during the transformation process, so that the lower free area can be fully utilized. For irregular modules with arcs, a rectangle should be drawn with the tangent line of the arc as the starting point to enclose it, as shown in the module in Figure 1(c). First, take the leftmost side of the whole module as the reference, that is, the starting point, and draw a rectangle with the top point of the upper arc as the end point and the top point of the upper arc as the top side, dividing the irregular module into two rectangles. The same division is done for more complex irregular modules.

2 Module Region Connection Algorithm

After the modules are divided, there are many small modules that need to be connected together. At this time, a new sequence must be established to reflect the relationship between these modules. As shown in Figure 2, the SS layout algorithm [4] changes the arrangement order of the SS sequence and the module data sequence respectively, and puts the module data sequence into the unit map generated by the SS sequence one by one, so that the layout changes continuously. Therefore, after adding the module area connection sequence, the connected modules should be placed in the unit generated by the SS sequence before changing the module data sequence. The algorithm rules are as follows:

(1) The divided small rectangles are numbered according to the input sequence, and the small rectangles of the same irregular module are grouped together. Different groups are separated by 0, thereby generating a module area connection sequence that reflects the interconnection relationship between modules.

(2) After the SS sequence is transformed, since the modules are divided from top to bottom, it is necessary to find the unit numbers in the SS unit diagram that are connected up and down and put them into the irregular module first. First, randomly select an SS sequence number A and find the unit number B that is adjacent to the unit below and closest to A in horizontal position, that is, the SS sequence number that satisfies the formula Mbl(A)-1=Mas(B) and Min(|Mbs(A)-Mbs(B)|).

(3) Place the corresponding module (divided small rectangle) in the module area connection sequence into the unit found by rule (2).

(4) According to the module area connection sequence, the module data sequence corresponding to the unit number obtained by rule (2) is exchanged.

(5) Generate a layout.

3 Flipping Algorithm for Irregular Modules

In the SS decoding algorithm, the module needs to be flipped to obtain a better placement. Since the irregular module is divided into many small rectangles, the length and width order of the rectangles cannot be simply changed when flipping, but the overall flipping should be combined with the module area connection sequence. Unlike simple rectangular modules, which only have two states of 0° and 90°, irregular modules are much more complicated, including four flip states of 0°, 90°, 180° and 270°, as shown in Figure 3.

3.1 180° flip algorithm

The 180° flip is relatively simple. As can be seen from Figure 3, the 180° flip only changes the up-and-down position relationship of the divided small rectangles based on the original state, and does not change the length and width data of these small rectangles. Therefore, it is only necessary to change the order of the corresponding groups in the module area connection sequence. Suppose the module area connection sequence is: XXXX0ABCD0XXX0XXX0XXX. To flip the module composed of the rectangle group ABCD by 180°, it is only necessary to change the sequence to XXXX0DCBA0XXX0XXX0XXX, as shown in Figure 4.

3.2 90° flip algorithm

The 90° flip is more complicated, as it not only involves the module area connection sequence, but also changes the length and width data of the small rectangle, which also changes the module data sequence. First, the modules need to be re-divided:

(1) Find the module with the shortest length in the original module data sequence, add its width to the width of all the modules in the reorganization, and use it as a new small rectangle.

(2) Find the second smallest module in the original module data sequence, and use its length minus the length of the rectangle in (1) as its new length. Its width is changed to the original width plus the width of all modules in the reorganization minus the width of the module with the smallest length in (1).

(3) Repeat the above steps until all rectangles are processed.

(4) Swap the length and width data in the modified module data sequence.

(5) Modify the module area connection sequence to make it correspond to the current module data sequence.

The module is flipped 90° as shown in FIG5 .

3.3 270° flip algorithm

270° is equivalent to flipping 180° again based on the 90° flip, so you only need to use the algorithm in Section 3.1 based on Section 3.2 to flip.

This paper improves the SS sequence algorithm, so that the original algorithm can layout some complex irregular modules on the basis of only being able to layout simple rectangular modules, which greatly increases the practical ability of the SS algorithm and its ability to handle complex modules, laying the foundation for the flexibility of integrated circuit layout in the future. This paper proposes a new concept of module division, and proposes new algorithms and concepts such as module area connection algorithm, irregular module flip algorithm, and module area connection sequence. It enriches the SS sequence algorithm, increases the function of the SS sequence algorithm, and greatly improves the practicality of the SS algorithm and its ability to handle complex situations.