Class RouteTracks - RouteTracks.h, RouteTracks.cc


 
Definition:
Route tracks are a set of RouteEdges arranged in a rectagular fashion.  The edges can be indexed in two ways.  First you must specify whether the edge is a vertical or horizontal edge.  We allow only rectilinar routing i.e. very edge must be vertical or horizontal.  Then you can find the edge according to it's x,y coordinate or its track and edge number.  For vertical edges, the track number indictates which vertical track it is located on (similar to x axis value).  The edge number indictates the edge within that track (similar to y axis value).  For horizontal edges, the track number indictates the horizontal track in which it is located (similar to the y axis value).  The edge number specifies the edge within that track (similar to the x axis value).  There are functions for address the edges in both manners.  RouteTracks is one of the main data structures used by the maze router (see Maze).
Typedefs:
typedef vector<RouteEdge *> RouteEdgeVector;
typedef RouteEdgeVector::iterator RouteEdgeVectorItr;
typedef vector<RouteEdgeVector *> RouteTrackVector;
typedef RouteTrackVector::iterator RouteTrackVectorItr;
typedef list<MazePoint *> MazeList;
typedef MazeList::iterator MazeListItr;
Included:
#include "RouteEdge.h"
#include "MazePoint.h"
#include "PrimMST.h"
#include <vector>
#include <list>
#include <limits.h>
#include <iostream.h>
#include <fstream.h>


Variable Index
 
o RouteTrackVector * horizontalTracks
A vector which holds the horizontal edges.  If you directly index into the vector you will get a pointer to another vector which holds the edges on that "track".  Methods are provided to mask the somewhat hairy underbelly of this structure.   Unless you have a strong stomach and a lot of time, I suggest using the given methods.  NOTE:  due to my extensive background in Java, I think of coordinates as they exist in the third quadrant.  Thus, the y-axis (or track number in this case) is inverted.  The track at location 1 is actually located at -1, though this shouldn't matter at all as long as you use a consistent quadrant throughout.
o RouteTrackVector * verticalTracks
A vector which holds the vertical edges.  The comments listed in horizontalTracks apply here.
o int verticalCapacity
The capacity of the vertical edges.  As of now, you can only have two capacities, one for the vertical edges and one for the horizontal edges.  This should change soon when I adopt the GSRC bookshelf routing input format.
o int horizontalCapacity
The capacity of the vertical edges.  As of now, you can only have two capacities, one for the vertical edges and one for the horizontal edges.  This should change soon when I adopt the GSRC bookshelf routing input format.
o int routeLength
The sum of all of the length of the routes over every routed net.

Constructor Index
 
o RouteTracks(int xNum, int yNum)
Acts a default constructor.  Initailizes the set of rectagular vertical and horizontal edges as specified.
o ~RouteTracks()
Deconstructor

 

 

Method Index
 

o int isValid(int x, int y)
Returns 'true' if the specified value falls within the range.  Should be used in order to prevent memory faults.
o RouteEdge * getHorizontalEdgeAt(int x, int y)
Returns the specifed horizontal route edge.  The edge is specified according to it coordinate.
o RouteEdge * getVerticalEdgeAt(int x, int y)
Returns the specified vertical edge.  The edge is specified according to it coordinate.
o RouteEdge * getEdgeAt(int x, int y, bool horiz)
Returns the specified route edge.  The edge is specified according to it coordinate.  If 'horiz' is true, it returns the horizontal edge at the specifed position.  Otherwise it returns the vertical edge.
o RouteEdge * getHorizontalEdgeWith(int trackNumber, int edgeNumber)
Returns the specified horizontal route edge.  The edge is specifed according to its track number and edge number.
o RouteEdge * getVerticalEdgeWith(int trackNumber, int edgeNumber)
Returns the specified vertical route edge.  The edge is specified according to its track number and edge number.
o RouteEdge * getEdgeWith(int trackNumber, int edgeNumber, bool horiz)
Returns the specified route edge.  The edges is specified according to its track number and edge number.
o int getWidth()
Returns the width of this RouteTracks object.
o int getHeight()
Returns the height of thsi RouteTracks object.
o int getCongestionAt(int x, int y, bool horizontal)
Returns the congestion (number of nets routed) at the specified edge.  Edge is specified according to its coordinate.
o int getVerticalCongestionBetween(int trackNum, int begin, int end)
Returns the congestion (number of nets routed) between the specified set of edges.  NOTE: a net will be counted more than once if it is routed on multiple tracks between 'begin' and 'end'.
o int getHorizontalCongestionBeween(int trackNum, int begin, int end)
Returns the congestion (number of nets routed) between the specified set of edges.  NOTE: a net will be counted more than once if it is routed on multiple tracks between 'begin' and 'end'.
o int getRouteLength()
Returns the variable routeLength -- the total amount of routing resources used in this object.
o int getHorizontalCapacity()
Returns the horizontal capacity of this object.
o int getVerticalCapacity()
Returns the vertical capacity of this object.
o int getOverflow()
Returns the overflow of this object.  Overflow of an edge is defined as the number of nets routed over the edge minus the capacity of the edge.  The number must be non-negitive (i.e. if negitive, the overflow is zero).
o int getWireLength()
Returns the total wire length of all the nets routed in this object.   NOTE: this is the same as the route length.
o bool isOverflown(int x, int y, bool horiz)
Returns 'true' if the specified edge has more nets routed over it than the capacity of the edge.  The edge is speciified by the given coordinate.
o bool isDensityOneBendRoutable(Net *aNet, int density)
Returns 'true' if the specified nets is routable (routing is restricted to upper-L or lower-L) according to the given density.  In other words, the function returns 'true' if for at least one of the L routings of the nets, the edges which the routing pass have a no more than 'density - 1' edges routed over them.  If this is true, then we can route the net without going over the 'density' restriction on the RouteEdges.
o bool isVerticalOneBendRoutableBetween(int trackNum, int begin, int end, int density)
A function used by isDensityOneBendRoutable().  Determines whether the vertical specified edges have less than 'density' - 1 nets routed over them.
o bool isHorizontalOneBendRoutableBetween(int trackNum, int begin, int end, int density)
A function used by isDensityOneBendRoutable().  Determines whether the horizontal specified edges have less than 'density' - 1 nets routed over them.
o void addNetToEdge(int x, int y, bool horiz, Net * aNet)
Adds the specifed net to the specified edge.  Edge is specified according to its coordinate.
o void removeNetFromEdge(int x, int y, bool horiz, Net * aNet)
Removes the specified net from the specified edge.  Edge is specified according to its coordinate.
o void addNetToEdgeWith(int track, int edge, bool horiz, Net * aNet)
Adds the specified net to the specified edge.  Edge is specified according to it track and edge location.
o void removeNetFromEdgeWith(int track, int edge, bool horiz, Net * aNet)
Removes the specified net from the specified edge.  Edge is specified according to its track and edge location.
o void setVerticalCapacity(int cap)
Sets the vertical capacity verticalCapacity to the specified value.
o void setHorizontalCapacity(int cap)
Sets the horizontal capacity horizontalCapacity to the specified value.
o void addHorizontalSegment(Net *, int trackNum, int begin, int end)
Adds the specified net to the specified set of horizontal tracks.
o void addVerticalSegment(Net *, int trackNum, int begin, int end)
Adds the specified net to the specified set of vertical tracks.
o NetList * ripNets()
Returns a list of nets which are good canidates for the ripup and reroute procedure.  The nets are choosen based on overflown edges.  The edges are sequentially searched until an overflown edge is found.  Once the edge is found, every net passing over this edge is unrouted and these nets are returned.  The function has memory, in that if it is called successive times, it will start from the last found overflown edge and not the first edge.
o NetList *oldRipNets()
This is the old function for finding nets to ripup and reroute.  The new function is well tested and this function probably will no longer work.  It should probably be removed.
o void printVerticalTracks()
Debugging function which will print the number of nets that cross over the vertical tracks.
o void printHorizontalTracks()
Debugging function which will print the number of nets that cross over the horizontal tracks.
o void print()
Debugging function which prints the number of nets that cross over the vertical and horizontal tracks.
o void printCongestionDisplayFile(ofstream & stream)
Prints the congestion information to a file which can then be used by my Java program to display the congestion.
o void routeOneBendNet(Net *aNet)
Takes a net and routes in a one bend fashion.  The net is first split into a set of two-terminal one bend routes according to the Prim's MST function (see PrimMST).  The one bend route is choosen according to the function findOneBendRoute().  NOTE: the routings are not checked for overlap, hence the net could have redundant route edges.
o void findOneBendRoute(Net * aNet, Pin *, Pin *)
Routes the specified pins of the net in a one bend fashion.  The route is choosen according to amount of overflow along its path.  The route with the least overflow (there are at most two one bend routes) is choosen.
o void findZRoute(Net *)
Takes a net and routes in a Z route fashion.  A Z route (only works when talking about two terminals) are the set of route which have two bends and are restricted to be within the bounding box.  This function breaks the net into a set of two-terminal nets using Prim's MST algorithm (see PrimMST).  It then calls the function findZRoute() on each two-terminal net.  NOTE: the routings are not checked for overlap, hence the net could have redundant route edges.
o void findZRoute(Net*, Pin *, Pin *)
Takes two terminals of a net and routes them in a Z route manner.  The function will choose the route whose path has the least amount of overflow.
o void routeBBNet(Net *)
Takes a net and routes it as it's bounding box.  This is not an exact routing of the net i.e. all of the pins are not guaranteed to be connected.  It was created to be used for estiimation purposes.