Truth-table 还原为三元逻辑运算，vpternlog
Truth-table reduction to ternary logic operations, vpternlog
我有很多变量（7 个或更多）的真值表，我使用工具（例如逻辑星期五 1）来简化逻辑公式。我可以手工完成，但那太容易出错了。然后我将这些公式转换为编译器内部函数（例如 _mm_xor_epi32），效果很好。
问题: 用vpternlog我可以进行三元逻辑运算。但是我不知道有一种方法可以将我的真值表简化为（有点）高效的 vpternlog 指令序列。
我不是在问是否有人知道可以简化任意三元逻辑运算的工具，虽然那会很棒，但我正在寻找一种方法来进行此类简化。
编辑：我在 Electrical Engineering 上问了一个类似的问题。
除了将其留给编译器或我回答的第二部分中的手动建议之外，请参阅 使用 FPGA 逻辑优化工具的自我回答。 （这个答案以赏金告终，因为它没有吸引其他任何人这样的答案；它不是真正值得赏金的。：/我在有赏金之前写了它，但没有其他有用的东西可以添加。）
ICC18 将链式 _mm512_and/or/xor_epi32 内在函数优化为 vpternlogd 指令，但 gcc/clang 不会。
On 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 个变量。
我认为一个真理 table 有可能有超过 3 个输入到 而不是 以这种方式简化为一个更小的真理 table 其中一个的列是 3 个输入的三元组合的结果。例如我认为不能保证可以将 4 输入函数简化为 vpternlog + AND、OR 或 XOR。
我绝对担心编译器可能会选择 3 个输入进行组合，而这并没有像选择 3 个不同的输入那样简化。
对于编译器来说，从一对二元运算或两个二元运算开始以设置三元运算甚至可能是最佳选择，尤其是如果这样可以实现更好的 ILP。
你可能会写一个蛮力 truth-table 优化器来寻找变量的三元组，这些变量可以组合成一个更小的 table 三元结果和其余的table。但我不确定贪婪的方法是否能保证给出最好的结果。如果有多种方法可以结合相同的总指令数，那么对于 ILP (Instruction Level Parallelism).
，它们可能并不都是等价的
如何将真理 table 转化为一系列 vpternlog 指令。
- 将真理table翻译成逻辑公式；使用例如逻辑星期五。
- 以 Synopsys 方程格式 (.eqn) 存储逻辑公式。例如，我使用了一个具有 6 个输入节点 A 到 F、两个输出节点 F0 和 F1 以及一个有点复杂（非单一）布尔函数的网络。
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: A System for Sequential Synthesis and Verification"。我使用的是 windows 版本。获取 ABC here.
在 ABC I 运行:
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-hard 问题。此外，无法将指令并行性告知 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 次...）
我有很多变量（7 个或更多）的真值表，我使用工具（例如逻辑星期五 1）来简化逻辑公式。我可以手工完成，但那太容易出错了。然后我将这些公式转换为编译器内部函数（例如 _mm_xor_epi32），效果很好。
问题: 用vpternlog我可以进行三元逻辑运算。但是我不知道有一种方法可以将我的真值表简化为（有点）高效的 vpternlog 指令序列。
我不是在问是否有人知道可以简化任意三元逻辑运算的工具，虽然那会很棒，但我正在寻找一种方法来进行此类简化。
编辑：我在 Electrical Engineering 上问了一个类似的问题。
除了将其留给编译器或我回答的第二部分中的手动建议之外，请参阅
ICC18 将链式 _mm512_and/or/xor_epi32 内在函数优化为 vpternlogd 指令，但 gcc/clang 不会。
On 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 个变量。
我认为一个真理 table 有可能有超过 3 个输入到 而不是 以这种方式简化为一个更小的真理 table 其中一个的列是 3 个输入的三元组合的结果。例如我认为不能保证可以将 4 输入函数简化为 vpternlog + AND、OR 或 XOR。
我绝对担心编译器可能会选择 3 个输入进行组合，而这并没有像选择 3 个不同的输入那样简化。
对于编译器来说，从一对二元运算或两个二元运算开始以设置三元运算甚至可能是最佳选择，尤其是如果这样可以实现更好的 ILP。
你可能会写一个蛮力 truth-table 优化器来寻找变量的三元组，这些变量可以组合成一个更小的 table 三元结果和其余的table。但我不确定贪婪的方法是否能保证给出最好的结果。如果有多种方法可以结合相同的总指令数，那么对于 ILP (Instruction Level Parallelism).
，它们可能并不都是等价的如何将真理 table 转化为一系列 vpternlog 指令。
- 将真理table翻译成逻辑公式；使用例如逻辑星期五。
- 以 Synopsys 方程格式 (.eqn) 存储逻辑公式。例如，我使用了一个具有 6 个输入节点 A 到 F、两个输出节点 F0 和 F1 以及一个有点复杂（非单一）布尔函数的网络。
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: A System for Sequential Synthesis and Verification"。我使用的是 windows 版本。获取 ABC here.
在 ABC I 运行:
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-hard 问题。此外，无法将指令并行性告知 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 次...）