SoftHdwPlaceAndRouteImpl.mesa
Copyright Ó 1988 by Xerox Corporation. All rights reserved.
Barth, November 2, 1988 12:30:45 pm PST
DIRECTORY CD, CDDirectory, CDImports, CDOps, CDProperties, Core, CoreFlat, CoreOps, LogicUtils, PW, RefTab, Rope, SoftHdwAssembly, SoftHdwBasics, SoftHdwPlaceAndRoute;
SoftHdwPlaceAndRouteImpl: CEDAR PROGRAM
IMPORTS CDDirectory, CDImports, CDOps, CDProperties, CoreOps, LogicUtils, PW, RefTab, Rope, SoftHdwAssembly, SoftHdwBasics
EXPORTS SoftHdwPlaceAndRoute
= BEGIN OPEN SoftHdwPlaceAndRoute;
180 is the number of lambda for the grid when doing assembly language programming.
Primitives
outputPrefix: CHAR = '*;
LoadLibrary: PUBLIC PROC RETURNS [primitives: Primitives] = {
design: CD.Design ← PW.OpenDesign["SoftHdwPrimitives.dale"];
base: SoftHdwBasics.ArrayBase ← SoftHdwBasics.CreateBase[[[1,1], [8,8], [8,8]]];
primitives ← NEW[PrimitivesRec];
primitives.each ← RefTab.Create[];
primitives.publics ← RefTab.Create[];
CDOps.SetMutability[design, readonly];
IF NOT CDImports.LoadAndBindAll[design] THEN ERROR;
FOR instances: CD.InstanceList ← CDOps.InstList[design], instances.rest WHILE instances#NIL DO
inst: CD.Instance ← instances.first;
instName: Rope.ROPE ← NARROW[CDProperties.GetObjectProp[inst.ob, $Describe]];
IF NOT Rope.Equal[instName, "MajorArray.sch"] THEN {
CheckWire: PROC [wire: Core.Wire] = {
name: Rope.ROPE ← CoreOps.GetShortWireName[wire];
IF NOT RefTab.Fetch[primitives.publics, wire].found AND NOT Rope.Equal[name, "Vdd"] AND NOT Rope.Equal[name, "Gnd"] AND NOT Rope.Equal[name, "CK"] THEN ERROR;
};
name: Rope.ROPE ← CDDirectory.Name[inst.ob, design];
program: SoftHdwAssembly.PositionedTiles ← SoftHdwAssembly.ParseTileProgram[base, inst.ob, design];
cellType: Core.CellType ← LogicUtils.MakeSC[name];
primitive: Primitive ← NEW[PrimitiveRec];
primitive.tile ← inst.ob;
FOR pts: SoftHdwAssembly.PositionedTiles ← program, pts.rest UNTIL pts=NIL DO
ConsNodePosition: PROC [type: NodeType] = {
np: NodePosition ← NEW[NodePositionRec];
np.type ← type;
np.position ← pt.position;
primitive.resources ← CONS[np, primitive.resources];
IF pt.name#NIL THEN {
publicName: Rope.ROPE ← pt.name;
output: BOOL ← FALSE;
public: Core.Wire;
pp: PrimitivePublic;
IF Rope.Fetch[publicName]=outputPrefix THEN {
publicName ← Rope.Substr[publicName, 1];
output ← TRUE;
};
public ← CoreOps.FindWire[cellType.public, publicName];
IF public=NIL THEN ERROR;
pp ← NARROW[RefTab.Fetch[primitives.publics, public].val];
IF pp=NIL THEN {
pp ← NEW[PrimitivePublicRec];
pp.output ← output;
IF NOT RefTab.Insert[primitives.publics, public, pp] THEN ERROR;
}
ELSE IF pp.output#output THEN ERROR;
pp.positions ← CONS [np, pp.positions];
};
};
pt: SoftHdwAssembly.PositionedTile ← pts.first;
SELECT pt.type FROM
HBit, HMatch => ConsNodePosition[horizontalShort];
HLong => ConsNodePosition[horizontalLong];
VMatch, VBit => ConsNodePosition[verticalShort];
VLong0, VLong1 => ConsNodePosition[verticalLong];
ENDCASE;
ENDLOOP;
CoreOps.VisitRootAtomics[cellType.public, CheckWire];
[] ← RefTab.Insert[primitives.each, cellType, primitive];
};
ENDLOOP;
};
Placement
Surface
CreateSurface: PUBLIC PROC [sizes: SoftHdwBasics.ArrayPosition] RETURNS [surface: Surface] = {
};
PlaceSurface: PUBLIC PROC [surface: Surface, placement: Placement] = {
};
Goal is to minimize the maximum number of arcs between an output and any input while still achieving a complete route. There is no concept of trying to minimize area in this level of the software. It has been allocated a set of resources by higher levels of software and its job is to achieve the aforementioned goal, no other.
Use the metric of getting closer to bias the search, compute closer from node.position.
A tree of INT which specify the arc indicies also specify a routing tree.
First the minimum trees which connect the terminals of a net are computed independently for each net. Each node then has the number of nets which would like to use it attached to it.
noArc: ArcIndex = LAST[ArcIndex];
NodeData: TYPE = REF NodeDataRec;
NodeDataRec: TYPE = RECORD [
cost: INT ← 0,
cameFrom: ArcIndex ← noArc];
Route: TYPE = REF RouteRec;
RouteRec: TYPE = RECORD [
cameFrom: ArcIndex ← noArc];
RouteSurface: PUBLIC PROC [surface: Surface] = {
EachFlatWire: RefTab.EachPairAction = {
flatWire: CoreFlat.FlatWire ← NARROW[key];
nodes: Nodes ← NARROW[val];
nodeDataTable: RefTab.Ref ← RouteFlatWire[flatWire, nodes];
};
[] ← RefTab.Pairs[surface.flatWires, EachFlatWire];
};
Avoids barriers but does not erect any. It is up to the caller to install the route found into the surface.
RouteFlatWire: PROC [flatWire: CoreFlat.FlatWire, nodes: Nodes] RETURNS [nodeDataTable: RefTab.Ref] = {
nodeDataTable ← RefTab.Create[];
FOR nl: Nodes ← nodes, nl.rest UNTIL nl=NIL DO
IF NOT RefTab.Insert[nodeDataTable, nl.first, NEW[NodeData]] THEN ERROR;
ENDLOOP;
};
END.