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: SCPrivate.TBSide, 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.