Все выпуски

Планирование вычислительных рабочих процессов, представленных направленными ациклическими графами (DAG), имеет ключевое значение для многих областей информатики, таких как облачные/edge задачи с распределенной рабочей нагрузкой и анализ данных. Сложность онлайнового планирования DAG усугубляется большим количеством вычислительных узлов, задержками передачи данных, неоднородностью (по типу и вычислительной мощности) исполнителей, ограничениями предшествования, накладываемыми DAG, и неравномерностью поступления задач. В данной статье представлен мультиагентный протокол локального голосования (MLVP) — новый подход, ориентированный на динамическое распределение нагрузки при планировании DAG в гетерогенных вычислительных средах, где исполнители представлены в виде агентов. MLVP использует протокол локального голосования для достижения эффективного распределения нагрузки, формулируя проблему как дифференцированное достижение консенсуса. Алгоритм вычисляет агрегированную метрику DAG для каждой пары исполнитель – узел на основе зависимостей между узлами, доступности узлов и производительности исполнителей. Баланс этих метрик как взвешенная сумма оптимизируется с помощью генетического алгоритма для вероятностного распределения задач, что позволяет добиться эффективного распределения рабочей нагрузки за счет обмена информацией и достижения консенсуса между исполнителями всей системы и, таким образом, улучшить время выполнения. Эффективность MLVP демонстрируется путем сравнения с современным алгоритмом планирования DAG и популярными эвристиками, такими как DONF, FIFO, Min-Min и Max-Min. Численное моделирование показывает, что MLVP достигает улучшения makepsan до 70% на определенных топологиях графов и среднего сокращения makepan на 23,99% по сравнению с DONF (современная эвристика планирования DAG) на случайно сгенерированном разнообразном наборе DAG. Примечательно, что масштабируемость алгоритма подтверждается ростом производительности при увеличении числа исполнителей и узлов графа.

Scheduling computational workflows represented by directed acyclic graphs (DAGs) is crucial in many areas of computer science, such as cloud/edge tasks with distributed workloads and data mining. The complexity of online DAG scheduling is compounded by the large number of computational nodes, data transfer delays, heterogeneity (by type and processing power) of executors, precedence constraints imposed by DAG, and the nonuniform arrival of tasks. This paper introduces the Multi-Agent Local Voting Protocol (MLVP), a novel approach focused on dynamic load balancing for DAG scheduling in heterogeneous computing environments, where executors are represented as agents. The MLVP employs a local voting protocol to achieve effective load distribution by formulating the problem as a differentiated consensus achievement. The algorithm calculates an aggregated DAG metric for each executor-node pair based on node dependencies, node availability, and executor performance. The balance of these metrics as a weighted sum is optimized using a genetic algorithm to assign tasks probabilistically, achieving efficient workload distribution via information sharing and reaching consensus among the executors across the system and thus improving makespan. The effectiveness of the MLVP is demonstrated through comparisons with the state-of-the-art DAG scheduling algorithm and popular heuristics such as DONF, FIFO, Min- Min, and Max-Min. Numerical simulations show that MLVP achieves makepsan improvements of up to 70% on specific graph topologies and an average makespan reduction of 23.99% over DONF (state-of-the-art DAG scheduling heuristic) across randomly generated diverse set of DAGs. Notably, the algorithm’s scalability is evidenced by enhanced performance with increasing numbers of executors and graph nodes.

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

The article presents updated technologies for solving two classes of linear resource allocation problems with dynamically changing characteristics of situational management systems and awareness of experts (and/or trained robots). The search for solutions is carried out in an interactive mode of computational experiment using updatable knowledge systems about problems considered as constructive objects (in accordance with the methodology of formalization of knowledge about programmable problems created in the theory of S-symbols). The technologies are focused on implementation in the form of Internet services. The first class includes resource allocation problems solved by the method of targeted solution movement. The second is the problems of allocating a single resource in hierarchical systems, taking into account the priorities of expense items, which can be solved (depending on the specified mandatory and orienting requirements for the solution) either by the interval method of allocation (with input data and result represented by numerical segments), or by the targeted solution movement method. The problem statements are determined by requirements for solutions and specifications of their applicability, which are set by an expert based on the results of the portraits of the target and achieved situations analysis. Unlike well-known methods for solving resource allocation problems as linear programming problems, the method of targeted solution movement is insensitive to small data changes and allows to find feasible solutions when the constraint system is incompatible. In single-resource allocation technologies, the segmented representation of data and results allows a more adequate (compared to a point representation) reflection of the state of system resource space and increases the practical applicability of solutions. The technologies discussed in the article are programmatically implemented and used to solve the problems of resource basement for decisions, budget design taking into account the priorities of expense items, etc. The technology of allocating a single resource is implemented in the form of an existing online cost planning service. The methodological consistency of the technologies is confirmed by the results of comparison with known technologies for solving the problems under consideration.

This paper is devoted to the problem of edge criticality identification and ranking in complex networks, which is a part of a modern research direction in the novel network science. The diffusion importance belongs to the set of acknowledged methods that help to identify the significant connections in the graph that are critical to retaining structural integrity. In the present work, we develop the Iterative Diffusion Importance algorithm that is based on the re-estimation of critical topological features at each step of the graph deconstruction. The Iterative Diffusion Importance has been compared with methods such as diffusion importance and degree product, which are two very well-known benchmark algorithms. As for benchmark networks, we tested the Iterative Diffusion Importance on three standard networks, such as Zachary’s Karate Club, the American Football Network, and the Dolphins Network, which are often used for algorithm efficiency evaluation and are different in size and density. Also, we proposed a new benchmark network representing the airplane communication between Japan and the US. The numerical experiment on finding the ranking of critical edges and the following network decomposition demonstrated that the proposed Iterative Diffusion Importance exceeds the conventional diffusion importance by the efficiency for 2–35% depending on the network complexity, the number of nodes, and the number of edges. The only drawback of the Iterative Diffusion Importance is an increase in computation complexity and hencely in the runtime, but this drawback can be easily compensated for by the preliminary planning of the network deconstruction or protection and by reducing the re-evaluation frequency of the iterative process.

This paper is devoted to the problem of edge criticality identification and ranking in complex networks, which is a part of a modern research direction in the novel network science. The diffusion importance belongs to the set of acknowledged methods that help to identify the significant connections in the graph that are critical to retaining structural integrity. In the present work, we develop the Iterative Diffusion Importance algorithm that is based on the re-estimation of critical topological features at each step of the graph deconstruction. The Iterative Diffusion Importance has been compared with methods such as diffusion importance and degree product, which are two very well-known benchmark algorithms. As for benchmark networks, we tested the Iterative Diffusion Importance on three standard networks, such as Zachary’s Karate Club, the American Football Network, and the Dolphins Network, which are often used for algorithm efficiency evaluation and are different in size and density. Also, we proposed a new benchmark network representing the airplane communication between Japan and the US. The numerical experiment on finding the ranking of critical edges and the following network decomposition demonstrated that the proposed Iterative Diffusion Importance exceeds the conventional diffusion importance by the efficiency for 2–35% depending on the network complexity, the number of nodes, and the number of edges. The only drawback of the Iterative Diffusion Importance is an increase in computation complexity and hencely in the runtime, but this drawback can be easily compensated for by the preliminary planning of the network deconstruction or protection and by reducing the re-evaluation frequency of the iterative process.

Получены численные решения двумерного реакционно-диффузионного уравнения с нелокальной нелинейностью, описывающие формирование диссипативной структуры. Рассмотрены структуры, возникающие из начальных распределений с одним и несколькими центрами локализации. При изменении параметров уравнения решения описывают формирование расширяющихся кольцевых структур. Рассмотрены особенности образования и взаимодействия расширяющихся кольцеобразных структур в зависимости от характера нелокального взаимодействия.

Numerical solutions for the two-dimensional reaction-diffusion equation with nonlocal nonlinearity are obtained. The solutions reveal formation of dissipative structures. Structures arising from initial distributions with one and several centers of localization are considered. Formation of extending circular structures is shown. Peculiarities of formation and interaction of extending circular structures depending on  nonlocal interaction are considered.

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

In this paper we present a mathematical model and numerical results on a propagation of the combustion front of the SHS compound, where the rate of chemical reaction at each point of the SHS sample is determined by solving the problem of diffusion and chemical reaction in the reaction cell. We obtained the dependence of the combustion front on the size of the average element of a heterogeneous structure with different values of the diffusion intensity. These dependences agree qualitatively with the experimental data. We studied the effect of activation energy for diffusion on the propagation velocity of combustion front. It is revealed the propagation of the combustion front transforms to an oscillatory regime at increase in activation energy of diffusion. A transition boundary of the combustion front propagation from the steady-state regime to the oscillatory one is defined.

Дана постановка задачи управления движения тела в вязкой жидкости. Движение тела индуцируется перемещением внутренних материальных точек. На основе численного решения уравнений движения тела и гидродинамических уравнений получены аппроксимирующие зависимости для вязких сил. С применением аппроксимаций решается задача оптимального управления движением тела по заданной траектории с применением гибридного генетического алгоритма. Установлена возможность направленного движения тела под действием возвратно-поступательного движения внутренней точки. Оптимальное управление направлением движения осуществляется движением другой внутренней точки по круговой траектории с переменной скоростью.

Statement of a problem of management of movement of a body in a viscous liquid is given. Movement bodies it is induced by moving of internal material points. On a basis the numerical decision of the equations of movement of a body and the hydrodynamic equations approximating dependencies for viscous forces are received. With application approximations the problem of optimum control of body movement dares on the set trajectory with application of hybrid genetic algorithm. Possibility of the directed movement of a body under action is established back and forth motion of an internal point. Optimum control movement direction it is carried out by motion of other internal point on circular trajectory with variable speed.

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

In the paper we construct the adjoint problem for the explicit and implicit parabolic quazi-linear grid boundary-value problems with one spatial variable; the coefficients of the problems depend on the solution at the same time and earlier times. Dependence on the history of the solution is via the state vector; its evolution is described by the differential equation. Many models of diffusion mass transport are reduced to such boundary-value problems. Having solutions to the direct and adjoint problems, one can obtain the exact value of the gradient of a functional in the space of parameters the problem also depends on. We present solving algorithms, including the parallel one.

Проведено математическое моделирование естественной конвекции и теплового излучения в квадратной замкнутой воздушной полости с изотермическими вертикальными стенками при наличии локального источника энергии постоянной температуры. Математическая модель построена в безразмерных переменных «функция тока – завихренность скорости – температура» в приближении Буссинеска и с учетом диатермичности воздушной среды. Получены распределения изолиний функции тока и температуры в широком диапазоне изменения определяющих параметров: число Рэлея $10^3 \leqslant Ra \leqslant 10^6$, приведенная степень черноты ограждающих стенок $0\leqslant\varepsilon < 1$, отношение длины источника энергии к размеру полости $0.2\leqslant l/L\leqslant0.6$ и время $0\leqslantτ\leqslant 100$. Установлены корреляционные соотношения для интегрального коэффициента теплообмена в зависимости от $Ra$, $ε$ и $l/L$.

Mathematical simulation of natural convection and surface radiation in a square air enclosure having isothermal vertical walls with a local heat source of constant temperature has been carried out. Mathematical model has been formulated on the basis of the dimensionless variables such as stream function, vorticity and temperature by using the Boussinesq approximation and diathermancy of air. Distributions of streamlines and isotherms reflecting an effect of Rayleigh number $ 10^3 \leqslant Ra \leqslant 10^6 $, surface emissivity $0 \leqslant ε < 1$, ratio between the length of heat source and the size of enclosure $0.2 \leqslant l/L \leqslant 0.6$ and dimensionless time $0 \leqslant τ \leqslant 100$ on fluid flow and heat transfer have been obtained. Correlations for the average heat transfer coefficient in dependence on $Ra$, $ε$ and $l/L$ have been ascertained.

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

This article represents numerical simulation technique for determining effective spectral electromagnetic properties (effective electrical conductivity and relative dielectric permittivity) of saturated porous media. Information about these properties is vastly applied during the interpretation of petrophysical exploration data of boreholes and studying of rock core samples. The main feature of the present paper consists in the fact, that it involves three-dimensional saturated digital rock models, which were constructed based on the combined data considering microscopic structure of the porous media and the information about capillary equilibrium of oil-water mixture in pores. Data considering microscopic structure of the model are obtained by means of X-ray microscopic tomography. Information about distributions of saturating fluids is based on hydrodynamic simulations with density functional technique. In order to determine electromagnetic properties of the numerical model time-domain Fourier transform of Maxwell equations is considered. In low frequency approximation the problem can be reduced to solving elliptic equation for the distribution of complex electric potential. Finite difference approximation is based on discretization of the model with homogeneous isotropic orthogonal grid. This discretization implies that each computational cell contains exclusively one medium: water, oil or rock. In order to obtain suitable numerical model the distributions of saturating components is segmented. Such kind of modification enables avoiding usage of heterogeneous grids and disregards influence on the results of simulations of the additional techniques, required in order to determine properties of cells, filled with mixture of media. Corresponding system of differential equations is solved by means of biconjugate gradient stabilized method with multigrid preconditioner. Based on the results of complex electric potential computations average values of electrical conductivity and relative dielectric permittivity is calculated. For the sake of simplicity, this paper considers exclusively simulations with no spectral dependence of conductivities and permittivities of model components. The results of numerical simulations of spectral dependence of effective characteristics of heterogeneously saturated porous media (electrical conductivity and relative dielectric permittivity) in broad range of frequencies and multiple water saturations are represented in figures and table. Efficiency of the presented approach for determining spectral electrical properties of saturated rocks is discussed in conclusion.

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

The different types of the reduced equations are known in the dynamics a heavy rigid body with a fixed point. Since the Euler−Poisson’s equations admit the three first integrals, then for the first approach the obtaining new forms of equations are usually based on these integrals. The system of six scalar equations can be transformed to a third-order system with them. However, in indicated approach the reduced system will have a feature as in the form of radical expressions a relatively the components of the angular velocity vector. This fact prevents the effective the effective application of numerical and asymptotic methods of solutions research. In the second approach the different types of variables in a problem are used: Euler’s angles, Hamilton’s variables and other variables. In this approach the Euler−Poisson’s equations are reduced to either the system of second-order differential equations, or the system for which the special methods are effective. In the article the method of finding the reduced system based on the introduction of an auxiliary variable is applied. This variable characterizes the mixed product of the angular momentum vector, the vector of vertical and the unit vector barycentric axis of the body. The system of four differential equations, two of which are linear differential equations was obtained. This system has no analog and does not contain the features that allows to apply to it the analytical and numerical methods. Received form of equations is applied for the analysis of a special class of solutions in the case when the center of mass of the body belongs to the barycentric axis. The variant in which the sum of the squares of the two components of the angular momentum vector with respect to not barycentric axes is constant. It is proved that this variant exists only in the Steklov’s solution. The obtained form of Euler−Poisson’s equations can be used to the investigation of the conditions of existence of other classes of solutions. Certain perspectives obtained equations consists a record of all solutions for which the center of mass is on barycentric axis in the variables of this article. It allows to carry out a classification solutions of Euler−Poisson’s equations depending on the order of invariant relations. Since the equations system specified in the article has no singularities, it can be considered in computer modeling using numerical methods.