SSL(Single Sequence Layout):A New Representation for Fixed-Outline Floorplanning

Floorplanning is a critical step in realizing the physical structure of circuits, directly impacting the performance, size, yield, and reliability of Very Large Scale Integration (VLSI) circuits. Experience shows that fixed-outline problems are more complex, and fixed-outline requirements have become essential in modern layout design. However, VLSI layout planning is an NP-hard problem, necessitating more efficient and concise methods to address it. This paper improves upon the traditional complex representation mechanism based on sequence pairs by proposing a more efficient Single Sequence Layout (SSL) representation. Compared to the original dual-sequence approach, SSL simplifies the data structure, making sequence operations more convenient and efficient. Additionally, SSL demonstrates advantages over dual-sequence representations when integrated with other optimization algorithms. For solving strategies, this paper introduces a meticulously designed improved genetic algorithm, which includes a modified mutation method tailored for the single-sequence and a novel crossover operation that preserves parental characteristics. The proposed method was tested on two sets of circuits, MCNC and GSRC, and compared with methods in existing literature. Experimental results indicate that using SSL combined with the redesigned genetic algorithm achieves a certain improvement in layout success rates. With a dead space rate of 15%, the layout success rate can reach 100%, verifying the feasibility of the SSL algorithm.