Summing of field elements. Doubling algotithm.

One of frequently used operations appears a procedure of summing of field elements. It's applied for scalar product, fast Fourier transformation, etc.

With STARAN architecture this operation can be realized with "mirror" permutation. In this algorithm we have field INF as input and field OUTF as a result, in which each element is equal to required sum of elements of field INF. At the begining filed INF is copied to filed OUTF, then algorithm runs iteratively. On each iteration field OUTF is divided on groups consisting of MC elements ( MC = 1, 2, 4, .. ) and transfers to MIRF filed applying "mirror" permutation. Than sum of fields OUTF and MIRF is written to field OUTF and process repeats until group size is equal to number of filed elements. This way of summing is known in literature as doubling algorithm.

procedure SUMF1( refer slice outf[ ], inf[ ]; index incap );

index

outcap, mc, i, j; { mc : mirror constant }

slice

mirf[ ];

begin

outcap := incap + lg2 Slicelen;{ Result filed size }

slice mirf[ outcap ];{ Field for mirror permutations }

for i := 0 to incap-1 do{ Copy initial field to outf }

begin

COPY( outf[ i ], inf[ i ] )

end;

mc := 1;{ Constant defining permutation type }

i := 0;

while mc < Slicelen do

begin

for j := 0 to incap-1+i do{ Transfer outf into mirf with mirror permutation }

begin

MIR( mirf[ j ], outf[ j ], mc )

end;

ADDF( outf, outf, mirf, incap+i, incap+i ); { Sum fields mirf and outf }

mc := mc*2;

i := i+1

end

end;{ End of SUMF1 }