Bit matrix transpose with tensor product and perfect shuffling

Efficient implementation of bit-level matrix transpose operations using a new family of perfect shuffle instructions in a word-based micro-processor architecture is investigated. Using a tensor representation of the perfect shuffle index mapping, we show how bit matrix of arbitrary size may be transposed using a minimal sequence of shuffle and pack instructions, and prove the correctness of the code so generated. Specifically, a shuffle decomposition approach, and a block matrix transpose approach are proposed and the performance of these approaches are compared. Implemented with Texas Instruments C64X instruction set, significant performance enhancement is observed.