如果源数据流的数量是3、5、7或9，则可以利用经证明的最优或接近最优的通过3的多数基元的 n 的多数计算，也就是三元中值算子Kmxyz。Knuth，TAOCP Vol.4a，指出 any 单调布尔函数可以完全用三元中值算子和常数0和1来表示。 最近的文献（见下面代码中的注解）展示了如何以一种已被证明的最佳方式从3个多数中构造7个多数，后者需要7个示例。以这种方式构造9个多数的最佳方法仍然是一个开放的研究问题，但最近发现了一种相当有效的构造方法，使用13个3个多数的示例。下面的ISO-C99代码用于探索这种方法。 使用最新的x86-64工具链和-march=skylake-avx512进行编译，可以获得相当高的数据吞吐量（数十GB/秒），但还没有达到系统内存吞吐量，这将是最终目标。其原因是编译器还不能可靠地将3的多数原语Map到AVX 512可用的vpternlogq指令，其中3个操作中的大多数可以用一条这样的指令来表示。人们必须通过使用intrinsic或使用内联汇编来解决这个问题。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define NBR_STREAMS (9) // 3, 5, 7, or 9
#define NBR_BLOCKS (10000000)
#define BENCH_ITERS (3)
#if defined(_WIN32)
#if !defined(WIN32_LEAN_AND_MEAN)
#define WIN32_LEAN_AND_MEAN
#endif
#include <windows.h>
double second (void)
{
LARGE_INTEGER t;
static double oofreq;
static int checkedForHighResTimer;
static BOOL hasHighResTimer;
if (!checkedForHighResTimer) {
hasHighResTimer = QueryPerformanceFrequency (&t);
oofreq = 1.0 / (double)t.QuadPart;
checkedForHighResTimer = 1;
}
if (hasHighResTimer) {
QueryPerformanceCounter (&t);
return (double)t.QuadPart * oofreq;
} else {
return (double)GetTickCount() * 1.0e-3;
}
}
#elif defined(__linux__) || defined(__APPLE__)
#include <stddef.h>
#include <sys/time.h>
double second (void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return (double)tv.tv_sec + (double)tv.tv_usec * 1.0e-6;
}
#else
#error unsupported platform
#endif
uint64_t maj3 (uint64_t a, uint64_t b, uint64_t c)
{
return (((b & c) | a) & (b | c));
}
uint64_t maj5 (uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e)
{
/* Knuth, TAOCP Vol. 4a, p. 64 */
return maj3 (a, maj3 (c, d, e), maj3 (b, c, maj3 (b, d, e)));
}
uint64_t maj7 (uint64_t a, uint64_t b, uint64_t c, uint64_t d,
uint64_t e, uint64_t f, uint64_t g)
{
/*
Eleonora Testa, et al., "Mapping Monotone Boolean Functions into Majority."
IEEE Transactions on Computers, Vol. 68, No. 5, May 2019, pp. 791-797.
*/
uint64_t s = maj3 (a, c, d);
uint64_t t = maj3 (e, f, g);
return maj3 (b, maj3 (e, s, maj3 (f, g, s)), maj3 (d, t, maj3 (a, c, t)));
}
uint64_t maj9 (uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e,
uint64_t f, uint64_t g, uint64_t h, uint64_t i)
{
/*
Thomas Häner, Damian S. Steiger, Helmut G. Katzgraber, "Parallel Tempering
for Logic Synthesis." arXiv.2311.12394, Nov. 21, 2023
*/
uint64_t r = maj3 (g, d, c);
uint64_t s = maj3 (g, e, b);
uint64_t t = maj3 (i, f, a);
uint64_t u = maj3 (r, s, h);
uint64_t v = maj3 (d, h, t);
uint64_t w = maj3 (c, d, h);
uint64_t x = maj3 (i, a, u);
uint64_t y = maj3 (c, v, t);
uint64_t z = maj3 (y, e, g);
return maj3 (maj3 (x, u, f), maj3 (z, b, y), maj3 (s, w, t));
}
/*
https://groups.google.com/forum/#!original/comp.lang.c/qFv18ql_WlU/IK8KGZZFJx4J
From: geo <[email protected]>
Newsgroups: sci.math,comp.lang.c,comp.lang.fortran
Subject: 64-bit KISS RNGs
Date: Sat, 28 Feb 2009 04:30:48 -0800 (PST)
This 64-bit KISS RNG has three components, each nearly
good enough to serve alone. The components are:
Multiply-With-Carry (MWC), period (2^121+2^63-1)
Xorshift (XSH), period 2^64-1
Congruential (CNG), period 2^64
*/
static uint64_t kiss64_x = 1234567890987654321ULL;
static uint64_t kiss64_c = 123456123456123456ULL;
static uint64_t kiss64_y = 362436362436362436ULL;
static uint64_t kiss64_z = 1066149217761810ULL;
static uint64_t kiss64_t;
#define MWC64 (kiss64_t = (kiss64_x << 58) + kiss64_c, \
kiss64_c = (kiss64_x >> 6), kiss64_x += kiss64_t, \
kiss64_c += (kiss64_x < kiss64_t), kiss64_x)
#define XSH64 (kiss64_y ^= (kiss64_y << 13), kiss64_y ^= (kiss64_y >> 17), \
kiss64_y ^= (kiss64_y << 43))
#define CNG64 (kiss64_z = 6906969069ULL * kiss64_z + 1234567ULL)
#define KISS64 (MWC64 + XSH64 + CNG64)
int main (void)
{
double start, stop, elapsed, datasize;
/* generate test data */
printf ("starting data generation\n"); fflush(stdout);
uint64_t *stream[NBR_STREAMS+1];
for (int i = 0; i <= NBR_STREAMS; i++) {
stream [i] = malloc (sizeof (uint64_t) * NBR_BLOCKS);
if (stream[i] == 0) {
printf ("allocation for stream %d failed\n", i);
return EXIT_FAILURE;
}
for (int j = 0; j < NBR_BLOCKS; j++) {
stream[i][j] = KISS64;
}
}
printf ("data generation complete\n");
/* compute bits of output stream as majority of bits of input streams */
printf ("generate output stream; timed portion of code\n"); fflush(stdout);
for (int n = 0; n < BENCH_ITERS; n++) {
start = second();
for (int j = 0; j < NBR_BLOCKS; j++) {
#if (NBR_STREAMS == 3)
stream[3][j] = maj3 (stream[0][j], stream[1][j], stream[2][j]);
#elif (NBR_STREAMS == 5)
stream[5][j] = maj5 (stream[0][j], stream[1][j], stream[2][j],
stream[3][j], stream[4][j]);
#elif (NBR_STREAMS == 7)
stream[7][j] = maj7 (stream[0][j], stream[1][j], stream[2][j],
stream[3][j], stream[4][j], stream[5][j],
stream[6][j]);
#elif (NBR_STREAMS == 9)
stream[9][j] = maj9 (stream[0][j], stream[1][j], stream[2][j],
stream[3][j], stream[4][j], stream[5][j],
stream[6][j], stream[7][j], stream[8][j]);
#else
#error unsupported N
#endif
}
stop = second();
}
elapsed = stop - start;
datasize = sizeof (uint64_t) * NBR_BLOCKS * (NBR_STREAMS + 1);
printf ("processed at %.3f GB/sec\n", datasize * 1e-9 / elapsed);
printf ("checking output stream\n"); fflush(stdout);
/* check result stream, the slow way */
for (int j = 0; j < NBR_BLOCKS; j++) {
uint64_t t[NBR_STREAMS+1];
for (int i = 0; i <= NBR_STREAMS; i++) {
t[i] = stream[i][j];
}
for (int k = 0; k < 64; k++) {
int majority, bitcount = 0;
for (int i = 0; i < NBR_STREAMS; i++) {
bitcount += (t[i] >> k) & 1;
}
majority = bitcount > (NBR_STREAMS / 2);
if (majority != ((t[NBR_STREAMS] >> k) & 1)) {
printf ("error at block %d bit %d res=%d ref=%d\n",
j, k, majority, (int)((t[NBR_STREAMS] >> k) & 1));
return EXIT_FAILURE;
}
}
}
printf ("test passed\n");
return EXIT_SUCCESS;
}
typedef unsigned long Chunk; // a wider type might help compilers make cleanup simpler
// if you can't promise them the size is a multiple of 64 bytes or something.
static inline
Chunk bitwise_majority_3(Chunk x, Chunk y, Chunk z) {
return (x&y) | (y&z) | (z&x);
}
static inline
Chunk bitwise_majority_5(Chunk a, Chunk b, Chunk c, Chunk d, Chunk e)
{
// abc ∨ abd ∨ abe ∨ acd ∨ ace∨ ade ∨ bcd ∨ bce ∨ bde ∨ cde
Chunk with_a = (a&b&c) | (a&b&d) | (a&b&e) |
(a&c&d) | (a&c&e) | (a&d&e);
Chunk without_a = (b&c&d) | (b&c&e) | (b&d&e) | (c&d&e);
return with_a | without_a;
}
static inline
Chunk bitwise_majority_7(Chunk a, Chunk b, Chunk c, Chunk d, Chunk e, Chunk f, Chunk g)
{
Chunk ab = a&b;
Chunk abc = ab&c; // some temporaries, mostly to save typing
Chunk abd = ab&d; // compilers make their own decisions about common subexpressions
Chunk fg = f&g;
Chunk with_ab = (abc & d) | (abc & e) | (abc & f) | (abc & g)
| (abd & e) | (abd & f) | (abd & g)
| (ab&e& f) | (ab&e& g)
| (ab& fg);
Chunk ac = a&c;
Chunk with_ac = (ac&d& e) | (ac&d& f) | (ac&d& g)
| (ac&e& f) | (ac&e& g)
| (ac& fg);
Chunk ad = a&d;
Chunk with_ad = (ad& e&f) | (ad& e&g) | (ad& fg);
Chunk with_a = with_ab | with_ac | with_ad | (a&e & fg);
Chunk bc = b&c;
Chunk with_bc = (bc&d& e) | (bc&d& f) | (bc&d& g) // same as with_ac but with bc
| (bc&e& f) | (bc&e& g)
| (bc& fg);
Chunk bd = b&d;
Chunk with_bd = (bd& e&f) | (bd& e&g) | (bd& fg);
Chunk with_b = with_bc | with_bd | (b&e & fg);
Chunk cd = c&d;
Chunk with_cd = (cd& e&f) | (cd& e&g) | (cd& fg);
Chunk with_c = with_cd | (c&e & fg);
Chunk with_d = (d&e & fg);
return with_a | with_b | with_c | with_d;
}
// bitwise_majority_9 left as an exercise for the reader
// or see njuffa's answer which implements maj9 in terms of maj3
型 给定这些标量构建块，我为编译器创建了简单的循环来向量化. __restrict，并且使用一个常量计数（是向量宽度的倍数）来避免任何清理或回退（用于重叠）代码，这就是我们要看的ASM。（Godbolt- MSVC vs. clang 17 for x86-64 AVX2 or for AArch64 SVE -mcpu=cortex-a710 . Change the cursor to look at GCC output.）
is_equal(a,b,c,d) == true, if popcount(a+b+c+d == 2)
value(a,b,c,d) = majority_of(a,b,c,d); // or ? for a tie
字符串 从maj5 == is_equal ? e : majority_of_four的构建块开始，如果4个值中已经存在多数，则第五个值不起作用;如果已经存在相等，则第五个值做出决定。 从四个输入a、B、c、d优化卡诺图给出10条指令（在ARM上--以及在VEX编码的SIMD上）
int maj5(int a, int b, int c, int d, int e)
{
// ab / cd
// 00 01 11 10
// 00 0 0 e 0
// 01 0 e 1 e
// 11 e 1 1 1
// 10 0 e 1 e
auto row0 = ~(a|b); // true for the top row
auto col0 = ~(c|d); // true for the leftmost column
auto row2 = a&b; // true for the row of `e 1 1 1`
auto col2 = c&d; // true for the col of `e 1 1 1`
// zero = true for all the entries in the map with output == 0
auto zero = (row0 | col0) & ~(row2 | col2);
// one = true for all the entries in the map with output == 1
auto one = (row2 | col2) & ~(row0 | col0);
// E = true for all those entries that are neither 0 or 1
auto E = ~(zero | one);
// final multiplex between one and `e`
return one | (e & E);
}
orr w5, w0, w1
and w0, w0, w1
orr w1, w2, w3
and w2, w2, w3
and w3, w5, w1
orr w1, w0, w2
eor w0, w1, w3
and w1, w1, w3
and w0, w0, w4
orr w0, w0, w1
int med7(int t, int o, int T, int O, int g) {
int G_OR_One = (t&o) | (T&O) | (o & T) | (O & t) | (t & T);
int One = (t & T) | (t & o & O) | (T & O & o);
return One | (G_OR_One & ~One & g);
}
and w8, w1, w3
orr w9, w0, w2
and w10, w2, w0
and w8, w9, w8
orr w11, w3, w1
orr w8, w8, w10
and w9, w11, w9
bic w10, w4, w8
and w9, w10, w9
orr w0, w9, w8
型 理论上，最后一个函数可以用6个任意的3输入函数来计算，而全加器需要4个，所以这比9个maj 3运算的最佳序列略差。但是当这样的函数不可用时，这个版本可能有用。 AArch 64 SVE has EOR3，一个3输入异或，全加器可以利用它。有一个non-SVE version用于FEAT_SHA3的CPU。 maj7的完整实现可能如下所示（原始版本有一个错误，即从第一个表达式中省略了一个术语(T & t)）。
typedef unsigned long long Chunk;
static inline
Chunk med7(Chunk t, Chunk o, Chunk T, Chunk O, Chunk g) {
Chunk G_OR_One = (t&o) | (T&O) | (o & T) | (O & t) | (t & T);
Chunk One = (t & T) | (t & o & O) | (T & O & o);
return One | (G_OR_One & ~One & g);
}
static inline
Chunk vertical_full_adder(Chunk x, Chunk y, Chunk z, Chunk *carry_out)
{
Chunk sum = x^y ^ z;
*carry_out = ((x^y) & z) | (x&y);
return sum;
//*carry_out = (x&y)|(x&z)|(y&z); // fun fact, this is a maj3
}
Chunk maj7_aki(Chunk a, Chunk b, Chunk c, Chunk d, Chunk e, Chunk f, Chunk g){
//[t, o] = full_adder(a,b,c); [T, O] = full_adder(d,e,f);
Chunk t, T;
Chunk o = vertical_full_adder(a,b,c, &t);
Chunk O = vertical_full_adder(d,e,f, &T);
return med7(t,o, T,O, g);
}
void testmaj7(){
Chunk a = 0x5555555555555555, b = 0x3333333333333333, c = 0x0f0f0f0f0f0f0f0f
, d = 0x00ff00ff00ff00ff, e = 0x0000ffff0000ffff, f = 0x00000000ffffffff;
// static_assert(maj7_aki(a,b,c,d,e,f, 0xffffffffffffffff) == bitwise_majority_7(a,b,c,d,e,f, 0xffffffffffffffff));
volatile Chunk sink; // look at the asm for constants stored
Chunk bitwise_majority_7(Chunk a, Chunk b, Chunk c, Chunk d, Chunk e, Chunk f, Chunk g); // reference version defined later
sink = maj7_aki(a,b,c,d,e,f, 0xffffffffffffffff);
sink = bitwise_majority_7(a,b,c,d,e,f, 0xffffffffffffffff); // same value: pass
sink = maj7_aki(0, a,b,c,d,e,f); // 0x101110117177F
sink = bitwise_majority_7(0, a,b,c,d,e,f); // 0x101170117177F : fail
// different value! ^
sink = maj7_aki(0, 0b0101,0b0011,0xf,0xf,0xf,0); // 1 // just the failing nibble
sink = bitwise_majority_7(0, 0b0101,0b0011,0xf,0xf,0xf,0); // 7
// 7 is indeed correct: 3 set bits in each position from the 0xf inputs
// and at least one additional set bit at each of the low 3 positions from the 0b0101 (5) and 0b0011 (3) inputs
// the full_adder maj7 needs a bit set in *both* those inputs to produce 1
}
型 也许最后一个编辑maj 7函数：
Chunk maj7_for_avx512(Chunk o, Chunk t, Chunk O, Chunk T, Chunk g) {
Chunk A = maj(o,t,T), B = maj(t,O,T); // 3 inputs each
return (A&B) | ((A|B) & g); // 3 inputs
}
4条答案
按热度按时间r3i60tvu1#
如果源数据流的数量是3、5、7或9，则可以利用经证明的最优或接近最优的通过3的多数基元的 n 的多数计算，也就是三元中值算子Kmxyz。Knuth，TAOCP Vol.4a，指出 any 单调布尔函数可以完全用三元中值算子和常数0和1来表示。
最近的文献（见下面代码中的注解）展示了如何以一种已被证明的最佳方式从3个多数中构造7个多数，后者需要7个示例。以这种方式构造9个多数的最佳方法仍然是一个开放的研究问题，但最近发现了一种相当有效的构造方法，使用13个3个多数的示例。下面的ISO-C99代码用于探索这种方法。
使用最新的x86-64工具链和
-march=skylake-avx512进行编译，可以获得相当高的数据吞吐量（数十GB/秒），但还没有达到系统内存吞吐量，这将是最终目标。其原因是编译器还不能可靠地将3的多数原语Map到AVX 512可用的vpternlogq指令，其中3个操作中的大多数可以用一条这样的指令来表示。人们必须通过使用intrinsic或使用内联汇编来解决这个问题。字符串
pw136qt22#
**编译器可以很好地自动向量化布尔运算;你可以编写一个在
unsigned char ***上运行的C循环，或者更大的块大小，如unsigned long*，如果这对你的数据方便的话，没有严格的别名冲突。结果asm应该一次在128或256位上运行。或者根据编译器调优选项，512位。如果您没有AVX-512可用（或另一个具有3输入逻辑操作的伊萨），请参阅阿基Suihkonen对手工优化的maj 5和maj 7的回答，这比编译器为这个回答中显示的天真版本所做的更好。（特别是非clang），比如Ice Lake上的Maj 7 AVX 2比这个答案的Maj 7与clang快1.33倍，或者3x vs. GCC。如果你在数组上的循环中使用这些函数，他的答案中显示的标量asm对应于AVX或 neon /SVE向量asm。
如果您 * 确实 * 有三进制逻辑可用并希望手动使用它，请参阅njuffa的答案（例如AVX-512 intrinsic），用于实现maj 5和更广泛的maj 3，并引用了该领域研究的一些文献。（显然严格使用maj 3作为构建块，而不是像AVX-512那样的任意三进制逻辑，阿基的函数也可以从三进制逻辑中受益，无论是手动还是让编译器找到3输入操作组，即使编译器在使用3输入逻辑方面远为最优。
AArch 64 SVE或FEAT_SHA3有EOR 3，一个3输入XOR，编译器用于阿基的版本，例如
-mcpu=cortex-a710. ASIMD version/SVE version。我不知道AArch 64中的其他3输入布尔运算，但3输入XOR对全加器很有用。手动矢量化可能有助于更好地利用AVX-512
vpternlogd，这是一种3输入按位布尔值，将8位真值表作为立即数，运行成本与简单的2输入vpand或vpor一样低（https://uops.info/），但它必须重写其输入之一，因此如果以后需要，可能需要vmovdqa寄存器副本。对于每个3位的垂直组，它在那个表中查找结果，就像FPGA一样。所以它可以在一条指令中计算任何3输入布尔函数（对于例如256位的整个向量），例如Maj3。编译器将使用a & b | c优化代码以使用它，但并不完美。对于编写Maj3的直接方法，GCC，Clang，MSVC和MSVC对每个结果向量使用两条vpternlogd或vpternlogq指令。字符串
如果你把
Maj5写成类似(a&b&c) | (a&b&d) | (a&b&e) | ...的东西，只做一次a&b部分，那么编译器也很擅长消除公共子表达式。简单可移植源代码的自动向量化可能对你的用例来说已经足够好了，至少有clang，很难击败intrinsic，除非你有一个三元操作（我认为只有AVX-512出ISA你提到。不是AVX 2或更早，我不知道一个在AArch 64 neon /ASIMD或SVE，而clang不使用一个。）编译器在Maj 5和Maj 7的内部循环中使用多少个按位布尔操作上有所不同。我没有看Maj 9，这比我感兴趣的要多！型
给定这些标量构建块，我为编译器创建了简单的循环来向量化.
__restrict，并且使用一个常量计数（是向量宽度的倍数）来避免任何清理或回退（用于重叠）代码，这就是我们要看的ASM。（Godbolt- MSVC vs. clang 17 for x86-64 AVX2 or for AArch64 SVE-mcpu=cortex-a710. Change the cursor to look at GCC output.）型
**Maj 3：**使用AVX 2或SVE：2x
vpand/ 2xvpor，加上3个加载和一个存储。Clang-O3 -march=x86-64-v3 -fno-unroll-loops（AVX 2）将在Intel CPU上运行10个uop，所以我们希望Ice Lake能够以每32字节输出2个周期的速度运行它，如果不从L2或更糟的地方检查缓存带宽的话。（另请参阅 * Micro fusion and addressing modes * -幸运的是，gcc -march=skylake而不是-march=x86-64-v3使用索引寻址模式两次使用相同的内存操作数进行单独加载。Clang的循环在14 ops中执行Maj 5，在26 ops中执行Maj 7，使用AVX 2 for ARM ASIMD或SVE。
GCC和MSVC更差，Maj 5使用17个双输入位操作。
Maj 7的情况更糟：GCC为60 ops，MSVC为36。
如果所有内容都命中L1 d缓存，https://uica.uops.info/预测Clang的
vec_majority_7循环将以每个输出向量8.69个周期的速度运行（对于具有32字节向量的AVX 2）。瓶颈是向量ALU端口。（要使用uiCA，只需从编译器asm输出中复制/粘贴循环体，从标签开始，以jnz .L3或其他什么结尾。不是整个函数的序言和ret。）AVX-512
AVX-512对Maj 7的改进远远没有达到应有的效果，因为
vpternlogq的使用效率低下。njuffa显示了总共7个maj 3（三进制）操作，但是clang总共使用了19条vpternlogq+vpand+vpor指令。所以这比它需要的慢了2.7倍。uica预测每32个周期有6.33个周期。字节向量，仅比AVX 2有小幅加速。AVX-512还允许512位向量。512位uop将关闭英特尔CPU上端口1上的向量ALU，因此如果AVX-512
vpternlogq ymm与AVX-512vpternlogq zmm的频率保持不变，我们预计吞吐量将提高约1.5倍。（这可能是在冰湖/火箭湖桌面芯片给予足够的冷却，因为按位操作是“轻”的限制最大涡轮增压）。uiCA对Ice Lake的分析是Maj 7的每64字节向量结果9.50个周期，因此每32字节输出4.75个周期。这是假设L1 d缓存命中，但整个缓存行的64字节加载可能有助于在非理想情况下避免额外的冲突未命中。
多输入流缓存冲突未命中注意事项
使用Maj 7，您有7个输入流（希望其中一个也是就地输出流）。L1 d缓存在许多CPU上只有8路关联，或12-way on some newer ones like Ice Lake。如果所有输入都位于不同页面内的类似偏移量，这可能导致冲突未命中。或者L2别名的较大区域大小内的类似偏移量，特别是在Skylake上，它只有4路关联。（后来Intel有更大的L2缓存，例如Ice Lake有512 K，并将关联性提升到8。）
参见 * For-loop efficiency: merging loops *，了解在Skylake等CPU上具有多个内存访问流的循环的一些细节;它们可以处理超过4个，但即使您没有4K别名暂停，7到9个也会推动它。
对于这一点，你可以做的并不多，除非有任何范围可以将5个输入减少到2个或其他东西，以块的方式工作来缓存它。或者在附近的时间间隔内从任何给定的缓存行读取所有数据，而不需要在其间阅读和写入大量其他缓存行。只有16个每个32字节的矢量缓存（AVX 2），加载两组7个向量只会留下两个临时变量，对于9个输入是不起作用的。但是如果你展开的话，也许你可以留下一些未读的变量。
使用AVX-512，你有32个向量对齐。你可以一次读取整个缓存行作为一个向量，假设你的数据是64对齐的。（或者128对齐，以利于L2空间预取器尝试完成对齐的对）。
如果冲突未命中是一个严重的问题，那么可以通过将9个输入阵列中的5个阵列中的一两个缓存行复制到一个连续的缓冲区中来实现缓存阻塞（5x 64 x2 = 640字节）。因此，对这些缓存行中的每一个的所有访问都是连续发生的，例如，使用4x 128位向量。然后您在该块上循环，从其中的固定步幅重新加载向量，同时从源阵列加载其他4个向量的数据。因此，对任何输入缓存行的访问仅被对可能Map到同一集合的其他5个缓存行的访问分隔开。这对于伪并且10缓存行缓冲区足够小，可以在L1 d中保持热状态，而不会耗尽L1 <->L2带宽。
如果你尝试这样做，检查asm以确保编译器没有破坏复制，或者如果它破坏了复制，有足够的向量寄存器让它做连续加载。
up9lanfz3#
问题
maj5的部分解决方案来自于首先计算两个输出maj4字符串
从
maj5 == is_equal ? e : majority_of_four的构建块开始，如果4个值中已经存在多数，则第五个值不起作用;如果已经存在相等，则第五个值做出决定。从四个输入a、B、c、d优化卡诺图给出10条指令（在ARM上--以及在VEX编码的SIMD上）
型
这个4输入逻辑功能的构建块可以转换为SSSE 3上的
pshufb或ARM 64上的vqtbl1q，因为位交织将是有效的。（在ARM 64上，vsri的树，vsli通常会像位矩阵转置一样做这件事;pmull和pclmulqdq也可以用于交织比特--但是根据经验，我希望vsri/vsli在转置上更有效。我还考虑将4个独立的流交织成半字节--随着流数量的增长，所需的算术函数数量只会线性增长（在一定程度上），并且还将避免由于高速缓存实现而导致的高速缓存行驱逐（4路和8路关联高速缓存可能仍然很常见）。如果数据将以8进行交织，那么 neon
vcnt和AVX-512vpopcntb就可以很容易地使用了--这使得整个算法的内存受限，而且在每个uint8_t存储一个布尔值方面可能有点浪费--但是，输出格式已经与输入格式基本兼容了。型
对于maj 7函数，我的最大努力并没有（显然）将maj 3树与7条指令相匹配，而是编译成比基于maj 3的方法更少的二进制操作。
上面的想法扩展到
[t, o] = full_adder(a,b,c); [T, O] = full_adder(d,e,f);，t，o Map到 twos，ones 或 carry，sum。型
理论上，最后一个函数可以用6个任意的3输入函数来计算，而全加器需要4个，所以这比9个maj 3运算的最佳序列略差。但是当这样的函数不可用时，这个版本可能有用。
AArch 64 SVE has EOR3，一个3输入异或，全加器可以利用它。有一个non-SVE version用于
FEAT_SHA3的CPU。maj7的完整实现可能如下所示（原始版本有一个错误，即从第一个表达式中省略了一个术语(T & t)）。型
也许最后一个编辑maj 7函数：
型
可以看出，现在只有3个独立的3操作数函数被调用，当与两个全加器调用相结合时，应该转换为7个
vpternlogd指令。Godbolt，包括这些maj 5和maj 7的自动向量化循环，clang使用2x
EOR3作为maj 7。希望这是可修复的，无需额外的指令。它对大多数输入都是正确的。这个不正确的版本在AVX 2的一个循环中编译为19个按位操作，在使用SVE的
-mcpu=cortex-a710中编译为19个按位操作，尽管其中两个是EOR 3。充其量它缩短了关键路径延迟，例如与eor dst2, z4, z3并行执行eor3 dst1, z4, z3, z5。inb24sb24#
正如在其他答案中所讨论的，Maj 3，Maj 5，Maj 7或Maj 9的特定函数可以很好地自动矢量化。（特别是AVX-512
vpternlogd，尽管编译器并没有将其最佳地用于Maj 3作为单个操作。）对于Skylake上的clang AVX 2，Maj 3这种方式比Maj 3这种方式快19倍，如果缓存带宽不是瓶颈的话。或者Maj 7是阿基版本的11倍。如果你需要支持任意数量的投票者，位置popcount是一种策略，在
n输入中每个比特位置一个字节，所以输出是1，如果count >= n/2+1。例如，以AVX 2为例，我们以SIMD字节比较和movemask结束，以获得32个输出比特。使用向量指令的一个选项是通过可移植的API（如
std::experimental::simd或gcc vector extensions built-in functions）来处理，例如，使用256位向量一次处理32个投票。它缺少一个movemask操作;编译器不够聪明，无法将这种可移植的提取和OR策略优化为x86 movemask或AArch64 shift-right-and-insert chains（当将多个向量减少到64位掩码时，这可能更有效）。
在带有AVX 2的x86上，它执行大约4条向量指令来加载每行32个投票（4个字节）并将其相加（广播加载，
v & mask == mask和减法）。另外10条指令用于计算和存储计数中的多数投票。字符串
产出：
型
生成的组件是体面的：循环被展开（由于编译时间常数
R（行））、向量化存储和广播加载，没有超出所需最小值的额外加载或存储、没有堆栈溢出，其中gcc-13.2 -O3和clang-17.0.1 -O2具有-march=x86-64-v3。但对于小的固定投票计数，这仍然比纯垂直按位操作慢 * 得多 *。最差的是Maj 3，这在AVX 2 clang的每4个结果字节的循环中有18个向量ALU指令的瓶颈，与Maj 3相比，使用
unsigned long自动矢量化(a&b) | (a&c) | (b&c)（每个结果向量优化为2个AND和2个OR），每32字节输出10条指令（Peter的答案）。如果没有缓存未命中，https://uica.uops.info/预测在Skylake或Ice Lake上每4个字节最多运行6个周期，而clang编译的方式每32个字节有2.5或2.0个周期。这是19倍的加速/减速。Maj 7没有那么极端，但仍然是阿基的11倍。
另一种选择是使用英特尔AVX 2内部函数来换取速度的可移植性，特别是清理速度。这个版本可以是more efficient than the above，每行投票大致相同的4条AVX指令，但只有5条来计算和存储结果，利用AVX
_mm256_movemask_epi8指令在gcc矢量扩展内置函数中不可用。型