NDLI: Fast Bit Gather, Bit Scatter and Bit Permutation Instructions for Commodity Microprocessors

Content Provider	Springer Nature Link
Author	Hilewitz, Yedidya Lee, Ruby B.
Copyright Year	2008
Abstract	Advanced bit manipulation operations are not efficiently supported by commodity word-oriented microprocessors. Programming tricks are typically devised to shorten the long sequence of instructions needed to emulate these complicated bit operations. As these bit manipulation operations are relevant to applications that are becoming increasingly important, we propose direct support for them in microprocessors. In particular, we propose fast bit gather (or parallel extract), bit scatter (or parallel deposit) and bit permutation instructions (including group, butterfly and inverse butterfly). We show that all these instructions can be implemented efficiently using both the fast butterfly and inverse butterfly network datapaths. Specifically, we show that parallel deposit can be mapped onto a butterfly circuit and parallel extract can be mapped onto an inverse butterfly circuit. We define static, dynamic and loop invariant versions of the instructions, with static versions utilizing a much simpler functional unit. We show how a hardware decoder can be implemented for the dynamic and loop-invariant versions to generate, dynamically, the control signals for the butterfly and inverse butterfly datapaths. The simplest functional unit we propose is smaller and faster than an ALU. We also show that these instructions yield significant speedups over a basic RISC architecture for a variety of different application kernels taken from applications domains including bioinformatics, steganography, coding, compression and random number generation.
Starting Page	145
Ending Page	169
Page Count	25
File Format	PDF
ISSN	19398018
Journal	Journal of Signal Processing Systems
Volume Number	53
Issue Number	1-2
e-ISSN	19398115
Language	English
Publisher	Springer US
Publisher Date	2008-06-04
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Bit manipulations Permutations Bit scatter Bit gather Parallel extract Parallel deposit Pack Unpack Microprocessors Instruction set architecture ISA Algorithm acceleration Bioinformatics Pattern matching Compression Steganography Cryptology Computer Imaging, Vision, Pattern Recognition and Graphics Pattern Recognition Image Processing and Computer Vision Electronic and Computer Engineering Circuits and Systems Signal, Image and Speech Processing
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Signal Processing Control and Systems Engineering Information Systems Modeling and Simulation Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations

A Fast Recursive Algorithm and Architecture for Pruned Bit-reversal Interleavers

Bit-by-Bit Pipelined and Hybrid-Grained 2D Architecture for Motion Estimation of H.264/AVC

A Novel VLSI Architecture of SPIHT Using Breadth First Search for Real-Time Applications

IMAPCAR: A 100 GOPS In-Vehicle Vision Processor Based on 128 Ring Connected Four-Way VLIW Processing Elements

CBS: Contourlet-Based Steganalysis Method

Hierarchical steganography using novel optimum quantization technique

New Distortion Metric for Efficient JPEG Steganography Using Linear Prediction

A Simple Compressive Sensing Algorithm for Parallel Many-Core Architectures

Fast Bit Gather, Bit Scatter and Bit Permutation Instructions for Commodity Microprocessors

Similar Documents

A New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations

A Fast Recursive Algorithm and Architecture for Pruned Bit-reversal Interleavers

Bit-by-Bit Pipelined and Hybrid-Grained 2D Architecture for Motion Estimation of H.264/AVC

A Novel VLSI Architecture of SPIHT Using Breadth First Search for Real-Time Applications

IMAPCAR: A 100 GOPS In-Vehicle Vision Processor Based on 128 Ring Connected Four-Way VLIW Processing Elements

CBS: Contourlet-Based Steganalysis Method

Hierarchical steganography using novel optimum quantization technique

New Distortion Metric for Efficient JPEG Steganography Using Linear Prediction

A Simple Compressive Sensing Algorithm for Parallel Many-Core Architectures

Fast Bit Gather, Bit Scatter and Bit Permutation Instructions for Commodity Microprocessors