Data processing: structural design – modeling – simulation – and em – Simulating nonelectrical device or system – Mechanical
Reexamination Certificate
1997-08-12
2002-04-16
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating nonelectrical device or system
Mechanical
C703S009000, C703S010000
Reexamination Certificate
active
06374200
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a two dimensional object layout apparatus for automatically designing a two-dimensional layout of many objects such as commodities in a warehouse, parts on a printed circuit board, or cells on a VLSI (Very Large Scale Integration) circuit, and a method thereof.
2. Description of the Related Art
In designing a printed circuit and a VLSI, a very large number of circuit parts, transistors, and so forth should be laid out on a two-dimensional board (or a chip). To do that, computer aided design (CAD) systems have been used.
Such CAD systems roughly operate in two phases. The first phase is a logical phase where logic circuits are formed, a process is simulated, and test data is generated. The second phase is a physical phase where cells (parts) are laid out and lines (leads) thereof are connected.
In the second phase, based on a design drawing of a logic circuit received from the first phase, a large number of circuit elements or semiconductor devices are optimally laid out on a two-dimensional plane (of multiple layers) and lines thereof are optimally connected corresponding to a predetermined design rule for each device and therebetween in such a manner that the total area of the structure becomes compact and the line lengths become short.
In the process for laying out cells, it is not effective to directly handle cells in the order of the 0.1 million cells or 1 million cells of an VLSI. Thus, conventionally, the physical design work is hierarchically performed and thereby several tens of cells to several hundreds of cells (module parts) are handled at a time. Each cell has the size and shape necessary for the internal logic and the input/output terminals. These cells should be connected with lines corresponding to the logical design. However, unless the layout of the cells is designated, wiring is not determined.
A fundamental problem for laying out cells is to optimally obtain a two-dimensional layout of cells of various sizes (mainly, rectangular cells) free from two-dimensionally overlapping in consideration of the line connections among them. The optimization of this layout is a problem in which the degree of freedom of the search space is very large. Thus, a highly heuristic solution is required.
The method that has been widely used for easily designing a layout is the standard cell method (gate array method). In this method, the lengths of individual cells are regulated and many cells are laid out breadthwise. Input/output terminals of the cells are laid out lengthwise only. When the lengths of the cells are restricted and the layout positions thereof are restricted, the degree of freedom of the two dimensional layout problem is reduced.
When cells are two-dimensionally laid out without restricting the sizes and shapes thereof, a problem for laying out many rectangles in a two-dimensional container (for example, a circuit base board or a chip) as compactly as possible needs to be solved. Thus, this problem is referred to as “a problem for optimizing a two-dimensional layout of rectangles.”
As one method for optimizing a two-dimensional layout of rectangles, Otten et al. has proposed the “Slicing floorplan” method (R. H. J. M Otten, “Automatic Floorplan Design, in Proc. 19th ACM/IEEE Design Automation Conf., pp. 261-267, 1982). In this method, one rectangular base board is sliced lengthwise or breadthwise into two portions at a suitable position. Each of the sliced portions is further sliced into two portions. This process is repeated.
A two-branched tree that represents such division is formed as a data structure. By laying out individual cells to branches, the required area is obtained. By varying the dividing method (a combination of lengthwise and breadth wise slicing), the minimum area is obtained. A drawback of this method is in that rectangles cannot be laid out in a chained pattern.
In addition, Nakatake et al. has proposed the BSG (Bounded Slicing Grid) method for optimizing a two-dimensional layout of rectangles (S. Nakatake, K. Fujiyoshi, H. Murata, Y. Kajitani, “Module Placement on BSG-Structure and IC Layout Applications,” Int. Conf. on Computer Aided Design, 1996). In this method, cells are laid out on grids with a special structure termed a BSG. The cells are mapped to a physical space corresponding to the rules of BSG method.
The BSG method represents a restriction in which cells are laid out lengthwise and breadth wise adjacent to the positions of the BSG grids. Since this restriction is strict, blanks are inserted at suitable positions on the grids to obtain a more compact layout. To optimize the layout of the cells, trial and error is repeated in laying out cells in the BSG and an optimum result is selected.
In the aforementioned standard cell method, slicing floorplan method, and BSG method, as a common process, various layouts are simulated and an optimum result is obtained. When this trial and error process is manually performed, huge amounts of work are required.
To solve this problem, with a proper evaluation function, the simulation is performed as effectively and systematically as possible. To do that, a conventional optimizing method can be used. As such a conventional method, the simulated annealing (SA) method has become popular.
In the SA method, the optimizing search space is represented with parameters. By a converting operation with parameters including a probability element, a desired solution is searched for by trial and error. In the SA method, it is important to consider how search parameters are structured for the problem they are to be applied to, (in this case a problem of a two-dimensional layout of rectangles), and when a particular parameter is given, how the given parameter is converted into a particular space (namely, laid out two-dimensionally) and how the obtained result is evaluated.
These points should be considered for individual problems and solutions. In reality, the optimization by the SA method has been attempted with the standard cell method, slicing floorplan method, and BSG method.
However, the aforementioned conventional solving methods have the following drawbacks.
In the standard cell method, so as to simplify a given problem, the lengths of cells and the two-dimensional layout thereof are restricted. According to this method, although the problem is simplified, it is not assured that wiring among the cells are optimum. It is logically clear that when such restrictions are not applied, better layout results can be obtained.
In the slicing floorplan method, since the slicing in two process is repeated, special layouts such as a four-rectangle-chained shape cannot be represented. Although a modification method for representing such a shape has been studied, complicated calculations are required.
In the BSG method, the structure of the grids is special and complicated. In addition, the restrictions are strict. In other words, unless many blanks are inserted on the grids, cells cannot be freely laid out. Thus, the BSG method is used for automatically optimizing a layout of cells corresponding to the SA method, rather than creating a BSG that represents a two-dimensional layout by a designer. Although good results from calculations in the SA method have been obtained at the laboratory level, they should be further improved for practical use.
As described above, although many CAD tools for two-dimensional layouts have been developed and used, with respect to calculation time and quality thereof, there are still many problems to be solved.
In the designing phase of a cell layout for a VLSI that requires high performance, it is stated that a manual layout performed by an experienced designer is superior to an automatic layout. In addition, as the structure and scale of the VLSI have become complicated and large and the required design period has become short, a new approach for solving the problem of a two-dimensional layout has been strongly desired.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a two-dimen
Fujitsu Limited
Jones Hugh
Teska Kevin J.
LandOfFree
Layout apparatus for laying out objects in space and method... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Layout apparatus for laying out objects in space and method..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Layout apparatus for laying out objects in space and method... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2841513