Untitled

Net tracing is a feature which is used to do electrical tracing in the layout.

Net Trace takes a connectivity {c1 c2...} as an input, where ci i=1, 2,... is a layer: datatype.

The result of the net trace is a set of shapes which are electrically connected.

Our net tracing has some issues. The main issue is the performance. It takes a lot of time to trace even not so big nets.

We write out the current net tracing algorithm in order to understand the way how to solve the current issues, for example`

Improve the current algorithm
Create a new algorithm based on the current one
Create brand new algorithm 
Algorithm visualization
Global Tracer
Local
Tracer
Local
Tracer
Local
Tracer
Local
Tracer
Local
Tracer
Seed Shapes
geom::cell
N3 shapes
geom::cell
N4 shapes
geom::cell
Nm shapes
geom::cell
N1 shapes
geom::cell
N2 shapes
.........

Algorithm description 




            Cell view





















Let's take a look at the Cell view.  

Net Tracing is divided into 2 parts: lbbTrace (macro-trace), localTrace (micro-trace). 

Each stage has its own containers described below.

containers: 

thisRound, lastRound, earlierRounds, goodThisRound.



thisRound - The net shapes we found in this round. These shapes will be used during next tracing rounds.

lastRound - The net shapes we found in the last round.

earlierRounds - Accumulation of all the net shapes found up through the last round. The bbox of all shapes accumulated here is the command result.

goodThisRound - The net shapes we found in this round. These shapes will not be used during next tracing rounds.



Let's start net trace from shape 1 and see the results.

The result of Net tracing is the merged bbox of found shapes.

Net tracing continues until no new shapes are found during lbb Trace.

If there is a limiting rectangle, then tracing will refuse to find new net shapes that are entirely outside the limiting rectangle, bringing the trace to an early halt. 



All the shapes are concurrent hash sets of findRecords.

FindRecord is a structure which records a shape found during tracing, together with the shape that it connects to (seed shape). 

For differentiation we will add a prefix (local and lbb) to the containers name to make it more understandable.

Both lBB tracing (Macro-tracing) and local tracing (Micro-tracing) work with rounds.

First round of LBB Tracing


Shape 1 is a seed shape (seed means that tracing starts from that shapes).

All the seed shapes are pushed into lbbLastRound container.



Current status of lbb containers

lbbLastRound = {( )}

lbbThisRound = {}

lbbEarlierRounds = {}

lbbGoodThisRound = {}



Lbb Trace does preparatory work before local tracer starts tracing.

Local tracer is created for each lbbLastRound record. 

Set up local tracer's containers:

The finding shape of lbbLastRound's current record is pushed into localLastRound set.

The found shape of current record is added into searchCell of local tracer.



 SearchCell





Current status of local containers

localLastRound = {( )}

localThisRound = {}

localEarlierRounds = {}


Local Trace searchBbox of the seed shape  (searchBbox is the bbox of the found shape from which local trace starts). The bbox is used when distributing localEarlierRound records into lbbGoodThisRound and lbbThisRound.



Lbb Trace finds the shapes intersecting with the found shape's  bbox and push them into local Tracer's searchCell.

Before searching it lbb Tracer enlarges the bbox with some tolerance to find the shapes that abut with search rectangle.



SearchCell





















Local Tracing


First round of Local Tracing


Local Tracer works until no more shapes are found.

For all the lastRoundShapes (found shape of current record of localLastRound), local Tracer takes the bbox of the it and starts searching on the searchCell, to find the shapes connecting to lastRoundShape.

In our example shape1 is lastRoundShape.



During this tracing we will search all the shapes that are connecting to lastRoundShape's bbox and then will push into localThisRound. 

As a result of local trace, we will get 2 kinds of net shapes.

lbbGoodThisRound - Those that lie entirely inside the key bbox
lbbThisRound - Those that do not lie entirely inside the key bbox
Search in cell
Before starting search, lastRoundShape is vectorized. Let's call lastRoundShape a net shape for convenience.

Search starts on the searchCell.

As a result of the search, we get candidate shapes.

If the net shape is a text item, then the shapes do not connect. 

Note the asymmetry. If the candidate shape is a text item, then it'll be detected as connected and go into the solution. But the text item will not be able to connect to anything in later generations, so it should not cause a short.

If both shapes are non-text shapes, then they connect if both are on the same physical layer or are on successive layers (secondPhisLayer == firstPhisLayer + 1 or vice versa. It's assumed that both shapes are on electrical layers).

If the candidate shape is entirely outside of the bounding rectangle (if any) refuse to propagate the net to it. We consider only the shapes that are not known to this local trace (macro trace).  

Let's return to our example. As a net shape we consider shape 1  and search the candidate shapes that are electrically connecting to it.

As a result of the search, we get shape 1  as a candidate shape for shape1. Both shapes are being vectorized to check if they are intersecting or not.

Now we have found a candidate shape for shape 1 , so push them into localThisRound set as a new findRecord (foundShape: , findingShape: ).

Current status of containers 

localLastRound = {( )}

localThisRound = {( )}

localEarlierRounds = {}



We continue searching. As a second candidate shape, we find shape 1. As the localThisRound is a set we don't keep duplicate findRecords and just ignore them. 

As a third candidate shape, we found shape 2 .  As shape 2  is intersecting with shape 1 we add them in localThisRound set as a findRecord (foundShape: , findingShape: ). 

Then we copy the shapes from localThisRound into localEarlierRounds, causing localEarlierRounds to contain all the known shapes. Then we clear localLastRound, copy the shapes from localThisRound into localLastRound, clear localThisRound, in order to continue local tracing. 



Current status of containers

localLastRound = {( ) ( )}.

localThisRound = {}

localEarlierRounds = {( ) ( )}.

Second round of Local Tracing


Now the localLastRound shapes are = {( ) ( )}.

We consider them sequentially.

Start with lastRoundShape ( ). 

Do search with foundShape 's bbox. candidate shape is shape 1 (layer connectivity checkers are satisfied).

As already we have a record in localEarlierRounds with  as a foundRecord we don't add anything in localThisRound and continue searching. 

The second found shape is shape 2  (layer connectivity checkers are satisfied) which also is in localEarlierRounds, so we don't add anything in localThisRound likewise and continue searching.

As a third shape we found shape 2  which also is in localEarlierRounds, so we don't add anything in localThisRound likewise and continue searching.

Let's consider the second lastRoundShape ( ). 

Do search with foundShape 's bbox. Found shape is shape 1 (layer connectivity checkers are satisfied), as we have a record in localEarlierRounds with  as a foundRecord we don't add anything in localThisRound and continue searching. 

Second found shape is shape 2 . This one is also in localEarlierRounds, so we don't add it into localThisRound also.

As a result of second micro-round, we don't have any found shape. So, the localEarlierRounds is the same as before the round start. Then clear localLastRound, copy the shapes from localThisRound into localLastRound, clear localThisRound, in order to continue micro tracing (local tracing) recursively. 



Current status of local containerslocalLastRound = {}

localThisRound = {}

localEarlierRounds = {( ) ( )}.



The second round of local trace finished. As we didn't find a new shape during second micro-round, we stop micro-tracing and return to macro-tracing (lbb tracing).

Before returning to macro-tracing, we'll separate local trace's result (the shapes) into 2 parts:  lbbGoodThisRound and lbbThisRound. 



lbbGoodThisRound - the shapes which are contained entirely into seed shapes' bbox.

lbbThisRound - the shapes which are partially intersected with seed shape.



Consider all the lastRoundShapes  of localEarlierRound.

If a foundShape is seen in lbbEarlierRound when we skip the removal of the shapes (foundShape and findingShape) from the searchCell.

Let's take a look at the steps in more detail.

localEarlierRounds has 2 records.

Consider them successively. The first record is ( ). As lbbEarlierRoundShapes currently is empty so we continue the process.

As already mentioned, if foundShape's bbox is entirely in the seed shape's bbox, then we add that record into lbbGoodThisRound. 

The current found shape is . It isn't entirely contained into seed shape's  bbox, so we add it into lbbThisRound for further macro-tracing search. 



Current status of lbb containers

lbbGoodThisRound = {}

lbbThisRound = {( )}



As the insertion succeeded, we delete the shapes from searchCell (we delete them from searchCell to be ensured that the shapes won't be deleted when search cell gets deleted).



Second found shape is . As it's entirely contained into seed shape's  bbox, then we add it into lbbGoodThisRound. 

As the insertion succeeded, we delete the shapes from searchCell.



Current status of lbb containers



lbbGoodThisRound = {( )}

lbbThisRound = {( )}



Now all the lbbThisRound, lbbGoodThisRound records are inserted into lbbEarlierRounds and lbbLastRound, lbbGoodThisRound shapes (foundShapes and findingShapes) are inserted into lbbEarlierRoundShapes.



Current status of lbb containers



lbbLastRound = {( )}

lbbThisRound = {( )}

lbbGoodThisRound = {( )}

lbbEarlierRounds = {( ) ( )}



Now we accumulate the shapes that are in lbbLastRound and lbbGoodThisRound but not in lbbEarlierRoundShapes and delete them. In our example we don't have any shape that is seen in lbbLastRound and lbbGoodThisRound and not seen in lbbEarlierRoundShapes. So, we don't delete anything from containers. 

As a last step we clear lbbLastRound and copy the findRecords from lbbThisRound to it then clear lbbThisRound also. In this way we prepare prerequisites to continue the rest of the algorithm recursively.

LBB first round finished.

As we still haven't found whole shapes of the trace, we continue tracing.



Second round of LBB Tracing


Current status of lbb containers



lbbLastRound = {( )}

lbbThisRound = {}

lbbGoodThisRound = {( )}

lbbEarlierRounds = {( ) ( )}



Let's continue the rest of the algorithm.

Lbb Trace does preparatory work before local tracer starts tracing.

Local tracer is created for each lbbLastRound record. 

Set up local tracer's containers:

The finding shape of lbbLastRound's current record is pushed into localLastRound set.

The found shape of current record is added into searchCell of local tracer.



SearchCell





Current status of local containers

localLastRound = {( )}

localThisRound = {}

localEarlierRounds = {}



Local Trace searchBbox of the seed shape  (searchBbox is the bbox of the found shape from which local trace starts). The bbox is used when distributing localEarlierRound records into lbbGoodThisRound and lbbThisRound.



Lbb Trace finds the shapes intersecting with the found shape's  bbox and push them into local Tracer's searchCell.

Before searching it lbb Tracer enlarges the bbox with some tolerance to find the shapes that abut with search rectangle.



SearchCell





Local Tracing


First round of Local Tracing


Local Tracer works until no more shapes are found.

For all the lastRoundShapes (found shape of current record of localLastRound), local Tracer takes the bbox of the it and starts searching on the searchCell, to find the shapes connecting to lastRoundShape.

In our example shape1 is lastRoundShape.



Search in cell
Before starting search, lastRoundShape is vectorized. Let's call lastRoundShape a net shape for convenience.

Search starts on the searchCell.

As a result of the search, we get candidate shapes. 

Let's consider net and Candidate shapes to understand if they are connected or not.

 In our example net shape is shape 1  and first candidate shape is also shape 1 .

As they are not yet seen in localEarlierRound, they are on the same physical layer, and also are intersecting, we add them into localThisRound as a findRecord (foundShape: , findingShape: ). 



Current status of local containers

localLastRound = {( )}

localThisRound = {( )}

localEarlierRounds = {}



The second candidate shape is the same as first found candidate shape: shape 1.

As localThisRound is a set, we don't duplicate it, so containers don't change.



Third candidate shape is shape 2 . Shape 1 and shape 2 are connected by layers, also they are intersecting so we add them into localThisRound (findRecord (foundShape: , findingShape: )) as they are not seen in localEarlierRound yet.



Current status of local containers

localLastRound = {( )}

localThisRound = {( ), ( )}

localEarlierRounds = {}



At the end of each local round, we insert localThisRound shapes into localEarlierRound, delete localLastRound copy localThisRound into localLastRound and clear localThisRound.

 Return value of local Trace is found shape count. During this round we have found 2 shapes.



Second round of Local Tracing


Current status of local containers

localLastRound = {( ) ( )}

localThisRound = {}

localEarlierRounds = {( ) ( )}



Consider all the lastRoundShapes of localLastRound .

The first lastRoundShape is shape2 .  Do search on searchCell with bbox  . 

As a candidate shape, we found shape 1 . As shape 1is already seen in localEarlierRound we skip it.

As a second candidate shape, we found shape 2 . As shape 2 is seen in localEarlierRound we skip it also.

As a third candidate shape, we found shape 2 , and skip it also.

As a fourth shape we found shape 3 .  As shape 3  hasn't yet seen in localEarlierRound we continue processing.

Connectivity check is satisfied,  and  are intersecting, so we add them into localThisRound.



Current status of local containers



localLastRound = {( ) ( )}

localThisRound = {( )}

localEarlierRounds = {( ) ( )}



The second lastRoundShape is shape1 .  Do search on searchCell with bbox of shape 1.

 As a first candidate shape, we get shape 1. As shape 1 is already in localEarlierRound we skip that case.

As a second candidate shape is shape 2 which is seen in localEarlierRound, so we skip it also.

As a third candidate shape is shape2  which is also seen in localEarlierRound, so we skip it also.



At the end of each local round, we insert localThisRound shapes into localEarlierRound, delete localLastRound copy localThisRound into localLastRound and clear localThisRound.

Third round of Local Tracing


Current status of local containers

localLastRound = {( )}

localThisRound = {}

localEarlierRounds = {( ) ( ) ( )}



Consider all the lastRoundShapes of localLastRound .

The first lastRoundShape is shape2 .  Do search on searchCell with bbox  . 

As a first candidate shape, we found shape 3 . As shape 2 is seen in localEarlierRound so we skip it.

As a second candidate shape, we found shape 2 . As shape 2 is seen in localEarlierRound we skip it also.



At the end of each local round, we insert localThisRound shapes into localEarlierRound, delete localLastRound copy localThisRound into localLastRound and clear localThisRound.



Current status of local containers

localLastRound = {}

localThisRound = {}

localEarlierRounds = {( ) ( ) ( )}



As a Last step we distribute the localEarlierRound's shape into 2 parts: lbbGoodThisRound, lbbThisRound.

Consider all the lastRoundShapes of localEarlierRound.

If a foundShape is seen in lbbEarlierRound when we skip the removal of the shapes (foundShape and findingShape) from the searchCell.

 In our example we consider shape 3. As shape 3  is not seen in lbbEarlierRound we continue processing.

If the foundShape bbox is entirely contained into searchBbox , then we add a lastRoundShape into lbbGoodThisRound.

If the foundShape is partially contained into searchBbox , then we add lastRoundShape into lbbThisRound.

As we consider shape 3, and it's partially contained into bbox , then we insert it into lbbThisRound.

 Then delete foundShape and finding shape from searchCell.

As a second lastRoundShape is shape 2 .

As shape 2  is seen in lbbEarlierRound, we stop processing (don't delete the shapes from searchCell and don't add anything in lbbThisRound and lbbGoodThisRound).

As a third foundShape is shape 1.

As shape 1  is seen in lbbEarlierRound, we stop processing (don't delete the shapes from searchCell and don't add anything in lbbThisRound and lbbGoodThisRound).

Return to LBB Trace.
lbb Trace already has the found shapes (found shapes during local tracing) in lbbThisRound and lbbGoodThisRound.

Then insert lbbThisRound and lbbGoodThisRound into lbbEarlierRound.

Then delete lbbLastRound copy the records from lbbThisRound into lbbLastRound then clear lbbThisRound.



Third Round of lbb Trace works the same way as previously described lbb first round and second round.