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];
InitGetChanWidth: PROCEDURE [handle: SC.Handle] = {

layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
wireSegs: SCWidthUtil.WireSegs _ NEW[SCWidthUtil.WireSegsRec];
layoutData.placeDat _ wireSegs;
SCRoutePinsUtil.InitGetChanPins[handle]};

TermGetChanWidth: PROCEDURE [handle: SC.Handle] = {

layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
layoutData.placeDat _ NIL;
SCRoutePinsUtil.TermGetChanPins[handle]};

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]};

EnterSideData: PROCEDURE[handle: SC.Handle, side, intrestingSide, chanSide: SC.Side] = {
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]};

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]};

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;

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 {
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};

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]};

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];


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];

SCRoutePinsUtil.EnterNetDat[handle, rowChan.chanNum, NIL, NIL, NetProc];
wireLength _ GetChanWl[handle];
IF fom = wlFom THEN
chanWidth _ wireLength * pitch * horzWireToAreaFact / lgRows.maxRowWidth
ELSE {
SortLimitData[handle];
chanWidth _ 2*handle.rules.rowRules.trunkToEdge + pitch*(MAX[1, MaxTrackDensity[handle]] - 1)};
TermGetChanWidth[handle]}};

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]};

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;

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]};

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.
όfile SCWidthUtilImpl.mesa
Copyright c 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


initialize for determining the width of a channel 
terminate for determining the width of a channel 
enter routing data for one side of one row into data base 
enter routing data for one side of one side into data base 
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

enter exit data for a channel into routing data structure 
sort the data representing the extremes of each net on each channel. this uses a shell sort, see software tools by kernigan and pluager 
test and exchange if necessary 
positions are equal, test end types 
find wirelength for this channel 
find maximum track density on a channel 
assemble data for pins on this channel 
compute or estimate chwidth based on fom type 
next sort the wireseg entries and find max track density 
enter data for connections between horiz and vert channels 
get width of channel on side
compute or estimate channel width based on fom 
find widths of all channels 
Κ	~˜
codeš
œ™Kšœ
Οm
œ1™<Kšœ+Οk™.—K˜Kš
œ™Kš
ΟcG™GKš
ŸK™KKš
ŸM™MKš
ŸG™Gš
ŸC™CKš
œ=™=—Kš
ŸV™VKš
Ÿ/™/Kš
Ÿ<™<Kš
Ÿ0™0Kš
ŸM™MKš
Ÿ.™.Kš
Ÿ.™.K™š
ž	˜	KšžœžœX˜gK˜—šΟnœžœ
ž˜Kšžœ
žœ?˜RKšžœ˜Kšžœ
žœ˜K˜Kš
ž˜K˜Kšœžœ˜"Kšœžœ˜"šœ
žœ˜!K™—Kš
œ2™2š œž	œ
žœ˜3K˜Kšœ#žœ˜=Kšœ!žœ˜>Kš
œ˜Kš
œ)˜)K˜—Kš
œ1™1š œž	œ
žœ˜3K˜Kšœ#žœ˜=Kšœžœ
˜Kš
œ)˜)K˜—Kš
œ:™:š œž	œ	žœ2žœ
˜`K˜š œ˜$š œ˜#š
žœžœ
žœžœ
žœ˜0Kšœžœ6˜@šžœžœ˜!Kš
œ ˜ šžœžœ
žœ˜Kš
œH˜HKšœUžœ˜`———K˜Kš
œ9˜9——K˜Kšœ#žœ˜=Kš
œ5˜5Kš
œ@˜@—Kš
œ;™;š 
œž	œ	žœ)žœ
˜XKš
œ1™1Kš
œ9™9Kš
œ1™1K™š œ˜$š œ˜#šžœžœ
žœ˜Kšœžœ6˜@šžœžœžœ
žœ˜6Kš
œ ˜ šžœžœ
žœ˜Kš
œH˜Hšœžœžœ
˜#Kš
œ˜Kš
œ˜Kšžœ9˜@—Kšœ:žœ˜E———K˜Kš
œ9˜9—K˜—Kšœ#žœ˜=Kš
œ1˜1Kš
œA˜A—K˜Kš
œ:™:š 
œž	œ	žœEžœ
˜tK˜š œ˜%Kš
œ'˜'K˜—Kšœ#žœ˜=Kš
œ<˜<Kš
œC˜C—K˜Kš
œˆ
™ˆ
š 
œž	œ
žœ˜0K˜Kšœ#žœ˜=Kšœ!žœ˜=Kš
œ<˜<šžœ	ž˜šžœ
 
œžœ%žœ
˜Lš 
œžœ˜šžœž˜Kš œ%˜'K˜Kš
œ™Kš
œ/˜/Kš
œ-˜-šžœžœ˜Kš
œ˜Kš
œ˜—šžœ
žœžœ˜$Kš
œ$™$šžœžœžœ˜7Kš
œ˜Kš
œ˜——Kš
œ˜Kšžœ˜	——Kšžœ
˜—Kš
œ
˜
Kšžœ˜
——Kš
œ!™!š
 	œž	œ
žœ	žœ	žœ˜KK˜š œ˜#Kšœ!žœ
˜4Kšžœ
žœ
žœ4˜HK˜—Kš
œ0˜0—K˜Kš
œ(™(š
 œž	œ	žœ	žœ
žœ	˜NKšœ	žœ˜K˜Kšœ#žœ˜=Kšœ!žœ˜=šžœ#žœžœ
˜JKš
œ4˜4šžœž˜š
œ	˜	Kš
œ˜Kšœžœ˜%—š
œ
˜
Kš
œ˜Kšžœ
žœ
žœ6˜L—Kšžœ
˜—Kšžœ˜	—K˜—š
 œžœ
ž	œ	žœFžœ
˜wKšžœžœ˜2K˜š œ˜$Kšœ!žœ
˜4šžœ
žœ
žœ˜šžœ!žœ˜)Kš
œ4˜4Kšœ(žœ2˜]Kš
œ4˜4Kšœ(žœ6˜a——K˜—Kšœ#žœ˜=Kš
œ˜šžœ	žœ˜Kš
œ-˜-Kš
œ3˜3Kšœžœ-˜6K˜Kš
œ˜Kšœžœ˜'K˜K˜Kš
œ'™'šžœžœ˜Kš
œ+˜+Kš
œ ˜ —šžœ
žœ"žœ˜/Kš
œ(˜(Kš
œ(˜(—šžœ˜Kš
œ-˜-Kš
œ/˜/—Kš
œ+˜+Kš
œ-˜-K˜Kš
œ.™.Kšœ5žœžœ˜HKš
œ˜šžœ
ž˜Kš
œH˜H—šžœ˜Kš
œ9™9K˜Kšœ9žœ#˜_—Kš
œ˜——Kš
œ;™;š 
œž	œ
žœ-žœ
˜]K˜š 	œ ˜)š 	œ˜&Kš
œ*˜*—š
œD˜DK˜——Kš
œ7˜7—Kš
œ™š œžœ
ž	œ	žœ;žœžœ˜—
K˜š œ˜$Kšœ!žœ
˜4šžœ
žœ
žœ˜šžœ!žœ˜)Kš
œ4˜4Kšœ(žœ2˜]Kš
œ4˜4Kšœ(žœ6˜a——K˜—Kšœ#žœ˜=Kš
œ˜Kš
œ9˜9Kšœžœžœ˜-Kšœžœ'˜0K˜Kš
œ˜Kšœžœ˜'šžœž˜š
œ
˜
Kš
œ(˜(Kš
œ&˜&—š
œ	˜	Kš
œ+˜+Kš
œ"˜"—Kšžœ
˜K˜—Kš
œ/™/Kšœ'žœžœ˜:Kš
œ˜šžœ
žœ˜Kš
œQ˜Q—šžœ˜K˜Kšœžœ$˜?—Kš
œ˜—Kš
œ™š 
œžœ
ž	œ	žœ$˜NKšœ#žœ˜=š œ!˜)Kš
œS˜SK˜—š œ ˜'KšœMžœ˜TK˜—Kš
œ5˜5Kš
œ5˜5—Kšžœ
˜——…—!|2φ