Synthetic data for 2D pathfinding
View Patent ↗Synthetically built training sets that can be used for neural network-based routing are set forth. Training datasets constructed in accordance with the principles herein are very fast, and can be used to generate a large, robust training set by a suitable router.
1 . A synthetic dataset for pathfinding applications, the synthetic dataset configured to capture the similarities of a real circuit, comprising
routed circuits generated by a computer-executable program stored on a computer readable storage media, when executed, the computer program generating the routed circuits via steps comprising:
generating within a rectangular bitmap a large set of net routing, wherein each tile of the rectangular bitmap comprises at least one terminal or a net segment placed on a perimeter of the rectangular bitmap;
joining two or more rectangular bitmaps via two edge net segments to obtain a larger bitmap, wherein the larger bitmap comprises a valid grouping of routed nets with smaller bitmaps being rotated and flipped as needed;
determining whether the joined bitmaps are a valid grouping if it does not exceed a maximum layout resolution as provided by a target training resolution; and
using the valid grouping of joined bitmaps to produce the routed circuits;
a high resolution, complex obstacle-avoiding multi-pin routed circuit comprising the routed circuits.
2 . The synthetic dataset of claim 1 , wherein the synthetic dataset captures a variety of realistic routing characteristics allowing neural networks to be trained on this dataset.
3 . A machined learning (ML) based pathfinding system network for generating routes comprising:
a parallel processing system implemented by using a graphics processing unit (GPU), a tensor processing unit (TPU), or other computing resource suitable for parallel processing,
a ML pathfinding model running on the parallel processing system,
the synthetic dataset for pathfinding applications of claim 1 ,
wherein the ML pathfinding model is trained on a training dataset generated from the synthetic dataset, and the ML pathfinding model, once being trained, is applied to route unseen nets.
4 . The system according to claim 3 , wherein the computer-executable program, when executed, generates the routed circuits via steps further comprises generating joinable and detached bitmap images for the synthetic dataset, as the training dataset generated from the synthetic dataset.
5 . The system of claim 4 , wherein the computer-executable program, when executed, generates the routed circuits via steps further comprises repeatable merges of joinable and detached bitmap images to form a high resolution, complex global synthetic dataset.
6 . The system according to claim 3 , the ML pathfinding model is a conditional generative adversarial network (CGAN) model.
7 . The system according to claim 6 , wherein the training dataset generated from the synthetic dataset for pathfinding applications is a set of suboptimal synthetic nets.
8 . AA method performed by data processing apparatus for generating a synthetic dataset capturing the similarities of real circuits in terms of the spread of the pins and obstacles and routing characteristics thereof, comprising:
obtaining a plurality of low-resolution optimally routed small bitmaps (LRSBs) each of which is a bitmap of an existing routed circuit, and each of which comprises at least one terminal of a net segment placed on the bitmap perimeter,
obtaining a target layout resolution,
selecting and merging two or more bitmaps from the plurality of LRSBs into a resulted bitmap,
continuing the selecting and merging step until the resulted bitmap reaches the target layout resolution, at which point, the resulted bitmap is a bitmap of a valid complex obstacle-avoiding multi-pin routed circuit,
outputting the resulted bitmap as one datapoint of the synthetic dataset.
9 . The method of claim 8 , wherein the selecting and merging further comprises:
randomly selecting and placing a bitmap b 1 from the plurality of LRSBs, wherein b 1 is adjacent to an unprocessed space SI,
randomly selecting a bitmap b 2 from a list of b 1 's joinable bitmaps, and placing b 2 in SI along the right edge of b 1 , wherein b 2 is adjacent to an unprocessed space SII,
randomly selecting a bitmap b 3 from a list of b 2 's joinable bitmaps, and placing b 3 in SII along the right edge of b 2 , wherein the bitmaps b 1 and b 3 are adjacent to an unprocessed space SIII,
randomly selecting a bitmap b 5 from an intersection of bitmap b 1 's joinable bitmaps and bitmap b 3 's detached bitmaps, and placing b 5 in SIII along the right edge of b 1 and the top edge of b 3 ,
outputting the b 1 , b 2 , SI SIL, b 3 , SILL, and b 5 in their respective placings to the resulted bitmap.
10 . A method performed by data processing apparatus of generating a complex global pathfinding training dataset and using the complex global pathfinding training dataset comprising:
generating a plurality of small bitmaps, each small bitmap comprises at least one terminal or a net segment placed on the small bitmap perimeter;
joining the plurality of small bitmaps via edge terminals and/or net segments into a longer, more complex net within a larger bitmap to generate the complex global pathfinding training dataset of placed bitmaps;
training a machine learning (ML) based pathfinding model based on the complex global pathfinding training dataset; and
applying the ML based pathfinding model in pathfinding applications.
11 . The method of claim 10 , further comprising the step of:
repeatedly improving the resolution the larger bitmap to generate a training sample from the complex global pathfinding training dataset.
12 . The method of claim 11 , further comprising the step of:
resolving any unprocessed space adjacent to placed bitmaps.
13 . The method of claim 10 , further comprising the steps of:
generating within a rectangular bitmap a large set of net routing, wherein each tile of the rectangular bitmap comprises at least one terminal or a net segment placed on a perimeter of the rectangular bitmap;
joining two or more rectangular bitmaps via two edge net segments to obtain a larger bitmap, wherein the larger bitmap comprises a valid grouping of routed nets with smaller bitmaps being rotated and flipped as needed; and
determining whether the joined bitmaps are a valid grouping if it does not exceed a maximum layout resolution as provided by a target training resolution.