Geodesic
An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 4 (2015) no. 3, pp. 67-84

Voir la notice de l'article provenant de la source Math-Net.Ru

In this work we assess performance of CPU and GPU implementations of some widely-used cryptanalytic combinatorial algorithms. In particular, we analyze obstacles for effective GPU im-plementation of “smart” combinatorial algorithms. Next, to alleviate performance problems arising from inefficient processing of conditional expressions in SIMD-devices we devise some special control flow graph transformation techniques. Finally, we demonstrate that contemporary GPU's memory access schemes are incompatible with typical memory access patterns of “smart” combinatorial algorithms studied. We use DES and A5/1 cryptographic functions as test cases.
Keywords: GPU, CUDA, cryptoanalysis, DPLL, SAT, SIMD. 
@article{VYURV_2015_4_3_a5,
     author = {V. G. Bulavintsev},
     title = {An evaluation of {CPU} vs. {GPU} performance of some combinatorial algorithms for cryptoanalysis},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {67--84},
     publisher = {mathdoc},
     volume = {4},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a5/}
}
TY  - JOUR
AU  - V. G. Bulavintsev
TI  - An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2015
SP  - 67
EP  - 84
VL  - 4
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a5/
LA  - ru
ID  - VYURV_2015_4_3_a5
ER  - 
%0 Journal Article
%A V. G. Bulavintsev
%T An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2015
%P 67-84
%V 4
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a5/
%G ru
%F VYURV_2015_4_3_a5
V. G. Bulavintsev. An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 4 (2015) no. 3, pp. 67-84. http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a5/