2016-05-30 04:30:29 -05:00
|
|
|
// -*- mode: C++; explicit-buffer-name: "Edges.cpp<anabatic>" -*-
|
|
|
|
|
//
|
|
|
|
|
// This file is part of the Coriolis Software.
|
2018-01-06 10:55:44 -06:00
|
|
|
// Copyright (c) UPMC 2016-2018, All Rights Reserved
|
2016-05-30 04:30:29 -05:00
|
|
|
//
|
|
|
|
|
// +-----------------------------------------------------------------+
|
|
|
|
|
// | C O R I O L I S |
|
|
|
|
|
// | A n a b a t i c - Global Routing Toolbox |
|
|
|
|
|
// | |
|
|
|
|
|
// | Author : Jean-Paul CHAPUT |
|
|
|
|
|
// | E-mail : Jean-Paul.Chaput@lip6.fr |
|
|
|
|
|
// | =============================================================== |
|
|
|
|
|
// | C++ Module : "./anabatic/Edges.cpp" |
|
|
|
|
|
// +-----------------------------------------------------------------+
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#include "anabatic/Edges.h"
|
|
|
|
|
#include "anabatic/GCell.h"
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
namespace Anabatic {
|
|
|
|
|
|
Support for density estimation for the global router.
* Bug: In Anabatic::Edge::getDistance(), remove the additionnal 0.1
added to horizontal edges. This was for testing before the hScaling
parameter was added (to the distance computation in GlobalRoute).
* New: Anabatic::Path_Edges, collectio to walkthrough all the edges
between two node. More complex than in Knik as we are no longer
using a regular grid. We may request the north bound path or south
bound path.
Collection returned by AnabaticEngine::getEdgesUnderPath().
* New: In Anabatic::NetData, add a new flag GlobalEstimated to tell if
the net RMST has been computed (using FLUTE).
* New: In Anabatic::PriorityQueue, used to sort Vertexes by increasing
distances, add a new criterion to be used in case of distance
equality. The attractor which should be the center of the search
area. In case of equality, we choose the Vertex which is closest
to the attractor. Give a small improvement, and more "dendritic"
trees.
For a more simple implementation of the comparison function it is
made as a static member (so no two Dijkstra objects at the same
time...).
* Change: In Anabatic::Edge, make the estimate occupance a floating
point number instead of an integer.
* New: In Katana::GlobalRoute, finally implement the estimated congestion
driven router. Net RMST estimated using FLUTE.
Use the historic cost from Knik implementation and not the one
given in Damien's thesis, which seems not be the same and a bit
strange.
* New: In KatanaEngine, add the ability to exclude nets from routing,
and export it to Python.
2019-02-26 13:03:53 -06:00
|
|
|
using std::cerr;
|
2016-05-30 04:30:29 -05:00
|
|
|
using std::endl;
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// -------------------------------------------------------------------
|
|
|
|
|
// Class : "Anabatic::GCell_Edges".
|
|
|
|
|
|
2016-06-10 11:27:06 -05:00
|
|
|
GCell_Edges::Locator::Locator ( const GCell* gcell, Flags filterFlags )
|
2016-05-30 04:30:29 -05:00
|
|
|
: EdgesHL()
|
2016-06-10 11:27:06 -05:00
|
|
|
, _gcell (gcell)
|
|
|
|
|
, _stateFlags (Flags::EastSide)
|
|
|
|
|
, _filterFlags(filterFlags)
|
|
|
|
|
, _iedge (0)
|
2016-05-30 04:30:29 -05:00
|
|
|
{
|
2016-06-17 06:09:34 -05:00
|
|
|
// cdebug_log(110,0) << "GCell_Edges::Locator::Locator() " << isValid() << endl;
|
2016-06-10 11:27:06 -05:00
|
|
|
if (_gcell->getEastEdges().empty() or not _filterFlags.contains(Flags::EastSide)) progress();
|
2016-05-30 04:30:29 -05:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
EdgesHL* GCell_Edges::Locator::getClone () const
|
2016-05-30 11:52:38 -05:00
|
|
|
{
|
2016-06-17 06:09:34 -05:00
|
|
|
// cdebug_log(110,0) << "GCell_Edges::Locator::getClone()" << endl;
|
2016-05-30 11:52:38 -05:00
|
|
|
return new Locator (*this);
|
|
|
|
|
}
|
2016-05-30 04:30:29 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
Edge* GCell_Edges::Locator::getElement () const
|
Anabatic transient commit 10. Ripup & reroute support in Dijsktra.
* New: In Anabatic:
- In AnabaticEngine, keep track of overflowed edges.
- In AnabaticEngine, getNetsFromedge() to lookup all nets going
through an Edge.
- In Configuration, read the Kite "reserved local" parameter to
decrease the Edge capacity (it's a guessing of the cost of the
local routing).
- In Edge, add an attribute to know if there is an associated
segment of the current net (set by Dijkstra::_traceback()).
Transparently manage the overflowed edges.
- In GCell_Edges, correct a filtering bug when not all sides are
selecteds.
- New GCell::getEdgeTo() to find the edge between two adjacent
GCells.
- New GCell::unrefContact() to automatically removes global contacts
no longer used by any global segments (used during the ripup
step).
- In Dijkstra::load(), now able to "reload" and already partially
or completly routed net (look for Contact of "gcontact" layer
and their attached segments).
- In Dijkstra, keep the last net loaded until the next one is.
Put the cleanup operations in an isolated function "_cleanup()".
- In Dijkstra::_selectFirstsource() and run(), load first source
component made of multiple vertexes.
- In Dijkstra::_trackback(), link the Net segments to the Edges.
- New Dijkstra::ripup(), Dijkstra::_propagateRipup() to perform
the ripup of one edge of a Net (must be loaded in Dijkstra first).
Dijkstra::_tagConnecteds() setup the connexId of a set of Vertexes
- that are connecteds through edges *with* segments.
- In GraphicAnabaticengine & GlobalRoute.cpp, embryo of a global
routing tool with ripup & reroute.
2016-06-26 07:32:32 -05:00
|
|
|
{
|
2016-06-10 11:27:06 -05:00
|
|
|
if (_stateFlags.contains(Flags::EastSide )) return _gcell->getEastEdges ()[_iedge];
|
|
|
|
|
if (_stateFlags.contains(Flags::NorthSide)) return _gcell->getNorthEdges()[_iedge];
|
|
|
|
|
if (_stateFlags.contains(Flags::WestSide )) return _gcell->getWestEdges ()[_iedge];
|
|
|
|
|
if (_stateFlags.contains(Flags::SouthSide)) return _gcell->getSouthEdges()[_iedge];
|
2016-05-30 04:30:29 -05:00
|
|
|
return NULL;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bool GCell_Edges::Locator::isValid () const
|
2016-06-10 11:27:06 -05:00
|
|
|
{ return _stateFlags; }
|
2016-05-30 04:30:29 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
void GCell_Edges::Locator::progress ()
|
|
|
|
|
{
|
Anabatic transient commit 10. Ripup & reroute support in Dijsktra.
* New: In Anabatic:
- In AnabaticEngine, keep track of overflowed edges.
- In AnabaticEngine, getNetsFromedge() to lookup all nets going
through an Edge.
- In Configuration, read the Kite "reserved local" parameter to
decrease the Edge capacity (it's a guessing of the cost of the
local routing).
- In Edge, add an attribute to know if there is an associated
segment of the current net (set by Dijkstra::_traceback()).
Transparently manage the overflowed edges.
- In GCell_Edges, correct a filtering bug when not all sides are
selecteds.
- New GCell::getEdgeTo() to find the edge between two adjacent
GCells.
- New GCell::unrefContact() to automatically removes global contacts
no longer used by any global segments (used during the ripup
step).
- In Dijkstra::load(), now able to "reload" and already partially
or completly routed net (look for Contact of "gcontact" layer
and their attached segments).
- In Dijkstra, keep the last net loaded until the next one is.
Put the cleanup operations in an isolated function "_cleanup()".
- In Dijkstra::_selectFirstsource() and run(), load first source
component made of multiple vertexes.
- In Dijkstra::_trackback(), link the Net segments to the Edges.
- New Dijkstra::ripup(), Dijkstra::_propagateRipup() to perform
the ripup of one edge of a Net (must be loaded in Dijkstra first).
Dijkstra::_tagConnecteds() setup the connexId of a set of Vertexes
- that are connecteds through edges *with* segments.
- In GraphicAnabaticengine & GlobalRoute.cpp, embryo of a global
routing tool with ripup & reroute.
2016-06-26 07:32:32 -05:00
|
|
|
cdebug_log(110,0) << "GCell_Edges::Locator::progress() [from] " << _stateFlags << " iedge:" << _iedge << endl;
|
|
|
|
|
cdebug_log(110,0) << " _filterFlags:" << _filterFlags << endl;
|
Added support for 2-Metal block routing in Anabatic & Katana.
* New: In AnabaticEngine::invalidateRoutingPads() this method is a temporary
workaround for a Hurricane problems. When an instance is moved, the
RoutingPads that use it must be moved accordingly, but they are not
invalidated so they stay in the wrong QuadTree.
New method ::_resizeMatrix() to be called when the associated Cell
is resized.
* Bug: In AutoHorizontal::getConstraints() and AutoVertical::getConstraints(),
the *target* constraints where never merged.
* Change: In AutoHorizontal::getCells() and AutoVertical::getGCells(),
now return a boolean to tell if it was ok (must not encounter a NULL
GCell while progessing from source to target).
* New: In Anabatic::Configuration and Anabatic:Session, create new methods:
- getDHorizontalLayer()
- getDhorizontalDepth()
- getDHorizontalWidth()
- getDHorizontalPitch()
And so on for Vertical and Contact.
They supply depth-independant informations about the H/V layers to
build the initial detailed routing.
The AutoSegment::create() methods have been modificated accordingly.
* New: In Anabatic::GCell, add two new types "StdCellRow" and "ChannelRow"
for implementing 2-Metal blocks.
Rename the GCell::setXY() method in GCell::setSouthWestCorner(),
move the contents of GCell::updateContactsPosition() into it and
suppress it.
WARNING: In case of a GCell shrink this may cause problems. But for
now we only expand...
New method GCell::getNetCount() to count the number of Net going
though the GCell.
* Change: In Anabatic::Edge, add specific support for capacity of 2-Metal
routing channels.
* Change: In Anabatic::Dijsktra various methods, replace the "gcell->isMatrix()"
calls by "not gcell->isAnalog()". Add more check so that the methods
pertaining to the analog routing (GRData) are not called in digital
mode.
* New: In Anabatic::Dijkstra::materialize(), add support for 2-Metal specific
cases. That is, always break in case of vertical pass-through or
U-turn. The global routing must always be broken in H-Channel.
* New: In Anabatic::GCell & Anabatic::Edge, make use of the Session mechanism
to ensure the revalidation. The "::revalidate()" method is then moved
as "::materialize()" (overload of Go) and "::_invalidate()" becomes
"::invalidate()"
* Change: In LoadGlobalRouting, cosmetic rename of SortHkByX in SortHookByX.
* New: In GCellTopology, added support for building 2-Metal topologies.
* ForkStack is now an object attribute as many methods do need it.
* To push segments/hook on the stack, a new method "push()" is
available. Perform NULL and fromHook checking. Can also setup
_southWestContact or _northEastContact if it is the "from" edge.
* N/S/E/W edges are now vector as in digital channel mode there
can be more than one.
* Added build topological build methods:
- doRp_2m_Access() RoutingPad stem access.
- _do_2m_1G_1M1() North or south access.
- _do_2m_2G_1M1() North AND south access.
- _do_2m_xG() H-Channel routing.
* New: In Anabatic::Matrix, new ::resize() function, as Cell can be resizeds.
* New: In Anabatic::Vertex, new static method ::getValueString() for a
friendly text rendering.
* New: In Katana::DigitalDistance, support for channel routing.
* Change: In KatanaEngine::digitalSetup() and KatanaEngine::runGlobalrouter(),
for channel routing, calls to setupPowerRails() and
protectRoutingPads() must be called after the core block has
been fully dimensionned.
::runGlobalrouter() contains the code tasked with the grid creation
and channel sizing.
* New: In KatanaEngine: Added support for core block, for 2-Metal routing.
May be expanded for over-the-cell routing in the future.
Added methods :
- isDigitalMode()
- isAnalogMode()
- isMixedMode()
- isChannelMode()
- getBlock() / addBlock()
- setupChannelMode()
- createChannel()
* New: In Katana, new class Block to manage core blocks and perform
channel routing.
* New: In Katana::Session, new convenience method "isOpen()".
2017-08-18 16:56:23 -05:00
|
|
|
cdebug_log(110,0) << " East:" << _gcell->getEastEdges ().size()
|
|
|
|
|
<< " North:" << _gcell->getNorthEdges().size()
|
|
|
|
|
<< " West:" << _gcell->getWestEdges ().size()
|
|
|
|
|
<< " South:" << _gcell->getSouthEdges().size() << endl;
|
Anabatic transient commit 10. Ripup & reroute support in Dijsktra.
* New: In Anabatic:
- In AnabaticEngine, keep track of overflowed edges.
- In AnabaticEngine, getNetsFromedge() to lookup all nets going
through an Edge.
- In Configuration, read the Kite "reserved local" parameter to
decrease the Edge capacity (it's a guessing of the cost of the
local routing).
- In Edge, add an attribute to know if there is an associated
segment of the current net (set by Dijkstra::_traceback()).
Transparently manage the overflowed edges.
- In GCell_Edges, correct a filtering bug when not all sides are
selecteds.
- New GCell::getEdgeTo() to find the edge between two adjacent
GCells.
- New GCell::unrefContact() to automatically removes global contacts
no longer used by any global segments (used during the ripup
step).
- In Dijkstra::load(), now able to "reload" and already partially
or completly routed net (look for Contact of "gcontact" layer
and their attached segments).
- In Dijkstra, keep the last net loaded until the next one is.
Put the cleanup operations in an isolated function "_cleanup()".
- In Dijkstra::_selectFirstsource() and run(), load first source
component made of multiple vertexes.
- In Dijkstra::_trackback(), link the Net segments to the Edges.
- New Dijkstra::ripup(), Dijkstra::_propagateRipup() to perform
the ripup of one edge of a Net (must be loaded in Dijkstra first).
Dijkstra::_tagConnecteds() setup the connexId of a set of Vertexes
- that are connecteds through edges *with* segments.
- In GraphicAnabaticengine & GlobalRoute.cpp, embryo of a global
routing tool with ripup & reroute.
2016-06-26 07:32:32 -05:00
|
|
|
cdebug_log(110,0) << this << endl;
|
2016-05-30 04:30:29 -05:00
|
|
|
|
|
|
|
|
++_iedge;
|
2016-06-10 11:27:06 -05:00
|
|
|
while (_stateFlags) {
|
Anabatic transient commit 10. Ripup & reroute support in Dijsktra.
* New: In Anabatic:
- In AnabaticEngine, keep track of overflowed edges.
- In AnabaticEngine, getNetsFromedge() to lookup all nets going
through an Edge.
- In Configuration, read the Kite "reserved local" parameter to
decrease the Edge capacity (it's a guessing of the cost of the
local routing).
- In Edge, add an attribute to know if there is an associated
segment of the current net (set by Dijkstra::_traceback()).
Transparently manage the overflowed edges.
- In GCell_Edges, correct a filtering bug when not all sides are
selecteds.
- New GCell::getEdgeTo() to find the edge between two adjacent
GCells.
- New GCell::unrefContact() to automatically removes global contacts
no longer used by any global segments (used during the ripup
step).
- In Dijkstra::load(), now able to "reload" and already partially
or completly routed net (look for Contact of "gcontact" layer
and their attached segments).
- In Dijkstra, keep the last net loaded until the next one is.
Put the cleanup operations in an isolated function "_cleanup()".
- In Dijkstra::_selectFirstsource() and run(), load first source
component made of multiple vertexes.
- In Dijkstra::_trackback(), link the Net segments to the Edges.
- New Dijkstra::ripup(), Dijkstra::_propagateRipup() to perform
the ripup of one edge of a Net (must be loaded in Dijkstra first).
Dijkstra::_tagConnecteds() setup the connexId of a set of Vertexes
- that are connecteds through edges *with* segments.
- In GraphicAnabaticengine & GlobalRoute.cpp, embryo of a global
routing tool with ripup & reroute.
2016-06-26 07:32:32 -05:00
|
|
|
if (_stateFlags.contains(Flags::EastSide)) {
|
|
|
|
|
if ( (_iedge < _gcell->getEastEdges().size())
|
|
|
|
|
and _filterFlags.contains(Flags::EastSide)) break;
|
2017-09-15 09:06:15 -05:00
|
|
|
//cdebug_log(110,0) << "Switching to North side." << endl;
|
2016-06-10 11:27:06 -05:00
|
|
|
_stateFlags = Flags::NorthSide;
|
|
|
|
|
_iedge = 0;
|
2016-06-17 06:09:34 -05:00
|
|
|
// cdebug_log(110,0) << this << endl;
|
2016-05-30 11:52:38 -05:00
|
|
|
continue;
|
2016-05-30 04:30:29 -05:00
|
|
|
}
|
Anabatic transient commit 10. Ripup & reroute support in Dijsktra.
* New: In Anabatic:
- In AnabaticEngine, keep track of overflowed edges.
- In AnabaticEngine, getNetsFromedge() to lookup all nets going
through an Edge.
- In Configuration, read the Kite "reserved local" parameter to
decrease the Edge capacity (it's a guessing of the cost of the
local routing).
- In Edge, add an attribute to know if there is an associated
segment of the current net (set by Dijkstra::_traceback()).
Transparently manage the overflowed edges.
- In GCell_Edges, correct a filtering bug when not all sides are
selecteds.
- New GCell::getEdgeTo() to find the edge between two adjacent
GCells.
- New GCell::unrefContact() to automatically removes global contacts
no longer used by any global segments (used during the ripup
step).
- In Dijkstra::load(), now able to "reload" and already partially
or completly routed net (look for Contact of "gcontact" layer
and their attached segments).
- In Dijkstra, keep the last net loaded until the next one is.
Put the cleanup operations in an isolated function "_cleanup()".
- In Dijkstra::_selectFirstsource() and run(), load first source
component made of multiple vertexes.
- In Dijkstra::_trackback(), link the Net segments to the Edges.
- New Dijkstra::ripup(), Dijkstra::_propagateRipup() to perform
the ripup of one edge of a Net (must be loaded in Dijkstra first).
Dijkstra::_tagConnecteds() setup the connexId of a set of Vertexes
- that are connecteds through edges *with* segments.
- In GraphicAnabaticengine & GlobalRoute.cpp, embryo of a global
routing tool with ripup & reroute.
2016-06-26 07:32:32 -05:00
|
|
|
if (_stateFlags.contains(Flags::NorthSide)) {
|
|
|
|
|
if ( (_iedge < _gcell->getNorthEdges().size())
|
|
|
|
|
and _filterFlags.contains(Flags::NorthSide)) break;
|
2017-09-15 09:06:15 -05:00
|
|
|
//cdebug_log(110,0) << "Switching to West side." << endl;
|
2016-06-10 11:27:06 -05:00
|
|
|
_stateFlags = Flags::WestSide;
|
|
|
|
|
_iedge = 0;
|
2016-06-17 06:09:34 -05:00
|
|
|
// cdebug_log(110,0) << this << endl;
|
2016-05-30 11:52:38 -05:00
|
|
|
continue;
|
2016-05-30 04:30:29 -05:00
|
|
|
}
|
Anabatic transient commit 10. Ripup & reroute support in Dijsktra.
* New: In Anabatic:
- In AnabaticEngine, keep track of overflowed edges.
- In AnabaticEngine, getNetsFromedge() to lookup all nets going
through an Edge.
- In Configuration, read the Kite "reserved local" parameter to
decrease the Edge capacity (it's a guessing of the cost of the
local routing).
- In Edge, add an attribute to know if there is an associated
segment of the current net (set by Dijkstra::_traceback()).
Transparently manage the overflowed edges.
- In GCell_Edges, correct a filtering bug when not all sides are
selecteds.
- New GCell::getEdgeTo() to find the edge between two adjacent
GCells.
- New GCell::unrefContact() to automatically removes global contacts
no longer used by any global segments (used during the ripup
step).
- In Dijkstra::load(), now able to "reload" and already partially
or completly routed net (look for Contact of "gcontact" layer
and their attached segments).
- In Dijkstra, keep the last net loaded until the next one is.
Put the cleanup operations in an isolated function "_cleanup()".
- In Dijkstra::_selectFirstsource() and run(), load first source
component made of multiple vertexes.
- In Dijkstra::_trackback(), link the Net segments to the Edges.
- New Dijkstra::ripup(), Dijkstra::_propagateRipup() to perform
the ripup of one edge of a Net (must be loaded in Dijkstra first).
Dijkstra::_tagConnecteds() setup the connexId of a set of Vertexes
- that are connecteds through edges *with* segments.
- In GraphicAnabaticengine & GlobalRoute.cpp, embryo of a global
routing tool with ripup & reroute.
2016-06-26 07:32:32 -05:00
|
|
|
if (_stateFlags.contains(Flags::WestSide)) {
|
|
|
|
|
if ( (_iedge < _gcell->getWestEdges().size())
|
|
|
|
|
and _filterFlags.contains(Flags::WestSide)) break;
|
2017-09-15 09:06:15 -05:00
|
|
|
//cdebug_log(110,0) << "Switching to South side." << endl;
|
2016-06-10 11:27:06 -05:00
|
|
|
_stateFlags = Flags::SouthSide;
|
|
|
|
|
_iedge = 0;
|
2016-05-30 11:52:38 -05:00
|
|
|
continue;
|
2016-05-30 04:30:29 -05:00
|
|
|
}
|
Anabatic transient commit 10. Ripup & reroute support in Dijsktra.
* New: In Anabatic:
- In AnabaticEngine, keep track of overflowed edges.
- In AnabaticEngine, getNetsFromedge() to lookup all nets going
through an Edge.
- In Configuration, read the Kite "reserved local" parameter to
decrease the Edge capacity (it's a guessing of the cost of the
local routing).
- In Edge, add an attribute to know if there is an associated
segment of the current net (set by Dijkstra::_traceback()).
Transparently manage the overflowed edges.
- In GCell_Edges, correct a filtering bug when not all sides are
selecteds.
- New GCell::getEdgeTo() to find the edge between two adjacent
GCells.
- New GCell::unrefContact() to automatically removes global contacts
no longer used by any global segments (used during the ripup
step).
- In Dijkstra::load(), now able to "reload" and already partially
or completly routed net (look for Contact of "gcontact" layer
and their attached segments).
- In Dijkstra, keep the last net loaded until the next one is.
Put the cleanup operations in an isolated function "_cleanup()".
- In Dijkstra::_selectFirstsource() and run(), load first source
component made of multiple vertexes.
- In Dijkstra::_trackback(), link the Net segments to the Edges.
- New Dijkstra::ripup(), Dijkstra::_propagateRipup() to perform
the ripup of one edge of a Net (must be loaded in Dijkstra first).
Dijkstra::_tagConnecteds() setup the connexId of a set of Vertexes
- that are connecteds through edges *with* segments.
- In GraphicAnabaticengine & GlobalRoute.cpp, embryo of a global
routing tool with ripup & reroute.
2016-06-26 07:32:32 -05:00
|
|
|
if (_stateFlags.contains(Flags::SouthSide)) {
|
|
|
|
|
if ( (_iedge < _gcell->getSouthEdges().size())
|
|
|
|
|
and _filterFlags.contains(Flags::SouthSide)) break;
|
2017-09-15 09:06:15 -05:00
|
|
|
//cdebug_log(110,0) << "All edges done." << endl;
|
2016-06-10 11:27:06 -05:00
|
|
|
_stateFlags = 0;
|
|
|
|
|
_iedge = 0;
|
2016-05-30 11:52:38 -05:00
|
|
|
break;;
|
2016-05-30 04:30:29 -05:00
|
|
|
}
|
|
|
|
|
}
|
2016-05-30 11:52:38 -05:00
|
|
|
|
Anabatic transient commit 10. Ripup & reroute support in Dijsktra.
* New: In Anabatic:
- In AnabaticEngine, keep track of overflowed edges.
- In AnabaticEngine, getNetsFromedge() to lookup all nets going
through an Edge.
- In Configuration, read the Kite "reserved local" parameter to
decrease the Edge capacity (it's a guessing of the cost of the
local routing).
- In Edge, add an attribute to know if there is an associated
segment of the current net (set by Dijkstra::_traceback()).
Transparently manage the overflowed edges.
- In GCell_Edges, correct a filtering bug when not all sides are
selecteds.
- New GCell::getEdgeTo() to find the edge between two adjacent
GCells.
- New GCell::unrefContact() to automatically removes global contacts
no longer used by any global segments (used during the ripup
step).
- In Dijkstra::load(), now able to "reload" and already partially
or completly routed net (look for Contact of "gcontact" layer
and their attached segments).
- In Dijkstra, keep the last net loaded until the next one is.
Put the cleanup operations in an isolated function "_cleanup()".
- In Dijkstra::_selectFirstsource() and run(), load first source
component made of multiple vertexes.
- In Dijkstra::_trackback(), link the Net segments to the Edges.
- New Dijkstra::ripup(), Dijkstra::_propagateRipup() to perform
the ripup of one edge of a Net (must be loaded in Dijkstra first).
Dijkstra::_tagConnecteds() setup the connexId of a set of Vertexes
- that are connecteds through edges *with* segments.
- In GraphicAnabaticengine & GlobalRoute.cpp, embryo of a global
routing tool with ripup & reroute.
2016-06-26 07:32:32 -05:00
|
|
|
cdebug_log(110,0) << "GCell_Edges::Locator::progress() [to] " << _stateFlags << " iedge:" << _iedge << endl;
|
2016-05-30 04:30:29 -05:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
string GCell_Edges::Locator::_getString () const
|
|
|
|
|
{
|
|
|
|
|
string s = "<GCell_Edges::Locator";
|
2016-06-10 11:27:06 -05:00
|
|
|
if (_stateFlags.contains(Flags::EastSide )) s += " East[" + getString(_iedge) + "]";
|
|
|
|
|
if (_stateFlags.contains(Flags::NorthSide)) s += " North[" + getString(_iedge) + "]";
|
|
|
|
|
if (_stateFlags.contains(Flags::WestSide )) s += " West[" + getString(_iedge) + "]";
|
|
|
|
|
if (_stateFlags.contains(Flags::SouthSide)) s += " South[" + getString(_iedge) + "]";
|
|
|
|
|
if (_stateFlags == 0) s += " invalid";
|
2016-05-30 04:30:29 -05:00
|
|
|
s += ">";
|
|
|
|
|
return s;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
EdgesHC* GCell_Edges::getClone () const
|
|
|
|
|
{ return new GCell_Edges (*this); }
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
EdgesHL* GCell_Edges::getLocator () const
|
2016-06-10 11:27:06 -05:00
|
|
|
{ return new Locator (_gcell,_filterFlags); }
|
2016-05-30 04:30:29 -05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
string GCell_Edges::_getString () const
|
|
|
|
|
{
|
|
|
|
|
string s = "<GCell_Edges "
|
|
|
|
|
+ getString(_gcell)
|
|
|
|
|
+ ">";
|
|
|
|
|
return s;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
Support for density estimation for the global router.
* Bug: In Anabatic::Edge::getDistance(), remove the additionnal 0.1
added to horizontal edges. This was for testing before the hScaling
parameter was added (to the distance computation in GlobalRoute).
* New: Anabatic::Path_Edges, collectio to walkthrough all the edges
between two node. More complex than in Knik as we are no longer
using a regular grid. We may request the north bound path or south
bound path.
Collection returned by AnabaticEngine::getEdgesUnderPath().
* New: In Anabatic::NetData, add a new flag GlobalEstimated to tell if
the net RMST has been computed (using FLUTE).
* New: In Anabatic::PriorityQueue, used to sort Vertexes by increasing
distances, add a new criterion to be used in case of distance
equality. The attractor which should be the center of the search
area. In case of equality, we choose the Vertex which is closest
to the attractor. Give a small improvement, and more "dendritic"
trees.
For a more simple implementation of the comparison function it is
made as a static member (so no two Dijkstra objects at the same
time...).
* Change: In Anabatic::Edge, make the estimate occupance a floating
point number instead of an integer.
* New: In Katana::GlobalRoute, finally implement the estimated congestion
driven router. Net RMST estimated using FLUTE.
Use the historic cost from Knik implementation and not the one
given in Damien's thesis, which seems not be the same and a bit
strange.
* New: In KatanaEngine, add the ability to exclude nets from routing,
and export it to Python.
2019-02-26 13:03:53 -06:00
|
|
|
// -------------------------------------------------------------------
|
|
|
|
|
// Class : "Anabatic::Path_Edges".
|
|
|
|
|
|
|
|
|
|
Path_Edges::Locator::Locator ( const GCell* source, const GCell* target, Flags pathFlags )
|
|
|
|
|
: EdgesHL()
|
|
|
|
|
, _source (source)
|
|
|
|
|
, _target (target)
|
|
|
|
|
, _stateFlags(Flags::NoFlags)
|
|
|
|
|
, _uprobe (0)
|
|
|
|
|
, _edge (NULL)
|
|
|
|
|
{
|
|
|
|
|
if (_source == _target) return;
|
|
|
|
|
|
|
|
|
|
Interval hoverlap = _source->getHSide().getIntersection( _target->getHSide() );
|
|
|
|
|
Interval voverlap = _source->getVSide().getIntersection( _target->getVSide() );
|
|
|
|
|
|
|
|
|
|
if (not voverlap.isEmpty()) {
|
|
|
|
|
if (_source->getXMin() > _target->getXMin()) std::swap( _source, _target );
|
|
|
|
|
_stateFlags |= Flags::EastSide;
|
|
|
|
|
_uprobe = voverlap.getCenter();
|
|
|
|
|
} else if (not hoverlap.isEmpty()) {
|
|
|
|
|
if (_source->getYMin() > _target->getYMin()) std::swap( _source, _target );
|
|
|
|
|
_stateFlags |= Flags::NorthSide;
|
|
|
|
|
_uprobe = hoverlap.getCenter();
|
|
|
|
|
} else {
|
|
|
|
|
if (_source->getXMin() > _target->getXMin()) {
|
|
|
|
|
std::swap( _source, _target );
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
if (_source->getYMin() < _target->getYMin()) {
|
|
|
|
|
if (pathFlags & Flags::NorthPath) {
|
|
|
|
|
_stateFlags |= Flags::NorthSide;
|
|
|
|
|
_uprobe = _source->getXCenter();
|
|
|
|
|
} else {
|
|
|
|
|
_stateFlags |= Flags::EastSide;
|
|
|
|
|
_uprobe = _source->getYCenter();
|
|
|
|
|
}
|
|
|
|
|
} else {
|
|
|
|
|
if (pathFlags & Flags::NorthPath) {
|
|
|
|
|
_stateFlags |= Flags::EastSide;
|
|
|
|
|
_uprobe = _source->getYCenter();
|
|
|
|
|
} else {
|
|
|
|
|
_stateFlags |= Flags::SouthSide;
|
|
|
|
|
_uprobe = _source->getXCenter();
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
_edge = _source->getEdgeAt( _stateFlags, _uprobe );
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
EdgesHL* Path_Edges::Locator::getClone () const
|
|
|
|
|
{ return new Locator (*this); }
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Edge* Path_Edges::Locator::getElement () const
|
|
|
|
|
{ return _edge; }
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bool Path_Edges::Locator::isValid () const
|
|
|
|
|
{ return (_edge != NULL); }
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
void Path_Edges::Locator::progress ()
|
|
|
|
|
{
|
|
|
|
|
if (not _edge) return;
|
|
|
|
|
|
|
|
|
|
GCell* neighbor = NULL;
|
|
|
|
|
if (_stateFlags.contains(Flags::SouthSide) or _stateFlags.contains(Flags::WestSide)) neighbor = _edge->getSource();
|
|
|
|
|
if (_stateFlags.contains(Flags::NorthSide) or _stateFlags.contains(Flags::EastSide)) neighbor = _edge->getTarget();
|
|
|
|
|
|
|
|
|
|
if (neighbor == _target) { _edge = NULL; return; }
|
|
|
|
|
|
|
|
|
|
if (_stateFlags.contains(Flags::EastSide)) {
|
|
|
|
|
Interval overlap = neighbor->getHSide().getIntersection( _target->getHSide() );
|
|
|
|
|
|
|
|
|
|
if (not overlap.isEmpty()) {
|
|
|
|
|
overlap = neighbor->getVSide().getIntersection( _target->getVSide() );
|
|
|
|
|
if (not overlap.isEmpty()) { _edge = NULL; return; }
|
|
|
|
|
|
|
|
|
|
_stateFlags.reset( Flags::EastSide );
|
|
|
|
|
_stateFlags |= (_target->getYMin() < _source->getYMin()) ? Flags::SouthSide
|
|
|
|
|
: Flags::NorthSide;
|
|
|
|
|
_uprobe = overlap.getCenter();
|
|
|
|
|
}
|
|
|
|
|
} else if (_stateFlags.contains(Flags::SouthSide)) {
|
|
|
|
|
Interval overlap = neighbor->getVSide().getIntersection( _target->getVSide() );
|
|
|
|
|
|
|
|
|
|
if (not overlap.isEmpty()) {
|
|
|
|
|
overlap = neighbor->getHSide().getIntersection( _target->getHSide() );
|
|
|
|
|
if (not overlap.isEmpty()) {
|
|
|
|
|
_edge = NULL; return; }
|
|
|
|
|
|
|
|
|
|
_stateFlags.reset( Flags::SouthSide );
|
|
|
|
|
_stateFlags |= Flags::EastSide;
|
|
|
|
|
_uprobe = overlap.getCenter();
|
|
|
|
|
}
|
|
|
|
|
} else if (_stateFlags.contains(Flags::NorthSide)) {
|
|
|
|
|
Interval overlap = neighbor->getVSide().getIntersection( _target->getVSide() );
|
|
|
|
|
|
|
|
|
|
if (not overlap.isEmpty()) {
|
|
|
|
|
overlap = neighbor->getHSide().getIntersection( _target->getHSide() );
|
|
|
|
|
if (not overlap.isEmpty()) { _edge = NULL; return; }
|
|
|
|
|
|
|
|
|
|
_stateFlags.reset( Flags::NorthSide );
|
|
|
|
|
_stateFlags |= Flags::EastSide;
|
|
|
|
|
_uprobe = overlap.getCenter();
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
_edge = neighbor->getEdgeAt( _stateFlags, _uprobe );
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
string Path_Edges::Locator::_getString () const
|
|
|
|
|
{
|
|
|
|
|
string s = "<Path_Edges::Locator @" + getString(_edge) + ">";
|
|
|
|
|
return s;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
EdgesHC* Path_Edges::getClone () const
|
|
|
|
|
{ return new Path_Edges( *this ); }
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
EdgesHL* Path_Edges::getLocator () const
|
|
|
|
|
{ return new Locator (_source,_target,_pathFlags); }
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
string Path_Edges::_getString () const
|
|
|
|
|
{
|
|
|
|
|
string s = "<Path_Edges from:"
|
|
|
|
|
+ getString(_source) + "to:"
|
|
|
|
|
+ getString(_target)
|
|
|
|
|
+ ">";
|
|
|
|
|
return s;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
2016-05-30 04:30:29 -05:00
|
|
|
} // Anabatic namespace.
|
