Search

В работе представлены три итерационных алгоритма быстрого преобразования Фурье с прореживанием по времени, имеющие алгоритмическую сложность 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

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

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

Алгоритм 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

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

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

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