Patent Number: 
Section: description

Branching Division Several embodiments of methods, according to the invention, for calculating cumulative exposure dose are set forth below. As a preface, the xe2x80x9cbranching divisionxe2x80x9d of regions, used in calculating cumulative exposure dose, is described first, referring first to FIG. 1. Branching division of a region according to the invention yields a xe2x80x9cbranching structurexe2x80x9d of the region as used in various embodiments described below. FIG. 1 schematically depicts a region of a reticle pattern. The region includes multiple pattern elements (not shown) and is the subject of a calculation performed to determine the cumulative dose of exposure energy to be received by the region. The results of such a calculation will be used in configuring the pattern elements, as defined in the region on the reticle, in a manner that decreases the proximity effect experienced when the region is exposed onto the substrate. The region shown in FIG. 1 is divided into eight columns and eight rows, yielding a total of 64 subregions. Each subregion has a unique identifying number 1-64, respectively. In each subregion 1-64, the number in parentheses denotes the respective number of pattern elements contained in the subregion. As a first example, when performing a branching division, the region is divided equally, horizontally and vertically, into four equally sized portions (i.e., divided into two columns and two rows). Each portion is divided further, horizontally and vertically, (according to certain rules as discussed below) into four smaller equally sized portions, and so on. As a second example, a region is divided into nine equally sized portions (i.e., divided equally horizontally and vertically to form three columns and three rows), and each portion is divided further (according to certain design rules) into nine smaller equally sized portions, and so on. As a third example, a region can be divided initially into sixteen equally sized portions (i.e., divided equally horizontally and vertical to produce four columns and four rows) or twenty-five equally sized portions (i.e., divided equally horizontally and vertically to produce five columns and five rows), and so on; however, these larger numbers of divisions quickly result in a large number of subregions that usually are too small and impractical. Also, when making a division, the number of vertical divisions and the number of horizontal divisions need not be always identical. For example, if it is known in advance that the region includes many vertically long pattern elements or many horizontally long pattern elements, a good result may result from changing the number of vertical or horizontal divisions accordingly. In FIG. 1, division of a region or portion thereof is performed until the number of pattern elements included in the resulting subregions is one or less (i.e., 1 or 0). Initially, the number of pattern elements in the entire region (the entire region is referred to as xe2x80x9clevel 1xe2x80x9d) is greater than one. Hence, the entire level-1 region is divided into four xe2x80x9clevel-2xe2x80x9d subregions consisting of, respectively, subregions 1-16, 17-32, 33-48, 49-64. Since the number of pattern elements in each of the level-2 subregions is greater than one, each level-2 subregion is further divided into four xe2x80x9clevel-3xe2x80x9d subregions. The number of pattern elements in the level-3 subregion consisting of subregions 9-12 and in the level-3 subregion consisting of subregions 37-40 is 0. As a result, further division of these level-3 subregions is not performed. Also, for example, the number of pattern elements in the level-3 subregion consisting of subregions 25-28 and in the level-3 subregion consisting of subregions 41-44 is 1. Consequently, these level-3 subregions are not further divided. Level-3 subregions having more than one element are divided further to produce respective sets of four xe2x80x9clevel-4xe2x80x9d subregions. At level 4, the number of pattern elements in each of the subregions is 1 or 0 in this example, so no further subdivision is performed. The scheme of branching division described above is diagrammed in the branching structure shown in FIG. 2. At each level shown in FIG. 2, the subregions included in each group are denoted by number. The numbers in parentheses denote the number of pattern elements included in each region or subregion at each level. In FIG. 2, subregions containing zero pattern elements do not affect the calculation, so further denotation and description of these xe2x80x9czero-elementxe2x80x9d subregions are not provided. In FIG. 1, branching division of a region alternatively can be performed until the number of pattern elements included in a resulting subregion is, for example, less than or equal to 2. First, the number of pattern elements included in the entire region (at level 1) is greater than 2, so the entire region is divided (equally horizontally and vertically) into four equally sized level-2 subregions consisting of subregions 1-16, 17-32, 33-48, and 49-64, respectively. The number of pattern elements included in each of the level-2 subregions is greater than 2 in each case, so each level-2 subregion is further divided into four equally sized level-3 subregions. The number of pattern elements in each of certain level-3 subregions (i.e., the subregion consisting of subregions 9-12 and the subregion consisting of subregions 37-40) is zero; and the number of pattern elements in each of certain other level-3 subregions (i.e., the subregion consisting of subregions 25-28 and the subregion consisting of subregions 41-44) is 1. Since the number of pattern elements in each of these level-3 subregions is two or less, further division of these level-3 subregions is not performed. Similarly, the number of pattern elements in each of certain other level-3 subregions (e.g., the subregion consisting of subregions 5-8, the subregion consisting of subregions 17-20, and the subregion consisting of subregions 53-56) is 2. Hence, these level-3 subregions also are not further subdivided. But, other level-3 subregions (e.g., the subregion consisting of subregions 13-16) have more than two elements each. Hence, each of these level-3 subregions is divided further into four equally sized subregions (level 4). At level 4 the number of pattern elements included in each subregion thus produced is either 1 or 0, so further subdivision is not performed. The results of this branching division are shown in FIG. 3. At each level shown in FIG. 3, the level-4 subregions included in each lower-order subregion are denoted by number. The numbers in parentheses denote the number of pattern elements included in the respective subregion at each level. In FIG. 3, subregions including no pattern elements do not affect the calculation, so further denotation and description of these xe2x80x9czero-elementxe2x80x9d portions are not provided. In view of the branching-division schemes shown in FIGS. 1-3, the first representative embodiment is described with reference to FIGS. 4 and 5. FIG. 4 depicts an exemplary level-1 region of a pattern defining pattern elements that can be used to calculate a cumulative dose of exposure energy for the region. The point denoted xe2x80x9c10xe2x80x9d is a location (xe2x80x9cevaluation pointxe2x80x9d) at which a cumulative exposure dose is calculated. (The point 10 corresponds, for example, to any of the points A1-AN in FIG. 20(c).) The reference numeral xe2x80x9c11xe2x80x9d denotes a side dimension of the level-1 region (and also is used herein to denote the level-1 region itself). Items 12-15 are respective level-2 subregions produced by dividing the region 11 (equally both horizontally and vertically) into four equally sized portions. The reference numerals 16-19 denote four level-3 subregions, respectively, produced by dividing the level-2 subregion 15 equally horizontally and vertically into four equally sized portions. Items F1-F4 are respective pattern elements in the region. FIG. 5 is a flowchart of a process for calculating (determining) a branching structure according to this representative embodiment. In the description, the exemplary pattern region is assumed to contain more than one pattern element. In this example, the region is divided evenly both vertically and horizontally to produce four equally sized lower-level subregions. If the number of pattern elements within a subregion is xe2x89xa61, then further subdivision of the respective subregion is not performed. In the figure, D is the distance between the center of a subject subregion (the center serving in this example as a xe2x80x9creference pointxe2x80x9d for the subregion) and the evaluation point 10, and L is the length of a side of the subregion. For the subregion, if the ratio D/L exceeds a threshold value xcfx86, then further subdivision of the respective subregion is not performed regardless of the number of pattern elements included in the subject subregion, and the pattern element(s) present in the subject subregion are converted into a respective representative figure. The threshold value xcfx86 normally is determined experimentally, taking into account the required accuracy with which cumulative exposure dose is to be calculated and the desired calculation time. The xe2x80x9crepresentative figurexe2x80x9d for a given subregion is located at the centroid of pattern element(s) in the subject subregion. The representative figure includes a weighted factor of the total area of the pattern element(s) present in the subregion. The weighted factor is a compensation factor that takes into account the fact that the representative figure is an approximation of reality, even if the representative figure is situated at the centroid. The weighted factor is applied to the contribution by the element(s) to cumulative exposure dose in the subregion. The representative figure can have any of various profiles. Also, there need not be only one representative figure for a given subregion. Furthermore, a subject subregion can be subdivided into sub-subregions, with a respective representative figure created for each sub-subregion. Referring further to FIG. 5, in step S01 the cumulative dose of exposure energy in the subject region is initialized to 0. Further aspects of FIG. 5 are described in the context of FIG. 4. In step S02, the length L of a side of the region 11 is determined (wherein L is a representative size parameter of the region). In step S03 the distance D is determined between the center of the region 11 (the center serving as a xe2x80x9creference pointxe2x80x9d) and the selected evaluation point 10 (at which cumulative exposure dose is calculated). In step S04 a decision is made on whether D/L exceeds a threshold value xcfx86. If D/L does not exceed xcfx86, then the process proceeds to step S07 at which a decision is made on whether the number of pattern elements in the region 11 is 0. If the number of pattern elements in the region 11 is greater than 0, then the process proceeds to step S08 at which a decision is made on whether the number of pattern elements in the region 11 is equal to 1. If the number of pattern elements in the region 11 is greater than 1, then the process proceeds to step S10 at which the region 11 is divided equally into four subregions 12-15. In step S11, a number k indicating the subregion number is initialized to 1, and the process proceeds to step S12. In step S12 a calculation starting with step S01 is performed for the subregions obtained. In step S13 k is incremented by 1. In step S14, if k is less than or equal to 4, then the process returns to step S12 and a branching structure is determined for the next subregion. If k is greater than 4, then calculation ends for all the subregions, thereby completing processing for the region. In the example shown in FIG. 4, for k=1 (level-2 subregion 12), D/L exceeds the threshold value xcfx86. As a result, for this subregion, the process proceeds to steps S05 and S06, in which a representative figure is created from the pattern elements F1, F2. The contribution of the representative figure to cumulative exposure dose is calculated, and the sum is added to the cumulative exposure dose for the region. In step S15 the value E is entered and the process xe2x80x9creturnsxe2x80x9d to the last division in the branching structure. This means that, for k=1, no further subdivisions or energy calculations are performed. Consequently, the process proceeds to step S 13 during which the value of k becomes 2, and the level-2 subregion 13 now is considered. Step S12 is performed for the subregion 13. That is, with k=2, the process starting at step S01 is performed for the subregion 13. For k=2, D/L exceeds the threshold value xcfx86 in the subregion 13. As a result, the process proceeds to steps S05 and S06. However, because no pattern elements are present in the subregion 13, a calculation and adding of the respective exposure-dose for this subregion to the overall exposure dose for the region 11 do not occur. Hence, k is incremented to k=3. For k=3 (level-2 subregion 14), D/L does not exceed the threshold value xcfx86, and the process proceeds to step S07. However, because no pattern elements are present in the subregion 14, the process proceeds to step S15. For k=4 (level-2 subregion 15), D/L is less than the threshold value xcfx86, and the process proceeds to step S07. But, because the number of pattern elements in the subregion 15 is greater than 0, the process proceeds to step S08. Since the number of pattern elements in the subregion 15 is greater than 1, in step S10 the subregion is divided into four level-3 sub-subregions 16-19. The process starting with step S01 is performed for each of the four sub-subregions 16-19 from k=1 to k=4, respectively. For each of the four level-3 subregions, since D/Lxe2x89xa6xcfx86 for k=1 to k=4, the process proceeds to step S07. For k=1 (sub-subregion 16) and k=4 (sub-subregion 19), the number of pattern elements in each respective sub-subregion is 1. As a result, the process proceeds in each instance to step S09, in which the contribution of the pattern elements F3, F4, respectively, to cumulative exposure dose is added to the cumulative exposure dose for the region 11. These contributions to cumulative exposure dose can be calculated from the shape of the respective pattern elements using well-known methods. Alternatively, as described previously, the process can proceed to step S05, as indicated by the broken-line arrow in FIG. 5, in which, for each sub-subregion, the respective pattern element is converted into a representative figure, and the contribution of the representative figure to cumulative exposure dose is calculated. For each of k=2 (sub-subregion 17) and k=3 (sub-subregion 18), the number of pattern elements is 0, so the process proceeds from step S07 to step S15. To summarize the process, first the region 11 is divided into four level-2 subregions 12-15. The contribution of subregion 12 to cumulative exposure dose is calculated in steps S05 and S06 and added to the cumulative exposure dose for the region 11. Each of the subregions 13 and 14 has no pattern elements, so no exposure dose from these two subregions can be added to the cumulative exposure dose. The subregion 15 is divided into four sub-subregions (level-3 subregions) 16-19. The respective contributions to cumulative exposure dose from the sub-subregion 16 and the sub-subregion 19 are calculated in step S09 and added to the cumulative exposure dose for the region 11. Each of sub-subregions 17 and 18 has no pattern elements, so no exposure dose is contributed by these two sub-subregions to the cumulative exposure dose for the region 11. A calculation of exposure dose in the region 11 is made for each evaluation point 10 in the region 11. A flowchart of a process according to this embodiment is shown in FIG. 6. The basic concept of the FIG.-6 process is as in the FIG.-5 process, and has a similar end effect. The main difference between the two processes is that, in the FIG.-5 process, the decision as to whether D/Lxe2x89xa6xcfx86 is made before a decision on whether the number of pattern elements in a region or subregion is less than or equal to 1. In contrast, in the FIG.-6 process, this sequence of steps is reversed. Hence, both processes have similar end effects. Referring more specifically to FIG. 6 (and referring also to FIG. 4), in step S21 the cumulative exposure dose affecting the region is initialized to 0. In step S22, the length L of one side of the region (wherein L is a representative size parameter) is determined. In step S23 the distance D between the center of the region and the evaluation point 10 is determined. This portion of the process also can occur between step S25 and step S27, described later. In step S24, a decision is made on whether the number of pattern elements in the region is 0. If the number is 0, then the process proceeds to step S35, and no further processing occurs for the region. If the number is greater than 0, then the process proceeds to step S25, and a decision is made on whether the number of pattern elements in the region is 1. If the number is 1, then the process proceeds to step S26, and the exposure-dose contribution of the subject region is added to the cumulative exposure dose for the region 11. During this step, the exposure-dose contribution to the cumulative exposure dose can be calculated from the shape of the respective pattern element using well-known methods. Alternatively, as indicated by the broken-line arrow in FIG. 6, the process can proceed to step S28, described below, during which the respective pattern element is converted to a representative figure, and the contribution to cumulative exposure dose is calculated from the representative figure. If the number of pattern elements in the subject region is 2 or more, then the process proceeds to step S27, and a decision is made on whether D/Lxe2x89xa6xcfx86. If D/Lxe2x89xa6xcfx86, then the process proceeds to steps S28 and S29, and a representative figure is created from the pattern elements. The contribution of the representative figure to cumulative exposure dose is calculated and added to the cumulative dose of exposure energy for the region 11. In step S35 the value of E is entered, meaning that the process is complete with respect to the subject region or subregion. The process then xe2x80x9creturnsxe2x80x9d to the last division in the branching structure and proceeds again. If D/Lxe2x89xa6xcfx86, then the process proceeds to step S30, and the region is divided into four equally sized subregions. Thereafter, steps S31 through S34 are the same as steps S11 through S14, respectively, in FIG. 5. In the embodiment of FIG. 6, branching division of a region and calculation of cumulative exposure dose are performed simultaneously. However, in this third representative embodiment, entry of the subject region (or subregion) into a branching structure for the region occurs first, followed by calculation of the cumulative exposure dose in the region (or subregion). The third representative embodiment is shown in FIG. 7. In step S41, a decision is made on whether the number of pattern elements in the subject region (or subregion) is 0. If the number is 0, then the process proceeds to step S49. Alternatively, the process can proceed to step S42, wherein the region (or subregion) is listed (xe2x80x9cregisteredxe2x80x9d) on a branching structure being created for the region, with the number of pattern elements set at 0 on the list. (Branching structures are created in a memory of a computer used to perform the steps of the process in a controllable manner.) However, in light of subsequent processing, it is more efficient not to register the region on a branching structure. I.e., not registering a region or subregion results in less calculation time. If the number is not zero, then in step S42 the region (or subregion) is registered on the branching structure, and the number of pattern elements included in the region is recorded. That is, as shown in FIG. 2, the subregions for each level and the number of pattern elements included in the respective subregions are registered on the branching structure. Then, in step S43, a decision is made on whether the number of pattern elements in the region (or subregion) is less than or equal to 1. If yes, then the process proceeds to step S49. If no, then the process proceeds to step S44, at which the subject region (or subregion) is divided (equally horizontally and vertically) into four equally sized subregions. Branching division according to step S46 is performed for each respective subregion produced in step S44. That is, the process starting with step S41 is performed for each of the respective subregions formed in step S44. By continuing this process for the entire region shown in FIG. 1, a branching structure such as that shown in FIG. 2 is created. (FIG. 2 shows a case in which regions with zero pattern elements are not registered on the branching structure. But, if regions with zero pattern elements were registered on the branching structure, then those elements would be included in the regions listed in FIG. 2.) As branching division of a region ends, calculation of a cumulative dose of exposure energy in the region begins. The calculations are performed by a process shown in FIG. 8, in which only regions (and subregions) containing pattern elements are regarded as registered in the branching structure. Calculations are performed only for those regions and subregions that are registered in the branching structure, thereby providing greater efficiency than conventional methods. In step S51 of FIG. 8, the cumulative dose of exposure energy affecting a region is initialized at 0. In step S52 the length L of one side of the region is determined (wherein L is a representative size parameter). In step S53 the distance D between the center of the region (as a respective reference point for the region) and the evaluation point in the region is selected. In step S54 a decision is made on whether D/L exceeds the threshold value xcfx86. If yes, then the process proceeds to steps S55 and S56, and a representative figure is created from the pattern element(s) in the region. The contribution of the representative figure to the cumulative exposure dose (energy) is calculated and added to the cumulative dose of exposure energy for the region. In step S60 the value of exposure dose (energy E) determined in a previous step is entered, indicating that processing in the respective region or subregion is complete. The process then returns to the last division in the branching structure and proceeds again, and so on until the entire region is completed. If D/Lxe2x89xa6xcfx86, then the process proceeds to step S57 in which a decision is made on whether the number of pattern elements in the subject region or subregion is 1. If the number is 1, then the process proceeds to step S59 in which the contribution to cumulative exposure dose from the subject pattern element is added to the cumulative dose of exposure energy for the region. (The contribution of a pattern element to cumulative exposure dose can be calculated from the shape of the subject pattern element using well-known methods.) As indicated by the broken-line arrow in FIG. 8, it alternatively is possible to proceed to step S55 and convert the subject pattern element to a representative figure, from which the respective contribution to cumulative exposure dose is calculated. If the number of pattern elements in the region is greater than 1, then the process proceeds to step S58 in which a branching structure is determined (xe2x80x9ccalculatedxe2x80x9d) for the next lower level from the subject region or subregion. That is, calculation (starting from step S51) is performed for all subregions registered at the next lower level. By continuing the process in this manner to the end, the cumulative dose of exposure energy is determined for the entire region with respect to a particular evaluation point. The process is repeated for each of the other evaluation points in the region. In the process shown in FIG. 8, the determination of whether D/Lxe2x89xa6xcfx86 is made before the decision on whether the subject region or subregion contains a single pattern element. Alternatively, the decision on whether the subject region or subregion contains a single pattern element can be made before a determination of whether D/Lxe2x89xa6xcfx86. In the latter instance, the sequence of process steps readily can be determined by applying the difference between FIGS. 6 and 7 to FIG. 8. This embodiment is directed to a method in which, for a given region, the determination of the branching structure and creation of representative figures are performed first, followed by a determination and summation of the respective contributions of the respective pattern elements and representative figures to cumulative exposure dose. FIG. 9 provides a process flowchart of this embodiment. In the first step, step S61, the length L of one side of the subject region (as a representative size parameter) is determined. In step S62 the distance D is determined between the center of the region (as a representative xe2x80x9creference pointxe2x80x9d for the region) and the selected evaluation point. In step S63 a decision is made on whether D/L exceeds the threshold value xcfx86. If D/L greater than xcfx86, then the process proceeds to step S64, in which a representative figure is created from the pattern elements in the region. Then, in step S73, the representative figure is returned (entered), thereby completing the process. If D/Lxe2x89xa6xcfx86, then the process proceeds to step S65, in which a decision is made on whether the number of pattern elements in the subject region (or subregion) is zero. If the number is zero, then the process proceeds to step S73 and processing for the particular region (or subregion) ends. If the subject region (or subregion) contains at least one element, then the process proceeds to step S66, in which a decision is made on whether the number of pattern elements in the region (or subregion) is 1. If the number is 1, then the process proceeds to step S67, in which the pattern element itself becomes the representative figure. Alternatively, as indicated by the broken-line arrow in FIG. 9, the process can proceed from step S66 to step S64, in which the pattern element is converted into a representative figure. If the number of pattern elements in the subject region (or subregion) is greater than 1, then the process proceeds to step S68, in which the subject region (or subregion) is divided (equally horizontally and vertically) into four equally sized subregions. The steps (S69 through S72) of determining a branching structure and creating a representative figure are performed for each of the four subregions. That is, the routine starting at step S61 is performed for each subregion. By continuing this process to its end, all representative figures are found for the subject region. Furthermore, in the process of FIG. 9, the decision on whether D/Lxe2x89xa6xcfx86 is made before making a decision on whether the number of pattern elements in the subject region is 1. Alternatively, it is possible to make the decision on whether there is one pattern element in the region before making the decision on whether D/Lxe2x89xa6xcfx86. In the latter instance, the sequence of process steps readily can be determined by applying the difference between FIGS. 6 and 7 to FIG. 9. After all representative figures are found in this manner, the contributions of the respective representative figures to the cumulative dose of exposure energy at the evaluation point are determined. The process is repeated for all other evaluation points in the region. In all of the foregoing embodiments, representative figures were created with reference to respective relationships of the various subregions of a region with the selected evaluation point in the region. It also is possible to divide the region in a branching manner and create representative figures without consideration of these relationships. In the latter instance, the respective relationships are referred to only when calculating the cumulative dose of exposure energy for the region. This embodiment is exemplary of such a scheme. A process according to this embodiment for dividing a region in a branching manner and creating representative figures in the subregions thus formed is shown in FIG. 10. In step S81, a decision is made on whether the number of pattern elements in the subject region (or subregion) is zero. If the number is zero, then the process proceeds to step S91 and further processing of the region (or subregion) ends. If the number is not zero, then in step 81 the subject region (or subregion) is registered on the branching structure being created for the region. Then, in step S83, a decision is made on whether the number of pattern elements in the subject region (or subregion) is one. If yes, then the process proceeds to step S84, in which the subject pattern element becomes the representative figure, or a specified representative figure is created from the subject pattern element. The process then proceeds to step S91 and further processing of the region (or subregion) ends. In step S83, if the number of pattern elements in the region (or subregion) is two or more, then the process proceeds to step S85, in which a representative figure is created for the subject region (or subregion). In step S86 the subject region (or subregion) is divided equally horizontally and vertically into four subregions at the next lower level (the subregions are equally sized). Branching division in this manner creates a respective portion of the branching structure for the region, and representative figures are created for each of the respective subregions in step S87 through step S90. That is, the process starting from step S81 is performed for each of the respective subregions. Performing this process to completion for all subregions of the region yields a branching structure as shown in FIG. 2, including representative figures corresponding to the respective subregions. This embodiment is directed to calculating cumulative dose of exposure energy using a branching structure and representative figures. The process flow is shown in FIG. 11. In the first step S101 the cumulative dose of exposure energy to the respective region is initialized at zero. In step S102 the length L of one side of the subject region (or subregion) is found, wherein L is a representative size parameter. In step S103 the distance D is found between the center of the region (or subregion) and the selected evaluation point for the region, wherein the center is a representative xe2x80x9creference pointxe2x80x9d for the region or subregion. In step S104 a decision is made on whether D/L exceeds the threshold value xcfx86. If D/L greater than xcfx86, then the process proceeds to step S105, in which the contribution of the representative figure(s) in the region or subregion to the cumulative dose of exposure energy (E) for the region is calculated. In step S108 the value of E is returned (entered), meaning that processing in the subject region (or subregion) is complete. If D/Lxe2x89xa6xcfx86, then the process proceeds to step S106, in which a decision is made on whether the number of pattern elements in the subject region (or subregion) is 1. If the number of pattern elements is 1, then the process proceeds to step S105, in which the contribution to cumulative exposure dose from the representative figure in the subject region (or subregion) is added to the cumulative exposure dose. In this step, the subject representative figure can be the corresponding pattern element itself. Alternatively, the pattern element can be converted into a representative figure having a specified shape according to step S84 in FIG. 10. If the number of pattern elements in the subject region (or subregion) is greater than 1, then the process proceeds to step S107, in which a branching structure is created for subregions at the next lower level from the subject region (or subregion). That is, the calculation is performed, starting with step S101, for all subregions one level down. By continuing this process to the end for all constituent subregions, the cumulative exposure dose at the selected evaluation point is determined for the subject region. (The process is repeated for all other evaluation points in the region.) Furthermore, in the process shown in FIG. 11, the decision on whether D/Lxe2x89xa6xcfx86 is made before the decision on whether there is one pattern element in the region (or subregion). Alternatively, the decision on whether there is one pattern element in the region (or subregion) can be made before the decision on whether D/Lxe2x89xa6xcfx86. In the latter instance, the sequence of process steps readily can be determined by applying the difference between FIGS. 6 and 7 to FIG. 11. In all of the embodiments discussed above, the decision to subdivide a region (or subregion) is made whenever D/L greater than xcfx86 or whenever the number of pattern elements included in the subject region (or subregion) is less than or equal to one. Alternatively, division of a region (or subregion) into subregions at the next lower level may end whenever D/L greater than xcfx86 or whenever the number of pattern elements included in the subject region (or subregion) is less than or equal to a specified number. The latter can be implemented readily by denoting step S08 (FIG. 5) as xe2x80x9cnumber of elements in the regionxe2x89xa6a specified numberxe2x80x9d, for example. In the latter instance, regions or subregions having a plurality of pattern elements remain, but the contribution to the cumulative exposure dose of the respective pattern elements can be calculated. For example, the representative figure in the region or subregion can be found via the broken-line route in FIG. 5. This embodiment is directed to an exemplary method for creating a representative figure. Referring to FIG. 12(a), a situation is considered in which a region 21 contains two pattern elements F5 and F6. The region 21 is square-shaped with side length 2. The element F5 is rectangularly shaped with a length of 2 units in the x-axis direction (horizontal direction in the plane of the page) and a width of 1 unit in the y-axis direction (vertical direction in the plane of the page). If the center of the region 21 is the selected evaluation point in the region 21, then the center of the element F5 is located at (xe2x88x921,1). The element F6 is square-shaped, with each side having a length of 1 unit. The center of the element F5 is located at (1,0). FIGS. 12(b)-12(f) show various respective ways in which the elements F5, F6 in the region 21 can be combined into a single representative figure in the region 21. Turning first to FIG. 12(b), the representative figure is a point located at the center of the region 21. Such a representative figure is applicable, for example, if the respective element is located remotely from the evaluation point. For evaluation purposes, the point has a xe2x80x9cweightxe2x80x9d of 3, which is the total of the areas of F5 and F6. I.e., even though the representative figure is a point, it still takes into consideration the area of the element(s) it represents. In this context, xe2x80x9cweightxe2x80x9d is essentially a factor used when calculating a respective contribution to cumulative exposure dose. Whether or not a point representative figure is or can be used also takes into account the required accuracy of the calculations and/or the calculation time. FIG. 12(c) is an exemplary square representative figure having a center located at the center of the region 21 and having an area of 3 (which is the total of the areas of the elements F5 and F6). FIG. 12(d) is an exemplary round representative figure having a center located at the center of the region 21 and having an area of 3 units (which is the total of the areas of the elements F5 and F6). FIGS. 12(b)-12(d) do not consider the net relative extensions in the x- and y-directions of the elements F5 and F6. Such a consideration is provided in FIG. 12(e), in which the representative figure is elliptical and horizontally extended. In the ellipse, the ratio of x-axis length to y-axis length is 3.5:2. The ellipse has an area of 3 units, which is the total of the areas of the elements F5 and F6. The axial ratio of the ellipse is derived from corresponding x- and y-dimensions of a rectangular figure, surrounding elements F5 and F6, having a length of 3.5 in the x-axis direction and a length 2 in the y-axis direction. FIG. 12(f) shows an exemplary rectangular representative figure of which the ratio of x-axis length to y-axis length is 3.5:2. The area of the rectangle is 3 units, which is the total of the areas of the elements F5 and F6. In FIGS. 12(a)-12(f), the locations of the respective centers of the representative figures are at the center of the region 21. Alternatively, the centers can be located at the center of the respective centroid of the pattern elements F5 and F6 in the region 21, thereby providing a more accurate representative figure. This is shown in FIGS. 13(a)-13(f). FIG. 13(a) shows the dispersion of pattern elements F5, F6 in the region 21. As can be seen, the pattern elements F5, F6 are distributed and sized exactly as in FIG. 12(a). The location of the centroid of elements F5 and F6 is located at (xe2x88x921/3,2/3), at which the center of the representative figure is located. FIGS. 13(b)-13(f) show exemplary representative figures corresponding to FIGS. 12(b)-12(f), respectively, but with respective centers situated at (xe2x88x921/3,2/3). In FIGS. 12(a)-12(f) and 13(a)-13(f), one representative figure was created in the region 21, incorporating multiple pattern elements F5, F6. It also is possible to create multiple representative figures in the region 21. In the latter case, for example, the region 21 is divided equally horizontally and vertically into four equally sized subregions, and a respective representative figure is created for each subregion. As discussed above, the number of divisions does not have to be equal horizontally and vertically. If many pattern elements have respective shapes that are long horizontally or long vertically, then the number of horizontal and vertical divisions can be modified accordingly. In the methods for dividing a region in a branching manner explained above, subregions distant from the selected evaluation point can be configured as large subregions, and subregions nearer to the evaluation point can be configured as small subregions. This is because the cumulative-dose effect of subregions more distant from the evaluation point is less than the effect of closer subregions. This allows the number of calculations to be minimized without significantly degrading the accuracy of the calculations. If a single large pattern element, having a complicated edge profile, is present in the subject region, then subdivision of the region ordinarily would not occur. In such a case, accuracy would not be affected adversely if exposure dose were calculated strictly according to the complex profile of the element, but the calculation time would be excessive. Alternatively, the complex pattern element can be replaced with a representative figure from which the exposure-dose calculation is performed. However, in a representative figure, the complex profile of the element essentially is ignored, and calculation accuracy is reduced undesirably. In such a situation, it is desirable to divide the single complex element into a core portion having a simple profile and multiple xe2x80x9csecondaryxe2x80x9d portions (including portions having a negative profile). With respect to the core portion, cumulative exposure dose can be calculated using conventional methods. I.e., because the profile of the core portion is simple, known rapid calculation methods can be used. With respect to the secondary portions, determination of a branching structure as described above can be performed. The cumulative exposure dose from the element is obtained by combining the results of the two calculations. FIGS. 14(a)-14(c) depict this situation. FIG. 14(a) depicts an actual exemplary pattern element F7 situated inside a region 22. Item 23 is the corresponding element actually to be transferred to the substrate. The pattern element F7 is divided into a relatively large core portion as shown in FIG. 14(b) and secondary portions as shown in FIG. 14(c). In FIG. 14(b) the core portion consists of five parts 24-28, wherein part 24 has a profile substantially the same as the element 23 to be transferred to the substrate, and parts 25-28 are corners. In FIG. 14(c) secondary portions with diagonal crosshatching are situated inside the pattern element F7 but outside the core portion. The secondary portions with horizontal-line shading are not situated inside the pattern element F7 but are situated inside the core portion. As used herein, secondary portions located within the core portion but outside the actual element 23 are referred to as having a xe2x80x9cnegativexe2x80x9d shape, i.e., having a negative area and thus making a negative contribution to cumulative exposure dose for the region 22. After dividing the pattern element in this manner, the contribution to cumulative exposure dose is calculated individually for each of the core parts 24-28 shown in FIG. 14(b). In practice, the profile of the core portion usually is simple, and the core portion usually consists of relatively few parts. As a result, calculating the contribution of the core parts to cumulative exposure dose of the selected evaluation point is relatively simple and can be performed using known methods. On the other hand, the contributions to cumulative exposure dose for the secondary portions shown in FIG. 14(c) are calculated using a branching-structure determination according to the invention. When performing the calculation, secondary portions having a negative shape make negative contributions to centroid, area, and cumulative exposure dose. In any event, the individual contributions of the core portion and secondary portions to cumulative exposure dose are summed to yield the cumulative dose of exposure energy for the region. The pattern-element profile of FIG. 14(a) is simplified for explanation purposes. Typically, in actual practice, the number of core portions is relatively small, and the number of secondary portions is very large. Hence, the advantages of employing a method, according to the invention, for making a branching division of a region are substantial. The methods described above for calculating the cumulative dose of exposure energy for a region can be incorporated into a program executed by a computer, stored on a recording medium such as a CD, optical disk, ROM, etc., and suitably used when configuring the pattern on a reticle, mask, or the like. Whereas, in the foregoing, embodiments are explained in the context of calculating a cumulative dose of exposure energy, it will be understood that calculating a proximity effect obtained using a CPB microlithography apparatus also is a type of cumulative-exposure-dose calculation that can benefit using methods according to the invention. I.e., in the respective flowcharts of the various embodiments described herein, the term xe2x80x9ccumulative exposure dosexe2x80x9d (cumulative dose of exposure energy) can be replaced with xe2x80x9ccumulative exposure dose due to proximity effects.xe2x80x9d If a proximity effect at a point on a sensitive substrate, such as a wafer, is determined, then it is possible to determine a required altered shape of a reticle or mask, and to alter the shape of the reticle or mask, respectively, according to the determination. FIG. 15 is a flowchart of an exemplary microelectronic-device fabrication method to which methods according to the invention readily can be applied. The fabrication method comprises the main steps of wafer production (wafer preparation); reticle production (reticle preparation); wafer processing; device assembly, dicing, and making the devices operational; and device inspection. Each step usually comprises several sub-steps. Among these main steps, wafer processing is key to achieving the smallest feature sizes (critical dimensions), best inter-layer registration, and performance of the microelectronic devices. In the wafer-processing step, multiple circuit patterns are layered successively atop one another on the wafer, wherein the formation of each layer typically involves multiple sub-steps. Usually, many operative microelectronic devices (e.g., microprocessor chips or memory chips) are produced on each wafer. Typical wafer-processing steps include: (1) thin-film formation (by, e.g., CVD or sputtering) involving formation of a dielectric layer for electrical insulation or a metal layer for interconnections; (2) oxidation to oxidize the thin film or the surface of the wafer itself; (3) microlithography to form a resist pattern (as defined by a reticle) on the wafer for selective processing of the thin film or the substrate itself; (4) etching (e.g., dry etching) or analogous step to etch the thin film or wafer according to the resist pattern; (5) doping or impurity implantation to implant ions or impurities into the thin film or wafer; (6) resist stripping to remove the resist from the wafer; and (7) chip inspection. Wafer processing is repeated as required (typically many times) to fabricate the desired microelectronic devices on the wafer. FIG. 5 provides a flowchart of typical steps involved in microlithography, which is a principal step in wafer processing. The microlithography step typically includes: (1) a resist-coating step, wherein a suitable resist is coated on the wafer surface (which can include as circuit pattern formed in a previous wafer-processing step); (2) an exposure step, to expose the resist with the desired pattern and form a latent image of the pattern in the resist; (3) a development step, to develop the latent image in the exposed resist; and (4) an optional annealing step, to enhance the durability of the developed resist pattern. These wafer-production steps, reticle-production steps, wafer-processing steps, and microlithography steps are well known. Hence, additional description of these steps is unnecessary. In any event, the microlithography step employs a reticle or mask that is configured accurately and quickly using a method according to the invention. An important result is the manufacture of microelectronic devices having fine patterns that can be fabricated quickly and with high yield. Referring to FIG. 17, a cumulative dose of exposure energy was calculated for pattern elements in a region measuring 120 xcexcmxc3x97100 xcexcm, using the method described in the first representative embodiment (FIG. 5). Specifically, cumulative-exposure-dose calculations were performed for each of multiple evaluation points in pattern elements to be transferred to the sensitive substrate. Cumulative-exposure-dose calculations for corner portions of the elements (e.g., portions corresponding to parts 25-28 in FIG. 14) were calculated separately from respective core portions of the elements. The method of the first representative embodiment was applied to the remaining parts of the pattern elements. In performing the calculations, the value of xcfx86 was 1. For each pattern element, the respective representative figure was a single point situated at the centroid of the respective pattern element. Whenever a region of the reticle contained only a single pattern element, the contribution to cumulative exposure dose from that region was calculated directly without converting the element to a representative figure. As a comparative example, the conventional method of calculating the effect of moving segments in the region, as shown in FIG. 20, was applied. FIG. 18 is a plot comparing respective calculation times for the example and comparative example, as a function of the number of segments referred to in the comparative example. In the comparative example, although high calculation accuracy is obtained, calculation time increases steeply with increased number of segments. In the example, in contrast, the calculation time is comparatively shorter (i.e., the xe2x80x9cexamplexe2x80x9d curve exhibits substantially less slope than corresponding regions of the xe2x80x9ccomparative examplexe2x80x9d curve) without degrading accuracy more than a significant extent. FIG. 19 depicts exemplary distributions of values of cumulative exposure dose accompanying various differences in cumulative exposure dose calculated according to the embodiment versus cumulative exposure dose calculated according to the comparative example. The area shown in FIG. 19 includes the center element shown in FIG. 17 as well as the respective adjacent longitudinal edges of the elements located above and below the center element (note similarity of coordinates between FIG. 19 and the corresponding region of FIG. 17). At each coordinate shown in FIG. 19, exposure dose is calculated by conventional method (Dc) and the method according to this example (De). The difference (Dcxe2x88x92De) is divided by a value of exposure dose (Dm, calculated according to the conventional method) that defines the pattern-element boundary on the sensitive substrate (i.e., the energy value serving as a threshold above which the resist can be developed and below which the resist cannot be developed). The result of this calculation, obtained at each coordinate shown in FIG. 19, is a xe2x80x9ccalculation errorxe2x80x9d which is a percentage difference in dose of the example method compared to the conventional method. In FIG. 19, the non-shaded regions are where the calculation error is 0.0000 to 0.0005 percent. The various shaded regions depict different percentage differences as indicated, and represent areas where proximity effects most likely would occur. As can be discerned from the figure, the difference between these two calculation methods is less than 1% of the energy value sufficient to create a pattern-element boundary in all regions of the substrate. (A difference of 0.002 to 0.0025 currently is deemed acceptable.) Hence, this embodiment provides a calculation accuracy, for practical purposes, that is essentially the same as realized using conventional methods, but the calculations performed according to the example were performed in substantially less time. Whereas the invention has been described in connection with multiple representative embodiments, it will be understood that the invention is not limited to those embodiments. On the contrary, the invention is intended to encompass all modifications, alternatives, and equivalents as may be included within the spirit and scope of the invention, as defined by the appended claims.