Advanced Bit Manipulation

Summary of Work

This project investigates the design and implementation of new instructions that accelerate bit manipulation operations. These operations include:

  • Bit permutation
  • Bit gather and bit scatter
  • Bit matrix multiply

More Coming Soon

Publications

Public Technical Report describing the full set of operations:

  • Yedidya Hilewitz and Ruby B. Lee, Advanced Bit Manipulation Instruction Set Architecture, Princeton University Department of Electrical Engineering Technical Report CE-L2006-004, November 2006. [PDF]

Published papers:

  • Yedidya Hilewitz, Ruby B. Lee, A New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations, IEEE Transactions on Computing, Vol. 58 No. 8, August 2009. Published on-line since Dec 2008".
  • Hilewitz, Y., Lauradoux, C., Lee, R.B., "Bit Matrix Multiplication in Commodity Processors", Proceedings of 19th IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP ‘08), July 2008.
  • Hilewitz, Y., Yin, Y.L., Lee, R.B., "Accelerating the Whirlpool Hash Function Using Parallel Table Lookup and Fast Cyclical Permutation", Proceedings of the 15th Fast Software Encryption Workshop (FSE), Lausanne, Switzerland, February 2008.
  • Hilewitz, Y., Lee, R.B., "Fast Bit Gather, Bit Scatter and Bit Permutation Instructions for Commodity Microprocessors", Journal of Signal Processing Systems, vol. 53, issue 1-2: Springer New York, pp. 145-169, 11/2008.
  • Hilewitz, Y., Lauradoux, C., Lee, R.B., Fast Bit Matrix Multiplication in Commodity Microprocessors, , Princeton University Department of Electrical Engineering Technical Report CE-L2007-011, November 2007.
  • Yedidya Hilewitz, Ruby B. Lee, Performing Advanced Bit Manipulations Efficiently in General-Purpose Processors, Proceedings of the 18th IEEE Symposium on Computer Arithmetic (ARITH-18), Montpellier, France, pp. 251-260, June 2007.
  • Yedidya Hilewitz and Ruby B. Lee, Fast Bit Compression and Expansion with Parallel Extract and Parallel Deposit Instructions, Proceedings of the IEEE 17th International Conference on Application-Specific Systems, Architectures and Processors (ASAP), pp. 65-72, September 11-13, 2006 (Best Paper Award). [PDF]
  • Ruby B. Lee, Xiao Yang and Zhijie Jerry Shi, Single-Cycle Bit Permutations with MOMR Execution, Journal of Computer Science and Technology, vol. 20, no. 5, pp. 577-585, September 2005. [PDF]
  • Yedidya Hilewitz, Zhijie Jerry Shi, and Ruby B. Lee, Comparing Fast Implementations of Bit Permutation Instructions, Proceedings of the 38th Annual Asilomar Conference on Signals, Systems, and Computers, pp. 1856-1863, November 2004. [PDF]
  • R. B. Lee, R. L. Rivest, M.J.B. Robshaw, Z.J. Shi, and Y.L. Yin, Permutation Operations in Block Ciphers, accepted for publication in Embedded Cryptographic Hardware: Design and Security, Nadia Nedjah and Luiza de Macedo Mourelle, eds., Nova Science, NY, ISBN 1-59454-145-0, September 2004. [PDF (formatted for A4 paper)]
  • R. B. Lee, R. L. Rivest, M.J.B. Robshaw, Z.J. Shi, and Y.L. Yin, On Permutation Operations in Cipher Design, Proceedings of the
    International Conference on Information Technology (ITCC), vol. 2, pp. 569 - 577, April 2004. [PDF]
  • Zhijie Jerry Shi and Ruby B. Lee, Implementation Complexity of Bit Permutation Instructions, Proceedings of the Asilomar Conference on Signals, Systems, and Computers, pp. 879-886, November 2003 (Nominated for Best Student Paper Award). [PDF]
  • John Patrick McGregor and Ruby B. Lee, Architectural Techniques for Accelerating Subword Permutations with Repetitions, IEEE Transactions on Very Large Scale Integration Systems, vol. 11, no. 3, pp. 325-335, June 2003. [PDF]
  • Zhijie Shi, Xiao Yang and Ruby B. Lee, Arbitrary Bit Permutations in One or Two Cycles, Proceedings of the IEEE International
    Conference on Application-Specific Systems, Architectures and Processors (ASAP 2003), pp. 237-247, June 2003. [PDF]
  • Zhijie Shi and Ruby B. Lee, Subword Sorting with Versatile Permutation Instructions, Proceedings of the International Conference on Computer Design (ICCD 2002), pp. 234-241, September 2002. [PDF]
  • Ruby B. Lee, Zhijie Shi, and Xiao Yang, How a Processor can Permute n bits in O(1) cycles, Proceedings of Hot Chips 14 - A Symposium on High Performance Chips, August 2002. [Presentation PDF]
  • Ruby B. Lee, Zhijie Shi, and Xiao Yang, Efficient Permutation Instructions for Fast Software Cryptography, IEEE Micro, vol. 21, no. 6, pp. 56-69, December 2001. [PDF]
  • John Patrick McGregor and Ruby B. Lee, Architectural Enhancements for Fast Subword Permutations with Repetitions in Cryptographic Applications, Proceedings of the International Conference on Computer Design (ICCD 2001), pp. 453-461, September 2001. [PDF]
  • Xiao Yang and Ruby B. Lee, Fast Subword Permutation Instructions Using Omega and Flip Network Stages, Proceedings of the International Conference on Computer Design (ICCD 2000), pp. 15-22,September 2000. [PDF]
  • Ruby B. Lee, Subword Permutation Instructions for Two-Dimensional Multimedia Processing in MicroSIMD Architectures, Proceedings
    of the IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP 2000), pp. 3-14, July 2000. [PDF]
  • Zhijie Shi and Ruby B. Lee, Bit Permutation Instructions for Accelerating Software Cryptography, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP 2000), pp. 138-148, July 2000. [PDF]
  • Xiao Yang, Manish Vachharajani, and Ruby B. Lee, Fast Subword Permutation Instructions Based on Butterfly Networks, Proceedings of Media Processors IS&T/SPIE Symposium on Electric Imaging: Science and Technology, pp. 80-86, January 2000. [PDF]

Technical Reports:

  • Yedidya Hilewitz, Cedric Lauradoux, Ruby Lee, Fast Bit Matrix Multiplication in Commodity Microprocessors, Princeton University Department of Electrical Engineering Technical Report CE-L2007-011, November 2007.
  • Yedidya Hilewitz, Ruby B. Lee, Achieving Very Fast Bit Matrix Multiplication in Commodity Microprocessors, Princeton University Department of Electrical Engineering Technical Report CE-L2007-006, August 2007.
  • Yedidya Hilewitz, Ruby B. Lee, A New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations, Princeton University Department of Electrical Engineering Technical Report CE-L2007-004, July 2007.
  • Yedidya Hilewitz, Ruby B. Lee, Accelerating the Whirlpool Hash Function using On-Chip Lookup Tables, Princeton University Department of Electrical Engineering Technical Report CE-L2007-001, February 2007.
  • Yedidya Hilewitz and Ruby B. Lee, Advanced Bit Manipulation Instructions: BFLY, IBFLY, PEX and PDEP, Princeton University Department of Electrical Engineering Technical Report CE-L2006-010, December 2006.
  • Yedidya Hilewitz and Ruby B. Lee, Performing Advanced Bit Manipulations Efficiently by Replacing the Shifter in General-Purpose Processors, Princeton University Department of Electrical Engineering Technical Report CE-L2006-005, October 2006.
  • Ruby B. Lee and Yedidya Hilewitz, Fast Pattern Matching with Parallel Extract Instructions, Princeton University Department of Electrical Engineering Technical Report CE-L2005-002, February 2005.
  • Zhijie J. Shi, Bit Permutation Instructions: Architecture, Implementation, and Cryptographic Properties, Ph.D. Thesis, Princeton University Department of Electrical Engineering, June 2004.
  • Xiao Yang and Ruby B. Lee, Implementation Complexity for Achieving Bit Permutations in One or Two Cycles in Superscalar Processors, Princeton University Department of Electrical Engineering Technical Report CE-L2003-002, May 2003.
  • Ruby B. Lee, Ronald L. Rivest, Zhijie J. Shi, and Yiqun L. Yin, Cryptographic Properties of Permutation Operations and Applications in Cipher Design, Princeton University Department of Electrical Engineering Technical Report CE-L2003-001, May 2003.
  • Ruby B. Lee, Xiao Yang, and Zhijie Shi, Validating Word-Oriented Processors for Bit-level Permutations and Multi-word Operations in Pervasive Secure Computing Paradigms, Princeton University Department of Electrical Engineering Technical Report CE-L2002-004, November 2002.
  • Ruby B. Lee, Zhijie Shi and Yiqun Lisa Yin, Cryptographic Properties and Implementation Complexity of Different Permutation Operations, Princeton University Department of Electrical Engineering Technical Report CE-L2002-002, May 2002.
  • Ruby B. Lee, Zhijie Shi, and Xiao Yang, Efficient Permutation Instructions for Secure Multimedia Information Processing, Princeton University Department of Electrical Engineering Technical Report CE-L2000-001, April 2000.
  • Zhijie Shi and Ruby B. Lee, Permutation Instructions for Symmetric-Key Cryptography, Princeton University Department of Electrical Engineering Technical Report CE-L99-004, September 1999.
  • Ruby B. Lee, Fundamental Subword Permutation Primitives for Two-Dimensional Media Processing with MicroSIMD Architectures, Princeton University Department of Electrical Engineering Technical Report CE-L98-001, October 1998.