Fast bit compression and expansion with parallel extract and parallel deposit instructions

Yedidya Hilewitz; Ruby B. Lee

doi:10.1109/ASAP.2006.33

Fast bit compression and expansion with parallel extract and parallel deposit instructions

Yedidya Hilewitz, Ruby B. Lee

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

14 Scopus citations

Abstract

Current microprocessor instruction set architectures are word oriented, with some subword support. Many important applications, however, can realize substantial performance benefits from bit-oriented instructions. We propose the parallel extract (pex) and parallel deposit (pdep) instructions to accelerate compressing and expanding selections of bits. We show that these instructions can be implemented by the fast inverse butterfly and butterfly network circuits. We evaluate latency and area costs of alternative functional units for implementing subsets of advanced bit manipulation instructions. We show applications exhibiting significant speedup, 3.41× on average over a basic RISC architecture, and 2.48× on average over an instruction set architecture (ISA) that supports extract and deposit instructions.

Original language	English (US)
Title of host publication	Proceedings - IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	65-70
Number of pages	6
ISBN (Print)	0769526829, 9780769526829
DOIs	https://doi.org/10.1109/ASAP.2006.33
State	Published - 2006
Event	IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006 - Steamboat Springs, CO, United States Duration: Sep 11 2006 → Sep 13 2006

Publication series

Name	Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors
ISSN (Print)	2160-0511
ISSN (Electronic)	2160-052X

Other

Other	IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006
Country/Territory	United States
City	Steamboat Springs, CO
Period	9/11/06 → 9/13/06

All Science Journal Classification (ASJC) codes

Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1109/ASAP.2006.33

Cite this

Hilewitz, Y., & Lee, R. B. (2006). Fast bit compression and expansion with parallel extract and parallel deposit instructions. In Proceedings - IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006 (pp. 65-70). Article 4019493 (Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASAP.2006.33

Hilewitz, Yedidya ; Lee, Ruby B. / Fast bit compression and expansion with parallel extract and parallel deposit instructions. Proceedings - IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006. Institute of Electrical and Electronics Engineers Inc., 2006. pp. 65-70 (Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors).

@inproceedings{3c4bdebe21b944e5b6589c53c1ce8ed5,

title = "Fast bit compression and expansion with parallel extract and parallel deposit instructions",

abstract = "Current microprocessor instruction set architectures are word oriented, with some subword support. Many important applications, however, can realize substantial performance benefits from bit-oriented instructions. We propose the parallel extract (pex) and parallel deposit (pdep) instructions to accelerate compressing and expanding selections of bits. We show that these instructions can be implemented by the fast inverse butterfly and butterfly network circuits. We evaluate latency and area costs of alternative functional units for implementing subsets of advanced bit manipulation instructions. We show applications exhibiting significant speedup, 3.41× on average over a basic RISC architecture, and 2.48× on average over an instruction set architecture (ISA) that supports extract and deposit instructions.",

author = "Yedidya Hilewitz and Lee, \{Ruby B.\}",

year = "2006",

doi = "10.1109/ASAP.2006.33",

language = "English (US)",

isbn = "0769526829",

series = "Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "65--70",

booktitle = "Proceedings - IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006",

address = "United States",

note = "IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006 ; Conference date: 11-09-2006 Through 13-09-2006",

}

Hilewitz, Y & Lee, RB 2006, Fast bit compression and expansion with parallel extract and parallel deposit instructions. in Proceedings - IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006., 4019493, Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors, Institute of Electrical and Electronics Engineers Inc., pp. 65-70, IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006, Steamboat Springs, CO, United States, 9/11/06. https://doi.org/10.1109/ASAP.2006.33

Fast bit compression and expansion with parallel extract and parallel deposit instructions. / Hilewitz, Yedidya; Lee, Ruby B.
Proceedings - IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006. Institute of Electrical and Electronics Engineers Inc., 2006. p. 65-70 4019493 (Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Fast bit compression and expansion with parallel extract and parallel deposit instructions

AU - Hilewitz, Yedidya

AU - Lee, Ruby B.

PY - 2006

Y1 - 2006

N2 - Current microprocessor instruction set architectures are word oriented, with some subword support. Many important applications, however, can realize substantial performance benefits from bit-oriented instructions. We propose the parallel extract (pex) and parallel deposit (pdep) instructions to accelerate compressing and expanding selections of bits. We show that these instructions can be implemented by the fast inverse butterfly and butterfly network circuits. We evaluate latency and area costs of alternative functional units for implementing subsets of advanced bit manipulation instructions. We show applications exhibiting significant speedup, 3.41× on average over a basic RISC architecture, and 2.48× on average over an instruction set architecture (ISA) that supports extract and deposit instructions.

AB - Current microprocessor instruction set architectures are word oriented, with some subword support. Many important applications, however, can realize substantial performance benefits from bit-oriented instructions. We propose the parallel extract (pex) and parallel deposit (pdep) instructions to accelerate compressing and expanding selections of bits. We show that these instructions can be implemented by the fast inverse butterfly and butterfly network circuits. We evaluate latency and area costs of alternative functional units for implementing subsets of advanced bit manipulation instructions. We show applications exhibiting significant speedup, 3.41× on average over a basic RISC architecture, and 2.48× on average over an instruction set architecture (ISA) that supports extract and deposit instructions.

UR - https://www.scopus.com/pages/publications/34547443955

UR - https://www.scopus.com/inward/citedby.url?scp=34547443955&partnerID=8YFLogxK

U2 - 10.1109/ASAP.2006.33

DO - 10.1109/ASAP.2006.33

M3 - Conference contribution

AN - SCOPUS:34547443955

SN - 0769526829

SN - 9780769526829

T3 - Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors

SP - 65

EP - 70

BT - Proceedings - IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006

Y2 - 11 September 2006 through 13 September 2006

ER -

Hilewitz Y, Lee RB. Fast bit compression and expansion with parallel extract and parallel deposit instructions. In Proceedings - IEEE 17th International Conference on Application-specific Systems, Architectures and Processors, ASAP 2006. Institute of Electrical and Electronics Engineers Inc. 2006. p. 65-70. 4019493. (Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors). doi: 10.1109/ASAP.2006.33

Fast bit compression and expansion with parallel extract and parallel deposit instructions

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this