Все выпуски

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

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

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

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