EFFECTIVE REALIZATION OF EXACT ALGORITHMS FOR SOLVING DISCRETE OPTIMIZATION PROBLEMS ON GRAPHIC ACCELERATORS
Journal Title: Современные информационные технологии и ИТ-образование - Year 2018, Vol 14, Issue 2
Abstract
Most of the problems of discrete optimization belong to the class of NP-complete problems. This means that algorithms that can find their exact solution, in general, can work with exponential complexity relative to the length of the input data. Thanks to progress, today there are technologies that have not yet been widely used to implement applied optimization methods. Among these technologies is GP GPU (General Purposed Graphical Processing Unit). The application of this technology to well-known algorithms can help to achieve greater efficiency. The purpose of this paper is to investigate the possibilities of using parallel computations on video cards to solve discrete optimization problems. The problem of a one-dimensional Boolean knapsack was chosen as the target problem. To solve the problem, methods for obtaining an exact solution are considered - the full search algorithm, which is the starting point in the study, and the "branches and boundaries" method, which allows to reduce the search by eliminating obviously inappropriate solutions. The algorithms considered are estimated in terms of the number of operations and execution time, implemented in a single-threaded configuration of the central processor, and then parallelized on a video card. Based on the results of these methods, a combined algorithm was created that combines both algorithms to achieve greater efficiency. For parallelizing the calculations on the graphics card, the CUDA technology is chosen. Algorithms are implemented in C. After the implementation of the algorithms, testing was carried out on various data sets and different configurations of the target platform. The results of experimental studies are presented, the acceleration of work is investigated with the use of parallel computations and a comparative analysis of the efficiency of the algorithms is carried out.
Authors and Affiliations
Michael Popov, Mikhail Posypkin
SIGNIFICANT COGNITIVE AND INFORMATION ASPECTS IN EDUCATION MANAGEMENT SYSTEM
In the article cognitive and information aspects which determine modern educational process using information technologies (IT) are described. Nowadays pedagogy considers various didactic approaches which make studying m...
PARTICULAR QUALITIES OF THE DEVELOPMENT AND APPLICATION OF FDM-TECHNOLOGY FOR CREATING AND PROTOTYPING 3D-OBJECTS
The article gives comparative analysis of additive technologies used in prototyping 3D-objects, and features of the FDM-technology are characterized. The parameters of the 3D printer using FDM-technology are described, a...
NEURAL NETWORK METHOD OF RESTORING AN INITIAL PROFILE OF THE SHOCK WAVE
In this paper, we apply neural network modeling to solve the inverse problem of mathematical physics with a system of nonlinear partial differential equations of hyperbolic type. In the problem, the initial conditions ar...
MODIFICATION OF THE ANT COLONY OPTIMIZATION FOR THE DEVELOPMENT OF SOFTWARE FOR SOLVING MULTI-CRITERION SUPPLY MANAGEMENT PROBLEMS
The article proposes three modifications of the Ant Colony Optimization, for finding multi-criterion solutions for the task of supplying spare parts for aviation equipment. A peculiarity of modifications is the weights m...
VECTORIZATION OF SMALL-SIZED SPECIAL-TYPE MATRICES MULTIPLICATION USING INSTRUCTIONS AVX-512
Modern software packages for supercomputer calculations require a large amount of computing resources. At the same time there are new hardware architectures that open up new opportunities for program code optimizing. The...