# Kite - Detailed Router

Algorithm Overview

Description of the algorithm. More...

Description of the algorithm.

The algorithm top-level is implemented in the `NegociateWindow`.

First step : NegociateWindow::_loadRouting()

1. Load routing wires (`AutoSegment`) from `KatabaticEngine` inside the Kite `GCell's`. Then update the `GCell's` density.
2. Sort the `GCell's` according to decreasing density (denser `GCell's` are to be routed first).

3. Agglomerate clusters of contiguous GCell's whose density is superior to 0.7 to the seed GCell. See `GCellRoutingSet` for the mechanism.

   GCellRoutingSet receive an increasing order number. The higher the order the lower the density. This order is transmitted to the `TrackSegment` of the `GCellRoutingSet` to be taken into account by the track cost function.

Second step : `NegociateWindow::_runOnGCellRoutingSet()`

For each `GCellRoutingSet` in decreasing density, negociate the set of associated `TrackSegment`.

1. Build a `RoutingEventQueue` from the list of `TrackSegment`. The queue is responsible for allocating the `RoutingEvent` associated to each `TrackSegment`.
2. The queue is sorted according to the "event level" then to the priority, which is for now the slack of the `TrackSegment`. That is, constrained `TrackSegment` are routed first.

3. The queue is processed till it's empty (no unprocessed `RoutingEvent` remains).

   Processing a `RoutingEvent` is trying to insert a `TrackSegment` in a suitable Track. We proceed as follow :

   - The maximum ripup count for the to be inserted segment has been reached. Issue a severe warning and left unrouted this `TrackSegment` (for now).
   - Compute the Tracks in which the `TrackSegment` can be inserted, then compute the insertion cost in each one. The candidates are ordered by the insertion cost.

   - Now consider the lower cost `Track`. If there is a free interval for the `TrackSegment`. Issue a `Session::addInsertEvent()` then finish.

     If there is a "soft overlap", that is the overlaping `TrackSegment` already in the `Track` could be shrunk either to the left or the right so the new `TrackSegment` can be inserted. This is managed by `RoutingEvent::_setAside()`, for each soft overlaping `TrackSegment`, gets its perpandiculars and issue a displacement request for all of them. That is, re-post a `RoutingEvent` with updated constraints and remove the perpandicular from it's Track if it has already been routed. Note that no request is issued for the overlaping `TrackSegment` itself has it do not change of Track.

     If there is a "hard overlap", that is the two `TrackSegment` cannot share the same `Track`, remove the previous one from the `Track` and re-post a `RoutingEvent`. Note that, the cost object should have selected a `TrackSegment` which could be ripped-up. Otherwise the `Track` would'nt even be a candidate.

   When a TrackSegment is riped up, it is re-routed immediately afterward. This is done by increasing his event level.

Generated by doxygen 1.8.14 on Mon Feb 3 2020 | Return to top of page

Kite - Detailed Router | Copyright © 2008-2016 UPMC. All rights reserved