DIRECTORY CD, Core, CoreFlat, DABasics, RefTab, Rope, SoftHdwBasics; SoftHdwPlaceAndRoute: CEDAR DEFINITIONS = BEGIN NodePositions: TYPE = LIST OF NodePosition; NodePosition: TYPE = REF NodePositionRec; NodePositionRec: TYPE = RECORD [ type: NodeType, position: SoftHdwBasics.ArrayPosition]; NodeType: TYPE = {horizontalShort, verticalShort, horizontalLong, verticalLong}; Primitives: TYPE = REF PrimitivesRec; PrimitivesRec: TYPE = RECORD [ each: RefTab.Ref _ NIL, -- maps Core.CellType to Primitive publics: RefTab.Ref _ NIL]; -- maps Core.Wire to PrimitivePublic. Primitive: TYPE = REF PrimitiveRec; PrimitiveRec: TYPE = RECORD [ resources: NodePositions, tile: CD.Object]; PrimitivePublic: TYPE = REF PrimitivePublicRec; PrimitivePublicRec: TYPE = RECORD [ positions: NodePositions _ NIL, output: BOOL _ FALSE]; LoadLibrary: PROC RETURNS [primitives: Primitives]; Transform: PROC [oldRoot: Core.CellType, primitives: Primitives] RETURNS [newRoot: Core.CellType]; Placement: TYPE = REF PlacementRec; PlacementRec: TYPE = RECORD [ root: Core.CellType, primitives: Primitives, positions: RefTab.Ref]; -- maps CoreFlat.FlatCellType to PositionRef PositionRef: TYPE = REF DABasics.Position; Place: PROC [root: Core.CellType, primitives: Primitives] RETURNS [placement: Placement]; PlacementToCD: PROC [placement: Placement] RETURNS [object: CD.Object]; MouseToCellPair: PROC [design: CD.Design, position: DABasics.Position, placement: Placement] RETURNS [legal, leftRight: BOOL _ FALSE, leftTop, rightBottom: CoreFlat.FlatCellType _ NIL]; Surface: TYPE = REF SurfaceRec; SurfaceRec: TYPE = RECORD [ sizes: SoftHdwBasics.ArrayPosition, flatWires: RefTab.Ref, -- maps CoreFlat.FlatWire to Nodes nodes: RefTab.Ref]; -- maps NodePosition to Node Nodes: TYPE = LIST OF Node; Node: TYPE = REF NodeRec; NodeRec: TYPE = RECORD [ position: NodePosition, flatCell: CoreFlat.FlatCellType _ NIL, flatWire: CoreFlat.FlatWire _ NIL, equivalenceClass: REF _ NIL, output: BOOL, arcs: SEQUENCE size: ArcIndex OF Arc]; ArcIndex: TYPE = CARDINAL; Arcs: TYPE = LIST OF Arc; Arc: TYPE = REF ArcRec; ArcRec: TYPE = RECORD [ flatWire: CoreFlat.FlatWire _ NIL, -- nil means unassigned direction: ArcDirection, this, that: Node _ NIL]; -- never nil after creation ArcDirection: TYPE = {thisToThat, thatToThis}; CreateSurface: PROC [sizes: SoftHdwBasics.ArrayPosition] RETURNS [surface: Surface]; PlaceSurface: PROC [surface: Surface, placement: Placement]; RouteSurface: PROC [surface: Surface]; MarkSurfaceDirections: PROC [surface: Surface]; EmitSurface: PROC [surface: Surface, placement: Placement] RETURNS [object: CD.Object]; END. êSoftHdwPlaceAndRoute.mesa Copyright Ó 1988 by Xerox Corporation. All rights reserved. Barth, October 25, 1988 9:07:36 pm PDT Theory This interface describes the transformation from a Core.CellType to a tiling which embodies both the placed primitives and the routing between them. Types position is dependent on type. If type is horizontalShort or verticalShort then all components of position are valid. If type is horizontalLong then position.minor and position.major.x are invalid. If type is verticalLong then position.minor and position.major.y are invalid. Primitives Primitives are described as if they were placed at the lower left corner of the lower left chip of the array ([[0, 0], [0, 0], [?, ?]]). Primitives come in chunks of minor arrays and so position.minor is invalid. The NodePositions found through publics describe the connection points of a public. A single RefTab is all that is necessary since the public wires of multiple CellTypes may not be shared. resources describe the routing nodes which are utilized by the primitive, including those used by the publics. tile is the object which must be emitted in the placed location. The router is only required to connect to one of the node positions. Builds a collection of primitives that maps the CMOSB library. Relies upon the immutability of the CMOSB primitives from the time that a .core file is written until this procedure is called. If the CMOSB .core file is changed then all .core files which depend upon it must be rebuilt before this procedure is invoked. Transforms a cell type based on CMOSB primitives into a cell type based on soft hardware library primitives. Initial implementation just builds a SymTab for the primitives and then replaces every cell in root which has an entry in the SymTab. This again relies on the immutability of the CMOSB .core file. Placement Uses primitives to define the cut set of root. Ensures there are enough feedthroughs in every row to handle the signals which must pass through. Surface All of the procedures below always use the same CoreFlat.FlatCellType and CoreFlat.FlatWire if the values are the same. This allows equality to be checked by comparing pointers rather than checking each bit of the value. Both flatCell and flatWire nil means the node is unassigned. Only flatWire not nil means the node is not part of a primitive. Only flatCell not nil means that the node is used by a primitive but is not a public wire. Both flatCell and flatWire not nil mean this node is part of a public wire of a primitive. Some day we might want to indicate the interior wires of primitives so flatCell#nil and flatWire=nil indicating an internal resource used by the primitive should not be relied upon. Create a surface in which no nodes or arcs are assigned. Assign the nodes used by the placed primitives. Simply assigning the value of PrimitivePublic to equivalenceClass should do the trick for that field. Assign nodes to flat wires so that all of the nodes with the same flat wire are connected by arcs. Two nodes with the same equivalenceClass and the same flatCell are implicitly connected, must have the same value for output, need not be connected by the router if output is false, and must not be connected if output is true. Given a placed and routed surface, set all of the Arc.direction fields so that the single output driving a set of nodes connected by arcs reaches all of the inputs. Emit the surface given the placement and a (potentially) partial assignment of the nodes and arcs to flat wires. Ê%˜codešœ™K™