Pin-efficient networks for cubic neighborhoods
Charles M. Fiduccia, Kevin J. Rappoport · 2002
Pin-efficient bussed network families are discussed that can-in one clock tick-simultaneously shift all data in a k-dimensional grid to neighboring processors in any one of the 3/sup k/-1 'compass directions' x/spl I.oarr//spl rarr/x/spl I.oarr/+/spl delta//spl I.oarr/, for every nonzero vector /spl delta//spl I.oarr/ /spl isin/ {-1,0,1}/sup k/. The networks have the advantages of being simple to describe (using a single 5-state automaton), extendible (the k-dimensional network is obtained by extending the busses of the (k-1)-dimensional network), and provably optimal for k/spl les/3. The networks use only [3/2(/spl radic/3)/sup k/] pins per processor, which is within 3/2 of the theoretical minimum number of pins required. The best previously known family uses 2/sup k/ pins.>