Abstract: The subject of research is the possibility of parallelizing loops with dependent iterations and a body, in which the order of execution of operators is strictly defined. Such loops are quite often encountered, for example, in problems of numerical simulation by the method of particles in cells, where at the first stage of the cycle body execution the particles are processed and a certain field determined by them is calculated, and at the second stage a partial differential equation dependent on this field is solved. The possibility of parallelizing the bodies of such cycles is currently insufficiently covered in the literature, this topic is relevant. The ideas of applying predictive (autoregressive point) channels in the programmed transactional memory are used. The implementation is built using object-oriented programming. For the first time, the concept of super-optimistic computing was formulated, that is, working with predictive channels in conditions of partially transactional memory. Mechanisms for the implementation of partially transactional memory, adapted to the use of channels, are proposed. A scheme for parallelizing linearly executed cycle bodies (with dependent loops) on the basis of super-optimistic calculations is proposed, its justification is shown on the example of solving the problem of modeling a beam of charged particles in an electrostatic lens.

Keywords: predictive dependencies, particles in cells, numerical simulation, predictive funnels, software transactional memory, value prediction, super-optimistic evaluations, parallelizing, partial differential equations, electrostatic lens

References:
Voevodin, V.V. Parallel'nye vychisleniya / V.V. Voevodin, Vl.V. Voevodin.— SPb.: BKhV-Peterburg, 2002. — 608 s.
Khokni R., Istvud Dzh. Chislennoe modelirovanie metodom chastits. — M.: Mir, 1987. — 640 s.
Pekunov V. V. Novye metody parallel'nogo modelirovaniya rasprostraneniya zagryazneniy v okrestnosti promyshlennykh i munitsipal'nykh ob'ektov // Dis. dokt. tekh. nauk.-Ivanovo, 2009.-274 s.
Chernyak, L. Tranzaktsionnaya pamyat'-pervye shagi / L. Chernyak // Otkrytye sistemy. SUBD. — 2007.— ¹4.— S.12-15.
Pekunov V.V. Preditsiruyushchie kanaly v parallel'nom programmirovanii: vozmozhnoe primenenie v matematicheskom modelirovanii protsessov v sploshnykh sredakh // Programmnye sistemy i vychislitel'nye metody. – 2019. – ¹ 3. – S. 37-48. DOI: 10.7256/2454-0714.2019.3.30393 URL: https://nbpublish.com/ library_read_article.php?id=30393
Salil Pant and Greg Byrd. A case for using value prediction to improve performance of transactional memory. In TRANSACT ’09: 4th Workshop on Transactional Computing, feb 2009. URL: http://transact09.cs.wa

Abstract: In this paper, the author considers the problem of applying prediction in classical and parallel programming of mathematical modeling problems based on the numerical integration of partial differential equations. Prediction can be used to replace fragments of a mathematical model with simpler approximate relations, to anticipate the values received during parallel counting, to predict the execution time of fragments of a parallel program when deciding whether to use a sequential or parallel algorithm and when balancing the load of individual processors of a computing system. To formalize the types of predictors and determine the mathematical relationships that allow them to be calculated, the approaches and methods of computational mathematics (theory of interpolation and extrapolation) are used. To determine the software implementations of predictors, approaches that are characteristic of parallel programming engineering are used. The results are verified experimentally. For the first time, a new type of technological means of prediction for use in parallel programming is proposed - prediction-solving channels. Two types of channels are proposed - autoregressive point and linear (explicit or implicit) collective solutions. The mathematical aspects of prediction in such channels are described, basic programming tools are briefly described. It is shown that combining channels with data prediction tools simplifies the programming of a number of algorithms related to numerical modeling, and allows, in particular, hidden transitions from explicit difference schemes to implicit ones, which are more stable in counting, as well as from sequential counting algorithms to parallel ones. Using the example of the problem of numerical integration of the non-stationary heat equation, it is shown that the adequate use of channels in some cases allows you to speed up the calculation on multi-core computing systems.

Keywords: finite difference scheme's approximation, calculation speedup, finite difference schemes, partial differential equations, mathematical modelling, data prediction, linear extrapolation, channels, parallel programming, perceptrons

References:
Pekunov V.V. Metasloy modelirovaniya algoritma, dannykh i funktsional'nykh kharakteristik posledovatel'nykh i parallel'nykh programm // Informatsionnye tekhnologii.-2011.-¹6.-S.51-56.
Pekunov V. V. Novye metody parallel'nogo modelirovaniya rasprostraneniya zagryazneniy v okrestnosti promyshlennykh i munitsipal'nykh ob'ektov // Dis. dokt. tekh. nauk.-Ivanovo, 2009.-274 s.
Popova A. I. Primenenie adaptivnykh algoritmov v chislennom metode prostranstvennoy i vremennoy ekstrapolyatsii mezometeorologicheskikh poley // Diss. kand. fiz.-mat. nauk. – Surgut, 2006. – 147 s.
Pekunov V.V. Primenenie prediktsii pri parallel'noy obrabotke tsepochek predikatov v regulyarno-logicheskikh vyrazheniyakh // Kibernetika i programmirovanie. – 2018. – ¹ 6. – S. 48-55. DOI: 10.25136/2306-4196.2018.6.27986 URL: https://nbpublish.com/library_read_article.php?id=27986
Dlib C++ Library. – URL: http://dlib.net
Abadi M., Agarwal A., Barham P. et al. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. Software available from tensorflo

Abstract: various metaheuristics, such as method of simulated annealing, are currently used for solving the tasks of resource usage optimization and computation scheduling. Simulated annealing is a serial method and it is difficult to parallelize it. However, different methods of parallelization have been developed recently in order to improve the quality of the solutions and the time of algorithm execution. The subjects of the study are the methods of parallelization for annealing simulation, in particular, the method of independent starts with and without synchronization. As an example of simulated annealing implementation the authors select the method with thermal scheme “quenching” as the fastest one. The article shows analytical review of simulated annealing parallelization, with a selection of the most promising methods, for which a series of computational experiments was carried out. Scientific novelty of the work is in the discovery of new dependencies and trends that were not described previously in similar studies. In discussing the parallelized annealing simulation with synchronization the authors raise a question of the existence of the dependence of the quality of the solutions with not only the number of computing devices, but also with the frequency of the solutions exchanges. For asynchronous parallel simulated annealing the article shows a tendency to solutions improvement with the increase of the number of computing devices, while for synchronous simulated annealing a similar dependence was not found.

Keywords: simulated annealing, parallel algorithm, optimization, computational system, resource optimization, parallel computing, resource assigning, metaheuristics, parallelization techniques, computation scheduling

References:
MsGee A. A. and Markarian M. D. Optimum Allocation of Research (Engineering Manpower within a Multi-Project Organizational Structures). IRE Trans. Engng. Manag., v. 9, No. 3, 1962.
Levy F. E., Thompson G., Wiest J. Multiship, Multishop, Workloadsmoothing Program, Naval Research, Logistics Quarterly, v. 9, No. 1, 1962.
Fey S.F. Least Cost Estimating and Scheduling with Limited Resources. Abstract. Recent Advances Math. Programm, 1963.
Barskiy A.B. Parallel'nye protsessy v vychislitel'nykh sistemakh: planirovanie i organizatsiya. – M.: Radio i svyaz', 1990.
F. Busetti, Simulated annealing overview. 2003. (http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary;jsessionid=9F958F3AD8ACB341A84315A737883592?doi=10.1.1.66.5018)
L.Ingber, Simulated annealing: practice versus theory.1993. (http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary?doi=10.1.1.15.1046)
Crainic T.G., Toulouse M. Parallel Metaheuristics. In T. G. Crainic and G. Laporte, editors, Fleet Management and Logistics, pages