Computer graphics processing and selective visual display system – Computer graphic processing system – Plural graphics processors
Reexamination Certificate
2000-08-03
2004-09-07
Tung, Kee M. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphic processing system
Plural graphics processors
C345S544000, C718S105000
Reexamination Certificate
active
06788302
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention generally relates to graphical shape data. More specifically, this invention relates to partitioning and load balancing graphical shape data for parallel applications.
2. Background Art
When semiconductor chips are created, there are certain patterns or shapes formed on a semiconductor wafer. These patterns are placed in many different layers. After all of the patterns for all of the layers are made, the semiconductor chip is complete, other than external wiring and packaging.
Often, a graphics file is used to store all of this pattern and shape information. Originally, the process of creating a graphics file was tedious, as each shape was physically laid out on a grid. Since then, these types of systems have become much more automated. Currently, designers use design tools that “hide” the actual graphical layout of the semiconductor chip. Instead, the designers use representations of individual or large parts, and the design tools then know how to actually layout the different parts. Once the design of the chip is complete, the design tools can output the graphics file. A semiconductor processing facility then uses the graphics file to create the semiconductor chip.
One common graphics file for semiconductor chips is called a “GL/1” graphics file, which is a particular file format that represents the graphical shape data for the chip. As is known in the art, a GL/1 graphics file contains a number of cells, which can range into the tens of thousands. Each cell has a number of “transforms”, which can take a different cell and perform various functions on it (such as rotating it, mirroring it, arraying it, etc.). To one skilled in the art of computer science, the transforms act like “includes” in the sense that other cells are included in the current cell. Unlike software, however, the transforms can manipulate the included cells in physical terms. In GL/1 files, there is a “prime” cell which is essentially the master cell. There are also “leaf” or “base” cells where the transform will be “null”, meaning that this cell does not include another cell. The base cells will be the building blocks that other cells can use. As such, these graphics files are nested and hierarchical because many cells may use the base cells and because some cells will include additional cells which themselves include additional cells, etc., until the base cells are finally included.
The cell structure of a GL/1 graphics file may be thought of as a tree: the prime cell is the root of the tree; the leaf or base cells are the leaves of the tree; and the cells between the prime cell and the base cells are the branches. It should also be noted that each cell is part of a level and the GL/1 graphics file will contain all of these levels. Because of this, when the GL/1 graphics file is examined through tools that allow the graphical shape data to be seen, a representation of the graphical shape data will be three dimensional.
Prior to manufacturing the semiconductor chip, the semiconductor processing fab generally runs checks and pre-manufacturing applications and processing on the graphics file. For instance, the facility might run “fill” functions that add metal shapes at levels for the optimum metal-to-oxide ratio to improve manufacturing yields. Alternatively, they could run a “cheese” function that removes metal to create the same optimum ratio. Additionally, the facility might run a very important “design rule checking” (DRC) function that checks to ensure that the patterns and shapes meet manufacturing design rules. If some of these design rules are not met, the chip may not function correctly or may have poor manufacturing yield.
The graphics files are beginning to create problems for semiconductor processing facilities. Without a method and apparatus for solving these problems, semiconductor processing facilities will be hampered more and more by these problems and need to invest in additional facilities improvements.
DISCLOSURE OF INVENTION
Before proceeding with a summary of the invention, it is beneficial to more particularly discuss the problems associated with graphics files. A major problem associated with these files is the amount of data needed for their representation. Contemporary graphics files can be as large as 3 gigabytes. In the future, even larger files will be prevalent. One common graphics file format is called “GL/1”. This format contains all of the many levels and interconnects of the semiconductor chip. Current GL/1 processing tools allow single levels of GL/1 to be separated. However, to perform this function, these tools require the entire graphics file to be loaded into computer memory so that the tools can remove the particular level. It will continue to become much harder to use computer systems with the necessary memory capable of removing the levels. Moreover, as semiconductor technology increases, the number and complexity of the levels increases. Even if the levels can be separated from the graphics file, some of the levels are so complex that it takes lengthy computation time to process these complex levels. These requirements are only going to increase in a super-linear or exponential fashion.
Thus, without a way to partition and load balance graphical shape data for parallel applications, semiconductor processing facilities are going to continue to outlay capital expenditures for increasingly powerful computers having substantial amounts of memory or are going to simply reach a time when their most powerful computers cannot process the graphics files.
The preferred embodiments of the present invention solve these problems by splitting the large graphics file into smaller output “frames” of graphics files. The splitting process is load balanced amongst any number of processors. This allows many processors to be used in parallel to divide the large graphics file and to then process the resulting smaller frames. Additionally, the load balancing is performed in such a manner that only portions of the graphics file are loaded by any one processor. This reduces memory and computational requirements for any one processor. Preferably, the graphics file is divided in a three-dimensional manner, such that any one processor will be assigned one three-dimensional block or volume of the graphics file. The three-dimensional partition of the graphics file will become one frame, and the one processor accesses the graphics file to copy its three-dimensional partition into the new output frame. Applications, such as various check tools, may be used on each computer to process the graphics file. This divides application processing amongst the processors.
Preferably, a metric of “data density” is used to divide the graphics file. The “data density” metric is the ratio of graphics file data per three-dimensional block or volume of space. The data density could have units of, for instance, bytes per cubic millimeter. The data density metric is used to evaluate and divide the graphics files.
The foregoing and other features and advantages of the present invention will be apparent in the preferred embodiments of the invention, as illustrated in the accompanying drawings.
REFERENCES:
patent: 4866637 (1989-09-01), Gonzalez-Lopez et al.
patent: 5530457 (1996-06-01), Helgeson
patent: 5587922 (1996-12-01), Hendrickson et al.
patent: 5598570 (1997-01-01), Ho et al.
patent: 5604848 (1997-02-01), Harada et al.
patent: 5999187 (1999-12-01), Dehmlow et al.
patent: 6008822 (1999-12-01), Yumoto et al.
IBVM Technical Disclosure Bulletin, “Techniques for Improving Multi-Partitioning Algorithm”, vol. 36, No. 1, Jan. 1993, pp. 473-477.
Journal of Parallel and Distributed Computing, “Prototyping and Simulating Parallel, Distributed Computations”, vol. 23, No. 1, Oct. 1994, pp. 1-9.
IBM Technical Disclosure Bulletin, “Placement Optimization Using a Graphical Placement Tool in the VLSI Interactive Design Automation System Database”, vo. 38, No. 8, Aug. 1995, pp. 353-354.
Proceedings Eighth SIAM Conference on Parallel Processing for Scientific Compu
Ditlow Gary S.
Dooling Daria R.
Moran David E.
Williams Ralph J.
Kotulak Richard M.
Schmeiser Olsen & Watts
Tung Kee M.
LandOfFree
Partitioning and load balancing graphical shape data for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Partitioning and load balancing graphical shape data for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partitioning and load balancing graphical shape data for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3205568