Back to Search
Start Over
Efficient Computation of Positional Population Counts Using SIMD Instructions
- Publication Year :
- 2019
- Publisher :
- arXiv, 2019.
-
Abstract
- In several fields such as statistics, machine learning, and bioinformatics, categorical variables are frequently represented as one-hot encoded vectors. For example, given 8 distinct values, we map each value to a byte where only a single bit has been set. We are motivated to quickly compute statistics over such encodings. Given a stream of k-bit words, we seek to compute k distinct sums corresponding to bit values at indexes 0, 1, 2, ..., k-1. If the k-bit words are one-hot encoded then the sums correspond to a frequency histogram. This multiple-sum problem is a generalization of the population-count problem where we seek the sum of all bit values. Accordingly, we refer to the multiple-sum problem as a positional population-count. Using SIMD (Single Instruction, Multiple Data) instructions from recent Intel processors, we describe algorithms for computing the 16-bit position population count using less than half of a CPU cycle per 16-bit word. Our best approach uses up to 400 times fewer instructions and is up to 50 times faster than baseline code using only regular (non-SIMD) instructions, for sufficiently large inputs.
- Subjects :
- FOS: Computer and information sciences
education.field_of_study
Computer Networks and Communications
Computer science
Population
Byte
020206 networking & telecommunications
02 engineering and technology
Computer Science Applications
Theoretical Computer Science
Set (abstract data type)
Computational Theory and Mathematics
Computer Science - Data Structures and Algorithms
0202 electrical engineering, electronic engineering, information engineering
Code (cryptography)
020201 artificial intelligence & image processing
Data Structures and Algorithms (cs.DS)
SIMD
Arithmetic
Instruction cycle
education
Categorical variable
Software
Word (computer architecture)
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....951ec4b73c84c4ab6a8b90b16a45a5fc
- Full Text :
- https://doi.org/10.48550/arxiv.1911.02696