Parallelization of Metaheuristics for the Optimization of Permuted Perceptron Problem
Keywords:
Permuted perceptron problem, ILS, Tabu Search, simulated annealing, metaheuristicsAbstract
Parallel computing has found a mainstream backing in graphics processing units (GPUs).These resources have enormous processing capacity, are energy efficient, and are broadly available, unlike grids. Since the advent of CUDA (Compute Unified Device Architecture) developed by NVIDIA that permits GPU programming in C, C++ language, GPUs are now being used in a variety of fields, including scientific computing. This thesis focuses on the optimization of the solution of a NPcomplete problem called Permuted Perceptron Problem based on cryptographic identification scheme, which particularly meets the requirements for resource restricted devices like smart cards. We will study about GPU optimization techniques for parallel metaheuristics in order to achieve an efficient solution.
References
Pointcheval D. A new identification scheme based on the perceptron problem. Lecture Notes in Computer Science International Conference on the Theory and Applications of Cryptographic Techniques. 1995:319-28. doi: 10.1007/3-540-49264-X_26.
Essaid M, Idoumghar L, Lepagnot J, Brévilliers M. GPU parallelization strategies for metaheuristics: a survey. Int J Parallel Emergent Distrib Syst. 2019;34(5):497-522. doi: 10.1080/17445760.2018.1428969.
Knudsen LR, Meier W. Cryptanalysis of an identification scheme based on the permuted perceptron problem. Lecture Notes in Computer Science International Conference on the Theory and Applications of Cryptographic Techniques. 1999:363-74. doi: 10.1007/3-540-48910-X_25.
Clark JA, Jacob JL. Fault injection and a timing channel on an analysis technique. Lecture Notes in Computer Science International Conference on the Theory and Applications of Cryptographic Techniques. 2002:181-96. doi: 10.1007/3-540-46035-7_12.
Van Luong T, Melab N, Talbi E-G. Local search algorithms on graphics processing units. a case study: the permutation perceptron problem. Lecture Notes in Computer Science. 2010:264-75. doi: 10.1007/978-3-642-12139-5_23.
