Moving Block Sequence and Organizational Evolutionary Algorithm for General Floorplanning with Arbitrarily Shaped Rectilinear Blocks Jing Liu',Member;IEEE Weicai Zhong',Member;IEEE Licheng Jiao,Senior Member,IEEE, Xue Li2,Member IEEE Institute of Intelligent Information Processing,Xidian University,Xi'an 710071,China 2School of Information Technology and Electrical Engineering,The University of Queensland,Brisbane, Qld 4072,Australia E-mail:neouma@163.com Abstract-A new nonslicing floorplan representation,the moving block sequence (MBS),is proposed in this paper.Our idea of the MBS originates from the observation that placing blocks on a chip has some similarities to playing the game,Tetris Because no extra constraints are exerted on solution spaces,the MBS is not only useful for evolutionary algorithms,but also for dealing with rectangular,convex rectilinear,and concave rectilinear blocks,similarly and simultaneously,without partitioning rectilinear blocks into sub-blocks.This is owed to a special structure designed for recording the information of both convex and concave rectilinear blocks in a uniform form.Theoretical analyses show that the computational cost of transforming an MBS to a floorplan with rectangular blocks,in terms of the number of blocks,is between linear and quadratic.Furthermore,as a follow-up of our previous works,a new organizational evolutionary algorithm (OEA)based on the MBS(MBS-OEA)is proposed.With the intrinsic properties of the MBS in mind,three new evolutionary operators are designed in the MBS-OEA. To test the performance of the MBS-OEA,benchmarks with hard rectangular,soft rectangular, and hard rectilinear blocks are used.The number of blocks in these benchmarks varies from 9 to
1 Moving Block Sequence and Organizational Evolutionary Algorithm for General Floorplanning with Arbitrarily Shaped Rectilinear Blocks Jing Liu1 , Member, IEEE Weicai Zhong1 , Member, IEEE Licheng Jiao1 , Senior Member, IEEE, Xue Li2 , Member IEEE 1 Institute of Intelligent Information Processing, Xidian University, Xi’an 710071, China 2 School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane, Qld 4072, Australia E-mail: neouma@163.com Abstract⎯A new nonslicing floorplan representation, the moving block sequence (MBS), is proposed in this paper. Our idea of the MBS originates from the observation that placing blocks on a chip has some similarities to playing the game, Tetris®. Because no extra constraints are exerted on solution spaces, the MBS is not only useful for evolutionary algorithms, but also for dealing with rectangular, convex rectilinear, and concave rectilinear blocks, similarly and simultaneously, without partitioning rectilinear blocks into sub-blocks. This is owed to a special structure designed for recording the information of both convex and concave rectilinear blocks in a uniform form. Theoretical analyses show that the computational cost of transforming an MBS to a floorplan with rectangular blocks, in terms of the number of blocks, is between linear and quadratic. Furthermore, as a follow-up of our previous works, a new organizational evolutionary algorithm (OEA) based on the MBS (MBS-OEA) is proposed. With the intrinsic properties of the MBS in mind, three new evolutionary operators are designed in the MBS-OEA. To test the performance of the MBS-OEA, benchmarks with hard rectangular, soft rectangular, and hard rectilinear blocks are used. The number of blocks in these benchmarks varies from 9 to
300.Also,the MBS-OEA and several well-designed existing algorithms are compared.The results show that the MBS-OEA can find high quality solutions for various problems. Additionally,the MBS-OEA shows a good performance in solving the problems with 300 hard rectangular blocks,100 soft rectangular blocks,and 100 hybrid blocks,including both soft rectangular and hard rectilinear blocks.This illustrates that the MBS-OEA is not only suitable for solving a wide range of problems,but also competent for solving large-scale problems. Finally,a set of specific experiments is designed to identify the key component that is mainly responsible for the good performance of the MBS-OEA. Index Terms-Very large scale integration,Floorplanning,Moving block sequence, Evolutionary algorithms,Organization
2 300. Also, the MBS-OEA and several well-designed existing algorithms are compared. The results show that the MBS-OEA can find high quality solutions for various problems. Additionally, the MBS-OEA shows a good performance in solving the problems with 300 hard rectangular blocks, 100 soft rectangular blocks, and 100 hybrid blocks, including both soft rectangular and hard rectilinear blocks. This illustrates that the MBS-OEA is not only suitable for solving a wide range of problems, but also competent for solving large-scale problems. Finally, a set of specific experiments is designed to identify the key component that is mainly responsible for the good performance of the MBS-OEA. Index Terms⎯Very large scale integration, Floorplanning, Moving block sequence, Evolutionary algorithms, Organization
I.Introduction Floorplanning is an essential step in the hierarchical physical design of deep sub-micron very large scale integration(VLSI)circuits.It involves planning the positions and shapes of a set of blocks on a chip to optimize circuit performances.Blocks must be placed without being overlapped.As the technology moves into the deep sub-micron era,circuit sizes and complexities are growing rapidly and floorplanning has become even more important than it was before.Although floorplanning has been studied extensively,most previous works used simulated annealing (SA)as the search algorithm and handled rectilinear blocks by partitioning them into a set of rectangular sub-blocks.Therefore,it is still challenging and practically useful to find a nonslicing floorplan representation that is not only suitable for evolutionary algorithms (EAs)because of their high potential,but can also handle both rectangular and rectilinear blocks,similarly and simultaneously,without partitioning rectilinear blocks into sub-blocks.This paper presents the moving block sequence(MBS)as a new nonslicing floorplan representation to meet the above requirements. Our idea of the MBS originates from the observation that placing blocks on a chip has some similarities to playing the game,Tetris As in Tetris we place blocks on a chip,one by one.Each block starts from an initial position and moves on the chip,until it reaches an appropriate position.In Tetris each block always appears on the top of the screen,and it is the players who find an appropriate position for each block during the descending process.In the MBS,on the other hand,four initial positions are designed from where the blocks could be moved to other places,according to the move rules. An MBS is designed to be composed of two tuples,one denoting the permutation of
3 I. Introduction Floorplanning is an essential step in the hierarchical physical design of deep sub-micron very large scale integration (VLSI) circuits. It involves planning the positions and shapes of a set of blocks on a chip to optimize circuit performances. Blocks must be placed without being overlapped. As the technology moves into the deep sub-micron era, circuit sizes and complexities are growing rapidly and floorplanning has become even more important than it was before. Although floorplanning has been studied extensively, most previous works used simulated annealing (SA) as the search algorithm and handled rectilinear blocks by partitioning them into a set of rectangular sub-blocks. Therefore, it is still challenging and practically useful to find a nonslicing floorplan representation that is not only suitable for evolutionary algorithms (EAs) because of their high potential, but can also handle both rectangular and rectilinear blocks, similarly and simultaneously, without partitioning rectilinear blocks into sub-blocks. This paper presents the moving block sequence (MBS) as a new nonslicing floorplan representation to meet the above requirements. Our idea of the MBS originates from the observation that placing blocks on a chip has some similarities to playing the game, Tetris®. As in Tetris®, we place blocks on a chip, one by one. Each block starts from an initial position and moves on the chip, until it reaches an appropriate position. In Tetris®, each block always appears on the top of the screen, and it is the players who find an appropriate position for each block during the descending process. In the MBS, on the other hand, four initial positions are designed from where the blocks could be moved to other places, according to the move rules. An MBS is designed to be composed of two tuples, one denoting the permutation of
block names and the other the initial positions of blocks.Each block is placed on the chip in the order it occurs in the permutation.There are four choices for the initial position and no extra constraints are exerted on the solution space.Hence,it is easy to design effective crossover operators for EAs on such a solution space.Owing to a special structure designed for recording the information of both convex and concave rectilinear blocks,the MBS can handle them in the same way as the rectangular blocks,namely,without partitioning them into sub-blocks.The MBS has a smaller solution space,(n22),than several existing representations,such as the sequence pair(SP)[1],the bounded-sliceline grid(BSG)[2],the transitive closure graph(TCG)[3],the TCG-S [4],the corner sequence(CS)[5],and so on. The solution space of each of the SP,the TCG,the TCG-S,and the CS is(n!)2,and that of the BSG is n!C(n2,n),where n is the number of blocks. From another viewpoint,the MBS can also be considered an extension of the bottom-left (BL)method,the most documented heuristic approach in the field of cutting and packing, because the BL has only one initial position.Other similarities and differences between the MBS and the BL are detailed in Subsection II.C. On the basis of the MBS,a new organizational evolutionary algorithm (OEA),the MBS-OEA,is proposed.OEAs are a new kind of EA proposed in our previous works,and have been successfully applied to classification problems [6],numerical optimization problems [7],and satisfiability problems [8].In this paper,three new operators,namely,the splitting operator,the annexing operator,and the training operator are designed on the basis of the MBS,so that the framework of the OEA is applicable to solving floorplanning problems. This paper is organized as follows.Section II discusses some related work.Section III
4 block names and the other the initial positions of blocks. Each block is placed on the chip in the order it occurs in the permutation. There are four choices for the initial position and no extra constraints are exerted on the solution space. Hence, it is easy to design effective crossover operators for EAs on such a solution space. Owing to a special structure designed for recording the information of both convex and concave rectilinear blocks, the MBS can handle them in the same way as the rectangular blocks, namely, without partitioning them into sub-blocks. The MBS has a smaller solution space, (n!22(n-1)), than several existing representations, such as the sequence pair (SP) [1], the bounded-sliceline grid (BSG) [2], the transitive closure graph (TCG) [3], the TCG-S [4], the corner sequence (CS) [5], and so on. The solution space of each of the SP, the TCG, the TCG-S, and the CS is (n!)2 , and that of the BSG is n!C(n 2 , n), where n is the number of blocks. From another viewpoint, the MBS can also be considered an extension of the bottom-left (BL) method, the most documented heuristic approach in the field of cutting and packing, because the BL has only one initial position. Other similarities and differences between the MBS and the BL are detailed in Subsection II.C. On the basis of the MBS, a new organizational evolutionary algorithm (OEA), the MBS-OEA, is proposed. OEAs are a new kind of EA proposed in our previous works, and have been successfully applied to classification problems [6], numerical optimization problems [7], and satisfiability problems [8]. In this paper, three new operators, namely, the splitting operator, the annexing operator, and the training operator are designed on the basis of the MBS, so that the framework of the OEA is applicable to solving floorplanning problems. This paper is organized as follows. Section II discusses some related work. Section III
gives the definition of the moving block sequence.Section IV presents the algorithm transforming an MBS to a floorplan.Section V introduces the MBS-OEA in detail. Experiments are given in Section VI.Section VII provides an experimental study that aims to identify the mechanism that is mainly responsible for the effectiveness of the MBS-OEA. Finally,some conclusions and future work are provided in Section VIII. IⅡ.Related Work Many researchers proposed various algorithms for floorplanning problems by applying different mathematical tools.Among these,stochastic optimization algorithms were the most popular and had attracted increasing attention.These algorithms employed methods of perturbing floorplans and searching for better solutions.As this kind of method can design specific operations based on the characteristics and complexities of problems,the quality of solutions was generally high.To optimize floorplans by stochastic optimization algorithms, the representation is one of the key and fundamental issues. The representation has been studied extensively.In general,there are two kinds of floorplans,slicing and nonslicing.A slicing floorplan can be obtained by recursively cutting rectangles horizontally or vertically into smaller rectangles;otherwise,it is a nonslicing floorplan.Slicing floorplan representations have smaller solution spaces and can describe any slicing structure with no redundancy.But in practical applications,most designs belong to nonslicing floorplans. Therefore,nonslicing floorplan representations have recently attracted much attention. Although this kind of representation is of more general utility and can utilize the area more effectively and achieve better routability,it is more complex and difficult to embody such
5 gives the definition of the moving block sequence. Section IV presents the algorithm transforming an MBS to a floorplan. Section V introduces the MBS-OEA in detail. Experiments are given in Section VI. Section VII provides an experimental study that aims to identify the mechanism that is mainly responsible for the effectiveness of the MBS-OEA. Finally, some conclusions and future work are provided in Section VIII. II. Related Work Many researchers proposed various algorithms for floorplanning problems by applying different mathematical tools. Among these, stochastic optimization algorithms were the most popular and had attracted increasing attention. These algorithms employed methods of perturbing floorplans and searching for better solutions. As this kind of method can design specific operations based on the characteristics and complexities of problems, the quality of solutions was generally high. To optimize floorplans by stochastic optimization algorithms, the representation is one of the key and fundamental issues. The representation has been studied extensively. In general, there are two kinds of floorplans, slicing and nonslicing. A slicing floorplan can be obtained by recursively cutting rectangles horizontally or vertically into smaller rectangles; otherwise, it is a nonslicing floorplan. Slicing floorplan representations have smaller solution spaces and can describe any slicing structure with no redundancy. But in practical applications, most designs belong to nonslicing floorplans. Therefore, nonslicing floorplan representations have recently attracted much attention. Although this kind of representation is of more general utility and can utilize the area more effectively and achieve better routability, it is more complex and difficult to embody such