MCEccImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Last Edited by: Don Curry June 29, 1987 9:45:14 pm PDT
Last Edited by: Gasbarro June 8, 1987 1:32:05 pm PDT
Dragon Memory Controler Ecc Wire Icon implementations.
DIRECTORY Core, CoreOps;
MCEccImpl: CEDAR PROGRAM
IMPORTS CoreOps
= BEGIN
MainTrees
In the case of the memory controler, n=64;
There is 1 full parity tree and Log2[n] subTrees.
FOR t IN [0..nofSubTrees), Tree t is the parity of 2^t groups each with n/2^(t+1) bits
Memory Controler: n=64, 1 parity tree and 6 subTrees
SubTree 0 is the parity of one 32 bit group (msb)
SubTree 5 is the parity of 32 one bit groups
This implementation assumes that there are two XOR rows. The first just computes the full parity. The second row does all of the subtrees using the various group parities from the full parity tree as the inputs.
The position of the XOR's in the full parity row is that of a simple flat tree. The position of the XOR's in the subtree row is similar except that each tree is shifted left by 2^t bits in order for them to fit together without conflict.
Log2: PROC[n: CARDINAL] RETURNS[log: CARDINAL𡤀] =
{FOR n ← n, n/2 WHILE n>1 DO log ← log+1 ENDLOOP};
MainTrees: PUBLIC PROC[n: CARDINAL] RETURNS[wire: Core.Wire] = {
logn:   CARDINAL ← Log2[n];
span:   CARDINAL;
groupSize: CARDINAL;
input:   Core.Wire  ← NewWires[n,   "in"];
out:   Core.Wire  ← NewWires[logn+1, "out"];
fullInLt:  Core.Wire  ← NewWires[n,   "tl"];
fullInRt:  Core.Wire  ← NewWires[n,   "tr"];
fullOut:  Core.Wire  ← NewWires[n,   "tm"];
subInLt:  Core.Wire  ← NewWires[n,   "bl"];
subInRt:  Core.Wire  ← NewWires[n,   "br"];
subOut:  Core.Wire  ← NewWires[n,   "bm"];
gnd:   Core.Wire  ← NewWires[0,   "Gnd"];
wire ← CoreOps.CreateWire[LIST[input,out,fullInLt,fullInRt,fullOut,subInLt,subInRt,subOut]];
Full Parity Tree
out[0] ← fullOut[n/2-1] ← NewWires[0];
span ← n/2; -- span of the two xor inputs (twice the length of a node wire)
FOR level: CARDINAL IN [1..logn] DO
FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO
phIdx: CARDINAL ← span-1 + levelIdx*2*span;
IF span>1
THEN {
fullInLt[phIdx] ← fullOut[phIdx-span/2] ← NewWires[0];
fullInRt[phIdx] ← fullOut[phIdx+span/2] ← NewWires[0]}
ELSE {
fullInLt[phIdx] ← input[phIdx]    ← NewWires[0];
fullInRt[phIdx] ← input[phIdx+1]   ← NewWires[0]};
ENDLOOP;
span ← span/2;
ENDLOOP;
SubTrees
out[1] ← fullOut[n/4-1]; -- first subtree needs no XORs in subtree row
groupSize ← n/4;
FOR tree: CARDINAL IN [1..logn) DO
span:  CARDINAL ← n/2;
out[tree+1] ← subOut[span-1 - groupSize] ← NewWires[0];
FOR span ← span, span/2 WHILE span>groupSize DO
FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO
phIdx: CARDINAL ← span-1 - groupSize + levelIdx*2*span;
IF span > 2*groupSize
THEN {
subInLt[phIdx]  ← subOut[phIdx-span/2] ← NewWires[0];
subInRt[phIdx]  ← subOut[phIdx+span/2] ← NewWires[0]}
ELSE IF groupSize>1
THEN {
subInLt[phIdx] ← fullOut[phIdx     - groupSize/2];
subInRt[phIdx] ← fullOut[phIdx + groupSize + groupSize/2]}
ELSE {
subInLt[phIdx] ← input[phIdx];
subInRt[phIdx] ← input[phIdx+2]};
ENDLOOP;
ENDLOOP;
groupSize ← groupSize/2;
ENDLOOP;
FOR index: CARDINAL IN [0..n) DO
IF fullInLt [index]=NIL THEN fullInLt [index] ← gnd;
IF fullInRt [index]=NIL THEN fullInRt [index] ← gnd;
IF fullOut [index]=NIL THEN fullOut [index] ← NewWires[0];
IF subInLt [index]=NIL THEN subInLt [index] ← gnd;
IF subInRt [index]=NIL THEN subInRt [index] ← gnd;
IF subOut [index]=NIL THEN subOut [index] ← NewWires[0];
ENDLOOP};
The normal way of computing the encode parity would be to first compute the check bits for the data, then compute the overall parity of data with check bits. This second operation would take Log2[Log2[n]+1] additional stages (3 for n=64 data bits). Instead we notice that the parity of the check bits is one for data bits checked by and odd number of check bits. These data bits are identified by the property of having a Ecc position index * with an odd number of 1's in it. Since the effect of each odd data bit is cancelled by the check bits, we can compute the overall parity of data with check bits by only computing the parity of all the even indexed data bits. Since one of the data bits is not present in the main trees, we make sure that it has no effect on the overall parity by assigning it an odd index (62).
Remember that although everything else (wires etc) are MSB=0, Ecc indexes are LSB=0. In addition (with n=64) the data in the code word is imagined to be in the top half at Ecc indexes 127 though 65 + 62 with check bits at 64, 32, 16, 8, 4, 2 and 1, and the parity bit at 0.
EvenIndex: PROC[i: CARDINAL] RETURNS[even: BOOLTRUE] =
{FOR i ← i, i/2 WHILE i#0 DO even ← ((i MOD 2)=1)#even ENDLOOP};
EncodeParity: PUBLIC PROC[n: CARDINAL] RETURNS[wire: Core.Wire] = {
logn:   CARDINAL ← Log2[n];
span:   CARDINAL;
input:   Core.Wire  ← NewWires[n, "in"];
out:   Core.Wire  ← NewWires[0, "out"];
treeInLt:  Core.Wire  ← NewWires[n, "l"];
treeInRt:  Core.Wire  ← NewWires[n, "r"];
treeOut:  Core.Wire  ← NewWires[n, "m"];
gnd:   Core.Wire  ← NewWires[0, "Gnd"];
wire ← CoreOps.CreateWire[LIST[input,out,treeInLt,treeInRt,treeOut]];
out ← treeOut[n/2-1] ← NewWires[0];
span ← n/2; -- span of the two xor inputs (twice the length of a node wire)
FOR level: CARDINAL IN [1..logn) DO
FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO
phIdx: CARDINAL ← span-1 + levelIdx*2*span;
IF span>2
THEN {
treeInLt[phIdx] ← treeOut[phIdx-span/2] ← NewWires[0];
treeInRt[phIdx] ← treeOut[phIdx+span/2] ← NewWires[0]}
ELSE {
off: CARDINALIF EvenIndex[2*n-1-phIdx] THEN 0 ELSE 1;
treeInLt[phIdx] ← input[phIdx-off]   ← NewWires[0];
treeInRt[phIdx] ← input[phIdx+off+1]  ← NewWires[0]};
ENDLOOP;
span ← span/2;
ENDLOOP;
FOR index: CARDINAL IN [0..n) DO
IF treeInLt [index]=NIL THEN treeInLt [index] ← gnd;
IF treeInRt [index]=NIL THEN treeInRt [index] ← gnd;
IF treeOut [index]=NIL THEN treeOut [index] ← NewWires[0];
IF input  [index]=NIL THEN input [index] ← NewWires[0];
ENDLOOP};
Puts 64 data bits in low order of 72 bits
EncodeParity64x8: PUBLIC PROC RETURNS[wire: Core.Wire] = {
wire ← EncodeParity64x8Heart[]; -- 64 data bits in high order of 72 bits
FOR i: INT IN [0..wire.size) DO
IF wire[i].size=72 THEN {
w: Core.Wire ← CoreOps.CreateWires[72, CoreOps.GetShortWireName[wire[i]]];
FOR j: INT IN [0..72) DO w[j] ← wire[i][(j+64) MOD 72] ENDLOOP;
wire[i] ← w};
ENDLOOP};
Nm: PROC[pre: Core.ROPE, i: CARDINAL] RETURNS[name: Core.ROPE] = {RETURN[NIL]};
Nm: PROC[pre: Core.ROPE, i: CARDINAL] RETURNS[name: Core.ROPE] =
{RETURN[IO.PutFR["%g%g", IO.rope[pre], IO.int[i]]]};
EncodeParity64x8Heart: PUBLIC PROC RETURNS[wire: Core.Wire] = {
n:    CARDINAL ← 64;
logn:   CARDINAL ← 6;
m:    CARDINAL ← 8;
span:   CARDINAL;
input:   Core.Wire  ← NewWires[n+m, "in"];
out:   Core.Wire  ← NewWires[0,  "out"];
treeInLt:  Core.Wire  ← NewWires[n+m, "l"];
treeInRt:  Core.Wire  ← NewWires[n+m, "r"];
treeOut:  Core.Wire  ← NewWires[n+m, "m"];
gnd:   Core.Wire  ← NewWires[0,  "Gnd"];
wire ← CoreOps.CreateWire[LIST[input,out,treeInLt,treeInRt,treeOut]];
treeOut[n/2-1] ← out;
span ← n/2; -- span of the two xor inputs (twice the length of a node wire)
FOR level: CARDINAL IN [1..logn) DO
FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO
phIdx: CARDINAL ← span-1 + levelIdx*2*span;
IF span>2
THEN {
treeInLt[phIdx] ← treeOut[phIdx-span/2] ← NewWires[0, Nm["T",phIdx-span/2]];
treeInRt[phIdx] ← treeOut[phIdx+span/2] ← NewWires[0, Nm["T",phIdx+span/2]]}
ELSE {
off: CARDINALIF EvenIndex[2*n-1-phIdx] THEN 0 ELSE 1;
treeInLt[phIdx] ← input[phIdx-off]   ← NewWires[0, Nm["I",phIdx-off]];
treeInRt[phIdx] ← input[phIdx+off+1]  ← NewWires[0, Nm["I",phIdx+off+1]]};
ENDLOOP;
span ← span/2;
ENDLOOP;
FOR index: CARDINAL IN [0..n+m) DO
IF treeInLt [index]=NIL THEN treeInLt [index] ← gnd;
IF treeInRt [index]=NIL THEN treeInRt [index] ← gnd;
IF treeOut [index]=NIL THEN treeOut [index] ← NewWires[0, Nm["t",index]];
IF input  [index]=NIL THEN input [index] ← NewWires[0, Nm ["i",index]];
ENDLOOP};
Puts 64 data bits in low order of 72 bits
ExtendedMainTrees64x8: PUBLIC PROC RETURNS[wire: Core.Wire] = {
wire ← ExtendedMainTrees64x8Heart[]; -- 64 data bits in high order of 72 bits
FOR i: INT IN [0..wire.size) DO
IF wire[i].size=72 THEN {
w: Core.Wire ← CoreOps.CreateWires[72, CoreOps.GetShortWireName[wire[i]]];
FOR j: INT IN [0..72) DO w[j] ← wire[i][(j+64) MOD 72] ENDLOOP;
wire[i] ← w};
ENDLOOP};
Include Next Level of trees (low oreder word with check bits and data bit 62)
Puts 64 data bits in high order of 72 bits
ExtendedMainTrees64x8Heart: PUBLIC PROC RETURNS[wire: Core.Wire] = {
n:    CARDINAL ← 64;
logn:   CARDINAL ← 6;
m:    CARDINAL ← 8;
logm:   CARDINAL ← 3;
span:   CARDINAL;
groupSize: CARDINAL;
input:   Core.Wire  ← NewWires[n+m, "in"];
out:   Core.Wire  ← NewWires[m-1, "out"];
dp:   Core.Wire  ← NewWires[0,  "dp"];
fullInLt:  Core.Wire  ← NewWires[n+m, "tl"];
fullInRt:  Core.Wire  ← NewWires[n+m, "tr"];
fullOut:  Core.Wire  ← NewWires[n+m, "tm"];
subInLt:  Core.Wire  ← NewWires[n+m, "bl"];
subInRt:  Core.Wire  ← NewWires[n+m, "br"];
subOut:  Core.Wire  ← NewWires[n+m, "bm"];
gnd:   Core.Wire  ← NewWires[0,  "Gnd"];
wire ← CoreOps.CreateWire
[LIST[input,out, dp,fullInLt,fullInRt,fullOut,subInLt,subInRt,subOut]];
Decode Full Parity Tree
span ← n/2; -- span of the two xor inputs (twice the length of a node wire)
FOR level: CARDINAL IN [1..logn] DO
FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO
phIdx: CARDINAL ← span-1 + levelIdx*2*span;
IF span>1
THEN {
fullInLt[phIdx] ← fullOut[phIdx-span/2] ← NewWires[0, Nm["F",phIdx-span/2]];
fullInRt[phIdx] ← fullOut[phIdx+span/2] ← NewWires[0, Nm["F",phIdx+span/2]]}
ELSE {
last1: CARDINALIF phIdx=n-2 THEN 1 ELSE 0;
fullInLt[phIdx] ← input[phIdx]    ← NewWires[0, Nm["I",phIdx]];
fullInRt[phIdx] ← input[phIdx+1+last1]  ← NewWires[0, Nm["I",phIdx+1+last1]]};
ENDLOOP;
span ← span/2;
ENDLOOP;
Decode Check Parity Tree
span ← m/2;
FOR level: CARDINAL IN [1..logm] DO
FOR levelIdx: CARDINAL IN [0..m/(2*span)) DO
phIdx: CARDINAL ← n + span-1 + levelIdx*2*span;
IF span>1
THEN {
fullInLt[phIdx] ← fullOut[phIdx-span/2] ← NewWires[0, Nm["F",phIdx-span/2]];
fullInRt[phIdx] ← fullOut[phIdx+span/2] ← NewWires[0, Nm["F",phIdx+span/2]]}
ELSE {
first1: CARDINALIF phIdx=n THEN 1 ELSE 0;
fullInLt[phIdx] ← input[phIdx-first1]  ← NewWires[0, Nm["I",phIdx-first1]];
fullInRt[phIdx] ← input[phIdx+1]   ← NewWires[0, Nm["I",phIdx+1]]};
ENDLOOP;
span ← span/2;
ENDLOOP;
Decode Parity root
fullOut[n + m/2-1] ← dp; -- Decode Parity
SubTrees
subInLt[n+0] ← input[n-1]; subInRt[n+0] ← input[n+0+1]; -- unique bit index = 62
subInLt[n+1] ← input[n-1]; subInRt[n+1] ← input[n+1+1];
subInLt[n+2] ← input[n-1]; subInRt[n+2] ← input[n+2+1];
subInLt[n+3] ← input[n-1]; subInRt[n+3] ← input[n+3+1];
subInLt[n+4] ← input[n-1]; subInRt[n+4] ← input[n+4+1];
subInLt[n+5] ← gnd;   subInRt[n+5] ← input[n+5+1];
out[0] ← fullOut[n/2-1] ← NewWires[0, Nm["O",0]]; -- 64 needs no XORs in subtree row
groupSize ← n/2;
FOR tree: CARDINAL IN [1..logn] DO
out[tree] ← subOut[n-1 - groupSize] ← NewWires[0, Nm["O",tree]];
FOR span: CARDINAL ← n, span/2 WHILE span>groupSize DO
IF span = n -- top, right arg in special location
THEN {
phIdx: CARDINAL ← n-1-groupSize;
IF span > 2*groupSize
THEN{ -- groupSize<32
subInLt[phIdx] ← subOut[phIdx-n/2] ← NewWires[0, Nm["S",phIdx-span/2]];
subInRt[phIdx] ← subOut[n-1 + tree] ← NewWires[0, Nm["S",n-1 + tree]]}
ELSE { -- groupSize=32
subInLt[phIdx] ← fullOut[phIdx - groupSize/2];
subInRt[phIdx] ← subOut[n-1 + tree] ← NewWires[0, Nm["S",n-1 + tree]]} }
ELSE FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO
phIdx: CARDINAL ← span-1 - groupSize + levelIdx*2*span;
IF span > 2*groupSize
THEN {
subInLt[phIdx] ← subOut[phIdx-span/2] ← NewWires[0, Nm["S",phIdx-span/2]];
subInRt[phIdx] ← subOut[phIdx+span/2] ← NewWires[0, Nm["S",phIdx+span/2]]}
ELSE IF groupSize>1
THEN {
subInLt[phIdx] ← fullOut[phIdx     - groupSize/2];
subInRt[phIdx] ← fullOut[phIdx + groupSize + groupSize/2]}
ELSE {
subInLt[phIdx] ← input[phIdx];
subInRt[phIdx] ← input[phIdx+2]};
ENDLOOP;
ENDLOOP;
groupSize ← groupSize/2;
ENDLOOP;
FOR index: CARDINAL IN [0..n+m) DO
IF fullInLt [index]=NIL THEN fullInLt [index] ← gnd;
IF fullInRt [index]=NIL THEN fullInRt [index] ← gnd;
IF fullOut [index]=NIL THEN fullOut [index] ← NewWires[0, Nm["f",index]];
IF subInLt [index]=NIL THEN subInLt [index] ← gnd;
IF subInRt [index]=NIL THEN subInRt [index] ← gnd;
IF subOut [index]=NIL THEN subOut [index] ← NewWires[0, Nm["s",index]];
ENDLOOP};
NewWires: PROC[n: INT ← 0, name: Core.ROPENIL] RETURNS[wire: Core.Wire] =
{RETURN[CoreOps.CreateWires[n, name]]};
END.