Klarqvist, Marcus D. R., Muła, Wojciech et Lemire, Daniel (2021). Efficient Computation of Positional Population Counts Using SIMD Instructions. Concurrency and Computation: Practice and Experience, 33 (17). 10.1002/cpe.6304
Fichier(s) associé(s) à ce document :![[thumbnail of shortpospopcnt-4.pdf]](https://r-libre.teluq.ca/style/images/fileicons/pdf.png "shortpospopcnt-4.pdf")
|
PDF
- shortpospopcnt-4.pdf
Contenu du fichier : Manuscrit soumis (avant évaluation) Licence : Creative Commons CC BY. |
|
| Catégorie de document : | Articles de revues |
|---|---|
| Évaluation par un comité de lecture : | Oui |
| Étape de publication : | Publié |
| Résumé : | 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. |
| Déposant: | Lemire, Daniel |
| Responsable : | Daniel Lemire |
| Dépôt : | 19 mars 2021 12:54 |
| Dernière modification : | 18 aout 2021 13:48 |
|
RÉVISER |
