Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi
Статьи журнала - Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика
Все статьи: 329
Применение гибридной вычислительной системы к решению прикладных задач аэрогазодинамики
Статья научная
Использованию графических ускорителей при решении прикладных задач уделяется большое внимание. В работе рассмотрены возможности использования гибридной вычислительной системы, основу которой составляют универсальные и графические процессоры.
Бесплатно
Статья научная
Работа посвящена вопросам применения графических процессоров для обработки запросов в параллельных системах баз данных. Целью данной работы является оценка эффективности выполнения запросов к сжатой базе данных без предварительной распаковки с использованием графических ускорителей, поддерживающих технологию CUDA. Объем внутренней памяти ГПУ на порядки меньше, чем объем оперативной памяти современных вычислительных систем. Это ограничивает размер базы данных, которую можно загрузить в память ГПУ и как следствие не позволяет раскрыть весь вычислительный потенциал графического процессора. Предлагается подход для обработки запросов над сжатыми данными на ГПУ. На основе предложенного подхода реализован эмулятор параллельной СУБД. Аналогичный эмулятор разработан для ЦПУ. Приведены результаты вычислительных экспериментов и произведена оценка эффективности данного подхода.
Бесплатно
Статья научная
Проблема повышения эффективности параллельных вычислений чрезвычайно актуальна. В статье продемонстрировано применение концепции Q-детерминанта для эффективной реализации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений. Концепция Q-детерминанта основана на унифицированном представлении численных алгоритмов в форме Q-детерминанта. Любой численный алгоритм имеет Q-детерминант. Q-детерминант состоит из Q-термов. Их число равно числу выходных данных алгоритма. Каждый Q-терм описывает все возможные способы вычисления одного из выходных данных на основе входных данных. Q-детерминант позволяет выразить и оценить внутренний параллелизм алгоритма, а также показать способ его параллельного исполнения. В работе приведены основные понятия концепции Q-детерминанта, необходимые для понимания приведенного исследования. Также описан основанный на концепции Q-детерминанта метод проектирования эффективных программ для численных алгоритмов. Результатом применения метода является программа, полностью использующая ресурс параллелизма алгоритма. Такая программа называется Q-эффективной. В качестве применения метода проектирования Q-эффективных программ описано проектирование программ для реализации метода сопряженных градиентов на параллельных вычислительных системах с общей и распределенной памятью. Приведены также результаты экспериментального исследования разработанных программ, проведенного с помощью суперкомпьютера «Торнадо ЮУрГУ».
Бесплатно
Применение концепции активных хранилищ в задачах обработки данных сейсмических наблюдений
Статья научная
Предложен подход для организации распределенной обработки сейсмических данных на базе свободно распространяемого пакета Seismic Un*x и системы активного хранения данных с использованием TSim и ФС Lustre. В работе рассмотрены ключевые проблемы обработки сейсмических данных, и для каждой предложено и обосновано использование соответствующего инструмента из арсенала системы активного хранения данных. Обработка данных непосредственно на узлах хранения позволяет продемонстрировать значительную эффективность за счет минимизации количества дорогостоящих операций передачи данных по сети. Проведено исследование производительности разработанного программного прототипа по обработке сейсмических данных в системе активного хранения для оценки перспектив полноценной интеграции.
Бесплатно
Применение математического моделирования для выбора инвестиционной программы предприятия
Статья научная
В статье представлены три экономико-математические модели для формирования инвестиционной программы предприятия: (1) на основе принципа гарантированного результата (т.е. принципа максимина); (2) на основе принципа максимизации ожидаемого в дисконтированного дохода при заданном ограничении сверху на его дисперсию; (3) на основе принципа максимизации ожидаемого в дисконтированного дохода при ограничении сверху вероятности его недостижимости. Последние две модели дают не гарантированные, а средние оценки доходности в уловиях риска и неопределенности. Решения предложенных задач позволяют дать системную оценку инвестиционной привлекательности предприятия, которую можно использовать при выборе эффективного инвестиционного портфеля с учетом склонности к риску лица принимающего решение.
Бесплатно
Применение метода проектирования q-эффективных программ для алгоритма Дейкстры
Статья научная
Проблема повышения эффективности параллельных вычислений чрезвычайно актуальна. В статье впервые продемонстрировано применение концепции Q-детерминанта для эффективной реализации алгоритма на графах. Концепция Q-детерминанта основана на унифицированном представлении численных алгоритмов в форме Q-детерминанта. Q-детерминант позволяет выразить и оценить внутренний параллелизм алгоритма, а также показать способ его параллельного исполнения. В работе приведены основные понятия концепции Q-детерминанта, необходимые для понимания приведенного исследования. Также описан основанный на концепции Q-детерминанта метод проектирования эффективных программ для численных алгоритмов. Результатом применения метода является программа, полностью использующая ресурс параллелизма алгоритма. Такая программа называется Q-эффективной. В качестве первого применения метода проектирования Q-эффективных программ для алгоритмов на графах описано проектирование программ для реализации алгоритма Дейкстры на параллельных вычислительных системах с общей и распределенной памятью. Приведены также результаты экспериментального исследования разработанных программ, проведенного с помощью суперкомпьютера «Торнадо ЮУрГУ». На основе анализа результатов экспериментального исследования определяются динамические характеристики разработанных программ и выявляются особенности их выполнения. Проведенные в статье исследования дают возможность сделать вывод, что применение концепции Q-детерминанта с целью разработки эффективных программ возможно не только для численных алгоритмов, но и для алгоритмов на графах.
Бесплатно
Применение многомерной квантильной функции в задаче пептид-белок докинг
Статья научная
Настоящая работа посвящена исследованию применения стохастических эволюционных алгоритмов оптимизации к задаче пептид-белок докинга. В статье продемонстрированы основные положения, сводящие докинг к задаче непрерывной глобальной оптимизации. Представлены основные особенности рассматриваемой задачи и возникающие трудности применения эволюционных алгоритмов оптимизации. Предложен способ применения эволюционных алгоритмов, включающий использование эмпирической квантильной функции. Приведено краткое «рекурсивное» определение структуры многомерной квантильной функции с использованием одномерного квантильного преобразования. Представлен сеточный подход применения квантильной функции и указаны его недостатки. Предложен детерминированный алгоритм построения выборки, приведена схема его распараллеливания и получаемое ускорение. Для квантильной функции описана схема использования параллельных вычислений, включающая вычисления на графических ускорителях. Предложено несколько способов параллелизации с использованием выборки в явном виде. Продемонстрирована их производительность в зависимости от размера выборки. Представлены результаты докинга с использованием эволюционного алгоритма и его модификации с применением квантильной функции. Выполнено сравнение с актуальным методом докинга в рамках одного силового поля. Проведен анализ результатов вычислительных экспериментов.
Бесплатно
Применение параллельных вычислений для аннотирования сенсорных данных
Статья научная
Аннотирование сенсорных данных предполагает автоматизированную разметку временного ряда показаний, снятых с сенсора, которая выделяет различные активности, заданные указанным рядом. Разметка активностей имеет широкий спектр практического применения: предиктивное техническое обслуживание, умное управление системами жизнеобеспечения, моделирование климата и др. Ранее нами разработан параллельный алгоритм PSF для аннотирования данных сенсоров с помощью графического процессора на основе концепции сниппетов. Сниппет представляет собой подпоследовательность, на которую похожи многие другие подпоследовательности данного ряда в смысле специализированной меры схожести, основанной на евклидовом расстоянии. В данной статье описаны два тематических исследования, выполненные с помощью алгоритма PSF: аннотирование показаний носимого виброакселерометра, закрепленного на человеке, и стационарного виброакселерометра, установленного на малогабаритной дробильной установке. В рамках исследований были проведены вычислительные эксперименты для оценки быстродействия и точности разработанного алгоритма. Также была исследована зависимость эффективности работы алгоритма от значений входных параметров: количества искомых сниппетов и длины подпоследовательности.
Бесплатно
Статья научная
Представлен подход к оптимизации вычислений, основанный на надстройке PROOF для пакета научных вычислений ROOT. Метод успешно применялся в задачах, возникающих в проекте NICA/MPD, таких как моделирование ridge-эффекта и вычисление радиационных длин детектора MPD. Получены зависимости ускорения от различных параметров.
Бесплатно
Статья научная
В связи со сложностью объекта исследования анализ данных в медицине является основным инструментом поиска закономерностей и проверки гипотез. Прежде всего, это относится к психологии, в том числе, к анализу поведения субъектов в тех или иных ситуациях. Для выявления высокотревожного состояния студентов, анализа склонности к депрессии или суициду ежегодно в Омском промышленно-экономическом колледже проводится исследование психоэмоционального состояния студентов. Традиционно для этого используются стандарные тесты, основанные на методике «Шкалы тревоги» Спилберегера-Ханина. Целью данной работы является снижение трудоемкости стандартных тестов. Значительные и слабо мотивированные усилия приходится прилагать студентам при заполнении тестов, затем преподавателям при обработке и анализе тестов. Для решения указанной проблемы предлагается сделать тест компактным за счет применения стандартных и оригинальных методов анализа данных с минимизацией потери точности тестирования. Основным новым результатом данной работы является диагностическая шкала, положенная в основу экспресс-оценки психоэмоционального состояния студентов. Расчет диагностической шкалы был выполнен с использованием графических процессоров на суперкомпьютере ИМ СО РАН. Исследования ориентированы на старшие классы общеобразовательных школ и младшие курсы учебных заведений среднего профессионального образования.
Бесплатно
Применение третичной структуры алгебраической байесовской сети в задаче апостериорного вывода
Статья научная
В теории алгебраических байесовских сетей существуют алгоритмы, позволяющие проводить глобальный апостериорный вывод с использованием вторичных структур. При этом построение вторичных структур предполагает использование третичной структуры. Следовательно, возникает вопрос об обособленном применении третичной структуры в задаче апостериорного вывода. Этот вопрос рассматривался ранее, но было приведено только общее описание алгоритма, при этом учитывались лишь модели со скалярными оценками вероятности истинности. В данной работе приведен алгоритм, расширяющий вышеупомянутый до возможности его использования в случае интервальных оценок. Помимо этого, важным свойством алгебраической байесовской сети является ацикличность, и корректность работы перечисленных алгоритмов обеспечивается только для ацикличных сетей. Поэтому необходимо также уметь проверять ацикличность алгебраической байесовской сети с применением третичной структуры. Описание этого алгоритма также представлено в работе, в его основе лежит ранее доказанная теорема, которая связывает количество моделей фрагментов знаний в сети с количеством непустых сепараторов и количеством компонент связности сильных сужений в цикличной АБС, а также доказанная в данной статье теорема о принадлежности двух моделей фрагментов знаний к одной компоненте связности сильного сужения. Для всех разработанных алгоритмов доказана корректность работы, а также вычислена их оценка временной сложности.
Бесплатно
Статья научная
Рассматриваются задачи поиска фраз и наборов слов в большом объеме текстов. В результате поиска получаем список документов, содержащих заданные слова, при этом документы, где слова располагаются ближе друг к другу, считаются более релевантными. Поскольку эта задача требует сохранения в индексе информации о каждом вхождении каждого слова в текстах, запросы, включающие часто встречающиеся слова, требуют для своего выполнения длительного времени. В некоторых поисковых системах предлагается ввести список стоп слов, которые не учитываются при поиске, но этот подход снижает качество поиска. В данной работе при поиске обрабатываются все слова и применяются дополнительные индексы. С помощью дополнительных индексов время выполнения поискового запроса, включающего часто встречающиеся слова, может быть снижено в десятки раз. Разработан новый вид индекса с трехкомпонентными ключами. Приведены алгоритмы поиска и результаты экспериментов поиска в сравнении с обычными индексами. Эксперименты показывают, что при применении разработанных индексов для определенного класса запросов, состоящих из самых часто встречающихся слов, скорость поиска возрастает более чем в 90 раз.
Бесплатно
Прогнозирование банкротств предприятий с помощью экстремального градиентного бустинга
Статья научная
Использование моделей прогнозирования банкротства предприятий для управления инвестиционными рисками лежит в основе управленческой деятельности финансовых учреждений. Важным фактором, позволяющим финансовым учреждениям определять объем капитала для покрытия кредитных потерь, является точность прогноза. В большинстве исследований для построения моделей банкротства предприятий используются традиционные методы статистики (например, дискриминантный анализ и логистическая регрессия).Однако точность построенных моделей обычно является достаточно низкой. Это обусловлено несбалансированностью классов обучающих наборов (доля фирм-банкротов составляет несколько процентов от общего числа фирм), которые используются при построении моделей. В настоящее время широкое распространение получают такие методы машинного обучения как метод случайного леса и метод градиентного бустинга. В данном исследовании основной акцент делается на использовании экстремального градиентного бустинга для прогнозирования банкротства. Экстремальный градиентный бустинг, используя LASSO или Ridge регуляризацию, штрафует сложные модели, что помогает избежать переобучения. Также в ходе обучения экстремальный градиентный бустинг заполняет пропущенные значения в наборе данных в зависимости от величины потерь. В статье для повышения эффективности экстремального градиентного бустинга предлагается использовать технологию SMOTE для улучшения сбалансированности классов. Метрики качества решений, полученных улучшенным экстремальным градиентным бустингом, сравниваются с решениями полученными другими методами.
Бесплатно
Статья научная
Описана процедура поиска потенциальных предикторов и создания прогнозных правил нечеткой логики и нечетких нейронных сетей для последующего прогнозирования вспышек численности синезеленой водоросли M. aeruginosa. В результате натурных наблюдений ряда биотических и абиотических параметров водной среды, проведенных на озере Смолино (г. Челябинск) за теплый период 2009 и 2011 года получены временные ряды численности M. aeruginosa и значений сопутствующих параметров. С помощью кросс-корреляционного анализа данных установлено, что потенциальными предикторами квазипериодических колебаний численности M. aeruginosa с периодом 12-20 дней могут выступать численность водоросли P. duplex, температура воды и концентрация нитрат-иона. По результатам кросс-корреляционного анализа заданы прогнозные правила и функции принадлежности в диапазоне изменений предиктанта и предиктора от нуля до 1. Для «автоматического» задания прогнозных правил и функций принадлежности с помощью специально написанной программы произведено обучение нечеткой нейронной сети на данных о значениях предиктанта и отобранных в ходе предварительного анализа параметров-предикторов. Для сравнения результатов дополнительно осуществлена линейная экстраполяция данных о численности предиктанта. Выявлено, что экстраполяционный прогноз хорошо работает на квазилинейных интервалах изменения численности, а алгоритмы нечеткой логики потенциально способны определить время наступления интенсивных вспышек численности предиктанта.
Бесплатно
Программная поддержка модели BSF
Статья научная
В статье описана программная поддержка модели параллельных вычислений BSF (Bulk Synchronous Farm), ориентированной на итерационные алгоритмы с высокой вычислительной сложностью, разрабатываемые для многопроцессорных систем с распределенной памятью экзафлопсного уровня производительности. Программная поддержка включает в себя параллельный BSF-каркас и веб-приложение BSF-Studio. Приведены определение и классификация параллельных программных каркасов. Описан новый BSF-каркас, разработанный согласно BSF-модели: его файловая структура и логика работы. BSF-каркас представляет собой совокупность файлов исходного кода на языке C++, используемых для быстрого создания BSF-программ. Приведено подробное описание проектирования и реализации веб-приложения BSF-Studio, которое представляет собой визуальный конструктор BSF-программ. BSF-Studio обеспечивает поэтапное заполнение проблемно-зависимых частей BSF-каркаса, а также компиляцию и запуск программного кода.
Бесплатно
Программное исследование полурешеток, связанных с автоматом Ватерлоо
Статья научная
Статья посвящена исследованию полурешеток, содержащих покрывающие автоматы для автомата Ватерлоо. В начальных разделах статьи описывается процесс построения покрывающих автоматов на основе подмножеств гридов исходного автомата (каждый грид представляет собой некоторое множество дуг, связанных с исходным автоматом), а также рассматриваются свойства полурешеток, образуемых покрывающими автоматами. Основным результатом статьи является полное описание полученных полурешеток с точки зрения эквивалентности входящих в них покрывающих автоматов исходному автомату Ватерлоо. Выделены три класса полурешеток, каждый из которых имеет особые свойства. Для полурешетки, построенной на базе минимального покрывающего автомата, получено графическое представление, которое позволяет наглядно отразить соотношения между ее наборами, состоящими из попарно эквивалентных автоматов. Кроме того, сформулирован критерий эквивалентности покрывающего автомата автомату Ватерлоо в терминах свойств подмножества гридов, определяющего покрывающий автомат. Исследование проводилось с применением библиотеки NFALib для анализа недетерминированных конечных автоматов, реализованной автором на языке C#. Актуальность изучения автомата Ватерлоо связана с его ролью в исследовании задачи вершинной минимизации недетерминированных конечных автоматов и разработке эвристических алгоритмов реального времени, используемых для ее решения.
Бесплатно
Статья научная
В CAD/CAM-системах технологической подготовки процессов раскроя встает задача построения маршрута движения режущего инструмента, при котором отрезанная от листа часть не требует дополнительных разрезаний и запрещены пересечения траектории резки (касания допускаются). Формально такая задача может быть сформулирована как задача построения самонепересекающейся цепи в плоском эйлеровом графе, представляющим гомеоморфный образ раскройного плана. В конечном счете задачи построения маршрутов, удовлетворяющих технологическим ограничениям, сводятся к нахождению A-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. В статье предложен алгоритм нахождения такой цепи. Выполнение алгоритма состоит из двух этапов. На первом этапе выявляются и расщепляются точки сочленения ранга k. На втором этапе построение цепи начинается из произвольной вершины, инцидентной внешней грани; первым ребром цепи выбирается инцидентное данной вершине ребро максимального ранга; далее организуется итерационный процесс, где в качестве следующего ребра выбирается непройденное ребро максимального ранга, являющееся левым либо правым соседом текущего ребра. Показано, что для плоского связного 4-регулярного графа алгоритм строит маршрут с указанными свойствами за линейное время. Представленные алгоритмы реализованы в виде компьютерной программы. Приведены примеры решения ряда тестовых задач.
Бесплатно
Краткое сообщение
Задачи нахождения маршрутов, удовлетворяющих определенным ограничениям, появились из конкретных практических ситуаций. Например, в задачах раскроя листового материала плоский граф является моделью раскройного плана, а маршрут, покрывающий все ребра, определяет траекторию режущего инструмента. В статье рассматривается алгоритм построения оптимального покрытия произвольного плоского (возможно, многосвязного) графа цепями с упорядоченным охватыванием, позволяющий построить такую траекторию движения режущего инструмента, при которой отрезанная от листа часть не требует дополнительных разрезаний. Показано, что алгоритм имеет полиномиальную сложность.
Бесплатно
Статья научная
В статье описывается оригинальный комплекс высокоуровневого синтеза, преобразующий последовательные программы в схемотехническую конфигурацию специализированных аппаратных средств для реконфигурируемых вычислительных систем. Из исходной последовательной программы строится абсолютно-параллельная форма - информационный граф. Далее, граф преобразуется в ресурсонезависимую параллельно-конвейерную форму - кадровую структуру, которую можно адаптировать к различному аппаратному ресурсу. Преобразование кадровой структуры в информационно-эквивалентную, но занимающую меньший аппаратный ресурс, структуру выполняется с помощью формализованных методов редукции производительности, что позволяет автоматически получить рациональное решение для заданной многокристальной реконфигурируемой вычислительной системы. В отличие от известных средств высокоуровневого синтеза результатом преобразования является не IP-ядро вычислительно-трудоемкого фрагмента, а автоматически синхронизированное решение прикладной задачи для всех кристаллов ПЛИС реконфигурируемой вычислительной системы. По сравнению с распараллеливающими компиляторами, число анализируемых вариантов синтеза рационального решения существенно меньше, что является отличительной особенностью описываемого комплекса. Применение программных средств высокоуровневого синтеза рассматривается на примере задачи решения системы линейных алгебраических уравнений методом Гаусса, содержащей информационно-взаимозависимые вычислительные фрагменты с существенно разной степенью параллелизма.
Бесплатно
Программный комплекс Радуга-Т для моделирования полей нейтронов в ядерно-энергетических установках
Статья научная
При проектировании и сопровождении эксплуатации ядерно-энергетических установок (ЯЭУ) необходимо выполнять моделирование в этих установках потоков нейтронов. При задании геометрии ЯЭУ необходимо учитывать границы разномасштабных конструктивных элементов, состоящих из материалов с существенно различными свойствами. Из-за больших размеров ЯЭУ для расчетов желательно использовать параллельные компьютеры. Для выполнения такого моделирования развиваются алгоритмы и программы численного решения краевой задачи для интегро-дифференциального уравнения переноса нейтронов на неструктурированных сетках. В статье приводится описание реализованных в программном комплексе РАДУГА-Т алгоритмов решения такой задачи. Представлены сетки, сеточные схемы, итерационные методы решения систем сеточных уравнений. Рассмотрены методы распараллеливания вычислений на гибридных компьютерах (используются технологии MPI и OpenMP). Представлены методы работы с пространственными сетками (построение, улучшение качества, декомпозиция, визуализация). Описаны особенности программной реализации. Проведено сравнение используемых в программном комплексе РАДУГА-Т алгоритмов с алгоритмами в других аналогичных программных комплексах. Приведены результаты исследования эффективности распараллеливания вычислений в задаче расчета коэффициента размножения нейтронов в модели легководного реактора. Исследования выполнены на многопроцессорном компьютере МВС-10П (МСЦ РАН). Приведены значения ускорения вычислений каждого из используемых в расчете алгоритмов и суммарного ускорения всего расчета.
Бесплатно
