Bit matrix multiplication in commodity processors

Yedidya Hilewitz, Cédric Lauradoux, Ruby B. Lee

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Registers in processors generally contain words or, with the addition of multimedia extensions, short vectors of subwords of bytes or 16-bit elements. In this paper, we view the contents of registers as vectors or matrices of individual bits. However, the facility to operate efficiently on the bit-level is generally lacking. A commodity processor usually only has logical and shift instructions and occasionally population count instructions. Perhaps the most powerful primitive bit-level operation is the bit matrix multiply (BMM) instruction, currently found only in supercomputers like Cray. This instruction multiplies two n x n bit matrices. In this paper, we show the power of BMM. We propose and analyze new processor instructions that implement simpler BMM primitive operations more suitable for a commodity processor. We show the impact of BMM on the performance of critical application kernels and discuss its hardware cost.

Original languageEnglish (US)
Title of host publicationASAP08, Conference Proceedings - IEEE 19th International Conference on Application-Specific Systems, Architectures and Processors
Pages7-12
Number of pages6
DOIs
StatePublished - Sep 18 2008
EventASAP08 - IEEE 19th International Conference on Application-Specific Systems, Architectures and Processors - Leuven, Belgium
Duration: Jul 2 2008Jul 4 2008

Publication series

NameProceedings of the International Conference on Application-Specific Systems, Architectures and Processors
ISSN (Print)1063-6862

Other

OtherASAP08 - IEEE 19th International Conference on Application-Specific Systems, Architectures and Processors
CountryBelgium
CityLeuven
Period7/2/087/4/08

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Bit matrix multiplication in commodity processors'. Together they form a unique fingerprint.

  • Cite this

    Hilewitz, Y., Lauradoux, C., & Lee, R. B. (2008). Bit matrix multiplication in commodity processors. In ASAP08, Conference Proceedings - IEEE 19th International Conference on Application-Specific Systems, Architectures and Processors (pp. 7-12). [4580146] (Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors). https://doi.org/10.1109/ASAP.2008.4580146