Constructing fill shapes for double-patterning technology

A computer system operative to:

• receive a design, characterized by a double patterning layer, in a memory of the computer when the computer is invoked to construct the design, wherein the design includes a plurality of net shapes each previously routed in accordance with a netlist of the design;
• generate a plurality of fill shapes along a plurality of tracks associated with the plurality of net shapes, wherein the plurality of fill shapes and the plurality of net shapes are decomposable into two colors in accordance with a spacing constraint of the double patterning layer, wherein the plurality of fill shapes are not associated with the netlist of the design, wherein the plurality of fill shapes are present in at least one mask generated from the design when the at least one mask is prepared;
• decompose the plurality of net shapes into the two colors in accordance with a graph;
• surround each decomposed net shape with a blocking region associated with a color of the two colors that corresponds to the color of the decomposed net shape to form a plurality of blocking regions;
• and
• construct the plurality of fill shapes in accordance with the plurality of blocking regions.

A non-transitory computer-readable storage medium comprising instructions, which when executed by a computer, cause the computer to:

• receive a design, characterized by a double patterning layer, in a memory of the computer when the computer is invoked to construct the design, wherein the design includes a plurality of net shapes each previously routed in accordance with a netlist of the design;
• generate a plurality of fill shapes along a plurality of tracks associated with the plurality of net shapes, wherein the plurality of fill shapes and the plurality of net shapes are decomposable into two colors in accordance with a spacing constraint of the double patterning layer, wherein the plurality of fill shapes are not associated with the netlist of the design, wherein the plurality of fill shapes are present in at least one mask generated from the design when the at least one mask is prepared;
• decompose the plurality of net shapes into the two colors in accordance with a graph;
• surround each decomposed net shape with a blocking region associated with a color of the two colors that corresponds to the color of the decomposed net shape to form a plurality of blocking regions;
• and
• construct the plurality of fill shapes in accordance with the plurality of blocking regions.