Search

Одна из основных сложностей разработки параллельной программы для кластера — необходимость принятия глобальных решений по распределению данных и вычислений с учетом свойств всей программы, а затем выполнения кропотливой работы по модификации программы и ее отладки. Большой объем программного кода, а также многомодульность, многовариантность и многоязыковость, затрудняют принятие решений по согласованному распределению данных и вычислений. Опыт использования предыдущей системы САПФОР показал, что при распараллеливании на кластер больших программ и программных комплексов необходимо уметь распараллеливать их постепенно, начиная с наиболее времяемких фрагментов и постепенно добавляя новые фрагменты, пока не достигнем желаемого уровня эффективности параллельной программы. С этой целью предыдущая система была полностью переработана, и на ее основе была создана новая система SAPFOR (System FOR Automated Parallelization). В данной статье будет рассмотрен опыт применения метода частичного распараллеливания, идея которого заключается в том, что распараллеливанию подвергается не вся программа целиком, а ее части (области распараллеливания) — в них заводятся дополнительные экземпляры требуемых данных, производится распределение этих данных и соответствующих им вычислений., The main difficulty in developing a parallel program for a cluster is the need to make global decisions on the distribution of data and computations, taking into account the properties of the entire program, and then doing the hard work of modifying the program and debugging it. A large amount of code as well as multimoduling, multivariant and multilanguage, make it difficult to make decisions on a consistent distribution of data and computations. The experience of using the previous SAPFOR system showed that, when parallelizing large programs and software packages for a cluster, one should be able to parallelize them gradually, starting with the most time-intensive fragments and gradually adding new fragments until we reach the desired level of parallel program efficiency. For this purpose, the previous system was completely redesigned and a new system SAPFOR (System FOR Automated Parallelization) was created. To solve this problem, the method of incremental or partial arallelization will be considered in this paper. The idea of this method is that not the entire program is subjected to parallelization, but only its parts (parallelization regions) where additional versions of the required data are created and distributed and the corresponding computations are performed. This paper also discusses the application of automated mapping of programs to a cluster using the proposed incremental parallelization method and using the example of a NPB (NAS Parallel Benchmarks) software package., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2020

Настоящая статья является результатом исследования потока задач суперкомпьютеров "Ломоносов" и "Ломоносов-2". Предложен подход к оценке эффективности функционирования суперкомпьютерной системы, основанный на ее базовых характеристиках. Введена новая функция потери качества планирования суперкомпьютера. Подход позволяет сравнивать разные суперкомпьютерные системы исходя из целей использования, которые стоят перед системными администраторами вычислительных центров. Описан опыт применения целевой оптимизации процессов планирования, основанной на предложенном подходе, для суперкомпьютеров "Ломоносов" и "Ломоносов-2"., This paper is a result of studying the task flows observed on the Lomonosov and Lomonosov-2 supercomputers. A new approach to evaluating the performance of a supercomputer system based on its basic performance characteristics is proposed. A supercomputer's scheduling efficiency function is introduced for Lomonosov, Lomonosov-2 and other systems. The approach allows the system administrators to compare various supercomputer systems based on their usage aims. This paper describes the Moscow State University experience of applying the proposed approach to the optimization of Lomonosov and Lomonosov-2 scheduling resources., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2019

Представлен метод балансировки нагрузки вычислений с использованием кривых Гильберта применительно к параллельному алгоритму решения уравнений мелкой воды. Рассматриваемая система уравнений мелкой воды возникает в сигма-модели общей циркуляции океана INMOM (Institute of Numerical Mathematics Ocean Model) при разрешении гравитационных волн и является одним из основных блоков модели. Из-за наличия в океанах островов и берегов балансировка нагрузки вычислений на процессоры является особенно актуальной задачей. В качестве одного из таких методов был выбран метод балансировки нагрузки вычислений с использованием кривых Гильберта. Продемонстрирована большая эффективность этого метода по сравнению с равномерным разбиением без балансировки нагрузки и показано, что этот метод служит хорошей альтернативой библиотеке разбиений METIS. Оптимальность реализованного разбиения для мелкой воды точно соответствует оптимальности и для трехмерной сигма-модели INMOM в силу одинакового количества вертикальных уровней во всей расчетной области., This paper presents a method of load balancing using Hilbert space-filling curves applied to a parallel algorithm for solving shallow water equations. We consider the system of shallow water equations in the form presented in the ocean general circulation sigma-model INMOM (Institute of Numerical Mathematics Ocean Model). This system of equations is one of the basic blocks of the model. Due to land points in the computational grid, the load balancing is an especially urgent task. The method of load balancing using Hilbert space-filling curves is chosen as one of such methods. The paper demonstrates the greater efficiency of this method in comparison with the uniform partitioning without load balancing. It is shown that this method is a good alternative to the METIS standard library. Moreover, the optimality of the implemented partition for the shallow water equations exactly corresponds to the optimality for the INMOM three-dimensional sigma-model due to the same number of vertical levels in the entire computational domain., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 1 2019

В работе представлены три итерационных алгоритма быстрого преобразования Фурье с прореживанием по времени, имеющие алгоритмическую сложность O (N·R·log2N), где R — частотное разрешение спектральной характеристики (отношение длины набора частот к длине N набора отсчетов исходного сигнала). Алгоритмы отличаются способами организации вычислений: некоторые используют обратную перестановку битов, другие — дополнительные массивы. Приведены подробные вычислительные графы, а также блок-схемы разработанных алгоритмов. Полученные результаты можно использовать для улучшения отечественной электроники и программного обеспечения, а также включать в учебный процесс при подготовке инженеров в области цифровой обработки сигналов., This paper presents three iterative algorithms for fast Fourier transform with decimation in time; these algorithms have the algorithmic complexity O (N·R·log2N), where R is the frequency resolution of the spectral characteristic (the ratio of the length of the frequency set to the length of the N set of samples of the source signal). The algorithms differ in the way they organize calculations: some use reverse bit permutation, while the others use additional arrays. Detailed computational graphs and flowcharts of the developed algorithms are provided. The results obtained can be used to improve domestic electronics and software as well as may be included in the training process for engineers in the field of digital signal processing., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 2 2021

В данной статье представлен обзор современного состояния суперкомпьютерной техники. Обзор сделан с разных точек зрения — начиная от особенностей построения современных вычислительных устройств до особенностей архитектуры больших суперкомпьютерных комплексов. В данный обзор вошли описания самых мощных суперкомпьютеров мира и России по состоянию на начало 2021 г., а также некоторых менее мощных систем, интересных с других точек зрения. Также делается акцент на тенденциях развития суперкомпьютерной отрасли и описываются наиболее известные проекты построения будущих экзафлопсных суперкомпьютеров., This paper provides an overview of the current state of supercomputer technology. The review is done from different points of view — from the construction features of modern computing devices to the features of the architecture of large supercomputer complexes. This review includes descriptions of the most powerful supercomputers in the world and Russia since the early of 2021 as well as some less powerful systems that are interesting from other points of view. It also focuses on the development trends of the supercomputer industry and describes the most famous projects for building future exascale supercomputers., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 2 2021

Статья посвящена решению обратных задач синтеза нанооптических защитных элементов. Синтез нанооптического элемента включает в себя как решение обратной задачи расчета его фазовой функции, так и прецизионное формирование микрорельефа. При освещении микрорельефа в любой точке нанооптического элемента когерентным излучением в фокальной плоскости, параллельной плоскости оптического элемента, формируется изображение, используемое для автоматизированного контроля. Область оптического элемента разбивается на элементарные области. Изображение в элементарных областях формируется с помощью бинарных киноформов, фазовая функция которых рассчитывается с помощью решения нелинейного интегрального уравнения Фредгольма первого рода. Глубина микрорельефа в каждой элементарной области постоянна и определяет цвет элементарной области при освещении оптического элемента белым светом. Разработанные элементы могут быть использованы для защиты документов, акцизных марок, брендов и др., This paper is concerned with solving inverse problems of the synthesis of nanooptical security elements. The synthesis of a nanooptical element involves calculating its phase function via solving an inverse problem and fabricating the microrelief with high precision. The microrelief of the nanooptical element illuminated at any point with coherent radiation produces an image in the focal plane parallel to the plane of the optical element. This image is used for the automated authenticity verification. The area of the optical element is divided into elementary regions. In each elementary region, the image is formed using binary kinoforms whose phase function is calculated via solving a nonlinear Fredholm integral equation of the first kind. The depth of the microrelief is constant in each elementary region and determines the color of that region when the optical element is illuminated with white light. The developed elements can be used to protect documents, excise stamps, and brands., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 1 2020

В статье рассматриваются результаты экспериментальной оценки производительности и энергоэффективности многоядерных процессоров MALT в задачах обработки изображений на примере фильтрации изображения с помощью оператора Собеля. Измерения осуществлялись с использованием низкоуровневого эмулятора MALTemu, прототипа процессора в ПЛИС и экспериментальной СБИС модели MALT-Cv2 Rev1. Полученные результаты сравниваются с аналогичными результатами для процессоров общего назначения (последовательная реализация) и графических процессоров с поддержкой технологии CUDA., In this paper we consider the experimental performance and energy efficiency evaluation in image processing tasks for the MALT manycore processors. The image filtering with the Sobel operator is used as an example. Measurements are conducted using the MALTemu low level emulator, an FPGA processor prototype and an experimental ASIC model MALT-Cv2 Rev1. The obtained results are compared with similar results for a general purpose CPU (sequential implementation) and a GPU with the CUDA technology support., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 2 2020

Системы уравнений с запаздываниями широко применяются в различных областях современного математического моделирования. В ходе разработки структуры математической модели и идентификации ее параметров приходится многократно решать задачу Коши для подобных систем. В случае высокой размерности системы, а также при условии жесткости задачи численное решение уравнений с запаздываниями может требовать значительных вычислительных и временных затрат. Таким образом, разработка и реализация эффективных алгоритмов численного решения различных классов уравнений с запаздывающими аргументами является актуальной задачей. В настоящей статье представлена модифицированная версия программного комплекса DIFSUBDEL, в которой реализованы методы численного решения дифференциальных уравнений с запаздываниями на основе линейных многошаговых методов. Переработанная версия разработана с применением принципов структурного программирования и является значительно более удобной в эксплуатации, чем исходная, а также обладает свойством потокобезопасности, что позволяет использовать комплекс в качестве блока в системах, основанных на технологиях параллельного программирования с общей памятью. Был проведен сравнительный анализ производительности переработанной системы DIFSUBDEL c другими существующими программными реализациями численных методов решения дифференциальных уравнений с запаздыванием и показана ее эффективность., The systems of delay differential equation are widely used in modern mathematical modeling. The process of mathematical model development and identification requires the repeated solution of initial value problems for such systems. The numerical solution of delay differential equations may be computationally expensive, especially when the problem is stiff and high-dimensional. Therefore, it is important to develop and implement the efficient algorithms for the numerical solution of different classes of delay differential equations. In this paper, a new implementation of DIFSUBDEL program package for the numerical solution of delay differential equations based on linear multistep methods is discussed. The modified version is based on structured programming principles to make the program thread safe and user-friendly. The modified program performance is compared with the existing implementations of numerical methods for the solution of delay differential equations., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 1 2020

Функционалы Минковского являются важным инструментом для изучения морфологии пористых сред. Настоящая работа посвящена построению алгоритма вычисления функционалов Минковского четырехмерных цифровых изображений, возникающих, в частности, при описании динамики изменения порового пространства среды. В работе впервые программно реализован алгоритм вычисления функционалов Минковского четырехмерных цифровых изображений., The Minkowskii functionals are important for studying the morphology of porous media. This paper is devoted to constructing an algorithm for computing the Minkowskii functionals for four-dimensional digital images used to describe the dynamics of porous media. This algorithm is implemented as a software package., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 2 2020

Статья посвящена изучению нелинейных эффектов в динамике популяции промысловой рыбы пиленгас Азовского моря при низкой и высокой ее численности с учетом эффекта Олли, конкуренции за ресурсы, таксиса, вылова, пространственного распределения биогенных веществ и детрита на основе многовидовой модели взаимодействия планктона и рыб. Дискретный аналог разработанной модельной задачи водной экологии, входящей в состав программного комплекса, получен на основе схем второго порядка точности с учетом частичной заполненности расчетных ячеек. Возникающая в процессе дискретизации система сеточных уравнений большой размерности была решена на основе модифицированного попеременно-треугольного метода, имеющего наибольшую скорость сходимости при условии асимптотической устойчивости разностных схем для параболических уравнений, эффективность которого была улучшена на основе уточненных спектральных оценок. Разработка эффективных параллельных алгоритмов численной реализации поставленной задачи биологической кинетики, ориентированных на многопроцессорную вычислительную систему (МВС) и графический ускоритель NVIDIA Tesla K80 с модификацией формата хранения данных, позволила анализировать процессы воспроизводства популяций биогидроценоза в режиме реального и ускоренного времени., Paper covers the research of nonlinear effects in population dynamics of the pelengas commercial fish of the Azov Sea taking into account the Allee effect, competition for resources, taxis, catching, spatial distribution of biogenic matter and detritus based on a multi-species model of plankton and fish interaction. Discrete analogue of developed model problem of water ecology, included in a software complex, were calculated using schemes of second order of accuracy taking into account the partial filling of computational cells. The system of grid equations of large dimension, arising at discretization, has been solved on the basis of adaptive modified alternately triangual variational method. Effective parallel algorithms were developed for numerical implementation of biological kinetics problem and oriented on multiprocessor computer system and NVIDIA Tesla K80 graphics accelerator with the data storage format modification. Due to it, the reproduction processes of biogeocenose populations have been analyzed in real and accelerated time., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2020

Диссонанс является уточнением понятия аномальной подпоследовательности (существенно непохожей на остальные подпоследовательности) временного ряда. Задача поиска диссонанса встречается в широком спектре предметных областей, связанных с временными рядами: медицина, экономика, моделирование климата и др. В работе предложен новый параллельный алгоритм поиска диссонанса во временном ряде на платформе многоядерного ускорителя для случая, когда входные данные могут быть размещены в оперативной памяти. Алгоритм использует возможность независимого вычисления евклидовых расстояний между подпоследовательностями ряда. Алгоритм состоит из двух этапов: подготовка данных и поиск. На этапе подготовки выполняется построение вспомогательных матричных структур данных, обеспечивающих распараллеливание и векторизацию вычислений. На стадии поиска осуществляется нахождение диссонанса с помощью построенных структур данных. Выполнена реализация алгоритма для ускорителей архитектур Intel MIC (Many Integrated Core) и NVIDIA GPU, распараллеливание выполнено с помощью технологий программирования OpenMP и OpenAcc соответственно. Представлены результаты вычислительных экспериментов, подтверждающих масштабируемость разработанного алгоритма., Discord is a refinement of the concept of anomalous subsequence of a time series. The discord discovery problem frequently occurs in a wide range of application areas related to time series: medicine, economics, climate modeling, etc. In this paper we propose a new parallel discord discovery algorithm for many-core systems in the case when the input data fit in the main memory. The algorithm exploits the ability to independently calculate the Euclidean distances between the subsequences of the time series. Computations are paralleled using OpenMP and OpenAcc for the Intel MIC (Many Integrated Core) and NVIDIA GPU platforms, respectively. The algorithm consists of two stages, namely precomputations and discovery. At the precomputation stage, we construct the auxiliary matrix data structures to ensure the efficient vectorization of computations on an accelerator. At the discovery stage, the algorithm searches for a discord based on the constructed structures. A number of numerical experiments confirm a high scalability of the proposed algorithm., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2019

Предложен метод проведения анализа эффективности и оптимизации суперкомпьютерных приложений, примененный на практике для изучения задач одного из пользователей суперкомпьютера Ломоносов2. Этот метод затрагивает различные этапы исследования задач, начиная от изучения общего поведения всех запусков пользователя на суперкомпьютере и заканчивая детальным изучением и оптимизацией исходного кода выбранной программы. Приведено описание общих этапов анализа, которые были выполнены на практике, показаны метрики производительности, на которые следует обратить внимание при выполнении подобного анализа, а также продемонстрированы конкретные примеры поведения задач и эффект от оптимизации, выполненной для задачи расчета жидкокристаллических капель., A method for the efficiency analysis and optimization of supercomputer applications applied earlier in practice to study jobs of a user on the Lomonosov2 supercomputer is proposed. This method involves various stages of the jobs research, starting from studying the general behavior of all user launches on a supercomputer and ending with a detailed study and optimization of the source code of a selected program. The paper describes the general stages of the analysis that were carried out in practice, shows performance metrics that should be paid attention to when performing such an analysis, and shows also some specific examples of the job behavior and the effect of optimization carried out for the task of calculating liquid crystal droplets., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2019

AlgoWiki - это открытая энциклопедия свойств алгоритмов и их реализаций на различных программно-аппаратных платформах. Ее можно использовать для достижения различных целей, например для поиска оптимального алгоритма решения некоторой задачи, анализа информационной структуры приложения или для сравнения эффективности различных реализаций какого-либо алгоритма. В настоящей статье описаны появляющиеся новые возможности энциклопедии AlgoWiki, направленные на создание связанного представления различных алгоритмических подходов решения одной и той же задачи. На это нацелено описание предметной области в виде цепочек задача-метод-алгоритм-реализация, дополненное возможностями формирования рейтингов на базе любых алгоритмов энциклопедии, а также механизмом архитектурных срезов., AlgoWiki is an open encyclopedia of algorithms' properties and features of their implementations on different hardware and software platforms. It can be used to achieve various aims, for example, to search for the optimal algorithm to solve a certain problem, to analyze the information structure of an application or to compare the efficiency of different implementations of an algorithm. This paper describes the emerging new features of the AlgoWiki encyclopedia aimed at creating a joint presentation of various algorithmic approaches to solve the same problem. This is the aim of the subject area description in the form of chains problem-method-algorithm-implementation supplemented by the possibility of generating ratings based on any algorithms of the encyclopedia as well as a mechanism of architectural profiles., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2019

В настоящее время проблема недостаточной эффективности работы суперкомпьютерных комплексов во многом связана с тем, что администраторы таких систем не всегда могут своевременно обнаруживать и устранять причины снижения эффективности. Это в большей степени касается не выхода из строя оборудования (такие случаи можно отслеживать с помощью систем мониторинга), а неявного снижения эффективности работы определенных компонентов суперкомпьютера при условии, что внешне они продолжают работать корректно. Возникновение подобной ситуации связано с тем, что на данный момент нет достаточно гибких и удобных средств для оперативного и комплексного анализа всех характеристик качества работы вычислительных систем. Существующие решения либо позволяют анализировать только небольшую часть таких характеристик, либо представляют собой не универсальные решения, удовлетворяющие только небольшой набор конкретных нужд администраторов определенной системы. В настоящей статье описывается системный подход к решению этого вопроса, который позволит проводить комплексный анализ различных аспектов работы суперкомпьютеров, связанных в первую очередь с выполнением суперкомпьютерных приложений. Разрабатываемый на основе этого подхода программный инструмент предназначен для сбора в рамках единой модели всех наиболее важных данных о свойствах и качестве выполняющихся на суперкомпьютере задач - данные об эффективности их выполнения, размере и длительности, наличии характерных или аномальных сценариев поведения, использовании прикладных пакетов и библиотек и др. С помощью гибких возможностей по агрегации будет задаваться нужная степень детализации, с какой необходимо предоставлять полученную информацию - по отдельным пользователям, проектам, прикладным пакетам, предметным областям, разделам суперкомпьютера, временным диапазонам и др. Это позволит создавать сотни и тысячи различных представлений для анализа состояния суперкомпьютера, что поможет администраторам выбирать наиболее подходящий для них вариант., Currently, the problem of low performance of supercomputer complexes is largely due to the fact that administrators of such complexes cannot always timely detect and eliminate the root causes of reduced efficiency. This largely concerns not the equipment failure (such cases can usually be detected using monitoring systems), but an implicit performance decrease of certain supercomputer components, provided that they seems to continue working correctly. Such a situation arises because there are no sufficiently flexible and convenient software tools for prompt and comprehensive analysis of all the performance quality characteristics of computer systems at the moment. The existing solutions either allow analyzing only a small part of such characteristics or are made as non-universal solutions that satisfy only a small set of specific needs provided by administrators of a particular system. This paper describes a systematic approach to solving this issue, which will allow one to perform a comprehensive analysis of various aspects of supercomputer functioning, primarily related to the execution of supercomputer applications. A software tool developed on the basis of this approach will collect, within a single model, all the most important data on the properties and quality of jobs running on the supercomputer - data on their execution performance, size and duration, presence of specific or abnormal behavior scenarios, the usage of application packages and libraries, etc. Using flexible aggregation capabilities, the required level of detail will be specified - individual users, projects, application packages, subject areas, supercomputer partitions, time ranges, etc. This will allow one to create hundreds and thousands of different views for analyzing the state of the supercomputer, which will help administrators to choose the most suitable option for them., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2019

Алгоритм PAM (Partitioning Around Medoids) представляет собой разделительный алгоритм кластеризации, в котором в качестве центров кластеров выбираются только кластеризуемые объекты (медоиды). Кластеризация на основе техники медоидов применяется в широком спектре приложений: сегментирование медицинских и спутниковых изображений, анализ ДНК-микрочипов и текстов и др. На сегодня имеются параллельные реализации PAM для систем GPU и FPGA, но отсутствуют таковые для многоядерных ускорителей архитектуры Intel Many Integrated Core (MIC). В настоящей статье предлагается новый параллельный алгоритм кластеризации PhiPAM для ускорителей Intel MIC. Вычисления распараллеливаются с помощью технологии OpenMP. Алгоритм предполагает использование специализированной компоновки данных в памяти и техники тайлинга, позволяющих эффективно векторизовать вычисления на системах Intel MIC. Эксперименты, проведенные на реальных наборах данных, показали хорошую масштабируемость алгоритма., The PAM (Partitioning Around Medoids) is a partitioning clustering algorithm where each cluster is represented by an object from the input dataset (called a medoid). The medoid-based clustering is used in a wide range of applications: the segmentation of medical and satellite images, the analysis of DNA microarrays and texts, etc. Currently, there are parallel implementations of PAM for GPU and FPGA systems, but not for Intel Many Integrated Core (MIC) accelerators. In this paper, we propose a novel parallel PhiPAM clustering algorithm for Intel MIC systems. Computations are parallelized by the OpenMP technology. The algorithm exploits a sophisticated memory data layout and loop tiling technique, which allows one to efficiently vectorize computations with Intel MIC. Experiments performed on real data sets show a good scalability of the algorithm., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 2 2019

Обратная задача 3D ультразвуковой томографии рассматривается в статье как нелинейная коэффициентная обратная задача для уравнения гиперболического типа. Используемая математическая модель хорошо описывает как дифракционные эффекты, так и поглощение ультразвука в неоднородной среде. В рассматриваемой постановке реконструируется скорость распространения акустической волны как функция трех координат. Количество неизвестных в нелинейной обратной задаче составляет порядка 50 миллионов. Разработанные итерационные алгоритмы решения обратной задачи ориентированы на использование GPUкластеров. Основным результатом работы является апробация алгоритмов на экспериментальных данных. В эксперименте использовался стенд для 3D ультразвуковых томографических исследований, разработанный в МГУ имени М.В. Ломоносова. Акустические параметры фантомов близки к акустическим параметрам мягких тканей человека. Объем экспериментальных данных составляет порядка 3 ГБ. Интерпретация данных эксперимента позволила не только продемонстрировать эффективность разработанных алгоритмов, но и подтвердила адекватность математической модели реальности. Для реализации разработанных численных алгоритмов использовался графический кластер суперкомпьютера Ломоносов-2., The inverse problem of 3D ultrasound tomography is considered in this paper as a nonlinear coefficient inverse problem for a hyperbolic equation. The employed mathematical model accurately describes the effects of ultrasound wave diffraction and absorption in inhomogeneous media. The velocity of acoustic waves inside the test sample is reconstructed as an unknown function of three spatial coordinates. The number of unknowns in the nonlinear inverse problem reaches 50 million. The developed iterative algorithms for solving the inverse problem are designed for GPU clusters. The main result of this study is testing the developed algorithms on experimental data. The experiments were carried out using a 3D ultrasound tomographic setup developed at Lomonosov Moscow State University. Acoustic properties of the test samples were close to those of human soft tissues. The volume of data collected in experiments is up to 3 GB. Experimental results show the efficiency of the proposed algorithms and confirm that the mathematical model is adequate to reality. The proposed algorithms were tested on the GPU partition of Lomonosov2 supercomputer., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2019

В настоящее время поиск похожих подпоследовательностей требуется в широком спектре приложений интеллектуального анализа временных рядов: моделирование климата, финансовые прогнозы, медицинские исследования и др. В большинстве указанных приложений при поиске используется мера схожести Dynamic Time Warping (DTW), поскольку на сегодняшний день научное сообщество признает меру DTW одной из лучших для большинства предметных областей. Мера DTW имеет квадратичную вычислительную сложность относительно длины искомой подпоследовательности, в силу чего разработан ряд параллельных алгоритмов ее вычисления на устройствах FPGA и многоядерных ускорителях с архитектурами GPU и Intel MIC. В настоящей статье предлагается новый параллельный алгоритм для поиска похожих подпоследовательностей в сверхбольших временных рядах на кластерных системах с узлами на базе многоядерных процессоров Intel Xeon Phi поколения Knights Landing (KNL). Вычисления распараллеливаются на двух уровнях: на уровне всех узлов кластера - с помощью технологии MPI и в рамках одного узла кластера - с помощью технологии OpenMP. Алгоритм предполагает использование дополнительных структур данных и избыточных вычислений, позволяющих эффективно задействовать возможности векторизации вычислений на процессорных системах Phi KNL. Эксперименты, проведенные на синтетических и реальных наборах данных, показали хорошую масштабируемость алгоритма., Nowadays, the subsequence similarity search is required in a wide range of time series mining applications: climate modeling, financial forecasts, medical research, etc. In most of these applications, the Dynamic Time Warping (DTW) similarity measure is used, since DTW is empirically confirmed as one of the best similarity measures for the majority of subject domains. Since the DTW measure has a quadratic computational complexity with respect to the length of query subsequence, a number of parallel algorithms for various many-core architectures are developed, namely FPGA, GPU, and Intel MIC. In this paper we propose a new parallel algorithm for subsequence similarity search in very large time series on computer cluster systems with nodes based on Intel Xeon Phi Knights Landing (KNL) many-core processors. Computations are parallelized on two levels as follows: by MPI at the level of all cluster nodes and by OpenMP within a single cluster node. The algorithm involves additional data structures and redundant computations, which make it possible to efficiently use the capabilities of vector computations on Phi KNL. Experimental evaluation of the algorithm on real-world and synthetic datasets shows that the proposed algorithm is highly scalable., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 1 2019

Рассмотрена задача о топливном коллекторе, которую можно отнести к обратным задачам гидродинамики: необходимо определить геометрию распределительного канала коллектора, обеспечивающего равномерную раздачу топлива. Однако профилирование коллектора на основе 3D стационарных уравнений Навье-Стокса для турбулентного течения несжимаемой вязкой среды в шероховатых каналах требует непрактичных вычислительных усилий. Использована иерархия математических моделей: 1D уравнения Навье-Стокса для профилирования и 3D уравнения Навье-Стокса для калибровки 1D модели. Показано, что используемая иерархия моделей позволяет существенно снизить объем вычислительной работы, необходимой для расчета оптимальной конструкции коллектора. Предложенный подход представляет интерес для оптимизации технических устройств различного назначения., A fuel collector problem is considered as an inverse problem of hydrodynamics: it is necessary to determine the distribution channel geometry of a collector for a uniform fuel distribution. However, the collector profiling based on the 3D stationary Navier-Stokes equations for turbulent flow of an incompressible viscous medium in rough channels requires impractical computational efforts. A hierarchy of mathematical models (1D Navier-Stokes equations for the collector profiling and 3D Navier-Stokes equations for 1D model validation) is used in this paper. It is shown that the hierarchy of models can significantly reduce amount of computational work needed for computing the optimal collector design. The developed approach is of interest for optimizing technical devices for various purposes., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2019

Статья посвящена разработке методики исследования масштабируемости ресурсоемких итерационных алгоритмов, применяемых в моделировании сложных физических процессов на суперкомпьютерных системах. В основе предлагаемой методики лежит модель параллельных вычислений BSF (Bulk Synchronous Farm), позволяющая на ранней стадии разработки итерационного алгоритма определить границу его масштабируемости. Модель BSF предполагает представление алгоритма в виде операций над списками с использованием функций высшего порядка. При этом рассматривается два класса представлений: BSF-M (Map BSF) и BSF-MR (Map-Reduce BSF). Предлагаемая методика описывается на примере решения систем линейных алгебраических уравнений методом Якоби. Для метода Якоби строится два итерационных алгоритма: Jacobi-M на основе представления BSF-M и Jacobi-MR на основе представления BSF-MR. Для указанных алгоритмов с помощью стоимостных метрик модели BSF даются аналитические оценки для ускорения, эффективности распараллеливания и верхней границы масштабируемости для многопроцессорных вычислительных систем с распределенной памятью. Приводится информация о реализации этих алгоритмов на языке C++ с использованием программного шаблона BSF и библиотеки параллельного программирования MPI. Демонстрируются результаты масштабных вычислительных экспериментов, выполненных на кластерной вычислительной системе. На основе экспериментальных результатов дается анализ адекватности оценок, полученных аналитическим путем с помощью стоимостных метрик модели BSF., This paper is devoted to the development of a methodology for evaluating the scalability of compute-intensive iterative algorithms used for simulating complex physical processes on supercomputer systems. The proposed methodology is based on the BSF (Bulk Synchronous Farm) parallel computation model, which makes it possible to predict the upper scalability bound of an iterative algorithm in early stages of its design. The BSF model assumes the representation of the algorithm in the form of operations on lists using high-order functions. Two classes of representations are considered: BSF-M (Map BSF) and BSF-MR (Map-Reduce BSF). The proposed methodology is described by the example of solving a system of linear equations by the Jacobi method. For the Jacobi method, two iterative algorithms are constructed: Jacobi-M based on the BSF-M representation and Jacobi-MR based on the BSF-MR representation. Analytical estimations of the speedup, parallel efficiency and upper scalability bound are obtained for these algorithms using the BSF cost metrics on multi-processor computing systems with distributed memory. These algorithms are implemented on C++ language using the BSF program skeleton and MPI parallel programming library. The results of large-scale computational experiments performed on a cluster computing system are discussed. Based on the experimental results, an analysis of the adequacy of estimations obtained analytically using the BSF cost metric is made., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2018

Современные вычисления устойчиво ассоциируются с параллелизмом на всех уровнях. От персональных планшетов и телефонов вплоть до лучших суперкомпьютеров отличаются масштабы и подходы к решению задач, но идея распределения вычислительной работы присутствует повсюду. Изучение возможностей параллельных вычислений для портативных платформ началось в Научно-исследовательском вычислительном центре МГУ им. М.В.Ломоносова несколько лет назад, в 2014 году. Были разработаны версии популярного бенчмарка Linpack для Android и iOS. Четыре года доступности рейтинга для пользователей вылились в почти двадцать тысяч результатов тестов. В статье рассматриваются факты и тенденции, полученные в результате анализа этих данных. В том числе, полученные результаты подтверждают целесообразность дальнейшего развития рейтинга мобильных устройств., Contemporary computing is strongly associated with parallelism. From personal tablets and phones and up to the top supercomputers, the scales and approaches differ, but the idea of work distribution is present everywhere. A study of portable platforms parallel computing capabilities was started at the Research Computing Center of Lomonosov Moscow State University several years ago, in 2014. There were Android and iOS implementations of popular benchmark developed. Four years of the test availability for regular users turned into almost 20 thousand of test results. This paper addresses the investigation of facts and trends, mined out of this data, proving the reasons for the further Mobile Linpack development., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2018

Статья посвящена исследованию алгоритма NSLP для решения нестационарных задач линейного программирования сверхбольшой размерности, ориентированного на кластерные вычислительные системы. В основе анализа лежит модель параллельных вычислений BSF, основанная на моделях BSP и SPMD. Даются краткие описания алгоритма NSLP и модели BSF. Рассматривается реализация алгоритма NSLP в виде BSF-программы. На базе стоимостной метрики модели BSF выводится верхняя граница масштабируемости алгоритма NSLP и оценивается эффективность его параллелизации. Описывается реализация алгоритма NSLP на основе программного каркаса BSF на языке Си и приводятся результаты экспериментов, исследующих масштабируемость указанной реализации на модельной задаче линейного программирования. Делается сравнение результатов, полученных аналитическим и экспериментальным путем., This paper is devoted to the scalability study of an NSLP algorithm for solving non-stationary high-dimension linear programming problems on cluster computing systems. The analysis is based on the BSF model of parallel computations. The BSF model is a new parallel computation model designed on the basis of BSP and SPMD models. The brief descriptions of the NSLP algorithm and the BSF model are given. The NSLP algorithm implementation in the form of a BSF program is considered. On the basis of the BSF cost metric, the upper bound of the NSLP algorithm scalability is derived and its parallel efficiency is estimated. The NSLP algorithm implementation using BSF skeleton is described. The scalability estimates obtained analytically and experimentally are compared., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2018

При распараллеливании решения трехмерных краевых задач, особенно в областях со сложной геометрией, важными являются технологии проведения вычислений и структуры данных. От них зависит объем хранимой информации и время решения. В статье предлагаются технологии распараллеливания метода декомпозиции расчетной области на подобласти, сопрягаемые без наложения, на квазиструктурированных сетках. Разработаны параллельные сеточные структуры данных, ориентированные преимущественно на работу со структурированными массивами данных. Приведен иллюстративный пример, показывающий основные положения предлагаемого подхода., When parallelizing the solution of three-dimensional boundary value problems, especially in domains with complex geometry, the сomputational technologies and data structureы are important. The amount of stored information and the computational time depend on them. In this paper we propose the technologies for parallelizing the method of decomposition of the computational domain into subdomains conjugated without overlapping on a quasistructured grid. Parallel grid data structures oriented mainly to work with structured data arrays are developed. An illustrative example clarifying the fundamentals of the proposed approach is discussed., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2018

Основной мотивацией для данной статьи послужила растущая популярность реконфигурируемых ПЛИС (программируемых логических интегральных схем) в области высокопроизводительных вычислений, а также необходимость исследовать особенности написания эффективных программ с использованием инструмента Altera SDK for OpenCL, позволяющего писать приложения для ПЛИС с помощью языка программирования Си++ и стандарта OpenCL. В статье рассмотрены особенности программной модели OpenCL и представлено исследование производительности и особенностей различных реализаций фильтра Собеля с использованием указанного инструмента., The main motivation is the growing popularity of reconfigurable FPGAs in the field of high-performance computing as well as the need to study the features of writing efficient software using the Altera SDK for OpenCL tool, which allows one to implement applications for FPGA using the C++ programming language and the OpenCL standard. The paper discusses the features of the OpenCL software model and presents a study of the performance and features of various Sobel filter implementations using the mentioned tool., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2018

Статья посвящена моделированию трещиноватых резервуаров. Построена трехмерная статистическая модель дискретной системы трещин. Предложен эффективный метод генерирования случайных реализаций статистической модели для произвольной расчетной сетки. Решена задача масштабирования модели трещин с использованием анализа сейсмических изображений статистической модели для различных значений шага сетки., This paper is devoted to modeling of fractured reservoirs. A three-dimensional statistical model of a discrete fracture network is developed. An efficient method to generate the random realizations of the statistical model for an arbitrary computational grid is proposed. The problem of scaling the fracture model using the analysis of seismic images for different grid steps is solved., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2018

Ассоциативные (контекстно адресуемые) параллельные процессоры типа SIMD с вертикальной обработкой информации ориентированы на решение задач нечисловой обработки данных. Моделирование работы таких систем описывается с помощью абстрактной модели типа SIMD (STAR-машины). На этой модели были разработаны эффективные алгоритмы для решения многих задач на графах. Однако из-за отсутствия широко распространенных ассоциативных архитектур эти алгоритмы не могли применяться на практике. С развитием графических ускорителей появилась возможность реализовывать ассоциативные параллельные модели без существенной потери эффективности. В качестве первого этапа реализации STAR-машины на графических ускорителях в виде библиотеки на CUDA были реализованы специфические для языка STAR типы данных и простейшие операции над ними. В настоящей статье приводится эффективная реализация на GPU библиотеки стандартных процедур языка STAR. Проведено сравнение времени работы данной реализации с временем работы процедур из стандартных библиотек (STL на CPU и CUDA thrust на GPU), выполняющих эти же операции. Планируется использовать представленную реализацию STAR-машины на GPU для решения задач на графах., The associative (content addressable) parallel processors of the SIMD type with vertical data processing are oriented on solving problems of non-numeric data processing. The simulation of such systems is described using an abstract SIMD-type model of a STAR machine. On the basis of this model, a number of efficient algorithms are developed to solve many graph problems. Since the associative architectures are not widely available, however, these algorithms cannot be used in practice. With advances in the production of GPU, the possibilities to implement the associative parallel models without significant loss of efficiency are increased. As the first stage in the implementation of the STAR-machine on GPU in the form of a CUDA library, specific data types and simple operations of the STAR language were developed. In this paper, we consider an efficient GPU implementation of the standard associative procedure library. The runtime of this implementation is compared with the runtime of similar procedures in the standard libraries (STL on CPU and CUDA thrust on GPU). We plan to use our library implementation to solve graph problems., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 1 (55) 2018

Статья посвящена ускорению параллельного решения трехмерных краевых задач методом декомпозиции расчетной области на подобласти, сопрягаемые без наложения. Декомпозиция проводится равномерной параллелепипедальной макросеткой. В каждой подобласти и на границе сопряжения (интерфейсе) строятся свои структурированные подсетки. Объединение этих подсеток образует квазиструктурированную сетку, на которой решается поставленная задача. Распараллеливание решения осуществляется при помощи MPI-технологий. Предложен и экспериментально исследован алгоритм ускорения внешнего итерационного процесса по подобластям для решения системы линейных алгебраических уравнений, аппроксимирующих уравнение Пуанкаре-Стеклова на интерфейсе. Проведены серии численных экспериментов на различных квазиструктурированных сетках и при различных параметрах вычислительных алгоритмов, показывающих ускорение вычислений., This paper is devoted to the acceleration of the parallel solution of three-dimensional boundary value problems by the computational domain decomposition method into subdomains that are conjugated without overlapping. The decomposition is performed by a uniform parallelepipedal macrogrid. In each subdomain and on the interface, some structured subgrids are constructed. The union of these subgrids forms a quasi-structured grid on which the problem is solved. The parallelization is carried out using the MPI-technology. We propose and experimentally study the acceleration algorithm for an external iterative process on subdomains to solve a system of linear algebraic equations approximating the Poincare-Steklov equation on the interface. A number of numerical experiments are carried out on various quasi-structured grids and with various parameters of computational algorithms showing the acceleration of computations., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 2 2018

Статья посвящена моделированию течений реальных газов и их смесей в микроканалах технических систем с использованием высокопроизводительных вычислений. Для моделирования используется многомасштабный двухуровневый подход, сочетающий расчеты на макро- и микроуровнях. Подход позволяет исследовать многокомпонентные течения в микроканалах сложной геометрии в широком диапазоне чисел Кнудсена. Параллельная реализация основана на методе разделения областей и функциональном параллелизме и ориентирована на использование вычислительных систем с гибридной архитектурой. В качестве примера рассмотрена задача истечения смеси азота и водорода в вакуум. На этом примере исследована корректность многомасштабного подхода. Кроме того, представлены результаты прямого молекулярно-динамического моделирования течения азота в никелевом микросопле, в том числе характеристика эффективности распараллеливания при большом числе частиц (0.5 млрд) и профили скорости в микросопле в зависимости от времени., This paper is devoted to the modeling of flows of real gases and their mixtures in microchannels of technical systems using high-performance computing. For modeling, a multiscale two-level approach is used; it combines calculations at macro- and microlevels. The approach makes it possible to study multicomponent flows in microchannels of complex geometry in a wide range of Knudsen numbers. The parallel implementation is based on the domain decomposition method and the functional parallelism and is oriented on the use of computer systems with hybrid architecture. As an example, the problem of outflow of a nitrogen and hydrogen mixture into vacuum is considered. This example is used to study the correctness of the multiscale approach. In addition, the results of direct molecular-dynamics modeling of nitrogen flow in a nickel micronozzle are discussed, including the parallelization performance at a large number of particles (0.5 billion) and the velocity profiles in a micronozzle as a function of time., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 1 (55) 2018

В Научно-исследовательском центре электронной вычислительной техники (НИЦЭВТ) разрабатывается высокоскоростная коммуникационная сеть Ангара с топологией "многомерный тор". При эксплуатации вычислительного кластера с сетью Ангара в условиях наличия занятых и отказавших узлов возникает задача поиска оптимального подмножества узлов сети для покрытия заданного числа узлов так, чтобы весь сетевой трафик лежал внутри этого подмножества узлов. В настоящей статье представлен приближенный полиномиальный алгоритм решения такой задачи., The Angara high-speed interconnect with multidimensional torus topology is under development in Scientific Research Center for Electronic Computer Technology. During the utilization of the Angara interconnect in cluster systems, there exist busy and failed nodes. Thus, there is a problem of finding an optimal cluster node subset such that the network traffic belongs to this node subset and the node subset size is not less than a given size. The paper presents an approximate algorithm for solving this problem., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 1 2017

Сейсмические данные характеризуются своей нерегулярностью, многомерностью и большим объемом. В настоящей статье рассматривается разложение данных по одному из наиболее оптимальных базисов - гауссовым волновым пакетам. На базе графических процессоров реализован и оптимизирован быстрый алгоритм прямого и обратного преобразования по трехмерным гауссовым волновым пакетам. Оптимизированная версия программы для графических ускорителей демонстрирует рост производительности в 2-6 раз по сравнению с 20-ядерным процессором.Проведено успешное тестирование алгоритмов на синтетических сейсмических данных: восстановление изображения по коэффициентам гауссовых волновых пакетов, сжатие данных, подавление шумов данных, интерполяция данных в случае пропущенных трасс., Seismic data are characterized by multidimensionality, large data sizes, and irregular structures. In this paper we consider an optimal decomposition of seismic data using the basis of Gaussian wave packets. We implemented and optimized a number of fast algorithms for forward and inverse transforms for three-dimensional seismic data decomposition. The algorithms implemented on GPU demonstrate 2-6 speedup compared to 20-core CPUs. The programs were tested on synthetic seismic data sets: data reconstruction by Gaussian wave-packet coefficients, data compression, denoising, and interpolation in the case of missing traces., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2017

Статья посвящена разработке эффективных итерационных методов решения нелинейных обратных задач волновой томографии. Итерационные алгоритмы приближенного решения обратной задачи используют явное представление для градиента функционала невязки между экспериментально измеренным и расcчитанным волновым полем. Большое значение для сходимости итерационного процесса в нелинейной обратной задаче имеет выбор начального приближения. В статье исследована возможность использования в качестве начального приближения скоростного разреза, полученного из решения обратной задачи в лучевом приближении. Эффективность такого подхода проиллюстрирована решением модельных обратных задач на суперЭВМ. Модельные задачи ориентированы на томографическую ультразвуковую диагностику мягких тканей в медицине., This paper is devoted to developing efficient iterative methods to solve nonlinear inverse problems of wave tomography. The iterative algorithms used to obtain an approximate solution of the inverse problem are based on an explicit representation of the gradient of the residual functional between the measured and computed wave fields. The choice of the initial approximation is of great importance for the convergence of the iterative process in a nonlinear inverse problem. The possibility of using an initial approximation to the sound speed obtained via solving the inverse problem in the ray approximation is studied. The efficiency of this approach is illustrated by solving model problems using a supercomputer. These model problems are designed for the ultrasound tomographic imaging of soft tissues in medicine., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2017

Статья посвящена разработке эффективных методов решения обратных задач волновой томографии. Предложена новая схема послойной томографии трехмерных объектов с экспериментальными данными, которые измеряются на цилиндрической поверхности. Такая схема обеспечивает измерение как отраженных, так и проходящих волн и легко реализуема на практике. Для решения обратной задачи используется математическая модель, которая хорошо описывает как дифракционные эффекты, так и эффект поглощения ультразвукового излучения. Предложены эффективные численные методы восстановления скоростного разреза по экспериментальным томографическим данным на цилиндрической поверхности. Разработанные методы ориентированы в первую очередь на диагностику рака молочной железы на ранних стадиях заболевания. Обратные задачи ультразвуковой томографии являются нелинейными и очень сложными с вычислительной точки зрения. Численные алгоритмы реализованы на графических процессорах. Эффективность разработанных алгоритмов иллюстрируется модельными расчетами., This paper is dedicated to developing efficient methods to solve inverse problems of wave tomography. The proposed new scheme of layer-by-layer tomography of 3D objects uses the experimental data measured on a cylindrical surface. This scheme provides the measurements of both the reflected and the transmitted waves and can easily be implemented in practice. The mathematical model used to solve the inverse problem takes into account the ultrasound diffraction and absorption effects. The authors developed efficient numerical methods to reconstruct the sound speed cross section using the tomographic data measured on the cylindrical surface. These methods are aimed primarily at early breast cancer diagnosis. The inverse problems of ultrasonic tomography are nonlinear and very computationally expensive. The efficiency of the developed methods is illustrated via numerical simulations. The numerical algorithm is implemented on GPU., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2017

Статья посвящена параллельной реализации многомасштабного подхода для расчета течений газов в микроканалах сложных технических систем. Многомасштабный подход сочетает решения уравнений квазигазодинамики (КГД) и молекулярной динамики (МД). Представлена параллельная реализация подхода, основанная на методах расщепления по физическим процессам и разделения областей. Реализация ориентирована на использование вычислительных систем с центральной и гибридной архитектурами. Разработанные параллельные алгоритмы обладают хорошей масштабируемостью. Полученные результаты подтвердили эффективность разработанного подхода. С его помощью методами МД были получены основные коэффициентные зависимости для КГД-системы, произведен расчет трехмерного течения., This paper is devoted to a parallel implementation of multiscale approach to the numerical study of gas flows in microchannels of complex technical systems. The multiscale approach combines the solutions of quasigasdynamic (QGD) equations and molecular dynamics (MD) equations. The proposed parallel implementation of this approach is based on the method of splitting into physical processes and the domain decomposition method. The implementation is oriented for using computer systems with central and hybrid architectures. The developed parallel algorithms show a good scalability. The obtained results confirm the efficiency of the approach under consideration. This approach was used to find the basic coefficient dependences for the QGD system by MD methods and to study a three-dimensional gas flow numerically., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 2 2016

В рамках широко распространенной технологии Augmented Reality обсуждается возможность контроля подлинности защитных оптических меток на основе бинарных нанооптических элементов. С помощью смартфона фотографируют изображение защитной метки. Полученное изображение интерпретируется как дифракционный оптический элемент. В приближении Френеля рассчитывают изображение, формируемое дифракционным оптическим элементом, которое используют для идентификации подлинности защитной метки. Защитная метка представляет собой фазовый оптический элемент, глубина микрорельефа которого не превышает 0.5 мкм. Нанооптические элементы изготавливаются с помощью электроннолучевой литографии. Разработанные нанооптические элементы устойчивы к частичному повреждению микрорельефа и могут быть использованы для идентификации банкнот, документов и др., This paper deals with optical security label identification technology as a part of augmented reality technology. Security labels are based on binary nanooptical elements and are photographed using a smartphone. Photographed images are interpreted as diffractive optical elements. Optical images formed by these diffractive elements are computed using the Fresnel approximation. These images are used to identify the security labels. A security label consists of a phase optical element whose microrelief height is of no more than 0.5 $\mu$m. Nanooptical elements are manufactured using electron-beam lithography. The optical security labels are resistant against microrelief damages and can withstand partial loss of an image. The optical elements developed can be used to protect and identify banknotes, documents, etc., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2016

Обобщаются данные о применении различных параллельных вычислительных архитектур при численном моделировании задач ламинарно-турбулентного перехода (ЛТП). Обычно анализ ЛТП основан на рассмотрении статистических параметров: корреляций пульсаций скорости, энергетических спектров и др. Анализ ЛТП как нелинейной динамической системы в дополнение к уже указанному анализу основан на анализе собственных значений якобиана, вида аттракторов систем в фазовом пространстве и собственных значений матрицы монодромии. В результате строятся бифуркационные сценарии и диаграммы. Это дает возможность проследить механизм усложнения для рассматриваемых задач при ЛТП при изменении выбранных параметров (чисел Рейнольдса, Маха, Фруда и др.). Рассмотрение процесса ЛТП с точки зрения нелинейных динамических систем накладывает требования точности и быстродействия используемых алгоритмов решения задач. Начиная с 2008 г. в наших работах используются GPU- и multiGPU-архитектуры совместно с CPU. За это время было рассмотрено восемь постановок задач ЛТП. Для численного моделирования применялись различные методы высокого порядка. В настоящей статье для каждого класса методов рассматриваются характерные вычислительные операции, приводятся использованные библиотеки и выполняется сравнение эффективности разработанных алгоритмов и примененных библиотек с CPU-версиями кода, а также между собой. Показано, что в среднем на один GPU по сравнению с CPU ускорение варьируется от 5 до 35 раз. В связи со сложностью алгоритмов при MPI CPU- и multiGPU-подходах ускорение редко бывает линейным и оно пропорционально степенной функции с показателем 0.78-0.81. Для multiGPU-анализа алгоритмы тестировались на пяти GPU. Обсуждаются результаты при гибридном применении CPU+multiGPU для одной из задач., The use of various parallel computational architectures for the direct numerical simulation (DNS) of laminar-turbulent transition problems (LTTPs) is summarized. Usually, DNS results are analyzed on the basis of a set of statistical parameters: pulsation velocities correlations, energy spectra, etc. When a dynamical system analysis approach is applied to DNS results, it is necessary to evaluate additional parameters: eigenvalues of Jacobi matrices, phase space attractors, and eigenvalues of monodromy matrices, etc. This allows one to present results as bifurcation scenarios and diagrams and bring up more details concerning LTTP scenario as functions of bifurcation parameters (e.g., Reynolds, Mach, and Froude numbers). This problem is computationally expensive and algorithms are complex. This brings up more demands on the hardware efficiency and software algorithm optimization. We are using GPU and multiGPU together with CPU architectures since 2008 for this kind of DNS. We considered eight different LTTPs since then. Various high-order methods were applied. In this paper we show typical computational operations for each class of problem. We illustrate the application of libraries and algorithms, perform efficiency benchmarking across GPUs and with CPU versions. It is shown that in general one GPU is 5 to 35 times faster than CPU. The acceleration is worse than linear and is proportional to a power function with an exponent between 0.78 and 0.81. We use five GPUs for multiGPU and show CPU+multiGPU efficiency for one of the problems under consideration., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 1 2016

Применение современных оптико-электронных приборов расширяет возможности исследований в области экспериментальной механики жидкостей. Методы вычислительной фотографии за счет использования основанных на ней устройств постепенно проникают в различные области науки и техники. Камера светового поля может использоваться для регистрации трехмерных распределений скорости в потоках жидкости и газа там, где расположение нескольких панорамных оптических сенсоров затруднено за счет ограничения оптического доступа и вибраций. В работе исследованы возможности пленоптической системы, состоящей из доступной на рынке промышленной камеры светового поля применительно для диагностики течений жидкости и газа. Предложен и протестирован новый программный алгоритм для вычисления карты глубины регистрируемой измерительной области. Согласно полученным результатам, пространственное разрешение метода по глубине при использовании 11 мегапиксельного сенсора достигает 1/40 от глубины резкости оптической системы. Указанный метод был использован для измерения 3D-полей скорости турбулентной струи внутри щелевого канала по всей его глубине. В будущем количество задач, в которых целесообразно использование пленоптических устройств с высоким пространственным разрешением, будет расти., Application of modern optoelectronic devices extends research in the field of experimental fluid mechanics. The methods of computational photography gradually penetrate into the various fields of science and technology due to using devices based on these methods. A light-field camera can be used to register a three-dimensional velocity distribution in fluid flows where the location of several panoramic optical sensors is difficult because of restrictions in an optical access and vibrations. in this paper we study the possibility of using a plenoptic system consisting of an industrial light-field camera to diagnose liquid and gas flows. A new software algorithm for computing a depth field of a measurement area is proposed. According to the obtained results, the spatial resolution of the method by depth reaches 1/40th of the depth of the field of the optical system when using 11 MP sensor. This method was used to measure 3D velocity fields of a turbulent jet inside a slot channel throughout its depth. In the future, the number of applications will grow for the cases where the use of plenoptic devices with high spatial resolution is appropriate., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2016

Статья посвящена проблемам построения перспективных реконфигурируемых вычислительных систем c жидкостным охлаждением для программируемых логических интегральных схем семейства Xilinx Virtex UltraScale. Рассматриваются архитектура, компоновка и сравнительные технические характеристики систем погружного жидкостного охлаждения. Приводятся результаты расчетов, макетирования и экспериментальной проверки основных технических решений созданного вычислительного модуля нового поколения для построения высокопроизводительных вычислительных систем с жидкостным охлаждением с производительностью 1 Пфлопс в стандартном вычислительном шкафу высотой 47U при потребляемой мощности 150 кВт. Реконфигурируемая вычислительная система с жидкостным охлаждением обеспечивает существенное преимущество по таким технико-экономическим параметрам, как реальная и удельная производительность, энергоэффективность, массогабаритные характеристики и другим по сравнению с аналогичными системами., The paper deals with problems of design of promising reconfigurable computer systems with liquid cooling for Xilinx Virtex UltraScale FPGAs. Architecture, placement and comparative technical parameters of systems with immersion liquid cooling are considered. Results of design, prototyping and experimental testing of the principal technical solutions of the designed computational module of the next generation are discussed. The computational module is intended for the creation of high-performance computer systems with liquid cooling with performance of 1 PFlops in a standard 47U computer rack with power of 150 kWatt. The reconfigurable computer system with liquid cooling provides considerable advantage in such technical and economical parameters as the real performance and the specific performance, power efficiency, mass and dimension parameters, etc. in comparison with similar systems., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 1 2016

Статья посвящена разработке, программной реализации и количественной оценке свойств вычислительного алгоритма метода декартовых сеток для математического моделирования распространения ударных волн в областях сложной формы с криволинейными границами. Представлено подробное описание вычислительного алгоритма, основанного на методе "h-ячеек''. Работоспособность алгоритма продемонстрирована на задачах о регулярном и простом маховском отражении ударной волны от клина, а также о взаимодействии ударной волны с цилиндром., This paper is devoted to the development, software implementation, and quantitative estimation of a numerical algorithm based on the Cartesian grid method for the mathematical modeling of shock wave propagation in domains of complex shape with curvilinear boundaries. A detailed description of an algorithm based on the method of ``h-boxes'' is given. The efficiency of the algorithm is analyzed on the problems of regular and single Mach reflection of a shock wave from a wedge as well as on the problem of shock wave/cylinder interaction., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2016

Представлены результаты экспериментов по добавлению биграмм в тематические модели и учету сходства между ними и униграммами. Предложен новый алгоритм PLSA-SIM, являющийся модификацией алгоритма построения тематических моделей PLSA (Probabilistic Latent Semantic Analysis). Предложенный алгоритм позволяет добавлять биграммы и учитывать сходство между ними и униграммными компонентами. Исследована возможность применения ассоциативных мер для выбора и последующего включения биграмм в тематические модели. В качестве текстовых коллекций взяты русскоязычная подборка статей из электронных банковских журналов, английские части корпусов параллельных текстов Europarl и JRC-Acquiz и англоязычный архив исследовательских работ по компьютерной лингвистике ACL Anthology. Выполненные эксперименты показывают, что существует подгруппа тестируемых мер, упорядочивающих биграммы таким образом, что при последующем их добавлении в предложенный алгоритм PLSA-SIM качество получающихся тематических моделей значительно повышается. Предложен новый итеративный алгоритм PLSA-ITER без учителя, позволяющий добавлять наиболее подходящие биграммы. Эксперименты показывают дальнейшее улучшение качества тематических моделей по сравнению с исходным алгоритмом PLSA., The results of experimental study of adding bigrams and taking account of the similarity between them and unigrams are discussed. A novel PLSA-SIM algorithm based on a modification of the original PLSA (Probabilistic Latent Semantic Analysis) algorithm is proposed. The proposed algorithm incorporates bigrams and takes into account the similarity between them and unigram components. Various word association measures are analyzed to integrate top-ranked bigrams into topic models. As target text collections, articles from various Russian electronic banking magazines, English parts of parallel corpora Europarl and JRC-Acquiz, and the English digital archive of research papers in computational linguistics (ACL Anthology) are chosen. The computational experiments show that there exists a subgroup of tested measures that produce top-ranked bigrams in such a way that their inclusion into the PLSA-SIM algorithm significantly improves the quality of topic models for all collections. A novel unsupervised iterative algorithm named PLSA-ITER is also proposed for adding the most relevant bigrams. The computational experiments show a further improvement in the quality of topic models compared to the PLSA algorithm., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 2 2015

Суперкомпьютерные вычисления экзафлопсной эры будут неизбежно ограничены энергоэффективностью. Сегодня в качестве возможных кандидатов для этих целей рассматриваются различные микропроцессорные архитектуры. Недавно микропроцессоры с архитектурой ARM в своем развитии достигли момента, когда уже можно серьезно обсуждать их применение для высокопроизводительных вычислений. В настоящей статье представлен анализ эффективности последних версий ARM-микропроцессоров и их производительности для задач классической молекулярной динамики., Supercomputing of the exascale era is inevitably limited by power efficiency. Nowadays, different CPU architectures are considered as possible choices for these purposes. Recently, the development of ARM processors has come to the point when their floating point performance can be seriously considered for a range of scientific applications. In this paper, we present an analysis of the floating point performance of the latest ARM cores and their efficiency for the algorithms of classical molecular dynamics., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2015

Рассматривается задача переупорядочения строк и столбцов симметричной положительно определенной разреженной матрицы с целью уменьшения числа ненулевых элементов в факторе Холецкого. Данная задача является NP-полной. Для ее решения используются эвристические алгоритмы, основанные на применении методов теории графов. Предлагается параллельный алгоритм переупорядочения для вычислительных систем с общей памятью. В качестве базы для распараллеливания используется модификация многоуровневого метода вложенных сечений, ранее реализованная авторами в виде библиотеки с открытым исходным кодом MORSy. Основная идея распараллеливания заключается в организации и параллельной обработке очереди задач, которые могут быть решены независимо. В отличие от широко распространенных аналогов, применяющих MPI для организации параллелизма как на распределенной, так и на общей памяти, предложенный алгоритм использует возможности стандарта OpenMP 3.0. Вычислительные эксперименты выполнены на симметричных положительно определенных матрицах из коллекции университета Флориды. Показано, что параллельный код MORSy дает сходные или лучшие перестановки в сравнении с библиотекой ParMETIS для всех тестовых матриц, кроме одной, в большинстве случаев опережая ParMETIS по времени работы. Программная реализация выполнена в виде библиотеки с открытым исходным кодом и доступна для скачивания на сайте Приволжского научно-образовательного центра суперкомпьютерных технологий., This paper deals with the NP-complete problem of finding a symmetric positive definite sparse matrix ordering that minimizes the Cholesky factor fill-in. For this purpose, heuristic approaches based on graph algorithms are applied. A new parallel ordering algorithm for shared-memory computing systems is proposed. The modified multilevel nested dissection algorithm from the recently presented MORSy library is used as a basis for ordering. The parallel processing is done in a task-based fashion. It uses the OpenMP 3.0 task parallelism relying on the dynamic load balancing implemented during the OpenMP runtime. The numerical experiments were performed using a number of symmetric positive definite matrices from the University of Florida Sparse Matrix Collection. The experimental results show the competitiveness of the proposed implementation on shared memory systems compared to the widely used ParMETIS library. In our experiments, the parallel MORSy version provides a better ordering than ParMETIS on all but one matrix in terms of the Cholesky factor fill-in and outperforms ParMETIS in most cases. The parallel MORSy version is publicly available from the Supercomputing Center of Lobachevsky State University of Nizhni Novgorod., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 3 2015