Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi
Статьи журнала - Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика
Все статьи: 329
Статья научная
Рассматривается новый способ организации высокоточных вычислений с плавающей точкой, позволяющий распараллеливать арифметические операции вплоть до уровня отдельных цифр многоразрядных мантисс путем использования модулярно-позиционного формата представления данных. Основная концепция данного формата заключается в представлении мантисс чисел в многомодульной системе остаточных классов (СОК), а порядков - в позиционной системе счисления. Мантиссы сопровождаются позиционной характеристикой, которая способствует реализации эффективных алгоритмов выполнения немодульных операций в СОК, таких как деление (частный случай) и округление. На основе данного подхода разрабатывается программное решение High Precision Digit-Parallel Solver (HPDP-Solver). Комплекс HPDP-Solver может быть гибко настроен на конфигурацию конкретной машины, в результате чего обеспечивается наиболее эффективное использование ее ресурсов. В результате экспериментального исследования быстродействия пакета HPDP-Solver были получены результаты, доказывающие его преимущества при решении высокоточных численных задач перед имеющей мировую известность позиционной библиотекой GNU Multiple Precision Arithmetic Library. Пакет HPDP-Solver может быть применен при решении задач, которые предъявляют особо высокие требования к вычислительной точности.
Бесплатно
Статья научная
Проведен сравнительный анализ вычислительной эффективности и масштабируемости молекулярной динамики (МД), реализованной в пакете AMBER, на реальных биологических системах с применением классического силового поля FF14SB с 4-центровой моделью воды TIP4P-Ew, а также нового многообещающего поля FF15IPQ с 3-центровой моделью воды SPC/Eb. Были использованы классические процессоры Intel Xeon E5-2697 v3, а также GPU ускорители Tesla K40 (архитектура Kepler) и P100 (Pascal). Уменьшение количества атомов в ячейке на 25-31 % в результате использования 3-центровой модели растворителя ускоряет расчет МД до 63% и ухудшает масштабируемость до 11 %. При этом полученные результаты могут качественно отличаться, что говорит о необходимости совместного использования разных силовых полей при изучении биологических систем. Использование GPU-ускорителей как альтернативы классическим CPU позволяет существенно увеличить длину траектории в повседневной практике.
Бесплатно
Направленные сплайны и их использование для сглаживания выбросов и изломов интерполянта
Статья научная
Сформулирован и предложен метод построения направленного кубического сплайна для набора точек на плоскости. Проведено сравнение сплайна с B-сплайном Шёнберга, сплайнами Акимы и Катмулла-Рома. Показано, что для неравноотстоящих точек в сравнении с B-сплайном он дает значительно меньшие выбросы и практически лишен сильных изломов, которые свойственны сплайнам Акимы. Сплайн не дает петель и осцилляций, которые являются характерным недостатком параметрических сплайнов, в частности, эрмитовых, к числу которых относится сплайн Катмулла-Рома. Предложен быстрый метод оптимизации направляющего коэффициента сплайна, цель которой состоит в минимизации разрывов второй производной функции в ее промежуточных точках. Приведен пример оптимизации направленного сплайна третьего порядка. Также предложен направленный сплайн четвертого порядка, который лишен изломов. Сформулирован метод оптимизации направленного сплайна четвертого порядка, изложен алгоритм его оптимизации. Критериями оптимизации являются длина сплайна и наименьшее расстояние между его глобальными максимумом и минимумом. Показано, что в сравнении с сплайна Шёнберга направленный сплайн четвертого порядка имеет меньшие выбросы. Предложен метод автоматического притупления острых пиков кривых, который можно применять ко всем типам сплайнов.
Бесплатно
Нейросетевой метод обнаружения аномалий в многомерных потоковых временных рядах
Статья научная
В статье рассмотрена задача детекции аномальных подпоследовательностей многомерного потокового временного ряда, элементы которого поступают в режиме реального времени, возникающая в настоящее время в широком спектре предметных областей: промышленный Интернет вещей, персональное здравоохранение и др. Предложен новый метод решения указанной задачи, получивший название mDiSSiD (Discord, Snippet, and Siamese Neural Network-based Detector of multivariate anomalies). Предложенный метод использует концепцию диссонанса временного ряда (подпоследовательность, имеющая наиболее не похожего на нее ближайшего соседа), обобщенную на многомерный случай. Под многомерным диссонансом понимается N-мерная подпоследовательность d-мерного временного ряда (где 1 N d), которая наиболее не похожа на все остальные подпоследовательности N-мерных временных рядов, полученных путем составления всевозможных сочетаний из d рядов по N. Детекция аномалий реализуется с помощью нейросетевой модели на основе сиамских нейросетей. Вычислительные эксперименты на реальных временных рядах из различных предметных областей показали, что метод mDiSSiD в среднем опережает по точности обнаружения аномалий передовые аналоги, использующие иные нейросетевые подходы (сверточные и рекуррентные нейронные сети, автоэнкодеры, генеративно-состязательные сети).
Бесплатно
Нейросетевой метод решения задачи мэппинга параллельных приложений
Статья научная
Статья посвящена проблеме повышения эффективности параллельных приложений. В статье предлагается подход к решению проблемы, основанный на сокращении накладных расходов, связанных с передачей данных между процессами параллельной программы во время ее выполнения на высокопроизводительной вычислительной системе. С ростом числа процессорных узлов расходы на передачу сообщений между узлами оказывают все большее влияние на производительность параллельных приложений. В связи с этим становится особо актуальной задача размещения процессов параллельной программы по вычислительным узлам суперкомпьютера, известная, как задача мэппинга. В работе предлагается новый подход к решению задачи мэппинга. Ключевой особенностью подхода является выбор коммуникационного шаблона путем фазового анализа приложения и использование сверточной нейронной сети для быстрого выбора подходящего алгоритма мэппинга, исходя из построенного коммуникационного шаблона. Для построения коммуникационных шаблонов проводится анализ поведения приложения с точки зрения передачи сообщений точка-точка между процессами параллельной программы. Временная шкала событий передачи сообщений разбивается на равные промежутки, для каждого из которых строится коммуникационных шаблон. К построенным шаблонам применяется двумерное вейвлет-преобразование Хаара для выделения признаков. Затем проводится кластеризация признаков и построение фаз во временной шкале работы приложения. Для каждой фазы строится коммуникационный шаблон, соответствующий этой фазе. Выбор подходящего алгоритма мэппинга проводится с помощью сверточной нейронной сети. Использование нейронной сети предполагает знание о свойствах коммуникационного поведения различных типов приложений и подходящих для этих типов алгоритмов мэппинга. Эти знания должны быть представлены в виде набора классов коммуникационных шаблонов (матриц) с известным для каждого класса наилучшим алгоритмом мэппинга. Нейронная сеть обучается на данном наборе классов. Обученная сеть решает задачу классификации входного коммуникационного шаблона, выбирая наиболее подходящий алгоритм мэппинга для данного параллельного приложения. В статье представлена реализация отдельных этапов метода, и продемонстрирована их работа на тестовых примерах.
Бесплатно
О вопросах распараллеливания крыловских итерационных методов
Статья научная
В работе рассматриваются математические вопросы многообразных вычислительных технологий методов распараллеливания итерационных процессов крыловского типа для решения больших разреженных симметричных и несимметричных СЛАУ, возникающих при сеточных аппроксимациях многомерных краевых задач для систем дифференциальных уравнений. Характерным примером являются конечно-элементные приближения в газогидродинамических приложениях, где в каждом узле определены пять неизвестных функций, в силу чего СЛАУ имеет мелкоблочную структуру. Основой применяемых алгоритмов является гибкий метод обобщенных минимальных невязок FGMRES с динамическими предобуславливателями аддитивного типа, представляющий собой верхний уровень двухступенчатого итерационного алгоритма Шварца. Для повышения производительности алгебраических решателей автором предлагается применение различных подходов: декомпозиции расчетной области с различными топологиями, типами краевых условий на смежных границах и размерами пересечений подобластей, методов грубосеточной коррекции и агрегации, дефляции и неполной факторизации матриц. Описываются унифицированные формулировки используемых алгоритмов, а также вопросы их вычислительной эффективности и масштабируемого распараллеливания на суперкомпьютерах гетерогенной архитектуры. Приводятся примеры технологических требований к особенностям программных реализаций библиотек параллельных алгоритмов для решения систем линейных алгебраических уравнений.
Бесплатно
О генерации случайных задач линейного программирования на кластерных вычислительных системах
Статья научная
В статье рассматривается масштабируемый алгоритм FRaGenLP для генерации больших совместных случайных задач линейного программирования произвольной размерности n на кластерных вычислительных системах. Для обеспечения совместности и ограниченности допустимой области система ограничений включает в себя 2n+1 стандартных неравенств, называемых опорными. Случайные неравенства добавляются в систему последовательно так, чтобы сохранялась совместность ограничений. Кроме этого, вводятся две метрики «похожести», которые препятствуют добавлению нового случайного неравенства, «похожего» на какое-либо из уже включенных в систему, включая опорные. Также отклоняются случайные неравенства, которые при фиксированной целевой функции не влияют на решение опорной задачи линейного программирования. Параллельная реализация алгоритма FRaGenLP выполнена на языке C++ с использованием параллельного BSF-каркаса, инкапсулирующего в проблемно-независимой части своего кода все аспекты, связанные с распараллеливанием программы на базе библиотеки MPI. Приводятся результаты масштабных вычислительных экспериментов на кластерной вычислительной системе, подтверждающие эффективность использованного подхода.
Бесплатно
О декодере мягких решений двоичных кодов Рида-Маллера второго порядка
Статья научная
Построена общая модель помехоустойчивого двоичного канала передачи данных, предназначенная для использования с различными декодерами мягких решений. Линия связи, рассматриваемая в модели, является дискретной по входу и непрерывной по выходу. На ее вход поступают дискретные сигналы из мультипликативного двоичного алфавита, а в силу искажений, действующих в линии связи, на выходе после фильтрации формируются символы из мультипликативной группы поля вещественных чисел, которые затем подаются на вход декодера помехоустойчивого кода. Мягкие и вероятностные декодеры помехоустойчивых кодов позволяют исправлять большее количество ошибок в кодовых словах, чем гарантируется минимальным расстоянием используемого кода. В работе рассмотрен вероятностный декодер мягких решений Сидельникова-Першакова для кодов Рида-Маллера второго порядка в модификации, предложенной П. Лоидрю и Б. Саккуром. Ранее эффективность этих декодеров была подтверждена с помощью имитационных экспериментов, но теоретическое обоснование отсутствовало. В настоящей работе сформулировано требование к каналу связи, названное гладкостью канала, при выполнении которого теоретически доказана корректность этого декодера в случае, когда количество ошибок на каждое кодовое слово не превосходит половины кодового расстояния. В основе доказательства лежит использование теории квадратичных форм и методов дифференциального исчисления в кольце полиномов нескольких переменных над полями Галуа.
Бесплатно
О единственности решения обратной задачи нестационарной фильтрации
Статья научная
При определении коэффициента гидропроводности нефтяного пласта методом гидродинамического прослушивания скважин возникает необходимость решения обратной задачи фильтрации. При этом важно поставить задачу таким образом, чтобы обеспечить единственность решения. В статье определяются условия, достаточные для единственности решения обратной задачи.
Бесплатно
Статья научная
Исследуется обратная задача по идентификации коэффициентов, зависящих только от времени, при источнике специального вида в линейных параболических уравнениях с точечными условиями переопределения. К исследуемым обратным задачам, в частности, приводятся краевые задачи с нелокальными (интегральными) краевыми условиями. Специфика рассматриваемой в данной работе обратной задачи заключается в том, что восстанавливаемые коэффициенты находятся при свободном члене и они зависят только от временной переменной. Предлагается методика численного решения задачи с применением метода прямых, основанная на использовании специального вида представления решения. Методом прямых задача приводится к параметрически обратной задаче относительно обыкновенной системы дифференциальных уравнений. Для ее решения предложено представление этого решения в специальном виде. Построены вспомогательные краевые задачи, которые определяют решение исходной задачи. Наиболее существенным в данной работе является то, что предлагаемый подход к численному решению исследуемой обратной задачи по идентификации коэффициентов не требует (в отличие от ранее известных методов) построения каких-либо итерационных процедур. Приводятся результаты численных экспериментов виде таблиц и графиков, полученных при решении тестовой задачи, и их анализ.
Бесплатно
О количественной модели рисков и преимуществ облачных вычислений
Статья научная
Перенос вычислительной инфраструктуры в облака стал сегодня одним из ключевых направлений оптимизации корпоративных ИТ. Обширный ряд исследований доказывает, что облачные вычисления обеспечивают экономическую выгоду, поскольку они повышают гибкость инфраструктуры и снижаю затраты на ее поддержание. Другие исследовательские работы посвящены обсуждению рисков, связанных с облаками, и их влиянию на бизнес. Однако, в большинстве случаев преимущества и риски облачных вычислений обсуждаются раздельно. В работе предложена модель, которая позволяет оценить одновременное влияние всех факторов. Идентифицированы материальные и нематериальные преимущества и риски адаптации к облаку, предложены простые правила, позволяющие оценить их количественно и построить непротиворечивую матрицу попарного сравнения. Использование предложенного метода иллюстрируется на простом примере.
Бесплатно
О некоторых вариантах метода декомпозиции областей
Статья научная
Рассматриваются алгоритмы масштабируемого распараллеливания решения сверхбольших разреженных сеточных СЛАУ, представленных в универсальных сжатых форматах, в том смысле, что их реализация осуществляется без программных ограничений на порядки алгебраических систем и на количество используемых вычислительных узлов, процессоров и/или ядер. Данная задача сводится к распределенному варианту алгебраической 3D-декомпозиции областей, в котором отсутствует чрезмерная расчетно-информационная нагрузка корневого процессора, т.е. все организуемые MPI-процессы, каждый из которых соответствует своей подобласти, являются практически равноправными. Вычислительный процесс состоит из двух основных этапов, первый из которых заключается в непосредственной автоматической декомпозиции, на основе анализа матричного портрета и формировании крупноблочного представления СЛАУ. Второй этап - это реализация крыловского итерационного алгоритма FGMRES (гибкого обобщенного метода минимальных невязок), использующего точное или приближенное обращение диагональных матричных блоков (многопоточное решение подсистем в подобластях с использованием средств OpenMP) с помощью прямого или итерационного метода соответственно. Описываемые методы реализованы в составе библиотеки алгебраических решателей Krylov. В работе приводятся некоторые оценки используемых ресурсов и особенности параллельных вычислительных технологий. Эффективность разработанных алгоритмов иллюстрируется результатами численных экспериментов по решению характерных алгебраических задач на различных конфигурациях многопроцессорной вычислительной системы.
Бесплатно
О некоторых проблемах «заоблачного» математического моделирования
Статья научная
Разработка интегрированного прикладного программного окружения для математического моделирования, ориентированного на решение междисциплинарных прямых и обратных задач широким кругом пользователей в рамках облачных вычислений на суперцентрах петафлопсного уровня ставит большой круг вопросов методического, технологического и организационного характера. В работе рассматривается концепция базовой системы моделирования (БСМ), функционирование которой предполагается в рамках вычислительного центра коллективного пользования (ВЦКП). БСМ представляет собой интегрированное программное окружение, поддерживающее все основные технологические этапы крупномасштабных вычислительных экспериментов, адаптируемое к эволюции моделей и алгоритмов решения задач, а также архитектур многопроцессорных вычислительных систем (МВС) и ориентированное на длительный жизненный цикл, обеспечиваемый эффективной генерацией пакетов прикладных программ (ППП) для конкретных предметных областей. Проблема достижения высокой суммарной производительности ВЦКП рассматривается как задача условной оптимизации расписания потока расчетных заданий с учетом используемых ресурсов конкретных приложений.
Бесплатно
О некоторых свойствах n-последовательносвязной цепи
Краткое сообщение
Вводится класс n-последовательносвязных цепей. Рассматриваются области применения n-последовательносвязных цепей, в частности задачи оптимального размещения в дискретных постановках и задачи выбора оптимального поведения в системах, описываемых управляемыми марковскими процессами. Приводятся основные характеристики п-последовательносвязной цепи, такие как число ребер, размер максимальной клики, хроматическое и цикломатическое число и др. Исследуются свойства n-последовательносвязных цепей. Определяются отношения класса n-последовательносвязных цепей к классам совершенных, триангулированных, полных и расщепляемых графов.
Бесплатно
О несуществовании простого варианта полиномиального алгоритма извлечения корня из языка
Статья научная
Для стандартной операции конкатенации слов, рассматриваемой как умножение, естественным образом определяется конкатенация языков, а на основе последней операции - степень языка и, при наличии, корень заданной степени. При описании алгоритмов построения языка, являющегося корнем степени M из заданного языка, большое значение имеют так называемые потенциальные корни: это такие слова (не языки), рассматриваемая M-я степень которых входит в заданный язык. Несложно показать, что все потенциальные корни для заданного языка строятся с помощью полиномиального алгоритма. Эта задача, по-видимому, не упрощается при рассмотрении слов и языков над 1-буквенным алфавитом - что и делается в настоящей статье. Табуированная пара потенциальных корней - это такая пара, конкатенация слов которой в язык не входит. В предыдущих публикациях на тему описания алгоритмов извлечения корней из языка возникала гипотеза, что полиномиальный алгоритм извлечения корня из языка может быть описан на основе рассмотрения только множества табуированных пар - путем перебора специально описываемых подмножеств множества потенциальных корней. В настоящей статье показывается, что подобный алгоритм (называемый «простым») невозможен, т.е. если и существует полиномиальный алгоритм извлечения корня из языка, то он (алгоритм) должен использовать некоторую дополнительную информацию.
Бесплатно
О новой версии апекс-метода для решения задач линейного программирования
Статья научная
В статье представлена новая версия масштабируемого итерационного метода линейного программирования, получившего название «апекс-метод». Ключевой особенностью этого метода является построение пути, близкого к оптимальному, на поверхности допустимой области от определенной начальной точки до точного решения задачи линейного программирования. Оптимальный путь - это путь движения по поверхности многогранника в направлении максимального увеличения или уменьшения значения целевой функции в зависимости от того, ee максимум или минимум необходимо найти. Апекс-метод основан на схеме предиктор-корректор и состоит из двух стадий: Quest (предиктор) и Target (корректор). На стадии Quest вычисляется грубое начальное приближение задачи линейного программирования. Основываясь на этом начальном приближении, на стадии Target вычисляется решение задачи линейного программирования с заданной точностью. Основная операция, используемая в апекс-методе, - это операция, которая вычисляет псевдопроекцию, являющуюся обобщением метрической проекции на выпуклое замкнутое множество. Псевдопроекция используется как на стадии Quest, так и на стадии Target. Представлен параллельный алгоритм, использующий фейеровское отображение для вычисления псевдопроекции. Получена аналитическая оценка ресурса параллелизма для этого алгоритма. Также приведен алгоритм, реализующий стадию Target, и доказана его сходимость. Описаны вычислительные эксперименты на кластерной вычислительной системе по применению апекс-метода для решения различных задач линейного программирования.
Бесплатно
Статья научная
Разработаны новые подходы к локальной модификации квазиструктурированных сеток, которые позволяют отследить неоднородности краевой задачи в расчетной области и адаптивны к криволинейным границам, а также просты в использовании и не требуют хранения большого объема данных, как это необходимо в неструктурированных сетках. Такие сетки предлагается использовать для эффективного моделирования широкого класса электрофизических приборов. Экспериментально показана необходимость локальной модификации прямоугольных сеток при расчетах в областях с криволинейной границей. Разработаны двухшаговые алгоритмы локальной модификации рассматриваемых квазиструктурированных сеток. На первом шаге проводится модификация приграничных узлов путем их сдвига на границу области по нормали к ней, а на втором - преобразование тех сеточных элементов, которые не удовлетворяют критериям качества, в качественные сеточные элементы. Разработаны специальные алгоритмы проведения таких преобразований, которые не нарушают структурированности подсеток в подобластях. Даны рекомендации по построению сеток на границах сопряжения подобластей (интерфейсе), которые содержат несогласованные сетки. Разработаны алгоритмы локальной модификации сеток на интерфейсе между подобластями, одна из которых содержит отрезок границы расчетной области. Проведены серии численных экспериментов по решению модельной задачи, результаты которых показали обоснованность предлагаемых подходов.
Бесплатно
О построении рейтинга устойчивого развития предприятий методом собственных состояний
Статья научная
В статье рассматривается решение задачи построения рейтинга устойчивого развития предприятий, методом собственных состояний. В основе методология формирования рейтинга лежит построение модели устойчивого развития предприятия, которая описывает эталонную деятельность предприятия, отвечающую требованиям устойчивого развития. Для построения рейтинга устойчивого развития предприятий предлагается использовать комплексный индикатор устойчивости, который получается путем сравнения фактической и эталонной деятельности предприятий. Оценка эффективности предлагаемой методологии демонстрируется на примере построения рейтинга нефтегазовых предприятий.
Бесплатно
О программных компонентах математического моделирования
Статья научная
Бурный рост мировых суперкомпьютерных мощностей неизбежно ведет к активизации применений математического моделирования в процессе реиндустриализации экономики. Расширение сфер использования и одновременное появление все новых вычислительных методов, сопровождающиеся эволюцией компьютерных архитектур - все это ведет к драматическому увеличению совокупного прикладного программного обеспечения, стоимость которого сравнима с ценами на многопроцессорные вычислительные системы (МВС) постпетафлопсного уровня. Такие количественные изменения влекут за собой качественный пересмотр концепции и технологических структур при создании массовых программных продуктов. Мы рассматриваем подходы к решению возникающих проблем в применении к базовой системе моделирования, ориентированной на интегрированную поддержку всех основныхэтапов крупномасштабного вычислительного эксперимента. Многообразие технологических вопросов включает обеспечение взаимодействия многоязыковых и кросс-платформенных программных компонент, внутренние и внешние интерфейсы с конвертацией множественных представлений данных, переиспользование внешних продуктов, длительный жизненный цикл системы с эволюцией функционального наполнения и адаптацией к модернизации МВС,а также масштабируемый параллелизм алгоритмов и программ.
Бесплатно
О распараллеливании решения краевых задач на квазиструктурированных сетках
Статья научная
Рассматриваются технологические аспекты решения краевых задач на предлагаемых квазиструктурированных сетках специального вида. Их особенностью является то, что и макросетка в расчетной области, и подсетки в подобластях являются структурированными и прямоугольными сетками, что обеспечивает создание экономичных структур данных и эффективное применение численных алгоритмов. В то же время, результирующая квазиструктурированная сетка является адаптивной к неоднородностям внутри области и к сложной конфигурации внешней границы, что достигается путем регулировки плотности узлов подсеток и локальной модификации сетки вблизи криволинейной границы. Существенным является то, что подсетки могут быть несогласованными. Решение ищется предлагаемым вариантом метода декомпозиции, который основан на отдельной аппроксимации краевой задачи на интерфейсе и в подобластях. Распараллеливание проводится путем группировки подобластей в объединения с целью балансировки загрузки процессоров. Приводятся оценки эффективности распараллеливания на примере решения модельной задачи на различном числе вычислительных ядер, различных сетках и объединениях.
Бесплатно
