How to draw a path and keep it out of pattern?

jiunnweiyeh

Hi sir,
I got a hard issue as attached file and figure below.
as this shown I want to draw a path by 13um , like the red-line I maked in picture.
This line start from left side of layer 71/0 , end at right side of layer 71/0 for the X-asix.
Path width is 13um and here is limitation:
1.keep it out of Mask pattern by 1um.
2.path "connections" can be "Diagonal" only.
3.Can been drawing run into the area of up-edge to down-edge by Y-asix.
as this case in GDS , we have around 1000um for the routing space.

this is a simple sample , in the real case we have so many Mask pattern and it is reason we can't make the path as a straight line.
Now , we make the path by manu manual , do you have any idea to make a scrpit for that?
in this case , we have so many path solution can be using , just make it keep the 3 rules.
I guess that I have to using xor or other function to find/define where the path routing area.
But I have no idea for the more detail .
Is it possible to make a script for that?

RawrRanger

Hi jiunnweiyeh

Here's a example that sometimes works under certain senerio.

Because this scrip is not clever enough to optimize to the pattern and path, you might need to fiddle around those magic numbers that hard coded in the script in order to make it even just show something if layout is changed.

The script involves three main sections:

genNodes :

• Take RDL layer and defines region of intrest using a base layer
• Convert layout to simple patterns to reduce DRC work load
• Roughly split RDL pads and RDL routings
• The spacing between RDL pads are the area for potential way points for routing
• Generate nodes from those spacings, output to L(110, 0)

genGridNodes:

• Take the results from genNodes L(110, 0)
• Makes the nodes becomes on grid, main purpose is to classify nodes using their X valuse and put into nodeHash.
• Sort nodeHash with X values, so now we get groups of node columns that is ready to be connected.
• This returns the nodeHash for path routing

genNodePath:

• UsesnodeHash from genGridNodes, loop through each columns and find minium path for routing

def genNodes(rdlLayer, roiLayer)
    rdlRoi  = rdlLayer.inside(roiLayer) 
    pix     =   5.um         # simplifying the RDL with a 2 * pix.um box
    dist    = 180.um         # usind layer.spacing(dist) to generate area for routing
    padSize =  50.um         # threshold for pad, larger than this will be recognize as a obsticle
    pixVec  = RBA::DVector::new(-pix, -pix)

    simplified = rdlRoi.collect_to_region{ |poly|
        bbox   = poly.bbox
        center = bbox.center
        (bbox.width < padSize) && (bbox.height < padSize) ? RBA::DBox::new(center + pixVec, center - pixVec) : bbox
    }

    padCenter  = simplified.with_bbox_max(   0 .. 1.0.um + pix * 2)
    obsticles  = simplified.without_bbox_max(0 .. 1.0.um + pix * 2)
    padSpace   = padCenter.space(dist, projection).polygons.raw.not_overlapping(padCenter).raw
    nodes1     = padSpace.merged(2)
    nodes2     = padSpace.not_interacting(nodes1).raw.not_overlapping(padCenter).raw.middle(as_boxes).sized(pix - dbu)
    nodes      = (nodes1 + nodes2).not_interacting(simplified)

    padCenter.output(100, 0) # for visualization
    obsticles.output(100, 1) # for visualization
    padSpace .output(100, 2) # for visualization
    nodes1   .output(100, 3) # for visualization
    nodes2   .output(100, 4) # for visualization
    nodes    .output(110, 0) # for visualization
    return nodes
end

def genGridNodes(nodesLayer)
    nodeHash   = {}
    gridXsize  =  5.um
    gridYsize  =  5.um
    pix        =  5.um
    pixVec     = RBA::DVector::new(-pix, -pix)

    gridNodes = nodesLayer.collect_to_region{ |poly| 
        center = poly.bbox.center()
        gx     = (center.x / gridXsize).to_int * gridXsize
        gy     = (center.y / gridYsize).to_int * gridYsize
        gc     = RBA::DPoint::new(gx, gy)
        if !nodeHash.key?(gx) then nodeHash[gx] = [] end
        nodeHash[gx].append(gy)
        RBA::DBox::new(gc - pixVec, gc + pixVec)
    }
    gridNodes.output(110, 1) # for visualization
    return nodeHash.sort.to_h
end

def genNodePath(nodeHash)
    nodePath  = []
    pathWidth = 13.um
    threshold = 300.um
    pathLayer = make_layer

    nodeHash.each{ |x, vys|
        nextNodes = vys.sort.map{|y| RBA::DPoint::new(x, y)}
        if nodePath.empty? then
            nodePath << nextNodes[rand(nextNodes.length)]
        else
            closeDist = Float::INFINITY
            prevNode  = nodePath[-1]
            closeNode = nextNodes[0]
            nextNodes.each{ |node|
                distance = node.distance(prevNode)
                if distance < closeDist then
                    closeDist = distance
                    closeNode = node
                end
            }
            if closeDist < threshold then
                nodePath << closeNode
            end
        end
    }

    pathLayer.insert(RBA::DPath::new(nodePath, pathWidth))
    pathLayer.output(120, 0) # for visualization
    return pathLayer
end

rdlLayer   = input( 3, 0)
roiLayer   = input(71, 0)
nodesLayer = genNodes(rdlLayer, roiLayer)
nodeHash   = genGridNodes(nodesLayer)
genNodePath(nodeHash)

RawrRanger

(1) genNodes simplify the patterns into orange boxes, later use layer space to extract spaced region.

(2) genNodes space extracted by layer.space, however if the pads are not exactly aligned othogonally, or the pitch change between sections than this part will not work correctly.

(3) genNodes simplify the space into nodes, again, if the pitch diviates alot from each other, this part also will not work.

(4) after genGridNodes, the nodes is being grouped by column, iterate throuth each column and find nodes that is close to previous one.

You probably can tell by now, this method cannot provide perfect 45 deg routing, and is not capable of doing tight routing, basically a run-and-prey type of algorithm.

jiunnweiyeh

Hi RawrRanger ,
Thanks for your code , I will check it and try to make it into what my code if it is fine.
Thanks.

Matthias

Holy cow!

@jiunnweiyeh You like these kind of puzzles do you?

From the academic viewpoint that looks like a variant of the path finding problem (see https://en.wikipedia.org/wiki/Pathfinding). "A*" is an algorithm often used in routers for manhattan paths, so maybe this applies here. For any-angle paths algorithms are more complex though (see https://en.wikipedia.org/wiki/Any-angle_path_planning).

I wonder if there is a generic library for that case. As there is a Python module for everything, maybe someone published a useful implementation already?

Matthias

jiunnweiyeh

Hi @Matthias
Let me explain this request...
This function , we called "stitching" .
cause the (customer's design) DIE size is large than our exposure machine limitation.
we have to cut our DIE as 2 part for photo Mask design.
but we have some process issue and request for this line ... that must to make it keep out IO/line and other something pattern.
I can't provided full GDS and rule in here , but the guildline would be what I means.
in the real case, IO/Bump/line will more than the sample GDS I provided.
so our designer has make the path as my first post by manual .
when I using RawRanger 's code , I found some of issue and I am tring to fix it or list down the condination.
Thanks very much for all of your help.

RawrRanger

Hi jiunnweiyeh,

Here's a revised version, the major differences are:
1) Can route multiple path in predefined regions, the script will perform auto route if routing is not successful
2) Now it can route mostly at 45 deg
3) Reduces huge swing during routing, will propagate using small zig-zag when ever possible

To make it route multiple paths, a guiding layer is required, in this case the layer in teal "L(72, 0) in code" is drawn for thsi purpose.

def genNodes(rdlRoi)
    pix       =   5.um         # simplifying the RDL with a 2 * pix.um box
    dist      = 180.um         # usind layer.spacing(dist) to generate area for routing
    padSize   =  50.um         # threshold for pad, larger than this will be recognize as a obsticle
    gridXsize =   5.um
    gridYsize =   5.um
    pixVec    = RBA::DVector::new(-pix, -pix)

    simplified = rdlRoi.collect_to_region{ |poly|
        bbox   = poly.bbox
        center = bbox.center
        gx     = (center.x / gridXsize).to_int * gridXsize
        gy     = (center.y / gridYsize).to_int * gridYsize
        gc     = RBA::DPoint::new(gx, gy)
        (bbox.width < padSize) && (bbox.height < padSize) ? RBA::DBox::new(gc + pixVec, gc - pixVec) : bbox
    }

    padCenter  = simplified.with_bbox_max(   0 .. 1.0.um + pix * 2)
    obsticles  = simplified.without_bbox_max(0 .. 1.0.um + pix * 2)
    padSpace   = padCenter.space(dist, projection).polygons.raw.not_interacting(obsticles)
    crossPoint = padSpace.merged(2)
    node       = padSpace.raw.sized(-1.um).merged().middle(as_boxes).sized(pix - dbu)
    node       = node.not_interacting(simplified)

    #padCenter.output(100, 0) # for visualization
    #obsticles.output(100, 1) # for visualization
    #padSpace .output(100, 2) # for visualization
    node     .output(100, 3) # for visualization
    return node
end


def genGridNodes(nodesLayer)
    nodeHash   = {}
    gridNodes  = nodesLayer.collect_to_region{ |poly| 
        center = poly.bbox.center()
        if !nodeHash.key?(center.x) then nodeHash[center.x] = [] end
        nodeHash[center.x].append(center.y)
    }
    return nodeHash.sort.to_h
end

def tidyGridNodes(nodeHash)

    # tidyup each column by x value again, groups columns 
    # with x direction distance < threshold
    # this reduce the chance of path routing at a wierd angle

    threshold   = 35.um
    newNodeHash = {}
    nodeHash.each{ |key, v|

        if newNodeHash.empty? then
            newNodeHash[key] = v
        else
            preKey = newNodeHash.keys[-1]
            delta  = key - preKey

            if (delta < threshold) then
                newNodeHash[preKey] += v
            else
                newNodeHash[key]     = v
            end
        end
    }
    return newNodeHash
end

def genNodePath(nodeHash, startPoint = 0)
    nodePath  = []

    nodeHash.each{ |x, vys|
        nextNodes = vys.sort.map{|y| RBA::DPoint::new(x, y)}
        if nodePath.empty? then
            startPoint = [startPoint, nextNodes.length].min
            nodePath << nextNodes[startPoint]
        else
            prevNode  = nodePath[-1]
            nextNodes = nextNodes.sort_by{ |node| node.distance(prevNode)}
            closeNode = nextNodes[0]

            # this part makes the routing tends to go in a zig-zag pattern
            # instead of sway in particular direction
            # pick two candidate that is close to previous point, compares the angle vector
            # choose the one that is vertical to previous path

            if (nextNodes.length > 1 ) && (nodePath.length > 1) then
                candidate1 = nextNodes[0]
                candidate2 = nextNodes[1]
                cadiDist1  = candidate1.distance(prevNode)
                cadiDist2  = candidate2.distance(prevNode)

                if (cadiDist1/cadiDist2).between?(0.6, 1.4)then
                    preVec    = prevNode   - nodePath[-2]
                    candiVec1 = candidate1 - prevNode
                    candiVec2 = candidate2 - prevNode
                    closeNode = (candiVec1.y * preVec.y) < 0 ? candidate1 : candidate2
                end
            end

            # after point is choosen, tried to rectify the path to be at 45 deg angle
            # if path is at a angle that is too large or too small, tried to insert addition
            # point and make it connect two points in 45 deg

            # if the angle is almost at 45 deg, we'll just modify next point coordinate slightly
            # to make it at exact 45 deg

            angleVec = closeNode - prevNode
            if !(angleVec.y / angleVec.x).abs.between?(0.4, 1.6) then 
                e1a     = RBA::DEdge::new(prevNode,  prevNode  + RBA::DVector::new( 1,  1))
                e1b     = RBA::DEdge::new(prevNode,  prevNode  + RBA::DVector::new( 1, -1))
                e2a     = RBA::DEdge::new(closeNode, closeNode + RBA::DVector::new(-1,  1))
                e2b     = RBA::DEdge::new(closeNode, closeNode + RBA::DVector::new(-1, -1))

                cutPt1  = e1a.cut_point( (e1a.is_parallel?(e2a)) ? e2b : e2a)
                cutPt2  = e1b.cut_point( (e1b.is_parallel?(e2a)) ? e2b : e2a)
                cutDst1 = cutPt1.distance(prevNode) + cutPt1.distance(closeNode)
                cutDst2 = cutPt2.distance(prevNode) + cutPt2.distance(closeNode)
                cutPt   = (cutDst1 > cutDst2) ? cutPt1 : cutPt2
                nodePath << cutPt
                nodePath << closeNode

            else
                dir = (angleVec.y / angleVec.y.abs)
                nodePath << prevNode + RBA::DVector::new(angleVec.x, dir * angleVec.x)

            end
        end
    }

    return nodePath
end

def routePath(rdlLayer, roiLayer, pathWidth = 13.um)
    goodPaths  = []
    badPaths   = []

    roiLayer.collect{ |p|
        eachROI = make_layer
        eachROI.insert(p)

        rdlRoi     = rdlLayer.interacting(eachROI) 
        nodesLayer = genNodes(rdlRoi)
        nodeHash   = genGridNodes(nodesLayer)
        nodeHash   = tidyGridNodes(nodeHash)
        maxRetry   = nodeHash[nodeHash.keys[0]].length

        # auto perform retry if the inserted path interfers with RDL pattern
        # retry by changing the entery point of first node

        (0..maxRetry).each{ |i|
            pathLayer   = make_layer
            nodePath    = genNodePath(nodeHash, startPoint = i)
            pathObj     = RBA::DPath::new(nodePath, pathWidth)
            pathLayer.insert(pathObj)
            noInterfere = rdlRoi.interacting(pathLayer).count == 0

            if noInterfere then
                goodPaths.append(pathObj)
                break
            elsif i == (maxRetry-1) 
                badPaths.append(pathObj)
            end
        }   
    }
    return goodPaths, badPaths
end 

cellView = RBA::CellView::active
layout   = cellView.layout
cell     = cellView.cell
rdlLayer = input( 2, 0)
roiLayer = input(72, 0)
goodPaths, badPaths = routePath(rdlLayer, roiLayer)

# insert using path instead of drc layer, due to drc layer converts everything into polygons
# which makes it difficult to be edited manually.

goodPaths.each{ |path| cell.shapes(layout.layer(120, 0)).insert(path)}
badPaths .each{ |path| cell.shapes(layout.layer(120, 1)).insert(path)}

RawrRanger

And for optimizing the route, implementing an A* or other type of path finding algorithms will be neccessary if the layout becomes complicated, without this type of optimization, the path might no always get all the way through to another side.

Due to the example shown here got a quite distinct characteristic, that is the each obsticles is small enough, and in most cases thay don't populated at a way that makes dead ends, so brute forcing this becomes a quick and somewhat feasible method.