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.


翻译:在统计、机器学习和生物信息学等多个领域,绝对变量通常以单热编码矢量表示。例如,根据8个不同的值,我们将每个值都映射到仅设定了一位数的字节。我们有动力快速计算这些编码的统计。在 k-bit 单词的流中,我们试图计算与指数0、1、2、...、 k-1 的比特值相对应的 k 单数。如果 k-bit 单词是一热编码,然后数数对应频率直方图。这个多和问题是一个人口计数问题的一般化问题,我们在这里寻找所有位数的总和。因此,我们把多和问题称为位置人口计。使用最近Intel 处理器的 SIMD (单调、多数据) 指令,我们描述计算16位人口数的算法,使用每16位单词的CPU周期不到一半。我们的最佳方法使用400倍的指令,并且比基线码快50倍,仅使用正常输入(非SIMD) 。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
123+阅读 · 2020年11月20日
最新《序列预测问题导论》教程,212页ppt
专知会员服务
84+阅读 · 2020年8月22日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
57+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
171+阅读 · 2019年10月11日
机器学习相关资源(框架、库、软件)大列表
专知会员服务
38+阅读 · 2019年10月9日
计算机类 | PLDI 2020等国际会议信息6条
Call4Papers
3+阅读 · 2019年7月8日
ICLR2019最佳论文出炉
专知
11+阅读 · 2019年5月6日
神器Cobalt Strike3.13破解版
黑白之道
12+阅读 · 2019年3月1日
时序数据异常检测工具/数据集大列表
极市平台
65+阅读 · 2019年2月23日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
误差反向传播——RNN
统计学习与视觉计算组
18+阅读 · 2018年9月6日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【论文】图上的表示学习综述
机器学习研究会
12+阅读 · 2017年9月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Arxiv
0+阅读 · 2021年5月6日
Arxiv
0+阅读 · 2021年5月6日
Arxiv
0+阅读 · 2021年5月5日
Arxiv
0+阅读 · 2021年5月4日
VIP会员
相关VIP内容
【干货书】机器学习速查手册,135页pdf
专知会员服务
123+阅读 · 2020年11月20日
最新《序列预测问题导论》教程,212页ppt
专知会员服务
84+阅读 · 2020年8月22日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
57+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
171+阅读 · 2019年10月11日
机器学习相关资源(框架、库、软件)大列表
专知会员服务
38+阅读 · 2019年10月9日
相关资讯
计算机类 | PLDI 2020等国际会议信息6条
Call4Papers
3+阅读 · 2019年7月8日
ICLR2019最佳论文出炉
专知
11+阅读 · 2019年5月6日
神器Cobalt Strike3.13破解版
黑白之道
12+阅读 · 2019年3月1日
时序数据异常检测工具/数据集大列表
极市平台
65+阅读 · 2019年2月23日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
误差反向传播——RNN
统计学习与视觉计算组
18+阅读 · 2018年9月6日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【论文】图上的表示学习综述
机器学习研究会
12+阅读 · 2017年9月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员