SoftHdwPlaceAndRoute.mesa
Copyright Ó 1988 by Xerox Corporation. All rights reserved.
Barth, October 25, 1988 9:07:36 pm PDT
DIRECTORY CD, Core, CoreFlat, DABasics, RefTab, Rope, SoftHdwBasics;
Types
NodePositions: TYPE = LIST OF NodePosition;
NodePosition: TYPE = REF NodePositionRec;
NodePositionRec:
TYPE =
RECORD [
type: NodeType,
position: SoftHdwBasics.ArrayPosition];
NodeType:
TYPE = {horizontalShort, verticalShort, horizontalLong, verticalLong};
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: TYPE = REF PrimitivesRec;
PrimitivesRec:
TYPE =
RECORD [
each: RefTab.Ref ← NIL, -- maps Core.CellType to Primitive
publics: RefTab.Ref ← NIL]; -- maps Core.Wire to PrimitivePublic.
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.
Primitive: TYPE = REF PrimitiveRec;
PrimitiveRec:
TYPE =
RECORD [
resources: NodePositions,
tile: CD.Object];
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.
PrimitivePublic: TYPE = REF PrimitivePublicRec;
PrimitivePublicRec:
TYPE =
RECORD [
positions: NodePositions ← NIL,
output: BOOL ← FALSE];
The router is only required to connect to one of the node positions.
LoadLibrary:
PROC
RETURNS [primitives: Primitives];
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.
Transform:
PROC [oldRoot: Core.CellType, primitives: Primitives]
RETURNS [newRoot: Core.CellType];
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
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];
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.
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
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.
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];
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.
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];
Create a surface in which no nodes or arcs are assigned.
PlaceSurface:
PROC [surface: Surface, placement: Placement];
Assign the nodes used by the placed primitives. Simply assigning the value of PrimitivePublic to equivalenceClass should do the trick for that field.
RouteSurface:
PROC [surface: Surface];
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.
MarkSurfaceDirections:
PROC [surface: Surface];
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.
EmitSurface:
PROC [surface: Surface, placement: Placement]
RETURNS [object:
CD.Object];
Emit the surface given the placement and a (potentially) partial assignment of the nodes and arcs to flat wires.