Adder:
CEDAR
PROGRAM
IMPORTS Basics, CDCells, CMos, IFUPW, PW, PWBasics
EXPORTS IFUPW =
BEGIN OPEN IFUPW;
AdderTree:
PUBLIC
PROC[
design: CD.Design,
firstSumBits: CARDINAL,
interleaveDepth: CARDINAL,
resultSums: CARDINAL,
names: LIST OF AdderNames ← NIL,
blankCells:
LIST
OF
BOOL ←
NIL ]
RETURNS[new: PW.ObjName]= { -- positive bus on top
Generates a flat adder of width firstSumBits * interleaveDepth with resultSums results
For instance:
AdderTree[32, 1, 1] => One ordinary 32 bit adder
AdderTree[8, 4, 1] => One 32 bit adder organized in the Dragon byte format
AdderTree[8, 4, 4] => Four 8 bit adders organized in the Dragon byte format
Parameter Requirements: (for now at least)
all parameter must be powers of 2
IF firstSumBits is 1 THEN resultSums must be 1
resultSums must be <= interleaveDepth
Uses 4 cells:
AdderSum, AdderGCP0, AdderGCP1 and AdderWireTile;
AdderWireTile contains 7 conditional objects:
Pass, ExtRt, ExtLt, ConnLtRt, ConnLtLt, ConnLtLtX and ConnRtRt
iDepth1: CARDINAL ← PW.TwoToTheLog2[interleaveDepth];
iDepth2: CARDINAL ← PW.TwoToTheLog2[resultSums];
size1: CARDINAL ← PW.TwoToTheLog2[firstSumBits];
size2: CARDINAL ← iDepth1/iDepth2;
levels1: CARDINAL ← PW.Log2[size1]; -- Not counting zero
levels2: CARDINAL ← PW.Log2[size2]; -- Not counting zero
tree2InputsPos: BOOL ← (levels1 MOD 2)=1; -- => upside down
tree1, tree2: PW.ObjName ← NIL;
xform, base: PW.ObjName ← NIL;
outPutD1: CARDINAL ← (levels1+1)/2*iDepth1; -- Tree1 output side depth
outNotD1: CARDINAL ← levels1 /2*iDepth1; -- Tree1 not output side depth
inPutD2: CARDINAL ← levels2 /2*iDepth2+iDepth1; -- Tree2 input side depth+xform
inNotD2: CARDINAL ← (levels2+1)/2*iDepth2; -- Tree2 not input side depth
IF levels1#0
THEN {
PWBasics.Output["\nBuilding Adder tree1"];
tree1 ← AdderGCPTree[
design: design,
size: size1,
depth: iDepth1,
endCell: levels2= 0,
inputsPos: FALSE,
inPutPad: 0,
inNotPad: 0,
outPutPad: inPutD2 - MIN[outPutD1, inPutD2],
outNotPad: inNotD2 - MIN[outNotD1, inNotD2],
blankCells: blankCells,
names: names ]};
IF levels2#0
THEN {
PWBasics.Output["\nBuilding Adder tree2"];
tree2 ← AdderGCPTree[
design: design,
size: size2,
depth: iDepth2,
endCell: TRUE,
inputsPos: tree2InputsPos,
inPutPad: outPutD1 - MIN[inPutD2, outPutD1],
inNotPad: outNotD1 - MIN[inNotD2, outNotD1],
outPutPad: 0,
outNotPad: 0,
blankCells: NIL,
names: names ] };
IF levels1#0
AND levels2#0
THEN {
PWBasics.Output["\nBuilding Adder xform"];
xform ← AdderIDepthXForm[iDepth1, iDepth2]; -- Defined for positive bus
IF NOT tree2InputsPos THEN xform ← PW.FlipY[xform]};
PWBasics.Output["\nBuilding Adder base"];
base ← AdderBaseTree[size1, iDepth1, blankCells];
PWBasics.Output["\nBuilding Adder ... "];
IF levels1#0
AND levels2#0
THEN
IF tree2InputsPos
THEN new ← PW.AbutY[tree2, xform]
ELSE new ← PW.AbutY[xform, tree2];
new ← PW.AbutX[tree1, new];
new ← PW.AbutY[base, new];
PWBasics.Output["done\n"]};
AdderGCPTree:
PROC[
-- positive bus on top
design: CD.Design,
size: CARDINAL,
depth: CARDINAL,
endCell: BOOL,
inputsPos: BOOL,
inPutPad: CARDINAL,
inNotPad: CARDINAL,
outPutPad: CARDINAL,
outNotPad: CARDINAL,
blankCells: LIST OF BOOL ← NIL,
names: LIST OF AdderNames ← NIL] RETURNS[new: PW.ObjName] = {
InputSide: PROC[levIndex: CARDINAL] RETURNS[BOOL] = {RETURN[(levIndex MOD 2)=0]};
list: LIST OF PW.ObjName ← NIL;
tile: PW.ObjName ← NIL;
sizeUsed: CARDINAL ← IF endCell THEN size ELSE size-1;
outLevel: CARDINAL ← PW.Log2[size];
topPad: CARDINAL;
botPad: CARDINAL;
topTile: PW.ObjName;
botTile: PW.ObjName;
sglBlank: PW.ObjName ← PW.Inst["AdderWireTile", LIST[ ], FALSE];
sglExtend: PW.ObjName ← PW.Inst["AdderWireTile", LIST["ExtLt", "ExtRt"], FALSE];
sglExtLt: PW.ObjName ← PW.Inst["AdderWireTile", LIST["ExtLt"], FALSE];
endCellOutsOnInputSide: BOOL ← NOT InputSide[outLevel];
wires: GCPWires ← GCPWireGen[PW.Log2[depth], blankCells, design, names];
FOR index:
CARDINAL
DECREASING
IN [0..sizeUsed)
DO
FOR group:
CARDINAL
DECREASING
IN [0..depth)
DO
tile, cell: PW.ObjName ← NIL;
input, other: PW.ObjName ← NIL;
level: CARDINAL ← 0;
isEdgeCell: BOOL ← FALSE;
isEndCell: BOOL ← FALSE;
inputSide: LIST OF PW.ObjName ← NIL;
otherSide: LIST OF PW.ObjName ← NIL;
wire: GCPWireNames ← wires[group];
test: CARDINAL ← 0;
PWBasics.Output["."];
FOR test←index, test/2 WHILE (test MOD 2 )=1 DO level ← level +1 ENDLOOP;
test ← Basics.BITXOR[index/2, index];
isEndCell ← level = outLevel; -- EndCell would connect at outLevel
isEdgeCell ← isEndCell AND (group = (depth-1));
FOR lev:
CARDINAL
DECREASING
IN (0..outLevel]
DO
tile ← wire[(
SELECT lev
FROM
> level+1 =>
IF
PW.XthBitOfN[lev-1, test]
THEN (IF level=0 AND InputSide[lev] THEN extPass ELSE pass)
ELSE (IF level=0 AND InputSide[lev] THEN extend ELSE blank),
level+1 => IF PW.XthBitOfN[lev, index] THEN driveLtX ELSE driveRt,
level => IF isEdgeCell THEN connNm ELSE conn,
< level => IF InputSide[level]=InputSide[lev] THEN extend ELSE extLt,
ENDCASE => ERROR)];
IF isEndCell
AND outLevel>1
AND InputSide[lev]#InputSide[level]
THEN tile ← wire
[(IF lev>2 THEN blank ELSE IF isEdgeCell THEN driveRtNm ELSE driveRt)];
IF InputSide[lev]
THEN inputSide ← CONS[tile, inputSide]
ELSE otherSide ← CONS[tile, otherSide];
ENDLOOP;
tile ←
IF Blanking[group, blankCells]
THEN "AdderGCPBlank"
ELSE
IF InputSide[level] = inputsPos
THEN "AdderGCP1" -- Defined Pos inputs UP and inverted output Down
ELSE "AdderGCP0"; -- Defined Pos output UP and inverted inputs Down
IF inputsPos THEN tile ← PW.FlipY[tile]; -- Input side down
input ← PW.AbutListY[ inputSide];
IF input#NIL THEN input ← PW.FlipY[input];
other ← PW.AbutListY[ otherSide];
topPad ← inNotPad+(IF InputSide[outLevel] THEN outNotPad ELSE outPutPad);
botPad ← inPutPad+(IF InputSide[outLevel] THEN outPutPad ELSE outNotPad);
topTile ← IF InputSide[level] THEN sglExtLt ELSE sglExtend;
botTile ← IF InputSide[level] THEN sglExtend ELSE sglExtLt;
IF isEndCell
AND outLevel<2
THEN {
-- not yet included in tree
IF endCellOutsOnInputSide
AND botPad>=depth
THEN {
tile←
PW.AbutY[
PW.FlipY[
wire[(IF isEdgeCell THEN driveRtNm ELSE driveRt)] ], tile];
botTile ← sglBlank;
botPad ← botPad-depth};
IF
NOT endCellOutsOnInputSide
AND topPad>=depth
THEN
{tile ← PW.AbutY[tile, wire[IF isEdgeCell THEN driveRtNm ELSE driveRt]];
topTile ← sglBlank;
topPad ← topPad-depth } };
THROUGH [0..topPad) DO tile ← PW.AbutY[tile, topTile] ENDLOOP;
THROUGH [0..botPad) DO tile ← PW.AbutY[botTile, tile] ENDLOOP;
cell ← PW.AbutListY[ LIST[input, tile, other]]; -- Input side down
IF inputsPos THEN cell ← PW.FlipY[cell]; -- positive side up
new ← PW.AbutX[cell, new];
ENDLOOP;
ENDLOOP };
AdderIDepthXForm:
PROC[ depth1, depth2:
CARDINAL]
-- for positive bus (top)
RETURNS[new: PW.ObjName] = { -- for top positive bus
xIndexRange: CARDINAL ← (depth1/depth2)/2;
yIndexRange: CARDINAL ← (depth1/depth2)/2;
xSumRange: CARDINAL ← depth1/xIndexRange;
ySumRange: CARDINAL ← xSumRange/2;
conn, cross, pass, extend, blank, cell: PW.ObjName;
conn ← PW.Inst["AdderWireTile", LIST["ConnLtLtX"], FALSE];
conn ← PW.AbutY[ PW.Inst["AdderWireTile", LIST["ExtLt", "ConnRtLtX"], FALSE], conn];
cross ← PW.Inst["AdderWireTile", LIST["ExtLt", "ExtRt", "Pass"], FALSE];
cross ← PW.AbutY[ cross, cross];
pass ← PW.Inst["AdderWireTile", LIST["Pass"], FALSE];
pass ← PW.AbutY[ pass, pass];
extend ← PW.Inst["AdderWireTile", LIST["ExtLt", "ExtRt"], FALSE];
extend ← PW.AbutY[ extend, extend];
blank ← PW.Inst["AdderWireTile", LIST[ ], FALSE];
blank ← PW.AbutY[ blank, blank];
new ← NIL;
Build from Rt to Lt and bottom to top assuming top bus application
FOR xIndex:
CARDINAL
DECREASING
IN [0..xIndexRange)
DO
FOR xSum:
CARDINAL
DECREASING
IN [0..xSumRange)
DO
cell ← NIL;
FOR ySum:
CARDINAL
DECREASING
IN [0..ySumRange)
DO
FOR yIndex:
CARDINAL
DECREASING
IN [0..yIndexRange)
DO
cell ←
PW.AbutY[cell, (
SELECT
TRUE
FROM
ySum = xSum AND yIndex = xIndex => conn,
ySum >= xSum AND yIndex >= xIndex => cross,
yIndex > xIndex => pass,
ySum > xSum => extend
ENDCASE => blank)];
ENDLOOP
ENDLOOP;
new ← PW.AbutX[cell, new];
ENDLOOP
ENDLOOP};
Blanking:
PROC[index:
INT, blankCell:
LIST
OF
BOOL]
RETURNS [
BOOL] = {
IF blankCell=NIL THEN RETURN[FALSE];
IF index=0 THEN RETURN[blankCell.first];
IF index>0 THEN RETURN[Blanking[index-1, blankCell.rest]];
ERROR};
GCPWires: TYPE = REF GCPWireRec;
GCPWireRec: TYPE = RECORD[SEQUENCE size: CARDINAL OF GCPWireNames];
GCPWireNames: TYPE = ARRAY GCPWireType OF PW.ObjName;
GCPWireType:
TYPE =
{pass, blank, driveLtX, driveRt, extend, extLt, extPass, conn, connNm, driveRtNm};
GCPWireGen:
PROC[
iDepthLog: CARDINAL,
blankCells: LIST OF BOOL,
design: CD.Design,
names: LIST OF AdderNames ← NIL]
RETURNS[wires: GCPWires] = { -- for top bus
Wire:
PROC
[i: CARDINAL,
type: GCPWireType,
pieces: LIST OF PW.ROPE ← NIL,
alt: LIST OF PW.ROPE ← NIL,
flip: BOOL ← FALSE] = {
cell: PW.ObjName;
IF Blanking[i, blankCells] THEN pieces ← alt;
cell ← PW.Inst["AdderWireTile", pieces, FALSE];
IF flip THEN cell ← PW.FlipY[cell];
wires[i][type] ← PW.AbutY[wires[i][type], cell] };
iDepth: CARDINAL ← PW.TwoToThe[iDepthLog];
wires ← NEW[GCPWireRec[iDepth]];
Array set up so that if wires placed below GCP row must be flipped in Y
PWBasics.Output[" "];
FOR ii:
CARDINAL
IN [0..iDepth)
DO
-- cell group index
PWBasics.Output["!"];
FOR jj: CARDINAL DECREASING IN [0..iDepth) DO -- bottom to top
IF Blanking[jj, blankCells] THEN LOOP;
These are used for building the GCP trees
Wire[ii, pass, LIST["Pass"], LIST["Pass"]];
Wire[ii, blank, LIST[ ], LIST[ ] ];
Wire[ii, extLt, LIST["ExtLt"], LIST[ ] ];
Wire[ii, extend, LIST["ExtLt", "ExtRt"], LIST[ ] ];
Wire[ii, extPass, LIST["ExtLt", "ExtRt", "Pass"], LIST["Pass"] ];
SELECT jj
FROM
<ii => Wire[ii, driveLtX, LIST[ ], LIST[ ]];
=ii => Wire[ii, driveLtX, LIST["ConnLtLtX"], LIST[ ]];
ENDCASE=> Wire[ii, driveLtX, LIST["ExtLt", "Pass"], LIST["Pass"]];
SELECT jj
FROM
<ii => Wire[ii, driveRt, LIST["Pass"], LIST["Pass"]];
=ii => Wire[ii, driveRt, LIST["ConnLtRt"], LIST[ ]];
ENDCASE => Wire[ii, driveRt, LIST["ExtLt"], LIST[ ]];
SELECT jj
FROM
<ii => Wire[ii, conn, LIST["Pass"], LIST["Pass"]];
=ii => Wire[ii, conn, LIST["ConnLtLtX", "ConnRtRt"], LIST[ ]];
ENDCASE => Wire[ii, conn, LIST["ExtLt", "ExtRt", "Pass"], LIST["Pass"] ];
ENDLOOP;
IF ii=(iDepth-1)
THEN {
drRtNm: CD.ObPtr ← CDCells.CreateEmptyCell[];
connNm: CD.ObPtr ← CDCells.CreateEmptyCell[];
drRt: CD.ObPtr ← PWBasics.ObjFromName[design, wires[ii][driveRt]];
conn: CD.ObPtr ← PWBasics.ObjFromName[design, wires[ii][conn]];
size: Size ← PWBasics.GetISize[conn];
loc: Location ← [size.x-4, size.y-28];
nameRec: AdderNames;
[] ← PWBasics.IncludeApplication[drRtNm, drRt];
[] ← PWBasics.IncludeApplication[connNm, conn];
FOR jj: CARDINAL IN [0..iDepth) DO
IF Blanking[jj, blankCells] THEN LOOP;
IF names=
NIL
THEN nameRec ← [ ]
ELSE {nameRec ← names.first; names ← names.rest};
PutPin[drRtNm, [4,4], [loc.x, loc.y+20], CMos.pol, nameRec.gout ];
PutPin[drRtNm, [4,4], [loc.x, loc.y+12], CMos.pol, nameRec.cin ];
PutPin[drRtNm, [4,4], [loc.x, loc.y+04], CMos.pol, nameRec.pout ];
PutPin[connNm, [4,4], [loc.x, loc.y+20], CMos.pol, nameRec.gin ];
PutPin[connNm, [4,4], [loc.x, loc.y+12], CMos.pol, nameRec.cout ];
PutPin[connNm, [4,4], [loc.x, loc.y+04], CMos.pol, nameRec.pin ];
loc.y ← loc.y-28;
ENDLOOP;
PWBasics.RepositionCell[design, drRtNm];
PWBasics.RepositionCell[design, connNm];
wires[ii][driveRtNm] ← PWBasics.NameFromObj[drRtNm];
wires[ii][connNm] ← PWBasics.NameFromObj[connNm]};
ENDLOOP };
BaseWires: TYPE = REF BaseWireRec;
BaseWireRec: TYPE = RECORD[SEQUENCE size: CARDINAL OF BaseWireNames];
BaseWireNames: TYPE = ARRAY BaseWireType OF PW.ObjName;
BaseWireType: TYPE = {extConnRt, connLt};
BaseWireGen:
PROC[iDepthLog:
CARDINAL, blankCells:
LIST
OF
BOOL]
RETURNS[wires: BaseWires] = { -- for top bus
Wire:
PROC
[i: CARDINAL,
type: BaseWireType,
pieces: LIST OF PW.ROPE ← NIL,
alt: LIST OF PW.ROPE ← NIL,
flip: BOOL ← FALSE] = {
cell: PW.ObjName;
IF Blanking[i, blankCells] THEN pieces ← alt;
cell ← PW.Inst["AdderWireTile", pieces, FALSE];
IF flip THEN cell ← PW.FlipY[cell];
wires[i][type] ← PW.AbutY[wires[i][type], cell] };
iDepth: CARDINAL ← PW.TwoToThe[iDepthLog];
wires ← NEW[BaseWireRec[iDepth]];
Array set up so that if wires placed below GCP row must be flipped in Y
PWBasics.Output[" "];
FOR ii:
CARDINAL
IN [0..iDepth)
DO
-- cell group index
PWBasics.Output["!"];
FOR jj: CARDINAL IN [0..iDepth) DO -- bottom to top
IF Blanking[jj, blankCells] THEN LOOP;
These are used for connecting the summers below the GCP trees
SELECT jj
FROM
-- msb at bottom
<ii => Wire[ii, extConnRt, LIST["ExtLt", "Pass"], LIST["Pass"] ];
=ii => Wire[ii, extConnRt, LIST["ExtLt", "ConnRtRt"], LIST[ ], TRUE];
ENDCASE => Wire[ii, extConnRt, LIST["ExtLt", "ExtRt"], LIST[ ] ];
SELECT jj
FROM
-- msb at bottom
<ii => Wire[ii, connLt, LIST["ExtLt"], LIST[ ] ];
=ii => Wire[ii, connLt, LIST["ConnLtLt"], LIST[ ] ];
ENDCASE => Wire[ii, connLt, LIST["Pass"], LIST["Pass"] ];
ENDLOOP;
ENDLOOP };
AdderBaseTree:
PROC[size, depth:
CARDINAL, blankCells:
LIST
OF
BOOL ←
NIL]
RETURNS[new: PW.ObjName] = {
cell0, cell1, base: PW.ObjName ← NIL;
wires: BaseWires ← BaseWireGen[PW.Log2[depth], blankCells];
new ← NIL;
FOR index:
CARDINAL
IN [0..depth)
DO
cell0 ← PW.AbutX[cell0, wires[index][extConnRt]];
cell1 ← PW.AbutX[cell1, wires[index][connLt]];
base ←
PW.AbutX[base, (
IF Blanking[index, blankCells]
THEN "AdderSumBlank"
ELSE "AdderSum")];
ENDLOOP;
cell0 ← PW.AbutY[base, cell0];
cell1 ← PW.AbutY[base, cell1];
FOR index:
CARDINAL
IN [0..size)
DO
IF ((index
MOD 2) = 0)
THEN new ← PW.AbutX[new, cell0]
ELSE new ← PW.AbutX[new, cell1] ENDLOOP };
Adder32x1x1: PW.UserProc = {RETURN[ AdderTree[design, 32, 1, 1]]};
Adder8x4x1: PW.UserProc = {RETURN[ AdderTree[design, 8, 4, 1]]};
Adder8x4x4: PW.UserProc = {RETURN[ AdderTree[design, 8, 4, 4]]};
Adder8x4x4x2:
PW.UserProc = {
RETURN[ AdderTree[design, 8, 4, 4,
NIL, LIST[TRUE, FALSE, TRUE, FALSE]]]};
PW.Register[Adder32x1x1, "Adder32x1x1"];
PW.Register[Adder8x4x1, "Adder8x4x1"];
PW.Register[Adder8x4x4, "Adder8x4x4"];
PW.Register[Adder8x4x4x2, "Adder8x4x4x2"];
END.