Data management method for mask writing

FIELD OF THE INVENTION

0001The present invention relates to photolithographic patterning, such as methods for creating photolithographic masks or reticles, and in particular, relates to data preparation methods for photolithographic masks or reticles.

BACKGROUND OF THE INVENTION

0002The vast majority of all complex integrated circuits (ICs) are created by circuit designers using computers. Most circuit designers use computer programs to define the functionality required of the circuit and the computer analyzes the functionality requested in order to create the electronic equivalent of a circuit diagram.

0003To convert the designers intent into a physical, integrated circuit, other computer programs take libraries of cells representing groups of transistors and other low level circuit components that provide the desired functionality, determine locations for these components, and construct the wiring necessary to interconnect them. Such a tool is often called a “place and route tool.” Custom design tools also exist to provide other methods to craft complete IC layouts. Once all the electronic devices have a physical representation, it is expected that the physical circuit will deliver the specified electrical performance.

0004The layers of the layout data are then fabricated as a set of masks, used in the photolithographic definition and processing of the actual circuits themselves.

0005Before translating the IC layout data into a format for use by a photolithographic mask or reticle writing tool, the IC layout data is often analyzed by another computer program to ensure that no design rules have been broken during the creation of the IC layout data and/or to correct for errors that can occur during the photolithographic printing process.

0006One example of such a program is the Calibre™ program produced by Mentor Graphics Corporation of Wilsonville, Oreg., the assignee of the present application. The Calibre™ program is a suite of tools that operate on the IC layout data. These tools include a design rule checking (DRC) program that ensures the compliance with a number of design rules particular to the manufacturing process to be used. For example, a design rule can specify a particular tolerance such as “no transistors can be located within x microns of other transistors,” etc. In addition, the Calibre™ program can perform optical process correction (OPC) to compensate the layout for distortions that occur during the printing of the photolithographic mask or reticle. In addition, Calibre™ can perform phase shift mask (PSM) modifications that add phase shifters to the mask or reticle in order to enhance contrast between features or add subresolution features on an integrated circuit.

0007The next step in preparing an integrated circuit is to translate the verified and/or corrected IC layout data into a format that can be utilized by a mask or reticle writing tool. Examples of such formats are MEBES, for raster scanning machines manufactured by ETEC, an Applied Materials Company, “.MIC” format from Micronics AB in Sweden for their mask writers, and various vector scan formats for Toshiba, JEOL, and Hitachi. Once written, the masks or reticles are then used in a photolithographic process to expose selected areas of a silicon wafer in order to produce the integrated circuit components on the wafer. Typical mask writing tool formats are flat, and computer files written in these formats containing the corrected IC layout data can be enormous. For example, one IC layout data file for a single layer of a field programmable gate array can be approximately 58 gigabytes long. The time required to transmit a file of this size to a mask or reticle writing tool with standard network protocols can exceed 60 hours. When such large files are transmitted over communication networks, the risk that an error will occur during transmission rises with the length of the file transmitted. In addition, the time required to transmit the data file can be longer than the time required for the mask or reticle writer to produce a mask or reticle from the file. Therefore, the mask writing tool is inefficiently used when the data files are too large.

0008Given these problems, there is a need for an improved method of translating data into a format that can be read by a photolithographic mask or reticle writing tool that will reduce the size of the file to be transmitted and reduce the likelihood of transmission errors.

SUMMARY OF THE INVENTION

0009The present invention is a method of reducing the amount of data that is transmitted to a mask or reticle writing tool to produce an IC or other device by a photolithographic process. A computer reads a file having a number of cells that completely define a layer of the device. One or more of these cells are selected and modified based on the interaction of the selected cells with other cells in the device layout. One or more additional or remainder cells are created that will produce structures on the mask not produced by the modified cells and will also prevent the formation of extraneous structures on the mask by the modified cells. The computer then creates a jobdeck for the mask or reticle writing tool that includes all the placements on the mask of the modified cells and the one or more additional cells. The jobdeck is created in a format that is readable by the mask or reticle writing tool. Once the description is complete, the jobdeck and the descriptions of the cells placed in the jobdeck are transmitted to the mask or reticle writing tool for execution. The data representation of the device layer using a jobdeck and cells is more compact than traditional flat formats for mask writing tools, yet also provides a complete set of instructions to produce the same mask.

BRIEF DESCRIPTION OF THE DRAWINGS

0010The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same become better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein:

0011<figref idref="DRAWINGS">FIG. 1</figref> illustrates a computer system used to create photolithographic masks in accordance with the present invention;

0012<figref idref="DRAWINGS">FIG. 2A</figref> is a simplified diagram of an IC layout including one or more cells having repeated patterns of polygons;

0013<figref idref="DRAWINGS">FIG. 2B</figref> illustrates a hierarchical structure of the cells that comprise the IC layout shown in <figref idref="DRAWINGS">FIG. 2A</figref>;

0014<figref idref="DRAWINGS">FIG. 3A</figref> is a simplified IC layout having a number of cells with repeating patterns of polygons;

0015<figref idref="DRAWINGS">FIGS. 3B-3E</figref> illustrate the individual polygons within cells that comprise the IC layout shown in <figref idref="DRAWINGS">FIG. 3A</figref>;

0016<figref idref="DRAWINGS">FIG. 3F</figref> illustrates a hierarchical structure of the cells that comprise the IC layout shown in <figref idref="DRAWINGS">FIG. 3A</figref>;

0017<figref idref="DRAWINGS">FIG. 4</figref> illustrates the IC layout shown in <figref idref="DRAWINGS">FIG. 3A</figref> after it has been “flattened”; and

0018<figref idref="DRAWINGS">FIGS. 5A-5D</figref> illustrate a number of modified cells and a remainder cell for use in creating a photolithographic mask in accordance with one embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

0019As indicated above, the present invention is a method and apparatus for creating a mask from IC layout data in a manner that reduces the amount of data that is transmitted to a mask writing tool, This is done by identifying certain cells that are repeated and eliminating redundant representations. To insure the entire chip is faithfully reconstructed, certain modifications are made to the cells as described below. Machine jobdeck formats then specify where the cells are to be placed on the mask to insure the complete layer is produced.

0020Although the present specification utilizes the term photolithographic “masks” and mask writing tools, it will be appreciated that the present invention is also applicable to systems that create photolithographic reticles, as well as for systems similar to mask writing systems that actually write patterns directly on wafers or other substrates. Therefore, as used herein, the term “mask” is intended to refer to both photolithographic masks and reticles as well as other structures that modulate lithographic exposure. Furthermore, although the present embodiment describes layout manipulations for production in a mask writing tool, it is clear that these same techniques can be applied to similar exposure systems that produce patterns on other substrates, such as semiconductor wafers or quartz waveguide substrates. In addition, although the present embodiment of the invention is described with respect to IC layout data, it will be appreciated that the techniques of the present invention are useful for producing other types of devices that require the use of photolithographic masks such as microelectromechanical systems (MEMS), thin film heads for magnetic recording, genechips for biological assays, etc.

0021<figref idref="DRAWINGS">FIG. 1</figref> illustrates a system for creating photolithographic masks in accordance with known methods and which can also be used in accordance with the present invention. A computer system <b>10</b> receives a file that contains the IC layout data and stores it in a database <b>12</b>. In the presently preferred embodiment of the invention, the computer system <b>10</b> runs the Calibre™ program that stores the IC layout data in a hierarchical database. The Calibre™ program subjects the IC layout data to design rule checking (DRC), optical process control (OPC) and may add phase shift masks (PSM) to the IC layout data in order to ensure the manufacturability of the IC as well as to compensate for distortions that can occur as part of a photolithographic process. In practice, processing speed improvements can be achieved by using computers with multiple processors (multithreading), or by distributing the computation tasks among a network of computers.

0022Once the IC layout data has been verified, the data is translated to a suitable mask writing tool data format and transmitted via a communication link <b>14</b> to the mask writing tool <b>16</b>. Typically, the communication link <b>14</b> is a dedicated computer link, a shared data communication link, such as a leased telephonic link, or a local or wide area network. As indicated above, the time required to transmit an IC layout from the computer system <b>10</b> to the mask writing tool <b>16</b> can be considerable.

0023The present invention seeks to reduce the amount of data that is transmitted from the computer system <b>10</b> to the mask writing tool <b>16</b>, by taking advantage of jobdeck management capabilities of the mask writing tool. Many mask writing tools have the ability to write data for several integrated circuits on the same mask. Typically, a jobdeck is created to specify the sequence and placement of these various circuit layouts within the mask. Jobdecks also typically contain practical information for the mask writing tool, such as the writing beam spot size, the address unit, dose control information, etc. As will be described in further detail below, the present invention takes advantage of the jobdeck format or language to eliminate the need to transmit redundant IC layout data to the mask writing tool.

0024<figref idref="DRAWINGS">FIG. 2A</figref> illustrates an IC layout <b>20</b> having a number of cells. The IC layout <b>20</b> has a number of replicated cells A as indicated by the reference number <b>22</b>, a cell B indicated by the reference number <b>24</b>, a cell C as indicated by the reference number <b>26</b>, a cell D as indicated by the reference number <b>28</b>, and a top cell T as indicated by the reference number <b>30</b>.

0025The IC layout shown in <figref idref="DRAWINGS">FIG. 2A</figref> can be represented as a hierarchical data structure as shown in FIG. <b>2</b>B. The top cell T includes each of the cells A, B, C, and D. The cell B includes a 3×7 array of cells A and the cell C includes a 2×2 array of cells A. The Calibre™ program produced by Mentor Graphics stores IC layout data in a hierarchical data structure of the type shown in FIG. <b>2</b>B. The hierarchical data structure is advantageous because complete descriptions of cells that are repeated in the IC layout do not need to be repeated in the database at every instance where the repeated cell occurs.

0026In conventional layout data preparation for mask creation, the IC layout data stored within a hierarchical database is “flattened” or compressed to a single layer. In a flattened file, a full description of a repeated cell is provided for each placement of the repeated cell and the descriptions are transmitted to the mask writing tool. As indicated above, flattened IC layout data files can be extremely large and time consuming to transmit.

0027<figref idref="DRAWINGS">FIG. 3A</figref> shows a simplified layout that illustrates various aspects of the present invention. It will be appreciated by those skilled in the art that the polygons shown in the cells of the layout are for purposes of illustration and is not supposed to represent actual circuit components. The layout shown in <figref idref="DRAWINGS">FIG. 3A</figref> includes four cells, as illustrated by the hierarchy tree in FIG. <b>3</b>F: a top cell T as indicated by the reference number <b>50</b>, a cell B as indicated by the reference number <b>52</b>, a cell C as indicated by reference number <b>54</b>, and one instance of a cell A as represented by reference number <b>56</b>′″. In addition, cell B contains two instances of cell A as represented by reference numbers <b>56</b>′ and <b>56</b>″. As will be appreciated from <figref idref="DRAWINGS">FIG. 3A</figref>, the cell <b>56</b>′″ is rotated clockwise 90° with respect to the other instances <b>56</b>′ and <b>56</b>″ of the cell A.

0028Each of the cells includes one or more polygons that define desired structures on a photolithographic mask. The structures defined by a polygon can be an opaque chrome area surrounded by clear areas in the case of bright-field photolithographic masks. Alternatively, the polygons can define structures that are clear areas on the mask surrounded by opaque areas in the case of dark-field photolithographic masks.

0029Each instance <b>56</b>′, <b>56</b>″, and <b>56</b>′″ of all the A cells include two polygons P<b>10</b> and P<b>12</b>. Cell B <b>52</b> has a single polygon P<b>14</b>. The cell C <b>54</b> has a single polygon P<b>16</b> and the top cell T <b>50</b> has a single polygon P<b>18</b>.

0030<figref idref="DRAWINGS">FIG. 4</figref> illustrates the top cell <b>50</b> if each of the remaining cells A, B, and C is flattened into a single data layer. The top cell <b>50</b> includes each instance of the polygons P<b>10</b>, P<b>12</b>, P<b>14</b>, P<b>16</b>, and P<b>18</b> contained in each of the previously described cells.

0031<figref idref="DRAWINGS">FIG. 5</figref> illustrates the cells for the layout of <figref idref="DRAWINGS">FIG. 3</figref> as modified by an embodiment of the invention. Each polygon originally in the layout of <figref idref="DRAWINGS">FIG. 3</figref> has a corresponding structure among the modified cells M<b>56</b>, M<b>54</b>, and M<b>64</b>, but additional polygons have been created to account for the overlap of cells when combined to write the mask. This will be described in more detail below.

0032To reduce the amount of IC layout data that is transmitted to a mask writing tool, the present invention selects certain cells and transmits fewer descriptions of a selected cell than the number of times the cell appears in the IC layout. Instead, a jobdeck simply specifies the placement of the repeated cells. As used herein, the term “repeated cell” refers to a cell that has a pattern of polygons that is repeated two or more times throughout the IC layout. In <figref idref="DRAWINGS">FIG. 3A</figref>, cell A is a repeated cell.

0033To write the mask, a repeated cell is loaded onto the mask writing tool, and written at various locations according to the jobdeck. This is typically done by making a coarse adjustment to the mask writing tool stage to set the overall position, then the fine patterns are written with local exposure control. Each time the stage of the mask writing tool is moved, there is some settling time. Therefore, if the selected cells are too small, the time required to write all the placements of the cells on the mask increases. On the other hand, if the area of selected cell is too large, then the time to transfer its description to the mask writing tool is too long. Finally, the area occupied by the selected cells on the mask should be maximized. It is against these competing criteria that cells of the IC layout are selected.

0034The set of cells that best meets these criteria may be optimally selected by considering every set of cells of every possible size. This method may be computationally time-consuming. Approximation methods may therefore be used that select a suboptimal set. In practice these approximate methods work very well, often as well as the optimal method, and with much less computation.

0035One such approximate method of selecting cells is to evaluate each cell in accordance with a cost function. In an actual embodiment of the invention, the cost function is set forth in Equation 1: <maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>M</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>i</mi></mrow><mo>=</mo><mrow><mrow><mi>K</mi><mo>·</mo><mfrac><mi>Ci</mi><mrow><mi>area</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>left</mi></mrow></mfrac></mrow><mo>+</mo><msup><mi>exp</mi><mrow><mo>-</mo><mrow><mo>(</mo><mfrac><mrow><mo>|</mo><mrow><mfrac><mi>Ai</mi><mi>chiparea</mi></mfrac><mo>-</mo><mi>M</mi></mrow><mo>|</mo></mrow><mi>S</mi></mfrac><mo>)</mo></mrow></mrow></msup></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> where “Mi” is the cost function result of a given cell, “Ci” is the coverage for the cell, i.e., the total area occupied by all instances of the cell within the integrated circuit. The term “chip area” refers to the total area of the integrated circuit. The term “area left” is the chip area less the area occupied by any previously selected cells. The term “Ai” is the area of an individual instance of the cell under consideration. Cell area may be measured as simply the size of the rectangular extent of the cell. A more accurate measurement reflects the area of the cell not overlapped by other cell placements in any of its placements (“template-specific area”), and the geometrical complexity of the data within that area. The term “M” represents an ideal cell area, which, in one embodiment of the invention, is about {fraction (1/250)} of the area of the integrated circuit and the term “S” characterizes the useful range of cell area values around M.

0036Each cell in the IC layout is given a score for the cost function and the highest scoring cells are chosen as the selected cells.

0037The following is a pseudo-code listing of a computer program that implements the selection of cells (referred to as cover cells in the pseudo-code) according to the cost function set forth in Equation 1.

0038<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0" pgwide="1"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>Inputs:</entry></row><row><entry /><entry>-------</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="77pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>hierarchical database</entry><entry>Contains geometry, overlap areas, and the hierarchy.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>Algorithm:</entry></row><row><entry /><entry>----------</entry></row><row><entry /><entry>// First, allocate storage space for various values for each cell.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="77pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>AllocateArray a[];</entry><entry>// Template specific area for each cell.</entry></row><row><entry /><entry>AllocateArray n[];</entry><entry>// Number of flat placements of each cell.</entry></row><row><entry /><entry>AllocateArray c[];</entry><entry>// “Coverage” for each cell.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>// Compute initial values for a[] and c[].</entry></row><row><entry /><entry>for each (cell in database) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>a[i] = EXTENT(cell) − OVERLAP_AREA(cell); // The template-specific area.</entry></row><row><entry /><entry>n[i] = number of flat placements of cell (from database);</entry></row><row><entry /><entry>c[i] = n[i] * tsArea;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>// Next, cover the chip area with placements of individually selected cells.</entry></row><row><entry /><entry>// After each cell is selected, update the area and placement count records</entry></row><row><entry /><entry>// for all remaining (not yet selected) cells.</entry></row><row><entry /><entry>stop = false;</entry></row><row><entry /><entry>areaLeft = total chip area;</entry></row><row><entry /><entry>coverCells = {};</entry></row><row><entry /><entry>while (stop == false) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>maxScore = 0;</entry></row><row><entry /><entry>maxCell = 0;</entry></row><row><entry /><entry>nTotal = 0;</entry></row><row><entry /><entry>NL = 4; NU = 300; // Empirically chosen constants.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>// The cell mark is a general purpose database flag.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>for each (cell in database) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry /><entry>if (NL <= n[cell] <= NU) clear cell mark;</entry></row><row><entry /><entry>else set cell mark;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>for each (unmarked cell in database) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry /><entry>m = Score(c[cell], a[cell], areaLeft);</entry></row><row><entry /><entry>if (m > maxScore) {</entry></row><row><entry /><entry> maxScore = m;</entry></row><row><entry /><entry> maxCell = cell;</entry></row><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>coverCells = coverCells UNION {maxCell};</entry></row><row><entry /><entry>nTotal = nTotal + n[cell];</entry></row><row><entry /><entry>areaLeft = areaLeft − c[cell];</entry></row><row><entry /><entry>UpdateCoverage(c, a, maxCell, database);</entry></row><row><entry /><entry>stop = UpdateStop(areaLeft, nTotal, maxCell);</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>// The coverage score function.</entry></row><row><entry /><entry>Score (ci, ai, areaLeft) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>// Empirically chosen constants.</entry></row><row><entry /><entry>K = 2;</entry></row><row><entry /><entry>M = 0.004;</entry></row><row><entry /><entry>S = 0.01;</entry></row><row><entry /><entry>return (K * (ci/areaLeft) + exp {-(|ai/chipArea- M|) /S};</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>// The stopping condition update function.</entry></row><row><entry /><entry>UpdateStop (areaLeft, n, maxCell) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>// Empirically chosen constants.</entry></row><row><entry /><entry>MAX_COVER = 40;</entry></row><row><entry /><entry>MAX_PLACEMENTS = 400;</entry></row><row><entry /><entry>AREA_LEFT = 0.05</entry></row><row><entry /><entry>// Stop if the number of selected cells is too large, the number</entry></row><row><entry /><entry>// of total placements is too large, or enough area has been covered.</entry></row><row><entry /><entry>return true if ((|coverCells| > MAX_COVER) OR</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>(nTotal > MAX_PLACEMENTS) OR</entry></row><row><entry /><entry>(areaLeft/chipArea < AREA_LEFT));</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>else return false;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>// The coverage update function.</entry></row><row><entry /><entry>UpdateCoverage (c, a, coverCell, database) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>// First, mark cells that contain the chosen cover cell.</entry></row><row><entry /><entry>// Disqualify these cells as future cover cells.</entry></row><row><entry /><entry>// “Previous” means previous in the topological sort sense.</entry></row><row><entry /><entry>// Alternatively, one could modify a[i] to account for</entry></row><row><entry /><entry>// placements of the cover cell, but that is less efficient.</entry></row><row><entry /><entry>mark (coverCell);</entry></row><row><entry /><entry>for (currentCell = coverCell−>previous; currentCell != TOPCELL;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>currentCell = coverCell−>previous) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>if (any placement of currentCell is marked) mark(currentCell);</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>// Now reduce coverage for cells that have placements in the</entry></row><row><entry /><entry>// cover cell.</entry></row><row><entry /><entry>// “Next” means next in the topological sort sense.</entry></row><row><entry /><entry>AllocateArray nn[]; // Number of placements of each cell in the cover cell.</entry></row><row><entry /><entry>initialize nn[] to zero;</entry></row><row><entry /><entry>for (currentCell = coverCell−>next; currentCell != BOTTOM;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>currentCell = currentCell−>next) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>for each (placement in currentCell) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry /><entry>nn[placement's cell] += nn[currentCell];</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>for each (cell in database) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="35pt" align="left" /><colspec colname="1" colwidth="224pt" align="left" /><tbody valign="top"><row><entry /><entry> c[cell] −= nn[cell] * n[coverCell];</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="259pt" align="left" /><tbody valign="top"><row><entry>}</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0039Although any cell is suitable for consideration as a selected cell, performance enhancements can be made by only considering cells that are repeated more than some minimum number of times in the layout and less than a maximum number of times in the layout. In one embodiment, the minimum number of times a cell must be repeated to be considered is 4 and the maximum number of times a cell can be repeated is several hundred.

0040Although one embodiment of the invention utilizes the cost function described above, it will be appreciated that there are other ways to select cells. For example, cells could be selected based on size alone, such as any cell having {fraction (1/200)}th area of the integrated circuit could be used. Alternatively, density of a cell could be used. Cells having a greater density of polygons take more time to transmit, so redundant cells having a relatively large area and high density could be selected. Manual selection could also be used.

0041In the example shown in <figref idref="DRAWINGS">FIG. 3A</figref>, the cells A and C are selected. Cell C is a selected cell for the purposes of illustrating aspects of the present invention even though it is not a repeated cell in the IC layout.

0042Next, the selected cells are modified to compensate for other cells that interact with the selected cells. In the one embodiment of the invention, the interaction of cells with selected cells is limited to the addition of polygons or portions of polygons from non-selected cells, which overlap a selected cell. However, other types of interaction may also be compensated, such as optical interference or etch microloading.

0043As can be seen in <figref idref="DRAWINGS">FIG. 3A</figref>, the B cell <b>52</b> includes a polygon P<b>14</b> having a portion of which overlaps the instance <b>56</b>′ of the A cell. Therefore, a modified A cell M<b>56</b>, as shown in <figref idref="DRAWINGS">FIG. 5B</figref>, is created having a polygon P<b>40</b> that represents the overlapping portion of the polygon P<b>14</b> and the instance <b>56</b>′ of the selected cell A. Similarly, a portion of the polygon P<b>14</b> overlaps a portion of the instance <b>56</b>″ of the selected cell A. Therefore, a polygon P<b>42</b> is added to the modified cell M<b>56</b> that represents the overlapping region of the polygon P<b>14</b> and the instance <b>56</b>″ of selected cell A. Finally, in the example shown, the top cell <b>50</b> has a polygon P<b>18</b> having a portion that overlaps a portion of the instance <b>56</b>″ of the selected cell A and the instance <b>56</b>′″ of selected cell A. Therefore, a polygon P<b>46</b> is added to the modified cell M<b>56</b> that represents the area of overlap of the polygon P<b>18</b> and the cell <b>56</b>″ as well as a polygon P<b>44</b> that represents the overlap of the polygon P<b>18</b> with the cell <b>56</b>′″. It should be noted that the additional polygons added to the modified cell M<b>56</b> are placed at the same relative location where they overlap the corresponding instances of the selected cell in the IC layout.

0044Although the present embodiment of the invention limits the modification of cells to the addition of polygons from overlapping cells, in some instances it may be desirable to compensate for other interactions, such as cells having “extents” or areas that overlap but have no overlapping polygons. For example, as shown in <figref idref="DRAWINGS">FIG. 3A</figref>, the extent of selected cell C <b>54</b> overlaps the instances <b>56</b>″ and the <b>56</b>′″ of cell A. Therefore, a modified cell M<b>54</b> as shown in <figref idref="DRAWINGS">FIG. 5C</figref> can be created having cutaway areas <b>60</b>, <b>62</b> that remove the areas that overlap with the other cells in the IC layout.

0045Once the selected cells have been modified to compensate for the interactions of other cells, one or more additional or remainder cells is created. As shown in <figref idref="DRAWINGS">FIG. 5A</figref>, the purpose of the one or more remainder cells <b>64</b> is to create structures on the mask that would not be created by the writing of the selected cells A and C. In <figref idref="DRAWINGS">FIG. 5A</figref>, the remainder cell includes polygons P<b>14</b> and P<b>18</b> to create structures not created by the selected cells A and C.

0046Because each of the selected cells may have been modified to compensate for interactions with other cells in the IC layout, the one or more additional or remainder cells are typically modified to prevent the formation of extraneous structures on the mask. As shown in <figref idref="DRAWINGS">FIG. 5D</figref>, a modified remainder cell M<b>64</b> is shown. The modified remainder has polygons that will create structures on the mask that are not created by the writing of the selected cells as well as areas that will prevent the creation of extraneous structures that would be created by the writing of the modified cells on the mask.

0047As can be seen by viewing the modified remainder cell M<b>64</b> in <figref idref="DRAWINGS">FIG. 5D</figref>, cell M<b>64</b> generally includes large blocks that cover the regions in which the selected cells are written. In addition, the modified remainder cell M<b>64</b> has a number of clear areas that prevent the formation of structures caused by the writing of the modified cells. For example, the modified remainder cell M<b>64</b> includes an area P<b>56</b> that prevents the formation of a structure on the mask that would be caused by writing the polygon P<b>42</b> in the modified cell A M<b>56</b> (<figref idref="DRAWINGS">FIG. 5B</figref>) at certain locations on the mask. Similarly, the modified cell M<b>64</b> includes a region P<b>54</b> that prevents the formation of structure on the mask that would caused by writing the polygon P<b>44</b> in the modified cell M<b>56</b> at certain locations on the mask.

0048Although the areas P<b>56</b>, P<b>54</b>, P<b>60</b>, P<b>62</b>, etc., are shown as clear areas, it will be appreciated that the modified remainder cell could be inverted such that the modified cell includes blocked areas where it is desired to prevent the formation of a feature on the mask and open areas where it is desired to produce a structure.

0049The following is a pseudo-code listing of the software command that create the modified cells and the one or more remainder cells using the Calibre™ program described above. However, it will be appreciated that many other computer programs could be written to implement the logic of the present invention.

0050<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0" pgwide="1"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>Inputs:</entry></row><row><entry /><entry>-------</entry></row><row><entry /><entry>geometryLayer original hierarchical geometry set</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="49pt" align="left" /><colspec colname="2" colwidth="196pt" align="left" /><tbody valign="top"><row><entry /><entry>coverCells</entry><entry>list of cover cells.</entry></row><row><entry /><entry>transforms</entry><entry>lists of required transforms, one for each cover cell</entry></row><row><entry /><entry>Algorithm:</entry></row><row><entry /><entry>----------</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="84pt" align="left" /><colspec colname="2" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>AllocateLayer(blockLayer);</entry><entry>// A temporary container (“layer”) for hierarchical</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="98pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>// geometry storage.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>// Modify and fracture each cover cell, and accumulate the hierarchical block layer.</entry></row><row><entry /><entry>for each (coverCell) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>// Accumulate the blocking geometry in the hierarchical set “blockLayer”.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>// Definitions:</entry></row><row><entry /><entry>// EXTENT: Smallest rectangle that covers all cell contents.</entry></row><row><entry /><entry>// OVERLAP_AREA: Area in a cell that is overlapped by placements of cells</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="259pt" align="left" /><tbody valign="top"><row><entry>anywhere</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>in the hierarchy</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>// HIER_OR: A hierarchical OR operation, as found in any DRC tool.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>blockRegion1 = EXTENT(coverCell) NOT OVERLAP_AREA(coverCell);</entry></row><row><entry /><entry>blockRegion2 = GEOMETRY(coverCell and descendants) AND</entry></row><row><entry /><entry>OVERLAP_AREA(coverCell);</entry></row><row><entry /><entry>blockRegion = blockRegion1 OR blockRegion2</entry></row><row><entry /><entry>add (blockRegion) to (blockLayer);</entry></row><row><entry /><entry>// Do a hierarchical OR operation to get the total fracture data for this cell.</entry></row><row><entry /><entry>AllocateLayer(fractureLayer);</entry></row><row><entry /><entry>fractureLayer = OVERLAP_AREA(coverCell) HIER_OR geometryLayer;</entry></row><row><entry /><entry>for each (transform) { // Fracture cell once per required transform.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry /><entry>Fracture(fractureLayer, coverCell, transform);</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="231pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="245pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>// Compute and fracture the remainder set.</entry></row><row><entry /><entry>AllocateLayer(remainderLayer);</entry></row><row><entry /><entry>remainderLayer = blockLayer HIER_OR geometryLayer;</entry></row><row><entry /><entry>Fracture(remainderLayer, topCell, identityTransform);</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0051The selection of cells for modification and the creation of the modified cells and the remainder cells can also be improved by running the computations using parallel processing, either with a computer with multiple processors (i.e., multithreading) or using a network of computers (distributed processing).

0052To produce the mask, a jobdeck file is created that describes the structure location and orientation of the selected, modified cells, as well as provides certain mask writing tool control parameters (such as address unit, beam and dose parameters, etc.) to be used with each file specified by the jobdeck. In addition, the jobdeck includes a description of the location and orientation of the one or more of modified remainder cells that are typically written over the entire area of the layout, along with the appropriate mask writing tool control parameters. The information in the jobdeck is then transmitted to the mask writing tool and the mask writing tool then writes the selected, modified cells at the locations indicated. In addition, the mask writing tool writes the one or more modified remainder cells. The order in which the cells are written is unimportant. For example, the one or more modified remainder cells may be written first, followed by writing the modified selected cells or vice versa.

0053In some instances, the orientation of the modified cells varies in the IC layout data. For example, as shown in <figref idref="DRAWINGS">FIG. 3A</figref>, the instances <b>56</b>′ and <b>56</b>′″ of cell A are the same with the exception that the cell <b>56</b>′″ is rotated 90° clockwise with respect to the cell <b>56</b>′. If the mask writing tool is sophisticated, then the jobdeck can contain a description of the modified cell that corresponds to the cell <b>56</b>′ and an indication of where the modified cell should be written on the mask with an instruction to rotate the modified cell by 90° in order to write a cell that corresponds to the rotated cell <b>56</b>′″. However, some mask writing tools are only capable of limited transformations. Therefore, prior to creating the jobdeck, the computer may need to determine what transformations the mask writing tool is capable of making and create a new modified cell that the mask writing tool is capable of writing directly or transforming in order to write in a way that corresponds to the orientation of the selected cell at a particular position on the IC mask.

0054By only transmitting the descriptions of the modified cells and the one or more modified remainder cells as well as a jobdeck specifying where and how these should be written, the amount of data that must be transmitted to the mask writing tool can be significantly reduced. By transmitting less data, the time required for the mask writing tool to receive the data is significantly reduced and the chance that an error will occur during transmission is likewise similarly reduced. The mask writing tool achieves a better utilization when the time it takes to transfer data to the writer is the same or less than the time it takes the mask writing tool to expose that data on the mask.

0055While the preferred embodiment of the invention has been illustrated and described, it will be appreciated that various changes can be made therein without departing from the spirit and scope of the invention. For example, one may provide for imperfect overlay alignment of the mask writing machine. If the machine is unable to exactly line up the modified selected cells with the one or more modified remainder cells, gaps may appear where the remainder geometry abuts geometry in the selected cells. This may be avoided by identifying such abutting edges in the remainder cell, and expanding them slightly towards the abutting geometry in the selected cell. Or, a different cost function could be utilized based on, for example, the density of the data contained in a cell or a fixed cell area threshold. The scope of the invention is therefore to be determined from the following claims and equivalents thereto.