Аннотация: В статье исследуются возможности конфигурирования цикла управления, т.е. определения распределения интервалов времени, необходимых для выполнения отдельных операций управления, по потокам исполнения, обеспечивающего реализуемость управления. Параллельное выполнение операций управления, там, где это допускается алгоритмом управления, в случае успешного конфигурирования цикла управления позволяет существенно снизить его длительность. Объектом исследования в данной статье являются системы управления с объектно-ориентированной архитектурой, предполагающей комбинированную вертикально-горизонтальную интеграцию функциональных блоков и модулей, распределяющих между собой все задачи управления. Данная архитектура реализуется посредством акторной инструментальной модели с использованием метапрограммирования. Такие системы управления наилучшим образом обеспечивают сокращение длительности цикла управления за счет параллельного выполнения вычислительных и других операций управления. Рассматриваются несколько подходов к конфигурированию цикла управления: без оптимизации, с комбинаторной оптимизацией по времени, с комбинаторной оптимизацией по ресурсам системы. Также достижение конфигурации, близкой к оптимальной, может быть достигнуто за счет использования адаптивного конфигурирования. Исследования показывают, что задача конфигурирования цикла системы управления имеет несколько вариантов решения. Практическое получение решения задачи конфигурирования в случае комбинаторной оптимизации связано с существенными сложностями, обусловленными высокой алгоритмической сложностью задачи и большим объемом потребных вычислений, быстро растущим по мере увеличения числа операций на этапах цикла управления. Возможным средством преодоления этих сложностей является использование стохастических методов, резко снижающих потребный объем вычислений. Также существенное снижение сложности задачи конфигурирования цикла системы управления можно добиться при использовании адаптивного конфигурирования, имеющего два варианта реализации. Первый вариант – это конфигурирование цикла системы управления в реальном времени. Второй вариант – это определение квазиоптимальной конфигурации на основе многократного конфигурирования с разными исходными данными и последующего сравнения получаемых результатов.

Ключевые слова: система управления, память-ориентированная, конфигурирование, оптимизация, цикл, элементы, операции управления, потоки исполнения, адаптивный, методы сортировки

Abstract: The paper investigates the possibilities of configuring the control cycle, i.e., determining the distribution of time intervals required for the execution of individual control operations across execution threads, which ensures the realizability of control. The object of research in this article are control systems with object-oriented architecture, assuming a combined vertical-horizontal integration of functional blocks and modules that distribute all control tasks among themselves. This architecture is realized by means of an actor instrumental model using metaprogramming. Such control systems are best at reducing control cycle time by performing computational and other control operations in parallel. Several approaches to control cycle configuration are considered: without optimization, with combinatorial optimization in time, with combinatorial optimization in system resources. Also, achieving a near-optimal configuration can be achieved by using adaptive configuration. Research shows that the control system cycle configuration problem has several solutions. Practical obtaining a solution to the configuration problem in the case of combinatorial optimization is associated with significant difficulties due to the high algorithmic complexity of the problem and a large amount of required computations, rapidly growing as the number of operations at the stages of the control cycle. A possible means of overcoming these difficulties is the use of stochastic methods, which sharply reduce the required amount of computation. Also, a significant reduction in the complexity of the task of configuring the control system cycle can be achieved by using adaptive configuration, which has two variants of realization. The first variant is the real-time configuration of the control system cycle. The second variant is the determination of quasi-optimal configuration on the basis of multiple configurations with different initial data and subsequent comparison of the obtained results.

Keywords: control operations, elements, loop, optimization, configuration, adaptive, sorting methods, execution threads, memory-oriented, control system

Аннотация: Предметом исследования является возможность распараллеливания циклов с зависимыми витками и телом, в котором порядок исполнения операторов строго определен. Такие циклы достаточно часто встречаются, например, в задачах численного моделирования методом частиц в ячейках, где на первой стадии исполнения тела цикла обрабатываются частицы и вычисляется некое определяемое ими поле, а на второй стадии решается дифференциальное уравнение в частных производных, зависимое от этого поля. Возможность распараллеливания тел таких циклов в настоящее время недостаточно освещена в литературе, данная тема является актуальной. Используются идеи применения прогнозирующих (авторегрессионных точечных) каналов в программной транзакционной памяти. Реализация построена с применением объектно-ориентированного программирования. Впервые сформулирована концепция сверхоптимистичных вычислений, то есть работы с прогнозирующими каналами в условиях частично транзакционной памяти. Предложены механизмы реализации частично транзакционной памяти, адаптированные к применению каналов. Предложена схема распараллеливания линейно исполняемых тел циклов (с зависимыми витками) на базе сверхоптимистичных вычислений, показана ее оправданность на примере решения задачи о моделировании пучка заряженных частиц в электростатической линзе.

Ключевые слова: сверхоптимистичные вычисления, предикция значений, программная транзакционная память, предицирующие каналы, численное моделирование, частицы в ячейках, прогностические зависимости, распараллеливание, дифференциальные уравнения, электростатическая линза

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

Аннотация: В данной работе рассматривается проблема применения предикции в классическом и параллельном программировании задач математического моделирования, основанных на численном интегрировании дифференциальных уравнений в частных производных. Предикция может использоваться для замены фрагментов математической модели более простыми приближенными соотношениями, для опережающего прогнозирования значений принимаемых в ходе параллельного счета данных, для прогнозирования времени исполнения фрагментов параллельной программы при решении вопроса о применении последовательного или параллельного алгоритма и при балансировке загрузки отдельных процессоров вычислительной системы. Для формализации видов предикторов и определения математических соотношений, позволяющих их вычислить, используются подходы и методы вычислительной математики (теории интерполяции и экстраполяции). Для определения программных реализаций предикторов используются подходы, характерные для инженерии параллельного программирования. Полученные результаты проверяются экспериментально. В работе впервые предложен новый вид технологических средств предикции для использовании в параллельном программировании – предикционно-решающие каналы. Предложены два вида каналов – авторегрессионные точечные и линейные (явные или неявные) коллективного решения. Изложены математические аспекты предикции в таких каналах, кратко описаны базовые средства программирования. Показано, что совмещение каналов со средствами предсказания данных упрощает программирование ряда алгоритмов, связанных с численным моделированием, и позволяет, в частности, осуществлять скрытые переходы от явных разностных схем к неявным, отличающихся большей устойчивостью счета, а также от последовательных алгоритмов счета к параллельным. На примере задачи численного интегрирования нестационарного уравнения теплопроводности показано, что адекватное применение каналов в ряде случаев позволяет ускорить расчет на многоядерных вычислительных системах.

Ключевые слова: ускорение счета, разностные схемы, дифференциальные уравнения, математическое моделирование, линейная экстраполяция, предсказание данных, каналы, параллельное программирование, аппроксимация разностных схем, персептроны

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

Аннотация: Для решения задачи оптимизации используемых ресурсов и планирования вычислений в настоящее время успешно используются различные метаэвристики, в частности, метод имитации отжига. Имитация отжига - метод последовательный, что затрудняет его распараллеливание, однако, в последнее время были разработаны различные способы распараллеливания с целью улучшения качества получаемых решений и времени работы алгоритма. Предметом исследования являются методы распараллеливания имитации отжига, в частности, метод независимых запусков с синхронизацией и асинхронный. В качестве примера реализации имитации отжига выбран метод с температурной схемой "тушения", как ниболее быстрый. Проведен аналитический обзор методов распараллеливания имитации отжига с выделением наиболее перспективных, для которых проведена серия вычислительных экспериментов с использованием. Научная новизна заключается в обнаружении новых зависимостей и тенденций, ранее не описанных в подобных исследованиях: для параллельной имитации отжига с синхронизацией поднят вопрос существования зависимости качества получаемого решения не только от количества вычисляющих устройств, но и от частоты обмена решениями. Для параллельнойй асинхронной имитации отжига прослеживается тенденция улучшения решений с увеличением количества вычисляющих устройств, тогда как для синхронной имитации отжига нельзя вести речь об однозначном улучшении и зависимости только от числа вычисляющих устройств.

Ключевые слова: имитация отжига, параллельный алгоритм, оптимизация, вычислительная система, оптимизация ресурсов, параллельные вычисления, распределение ресурсов, метаэвристика, методы распараллеливания, планирование вычислений

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