Статьи журнала - Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика
Все статьи: 316
Статья научная
The applying of the line-by-line recurrent method for solving systems of difference elliptic equations with nine-diagonal matrices is the subject of the article. Such matrices take place in the case of difference approximation of 2D differential problems of a higher order of accuracy on a regular grid covering the area under consideration. The technology of the so-called compensatory transform which allows replacing the initial nine-diagonal matrix of the system with the five-diagonal one is offered in the article, due to the fact that originally the line-by-line recurrent method was designed for solving systems of difference equations with a five-diagonal matrix. The efficiency of this technology is analyzed by comparing the solutions of the test boundary value problem in a unit square. The solutions are found both with the help of different implementations of the compensatory transform technology and by other modern highly efficient iterative methods for solving the systems of difference equations. The problem is solved on the sequence of grids from coarse (501х501) to fine (4001х4001) nodes. The accuracy of the solution convergence is determined by the relative norm of the residual, which is equal to 10-12 in the present work. It is shown that the line-by-line recurrent method retains its high efficiency over the entire range of the grids under consideration despite the use of the intermediate technology of the compensatory transform.
Бесплатно
Unified approach for provision of supercomputer center resources
Статья научная
Within one supercomputer center, there may be several computing systems with different architectures and principles of work with the end user. When organizing user access, it is necessary to fully describe the systems for the coordinated choice of tasks, software packages and hardware by the user, as well as to take into account the details of quotas, authentication, and launching applications on each of the individual machines within a single workflow. In this paper, we propose an approach to the provision of resources of a supercomputer center, where a user, using a complete description of computing systems, creates requests for access with desirable quotas. The approach describes the life cycle of access. When an access state transition occurs, it is supposed to interact with computing systems through their interfaces without deep integration. An overview of widely used approaches to quoting and organizing access is given, and the proposed approach is implemented as a software module for the Octoshell supercomputer center support system and tested on a computing system managed by the OpenNebula cloud computing platform.
Бесплатно
Virtualization of heterogeneous HPC-clusters based on OpenStack platform
Статья научная
The paper addresses to the problem of integration of heterogeneous computing clusters to the united environment based on a virtualization technology. OpenStack software is selected as a platform for managing the virtual environment. The OpenStack platform provides a wide range of components and solutions to a functional interaction with different hypervisors. These include KVM, XEN, ESXi, QEMU and other systems. In addition to the OpenStack platform, we developed a specialized hypervisor shell. It helps to start virtual machines using queues of the traditional resource management systems, such as PBS, SLURM, LSF, or SGE, that are used on clusters of a center of collective usage. The developed model of the resource allocation for virtual machines allowed us to use the knowledge about job requests, resource characteristics and current state of the environment, and the expertise of it administrators. The realized tools provide the capability for the “painless” integration of heterogeneous clusters with the preinstalled local resource managers for creating the virtual cluster with the required configuration. Extensive modeling shows that the hypervisor shell can improve efficiency of integrated environment nodes through reallocating virtual machines to queues of the traditional resource management systems.
Бесплатно
Статья научная
Описывается интернет-ориентированная информационно-вычислительная система (ИВС) WWW-MINCRYST, предназначенная для работы с кристаллическими структурами минералов, их синтетических аналогов и элементов. Основными компонентами ИВС являются собственно база данных (более 8000 записей для 3000 уникальных фаз), снабженная комплексом средств поиска и выбора информации, средствами мультимедийного представления информации (полиэдрические и шаровые интерактивные структуры, спектры и т.п.), возможностями обработки спектральной информации, в том числе с использованием пользовательских данных. ИВС размещена по адресу http://mincryst.iem.ac.ru и доступна пользователям без ограничений.
Бесплатно
Статья научная
Автоматическое отображение последовательных программ на вычислительные системы с распределенной памятью может потребовать предварительного преобразования программ, ориентированного на данный класс систем. Использование системы САПФОР для распараллеливания прикладных программ позволило выделить преобразования, выполнение которых может быть автоматизировано. В статье представлены преобразования, повышающие возможность эффективного распараллеливания программ за счет устранения причин, препятствующих распараллеливанию циклов. Выполнение данных преобразований позволило автоматизировать получение последовательной реализации, эффективно отображаемой на современные кластеры автоматически распараллеливающим компилятором системы, для задачи гидродинамики.
Бесплатно
Автоматизированное проектирование и исполнение эффективных программ для численных алгоритмов
Статья научная
Проектировать эффективные параллельные программы для многопроцессорных архитектур сложно, так как нет четких формальных правил, которых необходимо придерживаться. Для решения этой проблемы при реализации численных алгоритмов может применяться концепция Q-детерминанта. Данная теория позволяет проводить автоматизированный анализ ресурса параллелизма алгоритма, автоматизированное сравнение ресурсов параллелизма алгоритмов, решающих одну и ту же алгоритмическую проблему, проектировать эффективные программы для реализации алгоритмов с помощью специально разработанного метода проектирования, повысить эффективность реализации численных методов и алгоритмических проблем. Результаты, полученные на основе концепции Q-детерминанта, представляют собой один из вариантов решения проблемы эффективной реализации численных алгоритмов, методов и алгоритмических проблем на параллельных вычислительных системах. Однако пока остается не решенной фундаментальная проблема автоматизированного проектирования и исполнения для любого численного алгоритма программы, реализующей алгоритм эффективно. В статье описана разработка единой для численных алгоритмов программной системы проектирования и исполнения Q-эффективных программ - эффективных программ, спроектированных с помощью концепции Q-детерминанта. Система предназначена для использования на параллельных вычислительных системах с общей памятью. Она состоит из компилятора и виртуальной машины. Компилятор преобразует представление алгоритма в форме Q-детерминанта в исполняемую программу, использующую ресурс параллелизма алгоритма полностью. Виртуальная машина исполняет программу, полученную с помощью компилятора. В статье также приведено экспериментальное исследование созданной программной системы с применением суперкомпьютера «Торнадо ЮУрГУ».
Бесплатно
Статья научная
В данной работе рассматривается актуальная на данный момент проблема генерации набора нечетких правил для системы нечеткого вывода Мамдани на основе числовых данных, получаемых в процессе обучения управляемой системы. Предлагаемый в статье подход к решению данной проблемы базируется на алгоритмах четкой и нечеткой кластеризации, таких как алгоритм горной кластеризации и алгоритм Густафсона-Кесселя. Он позволяет значительно упростить процесс формирования набора нечетких правили минимизировать участие человека в этом процессе, позволяя автоматически подбирать количество правил,а также определять все необходимые параметры каждого из них. Для реализации предложенного подхода были написаны две компьютерные программы. Первая из них собирает числовые данные при управлении человеком гусеничной тележкой. На основе собранных данных эта программа строит базу нечетких правил управления гусеничным шасси. Эта база нечетких правил и ее компьютерная реализация в дальнейшем используется во второй программе для автоматизированного управления мобильным роботом на гусеничном шасси на плоскости при помощи изменения силы тяги каждой из гусениц в зависимости от положения цели,к которой робот должен приблизиться на заданное расстояние.
Бесплатно
Автоматическая генерация программ для графических процессоров по непроцедурным спецификациям
Статья научная
Рассмотрены методы и средства автоматического построения параллельных программ для графических процессоров по непроцедурной спецификации задачи, заданной на языке Норма. Приводятся алгоритмы автоматического построения программ для графических процессоров, основанные на анализе зависимостей и выявлении внутреннего параллелизма графа потока управления, полученного по программе на языке Норма. Приведены результаты применения описанных алгоритмов для создания расчетной программы с использованием технологии CUDA при решении задачи из области газодинамики и оценена производительность получающихся параллельных программ.
Бесплатно
Статья научная
В работе исследовано применение модели ARIMA прогнозирования временных рядов для анализа открытых данных о распространении коронавирусной инфекции в ряде регионов Российской Федерации. Рассматривается возможность применения существующих методов и алгоритмов языка программирования для статистической обработки данных R, приводятся алгоритмы подбора параметров модели ARIMA. Разработан и опубликован скрипт на языке программирования R, позволяющий осуществить с помощью стандартной библиотеки auto.arima прогнозирование суммарных случаев заражения и летальных исходов на выбранный промежуток времени. В работе показано, что параметры модели различны для временных рядов разной длины, для различных регионов, кроме того, параметры модели меняются с течением времени. Исследован имеющийся инструментарий языка R и показано, что существуют наборы данных для которых он не позволяет получить параметры модели, дающей наименьшую погрешность. Исследована частота переобучения модели, приведены данные об изменении параметров модели для временных рядов разной длины. Исследование случаев ошибки автоматического подбора параметров модели является темой для дальнейших исследований. Приведена содержательная интерпретация полученных данных. Проведено сравнение прогнозов, полученных в конце октября 2020 г. и актуальных данных на середину ноября 2020 г. Показано, что полученный прогноз позволил достаточно точно предсказать суммарное число заражений и летальных исходов на 7-10 дней.
Бесплатно
Автоматическое отображение программ на процессор с ПЛИС-ускорителем
Краткое сообщение
В работе рассматривается задача автоматического отображения высокоуровневых программ на процессор с ПЛИС-ускорителем. Для такого отображения разрабатывается и используется генератор HDL-кода из внутреннего представления распараллеливающей системы.
Бесплатно
Автоматическое отображение программ на языке Фортран на кластеры с графическими процессорами
Статья научная
В статье рассматриваются результаты использования системы автоматизации распараллеливания САПФОР для распараллеливания последовательных программ на кластеры с графическими ускорителями, в том числе программ с регулярными зависимостями по данным. Система переводит программу на языке Fortran в программу на языке Fortran DVMH. Полученная программа запускается на кластере. Язык Fortran DVMH, компиляторы для него и средства отладки входят в состав DVM-системы. Рассмотрены проведенные преобразования исходных программ. Получены параллельные программы, использующие различные технологии параллельного программирования. Приведены характеристики полученных текстов. Приведены экспериментальные данные об эффективности выполнения программ на графических и универсальных процессорах кластера К-100.
Бесплатно
Статья научная
Задача реконструкции неизвестных входов стохастического дифференциального уравнения исследуется с позиций подхода теории динамического обращения. Рассматривается постановка, в которой одновременное восстановление возмущений в детерминированном и стохастическом членах уравнения проводится на основе дискретной информации о некотором количестве реализаций случайного процесса. Задача сводится к обратной задаче для системы обыкновенных дифференциальных уравнений, которым удовлетворяют математическое ожидание и ковариационная матрица исходного процесса. Разработан программно-ориентированный алгоритм решения, основанный на конструкциях теории позиционного управления с моделью; получена оценка его точности относительно количества доступных измерению реализаций. Предложена программная процедура настройки параметров алгоритма для получения наилучшего результата аппроксимации различных возмущений, удовлетворяющих априорным ограничениям, в конкретной динамической системе. Искомые зависимости параметров алгоритма от количества измеряемых реализаций определяются эмпирически через решение специальной экстремальной задачи, в которой минимизируется отклонение выхода алгоритма от тестовой функции. Для оптимизации времяемкого процесса адаптации алгоритма к системе, предполагающего моделирование большого числа независимых траекторий стохастического уравнения, используется распараллеливание вычислений. Приведен модельный пример, иллюстрирующий предложенные конструкции. Рассмотрена система, упрощенно описывающая популяционную динамику двух взаимодействующих видов. Представлены результаты расчетов и характеристики эффективности распараллеливания.
Бесплатно
Алгоритм полиномиальной сложности для поиска соответствующих точек на основе эпиполярной геометрии
Статья научная
Задача установления соответствий между изображениями точек на различных снимках является основой многих базовых алгоритмов компьютерного зрения. Существуют несколько подходов к решению данной задачи: на основе дескрипторов, на основе эпиполярной геометрии и комбинированные методы. В настоящей статье рассматриваются методы поиска соответствующих точек, основанные на эпиполярной геометрии, применительно к разрабатываемой авторами фотограмметрической измерительной системе (ФИС), использующей искусственные световозвращающие однотипные круговые маркеры (мишени) в роли контрольных точек. В качестве математической модели для задачи нахождения соответствий авторами предлагается использовать взвешенный многодольный неориентированный граф, множество вершин в котором соответствует множеству изображений искусственных маркеров (мишеней) на снимках, а множество ребер определяет множество изображений, взаимно удовлетворяющих эпиполярным ограничениям. Представлено теоретически точное решение задачи на основе суперклики. Выполнена оценка временной сложности решения задачи через суперклику; показано, что данный подход является экспоненциально сложным. Рассмотрены варианты применения различных эвристических алгоритмов установления соответствий между точками. Подобные алгоритмы не всегда приводят к точному результату, однако способны сформировать приближенное решение за практически приемлемое время. Благодаря особой архитектуре, разработанной авторами ФИС, становится возможным использование быстрых приближенных алгоритмов; возможные неточности будут автоматически нейтрализованы на дальнейших этапах работы ФИС. Подобный подход позволяет восстанавливать точную трехмерную структуру измеряемой сцены за приемлемое время. Авторами предложен новый полиномиальный параллельный алгоритм поиска соответствующих точек. Оценена временная сложность разработанного алгоритма (полином 4-й степени). Выполнена сравнительная оценка производительности и эффективности нового алгоритма, в качестве алгоритмов сравнения выступают более ранние алгоритмы авторов, а также алгоритм H.-G. Maas. Новый алгоритм превосходит по производительности все конкурирующие алгоритмы.
Бесплатно
Статья научная
В статье предлагается алгоритм построения интегральной характеристики изменения качества системы на основании регистрируемых измерений, который обеспечивает решение задачи выделения сигнала в многомерном массиве данных в условиях априорной неопределенности о свойствах сигнала на основании задаваемого отношения сигнал/шум. Построение латентной интегральной характеристики изменения качества системы на основе статистических показателей для ряда последовательных наблюдений производится на основе метода главных компонент с учетом наличия шума в измеряемых данных (ОСШ-алгоритм). В отличие от классического метода главных компонент, где информативность вычисленной интегральной характеристики задается априорно и обеспечивается выбором числа главных компонент, в предлагаемом алгоритме информативность решения оценивается апостериорно на основании дисперсионного критерия и выбранного параметра отношения сигнал/шум. С помощью предложенного алгоритма построены интегральные индикаторы качества жизни субъектов Российской Федерации за 2007-2014 годы.
Бесплатно
Алгоритм репрезентативного сэмплинга для систем баз данных на основе фрагментного параллелизма
Статья научная
Сэмплинг является популярным подходом к обработке сверхбольших баз данных в широком спектре приложений, связанных с интеллектуальным анализом данных, построением гистограмм, приблизительное исполнение запросов и др. Использование сэмпла вместо оригинальной базы данных может уменьшить точность результатов, но компенсируется сокращением времени выполнения обработки. Репрезентативный сэмплинг позволяет сохранить в сэмпле определенные характеристики базы данных. Однако существующие алгоритмы репрезентативного сэмплинга не могут быть применены для параллельных систем баз данных, поскольку не учитывают характеристики данных, распределяемых по вычислительным узлам кластерной системы. В данной статье предлагается алгоритм репрезентативного сэмплинга для параллельных реляционных систем баз данных на основе фрагментного параллелизма. Приведены результаты вычислительных экспериментов над предложенным алгоритмом, показавшие адекватное сохранение репрезентативности свойств базы данных, распределенной по узлам кластерной системы.
Бесплатно
Алгоритм соединения циклов для метрической задачи коммивояжера на максимум
Статья научная
Задача коммивояжера на максимум имеет ряд практических приложений, например, при сжатии произвольных данных и анализе последовательностей ДНК. При том, что задача коммивояжера на максимум является менее разработанной, чем задача коммивояжера на минимум, для ее решения существуют эффективные приближенные алгоритмы. В статье приведены оценки точности лучших на сегодняшний день алгоритмов для приближенного решения метрической задачи коммивояжера на максимум, и предлагается еще один алгоритм приближенного решения задачи коммивояжера на максимум, состоящий из поиска 2-фактора максимального веса в заданном графе, а затем применения операции оптимального соединения циклов в один гамильтонов цикл. Приведено доказательство, что для метрической задачи коммивояжера на максимум отношение длины найденного алгоритмом гамильтонова цикла к максимально возможной длине гамильтонова цикла не менее 5/6. Вычислительная сложность алгоритма не превышает O(|V|3). Проведено тестирование качества алгоритма на случайно сгенерированных матрицах стоимостей с евклидовой метрикой. Аналитическое и численное исследование алгоритма объединения циклов позволило выдвинуть гипотезу об асимптотической точности алгоритма на классе метрических задач коммивояжера на максимум.
Бесплатно
Алгоритм фрактального поиска в реляционных базах данных
Статья научная
Статья посвящена вопросам разработки алгоритмов фрактального анализа реляционных баз данных. Дается обзор и сравнительный анализ известных приложений теории фракталов к обработке данных. Предложен новый алгоритм фрактального поиска в реляционной базе данных, позволяющий обнаруживать повторяющиеся группы данных. Приведена общая схема алгоритма. Рассмотрена реализация для СУБД Oracle. Представлена реализация с использованием модели распределенных вычислений MapReduce. Приводятся примеры использования разработанного алгоритма для сжатия и анализа содержимого базы данных
Бесплатно
Алгоритмы решения СЛАУ на системах с распределенной памятью в применении к задачам электромагнетизма
Статья научная
Рассматриваются различные аспекты моделирования гармонических электромагнитных полей на кластерах. Основная вычислительная сложность задачи заключается в решении систем линейных алгебраических уравнений (СЛАУ), возникающих в результате конечно-элементных аппроксимаций соответствующих краевых задач электромагнетизма элементами Неделека различных порядков. Рассмотрены эффективные и экономичные подходы к декомпозиции расчетной области и матрицы системы. Решение распределенных СЛАУ осуществляется итерационными методами в подпространствах Крылова с использованием аддитивного метода Шварца в качестве предобуславливателя. Для повышения эффективности алгоритмов итерации осуществляются в подпространствах следов. Реализованные решатели используют MPI для организации обмена данными. Решение систем в подобластях осуществляется при помощи прямого решателя PARDISO из библиотеки Intel® MKL. Результаты серии численных экспериментов на модельных и практических задачах демонстрируют эффективность предлагаемых алгоритмов.
Бесплатно
Анализ исполнения фрагментированных программ на основе факторов Slow
Статья научная
При исполнении параллельных программ, основанных на парадигме параллелизма задач, требуется решать ряд проблем, таких как выбор порядка запуска задач с учетом зависимостей между ними, распределение данных и задач по параллельным процессам, балансировка нагрузки на ресурсы. Эти проблемы относятся к области системного параллельного программирования, и их решение, как правило, обеспечивается специальной исполнительной системой. От качества решения этих проблем, а также от структуры и свойств прикладного алгоритма, лежащего в основе параллельной программы, зависит получаемая производительность. Если производительность программы недостаточна, то требуется ее оптимизация, а для этого нужно знать те причины («узкие места»), которые ограничивают ее производительность. Для определения узких мест программы обычно применяется профилирование, т.е. сбор некоторых характеристик исполнения, которые могут указать на источник проблемы. Однако обычные широко используемые средства профилирования параллельных программ не позволяют дать ответ в требуемых понятиях из-за сложности анализа асинхронного исполнения множества задач, а также из-за неспособности выделить в исполняющейся программе прикладную (множество задач) и системную (исполнительная система) компоненты. Поэтому для таких программ требуется разработка новых методов профилирования и анализа. В статье рассматривается проблема получения «понятных» характеристик выполнения параллельных программ на основе параллелизма задач для анализа производительности и оптимизации. Предлагается количественно оценить степень влияния следующих факторов: нехватка работы (Starvation), передача данных (Latency), накладные расходы (Overhead) и конфликт при доступе к общим ресурсам (Waiting for contention resolution). Представлен алгоритм получения соответствующих характеристик для системы фрагментированного программирования LuNA, а также способ их анализа для оптимизации LuNA-программ. Корректность подхода продемонстрирована на ряде синтетических экспериментов. Показано применение подхода к анализу «реальной» программы численного моделирования.
Бесплатно
Анализ механизма коллективного поведения на основе нечеткой логики
Статья научная
В предлагаемой работе рассматривается простейший механизм поведения коллектива как совокупность индивидуумов, каждый из которых, принимая решения по фиксированному вопросу, руководствуется как личным отношением к рассматриваемой проблеме, так и оценкой отношения других членов коллектива к данному вопросу. Например, индивидуум может решать: заниматься ли ему данным родом деятельности, вступать ли в данную общественную организацию, участвовать ли в данном мероприятии, голосовать ли за данное предложение и т.д. Во всех этих случаях индивидууму предстоит решать в сущности одну проблему: перейти ему в некоторое данное состояние или нет. Личное отношение каждого индивидуума к рассматриваемой проблеме и оценка им отношения других членов коллектива к данному вопросу носят неточный, расплывчатый характер. В статье принят подход, когда эта неточность рассматривается в рамках теории нечетких множеств и операций с ними. Исследуется поведение некоторых типов коллективов.
Бесплатно
