EFFICIENT NETWORK FOLDING TECHNIQUES FOR ROUTING PERMUTATIONS IN VLSI

Network folding is a technique for realizing permutations on N element s using interconnection networks with M input (and output) terminals, where M < N. A major motivation for network folding is the severely li mited number of I/O pins in microelectronic packages, such as VLSI chi ps or multichip module (MCM) packages. Cost overhead and performance d egradation due to off-chip communication as well as long on-chip wires may render implementing otherwise good designs infeasible or ineffici ent. In this paper, an efficient and systematic methodology is propose d for designing folded permutation networks that can route the class o f bit-permute-complement (BPC) permutations. In particular, it is show n that any folded BPC permutation network can be constructed using onl y two stages of uniform-size transpose networks. This results in highl y modular structures for BPC networks. The methodology trades off spee d (time), with I/O and chip-area.