Routing – connecting the dots within chip



Routing is an important step in the design of integrated circuits. It involves generating metal wires to connect the pins of same signal while obeying manufacturing design rules. Before routing is performed on the design, cell placement has to be carried out wherein the cells used in the design are placed. But the connections between the pins of the cells pertaining to same signal need to be made. At the time of placement, there are only logical connections between these pins. The physical connections are made by routing. More generally speaking, routing is to locate a set of wires in routing space so as to connect all the nets in the netlist taking into consideration routing channels’ capacities, wire widths and crossings etc. The objective of routing is to minimize total wire length and number of vias and that each net meets its timing budget. The tools that perform routing are termed as routers. You typically provide them with a placed netlist along with list of timing critical nets. These tools, in turn, provide you with the geometry of all the nets in the design.

Design going through stages of synthesis, placement and routing


VLSI routing is generally considered to be a complex combinatorial problem. Several algorithms have been developed for routing, each having its own pros and cons. The complexity of the routing problem is very high. To make it manageable, most routers usually take a two-step approach of global routing (approximation of routing wires) followed by detailed routing (actual routing of wires).
 




Global routing: Using a global routing algorithm, the router divides the design into tiles, each tile having a limited number of tracks and generates “loose” route for each connection by finding tile-to-tile paths (As shown in figure (ii)). The routes are not finalized, but the approximate length is known by the distance among the tiles. For example, a tile may have 12 tracks. So, global router will assign 12 tracks to each tile. But, the final assignment of the track is not done during global routing.

Detailed routing: Using detailed routing, the router determines the exact route for each net by searching within tile-to-tile path. It involves providing actual physical path to a net from one connected pin to another (as shown in figure (iii)). Hence, detailed routed wire represents actual resistance, capacitance and length of the net.

What router has to take care: While routing, a router has to pertain to specific constraints like timing budget for each critical net, also called performance constraints. There are other performance constraints too – like the router has to route in such a way as not to cause any crosstalk issues. There should not be any antenna issues. Also, there are a set of design rules like resistance, capacitance, wire/via width/spacing that need to be followed. For instance, technology may be limited by the minimum feature size it can have. Like, in 65 nm technology, the foundry cannot have wire widths less than 65 nm. So, the wires in the design have to be constrained to have wire length greater than 65 nm. Similarly, there are foundry specific constraints for other parameters. Each of these is termed as a Design Rule. Any violation pertaining to these in the design is termed as DRC (Design Rule Check) violation.

Grid based and gridless routing: In grid based routing, a routing grid is superimposed on routing region. Routing takes place along the grid lines. The space between adjacent grid lines is called wire pitch and is equal to sum of minimum width of wires and spacing of wires. On the other hand, any model that does not follow grid based routing is termed as gridless routing model. This model is suitable for wire sizing and perturbation and is more complex and slower than grid based routing. In other words, grid based routing is much easier and simpler in implementation.


Wire pitch is the sum of wire distance and wire width. Or we can say it is the distance between two grid lines


We have discussed here routing in VLSI designs. Although many advanced tools are available for achieving the purpose, most of these compromise with the quality of results to save run-time. Almost all tools have the option of routing with more emphasis on meeting timing or congestion. With most of the tools, in present day multi-million gate designs, perfect DRC-free routing (without opens and shorts) is generally not obtained in first pass. You have to route incrementally a few times to achieve the same.
 

Also read:


Lockup latch – principle, application and timing

What are lock-up latches: Lock-up latch is an important element in scan-based designs, especially for hold timing closure of shift modes. Lock-up latches are necessary to avoid skew problems during shift phase of scan-based testing. A lock-up latch is nothing more than a transparent latch used intelligently in the places where clock skew is very large and meeting hold timing is a challenge due to large uncommon clock path. That is why, lockup latches are used to connect two flops in scan chain having excessive clock skews/uncommon clock paths as the probability of hold failure is high in such cases. For instances, the launching and capturing flops may belong to two different domains (as shown in figure below). Functionally, they might not be interacting. Hence, the clock of these two domains will not be balanced and will have large uncommon path. But in scan-shift mode, these interact shifting the data in and out. Had there been no lockup latches, it would have been very difficult for STA engineer to close timing in a scan chain across domains. Also, probability of chip failure would have been high as there a large uncommon path between the clocks of the two flops leading to large on-chip-variations. That is why; lockup latches can be referred as as the soul mate of scan-based designs.

Lockup latches are needed where there is need to fix hold due to large skew between clock signals for launch and capture flops

Figure 1 : Lockup latches - the soul mate of scan-based designs


Where to use a lock-up latch: As mentioned above, a lock-up latch is used where there is high probability of hold failure in scan-shift modes. So, possible scenarios where lockup latches are to be inserted are:

  • Scan chains from different clock domains: In this case, since, the two domains do not interact functionally, so both the clock skew and uncommon clock path will be large.
  • Flops within same domain, but at remote places: Flops within a scan chain which are at remote places are likely to have more uncommon clock path. 
In both the above mentioned cases, there is a great chance that the skew between the launch and capture clocks will be high. There is both the probability of launch and capture clocks having greater latency. If the capture clock has greater latency than launch clock, then the hold check will be as shown in timing diagram in figure 3. If the skew difference is large, it will be a tough task to meet the hold timing without lockup latches.

A timing path crossing from one domain to another

Figure 2: A path crossing from domain 1 to domain 2 (scope for a lock-up latch insertion)

Waveform showing the skew between launch and capture clocks, resulting in hold violation

Figure 3: Timing diagram showing setup and hold checks for path crossing from domain 1 to domain 2

Positive or negative level latch?? It depends on the path you are inserting a lock-up latch. Since, lock-up latches are inserted for hold timing; these are not needed where the path starts at a positive edge-triggered flop and ends at a negative edge-triggered flop. It is to be noted that you will never find scan paths originating at positive edge-triggered flop and ending at negative edge-triggered flop due to DFT specific reasons. Similarly, these are not needed where path starts at a negative edge-triggered flop and ends at a positive edge-triggered flop. For rest two kinds of flop-to-flop paths, lockup latches are required. The polarity of the lockup latch needs to be such that it remains open during the inactive phase of the clock. Hence,

  • For flops triggering on positive edge of the clock, you need to have latch transparent when clock is low (negative level-sensitive lockup latch)
  • For flops triggering on negative edge of the clock, you need to have latch transparent when clock is high (positive level-sensitive lockup latch)
Who inserts a lock-up latch: These days, tools exist that automatically add lockup latches where a scan chain is crossing domains. However, for cases where a lockup latch is to be inserted in an intra-domain scan chain (i.e. for flops having uncommon path), it has to be inserted during physical implementation itself as physical information is not feasible during scan chain implementation (scan chain implementation is carried out at the synthesis stage itself).

Which clock should be connected to lock-up latch: There are two possible ways in which we can connect the clock pin of the lockup latch inserted. It can either have same clock as launching flop or capturing flop. Connecting the clock pin of lockup latch to clock of capturing flop will not solve the problem as discussed below.
  •  Lock-up latch and capturing flop having the same clock (Will not solve the problem): In this case, the setup and hold checks will be as shown in figure 5. As is apparent from the waveforms, the hold check between domain1 flop and lockup latch is still the same as it was between domain 1 flop and domain 2 flop before. So, this is not the correct way to insert lockup latch.


It is not appropriate to connect the capture flop's clock to the lockup latch as hold check will be the same

Figure 4: Lock-up latch clock pin connected to clock of capturing flop

Waveform showing the inability of connecting capture flop's clock in meeting hold

Figure 5: Timing diagrams for figure 4


  •  Lock-up latch and launching flop having the same clock: As shown in figure 7, connecting the lockup latch to launch flop’s clock causes the skew to reduce between the domain1 flop and lockup latch. This hold check can be easily met as both skew and uncommon clock path is low. The hold check between lockup latch and domain2 flop is already relaxed as it is half cycle check. So, we can say that the correct way to insert a lockup latch is to insert it closer to launching flop and connect the launch domain clock to its clock pin.

The correct way to connect the clock to lockup latch is to connect it with the clock coming at launch flop

Figure 6: Lock-up latch clock pin connected to clock of launch flop

Waveform for the connection of clock pin of lockup latch to launch flop's clock

Figure 7: Waveforms for figure 6


Why don’t we add buffers: If the clock skew is large at places, it will take a number of buffers to meet hold requirement. In normal scenario, the number of buffers will become so large that it will become a concern for power and area. Also, since skew/uncommon clock path is large, the variation due to OCV will be high. So, it is recommended to have a bigger margin for hold while signing it off for timing. Lock-up latch provides an area and power efficient solution for what a number of buffers together will not be able to achieve.

Advantages of inserting lockup latches:
  • Inserting lock-up latches helps in easier hold timing closure for scan-shift mode
  • Robust method of hold timing closure where uncommon path is high between launch and capture flops
  • Power efficient and area efficient
  • It improves yield as it enables the device to handle more variations.
Lockup registers: Instead of latches, registers can also be used as lockup elements; however, they have their own advantages and disadvantages. Please refer to Lockup latches vs. lockup registers : what to chose for a comparative study of using lockup latches vs lockup registers.

References:
1)  Why not add buffer but lockup latch” - http://www.edaboard.com/thread82364.html

Also read: