356 lines
17 KiB
Groff
356 lines
17 KiB
Groff
.TH "SegmentFsm" 3 "Thu Nov 12 2020" "Version 1.0" "Kite - Detailed Router" \" -*- nroff -*-
|
|
.ad l
|
|
.nh
|
|
.SH NAME
|
|
SegmentFsm \- Pseudo-decorator to process a \fBRoutingEvent\fP\&.
|
|
|
|
.SH SYNOPSIS
|
|
.br
|
|
.PP
|
|
.SS "Public Types"
|
|
|
|
.in +1c
|
|
.ti -1c
|
|
.RI "enum \fBState\fP { \fBMissingData\fP = (1<<0), \fBEmptyTrackList\fP = (1<<1), \fBInserted\fP = (1<<2), \fBSelf\fP = (1<<3), \fBOther\fP = (1<<4), \fBRipup\fP = (1<<5), \fBMaximumSlack\fP = (1<<6), \fBSelfInserted\fP = Self | Inserted, \fBOtherRipup\fP = Other | Ripup, \fBSelfMaximumSlack\fP = Self | MaximumSlack }"
|
|
.br
|
|
.in -1c
|
|
.SS "Public Member Functions"
|
|
|
|
.in +1c
|
|
.ti -1c
|
|
.RI "\fBSegmentFsm\fP (\fBRoutingEvent\fP *, \fBRoutingEventQueue\fP &, \fBRoutingEventHistory\fP &)"
|
|
.br
|
|
.ti -1c
|
|
.RI "bool \fBisFullBlocked\fP () const"
|
|
.br
|
|
.ti -1c
|
|
.RI "\fBRoutingEvent\fP * \fBgetEvent\fP () const"
|
|
.br
|
|
.ti -1c
|
|
.RI "\fBRoutingEventQueue\fP & \fBgetQueue\fP () const"
|
|
.br
|
|
.ti -1c
|
|
.RI "\fBRoutingEventHistory\fP & \fBgetHistory\fP () const"
|
|
.br
|
|
.ti -1c
|
|
.RI "unsigned int \fBgetState\fP () const"
|
|
.br
|
|
.ti -1c
|
|
.RI "\fBDataNegociate\fP * \fBgetData\fP ()"
|
|
.br
|
|
.ti -1c
|
|
.RI "\fBInterval\fP & \fBgetConstraint\fP ()"
|
|
.br
|
|
.ti -1c
|
|
.RI "\fBInterval\fP & \fBgetOptimal\fP ()"
|
|
.br
|
|
.ti -1c
|
|
.RI "vector< TrackCost > & \fBgetCosts\fP ()"
|
|
.br
|
|
.ti -1c
|
|
.RI "TrackCost & \fBgetCost\fP (size_t)"
|
|
.br
|
|
.ti -1c
|
|
.RI "\fBTrack\fP * \fBgetTrack\fP (size_t)"
|
|
.br
|
|
.ti -1c
|
|
.RI "size_t \fBgetBegin\fP (size_t)"
|
|
.br
|
|
.ti -1c
|
|
.RI "size_t \fBgetEnd\fP (size_t)"
|
|
.br
|
|
.ti -1c
|
|
.RI "vector< \fBSegmentAction\fP > & \fBgetActions\fP ()"
|
|
.br
|
|
.ti -1c
|
|
.RI "void \fBsetState\fP (unsigned int)"
|
|
.br
|
|
.ti -1c
|
|
.RI "void \fBaddAction\fP (\fBTrackElement\fP *, unsigned int type, \fBDbU::Unit\fP axisHint=0, unsigned int toState=0)"
|
|
.br
|
|
.ti -1c
|
|
.RI "void \fBdoActions\fP ()"
|
|
.br
|
|
.ti -1c
|
|
.RI "void \fBclearActions\fP ()"
|
|
.br
|
|
.ti -1c
|
|
.RI "bool \fBinsertInTrack\fP (size_t)"
|
|
.br
|
|
.ti -1c
|
|
.RI "bool \fBconflictSolveByHistory\fP ()"
|
|
.br
|
|
.ti -1c
|
|
.RI "bool \fBconflictSolveByPlaceds\fP ()"
|
|
.br
|
|
.ti -1c
|
|
.RI "bool \fBdesaturate\fP ()"
|
|
.br
|
|
.ti -1c
|
|
.RI "bool \fBslackenTopology\fP (unsigned int flags=0)"
|
|
.br
|
|
.ti -1c
|
|
.RI "bool \fBsolveFullBlockages\fP ()"
|
|
.br
|
|
.in -1c
|
|
.SH "Detailed Description"
|
|
.PP
|
|
Pseudo-decorator to process a \fBRoutingEvent\fP\&.
|
|
|
|
The \fBSegmentFsm\fP class actually perform the placement of the \fBKite::TrackElement\fP of the \fBKite::RoutingEvent\fP\&. It structured around three goals:
|
|
.IP "\(bu" 2
|
|
Implement the finite state machine for the \fBKite::DataNegociate\fP state\&.
|
|
.IP "\(bu" 2
|
|
Provide a kind of decoration on the RoutingEvent/TrackElement (it do not abide by the definition from Design Patterns)\&.
|
|
.IP "\(bu" 2
|
|
Cache a lot of on-the-fly computed datas needed during the \fBSegmentFsm\fP lifetime and the Manipulator(s) it may uses\&.
|
|
.PP
|
|
.SH "Update Mechanism"
|
|
.PP
|
|
The constructor of \fBSegmentFsm\fP triggers the update of the \fBRoutingEvent\fP and through it \fBDataNegociate\fP\&.
|
|
.SH "Slackening / FSM Transitions"
|
|
.PP
|
|
A transition occurs in the FSM whenener all the availables ripup methods for a segment have failed\&. Failure means that the topology of the net itself must be altered to allow a greater level of flexibility\&. Modifying the net topology means to give the current segment some more slack\&.
|
|
.PP
|
|
Availables slackening operations:
|
|
.IP "1." 4
|
|
\fBDataNegociate::RipupPerpandiculars\fP (\fBManipulator\fP) place the segments before any of it's perpandiculars are placed to allow a maximum track choice\&.
|
|
.IP "2." 4
|
|
\fBDataNegociate::Minimize\fP (\fBManipulator\fP) try to fit the segment in a hole in a track, perform a hole detection\&.
|
|
.IP "3." 4
|
|
\fBDataNegociate::Dogleg\fP (\fBManipulator\fP) create a dogleg matching \fIthe first track candidate\fP with a non-nul overlap\&.
|
|
.IP "4." 4
|
|
\fBDataNegociate::Slacken\fP (\fBManipulator\fP) to be reviewed\&.
|
|
.IP "5." 4
|
|
\fBDataNegociate::ConflictSolveByHistory\fP (\fBSegmentFsm\fP) try to find a break point on the segment, based on the ripup history\&.
|
|
.IP "6." 4
|
|
\fBDataNegociate::ConflictSolveByPlaceds\fP (\fBSegmentFsm\fP) try to find a break point on the segment, based on the current position of segments on the candidate tracks\&.
|
|
.IP "7." 4
|
|
\fBDataNegociate::MoveUp\fP (\fBManipulator\fP) try to move up the segment\&.
|
|
.PP
|
|
.PP
|
|
Simple slackening operations are defined in \fBManipulator\fP and complex ones directly in \fBSegmentFsm\fP\&.
|
|
.SH "Non-Slackening Operations"
|
|
.PP
|
|
In addition, some operation that do not modifies the topology are availables:
|
|
.IP "1." 4
|
|
\fBManipulator::forceOverLocals()\fP mostly for global segments to ripup a track from all it's locals\&.
|
|
.IP "2." 4
|
|
\fBSegmentFsm::insertInTrack()\fP automates the three subsequent ripup trials\&.
|
|
.PP
|
|
|
|
.SH "Member Enumeration Documentation"
|
|
.PP
|
|
.SS "enum \fBState\fP"
|
|
Indicates what the \fBSegmentFsm\fP has done the processed \fBTrackElement\fP, possible values are:
|
|
.IP "\(bu" 2
|
|
\fBSegmentFsm::MissingData\fP, this is an error condition, the \fBTrackElement\fP do not have associated \fBDataNegociate\fP structure\&. Nothing is done\&.
|
|
.IP "\(bu" 2
|
|
\fBSegmentFsm::EmptyTrackList\fP, no \fBTrack\fP is available for placement (free or used)\&.
|
|
.IP "\(bu" 2
|
|
\fBSegmentFsm::SelfInserted\fP, the \fBTrackElement\fP can be successfully inserted in a \fBTrack\fP (i\&.e\&. without overlap)\&.
|
|
.IP "\(bu" 2
|
|
\fBSegmentFsm::SelfMaximumSlack\fP, nothing can be done to further slacken the \fBTrackElement\fP, it is at maximum ripup of the last possible state (no more topological modifications are possibles)\&.
|
|
.IP "\(bu" 2
|
|
\fBSegmentFsm::OtherRipup\fP, the \fBTrackElement\fP can be inserted but it needs the ripup of some others\&.
|
|
.PP
|
|
|
|
.PP
|
|
\fBEnumerator\fP
|
|
.in +1c
|
|
.TP
|
|
\fB\fIMissingData \fP\fP
|
|
\fB[Flag]\fP, see SegmentFsm::SegmentFsmValue\&.
|
|
.TP
|
|
\fB\fIEmptyTrackList \fP\fP
|
|
\fB[Flag]\fP, see SegmentFsm::SegmentFsmValue\&.
|
|
.TP
|
|
\fB\fIInserted \fP\fP
|
|
\fB[Flag]\fP, the \fBTrackElement\fP can be inserted in a \fBTrack\fP\&.
|
|
.TP
|
|
\fB\fISelf \fP\fP
|
|
\fB[Flag]\fP, the action is related to the processed \fBTrackSegment\fP\&.
|
|
.TP
|
|
\fB\fIOther \fP\fP
|
|
\fB[Flag]\fP, the action is \fBnot\fP related to the processed \fBTrackSegment\fP, that is, others are being topologically modificated or riped up\&.
|
|
.TP
|
|
\fB\fIRipup \fP\fP
|
|
\fB[Flag]\fP, segement, that are not the processed one are being ripped up\&.
|
|
.TP
|
|
\fB\fIMaximumSlack \fP\fP
|
|
\fB[Flag]\fP, the processed segment as reached it's maximum ripup count on the last possible slackening state\&.
|
|
.TP
|
|
\fB\fISelfInserted \fP\fP
|
|
\fB[Mask]\fP, see SegmentFsm::SegmentFsmValue\&.
|
|
.TP
|
|
\fB\fIOtherRipup \fP\fP
|
|
\fB[Mask]\fP, see SegmentFsm::SegmentFsmValue\&.
|
|
.TP
|
|
\fB\fISelfMaximumSlack \fP\fP
|
|
\fB[Mask]\fP, see SegmentFsm::SegmentFsmValue\&.
|
|
.SH "Constructor & Destructor Documentation"
|
|
.PP
|
|
.SS "\fBSegmentFsm\fP (\fBRoutingEvent\fP * event, \fBRoutingEventQueue\fP & queue, \fBRoutingEventHistory\fP & history)"
|
|
|
|
.PP
|
|
\fBParameters:\fP
|
|
.RS 4
|
|
\fIevent\fP The \fBRoutingEvent\fP to be processed\&.
|
|
.br
|
|
\fIqueue\fP The \fBRoutingEvent\fP queue\&.
|
|
.br
|
|
\fIhistory\fP The complete history of \fBRoutingEvent\fP\&.
|
|
.RE
|
|
.PP
|
|
Construct a \fBSegmentFsm\fP from a \fBRoutingEvent\fP\&. The constructor is in charge of computing all the cached values\&.
|
|
.SH "Member Function Documentation"
|
|
.PP
|
|
.SS "bool isFullBlocked () const\fC [inline]\fP"
|
|
\fBReturns:\fP \fBtrue\fP if there are Tracks avalaibles but the constraints are such that none is actually usable\&.
|
|
.SS "\fBRoutingEvent\fP * getEvent () const\fC [inline]\fP"
|
|
\fBReturns:\fP The currently processed \fBRoutingEvent\fP (\fIcached\fP)\&.
|
|
.PP
|
|
Referenced by SegmentFsm::doActions(), SegmentFsm::slackenTopology(), and SegmentFsm::solveFullBlockages()\&.
|
|
.SS "\fBRoutingEventQueue\fP & getQueue () const\fC [inline]\fP"
|
|
\fBReturns:\fP The \fBRoutingEvent\fP queue (\fIcached\fP)\&.
|
|
.SS "\fBRoutingEventHistory\fP & getHistory () const\fC [inline]\fP"
|
|
\fBReturns:\fP The \fBRoutingEvent\fP history (\fIcached\fP)\&.
|
|
.PP
|
|
Referenced by SegmentFsm::conflictSolveByHistory()\&.
|
|
.SS "unsigned int getState () const\fC [inline]\fP"
|
|
\fBReturns:\fP The state (SegmentFsm::SegmentFsmValues) which the \fBSegmentFsm\fP has computed for the \fBRoutingEvent\fP\&. This is \fBnot\fP the state of the \fBDataNegociate\fP
|
|
.SS "\fBDataNegociate\fP * getData ()\fC [inline]\fP"
|
|
\fBReturns:\fP The \fBDataNegociate\fP of the \fBTrackElement\fP (\fIcached\fP)\&.
|
|
.SS "\fBInterval\fP & getConstraint ()\fC [inline]\fP"
|
|
\fBReturns:\fP The interval into which the segment axis can be set (computed from the topological constraints and the placement constraints on the already placed perpandiculars)\&.
|
|
.SS "\fBInterval\fP & getOptimal ()\fC [inline]\fP"
|
|
\fBReturns:\fP The interval for an optimal placement of the segment axis\&.
|
|
.SS "vector< TrackCost > & getCosts ()\fC [inline]\fP"
|
|
\fBReturns:\fP The table of cost for all the candidates Tracks of the segment\&. The table is sorted in increasing cost order (see TrackCost)\&.
|
|
.PP
|
|
Referenced by SegmentFsm::desaturate(), Manipulator::forceOverLocals(), Manipulator::makeDogleg(), and Manipulator::minimize()\&.
|
|
.SS "TrackCost & getCost (size_t i)\fC [inline]\fP"
|
|
\fBReturns:\fP The cost at index \fCi\fP in the table\&.
|
|
.PP
|
|
Referenced by SegmentFsm::desaturate(), Manipulator::forceOverLocals(), Manipulator::forceToTrack(), Manipulator::insertInTrack(), Manipulator::minimize(), and SegmentFsm::solveFullBlockages()\&.
|
|
.SS "\fBTrack\fP * getTrack (size_t i)\fC [inline]\fP"
|
|
\fBReturns:\fP The \fBTrack\fP for cost at index \fCi\fP in the table\&.
|
|
.PP
|
|
Referenced by SegmentFsm::desaturate(), Manipulator::forceOverLocals(), Manipulator::forceToTrack(), Manipulator::insertInTrack(), Manipulator::makeDogleg(), Manipulator::minimize(), and Manipulator::shrinkToTrack()\&.
|
|
.SS "size_t getBegin (size_t i)\fC [inline]\fP"
|
|
\fBReturns:\fP The overlapping \fIbegin\fP index in \fBTrack\fP for cost at index \fCi\fP in the table\&.
|
|
.PP
|
|
Referenced by SegmentFsm::desaturate(), Manipulator::forceOverLocals(), Manipulator::forceToTrack(), Manipulator::insertInTrack(), Manipulator::makeDogleg(), Manipulator::minimize(), and Manipulator::shrinkToTrack()\&.
|
|
.SS "size_t getEnd (size_t i)\fC [inline]\fP"
|
|
\fBReturns:\fP The overlapping \fIend\fP index in \fBTrack\fP for cost at index \fCi\fP in the table\&.
|
|
.PP
|
|
Referenced by SegmentFsm::desaturate(), Manipulator::forceOverLocals(), Manipulator::forceToTrack(), Manipulator::insertInTrack(), Manipulator::makeDogleg(), Manipulator::minimize(), and Manipulator::shrinkToTrack()\&.
|
|
.SS "vector< \fBSegmentAction\fP * > & getActions ()\fC [inline]\fP"
|
|
\fBReturns:\fP The table of \fBSegmentAction\fP, that is the delayed requests for \fBRoutingEvent\fP creation\&.
|
|
.PP
|
|
Referenced by Manipulator::shrinkToTrack()\&.
|
|
.SS "unsigned int setState (unsigned int state)\fC [inline]\fP"
|
|
\fBReturns:\fP Sets the state of the state\&.\&.\&.
|
|
.PP
|
|
Referenced by SegmentFsm::desaturate(), Manipulator::forceOverLocals(), Manipulator::forceToTrack(), Manipulator::insertInTrack(), and Manipulator::shrinkToTrack()\&.
|
|
.SS "void addAction (\fBTrackElement\fP * segment, unsigned int type, \fBDbU::Unit\fP axisHint = \fC0\fP, unsigned int toState = \fC0\fP)"
|
|
Request the creation of a new delayed \fBRoutingEvent\fP, for the meaning of the parameters, see \fBSegmentAction::SegmentAction\fP\&.
|
|
.PP
|
|
Referenced by SegmentFsm::desaturate(), Manipulator::forceOverLocals(), Manipulator::forceToTrack(), Manipulator::insertInTrack(), Manipulator::minimize(), Manipulator::relax(), Manipulator::repackPerpandiculars(), Manipulator::ripple(), Manipulator::ripup(), Manipulator::ripupPerpandiculars(), Manipulator::shrinkToTrack(), and SegmentFsm::slackenTopology()\&.
|
|
.SS "bool doActions ()"
|
|
Actually generate RoutingEvent(s) from the SegmentAction(s)\&.
|
|
.SS "void clearActions ()\fC [inline]\fP"
|
|
Clear the the table of requested actions, whithout generating them\&.
|
|
.PP
|
|
Referenced by Manipulator::insertInTrack(), and SegmentFsm::slackenTopology()\&.
|
|
.SS "bool insertInTrack (size_t i)"
|
|
Try to insert the \fBTrackElement\fP in the \fBTrack\fP at index \fCi\fP (in the cost table)\&. Return \fBtrue\fP if the insertion is possible\&.
|
|
.PP
|
|
The insertion is not done at this stage, but a set of ripup actions is emitted to allow insertion the next time the segment will be processed\&.
|
|
.PP
|
|
Three subsequent trials are done before giving up on inserting the segment:
|
|
.IP "1." 4
|
|
\fBManipulator::insertInTrack()\fP, try to push asides the neighbors\&.
|
|
.IP "2." 4
|
|
\fBManipulator::shrinkToTrack()\fP, try squeeze the segment in an existing free space\&.
|
|
.IP "3." 4
|
|
\fBManipulator::forceToTrack()\fP, perform a complete ripup of all the neighbors and their perpandiculars\&.
|
|
.PP
|
|
.PP
|
|
The event keeps track of the insertion attempt step (see \fBRoutingEvent::getInsertState()\fP)\&.
|
|
.SS "bool conflictSolveByHistory ()"
|
|
\fBReturns:\fP \fBtrue\fP if a suitable dogleg has been created in the segment\&.
|
|
.PP
|
|
Initially, global segments may be very long, and a placement solution in which each one is placed on a track of it's own may not be realisable\&. In that case, at least one of the global segment must be broken\&. The figure below illustrate the case: \fB(a)\fP, \fB(b)\fP, \fB(c)\fP form a first cluster and \fB(d)\fP, \fB(e)\fP, \fB(f)\fP form a second one\&. Due to the constraints of the segments the remaining free track cannot be the same in both clusters\&. The only solution to place \fB(g)\fP is to break it into two sub-globals\&. The whole point of the conflict solve is to correctly detect the cluster and choose the breaking point\&.
|
|
.PP
|
|
Conflict Between Globals This variant of the conflict solve method try to guess the track span for which there is a conflict by looking at the event history\&.
|
|
.PP
|
|
Building Conflicting Intervals \fBDislodger Definition:\fP
|
|
.PP
|
|
A segment is said to be a dislodger if it matches the two following criterions:
|
|
.IP "\(bu" 2
|
|
It's span intersect the to be inserted segment span\&.
|
|
.IP "\(bu" 2
|
|
It has been placed on a track inside the perpandicular span of the to be placed segment\&.
|
|
.PP
|
|
.PP
|
|
For the time beeing we limit the search to the last three dislodgers, to not waste too much time looking back the event history\&. We merge overlapping intervals into one (see the undocumented class \fCUnionIntervals\fP and \fCRipupHistory\fP in \fCSegmentFsm\&.cpp\fP)\&.
|
|
.PP
|
|
For the time beeing we only look on the track into which the to be inserted segment wants to be placed\&.
|
|
.PP
|
|
Then we try to break the to be placed segment, first under the lower bound (source) of the conflicting interval then, in case of failure under the upper bound (target)\&.
|
|
.PP
|
|
Interval Breaking
|
|
.SS "bool conflictSolveByPlaceds ()"
|
|
\fBReturns:\fP \fBtrue\fP if a suitable dogleg has been created in the segment \fIor\fP a dislodger has been moved up\&.
|
|
.PP
|
|
This methods achieve the same goal as \fBSegmentFsm::conflictSolveByHistory()\fP but uses a different strategy\&.
|
|
.PP
|
|
Instead of looking through the history to find dislodgers it analyses the placed segments in all the candidates tracks for the to be placed segment\&. Unlike it's sibling method, which creates only one dogleg, as it uses the \fBManipulator::relax()\fP method, it may creates up to two doglegs\&.
|
|
.PP
|
|
\fBSynthetic Description\fP
|
|
.PP
|
|
.IP "1." 4
|
|
For each track, find the dislodgers, merge the overlaps into one interval and store the length of the longuest overlap (aka conflict)\&.
|
|
.IP "2." 4
|
|
Sort the tracks according to decreasing longuest overlap/confict\&.
|
|
.IP "3." 4
|
|
For each track in the sorted list, look for a dislodger under the middle of the to be placed segment\&. If no dislodger is present at this place go to the next track\&. Otherwise:
|
|
.IP " \(bu" 4
|
|
\fIThe dislodger is local\fP, then try to relax the to placed segment around the dislodger\&.
|
|
.IP " \(bu" 4
|
|
\fIThe dislodger is global\fP, try to move it up, if it is not possible, fallback to the relax approach\&.
|
|
.PP
|
|
|
|
.IP "4." 4
|
|
Quit on the first successful move up or relax\&.
|
|
.IP "5." 4
|
|
If there is no candidate tracks, this means the vertical constraints are too tight, in that case, ripup the perpandiculars (fallback plan)\&.
|
|
.PP
|
|
.PP
|
|
\fBInterval Accounting\fP
|
|
.PP
|
|
Only global conflicting segments are took into account\&. Local segments may be took into account if they overlap global ones (all part of the same net)\&. All overlapping segments are merged into one big conflict interval\&. The whole length of a conflict interval is took into account event if it's overlap with the to be placed segment is only partial\&.
|
|
.PP
|
|
\fB\fBTrack\fP Ordering (lexicographic)\fP
|
|
.PP
|
|
.IP "1." 4
|
|
The longuest (in one interval) conflict length\&.
|
|
.IP "2." 4
|
|
The longuest cumulative conflict length (all interval summed up)\&.
|
|
.PP
|
|
.PP
|
|
Interval accounting and \fBTrack\fP ordering is managed through the undocumented \fCCs1Candidate\fP class implemented in \fCSegmentFsm\&.cpp\fP\&.
|
|
.PP
|
|
Candidates Track Ordering
|
|
.SS "bool desaturate ()"
|
|
Try to create a suitable empty space in a cost \fBTrack\fP by moving up \fBTrackElement\fP in conflict\&.
|
|
.SS "bool slackenTopology (unsigned int flags = \fC0\fP)"
|
|
Modificate the topology of the \fBTrackElement\fP to slacken it\&. It is the implementation of the slakening finite state machine\&.
|
|
.SS "bool solveFullBlockages ()"
|
|
Try to solve a fully blocked configuration\&.
|
|
|
|
.SH "Author"
|
|
.PP
|
|
Generated automatically by Doxygen for Kite - Detailed Router from the source code\&.
|