POPCNT如何在硬件中实现? [英] How is POPCNT implemented in hardware?
问题描述
根据 http://www.agner.org/optimize/instruction_tables.pdf，POPCNT指令(返回32位或64位寄存器中设置的位数)在现代Intel和AMD处理器上每个时钟周期的吞吐量为1条指令.这比需要多个指令的任何软件实现都要快得多(
According to http://www.agner.org/optimize/instruction_tables.pdf, the POPCNT instruction (which returns the number of set bits in a 32-bit or 64-bit register) has a throughput of 1 instruction per clock cycle on modern Intel and AMD processors. This is much faster than any software implementation which needs multiple instructions (How to count the number of set bits in a 32-bit integer?).
如何在硬件中如此高效地实现POPCNT?
How is POPCNT implemented so efficiently in hardware?
推荐答案
组合popcnt有一项专利，正向/反向位扫描:
There's a patent for combined popcnt, bit scan forward / reverse:
摘要
描述了PopCount和BitScan的合并数据路径.硬件电路包括用于PopCount功能的压缩树，该压缩树被BitScan功能(例如，正向扫描(BSF)或反向扫描(BSR))重用.选择器逻辑使压缩树能够根据微处理器指令对PopCount或BitScan操作的输入字进行操作.如果选择了BitScan操作，则对输入字进行编码.压缩器树接收输入字，对所有位进行操作，就好像所有位都具有相同的有效级别(例如，对于N位输入字而言，该输入字被视为N个一位输入).压缩器树电路的结果是一个二进制值，表示与执行的操作有关的数字(PopCount的设置位数，或通过扫描输入字遇到的第一个设置位的位位置).
A merged datapath for PopCount and BitScan is described. A hardware circuit includes a compressor tree utilized for a PopCount function, which is reused by a BitScan function (e.g., bit scan forward (BSF) or bit scan reverse (BSR)). Selector logic enables the compressor tree to operate on an input word for the PopCount or BitScan operation, based on a microprocessor instruction. The input word is encoded if a BitScan operation is selected. The compressor tree receives the input word, operates on the bits as though all bits have same level of significance (e.g., for an N-bit input word, the input word is treated as N one-bit inputs). The result of the compressor tree circuit is a binary value representing a number related to the operation performed (the number of set bits for PopCount, or the bit position of the first set bit encountered by scanning the input word).
这篇关于POPCNT如何在硬件中实现?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
