# Kite - Detailed Router

Public Member Functions | Static Public Member Functions | List of all members
TrackSegment Class Reference

Derived Katabatic::AutoSegment for the router. More...

Inheritance diagram for TrackSegment:
[legend]

## Public Member Functions
virtual bool | isFixed () const
virtual bool | isHorizontal () const
virtual bool | isVertical () const
virtual bool | isLocal () const
virtual bool | isGlobal () const
virtual bool | isBipoint () const
virtual bool | isTerminal () const
virtual bool | isStrap () const
virtual bool | isSlackened () const
virtual bool | isDogleg () const
virtual bool | canDogleg ()
virtual bool | canDogleg (Interval)
virtual bool | canDogleg (Katabatic::GCell *, unsigned int flags=0)
virtual float | getMaxUnderDensity (unsigned int flags) const
virtual unsigned long | getId () const
virtual unsigned int | getDirection () const
virtual Net * | getNet () const
virtual const Layer * | getLayer () const
virtual unsigned long | getFreedomDegree () const
virtual unsigned int | getDoglegLevel () const
virtual TrackElement * | getNext () const
virtual TrackElement * | getPrevious () const
virtual TrackElement * | getParent () const
virtual DbU::Unit | getAxis () const
virtual Interval | getFreeInterval () const
virtual Interval | getSourceConstraints () const
virtual Interval | getTargetConstraints () const
virtual DataNegociate * | getDataNegociate (unsigned int flags=KtDataSelf) const
virtual TrackElement * | getCanonical (Interval &)
virtual size_t | getGCells (Katabatic::GCellVector &) const
virtual TrackElement * | getSourceDogleg ()
virtual TrackElement * | getTargetDogleg ()
virtual TrackElements | getPerpandiculars ()
virtual void | setTrack (Track *)
virtual void | updateFreedomDegree ()
virtual void | setDoglegLevel (unsigned int)
virtual void | swapTrack (TrackElement *)
virtual void | reschedule (unsigned int level)
virtual void | detach ()
virtual void | invalidate ()
virtual void | revalidate ()
virtual void | setAxis (DbU::Unit, unsigned int flags)
virtual TrackElement * | makeDogleg ()
virtual TrackElement * | makeDogleg (Interval, unsigned int &flags)
virtual void | _postDoglegs (TrackElement *&perpandicular, TrackElement *&parallel)
virtual bool | _check () const
Public Member Functions inherited from TrackElement
bool | isCreated () const
bool | isInvalidated () const
bool | isBlockage () const
bool | isLocked () const
bool | isRouted () const
bool | hasSourceDogleg () const
bool | hasTargetDogleg () const
bool | canRipple () const
Track * | getTrack () const
size_t | getIndex () const
Box | getBoundingBox () const
DbU::Unit | getSourceU () const
DbU::Unit | getTargetU () const
DbU::Unit | getLength () const
Interval | getCanonicalInterval () const
void | setFlags (unsigned int)
void | unsetFlags (unsigned int)
void | setIndex (size_t)
virtual void | incOverlapCost (Net *, TrackCost &) const
bool | makeDogleg (Katabatic::GCell *)

## Static Public Member Functions
static TrackElement * | create (AutoSegment *, Track *, bool &created)
Static Public Member Functions inherited from TrackElement
static SegmentOverlapCostCB * | setOverlapCostCB (SegmentOverlapCostCB *)

## Detailed Description

Derived Katabatic::AutoSegment for the router.

Fig 1: TrackSegment Context

We create one TrackSegment per aligned Katabatic::AutoSegment set, the TrackSegment is associated to the canonical one of the set.

To provide some speedup, the full extention of the aligned segment set is computed once and stored in the TrackSegment itself. The drawback beeing that whenever one segment from the aligned set has it's extention modified, the full extention must be recomputed.

# Lazy Revalidate

When the TrackSegment::revalidate() method is called, it only update the cached size of the segment (from the AutoSegment set of aligneds) and the track into which it may be inserted.

The associated DataNegociate and RoutingEvent are not updated.

- The RoutingEvent will be updated when it's key is updated, typically during a requeueing operation and in the SegmentFsm constructor. This should be optimized in the future.
- The DataNegociate is updated only in the SegmentFsm constructor. This is the most costly of the two updates as it perform a perpandicular & parallel connexity exploration.

# Dogleg Management

The basic AutoSegment::canDogleg() method is declined in three more dedicated methods in this class:

- TrackSegment::canDogleg(), for locals only, check if a break is possible, never break a segment more than once (to avoid fragmentation).
- TrackSegment::canDogleg(Katabatic::GCell*,unsigned int flags) for globals, check that the segment is breakable in the desired GCell. Never break twice in the first/last GCell (fragmentation limitation), but may reuse an already existing dogleg.
- TrackSegment::canDogleg(Interval), for locals only, direct proxy for the AutoSegment method. Never allow more than one break.

Relationship between AutoSegment and TrackSegment

Figure 2 below, shows an example of dogleg creation:

- At the Katabatic level, AutoSegment `id:12` is broken. Thus the creation of AutoSegments `id:20` and `id:21`. The orignal TrackSegment (canonical AutoSegment `id:10`) remains on the right side (target) of the break.
- But, because the canonical of the former aligned AutoSegment set ``(10,11,12,13,14) was on the right side of the break, the new parallel TrackSegment will be created on the `left` side, associated to the newly promoted canonical AutoSegment `id:12`.

Fig 2: Dogleg Management

The TrackSegment::_postDoglegs() method called by all flavors of TrackSegment::makeDogleg() methods is responsible for creating new TrackSegments for the new doglegs (there may be more than one), it also update the dogleg level and source/target dogleg flags.

This section is not finished. I need to review the parent and doglevel numbering management. There seems to be a risk of infinite fragmentation as the numbering of the original segment is not increased, we should create a break counter separate from deepness.

# Global, Weak Global and Local Segments

There's a slight semantic change between Katabatic and Kite about what is local and what is local. This is due to how we consider the intermediate status of WeakGlobal.

A `WeakGlobal` segment is a local segment which is aligned with a global (though a VTee or an HTee contact).

In Katabatic a local segment is one that is not `Global`, a local segment can be both `Local` and `WeakGlobal`.

In Kite a local segment is one that is neither `Global` or `WeakGlobal`. The `WeakGlobal` sides with `Global` unlike in Katabatic.

## Member Function Documentation

## ◆ create()

static TrackSegment * create | ( | AutoSegment * | segment,
|  | Track * | track,
|  | bool & | created
| ) |  |
| static

Parameters

  segment | The Katabatic AutoSegment to decorate.
  track | A Track into which insert the TrackSegment (may be `NULL`).
  created | This flag is sets is a new TrackSegment has be created.

Returns
  A TrackSegment wrapped around an AutoSegment.

Constructor mainly used at loading time to decorate the Katabatic data-base with the router attributes.

Referenced by NegociateWindow::createTrackSegment().

## ◆ isFixed()

bool isFixed | ( |  | ) | const
| virtual

See also: Katabatic::AutoSegment::isFixed().

Reimplemented from TrackElement.

Referenced by TrackSegment::canDogleg().

## ◆ isHorizontal()

bool isHorizontal | ( |  | ) | const
| virtual

See also: Katabatic::AutoSegment::isHorizontal().

Implements TrackElement.

Referenced by TrackSegment::getGCells().

## ◆ isVertical()

bool isVertical | ( |  | ) | const
| virtual

See also: Katabatic::AutoSegment::isVertical().

Implements TrackElement.

## ◆ isLocal()

bool isLocal | ( |  | ) | const
| virtual

See also: Katabatic::isLocal().

Reimplemented from TrackElement.

Referenced by TrackSegment::_postDoglegs(), and TrackSegment::canDogleg().

## ◆ isGlobal()

bool isGlobal | ( |  | ) | const
| virtual

See also: Katabatic::AutoSegment::isGlobal().

Reimplemented from TrackElement.

## ◆ isBipoint()

bool isBipoint | ( |  | ) | const
| virtual

See also: Katabatic::AutoSegment::isBipoint().

Reimplemented from TrackElement.

## ◆ isTerminal()

bool isTerminal | ( |  | ) | const
| virtual

See also: Katabatic::AutoSegment::isTerminal().

Reimplemented from TrackElement.

## ◆ isStrap()

bool isStrap | ( |  | ) | const
| virtual

See also: Katabatic::AutoSegment::isStrap().

Reimplemented from TrackElement.

## ◆ isSlackened()

bool isSlackened | ( |  | ) | const
| virtual

See also: Katabatic::AutoSegment::isSlackened().

Reimplemented from TrackElement.

Referenced by TrackSegment::canDogleg().

## ◆ isDogleg()

bool isDogleg | ( |  | ) | const
| virtual

See also: Katabatic::isDogleg().

Reimplemented from TrackElement.

## ◆ canDogleg() [1/3]

bool canDogleg | ( |  | ) |
| virtual

See also: AutoSegment::canDogleg(). At Kite level, this variant of the method will apply only on local segments and the segment must not already have a source or target dogleg.

Reimplemented from TrackElement.

## ◆ canDogleg() [2/3]

bool canDogleg | ( | Interval |  | ) |
| virtual

See also: AutoSegment::canDogleg(). At Kite level, this variant of the method will apply only on local segments and the segment must not already have a source or target dogleg.

Reimplemented from TrackElement.

## ◆ canDogleg() [3/3]

bool canDogleg | ( | Katabatic::GCell * | doglegGCell,
|  | unsigned int | flags = `0`
| ) |  |
| virtual

See also: AutoSegment::canDogleg(). At kite level, this variant of the method is mainly targeted to global segment. For local segment it behave like TrackElement::canDogleg(Interval). For global segment, make the break in the requested GCell `doglegGCell`. If it's in the first or last GCell and there is already a dogleg, allow to reuse it if `flags` contains Kite::KtAllowDoglegReuse.

Reimplemented from TrackElement.

## ◆ getMaxUnderDensity()

float getMaxUnderDensity | ( | unsigned int | flags | ) | const
| virtual

Returns: The maximum density of all the GCells under this element.

Reimplemented from TrackElement.

## ◆ getId()

unsigned long getId | ( |  | ) | const
| virtual

Returns
  The `Id` of the supporting AutoSegment, if there is any. Zero otherwise.

Reimplemented from TrackElement.

Referenced by TrackSegment::detach().

## ◆ getDirection()

unsigned int getDirection | ( |  | ) | const
| virtual

Returns
  The direction of the supporting element (should match the preferred direction of the Track).

Implements TrackElement.

Referenced by TrackSegment::getSourceDogleg(), and TrackSegment::getTargetDogleg().

## ◆ getNet()

Net * getNet | ( |  | ) | const
| virtual

Returns: The Net associated to the element (may be `NULL`).

Implements TrackElement.

Referenced by TrackSegment::getFreeInterval(), TrackSegment::getNext(), and TrackSegment::getPrevious().

## ◆ getLayer()

const Layer * getLayer | ( |  | ) | const
| virtual

Returns: The Layer of the element (should match the one of the Track).

Implements TrackElement.

## ◆ getFreedomDegree()

unsigned long getFreedomDegree | ( |  | ) | const
| virtual

Returns: The degree of freedom of the element. It is used as a priority value when sorting TrackElement (in RoutingEvent).

Returns: The degree of freedom of the element. It is used as a priority value when sorting TrackElement (in RoutingEvent).

Currently, it is the slack of the Katabatic::AutoSegment.

Reimplemented from TrackElement.

## ◆ getDoglegLevel()

unsigned int getDoglegLevel | ( |  | ) | const
| virtual

Returns: The deepness of the dogleg.

Reimplemented from TrackElement.

Referenced by TrackSegment::canDogleg().

## ◆ getNext()

TrackElement * getNext | ( |  | ) | const
| virtual

Returns: The next TrackElement, on the same track and of a different net. See also: Track::getNext().

Reimplemented from TrackElement.

## ◆ getPrevious()

TrackElement * getPrevious | ( |  | ) | const
| virtual

Returns: The previous TrackElement, on the same track and of a different net. See also: Track::getPrevious().

Reimplemented from TrackElement.

## ◆ getParent()

TrackElement * getParent | ( |  | ) | const
| virtual

Returns: The TrackElement from which the dogleg has been created, if any.

Reimplemented from TrackElement.

Referenced by TrackSegment::getDataNegociate().

## ◆ getAxis()

DbU::Unit getAxis | ( |  | ) | const
| virtual

Returns: The axis position of the element (must be the same as the Track).

Implements TrackElement.

## ◆ getFreeInterval()

Interval getFreeInterval | ( |  | ) | const
| virtual

Returns: The greatest free interval enclosing this element.

Reimplemented from TrackElement.

## ◆ getSourceConstraints()

Interval getSourceConstraints | ( |  | ) | const
| virtual

See also: Katabatic::AutoSegment::getSourceConstraints().

Reimplemented from TrackElement.

## ◆ getTargetConstraints()

Interval getTargetConstraints | ( |  | ) | const
| virtual

See also: Katabatic::AutoSegment::getTargetConstraints().

Reimplemented from TrackElement.

## ◆ getDataNegociate()

DataNegociate * getDataNegociate | ( | unsigned int | flags = `KtDataSelf` | ) | const
| virtual

Returns: The additional data-structure supplied by the routing algorithm.

Reimplemented from TrackElement.

Referenced by TrackSegment::_postDoglegs(), and TrackSegment::swapTrack().

## ◆ getCanonical()

TrackElement * getCanonical | ( | Interval & | i | ) |
| virtual

Inner working still unclear to myself.

Reimplemented from TrackElement.

## ◆ getGCells()

size_t getGCells | ( | Katabatic::GCellVector & | gcells | ) | const
| virtual

Returns: The table of Katabatic::GCell underneath the element whole span.

Reimplemented from TrackElement.

Referenced by TrackSegment::canDogleg().

## ◆ getSourceDogleg()

TrackElement * getSourceDogleg | ( |  | ) |
| virtual

Returns: The source part of the segment from which the dogleg has been created.

Reimplemented from TrackElement.

## ◆ getTargetDogleg()

TrackElement * getTargetDogleg | ( |  | ) |
| virtual

Returns: The target part of the segment from which the dogleg has been created.

Reimplemented from TrackElement.

## ◆ getPerpandiculars()

TrackElements getPerpandiculars | ( |  | ) |
| virtual

Returns: The collection of all element perpandiculars to this one.

Reimplemented from TrackElement.

## ◆ setTrack()

void setTrack | ( | Track * | track | ) |
| virtual

Insert the element into `track`, also used as an insertion marker.

Reimplemented from TrackElement.

Referenced by TrackSegment::detach(), and TrackSegment::swapTrack().

## ◆ updateFreedomDegree()

void updateFreedomDegree | ( |  | ) |
| virtual

Update, from the element characteristics, it's degree of freedom.

Reimplemented from TrackElement.

## ◆ setDoglegLevel()

void setDoglegLevel | ( | unsigned int | level | ) |
| virtual

Sets the level of dogleg of the element.

Reimplemented from TrackElement.

## ◆ swapTrack()

void swapTrack | ( | TrackElement * | other | ) |
| virtual

Swap the tracks of `this` and `other`.

Reimplemented from TrackElement.

## ◆ reschedule()

void reschedule | ( | unsigned int | level | ) |
| virtual

If the TrackElement has already an event scheduled, change the level of this event, otherwise create a new event.

See also: NegotiateWindow::rescheduleEvent().

Reimplemented from TrackElement.

Referenced by TrackSegment::_postDoglegs().

## ◆ detach()

void detach | ( |  | ) |
| virtual

Remove the link from the TrackElement to it's owning Track, marking it for removal. The removal from the Track's vector is managed by the Track itself during the Session revalidation stage.

Reimplemented from TrackElement.

## ◆ invalidate()

void invalidate | ( |  | ) |
| virtual

See also: AutoSegment::invalidate().

Reimplemented from TrackElement.

Referenced by TrackSegment::create(), and TrackSegment::setAxis().

## ◆ revalidate()

void revalidate | ( |  | ) |
| virtual

Actualize the TrackSegment characteristics from the supporting elements (set of AutoSegment).

This method do not update the DataNegociate or the RoutingEvent. This is a lazy update delayed until the constructor of SegmentFsm is called. (see Lazy Revalidate).

Reimplemented from TrackElement.

## ◆ setAxis()

void setAxis | ( | DbU::Unit | ,
|  | unsigned int | flags
| ) |  |
| virtual

Sets the axis of the TrackElement.

Reimplemented from TrackElement.

## ◆ makeDogleg() [1/2]

TrackElement * makeDogleg | ( |  | ) |
| virtual

Create a dogleg on the source end of the TrackSegment. Put the dogleg axis on the source To be further reviewed.

See also: Dogleg management.

Post-processing done by TrackSegment::_postDoglegs().

Reimplemented from TrackElement.

## ◆ makeDogleg() [2/2]

TrackElement * makeDogleg | ( | Interval | interval,
|  | unsigned int & | flags
| ) |  |
| virtual

See also: AutoSegment::makeDogleg(), Dogleg management, the return flags from this method are returned through the `flags` variable.

Post-processing done by TrackSegment::_postDoglegs().

Reimplemented from TrackElement.

## ◆ _postDoglegs()

TrackSegment * _postDoglegs | ( | TrackElement *& | perpandicular,
|  | TrackElement *& | parallel
| ) |  |
| virtual

Post-process to be called inside the various dogleg creation or slacken methods. Iterate through the newly created AutoSegments to create, for the perpandicular and the new parallel associateds TrackSegments. Also sets the dogleg levels and flags of the newly created elements.

The session dogleg reset is called at the end of this method. The `perpandicular` and `parallel` references to pointers contains the newly created segments for the last dogleg. If more than one was created, you cannot access them (the need has not arised yet).

Reimplemented from TrackElement.

Referenced by TrackSegment::makeDogleg().

## ◆ _check()

bool _check | ( |  | ) | const
| virtual

Check the coherency of the element. For a TrackSegment:

- The supporting AutoSegment the canonical one of the set.
- The cached `min` & `max` values are identical to the computed ones.

Returns: true on success.

Reimplemented from TrackElement.

The documentation for this class was generated from the following files:

- TrackSegment.h
- TrackSegment.cpp
- TrackSegment.dox

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