ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ

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

The paper covers an intelligent support system that allows to describe and construct solutions to various scientific problems. In this study, in particular, we consider geophysical problems. This system is being developed at the Institute of Computational Mathematics and Mathematical Geophysics of the Russian Academy of Sciences (ICMMG SB RAS) and Institute of Informatics System of the Russian Academy of Sciences (IIS SB RAS). The system contains a knowledge base, the core of which is a set of several interconnected ontologies such as the ontology of supercomputer architectures, the ontology of algorithms and methods. Ontology can be viewed as a set of concepts and how those concepts are linked. As the result, the authors present an ontological description of two geophysical problems via the means of the intelligent support system: 1) the seismic wavefield simulation and 2) the reconstruction of a seismic image through pre-stack time or depth migration. For a better visual understanding of the system described and the results obtained, the paper also contains several schematic diagrams and images.

This paper is concerned with implementation of wave tomography algorithms on modern SIMD CPU and GPU computing platforms. The field of wave tomography, which is currently under development, requires powerful computing resources. Main applications of wave tomography are medical imaging, nondestructive testing, seismic studies. Practical applications depend on computing hardware. Tomographic image reconstruction via wave tomography technique involves solving coefficient inverse problems for the wave equation. Such problems can be solved using iterative gradient-based methods, which rely on repeated numerical simulation of wave propagation process. In this study, finite-difference time-domain (FDTD) method is employed for wave simulation. This paper discusses software implementation of the algorithms and compares the performance of various computing devices: multi-core Intel and ARM-based CPUs, NVidia graphics processors.

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

Выделенные свойства циклов DFS-базиса блока карты простого графа позволили составить математическую модель вычисления циклов ячеек карты графа. По данной модели предложен практический алгоритм вычисления циклов ячеек карты графа. Алгоритм имеет квадратическую сложность относительно числа вершин в графе.

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

В статье представлен параллельный алгоритм валидации решений задач линейного программирования. Идея метода состоит в том, чтобы генерировать регулярный набор точек на гиперсфере малого радиуса, центрированной в точке тестируемого решения. Целевая функция вычисляется для каждой точки валидационного множества, принадлежащей допустимой области. Если все полученные значения меньше или равны значению целевой функции в точке, проверяемой как решение, то эта точка считается корректным решением. Параллельная реализация алгоритма VaLiPro выполнена на языке C++ с использованием параллельного BSF-каркаса, инкапсулирующего в проблемно-независимой части своего кода все аспекты, связанные с распараллеливанием программы на базе библиотеки MPI. Приводятся результаты масштабных вычислительных экспериментов на кластерной вычислительной системе, подтверждающие эффективность предложенного подхода.

Системы SAPFOR и DVM были спроектированы и предназначены для упрощения разработки параллельных программ научно-технических расчетов. Главной целью системы SAPFOR является автоматизация процесса отображения последовательных программ на параллельные архитектуры в модели DVMH. В некоторых случаях пользователь системы SAPFOR может рассчитывать на полностью автоматическое распараллеливание, если программа была написана или приведена к потенциально параллельному виду. DVMH модель представляет собой расширение стандартных языков C и Fortran спецификациями параллелизма, которые оформлены в виде директив и не видимы стандартным компиляторам. В статье будет рассмотрено автоматизированное дополнительное распараллеливание существующих MPI-программ с помощью системы SAPFOR, где, в свою очередь, будут использованы новые возможности DVMH модели по распараллеливанию циклов в MPI программе внутри узла. Данный подход позволяет существенно снизить трудоемкость распараллеливания MPI программ на графические ускорители и многоядерные процессоры, сохранив при этом удобство сопровождения уже написанной программы. Данная возможность в системе SAPFOR была реализована для языков Fortran и C. Эффективность данного подхода показана на примере некоторых приложений из пакета NAS Parallel Benchmarks.