HJL*_*ink 9 boolean-logic intrinsics truthtable avx512
我有许多变量(7或更多)的真值表,我使用工具(例如逻辑星期五1)来简化逻辑公式.我可以手工完成,但这太容易出错了.这些公式然后转换为编译器内在函数(例如_mm_xor_epi32),它工作正常.
问题:使用vpternlog我可以进行三元逻辑运算.但我不知道一种方法来简化我的真值表到vpternlog指令序列(有些)有效.
我不是在问是否有人知道一个简化为任意三元逻辑运算的工具,虽然这很好,但我正在寻找一种方法来进行这种简化.
编辑:我问了一个关于电气工程的类似问题.
除了将它留给编译器,或者我的答案的第二部分中的手工波形建议之外,请参阅HJLebbink使用FPGA逻辑优化工具的自我回答.(这个答案最终得到了赏金,因为它未能从其他任何人那里吸引这样的答案;它并不是真正有价值的.:/我在有赏金之前写过它,但没有其他任何有用的东西可以补充.)
ICC18将链式_mm512_and/or/xor_epi32内在函数优化为vpternlogd指令,但gcc/clang则不然.
在Godbolt上这个以及使用一些输入多次的更复杂的功能:
#include <immintrin.h>
__m512i logic(__m512i a, __m512i b, __m512i c,
__m512i d, __m512i e, __m512i f, __m512i g) {
// return _mm512_and_epi32(_mm512_and_epi32(a, b), c);
return a & b & c & d & e & f;
}
gcc -O3 -march=skylake-avx512 每晚建造
logic:
vpandq zmm4, zmm4, zmm5
vpandq zmm3, zmm2, zmm3
vpandq zmm4, zmm4, zmm3
vpandq zmm0, zmm0, zmm1
vpandq zmm0, zmm4, zmm0
ret
ICC18 -O3 -march=skylake-avx512
logic:
vpternlogd zmm2, zmm0, zmm1, 128 #6.21
vpternlogd zmm4, zmm2, zmm3, 128 #6.29
vpandd zmm0, zmm4, zmm5 #6.33
ret #6.33
IDK在每个变量在不同的子表达式中多次使用时,选择最佳解决方案有多好.
要查看它是否做得好,您必须自己进行优化. 您希望找到3个变量的集合,这些变量可以组合成一个布尔值,而不需要在表达式中的任何其他位置使用这3个变量.
我认为有一个超过3个输入的真值表可能不会以这种方式简化到一个较小的真值表,其中一列是三个输入的三元组合的结果.例如,我认为不能保证将4输入函数简化为vpternlog + AND,OR或XOR.
我肯定担心编译器可能会选择3个输入来组合,这不会导致3个不同选择的简化.
对于编译器来说,最好是以二进制操作开始,或者在两对上开始设置三元运算,尤其是如果能够实现更好的ILP.
您可能可以编写一个强力真值表优化器,它可以查找变量的三元组,这些变量可以组合起来,只为三元结果和表格的其余部分创建一个较小的表.但我不确定贪婪的方法能保证给出最好的结果.如果有多种方法可以将相同的总指令数组合在一起,那么它们可能并不完全等同于ILP(指令级并行).
如何将真值表转换为vpternlog指令序列。
BF_Q6.eqn的内容：
INORDER = A B C D E F;
OUTORDER = F0 F1;
F0 = (!A*!B*!C*!D*!E*F) + (!A*!B*!C*!D*E*!F) + (!A*!B*!C*D*!E*!F) + (!A*!B*C*!D*!E*!F) + (!A*B*!C*!D*!E*!F) + (A*!B*!C*!D*!E*!F);
F1 = (!A*!B*!C*!D*E) + (!A*!B*!C*D*!E) + (!A*!B*C*!D*!E) + (!A*B*!C*!D*!E) + (A*!B*!C*!D*!E);
在 ABC 我运行：
abc 01> read_eqn BF_Q6.eqn
abc 02> choice; if -K 3; ps
abc 03> lutpack -N 3 -S 3; ps
abc 04> show
abc 05> write_bench BF_Q6.bench
您可能需要运行choice; if -K 3; ps多次才能获得更好的结果。
生成的 BF_Q6.bench 包含 FPGA 的 3-LUT：
INPUT(A)
INPUT(B)
INPUT(C)
INPUT(D)
INPUT(E)
INPUT(F)
OUTPUT(F0)
OUTPUT(F1)
n11 = LUT 0x01 ( B, C, D )
n12 = LUT 0x1 ( A, E )
n14 = LUT 0x9 ( A, E )
n16 = LUT 0xe9 ( B, C, D )
n18 = LUT 0x2 ( n11, n14 )
F1 = LUT 0xae ( n18, n12, n16 )
n21 = LUT 0xd9 ( F, n11, n14 )
n22 = LUT 0xd9 ( F, n12, n16 )
F0 = LUT 0x95 ( F, n21, n22 )
4. 这可以机械地翻译成C++：
__m512i not(__m512i a) { return _mm512_xor_si512(a, _mm512_set1_epi32(-1)); }
__m512i binary(__m512i a, __m512i b, int i) {
switch (i)
{
case 0: return _mm512_setzero_si512();
case 1: return not(_mm512_or_si512(a, b));
case 2: return _mm512_andnot_si512(a, b);
case 3: return not(a);
case 4: return _mm512_andnot_si512(b, a);
case 5: return not(b);
case 6: return _mm512_xor_si512(a, b);
case 7: return not(_mm512_and_si512(a, b));
case 8: return _mm512_and_si512(a, b);
case 9: return not(_mm512_xor_si512(a, b));
case 10: return b;
case 11: return _mm512_or_si512(not(a), b);
case 12: return a;
case 13: return mm512_or_si512(a, not(b));
case 14: return _mm512_or_si512(a, b);
case 15: return _mm512_set1_epi32(-1);
default: return _mm512_setzero_si512();
}
}
void BF_Q6(const __m512i A, const __m512i B, const __m512i C, const __m512i D, const __m512i E, const __m512i F, __m512i& F0, __m512i& F1) {
const auto n11 = _mm512_ternarylogic_epi64(B, C, D, 0x01);
const auto n12 = binary(A, E, 0x1);
const auto n14 = binary(A, E, 0x9);
const auto n16 = _mm512_ternarylogic_epi64(B, C, D, 0xe9);
const auto n18 = binary(n11, n14, 0x2);
F1 = _mm512_ternarylogic_epi64(n18, n12, n16, 0xae);
const auto n21 = _mm512_ternarylogic_epi64(F, n11, n14, 0xd9);
const auto n22 = _mm512_ternarylogic_epi64(F, n12, n16, 0xd9);
F0 = _mm512_ternarylogic_epi64(F, n21, n22, 0x95);
}
问题仍然是生成的 C++ 代码是否最优。我不认为这种方法（通常）会产生最小的 3-LUT 网络，仅仅是因为这个问题是 NP 困难的。此外，不可能告知 ABC 有关指令并行性的信息，也不可能对变量的顺序进行优先级排序，以便稍后使用的变量不会位于 LUT 的第一个位置（因为第一个源操作数被覆盖）结果）。但编译器可能足够聪明，可以进行此类优化。
ICC18 给出了以下汇编：
00007FF75DCE1340 sub rsp,78h
00007FF75DCE1344 vmovups xmmword ptr [rsp+40h],xmm15
00007FF75DCE134A vmovups zmm2,zmmword ptr [r9]
00007FF75DCE1350 vmovups zmm1,zmmword ptr [r8]
00007FF75DCE1356 vmovups zmm5,zmmword ptr [rdx]
00007FF75DCE135C vmovups zmm4,zmmword ptr [rcx]
00007FF75DCE1362 vpternlogd zmm15, zmm15, zmm15, 0FFh
00007FF75DCE1369 vpternlogq zmm5, zmm1, zmm2, 0E9h
00007FF75DCE1370 vmovaps zmm3, zmm2
00007FF75DCE1376 mov rax, qword ptr[&E]
00007FF75DCE137E vpternlogq zmm3, zmm1, zmmword ptr[rdx], 1
00007FF75DCE1385 mov r11, qword ptr[&F]
00007FF75DCE138D mov rcx, qword ptr[F0]
00007FF75DCE1395 mov r10, qword ptr[F1]
00007FF75DCE139D vpord zmm0, zmm4, zmmword ptr[rax]
00007FF75DCE13A3 vpxord zmm4, zmm4, zmmword ptr[rax]
00007FF75DCE13A9 vpxord zmm0, zmm0, zmm15
00007FF75DCE13AF vpxord zmm15, zmm4, zmm15
00007FF75DCE13B5 vpandnd zmm1, zmm3, zmm15
00007FF75DCE13BB vpternlogq zmm1, zmm0, zmm5, 0AEh
00007FF75DCE13C2 vpternlogq zmm15, zmm3, zmmword ptr[r11], 0CBh
^^^^^ ^^^^^^^^^^^^^^^^
00007FF75DCE13C9 vpternlogq zmm5, zmm0, zmmword ptr[r11], 0CBh
00007FF75DCE13D0 vmovups zmmword ptr[r10], zmm1
00007FF75DCE13D6 vpternlogq zmm5, zmm15, zmmword ptr[r11], 87h
00007FF75DCE13DD vmovups zmmword ptr [rcx],zmm5
00007FF75DCE13E3 vzeroupper
00007FF75DCE13E6 vmovups xmm15,xmmword ptr [rsp+40h]
00007FF75DCE13EC add rsp,78h
00007FF75DCE13F0 ret
ICC18 能够更改变量顺序，const auto n22 = _mm512_ternarylogic_epi64(F, n12, n16, 0xd9);以便vpternlogq zmm15, zmm3, zmmword ptr[r11], 0CBh变量 F 不会被覆盖。（但奇怪的是，从内存中提取了 3 次......）