Bounds, designs and layouts for multi-terminal FPIC architectures
Field-programmable interconnection chips provide the capability of realizing user programmable interconnections for any desired permutation. Such interconnections are very much desired for supporting rapid prototyping of hardware systems and for providing programmable communication networks for parallel and distributed computing. In this paper we address the problem of design of permutation network for routing any m to n,m?n permutation. Specifically, we obtain lower bounds for the number of switches required to realize any one to many permutation of connections. In addition, we also show that m to n permutations whose underlying graph is of degree d has a routing delay of at least . Also, we propose efficient designs for implementing networks for any m to n permutations with asymptotically optimal utilization. Efficient two-layer layouts for such networks are also proposed.
permutation networks routing delay field programmable interconnection chips programmable devices vlsi layout area-performance trade-off