We present a novel incremental algorithm for non-slicing floorplans based on the corner block list representation. The horizontal and vertical adjacency graphs are derived from the packing of the initial floorplanning...We present a novel incremental algorithm for non-slicing floorplans based on the corner block list representation. The horizontal and vertical adjacency graphs are derived from the packing of the initial floorplanning results. Based on the critical path and the accumulated slack distances we define,we choose the best position for insertion and do a series of operations incrementally, such as deleting modules, adding modules, and resizing modules quickly. This incremental floorplanning algorithm has a very high speed less than 1μm,which is one of the most important measures in this research. The algorithm preserves the original good performances on area and wire length. It can also supply other tools with good physical estimates for area, wire length, and other performance guidelines.展开更多
The coefficients of friction and squeezing of the key blocks comer in the roof structure of underground coalface are key factors to roof structure stability quantitative analysis. In this paper, through the special t...The coefficients of friction and squeezing of the key blocks comer in the roof structure of underground coalface are key factors to roof structure stability quantitative analysis. In this paper, through the special test of three-type corner friction and squeez- ing of real rock specimens, and physical simulation test on the roof key blocks of roof structure as well as the finite element calcula- tion of the corner stress distribution and failure mechanism, the characteristics of friction and squeezing of the roof key blocks comer are revealed. It is found that the friction angle of the roof key blocks corner is the residual friction angle, and the frictional angle of the roof key blocks is 22-32° (average 27°), so the friction coefficient is determined as 0.5. It also found the squeezing strength is less than the uniaxial strength, and the squeezing coefficient of the roof blocks corner is determined as 0.4. Based on the results, the ground control theory can be updated from qualitative analysis to quantitative analysis.展开更多
Floorplanning is a critical phase in physical design of VLSI circuits. The stochastic optimization method is widely used to handle this NP-hard problem. The key to the floorplanning algorithm based on stochastic optim...Floorplanning is a critical phase in physical design of VLSI circuits. The stochastic optimization method is widely used to handle this NP-hard problem. The key to the floorplanning algorithm based on stochastic optimization is to encode the floorplan structure properly. In this paper, corner block list (CBL)-a new efficient topological representation for non-slicing floorplan-is proposed with applications to VLSI floorplan. Given a corner block list, it takes only linear time to construct the floorplan. In floorplanning of typical VLSI design, some blocks are required to satisfy some constraints in the final packing. Boundary constraint is one kind of those constraints to pack some blocks along the pre-specified boundaries of the final chip so that the blocks are easier to be connected to certain I/O pads. We implement the boundary constraint algorithm for general floorplan by extending CBL. Our contribution is to find the necessary and sufficient characterization of the blocks along the boundary represented by CBL. We can check the boundary constraints by scanning the intermediate solutions in linear time during the simulated annealing process and fix the corner block list in case the constraints are violated. The experiment results are demonstrated by several examples of MCNC benchmarks and the performance is remarkable.展开更多
With the recent advent of deep submicron technology and new packing schemes, the components in the integrated circuit are often not rectangular. On the basis of the representation of Corner Block List （CBL）, we prop...With the recent advent of deep submicron technology and new packing schemes, the components in the integrated circuit are often not rectangular. On the basis of the representation of Corner Block List （CBL）, we propose a new method of handling rectilinear blocks. In this paper, the handling of the rectilinear blocks is simplified by transforming the L/T- shaped block problem into the Mign-abutment constraint problem. We devise the block rejoining process and block alignment operation for forming the L/T-shaped blocks into their original configurations. The shape flexibility of the soft blocks, and the rotation and reflection of L/T-shaped blocks are exploited to obtain a tight packing. The empty rooms are introduced to the process of block rejoining. The efficiency and effectiveness of the proposed method are demonstrated by the experimental results on a set of some benchmark examples.展开更多
This paper studies the buffer planning problem for interconnect-centric floorplanning for nanometer technologies. The dead-spaces are the spaces left unused within a placement that are not held by any circuit block. I...This paper studies the buffer planning problem for interconnect-centric floorplanning for nanometer technologies. The dead-spaces are the spaces left unused within a placement that are not held by any circuit block. In this paper, we proposed a buffer planning algorithm based on dead space redistribution to make good use of dead-spaces for buffer insertion. Associated with circuit blocks under topological representations, the dead space can be redistributed by moving freely some circuit blocks within their rooms in the placement. The total area and the topology of the placement keep unchanged while doing the dead space redistribution. The number of nets satisfying the delay constraint can be increased by redistributing the dead space all over the placement, which has been demonstrated by the experimental results. The increment of the number of nets that meet delay constraint is 9% on an average.展开更多
文摘We present a novel incremental algorithm for non-slicing floorplans based on the corner block list representation. The horizontal and vertical adjacency graphs are derived from the packing of the initial floorplanning results. Based on the critical path and the accumulated slack distances we define,we choose the best position for insertion and do a series of operations incrementally, such as deleting modules, adding modules, and resizing modules quickly. This incremental floorplanning algorithm has a very high speed less than 1μm,which is one of the most important measures in this research. The algorithm preserves the original good performances on area and wire length. It can also supply other tools with good physical estimates for area, wire length, and other performance guidelines.
基金This research was financially supported by the National Natural Science Foundation of China (No.50104009) and the Key Scienceand Technology Research Subject of the Ministry of Education of China (No.204183).
文摘The coefficients of friction and squeezing of the key blocks comer in the roof structure of underground coalface are key factors to roof structure stability quantitative analysis. In this paper, through the special test of three-type corner friction and squeez- ing of real rock specimens, and physical simulation test on the roof key blocks of roof structure as well as the finite element calcula- tion of the corner stress distribution and failure mechanism, the characteristics of friction and squeezing of the roof key blocks comer are revealed. It is found that the friction angle of the roof key blocks corner is the residual friction angle, and the frictional angle of the roof key blocks is 22-32° (average 27°), so the friction coefficient is determined as 0.5. It also found the squeezing strength is less than the uniaxial strength, and the squeezing coefficient of the roof blocks corner is determined as 0.4. Based on the results, the ground control theory can be updated from qualitative analysis to quantitative analysis.
文摘Floorplanning is a critical phase in physical design of VLSI circuits. The stochastic optimization method is widely used to handle this NP-hard problem. The key to the floorplanning algorithm based on stochastic optimization is to encode the floorplan structure properly. In this paper, corner block list (CBL)-a new efficient topological representation for non-slicing floorplan-is proposed with applications to VLSI floorplan. Given a corner block list, it takes only linear time to construct the floorplan. In floorplanning of typical VLSI design, some blocks are required to satisfy some constraints in the final packing. Boundary constraint is one kind of those constraints to pack some blocks along the pre-specified boundaries of the final chip so that the blocks are easier to be connected to certain I/O pads. We implement the boundary constraint algorithm for general floorplan by extending CBL. Our contribution is to find the necessary and sufficient characterization of the blocks along the boundary represented by CBL. We can check the boundary constraints by scanning the intermediate solutions in linear time during the simulated annealing process and fix the corner block list in case the constraints are violated. The experiment results are demonstrated by several examples of MCNC benchmarks and the performance is remarkable.
基金This work is supported by the National Natural Science Foundation of China （Grant Nos. 60473126 and 90407005）, National Natural Science Foundation of China and Hong Kong RGC Joint Project （Grant No. 60218004） and the Hi-Tech Research ＆ Development 863 Program of China （Grant Nos. 2004AA1Z1050 and 2002AA1Z1460）.
文摘With the recent advent of deep submicron technology and new packing schemes, the components in the integrated circuit are often not rectangular. On the basis of the representation of Corner Block List （CBL）, we propose a new method of handling rectilinear blocks. In this paper, the handling of the rectilinear blocks is simplified by transforming the L/T- shaped block problem into the Mign-abutment constraint problem. We devise the block rejoining process and block alignment operation for forming the L/T-shaped blocks into their original configurations. The shape flexibility of the soft blocks, and the rotation and reflection of L/T-shaped blocks are exploited to obtain a tight packing. The empty rooms are introduced to the process of block rejoining. The efficiency and effectiveness of the proposed method are demonstrated by the experimental results on a set of some benchmark examples.
文摘This paper studies the buffer planning problem for interconnect-centric floorplanning for nanometer technologies. The dead-spaces are the spaces left unused within a placement that are not held by any circuit block. In this paper, we proposed a buffer planning algorithm based on dead space redistribution to make good use of dead-spaces for buffer insertion. Associated with circuit blocks under topological representations, the dead space can be redistributed by moving freely some circuit blocks within their rooms in the placement. The total area and the topology of the placement keep unchanged while doing the dead space redistribution. The number of nets satisfying the delay constraint can be increased by redistributing the dead space all over the placement, which has been demonstrated by the experimental results. The increment of the number of nets that meet delay constraint is 9% on an average.
