FPGA Routing is a way of deciding the amount of area used by wire segments and programmable switches as compared to area consumed by logic blocks. A

Allows logic block I/O to be connected to a larger circuit

Long paths - propagation delays

Goals for efficient routing

• Get it all routed
• Avoid congestion
• Minimal delay

Problems

Lack of routing resources. Whilst we could use routing trees, these trees become a critical path and become a source of resource constraints in themselves.

"Rip-up and retry" algorithm proposed - but the success of a route is dependent on both the choice of which nets are routed, but also the order of rerouting

Other variations

• blame factor
• global router
• delay

Coarse Graph Expansion Algorithm (CGE)

Background Information

Cost Function Design

A routing conflict

Algorithm - LocusRoute Global Routing

Notes: "two point connection" = logic block

Post operation

We need to choose the best wiring segment to implement the connection

Detailed Routing

Connection Formation

Controlling Capacity

Pruning Algorithm

Iterative Approach to Design

• Start with small value parameters, if not possible / timeout, then increase parameters

Pathfinder Algorithm

The global router instructs the signal router to select a path from a source to a sink.
Creates a MST tree (hence shortest paths)

Slack Ratio

Ratio = Longest path used by the resource : Longest path in the graph

Ratio ~= 1 -> Higher priority since it is more of a critical path

Cost Function

A_ij = Slack ratio from i to j

Negotiated Congestion/Delay (NCD) Pseudocode