RouteImpl.mesa
Copyright © 1985, 1987 by Xerox Corporation. All rights reserved.
Bryan Preas, July 10, 1985 11:14:39 am PDT
last edited Bryan Preas, February 5, 1987 8:27:21 pm PST
DIRECTORY
CD, CDBasics, HashTable, List, PWObjects, Rope, Route, RouteChannel, RoutePrivate, RouteTechnology, RouteUtil;
RouteImpl:
CEDAR
PROGRAM
IMPORTS CD, CDBasics, HashTable, PWObjects, Route, RouteChannel, RouteTechnology, RouteUtil
EXPORTS Route, RoutePrivate
SHARES Route = {
RoutingLayerName: PUBLIC ARRAY RoutePrivate.RoutingLayerOrNone OF Rope.ROPE ← ["trunk", "branch", "none"];
Error: PUBLIC ERROR[errorType: Route.ErrorType ← callingError, explanation: Rope.ROPE ← NIL] = CODE;
Signal: PUBLIC SIGNAL[errorType: Route.ErrorType ← callingError, explanation: Rope.ROPE ← NIL] = CODE;
trunkWidthKey: PUBLIC REF ATOM ← NEW[ATOM ← $trunkWidth];
branchWidthKey: PUBLIC REF ATOM ← NEW[ATOM ← $branchWidth];
CreateDesignRules:
PUBLIC
PROC [technologyKey:
ATOM, horizLayer, vertLayer: Route.Layer, trunkDirection: Route.Direction, properties: Route.PropList ←
NIL]
RETURNS [dr: Route.DesignRules] = {
Define the routing design rules. technologyKey values are predefinded for now.
IF technologyKey #
NIL
THEN
{technology: CD.Technology ← CD.FetchTechnology[technologyKey];
dr ← NEW[Route.DesignRulesRec];
dr.CDLambda ← technology.lambda;
dr.technology ← technology;
dr.horizLayer ← horizLayer; dr.vertLayer ← vertLayer;
SELECT trunkDirection
FROM
horizontal =>
{dr.branchDirection ← vertical; dr.trunkDirection ← horizontal;
RouteTechnology.CmosDesignRules[dr, horizLayer, vertLayer]};
vertical =>
{dr.branchDirection ← horizontal; dr.trunkDirection ← vertical;
RouteTechnology.CmosDesignRules[dr, vertLayer, horizLayer]};
ENDCASE}
ELSE
-- invalid technology
Error[callingError, "Invalid technology."]};
CreateRoutingBarrier:
PUBLIC
PROC [layer: Route.Layer, barrier: Route.RectList ←
NIL, properties: Route.PropList ←
NIL]
RETURNS [routingBarrier: Route.RoutingBarrier] = {
Create a routing barrier for a layer.
routingBarrier ← NEW[Route.RoutingBarrierRec];
routingBarrier.layer ← layer;
routingBarrier.barrier ← barrier;
routingBarrier.properties ← properties};
IncludeRoutingAreaSide:
PUBLIC
PROC [routingArea: Route.RoutingArea, side: Route.Side, sideFiducial: Route.Position, barriers: Route.RoutingBarrierList ←
NIL, properties: Route.PropList ←
NIL] = {
Include a routing area side in a routing area. Each side has its own coordinate system: the barriers, pins and the *ChannelEnd's have coordinates with respect to the side. fixedSide = TRUE -> the side should not be moved with respect to the routing area.
routingSides: RoutePrivate.RoutingAreaSides ← NARROW[routingArea.routingSides];
IF routingSides[side] #
NIL
THEN
Route.Error[callingError, "Multiple side descriptions."]
ELSE
{routingAreaSide: RoutePrivate.RoutingAreaSide ← NEW[RoutePrivate.RoutingAreaSideRec];
routingAreaSide.side ← side;
routingAreaSide.sideFiducial ← sideFiducial;
routingAreaSide.properties ← properties;
routingAreaSide.barrierList ← barriers;
routingSides[side] ← routingAreaSide}};
CreateRoutingArea:
PUBLIC
PROC [routingAreaName: Rope.
ROPE ←
NIL, designRules: Route.DesignRules, properties: Route.PropList ←
NIL]
RETURNS [routingArea: Route.RoutingArea] = {
Create a RoutingArea. The RoutingArea definition includes the design rules (conductor and via widths and spacings) and definition of the routing area sides.
IF designRules =
NIL
THEN
Route.Error[callingError, "No design rules."]
ELSE {
routingSides: RoutePrivate.RoutingAreaSides ← NEW[RoutePrivate.RoutingAreaSidesRec ← [NIL, NIL, NIL, NIL]];
routingArea ← NEW[Route.RoutingAreaRec];
routingArea.name ← routingAreaName;
routingArea.rules ← designRules;
routingArea.properties ← properties;
routingArea.routingSides ← routingSides;
set up the parameter data
routingArea.parms ← NARROW[NEW[RoutePrivate.RoutingAreaParmsRec], RoutePrivate.RoutingAreaParms];
set up the net data
routingArea.nets ← NARROW[NEW[RoutePrivate.NetTabRec ← [size: RoutePrivate.maxNets, count: 0, n: ALL[NIL]]], RoutePrivate.NetTab]}};
CreatePin:
PUBLIC
PROC [cdPin:
CD.Instance, side: Route.Side]
RETURNS [pin: Route.Pin] = {
Create a pin. Use IncludeNet to specify the pins that are to be connected.
pin ← NEW[Route.PinRec ← [cdPin, side]]};
IncludeNet:
PUBLIC
PROC [routingArea: Route.RoutingArea, netName: Rope.
ROPE, connections: Route.PinList, properties: Route.PropList ←
NIL] = {
Create a net within the interconnection area.
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
netTab: RoutePrivate.NetTab ← NARROW[routingArea.nets, RoutePrivate.NetTab];
netPart: NAT ← 1;
nextNetNum: NAT ← netTab.count + 1;
FOR netIndex: RoutePrivate.ZMaxNets
IN [1 .. netTab.count]
DO
IF netTab.n[netIndex].name = netName THEN netPart ← netPart + 1;
ENDLOOP;
IF nextNetNum > netTab.size
THEN
Route.Error[noResource, "Too many nets."]
ELSE {
channelDirection: Route.Direction ← routingArea.rules.trunkDirection;
trunkWidth, trunkWidthSpec, branchWidth, branchWidthSpec, widestBranchPin, widestTrunkPin: Route.Number;
[widestBranchPin, widestTrunkPin] ← RouteUtil.GetPinWidth[routingArea, connections, channelDirection];
trunkWidthSpec ← RouteUtil.GetNumberProp[properties, Route.trunkWidthKey, routingArea.rules.trunkWidth];
trunkWidth ←
IF trunkWidthSpec > routingArea.rules.trunkWidth
THEN
trunkWidthSpec
ELSE IF widestTrunkPin > 0 THEN MAX[routingArea.rules.trunkWidth, widestTrunkPin]
ELSE MAX[routingArea.rules.trunkWidth, widestBranchPin];
branchWidthSpec ← RouteUtil.GetNumberProp[properties, Route.branchWidthKey, routingArea.rules.branchWidth];
branchWidth ←
IF branchWidthSpec > routingArea.rules.branchWidth
THEN
branchWidthSpec
ELSE MAX[routingArea.rules.branchWidth, widestBranchPin, trunkWidth];
parms.widestTrunk ← MAX[trunkWidth, parms.widestTrunk];
parms.widestBranch ← MAX[branchWidth, parms.widestBranch];
parms.numTracksToUse ← parms.numTracksToUse + 2*RouteChannel.InfluenceTracks[routingArea, trunkWidth];
netTab.n[nextNetNum] ← NEW[RoutePrivate.NetRec ← [name: netName, netNum: nextNetNum, netPart: netPart, branchWidth: branchWidth, trunkWidth: trunkWidth, pinList: connections, properties: properties]];
netTab.count ← nextNetNum}};
ChannelRoute:
PUBLIC
PROC [routingArea: Route.RoutingArea, sideOrgins: Route.PositionVec, routingRect: Route.Rect, opt: Route.Optimization ← full, signalSinglePinNets, signalCoincidentPins:
BOOLEAN ←
TRUE]
RETURNS [routingResult: Route.RoutingResult] = {
Channel Route the routing area.
RouteChannel.InitChannel[routingArea, sideOrgins, routingRect, channel, signalSinglePinNets, signalCoincidentPins, FALSE, FALSE];
IF RouteChannel.GenerateConstraints[routingArea, channel]
THEN
routingResult ← RouteChannel.TopoWiring[routingArea, opt]
ELSE
routingResult ← NEW[Route.RoutingResultRec ← [routingArea: routingArea, routingRect: EmptyRect[routingArea, routingRect]]]};
SwitchBoxRoute:
PUBLIC
PROC [routingArea: Route.RoutingArea, sideOrgins: Route.PositionVec, routingRect: Route.Rect, opt: Route.Optimization ← full, signalSinglePinNets, signalCoincidentPins:
BOOLEAN ←
TRUE, okToDiddleLLPins, okToDiddleURPins:
BOOLEAN ←
FALSE]
RETURNS [routingResult: Route.RoutingResult] = {
SwitchBox Route the routing area.
RouteChannel.InitChannel[routingArea, sideOrgins, routingRect, switchBox, signalSinglePinNets, signalCoincidentPins, okToDiddleLLPins, okToDiddleURPins];
IF RouteChannel.GenerateConstraints[routingArea, switchBox]
THEN
routingResult ← RouteChannel.TopoWiring[routingArea, opt]
ELSE
routingResult ← NEW[Route.RoutingResultRec ← [routingArea: routingArea, routingRect: routingRect]]};
MazeRoute:
PUBLIC
PROC [routingArea: Route.RoutingArea, sideCoords: Route.PositionVec, routingRect: Route.Rect, opt: Route.Optimization ← full]
RETURNS [routingResult: Route.RoutingResult] = {
Maze Route the routing area.
RetrieveRouting:
PUBLIC
PROC [routingResult: Route.RoutingResult, cellName: Rope.
ROPE ←
NIL, retrieveRect: Route.RefRect ←
NIL, properties: Route.PropList ←
NIL, viaTable: HashTable.Table ←
NIL]
RETURNS [object: Route.Object, externalConnections: Route.PinList] = {
Create a ChipNDale object and include the routing in the object. This object will be included in design if design # NIL. 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 CND object.
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingResult.routingArea.parms];
parms.viaTable ← IF viaTable # NIL THEN viaTable ELSE HashTable.Create[equal: EqualProc, hash: HashProc];
parms.entityTable ← HashTable.Create[equal: HashTable.RopeEqual, hash: HashTable.HashRope];
SELECT parms.routerUsed
FROM
channel, switchBox => {
rect: Route.Rect ← IF retrieveRect = NIL THEN routingResult.routingRect
ELSE CDBasics.Surround[retrieveRect^, routingResult.routingRect];
externalConnections ← RouteChannel.GetRouting[routingResult.routingArea, rect, properties, RouteChannel.RetrieveSegments, RouteChannel.RetrievePins, RouteChannel.RetrieveVias, RouteChannel.RetrieveExits, RouteChannel.RetrieveIncompletes];
object ← PWObjects.CreateRouting[rect, CreateNodes[parms.entityTable]]};
maze => NULL;
ENDCASE};
Destroy:
PUBLIC
PROC [routingArea: Route.RoutingArea] ~ {
Remove circular references so garbage collection can work
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
SELECT parms.routerUsed
FROM
channel, switchBox => RouteChannel.Destroy[routingArea];
maze => NULL;
EqualProc:
PROC [k1, k2: HashTable.Key]
RETURNS [eq:
BOOL] = {
p1: Route.Position ← NARROW[k1, REF Route.Position]^;
p2: Route.Position ← NARROW[k2, REF Route.Position]^;
eq ← p1.x = p2.x AND p1.y = p2.y};
HashProc:
PROC [k: HashTable.Key]
RETURNS [hash:
CARDINAL] = {
size: Route.Position ← NARROW[k, REF Route.Position]^;
hash ← size.x + size.y};
PlOs: TYPE = REF PlORec;
PlORec: TYPE =
RECORD[
list: LIST OF REF PWObjects.PlacedObject ← NIL];
CreateNodes:
PROC [table: HashTable.Table]
RETURNS [nodes:
LIST
OF PWObjects.Node ←
NIL] = {
EachPair: HashTable.EachPairAction = {
name: Rope.ROPE = NARROW [key];
geometry: PlOs = NARROW [value];
node: PWObjects.Node = CreateNode[geometry.list, LIST [[key: $InstanceName, val: name], [key: $SignalName, val: name]]];
nodes ← CONS [node, nodes];
};
[] ← HashTable.Pairs[table, EachPair]};
CreateNode:
PROC [geometry:
LIST
OF REF PWObjects.PlacedObject, properties:
CD.PropList ←
NIL]
RETURNS [node: PWObjects.Node] = {
size: NAT ← 0;
FOR list: LIST OF REF PWObjects.PlacedObject ← geometry, list.rest WHILE list#NIL DO size ← size + 1 ENDLOOP;
node ← NEW [PWObjects.NodeRep[size]];
node.properties ← properties;
FOR i: NAT IN [0 .. size) DO node[i] ← geometry.first^; geometry ← geometry.rest ENDLOOP};
EmptyRect:
PROC [routingArea: Route.RoutingArea, routingRect: Route.Rect]
RETURNS [empty: Route.Rect] ~ {
nRect: Route.Rect ← CDBasics.ReInterpreteRect[routingRect];
upPos: RoutePrivate.PQPosition ← RouteUtil.XYToPQ[routingArea, [nRect.x2, nRect.y2]];
upXy: Route.Position ← RouteUtil.PQToXY[routingArea, [upPos.p, nRect.y1 + routingArea.rules.pinSpacing]];
empty ← [nRect.x1, nRect.y1, upXy.x, upXy.y]};
}.