Route.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Last Edited by: Preas, August 19, 1985 10:25:35 am PDT
DIRECTORY
CD,
D2Basic,
Properties,
Rope,
RTBasic;
Route: CEDAR DEFINITIONS = BEGIN
Theory
This interface provides the procedures necessary to define and route an interconnection area using the major algorithms: channel router, and switchbox router. The client program must first define the routing area (design rules, boundries on each side of the routing area) and include the interconnection nets to be routed. Next, one of the routing algorithms is invoked; this algorithm passes back summary routing information (required size, whether expansion is needed, list of incomplete nets if any). Finally, the routing area is made into a ChipNDale cell by invoking RetreiveRouting.
Route supports both fixed coordinate routing (SwitchBox) where the pin and side locations are not modified by the algorithm and topological routing (Channel) where the routing area is expanded to the required size to hold all of the routing.
Each side of the routing area (including the pins on that side) has a separate origin to allow for expandable routing areas and topological routing algorithms. The separate coordinate systems for the 1 to 4 sides are related by the sideCoords vector that specifies the plsition of the fiducial in the routing coordinate space. Each coordinate system must have the same scale; up and right are the positive directions. The routing area proper is defined by routingRect; ares may be removed from consideration by placing routing barriers in the routingRect.
The following restrictions apply:
The routing area is rectangular but may have irregular routing barriers on the edges of the rectangle.
The pins may not lie in the routing area proper (that is, they must lie outside the routing area of within the route barriers).
The pins must be accessable by straight line segments on the layer for the routing material used. A via or contact will be inserted if necessary.
The routing area (except for the routing barriers) is owned by Route. Route will disregard any pre-existing material in the routing area proper.
Channel Router restrictions:
Pins must have fixed positions on the sides parallel to the trunk layer direction. Pins on the channel ends (routing area sides parallel to the branch direction) are positioned by the channel router to minimize the routing area.
Channel routing algorithms do not exploit the area in the shadow of routing barriers well.
SwitchBox Router restrictions:
The routing area is not altered from the input specification. The SwitchBox router does the best it can in the area specified.
Common Types
RopeList: TYPE = LIST OF Rope.ROPE;
Layer: TYPE = CD.Layer;
Object: TYPE = CD.Object;
Rect: TYPE = D2Basic.Rect;
RectList: TYPE = LIST OF Rect;
RefRect: TYPE = REF Rect;
Position: TYPE = D2Basic.Pos;
PositionList: TYPE = LIST OF Position;
Number: TYPE = D2Basic.Number;
SideOrNone: TYPE = {bottom, right, top, left, none};
Side: TYPE = SideOrNone[bottom .. left];
DirectionOrNone: TYPE = RTBasic.DirectionOrNone;
Direction: TYPE = RTBasic.Direction;
PropList: TYPE = Properties.PropList;
Optimization: TYPE = {full, noIncompletes};
Errors
Error: ERROR [errorType: ErrorType ← callingError, explanation: Rope.ROPE ← NIL];
Signal: SIGNAL [errorType: ErrorType ← callingError, explanation: Rope.ROPE ← NIL];
ErrorType: TYPE = {programmingError, callingError, noResource, other};
Routing Areas
RoutingArea: TYPE = REF RoutingAreaRec;
RoutingAreaRec:
TYPE =
RECORD [
name: Rope.ROPE ← NIL,
rules: DesignRules ← NIL,
routingSides: PRIVATE REF ANY ← NIL,
properties: PRIVATE REF ANY ← NIL,
nets: PRIVATE REF ANY ← NIL,
parms: PRIVATE REF ANY ← NIL,
privateData: PRIVATE REF ANY ← NIL];
CreateRoutingArea:
PROC [routingAreaName: Rope.
ROPE ←
NIL, designRules: DesignRules, properties: PropList ←
NIL]
RETURNS [routingArea: RoutingArea];
Create a RoutingArea. The RoutingArea definition includes the design rules (conductor and via widths and spacings) and definition of the routing area sides.
Design Rules
DesignRules: TYPE = REF DesignRulesRec;
DesignRulesRec:
TYPE =
RECORD[
horizLayer, vertLayer, trunkLayer, branchLayer: Layer,
CDLambda: Number,
trunkDirection, branchDirection: DirectionOrNone,
trunkWidth, trunkSpacing, trunkToContact, trunkToTrunk, trunkOffset, branchWidth, branchSpacing, branchToContact, branchToBranch, branchOffset, contactSize, contactToContact, pinSpacing, trunkToEdge: Number ← 0,
technology: PRIVATE REF ANY ← NIL];
CreateDesignRules:
PROC [technologyKey:
ATOM, horizLayer, vertLayer: Layer, trunkDirection: Direction, properties: PropList ←
NIL]
RETURNS [designRules: DesignRules];
Define the routing design rules. technologyKey values must correspond to ChipNDale technologies.
Routing Area Sides
A RoutingBarrier describes one of the routing layers adjacent to the associated side. The barrer extends from the routing area side to the fartherest extent of the barrier rectangle.
RoutingBarrier: TYPE = REF RoutingBarrierRec;
RoutingBarrierList: TYPE = LIST OF RoutingBarrier;
RoutingBarrierRec:
TYPE =
RECORD[
layer: Layer ← CD.combined,
barrier: RectList ← NIL,
properties: PropList ← NIL];
CreateRoutingBarrier:
PROC [layer: Layer, barrier: RectList ←
NIL, properties: PropList ←
NIL]
RETURNS [routingBarrier: RoutingBarrier];
Create a routing barrier for a layer. Only barriers on the sides parallel to te trunk direction are used.
IncludeRoutingAreaSide:
PROC [routingArea: Route.RoutingArea, side: Side, sideFiducial: Position, barriers: RoutingBarrierList ←
NIL, properties: PropList ←
NIL];
Create a routing area side. Each side is typically a ChipNDale object, and hence has its own coordinate system: the barriers, pins and the sideFiducial have coordinates with respect to the side. sideFiducial is used to position the side with respect to each other (see *Route procedures); it is normally the ChipNDale cell orgin The coordinate position of the sideFiducial that is perpendicular to the Side (y for top and bottom, x for left and right) determines the edge of the routing area in the coordinate space of the side. Barriers should be used to block any area that is in the routing area but not to be used for routing.
Interconnections
Pin: TYPE = REF PinRec;
PinList: TYPE = LIST OF Pin;
PinRec:
TYPE =
RECORD[
pin: CD.Instance ← NIL,
side: Side];
CreatePin:
PROC [cdPin: CD.Instance, side: Side] RETURNS [pin: Pin];
Create a pin. Use IncludeNet to specify the pins that are to be connected.
IncludeNet:
PROC [routingArea: RoutingArea, netName: Rope.
ROPE, connections: PinList, properties: PropList ←
NIL];
Create a net within the interconnection area. Mutiple calls for same net create independent connections.
Routing Operations
RoutingResult: TYPE = REF RoutingResultRec;
RoutingResultRec:
TYPE =
RECORD[
routingArea: RoutingArea,
polyLength, metalLength, metal2Length: Route.Number ← 0,
polyToMetal, metalToMetal2, numTrunkTracks, numIncompletes: NAT ← 0,
routingRect: Rect ← Rect[0, 0, 0, 0],
moreAreaRequired: BOOL ← FALSE,
incompleteNets, breakAtExitNets: RopeList ← NIL];
PositionVec: TYPE = ARRAY Side OF Position;
ChannelRoute:
PROC [routingArea: RoutingArea, sideOrgins: PositionVec, routingRect: Rect, opt: Optimization ← full]
RETURNS [routingResult: RoutingResult];
Channel Route the routing area. sideOrgins defines the orgins of the side objects in the coordinate space where the routing is to take place. The sideFiducials are placed ath the sideCoords respectively. Routing area sides parallel to trunk direction may be moved by ChannelRoute. Use combination of routingRect and retrieveRect (RetrieveRouting) to adjust the coordinates if necessary.
SwitchBoxRoute:
PROC [routingArea: RoutingArea, sideOrgins: PositionVec, routingRect: Rect, opt: Optimization ← full]
RETURNS [routingResult: RoutingResult];
SwitchBox Route the routing area. sideOrgins defines the orgins of the side objects. The sideFiducials are placed at the sideOrgins respectively. Side positions are not changed by SwitchBoxRoute. Incompletes should be remidied by increasing the routing area size.
MazeRoute:
PROC [routingArea: RoutingArea, sideCoords: PositionVec, routingRect: Rect, opt: Optimization]
RETURNS [routingResult: RoutingResult];
Maze Route the routing area. sideCoords define the limits of the routing area. The sideFiducials are placed ath the sideCoords respectively.
Data Retrevial
RetrieveRouting:
PROC [routingResult: RoutingResult, cellName: Rope.
ROPE ←
NIL, retrieveRect: RefRect ←
NIL, properties: PropList ←
NIL]
RETURNS [object: Object, externalConnections: PinList];
Create a ChipNDale object and include the routing in the object. RetreiveRouting is a separate procedure to allow routingArea size to be modified after routing is complete.
The externalConnections describe the location of a pin connecting the routingArea to the external environment. Equivalent information is recorded as pins in the ChipNDale object.
retreiveRect = NIL => use routingRect from RoutingResult.
Clean Up
Destroy:
PROC [routingArea: RoutingArea];
Remove circular references so garbage collection can work
END.