WIRE ROUTING BY OPTIMIZING CHANNEL ASSIGNMENT WITHIN LARGE APERTURES
- Vaibhav Damle - Amit Tamboli
Left-Edge Algorithm
Proposed by Hashimoto and Stevens in 1971 Regarded as the first channel routing algorithm Can be used in solving Channel Routing Problems Originally used in PCB design Can be applied on VLSI physical design
Basic Left-Edge Algorithm
Attempts to maximize placement of horizontal segments in each track No vertical constraints HV-layer model is used Doglegs are not allowed Produces optimal routing solution with minimum # of tracks(If no vertical constraint)
Algorithm
1. Sort all nets on their leftmost end positions. 2. Select the net with lowest left position; place it on the first available track; delete net from list. 3. Continue scanning the list and select from it nets that do not overlap with the nets assigned to this track; Assign the nets to the current track and delete from list. 4. If list null then goto 2. 5. Exit
N2
N1
N3 N4 N5 N6 N7 N8 N9 N10
N2
N7
N1
N3 N4 N5
N6
N8
N9
N10
N2 N1 N3 N4 N5 N6 N7 N8 N9 N10
The Left-Edge Algorithm (contd) Step 1: Build VCG
The Left-Edge Algorithm (contd) Step 2: Place horizontal segments
Consider horizontal segments of N1, N4, and N10 (the nets that do not have ancestors)
8
The Left-Edge Algorithm (contd) Step 2: Place horizontal segments
N1 has the smallest x coordinate N1 and N4 cannot be placed on the same track N1 and N10 can be placed on the same track Place N1 and N10 on the highest track
9
The Left-Edge Algorithm (contd) Step 2: Place horizontal segments
N1 has the smallest x coordinate N1 and N4 cannot be placed on the same track N1 and N10 can be placed on the same track Place N1 and N10 on the highest track
10
The Left-Edge Algorithm (contd) Step 2: Place horizontal segments
Update the VCG (remove N1 and N10 from the VCG)
11
The Left-Edge Algorithm (contd) Step 2: Place horizontal segments
Update the VCG (remove N1 and N10 from the VCG)
12
The Left-Edge Algorithm (contd) Step 2: Place horizontal segments
Consider horizontal segments of N4 and N7 (the nets that do not have ancestors)
13
The Left-Edge Algorithm (contd) Step 2: Place horizontal segments
Consider horizontal segments of N4 and N7 (the nets that do not have ancestors)
14
The Left-Edge Algorithm (contd) Step 2: Place horizontal segments
Consider horizontal segments of N4 and N7 (the nets that do not have ancestors) N4 has the smallest x coordinate N4 and N7 cannot be placed on the same track Place N4 on the second highest track
15
The Left-Edge Algorithm (contd) Step 2: Place horizontal segments
Consider horizontal segments of N4 and N7 (the nets that do not have ancestors) N4 has the smallest x coordinate N4 and N7 cannot be placed on the same track Place N4 on the second highest track
16
The Left-Edge Algorithm (contd) Step 2: Place horizontal segments
Update the VCG (remove N4 from the VCG)
17
The Left-Edge Algorithm (contd) Step 2: Place horizontal segments
Update the VCG (remove N4 from the VCG) Repeat the placement iterations
18
The Left-Edge Algorithm (contd) - Result of the Example
19
The Left-Edge Algorithm (contd) - Result of the Example
N1 = 5 N2 = 1 N3 = 2 N4 = 4 N5 = 3 N6 = 2 N7 = 3 N8 = 1 N9 = 2 N10 = 5
(The Output of Your Channel Router)
20
What if VCG is Cyclic
Left Edge cannot handle Cyclic VCG
Solution - Doglegging
Improvement
Doglegging can also reduce the height of channel.
# of Tracks 3 (w/o Doglegging)
# of Tracks 2 (w/ Doglegging)
Summary
With 2 layer modeling, Basic Left Edge Algorithm produces minimum # of Tracks VCG is used to remove vertical constraints Cyclic VCG is solved using doglegging.