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; 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; }; CreateSurface: PUBLIC PROC [sizes: SoftHdwBasics.ArrayPosition] RETURNS [surface: Surface] = { }; PlaceSurface: PUBLIC PROC [surface: Surface, placement: Placement] = { }; 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]; }; 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. SoftHdwPlaceAndRouteImpl.mesa Copyright Ó 1988 by Xerox Corporation. All rights reserved. Barth, November 2, 1988 12:30:45 pm PST 180 is the number of lambda for the grid when doing assembly language programming. Primitives Placement Surface 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. Avoids barriers but does not erect any. It is up to the caller to install the route found into the surface. Ê¿– "cedar" style˜codešœ™K™