Permutations on Superposed Parallel Buses

Abstract:

This paper presents two systolic algorithms, a self-pipelined and a multi-pipelined algorithm, for both static and dynamic permutations. These algorithms are derived from the simulation of an omega-network on interconnection schemes based on superposed parallel buses. These algorithms are area-efficient and
almost optimal for permutations using the AT2 measure. They are faster than previously reported interconnection schemes using almost linear area. They are especially suitable for highspeed but area-limited technologies, due to simple control algorithms and regular, area-efficient interconnections. Descriptions of these two algorithms and a summary of their VLSI complexities for both static and dynamic cases are included.