Double patterning aware routing without stitching

Abstract

An approach is provided in which an enhanced routing module creates connection objects on a double patterning layout that are correct-by-construction and do not require a semiconductor fabrication stitching process. The enhanced routing module efficiently tracks accumulated mask selection constraints, during maze expansion, when the enhanced routing module traverses possible connection routes from a source grid point to a target grid point. In turn, the enhanced routing module avoids grid points that impose mask selection constraints that are incompatible with existing mask selection constraints of the possible connection routes. As a result, a connection object created by any one of the possible connection routes can be assigned to a specific mask, thus avoiding stitching process requirements from a semiconductor fabrication facility.

The invention claimed is: 
     
       1. A method comprising:
 retrieving, from a storage area by one or more processors, a design layout that includes a plurality of grid points corresponding to a plurality of masks utilized to generate one physical layer on a semiconductor wafer; and 
 creating, by one or more of the processors, a connection object on the design layout by identifying a series of grid points from the plurality of grid points, wherein identification of each of the grid points included in the series of grid points ensures that the connection object is constrained to be assigned to one of the plurality of masks. 
 
     
     
       2. The method of  claim 1  wherein the series of grid points comprises a possible connection route, the method further comprising:
 selecting a first grid point assigned to the possible connection route and a second grid point not assigned to the possible connection route, the first grid point and the second grid point included in the plurality of grid points; and 
 assigning the second grid point to the possible connection route in response to determining that combining one or more first mask selection constraints corresponding to the first grid point with one or more second mask selection constraints corresponding to the second grid point allows an assignment of at least one of the plurality of masks to be permitted to the possible connection route. 
 
     
     
       3. The method of  claim 2  further comprising:
 determining whether one or more first object group identifiers included in the one or more first mask selection constraints matches one or more second object group identifiers included in the one or more second mask selection constraints, the one or more first object group identifiers corresponding to a first set of objects and the one or more second object group identifiers corresponding to a second set of objects; and 
 permitting the assignment to the possible connection route of at least one of the plurality of masks in response to determining that the one or more first object group identifiers fails to match the one or more second object group identifiers. 
 
     
     
       4. The method of  claim 3  wherein, in response to determining that at least one of the one or more first object group identifiers matches at least one of the one or more second object group identifier, the method further comprises:
 determining whether a first mask assignment identifier corresponding to the matched first object group identifier matches a second mask assignment identifier corresponding to the matched second object group identifier, wherein the first mask assignment identifier identifies one of the plurality of masks and the second mask assignment identifier identifies one of the plurality of masks; and 
 permitting the assignment to the possible connection route of at least one of the plurality of masks in response to determining that the first mask assignment identifier matches the second mask assignment identifier. 
 
     
     
       5. The method of  claim 4  further comprising:
 avoiding the second grid point during generation of the possible connection route in response to determining that the first mask assignment identifier fails to match the second mask assignment identifier. 
 
     
     
       6. The method of  claim 2  further comprising:
 creating a plurality of possible connection routes between a source grid point and a target grid point, the possible connection route included in the plurality of possible connection routes; 
 generating a connection cost of each of the plurality of possible connection routes, resulting in a plurality of connection costs, wherein the connection cost of the possible connection route corresponds to a distance between the source grid point and the target grid point and is based upon at least the one or more first mask selection constraints; 
 determining that the possible connection route has a lowest connection cost out of the plurality of connection costs; and 
 back tracking the possible connection route from the target grid point to the source grid point in response to determining that the possible connection route has the lowest connection cost out of the plurality of connection costs, wherein the connection route is created in response to the back tracking of the possible connection route. 
 
     
     
       7. The method of  claim 6  wherein the connection object corresponds to a first object group and a second object group, wherein the first object group includes a plurality of first objects and the second object group includes a plurality of second objects, the method further comprising:
 combining the plurality first objects, the plurality of second objects, and the connection object into a single object group in response to the back tracking of the possible connection route. 
 
     
     
       8. The method of  claim 7  further comprising:
 changing a mask assignment identifier of each of the plurality of second objects in response to combining the plurality first objects, the plurality of second objects, and the connection object into the single object group. 
 
     
     
       9. The method of  claim 2  wherein the one or more first mask selection constraints and the one or more second mask selection constraints are included in a set of constraint vectors, the method further comprising:
 selecting a third grid point not assigned to the possible connection route; 
 determining that the third grid point is located on a different plurality of grid points corresponding to a different mask utilized to generate a different physical layer on the semiconductor wafer; 
 storing the first mask selection constraints and the second mask selection constraints in a storage area; 
 resetting the set of constraint vectors, wherein the resetting removes the first mask selection constraints and the second mask selection constraints; 
 including one or more third mask selection constraints corresponding to the third grid point in the reset set of constraint vectors; and 
 assigning the third grid point to the possible connection route. 
 
     
     
       10. The method of  claim 9  further comprising:
 selecting a fourth grid point not assigned to the connection route; 
 determining that the fourth grid point is located on the plurality of grid points; 
 retrieving the one or more first mask selection constraints and the one or more second mask selection constraints from the storage area in response to determining that the fourth grid point is located on the plurality of grid points; 
 comparing one or more fourth mask selection constraints corresponding to the fourth grid point to the retrieved one or more first mask selection constraints and the retrieved one or more second mask selection constraints; and 
 assigning the fourth grid point to the connection route based upon a comparison result of the comparing. 
 
     
     
       11. The method of  claim 1  wherein the design layout is devoid of a semiconductor manufacturing stitching requirement to connect one or more first physical objects generated from a first one of the plurality of masks with one or more second physical objects generated from a second one of the plurality of masks. 
     
     
       12. An information handling system comprising:
 one or more processors; 
 one or more memories accessible by at least one of the processors; 
 a design layout tool, executable by the one or more processors, that retrieves, from one of the one or more memories, a design layout that includes a plurality of grid points corresponding to a plurality of masks utilized to generate one physical layer on a semiconductor wafer; and 
 an enhanced routing module included in the design layout tool that creates a connection object on the design layout by identifying a series of grid points from the plurality of grid points, wherein identification of each of the grid points included in the series of grid points ensures that the connection object is constrained to be assigned to one of the plurality of masks. 
 
     
     
       13. The information handling system of  claim 12  wherein the series of grid points comprise a possible connection route, the information handling system further comprising:
 selection logic included in the enhanced routing module that selects a first grid point assigned to the possible connection route and a second grid point not assigned to the possible connection route, the first grid point and the second grid point included in the plurality of grid points; and 
 assignment logic included in the enhanced routing module that assigns the second grid point to the possible connection route in response to determining that combining one or more first mask selection constraints corresponding to the first grid point with one or more second mask selection constraints corresponding to the second grid point allows an assignment of at least one of the plurality of masks to be permitted to the possible connection route. 
 
     
     
       14. The information handling system of  claim 13  further comprising:
 determination logic included in the enhanced routing module that determines whether one or more first object group identifiers included in the one or more first mask selection constraints matches one or more second object group identifiers included in the one or more second mask selection constraints, the one or more first object group identifiers corresponding to a first set of objects and the one or more second object group identifiers corresponding to a second set of objects; 
 analysis logic included in the enhanced routing module that permits the assignment to the possible connection route of at least one of the plurality of masks in response to the determination logic determining that the one or more first object group identifiers fails to match the one or more second object group identifiers; and 
 the analysis logic that, in response to the determination logic determining that at least one of the one or more first object group identifiers matches at least one of the one or more second object group identifier:
 determines whether a first mask assignment identifier corresponding to the matched first object group identifier matches a second mask assignment identifier corresponding to the matched second object group identifier, 
 wherein the first mask assignment identifier identifies one of the plurality of masks and the second mask assignment identifier identifies one of the plurality of masks; and 
 permits the assignment to the possible connection route of at least one of the plurality of masks in response to determining that the first mask assignment identifier matches the second mask assignment identifier. 
 
 
     
     
       15. The information handling system of  claim 14  further comprising:
 the enhanced routing module that avoids the second grid point during generation of the possible connection route in response to determining that the first mask assignment identifier fails to match the second mask assignment identifier. 
 
     
     
       16. A computer program product stored in a computer readable storage device, comprising computer program code that, when executed by an information handling system, causes the information handling system to perform actions comprising:
 retrieving a design layout that includes a plurality of grid points corresponding to a plurality of masks utilized to generate one physical layer on a semiconductor wafer; and 
 creating a connection object on the design layout by identifying a series of grid points from the plurality of grid points, wherein identification of each of the grid points included in the series of grid points ensures that the connection object is constrained to be assigned to one of the plurality of masks. 
 
     
     
       17. The computer program product of  claim 16  wherein the series of grid points comprise a possible connection route, and wherein the computer readable storage device stores additional instructions that, when executed by the information handling system, cause the information handling system to perform additional actions comprising:
 selecting a first grid point assigned to the possible connection route and a second grid point not assigned to the possible connection route, the first grid point and the second grid point included in the plurality of grid points; and 
 assigning the second grid point to the possible connection route in response to determining that combining one or more first mask selection constraints corresponding to the first grid point with one or more second mask selection constraints corresponding to the second grid point allows an assignment of at least one of the plurality of masks to be permitted to the possible connection route. 
 
     
     
       18. The computer program product of  claim 17  wherein the computer readable storage device stores additional instructions that, when executed by the information handling system, cause the information handling system to perform additional actions comprising:
 determining whether one or more first object group identifiers included in the one or more first mask selection constraints matches one or more second object group identifiers included in the one or more second mask selection constraints, the one or more first object group identifiers corresponding to a first set of objects and the one or more second object group identifiers corresponding to a second set of objects; 
 permitting the assignment to the possible connection route of at least one of the plurality of masks in response to determining that the one or more first object group identifiers fails to match the one or more second object group identifiers; and 
 in response to determining that at least one of the one or more first object group identifiers matches at least one of the one or more second object group identifier:
 determining whether a first mask assignment identifier corresponding to the matched first object group identifier matches a second mask assignment identifier corresponding to the matched second object group identifier, wherein the first mask assignment identifier identifies one of the plurality of masks and the second mask assignment identifier identifies one of the plurality of masks; and 
 permitting the assignment to the possible connection route of at least one of the plurality of masks in response to determining that the first mask assignment identifier matches the second mask assignment identifier. 
 
 
     
     
       19. The computer program product of  claim 18  wherein the computer readable storage device stores additional instructions that, when executed by the information handling system, cause the information handling system to perform additional actions comprising:
 avoiding the second grid point during generation of the possible connection route in response to determining that the first mask assignment identifier fails to match the second mask assignment identifier. 
 
     
     
       20. The computer program product of  claim 16  wherein the connection object corresponds to a first object group and a second object group, wherein the first object group includes a plurality of first objects and the second object group includes a plurality of second objects, and wherein the computer readable storage device stores additional instructions that, when executed by the information handling system, cause the information handling system to perform additional actions comprising:
 combining the plurality first objects, the plurality of second objects, and the connection object into a single object group in response to back tracking the possible connection route; and 
 changing a mask assignment identifier of each of the plurality of second objects in response to combining the plurality first objects, the plurality of second objects, and the connection object into the single object group.