file SCWidthUtilImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Bryan Preas, December 31, 1986 12:14:46 pm PST
placement utility routines
-- InitGetChanWidth - initialize for determining the width of a channel
-- EnterRowData - enter routing data for one side of one row into data base
-- EnterSideData - enter routing data for one side of one side into data base
-- EnterExitData - enter exit data for a channel into routing data base
-- EnterNetData - minmium route channels need special processing to
include the minimun number of wire segments of minimum length
-- SortLimitData - 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
-- EnterCntdData - enter data for connections between horiz and vert channels
-- GetSideWidth - get width of channel on side
-- AllChanWidths - find widths of all channels
DIRECTORY
CD, RTBasic, SC, SCChanUtil, SCNetUtil, SCPrivate, SCRoutePinsUtil, SCRowUtil, SCWidthUtil, SCInstUtil;
SCWidthUtilImpl: CEDAR PROGRAM
IMPORTS RTBasic, SC, SCChanUtil, SCNetUtil, SCInstUtil, SCRoutePinsUtil, SCRowUtil
EXPORTS SCWidthUtil
SHARES SC =
BEGIN
vertWireToAreaFact: SC.Number ← 3;
horzWireToAreaFact: SC.Number ← 3;
zeroRect: SC.Rect ← [0, 0, 0, 0];
initialize for determining the width of a channel
InitGetChanWidth: PROCEDURE [handle: SC.Handle] = {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
wireSegs: SCWidthUtil.WireSegs ← NEW[SCWidthUtil.WireSegsRec];
layoutData.placeDat ← wireSegs;
SCRoutePinsUtil.InitGetChanPins[handle]};
terminate for determining the width of a channel
TermGetChanWidth: PROCEDURE [handle: SC.Handle] = {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
layoutData.placeDat ← NIL;
SCRoutePinsUtil.TermGetChanPins[handle]};
enter routing data for one side of one row into data base
EnterRowData: PROCEDURE[handle: SC.Handle, row: SCPrivate.MaxRowSr, intrestingSide: SC.Side] = {
InstProc: SCRowUtil.EachInstProc = {
PinProc: SCInstUtil.EachPinProc = {
IF netPin.pin # NIL AND netPin.net # NIL THEN {
sideOn: SC.Side ← SCInstUtil.PosOf[instance, netPin.pin].sideOn;
IF sideOn = intrestingSide THEN {
net: SCPrivate.Net ← netPin.net;
IF net # NIL THEN {
pos: RTBasic.PQPos ← SCInstUtil.InstPosOf[handle, instance, netPin.pin];
SCRoutePinsUtil.EnterPin[pos.p, pos.p, 0, netPin, RTBasic.OtherSide[intrestingSide], FALSE]}}}};
[ ] ← 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
EnterSideData: PROCEDURE[handle: SC.Handle, side, intrestingSide, chanSide: SC.Side] = {
side is the side of the chip the the io row is on
intrestingSide is the side of the cell that the pin is on
chanSide is the side of the channel the pin is on
InstProc: SCRowUtil.EachInstProc = {
PinProc: SCInstUtil.EachPinProc = {
IF netPin.pin # NIL THEN {
sideOn: SC.Side ← SCInstUtil.PosOf[instance, netPin.pin].sideOn;
IF sideOn = intrestingSide AND netPin.net # NIL THEN {
net: SCPrivate.Net ← netPin.net;
IF net # NIL THEN {
pos: RTBasic.PQPos ← SCInstUtil.InstPosOf[handle, instance, netPin.pin];
pPos: SC.Number ← SELECT side FROM
bottom, top => pos.p,
left, right => pos.q,
ENDCASE => SC.Error[programmingError, "Not suppose to happen."];
SCRoutePinsUtil.EnterPin[pPos, pPos, 0, netPin, chanSide, FALSE]}}}};
[ ] ← 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 structure
EnterExitData: PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan, lrSide: SCPrivate.LRSide, side: SC.Side] = {
ExitProc: SCChanUtil.EachExitProc = {
SCRoutePinsUtil.EnterExit[exit, side]};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
sideChan: SCPrivate.SideChan ← layoutData.sideChans[lrSide];
[] ← SCChanUtil.EnumerateExits[handle, rowChan, lrSide, ExitProc]};
sort the data representing the extremes of each net on each channel. this uses a shell sort, see software tools by kernigan and pluager
SortLimitData: PROCEDURE [handle: SC.Handle] = {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
wireSegs: SCWidthUtil.WireSegs ← NARROW[layoutData.placeDat];
gap: SCWidthUtil.ZMaxWireSegsSr ← wireSegs.nWireSegsOnCh /2;
WHILE gap > 0 DO
FOR I: SCWidthUtil.ZMaxWireSegsSr IN [ gap+1 .. wireSegs.nWireSegsOnCh ] DO
J: INTEGER ← I - gap;
WHILE J > 0 DO
Jg: SCWidthUtil.MaxWireSegsSr ← J +gap;
test and exchange if necessary
jgPtr: SCWidthUtil.WireSeg ← wireSegs.segs[Jg];
jPtr: SCWidthUtil.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};
find wirelength for this channel
GetChanWl: PROCEDURE [handle: SC.Handle] RETURNS [score: SC.Number ← 0] = {
ScoreNet: SCNetUtil.EachNetProc = {
netDat: SCRoutePinsUtil.NetDat ← NARROW[net.netDat];
IF netDat # NIL THEN score ← score + (netDat.bounds2 - netDat.bounds1)};
[] ← SCNetUtil.EnumerateNets[handle, ScoreNet]};
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: SCWidthUtil.WireSegs ← NARROW[layoutData.placeDat];
FOR index: SCWidthUtil.ZMaxWireSegsSr IN [1 .. wireSegs.nWireSegsOnCh] DO
wireSeg: SCWidthUtil.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] = {
NetProc: SCRoutePinsUtil.NetProc = {
netDat: SCRoutePinsUtil.NetDat ← NARROW[net.netDat];
IF netDat # NIL THEN {
IF netDat.bounds1 < netDat.bounds2 THEN {
wireSegs.nWireSegsOnCh ← wireSegs.nWireSegsOnCh + 1;
wireSegs.segs[wireSegs.nWireSegsOnCh] ← NEW[SCWidthUtil.WireSegRec ← [netDat.bounds1, left]];
wireSegs.nWireSegsOnCh ← wireSegs.nWireSegsOnCh + 1;
wireSegs.segs[wireSegs.nWireSegsOnCh] ← NEW[SCWidthUtil.WireSegRec ← [netDat.bounds2, right]]}}};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
wireSegs: SCWidthUtil.WireSegs;
IF doWidth THEN {
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
pitch: SC.Number ← handle.rules.rowRules.trunkToTrunk;
InitGetChanWidth[handle];
wireSegs ← NARROW[layoutData.placeDat];
assemble data for pins on this channel
IF rowChan.chanNum = 1 THEN {
EnterSideData[handle, bottom, top, bottom];
EnterRowData[handle, 1, bottom]}
ELSE IF rowChan.chanNum = rowChans.count THEN {
EnterRowData[handle, lgRows.count, top];
EnterSideData[handle, top, bottom, top]}
ELSE {
EnterRowData[handle, rowChan.chanNum-1, top];
EnterRowData[handle, rowChan.chanNum, bottom]};
EnterExitData[handle, rowChan, left, left];
EnterExitData[handle, rowChan, right, right];
compute or estimate chwidth based on fom type
SCRoutePinsUtil.EnterNetDat[handle, rowChan.chanNum, NIL, NIL, NetProc];
wireLength ← GetChanWl[handle];
IF fom = wlFom THEN
chanWidth ← wireLength * pitch * horzWireToAreaFact / lgRows.maxRowWidth
ELSE {
next sort the wireseg entries and find max track density
SortLimitData[handle];
chanWidth ← 2*handle.rules.rowRules.trunkToEdge + pitch*(MAX[1, MaxTrackDensity[handle]] - 1)};
TermGetChanWidth[handle]}};
enter data for connections between horiz and vert channels
EnterCntdData: PROCEDURE [handle: SC.Handle, lrSide: SCPrivate.LRSide, chanSide: SC.Side] = {
ChansProc: SCChanUtil.EachRowChanProc = {
ExitsProc: SCChanUtil.EachExitProc = {
SCRoutePinsUtil.EnterExit[exit, lrSide]};
[] ← 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 ← 0] = {
NetProc: SCRoutePinsUtil.NetProc = {
netDat: SCRoutePinsUtil.NetDat ← NARROW[net.netDat];
IF netDat # NIL THEN {
IF netDat.bounds1 < netDat.bounds2 THEN {
wireSegs.nWireSegsOnCh ← wireSegs.nWireSegsOnCh + 1;
wireSegs.segs[wireSegs.nWireSegsOnCh] ← NEW[SCWidthUtil.WireSegRec ← [netDat.bounds1, left]];
wireSegs.nWireSegsOnCh ← wireSegs.nWireSegsOnCh + 1;
wireSegs.segs[wireSegs.nWireSegsOnCh] ← NEW[SCWidthUtil.WireSegRec ← [netDat.bounds2, right]]}}};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
wireSegs: SCWidthUtil.WireSegs;
powerBuses: SCPrivate.PowerBuses ← layoutData.powerBuses;
rules: SC.DesignRules ← NARROW[handle.rules];
pitch: SC.Number ← rules.sideRules.trunkToTrunk;
InitGetChanWidth[handle];
wireSegs ← NARROW[layoutData.placeDat];
SELECT lRSide FROM
right => {
EnterSideData[handle, right, left, top];
EnterCntdData[handle, right, bottom]};
left => {
EnterSideData[handle, left, right, bottom];
EnterCntdData[handle, left, top]};
ENDCASE;
compute or estimate channel width based on fom
SCRoutePinsUtil.EnterNetDat[handle, 0, NIL, NIL, NetProc];
wireLength ← GetChanWl[handle];
IF fom = wlFom THEN {
chanWidth ← chanWidth + wireLength*pitch*vertWireToAreaFact/layoutData.totHeight}
ELSE {
SortLimitData[handle];
chanWidth ← chanWidth + MAX[1, MaxTrackDensity[handle]]*pitch};
TermGetChanWidth[handle]};
find widths of all channels
AllChanWidths: PUBLIC PROCEDURE[handle: SC.Handle, fom: SCPrivate.FomType] = {
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.