representations.There were no such efficient representations other than the constraint graphs until the SP [1]and the BSG [2]appeared in the mid-1990s.Subsequently,several efficient representations were proposed,such as the O-tree [9],the B'-tree [10],the corner block list (CBL)[11],the TCG [3],the TCG-S [4],the twin binary sequences(TBS)[12],the CS [5], and so on.However,most stochastic optimization algorithms using these representations were SA.Moreover,these representations were designed for rectangular blocks and cannot handle rectilinear blocks directly A.Stochastic Optimization Algorithms In the field of floorplanning,SA is much more popular than EAs.Several researchers used general SA to search solution spaces [1]-[5],[10]-[12].They perturbed the current floorplan according to properties of the employed representation and decreased the temperature according to a pre-defined cooling schedule.Additionally,on the basis of the SP, [13]proposed an orthogonal SA algorithm (OSA)with an efficient generation mechanism (EGM)for solving floorplanning problems.The EGM sampled a small number of representative floorplans and then efficiently derived a high-performance floorplan using a systematic reasoning method for the next move of the OSA,based on the orthogonal experimental design. In recent years,EAs have attracted increasing attention because they are suitable for solving complex and ill-defined problems.They have been successfully applied to the fields of numerical optimization [14],constraint satisfaction problems [15],data mining and knowledge discovery [16],[17],neural networks [18],and so on. There were also a few studies on the application of EAs to floorplanning problems. 6
6 representations. There were no such efficient representations other than the constraint graphs until the SP [1] and the BSG [2] appeared in the mid-1990s. Subsequently, several efficient representations were proposed, such as the O-tree [9], the B* -tree [10], the corner block list (CBL) [11], the TCG [3], the TCG-S [4], the twin binary sequences (TBS) [12], the CS [5], and so on. However, most stochastic optimization algorithms using these representations were SA. Moreover, these representations were designed for rectangular blocks and cannot handle rectilinear blocks directly. A. Stochastic Optimization Algorithms In the field of floorplanning, SA is much more popular than EAs. Several researchers used general SA to search solution spaces [1]-[5], [10]-[12]. They perturbed the current floorplan according to properties of the employed representation and decreased the temperature according to a pre-defined cooling schedule. Additionally, on the basis of the SP, [13] proposed an orthogonal SA algorithm (OSA) with an efficient generation mechanism (EGM) for solving floorplanning problems. The EGM sampled a small number of representative floorplans and then efficiently derived a high-performance floorplan using a systematic reasoning method for the next move of the OSA, based on the orthogonal experimental design. In recent years, EAs have attracted increasing attention because they are suitable for solving complex and ill-defined problems. They have been successfully applied to the fields of numerical optimization [14], constraint satisfaction problems [15], data mining and knowledge discovery [16], [17], neural networks [18], and so on. There were also a few studies on the application of EAs to floorplanning problems
Cohoon et al.in [19]offered the classical work on using genetic algorithms (GAs)for floorplanning.The arrangement of rooms on the layout surface was represented in the genotype by a postfix expression that was not normalized of the corresponding slicing tree. Schnecke et al.in [20]used a GA to manipulate the binary slicing tree directly for floorplanning.However,the crossover involved complex repair mechanisms simply to ensure that the offspring represented a legal slicing floorplan.Valenzuela et al.in [21]presented a GA that used a slicing tree construction process.They used an order-based representation that encoded rectangles and binary operations into a simple permutation of structures and a decoder that converted the permutation of structures into a normalized postfix expression. Generally speaking,applications of EAs to floorplanning problems are much fewer than those of SA.Although some researchers [19]-[21]used EAs,their works were all based on the slicing structure instead of the nonslicing structure.This restricted the popularization of these methods to some extent.In our opinion,the reason for fewer applications of EAs is that the nonslicing floorplan representations are generally very complex and solution spaces are constrained.In this case,EAs with traditional evolutionary operators (e.g.,crossover)tend to create infeasible individuals during the search.To boost the development of EAs in the field of floorplanning,it is important to design new nonslicing floorplan representations that do not exert extra constraints on solution spaces and facilitate effective crossover operators. B.Floorplanning Problems with Arbitrarily Shaped Rectilinear Blocks In the simplest situation of floorplanning,all blocks are rectangular.However,in real design,as some of the circuit blocks come from design re-use,they are not necessarily rectangular.To fully optimize some predefined cost metric,for example,area,wirelength,or
7 Cohoon et al. in [19] offered the classical work on using genetic algorithms (GAs) for floorplanning. The arrangement of rooms on the layout surface was represented in the genotype by a postfix expression that was not normalized of the corresponding slicing tree. Schnecke et al. in [20] used a GA to manipulate the binary slicing tree directly for floorplanning. However, the crossover involved complex repair mechanisms simply to ensure that the offspring represented a legal slicing floorplan. Valenzuela et al. in [21] presented a GA that used a slicing tree construction process. They used an order-based representation that encoded rectangles and binary operations into a simple permutation of structures and a decoder that converted the permutation of structures into a normalized postfix expression. Generally speaking, applications of EAs to floorplanning problems are much fewer than those of SA. Although some researchers [19]-[21] used EAs, their works were all based on the slicing structure instead of the nonslicing structure. This restricted the popularization of these methods to some extent. In our opinion, the reason for fewer applications of EAs is that the nonslicing floorplan representations are generally very complex and solution spaces are constrained. In this case, EAs with traditional evolutionary operators (e.g., crossover) tend to create infeasible individuals during the search. To boost the development of EAs in the field of floorplanning, it is important to design new nonslicing floorplan representations that do not exert extra constraints on solution spaces and facilitate effective crossover operators. B. Floorplanning Problems with Arbitrarily Shaped Rectilinear Blocks In the simplest situation of floorplanning, all blocks are rectangular. However, in real design, as some of the circuit blocks come from design re-use, they are not necessarily rectangular. To fully optimize some predefined cost metric, for example, area, wirelength, or
routability,it is important to deal with floorplanning problems with arbitrarily shaped rectilinear blocks.There are a few existing partition-based approaches that use the well-known representations. Xu et al.in [22]explored the conditions of the feasible SP for L-shaped blocks.Kang et al.in [23]derived three necessary and sufficient conditions for recovering the shapes of convex rectilinear blocks based on the SP.Fujiyoshi et al.in [24]derived a necessary and sufficient condition of the feasible SP for rectilinear blocks.Nakatake et al.in [25]handled pre-placed and rectilinear blocks using the BSG.Kang et al.in [26]used the BSG and the SP to solve the topology constrained block packing for ordered convex rectilinear blocks and extended the method to handle arbitrary rectilinear blocks.Pang et al.in [27]and Wu et al.in [28]used the O-tree and the B'-tree,respectively,to handle rectilinear blocks.Ma et al.in [29] used the CBL to deal with the placement abutment constraint and extended the method to deal with L-and T-shaped blocks.Lin et al.in [30]derived necessary and sufficient conditions of the feasible TCG for the sub-blocks.Additionally,Chu et al.in [31]dealt with the problem of giving a preliminary floorplan and changed the shapes and dimensions of some soft blocks to L-shaped to fill up the empty space. From the literature cited,we can see that most previous works on floorplanning problems with rectilinear blocks partitioned rectilinear blocks into a set of rectangular sub-blocks and operated on sub-blocks under some constraints induced from the original rectilinear blocks. However,as the original rectilinear blocks were partitioned,some additional operations became necessary to retrieve the original shapes after packing,resulting in a larger computational cost.Thus,it is necessary to design a representation that can handle rectilinear 8
8 routability, it is important to deal with floorplanning problems with arbitrarily shaped rectilinear blocks. There are a few existing partition-based approaches that use the well-known representations. Xu et al. in [22] explored the conditions of the feasible SP for L-shaped blocks. Kang et al. in [23] derived three necessary and sufficient conditions for recovering the shapes of convex rectilinear blocks based on the SP. Fujiyoshi et al. in [24] derived a necessary and sufficient condition of the feasible SP for rectilinear blocks. Nakatake et al. in [25] handled pre-placed and rectilinear blocks using the BSG. Kang et al. in [26] used the BSG and the SP to solve the topology constrained block packing for ordered convex rectilinear blocks and extended the method to handle arbitrary rectilinear blocks. Pang et al. in [27] and Wu et al. in [28] used the O-tree and the B* -tree, respectively, to handle rectilinear blocks. Ma et al. in [29] used the CBL to deal with the placement abutment constraint and extended the method to deal with L- and T-shaped blocks. Lin et al. in [30] derived necessary and sufficient conditions of the feasible TCG for the sub-blocks. Additionally, Chu et al. in [31] dealt with the problem of giving a preliminary floorplan and changed the shapes and dimensions of some soft blocks to L-shaped to fill up the empty space. From the literature cited, we can see that most previous works on floorplanning problems with rectilinear blocks partitioned rectilinear blocks into a set of rectangular sub-blocks and operated on sub-blocks under some constraints induced from the original rectilinear blocks. However, as the original rectilinear blocks were partitioned, some additional operations became necessary to retrieve the original shapes after packing, resulting in a larger computational cost. Thus, it is necessary to design a representation that can handle rectilinear
blocks directly C.Cutting and Packing Problems One might argue that the MBS is similar to the bottom-left(BL)and the bottom-left-fill (BLF)methods [32],[33]used in the field of cutting and packing.In the BL,each block starts from the top-right corner and slides as far as possible to the bottom,and then as far as possible to the left.These successive vertical and horizontal movements are repeated until blocks lock in a stable position.The BLF is a modified version of the BL and can fill the holes in placed rectangles. Although all the BL,the BLF,and the MBS move blocks on a region,the BL and the BLF have only one initial position,namely,the top-right location,whereas the MBS has four initial positions.Moreover,the MBS has four move rules corresponding to the four initial positions.To illustrate the usefulness of these extra choices for the initial positions and the move rules in the MBS,a group of experiments on the MBS with only one or two initial positions is carried out and the results are presented in Subsection VII.A. On the other hand,there is a major difference between cutting and packing problems and floorplanning.In the former,the width of the region is fixed and only the height needs to be minimized,whereas in the latter,there are no constraints on the regions,and the area needs to be minimized.Additionally,in the field of cutting and packing,problems are usually categorized into orthogonal problems (where blocks are rectangular)[34]and irregular problems [35].The emphasis of the MBS is to handle rectilinear blocks,which are more general than rectangular blocks,but are a special case of irregular blocks. EAs are also used in the field of cutting and packing.In 1985,Smith [36]first applied 9
9 blocks directly. C. Cutting and Packing Problems One might argue that the MBS is similar to the bottom-left (BL) and the bottom-left-fill (BLF) methods [32], [33] used in the field of cutting and packing. In the BL, each block starts from the top-right corner and slides as far as possible to the bottom, and then as far as possible to the left. These successive vertical and horizontal movements are repeated until blocks lock in a stable position. The BLF is a modified version of the BL and can fill the holes in placed rectangles. Although all the BL, the BLF, and the MBS move blocks on a region, the BL and the BLF have only one initial position, namely, the top-right location, whereas the MBS has four initial positions. Moreover, the MBS has four move rules corresponding to the four initial positions. To illustrate the usefulness of these extra choices for the initial positions and the move rules in the MBS, a group of experiments on the MBS with only one or two initial positions is carried out and the results are presented in Subsection VII.A. On the other hand, there is a major difference between cutting and packing problems and floorplanning. In the former, the width of the region is fixed and only the height needs to be minimized, whereas in the latter, there are no constraints on the regions, and the area needs to be minimized. Additionally, in the field of cutting and packing, problems are usually categorized into orthogonal problems (where blocks are rectangular) [34] and irregular problems [35]. The emphasis of the MBS is to handle rectilinear blocks, which are more general than rectangular blocks, but are a special case of irregular blocks. EAs are also used in the field of cutting and packing. In 1985, Smith [36] first applied
GAs to packing problems.At the same time,Davis [37]summarized the techniques for applications of GAs to epistatic domains using the example of two-dimensional (2D)bin packing.Since then,various packing problems,ranging from regular to arbitrary shapes in two or more dimensions,have been approached.In these approaches,individuals were represented as permutations of blocks.A placement heuristic was used to decode the representation by packing the pieces in the order given by the permutation.This approach remained popular for cutting and packing problems [38],[39].There were also several approaches by incorporating the bound information of the branches of search trees into GAs [40].Hopper and Turton [41]had reviewed applications of GAs to packing problems.They also conducted an empirical study of meta-heuristic and heuristic algorithms for 2D packing problems [42]. In the field of cutting and packing,because individuals are usually represented as permutations of blocks,the only task of EAs is to optimize the permutations.However,the MBS has two tuples,permutation and initial position.Thus,the task of the MBS-OEA is to optimize not only the permutation,but also the initial positions. III.Moving Block Sequence Representation The blocks in floorplanning can be classified into three types:hard rectangular blocks (HRaBs),soft rectangular blocks(SRaBs),and hard rectilinear blocks(HRiBs).Regardless of the type of blocks,the goal of floorplanning is to determine the shapes and locations of a set of blocks so that no block overlaps and to minimize some predefined cost metric induced by a floorplan.Each block is free to rotate. Given a floorplanning problem with n blocks,B=(Bo,B1,...,B1),let F(B)denote a 10
10 GAs to packing problems. At the same time, Davis [37] summarized the techniques for applications of GAs to epistatic domains using the example of two-dimensional (2D) bin packing. Since then, various packing problems, ranging from regular to arbitrary shapes in two or more dimensions, have been approached. In these approaches, individuals were represented as permutations of blocks. A placement heuristic was used to decode the representation by packing the pieces in the order given by the permutation. This approach remained popular for cutting and packing problems [38], [39]. There were also several approaches by incorporating the bound information of the branches of search trees into GAs [40]. Hopper and Turton [41] had reviewed applications of GAs to packing problems. They also conducted an empirical study of meta-heuristic and heuristic algorithms for 2D packing problems [42]. In the field of cutting and packing, because individuals are usually represented as permutations of blocks, the only task of EAs is to optimize the permutations. However, the MBS has two tuples, permutation and initial position. Thus, the task of the MBS-OEA is to optimize not only the permutation, but also the initial positions. III. Moving Block Sequence Representation The blocks in floorplanning can be classified into three types: hard rectangular blocks (HRaBs), soft rectangular blocks (SRaBs), and hard rectilinear blocks (HRiBs). Regardless of the type of blocks, the goal of floorplanning is to determine the shapes and locations of a set of blocks so that no block overlaps and to minimize some predefined cost metric induced by a floorplan. Each block is free to rotate. Given a floorplanning problem with n blocks, B={B0, B1, …, Bn-1}, let F(B) denote a