Все выпуски

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

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

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

This work investigates the application of the Chinese Remainder Theorem (CRT) to improve the efficiency of computations involving large integers in high-performance computing tasks. The relevance of this study arises from the fact that a number of problems in theoretical physics, numerical simulation, and exhaustive search algorithms require integers whose bit length significantly exceeds the capabilities of standard machine data types. This necessitates the use of arbitraryprecision arithmetic and leads to substantial computational overhead. Traditional representations of large integers as sequences of machine words scale poorly and do not efficiently utilize the architecture of graphics processing units (GPUs).

The proposed approach is based on representing integers in a residue number system defined by a set of pairwise coprime moduli. Such a decomposition replaces operations on multi-byte integers with independent modular operations on arrays of residues, enabling natural parallelization. Arithmetic operations including addition, subtraction, and multiplication are performed componentwise within the modular system, while reconstruction of the original integer is carried out using algorithms based on the extended Euclidean algorithm. It is shown that in sequential computations the proposed method does not provide a significant advantage over classical arbitrary-precision arithmetic; however, when implemented on GPUs, a substantial performance gain is achieved due to massive parallelism and independence of operations across moduli. An additional advantage is the reduced risk of overflow and more efficient memory access organization enabled by the use of fixed-width integers.

Thus, the use of the CRT constitutes an effective tool for implementing multipoint computations with large integers in supercomputing systems and can be applied to numerical simulation, cryptography, and exhaustive search algorithms requiring high performance and scalability.

The Lipschitz continuous property has been used for a long time to solve the global optimization problem and continues to be used. Here we can mention the work of Piyavskii, Yevtushenko, Strongin, Shubert, Sergeyev, Kvasov and others. Most papers assume a priori knowledge of the Lipschitz constant, but the derivation of this constant is a separate problem. Further still, we must prove that an objective function is really Lipschitz, and it is a complicated problem too. In the case where the Lipschitz continuity is established, Strongin proposed an algorithm for global optimization of a satisfying Lipschitz condition on a compact interval function without any a priori knowledge of the Lipschitz estimate. The algorithm not only finds a global extremum, but it determines the Lipschitz estimate too. It is known that every function that satisfies the Lipchitz condition on a compact convex set is uniformly continuous, but the reverse is not always true. However, there exist models (Arutyunova, Dulliev, Zabotin) whose study requires a minimization of the continuous but definitely not Lipschitz function. One of the algorithms for solving such a problem was proposed by R. J. Vanderbei. In his work he introduced some generalization of the Lipchitz property named $\varepsilon$-Lipchitz and proved that a function defined on a compact convex set is uniformly continuous if and only if it satisfies the $\varepsilon$-Lipchitz condition. The above-mentioned property allowed him to extend Piyavskii’s method. However, Vanderbei assumed that for a given value of $\varepsilon$ it is possible to obtain an associate Lipschitz $\varepsilon$-constant, which is a very difficult problem. Thus, there is a need to construct, for a function continuous on a compact convex domain, a global optimization algorithm which works in some way like Strongin’s algorithm, i.e., without any a priori knowledge of the Lipschitz $\varepsilon$-constant. In this paper we propose an extension of Strongin’s global optimization algorithm to a function continuous on a compact interval using the $\varepsilon$-Lipchitz conception, prove its convergence and solve some numerical examples using the software that implements the developed method.

The Lipschitz continuous property has been used for a long time to solve the global optimization problem and continues to be used. Here we can mention the work of Piyavskii, Yevtushenko, Strongin, Shubert, Sergeyev, Kvasov and others. Most papers assume a priori knowledge of the Lipschitz constant, but the derivation of this constant is a separate problem. Further still, we must prove that an objective function is really Lipschitz, and it is a complicated problem too. In the case where the Lipschitz continuity is established, Strongin proposed an algorithm for global optimization of a satisfying Lipschitz condition on a compact interval function without any a priori knowledge of the Lipschitz estimate. The algorithm not only finds a global extremum, but it determines the Lipschitz estimate too. It is known that every function that satisfies the Lipchitz condition on a compact convex set is uniformly continuous, but the reverse is not always true. However, there exist models (Arutyunova, Dulliev, Zabotin) whose study requires a minimization of the continuous but definitely not Lipschitz function. One of the algorithms for solving such a problem was proposed by R. J. Vanderbei. In his work he introduced some generalization of the Lipchitz property named $\varepsilon$-Lipchitz and proved that a function defined on a compact convex set is uniformly continuous if and only if it satisfies the $\varepsilon$-Lipchitz condition. The above-mentioned property allowed him to extend Piyavskii’s method. However, Vanderbei assumed that for a given value of $\varepsilon$ it is possible to obtain an associate Lipschitz $\varepsilon$-constant, which is a very difficult problem. Thus, there is a need to construct, for a function continuous on a compact convex domain, a global optimization algorithm which works in some way like Strongin’s algorithm, i.e., without any a priori knowledge of the Lipschitz $\varepsilon$-constant. In this paper we propose an extension of Strongin’s global optimization algorithm to a function continuous on a compact interval using the $\varepsilon$-Lipchitz conception, prove its convergence and solve some numerical examples using the software that implements the developed method.

Молекулярно-динамические методы, использующие силовое поле ReaxFF, позволяют получать достаточно хорошие результаты при моделировании больших многокомпонентных химически-реактивных систем. Здесь представлены алгоритм поиска оптимальных параметров силового поля ReaxFF для произвольных химических систем, а также его реализация. Метод основан на способе многомерного поиска глобального минимума, предложенном Р. Г. Стронгиным. Алгоритм хорошо масштабируемый и хорошо подходит для работы на параллельных вычислительных кластерах.

Molecular dynamic methods that use ReaxFF force field allow one to obtain sufficiently good results in simulating large multicomponent chemically reactive systems. Here is represented an algorithm of searching optimal parameters of molecular-dynamic force field ReaxFF for arbitrary chemical systems and its implementation. The method is based on the multidimensional technique of global minimum search suggested by R.G. Strongin. It has good scalability useful for running on distributed parallel computers.