3 진 논리 연산에 대한 진리표 감소, vpternlog

Question

많은 논리 테이블 (7 개 이상)을 가지고 있으며 논리 공식을 단순화하는 도구 (예 : 논리 금요일 1)를 사용합니다. 나는 손으로 그것을 할 수 있었다. 그러나 그것은 너무 많이 범하는 경향이있다. 이 수식을 컴파일러 내장 함수 (예 : _mm_xor_epi32)로 변환하면 정상적으로 작동합니다.

질문 : vpternlog 나는 삼항 논리 연산을 만들 수 있습니다. 그러나 (다소) 효율적인 vpternlog 명령어 시퀀스로 내 진리표를 단순화하는 방법을 알고 있지 않습니다.

임의의 3 진 논리 연산을 단순화하는 도구를 알고 있는지 묻지는 않지만 위와 같은 단순화 방법을 찾고 있습니다.

편집 : 나는 비슷한 질문을 Electrical Engineering에 요청했다.

Answer 1

진실 표를 vpternlog 명령 시퀀스로 변환하는 방법.

1. 진리표를 논리적 공식으로 변환합니다. 예 : Logic Friday를 사용합니다.
2. 논리 공식을 Synopsys 방정식 형식 (.eqn)으로 저장하십시오. 예를 들어, 6 개의 입력 노드 A ~ F, 2 개의 출력 노드 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); 

1. 사용 : 버클리 검증 및 합성 연구 센터에서 "ABC를 순차 합성 및 검증을위한 시스템". Windows 버전을 사용했습니다. ABC here을 받으십시오. 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 여러 번 실행해야 할 수도 있습니다.

문제가 남아

__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 여부 ++이 기계적 C++로 번역 될 수

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. :

생성 BF_Q6.bench는 FPGA에 대한 3 개의 LUT를 포함 코드가 최적입니다. 나는이 방법이 (종종)이 문제가 NP 하드이기 때문에 3-LUT의 가장 작은 네트워크를 산출한다고 생각하지 않는다. 또한 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 번 가져온다 ...)

Answer 2

제 대답의 두 번째 섹션에서 컴파일러 또는 손을 물어 보지 않는 것 외에도 FPGA 로직 최적화 도구를 사용하는 HJLebbink의 자체 응답을 참조하십시오. (이 답변은 다른 사람들로부터 그러한 답변을 끌어 내지 못했기 때문에 현상금으로 끝나기는했지만 실제로는 현상금이 아닙니다 : : 현상금이 부과되기 전에 썼습니다 만 추가할만한 것이 없습니다.)

---

ICC18는 vpternlogd 지침에 _mm512_and/or/xor_epi32 내장 함수를 체인 최적화합니다,하지만 GCC/그 소리는하지 않습니다. 이 및 사용하여 더 복잡한 기능

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: 
    vpternlogd zmm2, zmm0, zmm1, 128      #6.21 
    vpternlogd zmm4, zmm2, zmm3, 128      #6.29 
    vpandd zmm0, zmm4, zmm5        #6.33 
    ret              #6.33 

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 그것에서 얼마나 좋은 IDK 구축 최적 해를 구하는 것 wh 각 변수는 서로 다른 하위 표현식에서 두 번 이상 사용됩니다.

---

잘하는 지 확인하려면 직접 최적화해야합니다. 표현식에서 다른 곳의 변수를 필요로하지 않으면 서 하나의 부울 값으로 결합 할 수있는 3 개의 변수 세트를 찾고 싶습니다.

가 나는 열 중 하나는 입력의 3 원계 조합의 결과 인 작은 진실 테이블에,이 방법을 단순화하지에 3 개 이상의 입력을 진리표에 대해 가능하다고 생각. 예 : vpternlog + AND, OR 또는 XOR에 대한 4 입력 기능을 단순화하는 것이 가능하다고 보장하지는 않는다고 생각합니다.

나는 확실히 컴파일러 바이너리로 시작하는 컴파일러가 그것은 심지어 최적의 수 있습니다 3.

의 다른 선택만큼 단순화를 초래하지 않았다 결합하는 3 개 입력을 선택할 수 있다는 걱정 것 하나 또는 두 개의 쌍으로 두 개를 조합하여 세 번째 연산을 설정할 수 있습니다.

아마도 3 진 결과와 나머지 테이블에 대해 더 작은 테이블을 만들기 위해 결합 될 수있는 변수의 세 쌍을 찾는 brute-force 진리표 최적화기를 작성할 수 있습니다. 그러나 나는 욕심 많은 접근 방식이 최고의 결과를 보장한다고 확신하지 못합니다. 동일한 총 명령어 수와 결합 할 수있는 여러 가지 방법이있는 경우 ILP (Instruction Level Parallelism)에 대해 모두 동일한 것은 아닙니다.