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
Keywords
Related Articles
- EP ID EP519313
- DOI 10.25559/SITITO.14.201802.408-418
- Views 99
- Downloads 0
DEVELOPMENT AND IMPLEMENTATION OF A CONCEPTUAL INFORMATION SYSTEM “BUSINESS INTELLIGENCE” MODEL OF A PHARMACEUTICAL COMPANY'S “SAIDAL” COMMERCIAL SERVICE
The Dynamic nature of modern business operations, the constant growth and the complexity of the data flows companies to turn to the most advanced data processing means, one of these tools is the Business Intelligence (BI...
PROGRAMS FOR ATRIBUTION AND FOR VIEWING PHOTOCOPIES OF A COLLECTION OF PORTRAITS
The article deals with the problem of digitization and attribution of portraits in archive collections. The principal example is the collection of portraits from the Moscow Society of Naturalists archives. Special softwa...
METHODS OF CREATING DIGITAL TWINS BASED ON NEURAL NETWORK MODELING
It is assumed that by 2021, about half of the companies will use digital counterparts of different levels. The simplest digital twin models may not use machine learning, but the models using machine learning algorithms w...
NEURAL NETWORK MODEL OF PREDICTING THE RISK GROUP FOR THE ACCESSION OF STUDENTS OF THE FIRST COURSE
Many Russian universities face the problem when applicants who successfully passed a single state examination in core disciplines become outsiders as a result of the first academic period. Especially it concerns the spec...
CLUSTERING MODEL OF LOW-STRUCTURED TEXT DATA
The article proposes a clustering model for collections of news text messages, as well as the corresponding bubble trap clustering algorithm. The essence of the proposed approach is to divide the entire vector space of t...