10

我有很多变量(7 个或更多)的真值表,我使用工具(例如逻辑星期五 1)来简化逻辑公式。我可以手动完成,但这太容易出错了。然后我将这些公式转换为运行良好的编译器内在函数(例如_mm_xor_epi32)。

问题:使用vpternlog我可以进行三元逻辑运算。但是我不知道有一种方法可以将我的真值表简化为(有点)有效的 vpternlog 指令序列。

我不是在问是否有人知道一种可以简化为任意三元逻辑运算的工具,尽管那会很棒,但我正在寻找一种方法来进行这种简化。

编辑:我问了一个关于电气工程的类似问题。

4

2 回答 2

8

除了将其留给编译器或我的答案第二部分中的手动建议之外,请参阅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 个输入的真值表可能不会以这种方式简化为一个较小的真值表,其中一列是 3 个输入的三元组合的结果。例如,我认为不能保证可以将 4 输入函数简化为 vpternlog + AND、OR 或 XOR。

我肯定会担心编译器可能会选择 3 个输入来组合,这不会像选择 3 那样简化。

对于编译器来说,从一对或两个二元运算开始以设置三元运算甚至可能是最佳选择,特别是如果这样可以实现更好的 ILP。

您可能会编写一个蛮力真值表优化器,它寻找三元组变量,这些变量可以组合成一个较小的表,仅用于三元结果和表的其余部分。但我不确定贪婪的方法能保证给出最好的结果。如果有多种方法可以结合相同的总指令数,那么它们可能并不完全等同于ILP(指令级并行)

于 2017-11-28T18:00:34.950 回答
4

How to translate a truth table to a sequence of vpternlog instructions.

  1. Translate the truth table into a logical formula; use e.g., Logic Friday.
  2. Store the logical formula in Synopsys equation format (.eqn). E.g., I used a network with 6 input nodes A to F, two output nodes F0 and F1, and a somewhat complicated (non unate) Boolean function.

Content of 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);
  1. Use "ABC: A System for Sequential Synthesis and Verification" from the Berkeley Verification and Synthesis Research Center. I used the windows version. Get ABC here.

In ABC I run:

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

You may need to run choice; if -K 3; ps multiple time to get better results.

The resulting BF_Q6.bench contains the 3-LUTs for an FPGA:

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. This can be translated to C++ mechanically:

__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);
}

The question remains whether the resulting C++ code is optimal. I don't think that this method (often) yields the smallest networks of 3-LUTs, simply because this problem is NP-hard. Additionally, it is not possible to inform ABC about instruction parallelism, and it is not possible to prioritize the order of variables such that variables that will be used later are not in the first position of the LUT (since the first source operand is overwritten with the result). But the compiler may be smart enough to do such optimizations.

ICC18 gives the following assembly:

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 is able to change the variable ordering in const auto n22 = _mm512_ternarylogic_epi64(F, n12, n16, 0xd9); to vpternlogq zmm15, zmm3, zmmword ptr[r11], 0CBh such that variable F is not overwritten. (But strangely enough fetched from memory 3 times...)

于 2017-12-12T14:46:08.730 回答