file ///StdCell/SCWidthUtilImpl.mesa
placement utility routines
-- InitGetChanWidth - initialize for determining the width of a channel
-- NewWsEntry - get a new wire segment entry and insert pos, return location
-- EnterNet - enter a net on a channel into data base
-- EnterRowDat - enter routing data for one side of one row into data base
-- EnterSideDat - enter routing data for one side of one side into data base
-- EnterExitDat - enter exit data for a channel into routing data base
-- EnterMinDat - minmium route channels need special processing to
include the minimun number of wire segments of minimum length
-- SortPinDat - sort the pin data
-- SortLimitDat - sort the data representing the extremes of each net on each channel
-- GetChanWl - find wirelength for this channel
-- MaxTrackDensity - find maximum track density on a channel
-- GetChanWidth - get width of channel specified
-- EnterCntdDat - enter data for connections between horiz and vert channels
-- GetSideWidth - get width of channel on side
-- AllChanWidths - find widths of all channels
DIRECTORY
RTBasic,
SC,
SCChanUtil,
SCNetUtil,
SCPrivate,
SCRowUtil,
SCWidthUtil,
SCInstUtil;
SCWidthUtilImpl: CEDAR PROGRAM
IMPORTS SC, SCChanUtil, SCNetUtil, SCInstUtil, SCRowUtil
EXPORTS SCWidthUtil
SHARES SC =
BEGIN
initialize for determining the width of a channel
InitOrTerm: TYPE = {init, term};
InitGetChanWidth: PROCEDURE [handle: SC.Handle, whatToDo: InitOrTerm] = {
EachNet: SCNetUtil.EachNetProc = {
net.bounds1 ← net.bounds2 ← NIL;
net.minPinDist ← LAST[INT];
net.lastEntry ← NIL};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
layoutData.wireSegPins ← NEW[SCPrivate.WireSegPinsRec];
layoutData.wireSegs ← NEW[SCPrivate.WireSegsRec];
[] ← SCNetUtil.EnumerateNets[handle, EachNet];
IF whatToDo = init THEN {
layoutData.wireSegs ← NEW[SCPrivate.WireSegsRec];
layoutData.wireSegPins ← NEW[SCPrivate.WireSegPinsRec]}
ELSE {
layoutData.wireSegs ← NIL; layoutData.wireSegPins ← NIL}};

get a new wire segment entry and insert pos, return location
NewWsEntry: PROCEDURE[handle: SC.Handle, pos: SC.Number, side: SC.Side] RETURNS [wireSeg: SCPrivate.WireSeg] = {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
wireSegs: SCPrivate.WireSegs ← layoutData.wireSegs;
wireSegs.nWireSegsOnCh ← wireSegs.nWireSegsOnCh + 1;
wireSeg ← NEW[SCPrivate.WireSegRec ← [pos, side]];
wireSegs.segs[wireSegs.nWireSegsOnCh] ← wireSeg};
enter a net on a channel into data base
EnterNet: PROCEDURE[handle: SC.Handle, net: SCPrivate.Net, pos: SC.Number, side: RTBasic.Side, minMaxRoute: SCPrivate.RouteType] = {
the type of route on this channel determines how the data is stored
SELECT minMaxRoute FROM
maxRoute => {
IF net.bounds1 = NIL THEN
{net.bounds1 ← NewWsEntry[handle, pos, left];
net.bounds2 ← NewWsEntry[handle, pos, right]}
ELSE
{net.bounds1.pos ← MIN[net.bounds1.pos, pos];
net.bounds2.pos ← MAX[net.bounds2.pos, pos]}};
minRoute => {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
wireSegPins: SCPrivate.WireSegPins ← layoutData.wireSegPins;
wireSegPin: SCPrivate.WireSegPin ← NEW[SCPrivate.WireSegPinRec ← [pos, net, side]];
wireSegPins.nPinsOnCh ← wireSegPins.nPinsOnCh +1;
wireSegPins.pins[wireSegPins.nPinsOnCh] ← wireSegPin};
ENDCASE};
enter routing data for one side of one row into data base
EnterRowDat: PROCEDURE[handle: SC.Handle, row: SCPrivate.MaxRowSr, side, intrestingSide: SC.Side, minMaxRoute: SCPrivate.RouteType] = {
InstProc: SCRowUtil.EachInstProc = {
PinProc: SCInstUtil.EachPinProc = {
IF netPin.pin # NIL AND netPin.net # NIL THEN {
pd: SCInstUtil.PinDescription ← SCInstUtil.PosOf[instance, netPin.pin];
IF pd.sideOn = intrestingSide THEN {
net: SCPrivate.Net ← netPin.net;
IF net # NIL THEN
EnterNet[handle, net, instance.offset + lgRow.rowOrg.p + pd.xPos, intrestingSide, minMaxRoute]}}};
[ ] ← SCInstUtil.EnumeratePinsOnInst[instance, PinProc]};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRow: SCPrivate.LgRow ← layoutData.lgRows.rows[row];
[ ] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, InstProc]};
enter routing data for one side of one side into data base
EnterSideDat: PROCEDURE[handle: SC.Handle, side, intrestingSide, chanSide: SC.Side, minMaxRoute: SCPrivate.RouteType] = {
InstProc: SCRowUtil.EachInstProc = {
PinProc: SCInstUtil.EachPinProc = {
IF netPin.pin # NIL THEN {
pd: SCInstUtil.PinDescription ← SCInstUtil.PosOf[instance, netPin.pin];
IF pd.sideOn = intrestingSide AND netPin.net # NIL THEN {
net: SCPrivate.Net ← netPin.net;
IF net # NIL THEN {
xyPos: SC.Number;
SELECT side FROM
bottom => xyPos ← bpRow.sideOrg.p + instance.offset + pd.xPos;
right => xyPos ← bpRow.sideOrg.q + instance.offset + pd.yPos;
top => xyPos ← bpRow.sideOrg.p - instance.offset + pd.xPos;
left => xyPos ← bpRow.sideOrg.q - instance.offset + pd.yPos;
ENDCASE;
EnterNet[handle, net, xyPos, chanSide, minMaxRoute]}}}};
[ ] ← SCInstUtil.EnumeratePinsOnInst[instance, PinProc]};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
bpRow: SCPrivate.BpRow ← layoutData.bpRows[side];
[ ] ← SCRowUtil.EnumerateAllInstsOnSide[handle, side, InstProc]};
enter exit data for a channel into routing data base
EnterExitDat: PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan, lrSide: SCPrivate.LRSide, side: SC.Side, minMaxRoute: SCPrivate.RouteType] = {
ExitProc: SCChanUtil.EachExitProc = {
EnterNet[handle, exit.net, sideChan.sideChanPos + MAX[sideChan.sideChanWidth, sideChan.minSideChanWidth]/2, side, minMaxRoute]};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
sideChan: SCPrivate.SideChan ← layoutData.sideChans[lrSide];
[] ← SCChanUtil.EnumerateExits[handle, rowChan, lrSide, ExitProc]};
minmium route channels need special processing to
include the minimun number of wire segments of minimum length
EnterMinDat: PROCEDURE [handle: SC.Handle] = {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
wireSegPins: SCPrivate.WireSegPins ← layoutData.wireSegPins;
FOR index: SCPrivate.ZMaxPinsOnChSr IN [1 .. wireSegPins.nPinsOnCh] DO
entry: SCPrivate.WireSegPin ← wireSegPins.pins[index];
net: SCPrivate.Net ← entry.net;
last: SCPrivate.WireSegPin ← net.lastEntry;
check to see if a pin for this net has been seen before
IF last # NIL THEN {
see if an exit entry needs to be processed
IF last.side = left OR entry.side = right THEN {
[] ← NewWsEntry[handle, last.pos, last.side];
[] ← NewWsEntry[handle, entry.pos, entry.side]}
ELSE IF entry.side # last.side THEN {
two pins on different sides of chan, see if min dist
thisDist: SC.Number ← ABS[entry.pos - last.pos];
IF thisDist < net.minPinDist THEN {
net.minPinDist ← thisDist;
IF net.bounds1 = NIL THEN {
net.bounds1 ← NewWsEntry[handle, last.pos, last.side];
net.bounds2 ← NewWsEntry[handle, entry.pos, entry.side]}
ELSE {
net.bounds1.pos ← last.pos;
net.bounds2.pos ← entry.pos}}}};
net.lastEntry ← entry;
ENDLOOP};
sort the pin data
this uses a shell sort, see software tools by kernigan and pluager
SortPinDat: PROCEDURE [handle: SC.Handle] =
BEGIN
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
wireSegPins: SCPrivate.WireSegPins ← layoutData.wireSegPins;
gap: SCPrivate.ZMaxPinsOnChSr ← wireSegPins.nPinsOnCh /2;
WHILE gap >0 DO
FOR I: SCPrivate.ZMaxPinsOnChSr IN [gap+1 .. wireSegPins.nPinsOnCh] DO
J: INTEGER ← I - gap;
WHILE J > 0 DO
Jg: SCPrivate.MaxPinsOnChSr ← J + gap;
test and exchange if necessary
jgPtr: SCPrivate.WireSegPin ← wireSegPins.pins[Jg];
jPtr: SCPrivate.WireSegPin ← wireSegPins.pins[J];
IF jgPtr.pos < jPtr.pos THEN {
wireSegPins.pins[Jg] ← jPtr;
wireSegPins.pins[J] ← jgPtr};
J ← J -gap;
ENDLOOP ;
ENDLOOP;
gap ← gap /2;
ENDLOOP ;
END;
sort the data representing the extremes of each net on each channel
this uses a shell sort, see software tools by kernigan and pluager
SortLimitDat: PROCEDURE [handle: SC.Handle] =
BEGIN
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
wireSegs: SCPrivate.WireSegs ← layoutData.wireSegs;
gap: SCPrivate.ZMaxWireSegsSr ← wireSegs.nWireSegsOnCh /2;
WHILE gap > 0 DO
FOR I: SCPrivate.ZMaxWireSegsSr IN [ gap+1 .. wireSegs.nWireSegsOnCh ] DO
J: INTEGER ← I - gap;
WHILE J > 0 DO
Jg: SCPrivate.MaxWireSegsSr ← J +gap;
test and exchange if necessary
jgPtr: SCPrivate.WireSeg ← wireSegs.segs[Jg];
jPtr: SCPrivate.WireSeg ← wireSegs.segs[J];
IF jgPtr.pos < jPtr.pos THEN {
wireSegs.segs[Jg] ← jPtr;
wireSegs.segs[J] ← jgPtr}
ELSE IF jgPtr.pos <= jPtr.pos THEN {
positions are equal, test end types
IF jgPtr.endType = left AND jPtr.endType = right THEN {
wireSegs.segs[Jg] ← jPtr;
wireSegs.segs[J] ← jgPtr}};
J ← J - gap;
ENDLOOP ;
ENDLOOP;
gap ← gap /2;
ENDLOOP ;
END;
find wirelength for this channel
GetChanWl: PUBLIC PROCEDURE [handle: SC.Handle] RETURNS [wireLength: SC.Number ← 0] = {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
wireSegs: SCPrivate.WireSegs ← layoutData.wireSegs;
FOR index: SCPrivate.ZMaxWireSegsSr IN [1 .. wireSegs.nWireSegsOnCh] DO
wireSeg: SCPrivate.WireSeg ← wireSegs.segs[index];
IF wireSeg.endType = left THEN wireLength ← wireLength - wireSeg.pos
ELSE IF wireSeg.endType = right THEN wireLength ← wireLength + wireSeg.pos;
ENDLOOP};
find maximum track density on a channel
MaxTrackDensity: PROCEDURE[handle: SC.Handle] RETURNS [maxTracks: NAT ← 0] = {
nTracks: NAT ← 0;
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
wireSegs: SCPrivate.WireSegs ← layoutData.wireSegs;
FOR index: SCPrivate.ZMaxWireSegsSr IN [1 .. wireSegs.nWireSegsOnCh] DO
wireSeg: SCPrivate.WireSeg ← wireSegs.segs[index];
SELECT wireSeg.endType FROM
left => {
nTracks ← nTracks +1;
maxTracks ← MAX[maxTracks, nTracks]};
right => {
nTracks ← nTracks -1;
IF nTracks < 0 THEN SC.Error[programmingError, "Invalid wires in channel"]};
ENDCASE;
ENDLOOP};
GetChanWidth: PUBLIC PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan, fom: SCPrivate.FomType, doWidth: BOOLEAN]
RETURNS [chanWidth, wireLength: SC.Number ← 0] = {
IF doWidth THEN {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
pitch: SC.Number ← handle.rules.rowRules.trunkToTrunk;
minMaxRoute: SCPrivate.RouteType ← IF fom = wlFom THEN maxRoute
ELSE rowChan.routeType;
InitGetChanWidth[handle, init];
use figure of merit type to set flag
IF fom = wlFom THEN minMaxRoute ← maxRoute
ELSE minMaxRoute ← rowChan.routeType;
assemble data for pins on this channel
IF rowChan.chanNum = 1 THEN {
EnterSideDat[handle, bottom, top, bottom, minMaxRoute];
EnterRowDat[handle, 1, bottom, top, minMaxRoute]}
ELSE IF rowChan.chanNum = rowChans.count THEN {
EnterRowDat[handle, lgRows.count, top, bottom, minMaxRoute];
EnterSideDat[handle, top, bottom, top, minMaxRoute]}
ELSE {
EnterRowDat[handle, rowChan.chanNum-1, top, bottom, minMaxRoute];
EnterRowDat[handle, rowChan.chanNum, bottom, top, minMaxRoute]};
EnterExitDat[handle, rowChan, left, left, minMaxRoute];
EnterExitDat[handle, rowChan, right, right, minMaxRoute];
compute or estimate chwidth based on fom type
wireLength ← GetChanWl[handle];
IF fom = wlFom THEN
chanWidth ← wireLength * pitch * horzWireToAreaFact / lgRows.maxRowWidth
ELSE {
a minimum route channel requires special processing
IF minMaxRoute = minRoute THEN {
SortPinDat[handle];
EnterMinDat[handle]};
next sort the wireseg entries and find max track density
SortLimitDat[handle];
chanWidth ← MAX[1, MaxTrackDensity[handle]] * pitch};
InitGetChanWidth[handle, term];
}};
enter data for connections between horiz and vert channels
EnterCntdDat: PROCEDURE [handle: SC.Handle, lrSide: SCPrivate.LRSide, side, chanSide: SC.Side] = {
ChansProc: SCChanUtil.EachRowChanProc = {
ExitsProc: SCChanUtil.EachExitProc = {
EnterNet[handle, exit.net, rowChan.chanPos + MAX[rowChan.chanWidth, rowChan.minChanWidth]/2, chanSide, maxRoute]};
[] ← SCChanUtil.EnumerateExits[handle, rowChan, lrSide, ExitsProc]};
[] ← SCChanUtil.EnumerateRowChans[handle, ChansProc]};
get width of channel on side
GetSideWidth: PUBLIC PROCEDURE[handle: SC.Handle, lRSide: SCPrivate.LRSide, fom: SCPrivate.FomType] RETURNS [chanWidth, wireLength: SC.Number] = {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
acBuses: SCPrivate.AcBuses ← layoutData.acBuses;
powerBuses: SCPrivate.PowerBuses ← layoutData.powerBuses;
rules: SC.DesignRules ← NARROW[handle.rules];
pitch: SC.Number ← rules.sideRules.trunkToTrunk;
chanWidth ← acBuses[lRSide].width + powerBuses[lRSide].width;
InitGetChanWidth[handle, init];
SELECT lRSide FROM
right => {
EnterSideDat[handle, right, left, bottom, maxRoute];
EnterCntdDat[handle, right, right, top]};
left => {
EnterSideDat[handle, left, right, top, maxRoute];
EnterCntdDat[handle, left, left, bottom]};
ENDCASE;
compute or estimate channel width based on fom
wireLength ← GetChanWl[handle];
IF fom = wlFom THEN {
chanWidth ← chanWidth + wireLength*pitch*vertWireToAreaFact/layoutData.totHeight}
ELSE {
SortLimitDat[handle];
chanWidth ← chanWidth + MAX[1, MaxTrackDensity[handle]]*pitch};
InitGetChanWidth[handle, term]};

find widths of all channels
AllChanWidths: PUBLIC PROCEDURE[handle: SC.Handle, fom: SCPrivate.FomType] =
BEGIN
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
SideChan: SCChanUtil.EachSideChanProc = {
[sideChan.sideChanWidth, sideChan.wireLength] ← GetSideWidth[handle, lrSide, fom]};
RowChan: SCChanUtil.EachRowChanProc = {
[rowChan.chanWidth, rowChan.wireLength] ← GetChanWidth[handle, rowChan, fom, TRUE]};
[] ← SCChanUtil.EnumerateSideChans[handle, SideChan];
[] ← SCChanUtil.EnumerateRowChans[handle, RowChan];
END;
vertWireToAreaFact: SC.Number ← 3;
horzWireToAreaFact: SC.Number ← 3;
END.