Perfect shifters [multiprocessor interconnection networks]
Charles M. Fiduccia, Kevin J. Rappoport · IEEE Transactions on Computers · 1994
Pin-efficient single-instruction multiple-data networks, with p/spl ap//spl radic/(2m) pins per cell that can/spl minus/in one clock tick/spl minus/shift data by any amount k in an interval /spl lsqb//spl minus/m,m/spl rsqb/ are considered. Perfect barrel shifters, which perform the group of permutations c/spl rarr/c+k(mod n), 0/spl les/k/spl les/n/spl minus/1, using p=q+1 pins per cell, are known to exist for all n=q/sup 2/+q+1, where q is any prime power. In sharp contrast, it is shown that for any permutation /spl pi/ of order greater than 3m, one-tick perfect shifters for the set of permutations /spl pi//sup /spl lsqb//spl minus/m,m/spl rsqb//=/spl lcub//spl pi//sup k//spl verbar//spl minus/m/spl les/k/spl les/m/spl rcub/ exist only for the three cases (m=1, p=2), (m=3, p=3), and (m=6, p=4). In particular, only three perfect linear arrays, c/spl rarr/c+k, exist. The proof is based on a relationship between the difference covers and zero-one solutions to certain quadratic equations.>