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.