Left Edge Channel Algorithm for detailed routing

Left edge and dogleg algorithm comes under detailed routing where it determines the exact route and layers for each net. These algorithm helps in minimizing the area (congestion).

Left -Edge Algorithm:

Left edge order is detailed routing. It is based on VCG and left -edge order. Each net uses only one horizontal segment.

Steps:

a.       Build the vertical constraint graph (VCG) for the input channel routing

b.       Place horizontal segments (choose nets (1) that do not have ancestors in the VCG and (2) whose horizontal segments do not overlap) and update the VCG

c.       Step 3: Repeat Step 2 until all the horizontal segments have been placed

Example:

VCG for this would be :

Since left edge algo is based on VCG, One starts with the VCG and make a list of vertices that have no incoming edges.

In this case, vertices 1,2, 5 and 8 would be routed first.  But 2 overlaps with 1, we can’t add net 2 to the first row so we skip it and go on to net 5 and 8.

In next cycle net 3,2, and 7 would be routed and so on.

Below is the final routing using this algorithm.

Table of Contents