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:
BOOL ←
TRUE] =
{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: CARDINAL ← IF 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: CARDINAL ← IF 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: CARDINAL ← IF 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: CARDINAL ← IF 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.
ROPE ←
NIL]
RETURNS[wire: Core.Wire] =
{RETURN[CoreOps.CreateWires[n, name]]};
END.