# Kite - Detailed Router

Notes

# Summary

- Various Things to Remeber
- Pending Modifications
- Modifications History
- Changes in the general architecture
  - Changes in KiteEngine class design
  - Changes in DataNegociate class design
  - Changes in TrackElement class design
  - Changes in TrackSegment class design
  - Changes in AutoSegment class design
  - Changes in AutoContact class design
- Bug Solving Memento
- Evaluation with Cadence NanoRoute

# Various Things to Remember

- Determinism checking. The trace level to get only determinism related log is `500`. Each line for the determinism is prepended with 'Deter|', possible with some leading spaces.
- The router only sees/manages the aligned segment sets (through a pseudo- decorator on their canonical segment). So the non-canonical segments and the contacts should not be handled at all at this level.
- Do do confuse the Session::Event, events that modificate the state of the Kite database (insert, move or remove TrackSegment in Track) and the RoutingEvent class which request that a segment must be processed.
- In the various processing method of RoutingEvent, when a TrackSegment can be inserted inside a Track a Session::Event is generated but no further RoutingEvent, this end the placement processus of segment (until it is ripped-up).
- AutoSegment do not invalidate their S/T anchor contacts.
- AutoContact invalidate their anchored upon AutoSegment.
- Now that the Hurricane database is deterministic, the router seems to be likewise.
- Reduce/raise mechanism. To manage same layer dogleg this mechanism has been implemented. When a candidate dogleg perpandicular segment length shrink below one pitch it is removed from any track to become invisible. Conversely, when a reduced segment length expand over one pitch generate a new RoutingEvent to insert it. All this is managed in the Session::revalidate() method.

# Pending Modifications

- In SegmentAction::doAction(), completly disable the movement of TrackSegment on it's target Track axis. This should not be needed as, if the algorithm as worked correctly, the next time it's RoutingEvent is processed, the target Track will have a free space to insert into. Then the Track insertion will set the TrackSegment axis.
- Has to complete the lazy evaluation of the TrackSegment / DataNegociate / RoutingEvent. There is still some redundancy when the key of the RoutingEvent is updated.
- In AutoContact::updateTopology() & AutoContact::updateGeometry() we could avoid to systematically run through the Hooks to cache the connected segments. This can be done once at the first call of either method (whichever comes first) on the first revalidate. Afterwards the cache can be updated only by AutoContact::updateTopology().
- The canonization is done in two places, directly on a set of aligneds AutoSegments through AutoSegment::canonize() and for the whole net Session::_canonize(), which is called after the initial creation and each time the topology is modificated. The later may be suppressed if we uses more intelligently the former, and gain some more speedup.

# Modifications History

## Changes in the general architecture

- Lazy Update. Update of DataNegociate and RoutingEvent are now delayed until the event is processed, and systematically done at this point. Thus, the explicit invalidation of those objects is no longer needed. The revalidation is no longer triggered by the revalidation of TrackSegment.

## Changes in KiteEngine class design

- Suppress the lookup table of Hurricane::Segment toward TrackSegment. Instead uses the Observer mecanism between Katabatic::AutoSegment and TrackSegment.

## Changes in DataNegociate class design

- Merge in the separate class `Cost`.
- Suppress the `SlackState::Desalignate`, due to the simplificated structure of the AutoSegment/AutoContacts (no more collapseds, or forced alignements).
- Displace the computation and caching of the perpandiculars and perpandicular free interval from RoutingEvent into DataNegociate. Allows code factorization with the attractors computation, and data size reduction as there is exaclty one DataNegociate but there may be more than one RoutingEvent for the same TrackSegment.

## Changes in TrackElement class design

- Due to the simplificated structure of the Katabatic contacts (terminal, turn, vtee & htee), there's no longer collapsed AutoSegment or expandable contacts. The desalignate feature, relaxing constraints due to collapsed segments or contacts with more than three segments, is no longer implemented. Have to redevelop a method to break long segments linked by HTee or VTee.

## Changes in TrackSegment class design

- The method `TrackSegment::_postModify()` is merged with TrackSegment::_postDoglegs() as, in the context of TrackSegment the only used topological modifications goes through the creation of one or more dogleg.

## Changes in AutoSegment class design

- In AutoSegment::_makeDogleg(), update the local/global status of the involved AutoSegment and re-canonize only what is necessary. Thus, guarantee that the net's topology is still valid after this method call and no topological update is needed at Session level (should be much faster). In this method, the code sharing between AutoHorizontal and AutoVertical can still be increased (update mechanisms are identicals).
- The `id` support is now also implemented at Hurricane level. We may choose to use as a replacement of the one already present in AutoSegment. But in that case, we at least must cache the id in the AutoSegment. So we will not gain in memory footprint, the only benefit would be to have coherent id number throughout all the tools, but the sequentiality will be lost (this may not be a big issue).

## Changes in AutoContact class design

- In AutoSegment::invalidate(), no longer uses collection to walk through attached AutoSegment, directly uses the cache. Much simple and efficient as we exactly know what is attached on every kind of contact.

# Bug Solving Memento

LUT lookup change: When breaking a TrackSegment, the break may not occurs in the associated canonical AutoSegment. In that case the `dogleg[O]` will not match the one that is looked up for the broken (canonical) segment. Thus it was not a bug but a misunderstanding...

Overlap of perpandiculars after a dogleg creation: The axis of the new parallel was not set to the axis of it's parent. This was due to the uses of AutoSegment::setAxis() in AutoHorizontal::_makeDogleg() which silently do nothing on non-canonical AutoSegment, and at this point, the re-canonisation did not yet take place. Now Uses AutoSegment::_setAxis() the atomic variant wich works inconditionnaly.

# Evaluation with Cadence NanoRoute

To perform a comparison with NanoRoute the procedure is as follow:

- Export the design in Alliance `DEF` format. It will generate both `DEF` file and the supporting `LEF` file containing the technology and the abstract of all the standard cell of the design. As Alliance uses symbolic units (lambda), they are translated with the simple rule: 1 lambda == 1 micron.
- Run the commands in NanoRoute:
  - `loadLefFile design.lef`
  - `loadDefFile design.def`
  - `generateTracks`
  - `generateVias`
  - `setNanoRouteMode -quiet -drouteFixAntenna 0`
  - `setNanoRouteMode -quiet -drouteStartIteration default`
  - `setNanoRouteMode -quiet -routeTopRoutingLayer default`
  - `setNanoRouteMode -quiet -routeBottomRoutingLayer 2`
  - `setNanoRouteMode -quiet -drouteEndIteration default`
  - `setNanoRouteMode -quiet -routeWithTimingDriven false`
  - `setNanoRouteMode -quiet -routeWithSiDriven false`
  - `routeDesign -globalDetail`
- To perform as fair a comparison as possible, those commands disable antenna effect protection and disable the use of the `M1` as a routing layer (`-routeBottomRoutingLayer 2`). Those commands are issued through the graphical interface of NanoRoute.

To see the resulting layout, do not forget to switch the view mode.

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