Fast subword permutation instructions based on butterfly networks

Xiao Yang, Manish Vachharajani, Ruby B. Lee

Research output: Contribution to journalConference articlepeer-review

29 Scopus citations


Many contemporary microprocessor architectures incorporate multimedia extensions to accelerate media-rich applications using subword arithmetic. While these extensions significantly improve the performance of most multimedia applications, the lack of subword rearrangement support potentially limits performance gain. Several means of adding architectural support for subword rearrangement were proposed and implemented but none of them provide a fully general solution. In this paper, a new class of permutation instructions based on the butterfly interconnection network is proposed to address the general subword rearrangement problem. It can be used to perform arbitrary permutation (without repetition) of n subwords within log n cycles regardless of the subword size. The instruction coding and the low-level implementation for the instructions are quite simple. An algorithm is also given to derive an instruction sequence for any arbitrary permutation.

Original languageEnglish (US)
Pages (from-to)80-86
Number of pages7
JournalProceedings of SPIE - The International Society for Optical Engineering
StatePublished - 2000
EventProceedings of the Media Processors 2000 - San Jose, CA, USA
Duration: Jan 27 2000Jan 28 2000

All Science Journal Classification (ASJC) codes

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering


Dive into the research topics of 'Fast subword permutation instructions based on butterfly networks'. Together they form a unique fingerprint.

Cite this