Bob Steagall baru-baru ini memberikan ceramah di CppCon 2020 berjudul " Adventures in SIMD-thinking ", di mana, antara lain, dia berbicara tentang pengalamannya menggunakan AVX512 untuk median filtering dengan jendela 7. Pembicaraan ini menimbulkan dua perasaan bagi saya: di satu sisi, keren , dan diklaim hampir 20x lebih cepat dari implementasi STL paling bodoh; Di sisi lain, dalam satu kali pass algoritme dari 16 sampel input, ternyata hanya 2 output, meskipun data input cukup untuk 10, dan beberapa detail implementasi membuat saya ingin mencoba memperbaikinya. Saya berpikir, berpikir, dan mendapatkan ide, lalu ide lain, lalu mencobanya "dalam perangkat lunak" dan menyadari bahwa saya punya sesuatu untuk dibagikan :) Jadi, artikel ini ternyata.
Implementasi dasar
Saya akan menjelaskan secara singkat bagaimana hal itu dilakukan oleh Bob (sebenarnya, menceritakan kembali singkat dari bagian yang sesuai dari ceritanya, bersama dengan gambarnya sendiri). Dia membuat primitif berikut menggunakan AVX512 (Saya akan menghilangkan primitif yang dijelaskan olehnya yang secara langsung sesuai dengan satu operasi AVX512):
rotate: putar elemen di register AVX-512 dalam lingkaran
shift with carry : memindahkan item dari register, mengganti item dari register kedua
in place shift with carry : seperti shift dengan carry, tetapi register input dilewatkan oleh referensi dan hasil shift tetap ada di dalamnya
bandingkan dengan pertukaran : penyortiran paralel hingga 8 pasang elemen dalam satu register
, , : perm 0..15, ; mask 1 «» . : , perm. vmin , vmax ́ . , .
, , . :
1) shift with carry, «» , «» (.. 0 0..6, 1 — 1..7 . .)
2) , 0 , 1 —
3) 7 , — 6 compare and exchange, . — — .
0
- , . , , ( , L2). , . AVX-512…
1
, — . 7 ; 6 !
, 6 r1-r6 , r0 r7? S[0..5], X, , S[3] .
X >= S[3], S[3] ,X <= S[2], S[2] S[3], S[2]S[2] < X < S[3], X S[3], , X. ,clamp(X, S[2], S[3])=>min(max(X, S[2]), S[3])!
:
«» 4 7- ( 0, 7, 2, 9) – X 4
6- 1..6 3..8 ( 0..7 8..15, )
6-
clamp 2 3 X[0] X[1], 2 3 X[2] X[3]
2x — 2 ( 6 5 , 7 — 6), clamp . : 1,86x . . ?
2
«» X . 6- ; 5 , 2 ( 3 ). — : S[0] <=> S[1], S[2] <=> S[3], S[4] <=> S[5]
2, . . , , !
— 2 , 2 . , : 1.06x. , .
3
- , 1, 6- .
, 4 ( ), 6; , 4- ?
2 , 4- . 6- : 2- Y 4- S, 2 3 ( Z). , min(Y[0], S[0]) => Z[0], ; max(Y[0], S[0]) Z[1]..Z[5] – . max(Y[1], S[3]) , min(Y[1], S[3]).
4- S[1], S[2], min/max. , 4 , 1 2 — 2 3 6- . , «» 4- S[1] S[2], — . , 2 , Y.
:
r1-r2 . .
— Y, r1-2, r5-6, r7-8, r11-12; permute 4 , Y r0-1, r4-5 . .
( ) «» ; r3-r6 r7-r10
max min Y[0]/S[0], Y[1]/S[3]
mask_permute Y S, S[1] S[2] ,
4
1 2, min/max X 8
, , , 2. — 1.64x , 2, 3 , .
; ( - permute; , - ), .
, :)
benchmark:
512 : 3.1-3.2 ; 7.3 , memcpy avx-512
50 : 2.8-2.9 ; 1.8 , memcpy (!)
.
5? , (disclaimer: — ).
16- 12 .
- 3 ( …)
1 , 4 ( 6 ) 4- — , . . 4 , 5 ; 8 .
2 , — 2 ; , .
3 , . , — , 12 . , «» — 24 , 12 .
9? 8 .
—
1 — 2 8- 4 , 4 ( 7 6 )
2 — , -
3 — , — 6- 2, 6- ( , ) , 8-.
, - . , https://github.com/tea/avx-median/. « », , -. , .
- , — . .
UPDATE
AVX2 . , , , , ( , 16 , ). , : 1.64x , .
Ternyata tidak semuanya hilang - langkah pengoptimalan pertama juga bisa diterapkan pada varian ini! Anda perlu mengumpulkan 32 tepi X, Anda perlu mengacaukan data untuk penyortiran, data yang diurutkan juga perlu diubah, dll., Tetapi terlepas dari semua gerakan ini, kami mendapat percepatan 1,27x kali.
Saya tidak mencoba melakukan langkah 2 dan 3, karena jelas akan lebih lambat. Sangat mungkin bahwa untuk kasus dengan, katakanlah, jendela 11, mereka akan bekerja dalam nilai plus (hanya jika seseorang membutuhkan filter 1D-median cepat dengan jendela besar - saya tidak tahu).