# Kite - Detailed Router

Public Types | Public Member Functions | List of all members
Manipulator Class Reference

Handle TrackElement ripup & topological modifications. More...

## Public Types
enum | FunctionFlag { ToRipupLimit = 0x0001, AllowExpand = 0x0002, NoExpand = 0x0004, PerpandicularsFirst = 0x0008, ToMoveUp = 0x0010, AllowLocalMoveUp = 0x0020, AllowTerminalMoveUp = 0x0040, AllowShortPivotUp = 0x0080, NoDoglegReuse = 0x0100, LeftAxisHint = 0x0200, RightAxisHint = 0x0400, NotOnLastRipup = 0x0800 }

## Public Member Functions
| Manipulator (TrackElement *, SegmentFsm &)
TrackElement * | getSegment () const
DataNegociate * | getData () const
RoutingEvent * | getEvent () const
bool | canRipup (unsigned int flags=0) const
bool | isCaged (DbU::Unit) const
bool | ripup (unsigned int type, DbU::Unit axisHint=0)
bool | ripupPerpandiculars (unsigned int flags=0)
void | repackPerpandiculars ()
bool | ripple ()
bool | minimize ()
bool | slacken (unsigned int flags=KbNoFlags)
bool | pivotUp ()
bool | pivotDown ()
bool | moveUp (unsigned int flags=0)
bool | makeDogleg ()
bool | makeDogleg (DbU::Unit)
bool | makeDogleg (Interval)
bool | relax (Interval, unsigned int flags=AllowExpand)
bool | insertInTrack (size_t)
bool | shrinkToTrack (size_t, unsigned int flags=0, DbU::Unit leftAxisHint=0, DbU::Unit rightAxisHint=0)
bool | forceToTrack (size_t)
bool | forceOverLocals ()

## Detailed Description

Handle TrackElement ripup & topological modifications.

# Manipulator Structure

A Manipulator basically binds together a TrackElement, it's DataNegociate and RoutingEvent (cached for fast access), and a SegmentFsm.

The TrackElement may differs from the one of the SegmentFsm. This can occurs when manipulating perpandiculars or segments from other nets in conflict. For example: Manipulator::isCaged().

In the following documentation, the segment which is associated to the SegmentFsm will be called the reference segment.

# Delayed Modifications

It is important to note that when a Manipulator is called to modificate a TrackElement, nothing is actually done by the Manipulator itself. Instead, the Manipulator create the relevant SegmentAction (s) that are stored in the SegmentFsm. The action themselves are done at the end of the SegmentFsm lifecycle (wrapped inside a Session).

This is not true! When dogleg are created, the topology is immediatly modificated. That way of doing must be clarified.

## Member Enumeration Documentation

## ◆ FunctionFlag

enum FunctionFlag

The various flags that can be passed to the Manipulator methods.

Enumerator
ToRipupLimit | The ripup limit must be immediatly to it's limit for the current state.
AllowExpand | Allow break points for dogleg not to be exactly on the requested position. Meaning that they are moved to the least congested GCell.
NoExpand | Breakpoints for dogleg are kept right where they are requested.
PerpandicularsFirst | Reorder the events so that perpandiculars segments are re-processed before their reference segment. By default this is the other way around.
ToMoveUp | Try to move up ripped up segments.
AllowLocalMoveUp | Allow local segments to be moved up (forbidden by default).
AllowTerminalMoveUp | Allow terminal segments to be moved up (forbidden by default).
AllowShortPivotUp | Allow short segment yo be pivoted up.
NoDoglegReuse | When creating a dogleg, the default behavior is not to create a new one if there's already one in the same GCell. If this flag is set, a second dogleg will be created.
LeftAxisHint | An explicit left axis hint has been supplied as argument.
RightAxisHint | An explicit right axis hint has been supplied as argument.
NotOnLastRipup | The reference segment has still more than one ripup to go for the given state.

## Constructor & Destructor Documentation

## ◆ Manipulator()

Manipulator | ( | TrackElement * | segment,
|  | SegmentFsm & | fsm
| ) |  |

Parameters

  segment | The TrackElement to manipulate.
  fsm | The associated SegmentFsm.

Construct a new Manipulator on `segment`.

Referenced by Manipulator::forceOverLocals(), Manipulator::forceToTrack(), Manipulator::insertInTrack(), Manipulator::ripupPerpandiculars(), and Manipulator::shrinkToTrack().

## Member Function Documentation

## ◆ getSegment()

TrackElement * getSegment | ( |  | ) | const
| inline

Returns: The working TrackElement.

## ◆ getData()

DataNegociate * getData | ( |  | ) | const
| inline

Returns: The DataNegociate of the TrackElement (act as a cache).

## ◆ getEvent()

RoutingEvent * getEvent | ( |  | ) | const
| inline

Returns: The RoutingEvent associated to the TrackElement (act as a cache).

## ◆ canRipup()

bool canRipup | ( | unsigned int | flags = `0` | ) | const

Returns: true if the maximum ripup, for the given SegmentFsm::State has not been reached. If `flags` contains Manipulator::HasNextRipup, return true only if it still have at least one ripup to go.

Referenced by Manipulator::forceToTrack(), and Manipulator::ripup().

## ◆ isCaged()

bool isCaged | ( | DbU::Unit | axis | ) | const

Returns: true if the segment is enclosed (in it's Track) by two fixed or blockage segments which at least one is closer than 10 lambdas from `axis`. Mostly used to know if a perpandicular is actually restricting the axis span of a reference segment.

Referenced by Manipulator::ripupPerpandiculars().

## ◆ ripup()

bool ripup | ( | unsigned int | type,
|  | DbU::Unit | axisHint = `0`
| ) |  |

Parameters

  type | The type of ripup action.
  axisHint | An indication as where to move the riped up segment.

Returns
  true if the operation has succedeed.

If the TrackElement can be ripped up, schedule a ripup action, possibly with a hint for the preferred axis position.

Referenced by Manipulator::forceOverLocals(), Manipulator::forceToTrack(), Manipulator::insertInTrack(), and Manipulator::ripupPerpandiculars().

## ◆ ripupPerpandiculars()

bool ripupPerpandiculars | ( | unsigned int | flags = `0` | ) |

Schedule a ripup of all the perpandiculars of the reference segment. `flags` that modificate the behavior:

- Manipulator::PerpandicularsFirst : the queue will be reordered so that all the perpandiculars are re-processed (placed) before the reference segment.
- Manipulator::ToRipupLimit : the ripup count of the reference segment is set to the limit (i.e. only one more attempt before a slackening occurs).

The method will fails (return false) if at least one perpandicular can't be changed of track (i.e. ripped up) and none of it's neighbors could be ripped up either. Meaning that the free span on that track cannot be changed.

Referenced by SegmentFsm::conflictSolveByPlaceds().

## ◆ repackPerpandiculars()

bool repackPerpandiculars | ( |  | ) |

Ripup all the perpandiculars of the reference segment, except fixed or globals. The reference segment is rescheduled first (before it's perpandicular).

This function may be used to find a better placement, maximizing the overlap of the various perpandiculars.

Ripup all perpandiculars and the reference segment itself for a complete re-placement. The reference segment will be reprocessed before it's perpandiculars.

## ◆ ripple()

bool ripple | ( |  | ) |

Returns: true if the reference segment is local.

Applies only on reference segments that are of local type. Tries to make room for the reference segment by ripping up it's neigbors on the parallels tracks. On a vertical plane, left neigbors are shifted one track left (trough axis hint) and right ones, one track right. Note that they are ripped up and the shift is just a hint, there's no guarantee that the router can honor it.

Referenced by Manipulator::ripupPerpandiculars().

## ◆ minimize()

bool minimize | ( |  | ) |

Returns: true if the reference segment can be mimized in a suitable track hole.

Compute the miminal span of the reference segment, summing up contraints from source anchor and target anchors (if any) and perpandiculars. Then find holes in the avalaible tracks, and check if one is suitable for the miminized segment (try first the biggest hole).

This operation can only be called once on a segment (a flag is set in the event).

## ◆ slacken()

bool slacken | ( | unsigned int | flags = `KbNoFlags` | ) |

Simple proxy towards TrackElement::slacken().

To be reviewed.

## ◆ pivotUp()

bool pivotUp | ( |  | ) |

Tries to move up the reference segment. The segment will be moved up only if a half track is free (for a local) or a full track is free (for a global).

This function do not modifies/create perpandiculars.

Referenced by SegmentFsm::solveFullBlockages().

## ◆ pivotDown()

bool pivotDown | ( |  | ) |

Tries to move down the reference segment. The segment will be moved up only if two track are free (whether global or local). Is is more restrictive than Manipulator::pivotUp().

This function do not modifies/create perpandiculars.

## ◆ moveUp()

bool moveUp | ( | unsigned int | flags = `0` | ) |

Tries to move up a segment, if there is enough space in the RoutingPlane above and in the same direction.

This function may modificate perpandiculars in order to maintain connexity.

To be reviewed.

Referenced by SegmentFsm::solveFullBlockages().

## ◆ makeDogleg() [1/3]

bool makeDogleg | ( |  | ) |

Returns: false if the segment is not local or the dogleg cannot be done.

For local reference segment only, look in the first track candidate for other segment overlapping and break the reference accordingly.

## ◆ makeDogleg() [2/3]

bool makeDogleg | ( | DbU::Unit | position | ) |

Create a dogleg in the GCell under `position`.

## ◆ makeDogleg() [3/3]

bool makeDogleg | ( | Interval | overlap | ) |

Create a dogleg to avoid the obstructed interval `overlap`.

## ◆ relax()

bool relax | ( | Interval | overlap,
|  | unsigned int | flags = `AllowExpand`
| ) |  |

Break the reference segment so it can detour around the interval `overlap`. If `overlap` is completly enclosed inside the span of the reference segment two dogleg will be created. If the overlap occurs only on one side of the reference segment, only one dogleg will be created.

If `flags` contains Manipulator::AllowExpand, the dogleg are not created exactly at the edges of the overlap but on the lowest density GCell (outside the overlap interval).

The axis of the created dogleg are sets so that the broken part of the segment completly enclose `overlap`. That is, the orignal segment no longer intersect with `overlap`. So the min dogleg is pushed to the left and the max to the right if they are in the same GCell as the min/max of `overlap`. Otherwise (they have been expanded), they are put in the center of the GCell.

We do not allow to dogleg twice in the same GCell, so if min or max is in respectively the first or last GCell, it is not done. Moreover if there is only one dogleg and it is in the first or last GCell, the relax method is cancelled (and returns false). It means that this is the segment which is likely to be enclosed inside `overlap`.

Important: The doglegs are created immediatly and not in a delayed fashion like the SegmentAction.

Two Doglegs (min & max), no expansion
Two Doglegs (min & max), with expansion
One Dogleg (min)
One Dogleg (max)

## ◆ insertInTrack()

bool insertInTrack | ( | size_t | i | ) |

Try to insert the reference segment in the track at index `i` (in the cost table from SegmentFsm). The insertion is done by ripping up overlapping segment or shrinking them to left/right if possible.

This operation ripup the processed segment neighbors (and their perpandiculars).

## ◆ shrinkToTrack()

bool shrinkToTrack | ( | size_t | i,
|  | unsigned int | flags = `0`,
|  | DbU::Unit | leftAxisHint = `0`,
|  | DbU::Unit | rightAxisHint = `0`
| ) |  |

Attempt to minimize the reference segment to fit into the track. For this operation to succeed, the minimal span of the segment must not overlap any other segment already in the track. To reach the minimal span the perpandiculars are ripped up with an axis hint which is the center of the minimal span or the explicit value given as arguments `leftAxisHint` and `rightAxisHint` if `flags` contains respectively Manipulator::LeftAxisHint or Manipulator::RightAxisHint.

This operation ripup the processed segment itself and its perpandiculars.

## ◆ forceToTrack()

bool forceToTrack | ( | size_t | i | ) |

Try to insert the reference segment in the track at index `i` (in the cost table from SegmentFsm). The insertion is done by forcibly ripping up the overlapping segments and their perpandiculars.

This operation ripup the processed segment neighbors (and their perpandiculars).

## ◆ forceOverLocals()

bool forceOverLocals | ( |  | ) |

Loop over all the candidate tracks and, insert in the first which all conflicting segments are locals (rip them up).

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

- Manipulator.h
- Manipulator.cpp
- Manipulator.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