Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi
Статьи журнала - Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика
Все статьи: 329
Статья научная
В данной работе рассматривается построение параллельной версии алгоритма глобальной оптимизации, решающего одновременно множество задач с нелинейными ограничениями и получающего при этом равномерные оценки решений на этом множестве. Последнее свойство позволяет наиболее оптимально распределять вычислительные ресурсы, т.к. в процессе работы алгоритма погрешности численного решения во всех задачах убывают примерно с одинаковой скоростью. Алгоритм присваивает приоритет каждой задаче и на каждой итерации производит вычисления целевых функций в нескольких задачах параллельно. При окончании работы метода в произвольный момент времени во всех задачах из решаемой серии будут получены решения сходного качества. Серии из нескольких задач возникают, если задача глобальной оптимизации имеет дискретный параметр или, например, при решении задачи многокритериальной оптимизации методом свертки критериев. Рассматриваемый алгоритм использует отображения типа кривой Пеано для редукции многомерных задач оптимизации к одномерным. Эффективность реализованного алгоритма протестирована на наборах искусственно сгенерированных задач глобальной оптимизации, а также при решении серии задач, полученной в результате скаляризации задачи многокритериальной оптимизации. Также экспериментально подтверждена равномерная сходимость метода.
Бесплатно
Параллельный алгоритм поиска лейтмотивов временного ряда для графического процессора
Статья научная
Лейтмотив представляет собой пару подпоследовательностей временного ряда, наиболее похожих друг на друга. Задача поиска лейтмотивов встречается в широком спектре предметных областей: медицина, биология, предсказание погоды и др. В работе предложен новый параллельный алгоритм поиска лейтмотива во временном ряде на платформе графического процессора для случая, когда входные данные могут быть размещены в оперативной памяти. Предлагаемый алгоритм использует в качестве основы алгоритм MK, в котором применяется евклидово расстояние и неравенство треугольника для отбрасывания бесперспективных лейтмотивов без вычисления расстояния. MK позволяет сократить время поиска в разы по сравнению с другими последовательными алгоритмами, однако его производительность значительно снижается на временных рядах, имеющих длину от сотен тысяч элементов. Распараллеливание выполнено с помощью технологии программирования OpenACC. Разработаны матричные структуры данных, позволяющие эффективно распараллелить вычисления на графическом процессоре. Представлены результаты вычислительных экспериментов на реальных и синтетических наборах данных, подтверждающих высокую масштабируемость разработанного алгоритма.
Бесплатно
Статья научная
Рассмотрены задачи динамики встречных пучков заряженных частиц в ускорителях и динамики плазменных электронов в ловушке с инверсными магнитными пробками и мультипольными магнитными стенками. Модели построены на основе метода частиц в ячейках. Такие задачи требуют большого объема вычислений и могут быть решены только с применением мощных суперЭВМ. Для равномерной и полной загрузки вычислительных узлов выполнена модификация эйлерово-лагранжевой декомпозиции в случае существенно неравномерного распределения частиц по пространству и по времени.
Бесплатно
Параллельный метод объединения результатов работы программ по сборке генома
Статья научная
В данной работе проводится исследование в области применения многопроцессорных систем для задачи коррекции сборки генома. Существует большое количество алгоритмических подходов к проблеме сборки генома из набора коротких фрагментов, при этом результаты их работы на одних и тех же экспериментальных данных зачастую существенно разнятся. Вследствие большого объема данных необходима организация вычислений в модели распределенной памяти на вычислительном кластере. Авторами предложен алгоритм объединения результатов работ геномных сборщиков, основанный на построении распределенного взвешенного графа контигов. Предлагаемый подход использует комбинацию выводов программ сборки гeномов, что позволяет уменьшить фрагментированность контигов в результирующем наборе. Последовательная версия алгоритма реализована на C/C++ и доступна по адресу: https://bitbucket.org/kromanenkov/gar.
Бесплатно
Параллельный поиск частых наборов на многоядерных ускорителях Intel Mic
Статья научная
Поиск ассоциативных правил предполагает нахождение устойчивых корреляций между наборами элементов в больших базах транзакционных данных и является одной из основных задач интеллектуального анализа данных. Ассоциативные правила генерируются на основе множества всех наборов, в которых элементы часто встречаются совместно. Алгоритм DIC (Dynamic Itemset Counting) является модификацией классического алгоритма Apriori поиска частых наборов. В отличие от предшественника DIC пытается сократить количество проходов по базе транзакций и сохранить при этом относительно небольшое количество наборов, поддержка которых подсчитывается в рамках одного прохода. В статье рассмотрена проблема ускорения алгоритма DIC на многоядерной архитектуре Intel Many Integrated Core (MIC) для случая, когда база транзакций помещается в оперативную память. Разработанная с помощью технологии OpenMP параллельная реализация алгоритма DIC использует битовое представление транзакций и наборов, что позволяет ускорить и векторизовать подсчет поддержки наборов, реализуемый посредством логических побитовых операций. Проведенные эксперименты с синтетическими и реальными данными подтвердили хорошую производительность и масштабируемость предложенного алгоритма.
Бесплатно
Краткое сообщение
Представлен подход к интеграции интеллектуального анализа данных (ИАД) в реляционную СУБД. Подход предполагает использование XML-разметки алгоритма ИАД, выраженного на языке SQL. Разметка позволяет выполнить автоматическую генерацию хранимых процедур на языке SQL, реализующих данный алгоритм, в зависимости от специфицированных пользователем таблиц исходных данных и параметров алгоритма. Приведено описание предложенного языка разметки. Если для решения задачи ИАД имеется несколько алгоритмов, подход предполагает генерацию SQL-кода, реализующего наиболее эффективный из них. Выбор наиболее эффективного алгоритма осуществляется на основе использования имеющейся в современных СУБД команды EXPLAIN, позволяющей получить оценку времени исполнения запроса SQL без его фактического выполнения. Описана модульная структура и интерфейс программной системы, реализующей данный подход.
Бесплатно
Статья научная
При реализации алгоритмов на многопроцессорных вычислительных устройствах важнейшую роль для достижения высокой производительности играет локальность — вычислительное свойство алгоритма, отражаюшее степень использования памяти с быстрым доступом. Для суперкомпьютеров с распределенной памятью быстрой считается локальная память вычислительного узла. Параллельные алгоритмы с меньшим объемом и лучшей структурой коммуникационных операций обладают лучшей локальностью. В работе на основе схемы расщепления с весами построен новый параллельный алгоритм численного решения трехмерного линейного уравнения теплопроводности. Алгоритм ориентирован на компьютеры с распределенной памятью, сочетает конвейерный и естественный параллелизм, использует 2D структуру процессов. Схема расщепления обладает естественным параллелизмом. Ранее для случая 1D структуры процессов было показано, что использование конвейерного параллелизма вместо части естественного параллелизма приводит к меньшим объемам и лучшей структуре коммуникационных операций. Построенный 2D алгоритм обобщает известный 1D алгоритм. Использование двумерных структур позволяет уменьшить объем и улучшить структуру коммуникационных операций, уменьшить время разгона и торможения вычислений. Поэтому 2D алгоритм обладает лучшей локальностью по сравнению с использованием 1D структуры процессов. Вычислительные эксперименты на суперкомпьютере показали преимущество нового параллельного алгоритма. По аналогии с представленным алгоритмом можно получить и исследовать параллельные алгоритмы для других схем метода дробных шагов. На примере алгоритма, реализующего схему расщепления, представлен подход к получению асимптотических оценок объема коммуникационных операций зернистых (т.е. уровня макроопераций) параллельных вычислительных процессов, логически организованных в двумерную структуру. Оценки могут быть использованы для сравнения коммуникационных затрат при получении альтернативных вариантов параллельных алгоритмов
Бесплатно
Подход к разбиению сверхбольших графов с помощью параллельных СУБД
Краткое сообщение
Разбиение графов на подграфы представляет собой интересную задачу интеллектуального анализа графов, которая находит свое применение в ряде теоретических и практических задач (раскраска графа, проектирование БИС и ПЛИС, конечноэлементное моделирование и др.). Существующие последовательные и параллельные алгоритмы предполагают возможность размещения графов и промежуточных данных обработки в оперативной памяти и неприменимы для случая сверхбольших графов. Представлен подход к обработке сверхбольших графов на основе использования параллельной реляционной СУБД PargreSQL, разработанной на базе свободной СУБД PostgreSQL.
Бесплатно
Статья научная
Рассматривается задача детектирования объектов разных классов на статических изображениях: фотографиях или отдельных кадрах видеопотока. Описывается схема решения данной задачи с использованием алгоритма Latent SVM. Используется известный подход к ускорению вычислений — построение каскада классификаторов. Описывается вычислительная схема решения задачи детектирования с помощью каскадного Latent SVM. Обсуждаются проблемы распараллеливания и оптимизации времени поиска объектов одного класса на изображении. Проводится анализ вариантов решения указанных проблем. Выделяются наиболее трудоемкие участки реализаций, рассматриваются различные схемы распараллеливания, оцениваются их преимущества и недостатки. Приводятся результаты вычислительных экспериментов на базе изображений PASCAL Visual Object Challenge 2007, дается их анализ, а также формулируются выводы и планы по дальнейшему развитию.
Бесплатно
Поиск аномалий в сенсорных данных цифровой индустрии с помощью параллельных вычислений
Статья научная
В статье представлены результаты исследований по поиску аномалий в сенсорных данных из различных приложений цифровой индустрии. Рассматриваются временные ряды, полученные при эксплуатации деталей машин, показания датчиков, установленных на металлургическом оборудовании, и показания температурных датчиков в системе умного управления отоплением зданий. Аномалии, найденные в таких данных, свидетельствуют о нештатной ситуации, отказах, сбоях и износе технологического оборудования. Аномалия формализуется как диапазонный диссонанс - подпоследовательность временного ряда, расстояние от которой до ее ближайшего соседа не менее наперед заданного аналитиком порога. Ближайшим соседом данной подпоследовательности является такая подпоследовательность ряда, которая не пересекается с данной и имеет минимальное расстояние до нее. Поиск диссонансов выполняется с помощью параллельного алгоритма для графического процессора, ранее разработанного автором данной статьи. Для визуализации найденных аномалий предложены метод построения тепловой карты диссонансов, имеющих различные длины, и алгоритм нахождения в построенной тепловой карте наиболее значимых диссонансов независимо от их длин.
Бесплатно
Статья научная
В статье рассматривается подход к решению задач поиска систем ортогональных латинских квадратов, основанный на сведении этих задач к проблеме булевой выполнимости. Была построена соответствующая кодировка для задачи поиска пар ортогональных диагональных латинских квадратов порядка 10. С помощью построенной кодировки в проекте добровольных распределенных вычислений SAT@home были найдены 17 новых пар. На основе 17 найденных пар, а также 3 ранее известных пар, были построены псевдотройки диагональных латинских квадратов порядка 10. Построение псевдотроек было осуществлено на вычислительном кластере, для этого была сделана параллельная реализация алгоритма генерации диагональных латинских квадратов порядка 10.
Бесплатно
Помехоустойчивый алгоритм построения поля потоков изображений отпечатков пальцев
Статья научная
Поле потоков отпечатков пальцев является одной из наиболее важных характеристик узора и оказывает большое влияние на всю процедуру дактилоскопической идентификации. Методы для построения поля потоков, основанные на градиенте, весьма популярны, однако, слишком чувствительны к различным шумам и дефектам, которые тем или иным образом проявляются на многих изображениях отпечатков. В данной статье предлагается новый метод построения поля потоков для цифровых изображений отпечатков пальцев. Он позволяет улучшить решение ряда ключевых задач обработки изображений. Среди таких задач прогноз направлений линий в области складок кожи, шрамов и других дефектов поверхности пальца. Метод опирается на такие подходы, как обработка изображения на субпиксельном уровне, на кластерный анализ поля градиентов изображения и заключатся в последовательном применении нескольких алгоритмов. Это интерполяция изображения и оценка значений градиента на нем, свертка поля градиента с заданным шаблоном для борьбы с шумами на субпиксельном уровне, выделение опорных областей на основе построения локальных оценок качества узора, прогнозирование поля направлений от опорных областей на всё изображение с адаптацией прогнозируемых значений под результаты измерений. Верификация результатов работы предлагаемого метода выполнена с помощью веб-фреймворка, созданного на базе Болонского университета в Италии. Новые результаты верификации сравниваются с результатами верификации предшествующего метода, развитого в данной статье, и с другими опубликованными алгоритмами на том же веб-фреймворке.
Бесплатно
Статья научная
Статья посвящена краткому обзору истории и авторской оценке состояния реализации проектов сбора и распределенной обработки данных, основанной на использовании Грид-технологий. Особое внимание уделяется этапам реализации и областям их применений в рамках панЕвропейского проекта EGI (European Grid Initiative), а также перспектив его развития для возможной реализации проекта типа WGI (Wordlewide Grid Initiative).
Бесплатно
Построение самонепересекающихся OE-маршрутов в плоском эйлеровом графе
Статья научная
В статье предложен полиномиальный алгоритм построения самонепересекающегося маршрута с упорядоченным охватыванием в плоском эйлеровом графе. Предложенный подход состоит в расщеплении всех вершин исходного графа степени выше 4 и введении фиктивных вершин и ребер, сводя, таким образом, исходную задачу к решенной ранее автором задаче построения A-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. Приведенный алгоритм сведения решает поставленную задачу за полиномиальное время. Рассмотрен тестовый пример построения самонепересекающейся цепи с упорядоченным охватыванием. Данная задача возникает при технологической подготовке процесса раскроя, когда требуется определить маршрут движения режущего инструмента, при котором отсутствуют самопересечения траектории резки и отрезанная от листа часть не требует разрезаний. Раскройный план представлен в виде плоского графа, являющегося его гомеоморфным образом. Предложенный в статье алгоритм решает проблему маршрутизации при вырезании деталей, когда на маршрут движения режущего инструмента одновременно наложены такие технологические ограничения.
Бесплатно
Правда, искажающая истину. Как следует анализировать Top500?
Статья научная
После каждого выпуска рейтинга Top500 выполняются подсчеты и публикуются суждения, вида: «Подавляющее большинство суперкомпьютеров списка Top500 используется в промышленности». Появляются и другие подобные подсчеты и суждения о долях в списке Top500 разных типов процессоров, различных типов интерконнекта, производителей суперкомпьютеров, стран и т.п. Часто на базе подобных суждений принимаются серьезные решения, в том числе и на правительственном уровне. В данной работе показано: все, что фиксируется в подобных суждениях — правда, однако эта правда серьезно искажает истину и не отражает истинное положение дел в суперкомпьютерной отрасли. Кроме того, дается анализ причины серьезного отличия «правды» от «истины», приводятся методика корректного анализа данных Top500 и результаты такого анализа.
Бесплатно
Статья научная
Рассматривается применение задачи сильной отделимости для получения решений о покупке или продаже финансовых активов, таких как акции, иностранная валюта, фьючерсы и т.д. на биржевом рынке. Для этого выполнено построение двух систем линейных неравенств, задающих области в n-мерном пространстве, которые описывают экспертные торговые сигналы на основе адаптивной скользящей средней Кауфмана.
Бесплатно
Статья научная
Данная статья продолжает цикл работ автора, посвященных проблеме возраста информации (Age of Information, AoI) - метрики, используемой в информационных системах для мониторинга и управления удаленными источниками информации со стороны центра управления. Теоретический анализ систем передачи информации требует количественной оценки «свежести» информации, доставляемой в центр управления. В данной работе рассматривается модель двухузловой группы передачи, состоящей из источника информации (узла-отправителя), центра управления (узла-получателя) и нескольких каналов связи между ними. Предполагается, что пропускные способности каналов могут быть различными. При этом, сетевой протокол требует, чтобы информация, поступающая в узел-получатель считывалась в той же последовательности, в какой она была передана из узла-отправителя. В результате пакеты, нарушившие установленный порядок, задерживаются в узле-отправителе на время, требуемое для восстановления порядка. В данной работе процесс передачи информации моделируется с помощью многоканальной системы массового обслуживания с ограниченным накопителем, пуассоновским потоком заявок, экспоненциальным обслуживанием и переупорядочиванием заявок. При этом заявки моделируют пакеты передаваемой информации, накопитель системы - очередь пакетов на передачу, обслуживание заявок на приборах различной интенсивности - процесс передачи пакетов по каналам связи. Данная модель для оценки возраста информации использовалась впервые. В результате проведенного исследования получены выражения для преобразования Лапласа-Стилтьеса стационарной функции распределения и начальных моментов максимального значения возраста информации, называемого пиковым возрастом. Проведено численное исследование показателей производительности системы, включающее анализ пикового возраста информации при различных загрузках системы. Корректность аналитических результатов подтверждена результатами имитационного моделирования.
Бесплатно
Статья научная
Статья посвящена поиску троек взаимно частично ортогональных диагональных латинских квадратов порядка 10. Для каждой известной пары ортогональных диагональных латинских квадратов порядка 10 достраивается третий диагональный латинский квадрат таким образом, чтобы условие ортогональности между ним и квадратами из рассматриваемой пары нарушалось в как можно меньшем количестве ячеек. Используются два подхода: первый основан на сведении исходной задачи к задаче о булевой выполнимости, а второй - на использовании метода грубой силы. Построено несколько троек указанного вида с рекордными характеристиками. Эксперименты были проведены в проекте добровольных распределенных вычислений SAT@home, а также на вычислительном кластере.
Бесплатно
Применение вычислительных схем повышенной точности в проектировании антенных систем
Статья научная
Предложены эффективные вычислительные методы для исследования математических моделей антенных систем. Для построения математических моделей используются строгие электродинамические принципы и уравнения. Применение квадратурных формул повышенной точности для решения интегрального уравнения Поклингтона и специальной регуляризирующей процедуры для интегрального уравнения II рода позволяет получить устойчивые результаты моделирования с заданной точностью и высокими динамическими характеристиками.
Бесплатно
