Routing is to find the best possible connection [route] between two elements [clocks, flip-flops etc]. There have been many routing algorithms created like Steiner Tree algorithm, Line Search algorithm etc. and one such algorithm we will go into detail is Maze Routing - Lee's Algorithm (Lee 1961).
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
Consider connecting points 1 and 2 in the above picture, where in 1 is the source and 2 the target. The need is to find the best possible [shortest] path to connect 1 and 2. This route will aim to have very little or none routes with zig-zags, and mostly the routes are L-shaped. From an algorithmic standpoint, the software needs to search and connect the two poi+nts. From a physical design point of view, it is a physical/wire that allows signals to travel.
Lee's Algorithm is popularly used in maze routing [type of problem where path from source to destination needs to found in grid similar to a maze]. This algorithm is especially effective for routing in grid or mesh-based structures, making it an excellent choice for integrated circuit design.
Steps:
- Initialisation - In this step, a routing grid/matrix is created in the area to be routed. It categorises each cell into one of various states - (i) obstacle ; (ii) empty ; (iii) visited ; (iv) source ; (v) target.
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
- Wave Expansion - The algorithm performs a wave expansion from the source [marked as 'S'] cell, spreading outwards in all directions. At each step, the algorithm examines neighboring cells (up, down, left, and right) and assigns them a value one greater than the minimum value of their neighboring cells (excluding obstacles and starts from 1). This process continues until the target [marked as T] cell is reached or until no more cells can be visited.
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
[Continuation of Steps]
- Backtracking and Path Reconstruction - Once the target is reached, the algorithm backtracks the path to the source by following the cell values. Through this there might be multiple paths obtained but the tool will choose one with less bends i.e. a shorter route along the algorithm to give us the shortest route.
The route should not be diagonal and must not overlap any blockage/obstruction such as macros or HIPs.
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
When we route, we do not just merely connect two points, we must also adhere to certain rules. For example, one rule mention how when constructing two wires there must be a minimum distance between them, they must have a minimum width and pitch etc. ence, DRC cleaning is done to ensure that the routes can be fabricated and printed in silicon properly.
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
Another critical issue is signal short, which causes functionality failure. This can be removed by moving the route to the next layer. This leads to more DRCs (via width, via spacing, higher metal layer must be wider than lower metal layer etc.).
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
The lab steps to build a power distribution network are -:
-
Go to the openlane directory
-
Enter the command docker and then ./flow.tcl -interactive . To subsequently get the openlane package, type package require openlane 0.9.
-
Then prep the design using -: **prep -design picorv32a -tag [folder name of run where in cts had been done]
-
Then type echo $::env(CURRENT_DEF) /openLANE_flow/designs/picorv32a/runs/[folder name of run where in cts had been done]/results/cts/picorv32a.cts.def
-
Then, type this to generate the PDN -: gen_pdn
{IMAGE CREDITS: AUTHOR; SCREENSHOT TAKEN FROM DEVICE}
{IMAGE CREDITS: AUTHOR; SCREENSHOT TAKEN FROM DEVICE}
The power and ground rails have a pitch of 2.72µm and hence the custom inverter cell also has a height of 2.72µm. This is as otherwise power and ground rails will not be able to power the cell. We also see that looking at the LEF file runs/[date]/tmp/merged.lef, all cells are have height of 2.72µm and only their width differs.
{IMAGE CREDITS: AUTHOR; SCREENSHOT TAKEN FROM DEVICE}
It is shown below how standard cells are powered up :- power/ground pads -> power/ground ring-> power/ground straps -> power/ground rails
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
{IMAGE CREDITS: AUTHOR; SCREENSHOT TAKEN FROM DEVICE}
TritonRoute is the engine that is used for routing through the run_routing command.
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
In the VLSI flow, the routing stage is highly critical and can be executed using either open-source or commercial tools. This stage is divided into two phases:
Global Route / Fast Route:
This is accomplished using fast routing techniques where the area to be routed is partitioned into tiles or rectangles. Global routing establishes the initial framework for routing paths. Detail Route:
This phase involves meticulous tracking routing techniques to complete the routing process. Detailed routing fine-tunes and finalizes the paths to ensure proper connectivity and compliance with design constraints.
In VLSI, routing is extremely important and is either done through open-source/commericial tools. It has mainly two phases -:
- Global Route - Also known as fast route, it uses fast routing techniques wherein we partition the area to routed into tiles/rectangles. It establishes the initial framework
- Detailed Route - This process uses more meticulous routing techniques, and completes the process by fine-tuning and finalizing the paths to ensure connectivity and compliance with DRC.
The preferred direction for M1 and M2 respectively is vertical and horizontal. Whenever, a non-preferred direction route is found by the tool, the tool divides the route into unit width in a process called splitting. The sections that fall into the preferred directions are subsequently combined. Sections parallel to the preferred direction are bridged with upper layer [in bridging]. Non-preferred routes are converted into preferred routing guides of M2.
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
The second feature is interguide connectivity:-
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
As mentioned earlier, the preferred direction of M1 is vertical - resulting in vertically oriented lines. Panels are the dashed lines with a routing guide for each panel. Intra layer panel routing is when routing occurs withing even-index panels. Initially, routing takes place simultaneously in all even-index panels, which is followed by routing in odd-index panels. This routing remains confined within a particular layer and then Routing progresses from lower to upper layers, ensuring the orderly flow of routing operations.
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
The aim of MILP (Mixed Integer Linear Programming) is to find the optimal solution to connect two access point clusters.
In the below algorithm, cost is found for each access point. Then, a minimum spanning tree between access points and cost is made. So, the algorithm says that the minimal and most optimal point is needed between two APCs.
{IMAGE CREDITS: VSDIAT; SCREENSHOT TAKEN FROM LECTURE}
After running the run_routing command, routing [both global and detail] is completed. Routing Strategy was set to 0, which meant that DRC violations must be brought down from a high value [25000 in this case] to 0. This takes multiple iterations [34] and nearly 20 minutes to half an hour.
{IMAGE CREDITS: AUTHOR; SCREENSHOT TAKEN FROM DEVICE}
{IMAGE CREDITS: AUTHOR; SCREENSHOT TAKEN FROM DEVICE}
{IMAGE CREDITS: AUTHOR; SCREENSHOT TAKEN FROM DEVICE}
After this, a def file will be formed in the location [runs/[date]/results/routing/picorv32.def], which has to opened in MAGIC -:
{IMAGE CREDITS: AUTHOR; SCREENSHOT TAKEN FROM DEVICE}
NOTE: OpenLANE does not have any spef extraction tool, so we use a separate tool present in work/tools/ directory.
The steps for extraction are -:
-
Go to /home/vsduser/Desktop/work/tools/SPEF_EXTRACTOR, where in there are a list of files, one of which is a python file called main.py. This file helps in generation of the SPEF provided. There are also lef & def files in the folder.
-
Now, to create the SPEF file python3 main.py /home/vsduser/work/tools/openlane_working_dir/openlane/designs/picorv32a/runs/26-03_05-49/tmp/merged.lef /home/vsduser/work/tools/openlane_working_dir/openlane/designs/picorv32a/runs/26-03_05-49/tmp/routing/picorv32a.def
NOTE: spef will be saved in the same location as def file. /home/vsduser/work/tools/openlane_working_dir/openlane/designs/picorv32a/runs/26-03_05-49/tmp/routing
{IMAGE CREDITS: AUTHOR; SCREENSHOT TAKEN FROM DEVICE}
The last stage will be to extract the GDSII file ready for fabrication run_magic
This uses Magic to stream the GDSII file runs/26-03_05-49/results/magic/picorv32a.gds. This GDSII file can then be read by Magic:
The last stage is to extract the GDSII file ready for fabrication through run_magic. This uses MAGIC to stream the GDSII file runs/26-03_05-49/results/magic/picorv32a.gds. The GDSII can now be ready by MAGIC -:
{IMAGE CREDITS: AUTHOR; SCREENSHOT TAKEN FROM DEVICE}
