Все выпуски

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