Mask data preparation using a generic hierarchical engine
04/01/2003
Mask data preparation has been identified as a severe bottleneck and data volumes are more than doubling each year as the industry pursues the ITRS roadmap. Part of the data explosion is because some software tools are not able to deal with hierarchical data, i.e., the software completely destroys (flattens) hierarchy. The problem is intensified by the fact that electronic layouts are usually flattened on their path from the hierarchical source downstream to the wafer. Flattening means a data explosion. With the increasing use of optical proximity correction and phase-shifting masks, data volumes are quickly escalating. Hierarchical treatment is one of the most powerful means to contain memory consumption and CPU loads.
A hierarchical engine is a software package that is able to handle hierarchical layouts without flattening the data. Mask data preparation is the most critical area—one that calls for a sound infrastructure to reduce the data-handling problem. Gaining more attention, though, are other applications such as large area simulation and manufacturing rule checking. All would profit from a generic engine capable of efficiently treating hierarchical data. Efficiency is a measure of how hierarchy is exploited—processing the data in such a way as to reduce processing time while also preserving hierarchy in order to keep the amount of data small.
The major challenge for a hierarchical engine is to preserve steady transitions along cell borders. A cell is seen as a "tile" of a wallpapered large area. To process a cell without consideration for adjacent cells would destroy a steady transition. To flatten the layout would solve the problem, but would also cause a data explosion. A hierarchical engine links neighboring cells without destroying the hierarchy.
null
Figure 1 taken from the cell field of a DRAM demonstrates the effect of processing an isolated leaf by ignoring the neighborhood. In the actual layout (Fig. 1, left), a tile is used for wallpapering a large area; note the left and right border of the aerial image of the tile. As the calculation has no information on the bit lines crossing the border, the contour lines are closed at the ends. Thus, the influence of the neighborhood is neglected.
What has been shown so far is true for any physical effect with a nonvanishing influence range. Prominent examples are proximity effects of any kind, whether caused by optical interference or electron-beam scattering; flattening the layout circumvents the problem. If the neighborhood is nonrepetitive, then there is no reason to maintain hierarchy. If, however, the neighborhood is repetitive, is there a way to exploit the hierarchy?
A generic engine for hierarchical treatment that solves the major problem of steady transitions along cell borders is presented below. Because the art of design and the degree and quality of hierarchy provides a large variety of hierarchical layouts, a generic engine has to make intelligent decisions when exploding the hierarchy tree. A solution for creating a data hierarchy with maximum efficiency is discussed, and it will be shown how far the limits of exploitation of hierarchy can be pushed with this engine.
Layout data-processing challenges
Processing layout data on its way to the mask shop is a critical yet time-consuming task. The reason is that the CPU time and memory capacity required for some data-processing steps scales at a faster pace than the enhancements of the computer equipment. The physical layout of integrated circuits is typically represented in a compacted form, a so-called hierarchy tree. The quality and usability of hierarchy depends on the creation process. The productivity of designers depends on their cleverness in reusing cells. Place and route tools have a tendency to destroy any hierarchy. Hierarchy is, therefore, not a cure-all. It is a strong measure when the hierarchy factor is large enough. If so, it is worthwhile to exploit.
The requirement for continuity calls for treatment of data in a way that takes note of the neighborhood. It is immediately apparent that walking through a hierarchy tree by just addressing the leaves is not a solution. A generic methodology to exploit the hierarchy by providing continuous transitions at the borders is presented below.
Continuity
Continuity across cell borders has to be provided in hierarchical processing. The borders of cells do not seamlessly stitch together if only the contents of cells are regarded and not their immediate neighborhood. Elements of the neighborhood influence the cell, given the distance is smaller than a certain range. The influence range, in turn, is a function of the quantity observed. In designing a hierarchical engine, it is most efficient to assume a constant influence range by choosing it to be a little larger for safety reasons.
 |
Figure 2. Layout of Fig. 1, including the influence range. The cell on the left has been sized by roughly l/NA = 248/0.6nm ~ 400nm. A dashed line in the layout displays the original cell and aids in seeing where the influence range begins; this line is also the border for the intensity distribution on the right. As the bit lines continue across the left and right border, a difference is expected along these lines. The effect is visible in the intensity distribution at the border between the adjoining tiles.
 Figure 3. Core and seam of cells showing instances of cell A and cell B. The proximity area of A intersects B, so a new variant (A*) must be created |
null
Looking at the aerial image, the hierarchy engine hems around the cell with a constant seam (left side of Fig. 2). In contrast to Fig. 1, the area can be wallpapered with the calculated cell by cutting the extra seam off. So, the seam is only used to take the neighboring influence into account; however, it is not used in the expansion of the layout. Taking the neighborhood into account will change the hierarchy when generating enlarged cells. If every neighbor of a cell were different, the hierarchy tree would locally collapse to many leaves. In an extreme case, the entire tree might collapse. A strategy to create a tree containing cells with seams is needed.
Strategy of hierarchical processing
While aiming for a generic engine, the physical effect can, for example, be the function describing the image formation in an optical projection system or a point spread function describing the scattering of electrons. The hierarchy tree is processed by applying the transfer function, or operator F, which models the physical effect, onto a cell. The result is typically a scalar field S over a suitably defined grid (x, y).
S(cell, x, y) = F(cell)
The task is to develop a strategy providing continuity across cell borders. At first sight, it appears unnatural to start at the top of a tree. A hierarchical layout contains a hierarchy tree representing relationships between structures (e.g., structure A is father of structure B). The hierarchy tree itself, however, does not carry information on the geometrical neighborhood.
The top-down method for handling hierarchical data needs a pre-processing step, the so-called "variant creation." A variant of a structure definition is composed of a core and a shell (Fig. 3). The core is the structure definition itself. The shell encompasses the neighborhood of the structure reference consisting of all elements within the proximity range around the cell.
To create variants, start at the top of the hierarchy tree and move downward to build them (i.e., the top-down approach). In order to build a variant, a structure reference with its proximity area is considered and compared to all existing variants with the same core. If the variant already exists, no action is needed; otherwise, a new variant must be created. A new name list, containing all the new variants, is the result, and a modified hierarchy tree is also obtained. After the variant creation, a final state is reached where it is known that there is no further constellation in the layout that is not already considered in any of the variants.
After the pre-step, all variants are generated and the hierarchy engine can now traverse the name list of the variants in any order by taking every variant, including its shell, as isolated. After processing, all shells are removed, since only the set of cores contain the correct result.
There is one more advantage to the top-down strategy — it rebuilds the hierarchy tree before processing. It is therefore possible to assess how much of the existing hierarchy is usable and characteristic numbers for hierarchical processing can be calculated for each branch of the hierarchy tree [1]. A decision can be made, depending on the degree of compaction, whether traversing the modified branch of the hierarchy tree is more efficient than flattening it.
Hierarchy guidelines
In many cases, the same layout can be constructed in different ways. For example, Fig. 4 demonstrates the creation of a kind of hierarchy that gains CPU time and memory. The left sub-tree is much easier to handle. The process is as follows: cell E will be surrounded by a seam corresponding to the influence range. Next, the original pitch and repeat rate in x and y are applied to check if all enlarged cells are the same. The corners and edges are typically different from the center as shown below. A minimum of four different variants is created. Taking the right tree, the algorithm detects overlap of A and B and C and D, which, at first glance, leads to a completely flat cell.
 |
Figure 4. A 2-D array and possible hierarchy trees. Scenarios like this are often found in repetitive layouts. The hierarchy tree on the right is one alternative to describe the layout. Four 2-D arrays are used to create overlaps over the entire range of the array — very unfortunate for hierarchical processing. The alternative on the left is a favorable case and contains the unit cell E (i.e., the pattern that fills the entire space by shifting the unit cell in the x and y directions). The unit cell is represented by the dashed line.
 |
null
In summary, the efficiency of hierarchical processing can be greatly enhanced by following these guidelines, ranked in order of importance:
- large arrays: use the unit cell as the base cell of the array; in other words, avoid interleaving arrays;
- large arrays: use the unit cell of space group p1 instead of the asymmetric units; avoid symmetry operators throughout the layout (memory and time consuming); and
- avoid random instances of cells; instead, use repetition.
Performance considerations
Figure 1 shows an example of the degree to which the hierarchy collapses and the gains that can be expected from hierarchical treatment. To start, the aerial image of a large area represented by an array with a repeat rate of 64 in x and 63 in y of the cell of Fig. 1 can be displayed. The hierarchy engine takes the influence range of the physical effect into account, in this case, a range of 0.4µm on each side of the cell. The array collapses into four 1-D arrays and one 2-D array. The corners, one cell each, are flat data. After hierarchical processing, there are nine different cells.
The collapse of the hierarchy tree depends primarily on the size of the influence range, so a more systematic view is of interest. The table shows this dependence and the quantitative gain of hierarchical processing over flat processing for a specific case. The second row is typical for optical interference effects with a wavelength of l = 248nm. E-beam proximity correction would be described by a value between 1–10µm; the gain is still considerable. As expected, for a large influence range, the physical effect turns the layout into a flat one, in which hierarchical processing creates more overhead than it does any good, as shown in the last row of the table.
Conclusion
A generic hierarchical engine has been presented that is able to cope with any physical effect. A microlithography application — the calculation of large aerial images — was described. But the e-beam proximity effect or a manufacturing rule checker could have been used as well. The top-down approach in this example was, as it is in most cases, more efficient, because it creates a valuable intermediate result: a modified hierarchy tree. The opportunities to create hierarchy trees, given a specific layout, are abundant. Several guidelines that create favorable trees for a top-down process were illustrated. Additionally, some of the unfavorable cases, which are widespread, were shown. The guidelines under which hierarchical processing can be accelerated to a large extent without creating undue requirements were named. In particular, the description of large arrays should be done by following wallpaper tilings. Further work is needed, including intense collaboration with designers.
Regarding performance considerations, it is almost impossible to make a general statement for the improvement of a hierarchical engine over its flat counterpart. Therefore, a specific case of a medium-size array was chosen and the gain in CPU time for small influence ranges was demonstrated. The intuitive expectation that for large proximities the benefit turns into a disadvantage was also made manifest. The conditions under which the generic hierarchical engine outperforms a flat engine can be named. To fulfill the conditions, however, may be an education process for the industry.
Michal Simecek, Christoph Sambale, Christian K. Kalus, SIGMA-C, Munich, Germany
Reference
1. C.K. Kalus, M. Simecek, "Elements of Hierarchical Mask Data Preparation," Proceedings of the European Mask Conference, Munich 2002, in press.
Michal Simecek is project manager, CAPROX, at SIGMA-C.
Christoph Sambale is a software engineer at SIGMA-C.
Christian K. Kalus is CEO and president of SIGMA-C GmbH, Thomas-Dehler-Str. 9, 81737 Munich, Germany; ph 49/89-63025740, fax 49/89-63025749, e-mail [email protected].