Application of distributed parallel computing for dynamic visual cryptography

Abstract

We consider one applied global optimization problem where a set of feasible solutions is discrete and very large. The goal is to find optimal perfect gratings, which can guarantee high quality and security of the visual cryptography method. A priori estimation techniques, such as branch and bound type methods, cannot be applied to exclude an essential part of elements from the feasible set. Thus, a full search is required to solve this global optimization problem exactly, which is very computationally demanding. A library of C++ templates is developed that allows its user to implement parallel master–slave algorithms for his/her application without any knowledge of parallel programming API (application programming interface). Design of the templates allows users to build a parallel solver using MPI (message passing interface) API or distributed computing application using BOINC (Berkeley open infrastructure for network computing) API from the same C/C++ code with implementation of application-specific tasks. We build parallel and distributed computing solvers for the considered optimization problem and present results of computational experiments using a computer cluster and BOINC project for volunteer computing. Heuristic methods are also considered as an alternative to the full search algorithm. Due to complicated conditions defining feasible solutions (perfect gratings), genetic algorithms cannot be used to solve this problem efficiently. We propose two memetic heuristic algorithms, when a basic stochastic or simplified full search algorithm is combined with a local search algorithm. Parallel heuristic algorithms are also proposed and implemented. The efficiency and accuracy of heuristics are investigated and results of experiments are presented.