Left Edge Channel Algorithm for detailed routing

🔍 Left Edge Algorithm Basics

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.

Problem: You have a set of horizontal nets (wires) that need to be routed in a channel, connecting terminals on the top and bottom of the channel. Each net spans from a leftmost column to a rightmost column.

Assumptions:

• One routing layer (usually horizontal).

• No doglegs (i.e., each net must be assigned to a single horizontal track).

• Each track can carry multiple nets, but only if they don't overlap.

• Vertical connections (vias) are made at terminal positions.

LEA Steps:

1. Sort all nets by their left edge (i.e., starting column) in increasing order.

2. Initialize an empty set of tracks.

3. For each net in sorted order:

   • Try to assign it to the lowest-numbered track where it does not overlap with any net already on that track.

   • If no such track is found, create a new track and assign the net there.

---

📦 Example Input Format

Let’s say each net is defined by its left and right span (columns it needs to go from/to):

// Nets:  (NetID, LeftEdge, RightEdge)
Net0: (0, 1, 5)
Net1: (1, 2, 6)
Net2: (2, 4, 8)
Net3: (3, 0, 2)
Net4: (4, 7, 9)

Sort by LeftEdge:

Net3 (0,2), Net0 (1,5), Net1 (2,6), Net2 (4,8), Net4 (7,9)

Routing (greedy LEA assignment):

• Track 0: Net3, Net1, Net4

• Track 1: Net0, Net2

---

🧠 Verilog Implementation?

The LEA is usually implemented in a software language (C++, Python, etc.) for physical design tools, not Verilog, since Verilog is for hardware description.

But, if you really want to simulate the LEA logic in Verilog as a behavioural model (just for educational purposes), you could do something like:

---

🔧 Pseudo-Verilog (Behavioural Modelling)

module left_edge_router;
  integer i, j;
  parameter NUM_NETS = 5;
  parameter MAX_TRACKS = 10;
  // Net definition: [left_edge][right_edge]
  integer left[0:NUM_NETS-1];
  integer right[0:NUM_NETS-1];
  integer track_assignment[0:NUM_NETS-1];
  integer track_ends[0:MAX_TRACKS-1];
  initial begin
    // Define net intervals
    left[0] = 1; right[0] = 5;
    left[1] = 2; right[1] = 6;
    left[2] = 4; right[2] = 8;
    left[3] = 0; right[3] = 2;
    left[4] = 7; right[4] = 9;
    // Initialize
    for (i = 0; i < NUM_NETS; i = i + 1)
      track_assignment[i] = -1;
    for (i = 0; i < MAX_TRACKS; i = i + 1)
      track_ends[i] = -1;
    // Sort by left edge (simple bubble sort for illustration)
    integer temp_l, temp_r;
    for (i = 0; i < NUM_NETS; i = i + 1) begin
      for (j = i + 1; j < NUM_NETS; j = j + 1) begin
        if (left[i] > left[j]) begin
          temp_l = left[i]; temp_r = right[i];
          left[i] = left[j]; right[i] = right[j];
          left[j] = temp_l;  right[j] = temp_r;
        end
      end
    end
    // Left Edge Algorithm
    for (i = 0; i < NUM_NETS; i = i + 1) begin
      for (j = 0; j < MAX_TRACKS; j = j + 1) begin
        if (track_ends[j] < left[i]) begin
          track_assignment[i] = j;
          track_ends[j] = right[i];
          break;
        end
      end
    end
    // Print assignments
    for (i = 0; i < NUM_NETS; i = i + 1)
      $display("Net %0d assigned to Track %0d", i, track_assignment[i]);
    $finish;
  end
endmodule

---

🧪 Output (Expected):

Net 3 assigned to Track 0
Net 0 assigned to Track 1
Net 1 assigned to Track 0
Net 2 assigned to Track 1
Net 4 assigned to Track 0

Table of Contents