A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. We call a floorplan room-to-room when adjacencies between rooms are considered. Fujimaki and Takahashi showed that any room-to-room floorplan can be represented as a permutation. In this paper, we give an O(n)-time algorithm that constructs the vertical and the horizontal constraint graphs of a floorplan for a given permutation under this representation.

A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. Heuristic search algorithms are used to find desired floorplans in applications, including sheet-cutting, scheduling, and VLSI layout design. Representation of floorplan is critical in floorplan algorithms, because it determines the solution space searched by floorplan algorithms. In this paper, we show a surjective mapping from permutations to room-to-room floorplans. This mapping gives us a simple representation of room-to-room floorplans.

In the floorplan design of System-on-Chip (SOC), Buffer Site Approach (BSA) has been used to relax the buffer congestion problem. However, for a floorplan with dominant wide bus, BSA may instead worsen the congestion. Our proposed Enhanced Buffer Site Approach (EBSA) extends existing BSA in a way that buffers of dominant wide bus can be distributed more evenly while reserving the same fast operation speed as BSA does. Experiments have been performed to integrate our model into an iterative floorplanning algorithm, and the results reveal that buffer congestion in a floorplan with dominant wide bus can be much abated.

In the VLSI layout design, a floorplan is often obtained to define rough arrangement of modules in the early design stage. In the stage, the aspect ratio of each soft module is also determined. The aspect ratio can be changed in the designated range keeping its area of each module. In this paper, in order to determine the aspect ratio, we propose a graph-based one dimensional compaction method which determines the aspect ratio quickly under the constraint that topology of a floorplan must not be changed. The proposed method is divided into two steps: (1) Selection of a minimal set of soft modules to adjust the aspect ratio. (2) Decision on the aspect ratio. (1) is formulated as the minimal cut problem in graph theory. We solve the problem by transforming it to the shortest path problem. (2) is divided into two operations. One is to determine the increment limit in height or width of each soft module and the other is to determine the aspect ratio of each soft module by Newton-Raphson method. The experimental comparisons show effectiveness of the proposed method.

This paper discusses how to minimize the number of dissection lines regarded as wiring channels on a floorplan corresponding to a placement of n modules. In a floorplan (rectangular dissection), the number of dissection lines exceeds the number of rooms exactly by three. Since a floorplan obtained from a given module placement may have many empty rooms where no module is assigned, redundant wiring channels and wire bends may also be generated. Hence, in order to reduce redundant channels and wire bends, removal of empty rooms is required. For this purpose, we formulate a problem of obtaining a floorplan with the minimum possible empty rooms based on a given module placement. Then, we propose a method of removing as many redundant empty rooms as possible by merging dissection lines on a floorplan in O(n) time. The number of empty rooms in the resultant floorplan is reduced to n- or less.

The success in topdown design of recent huge system LSIs is in a seamless transfer of the information resulted from the high level design to the lower level of floorplanning. For the purpose, we introduce a new concept abstract floorplan which is included in the output of high level design. From the abstract floorplan, the pillar blocks are derived which are critical sets of blocks that are expected to determine the width and height of the chip, named the frame. Since the frame and pillar blocks are obtained in the high level stage, they are useful to keep the consistency in the low level physical design if we apply optimization regarding them as constraints. Experiments to MCNC benchmarks showed that abstract floorplanning by pillar blocks output a placement faithful to the one physically optimized block placement with respect to the chip area and the wire-length.

A floorplan specifies the layout of modules in very large scale integration (VLSI) design, and a new code, called the EQ-sequence, for representing a floorplan is presented in this paper. The EQ-sequence is based on a Q-sequence. The EQ-sequence can preserve the adjacent relationships of rooms on a floorplan, but the Q-sequence cannot. The algorithms for encoding, moving and decoding of an EQ-sequence are introduced. With the EQ-sequence, we can check whether two modules abut each other on a floorplan. It has been proved that any floorplan of n rooms is uniquely encoded by an EQ-sequence and any EQ-sequence is uniquely decoded to a floorplan, both in O(n) time.

In this paper, a test architecture optimization for system-on-a-chip under floorplanning constraints is proposed. The models of previous test architecture optimizations were too ideal to be applied to industrial SOCs. To make matters worse, they couldn't treat topological locality of cores, that is, floorplanning constraints. The optimization proposed in this paper can avoid long wires for TAMs in consideration of floorplanning constraints and finish optimizing test architectures within reasonable computation time.

Solution space smoothing allows a local search heuristic to escape from a poor, local minimum. In this paper, we propose a technique that can smooth the rugged terrain surface of the solution space of a placement problem. We test the smoothing heuristics for MCNC benchmarks, and for VLSI placement with pre-placed modules and placement with consideration of congestion. Experiment results demonstrated that solution space smoothing is very efficient for VLSI module placement, and it can be applied to all floorplanning representations proposed so far.

In this paper, we propose a floorplanning method for VLSI building block layout. The proposed method produces a floorplan under the timing constraint for a given netlist. To evaluate the wiring delay, the proposed method estimates the global routing cost for each net with buffer insertion and wire sizing. The slicing structure is adopted to represent a floorplan, and the Elmore delay model is used to estimate the wiring delay. The proposed method is based on simulated annealing. To shorten the computation time, a table look-up method is adopted to calculate the wiring delay. Experimental results show that the proposed algorithm performs well for producing satisfactory floorplans for industrial data.

The sequence-pair was proposed as a representation method of block placement to determine the densest possible placement of rectangular modules in VLSI layout design. A method of achieving bottom left corner packing in O(n2) time based on a given sequence-pair of n rectangles was proposed using horizontal/vertical constraint graphs. Also, a method of determining packing from a sequence-pair in O(n log n) time was proposed. Another method of obtaining packing in O(n log log n) time was recently proposed, but further improvement was still required. In this paper, we propose a method of obtaining packing via the Q-sequence (representation of rectangular dissection) in O(n+k) time from a given sequence-pair of n rectangles with k subsequences called adjacent crosses, given the position of adjacent crosses and the insertion order of dummy modules into adjacent crosses. The position of adjacent crosses and insertion order of dummy modules can be obtained from a sequence-pair in O(n+k) time using the conventional method. Here, we prove that arbitrary packing can be represented by a sequence-pair, keeping the value of k not more than n-3. Therefore, we can determine packing from a sequence-pair with k of O(n) in linear time using the proposed method and the conventional method.

As a design flow for low-power FPGA implementation, Datapath-Layout-Driven Design (DLDD) has been proposed. This letter reports the effect of DLDD for standard-cell-based ASIC implementation, and proposes necessary improvements. Experimental results shows that about 8.3% reduction of power dissipation is achieved in the best case.

In reuse of the VLSI layout design when technology migration takes place, the information to be abstracted from the original design and the data structure to store the information shall be specified. In this paper, they are assumed as the seg-based 4-direction and the parametric BSG, respectively. The parametric BSG is a BSG whose segs are generalized to take any number of units of length. The seg-based 4-direction is the right-of, left-of, above, and below relations between two rooms in accordance with the segs between them. An elegant procedure is given to map the floorplan of the model into a parametric BSG of the minimum size, keeping the abstracted seg-based 4-direction. Merits of the PBSG are discussed and a way of reuse is suggested by illustrative instances. Finally, a superior potential of the parametric BSG as the data structure is discussed empirically.

Boundary Constraints of VLSI floorplanning require a set of blocks to be placed along the boundaries of the chip. Thus, this set of blocks can be adjacent to I/O pads for external communication. Furthermore, these blocks are kept away from the central area so that they do not form blockage for internal routing. In the paper, we devise an algorithm of VLSI floorplanning with boundary constraints using a Corner Block List (CBL) representation. We identify the necessary and sufficient conditions of the CBL representation for the boundary constraints. We design a linear time approach to scan the conditions and formulate a penalty function to punish the constraint violation. A simulated annealing process is adopted to optimize the floorplan. Experiments on MCNC benchmarks show promising results.

With the proliferation of the transistor count in VLSI design, more and more design groups try to figure out an efficient way to combine their designs. The Internet features distributed computing and resource sharing. Consequently, a hierarchical design can adequately be solved in the Internet environment. In this paper, we demonstrate the facilitation of the Internet environment by solving the area minimization floorplan problem. We propose the RMG algorithm taking advantage of the Internet. Based on the model of transfer latencies, the RMG algorithm reduces the computing time by shortening the critical path in the floorplan tree. Our experimental results show that the Internet is suitable for Electronic Design Automation (EDA).

In this paper, we present a hierarchical technique for simultaneous pin assignment and global routing during floorplanning based on the minimum cost maximum integer flow algorithm with several heuristic cost functions. Furthermore, our algorithm handles feedthrough pins and equi-potential pins taking into account global routes. Our algorithm allows various user specified constraints such as pre-specified pin positions, wiring paths, wiring widths and critical nets. Experimental results including Xerox floorplanning benchmark have shown the effectiveness of the heuristics.

A floorplan is a partition of a rectangle into subrectangles, each of which is associated with a module. Zero-wasted-area layouts are known to exist when the height and width of modules are constrained only by the area, and several methods have been proposed for deriving such layouts. However, because these methods are global and indirect, they are inherently slow. We propose a new algorithm which simulates the air-pressure mechanics. It begins with a layout, which is not necessarily feasible, and iterates the movement of one wall at a time to the force-balancing position. The key issue is that it is guaranteed that every movement makes a current layout approach a zero-wasted-area layout by the measure of energy which is defined here. Experimental results on the example in several literatures and artificially made complex examples showed very fast convergence. The algorithm is evolved to methods which move all the walls simultaneously, resulting in a further speed enhancement.

In the floorplan design problem, soft blocks can take various rectilinear shapes. The conventional floorplanning methods, however, restrict their shapes only to rectangle. As a result, waste area often remains in the layout. Some floorplanning methods have been developed to handle rectilinear hard blocks, however, no floorplanning methods have been developed to optimize rectilinear soft blocks. In this paper, we propose a floorplanning method which places rectilinear soft blocks. The advantages of the method are reducing both waste area and wire length. We present Separate-Rejoin method which efficiently forms rectilinear shapes for soft blocks. The result is obtained quickly because the method is based on the slicing structure in spite of handling rectilinear block. Thus, our method is suitable for practical use in terms of layout area, wire length and processing time. We applied our method to a benchmark example and an industrial data. For the benchmark example, our method reduces waste area by 25% and wire length by 13% in comparison with the conventional rectangular soft block approach.

This paper presents a heuristic floorplanning method that improves the method proposed by Vijayan and Tsay. It is based on tentative insertion of constraints, that intentionally produces redundant constraints to make it possible to search in a wide range of solution space. The proposed method can reduce the total area of blocks with the removal and insertion of constraints on the critical path in both horizontal and vertical constraint graphs. Experimental results for MCNC benchmarks showed that the quality of solutions of the proposed method is better than [7],[8] by about 15% on average, and even for the large number of blocks, the proposed method keeps the high quality of solutions.

This paper presents a mathematical formulation of a data path allocation and floorplanning problem using the mixed integer linear programming, and shows some experimental results. We assume that a data flow graph and the scheduled result are given in advance. The chip area and total wire length are used for the quality measures of the solution for the problem. This method is applied to some examples, and compared with the other method reported previously in the points of the solution and computation time.