An FPGA implementation of bene" permutation networks
Anatole D. Ruslanov, Jeremy Russell Johnson · 2004
This work discusses an FPGA implementation study of the Bene Permutation Network (BPN). The BPN, originally developed for connecting devices in telephone switching, is a circuit of size O(n log n) and O(log n) depth, built from 2 x 2 switches, which is capable of performing an arbitrary permutation. The BPN provides an asymptotic improvement in area over the straightforward network built with multiplexers, and the work presented here shows that an FPGA implementation uses less area for networks as small as size 4. The implementation presented in this paper uses a special-purpose tool to synthesize and place and route the circuit. The place and route tool can be used to systematically explore alternative place and route strategies and was used to obtain significantly better area utilization and timing performance compared to general-purpose tools. In addition, several general improvements and extensions were discovered that further improve performance and reduce area.