Статьи журнала - Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика
Все статьи: 306
Параллельное решение систем линейных уравнений на гибридной архитектуре CPU+GPU
Статья научная
В статье рассматривается параллельная реализация решения систем линейных алгебраических уравнений на вычислительных узлах, содержащих центральный процессор (CPU) и графические ускорители (GPU). Производительность параллельных алгоритмов для классических схем метода сопряженных градиентов при совместном использовании CPU и GPU существенно ограничивается наличием точек синхронизации. В статье исследуется конвейерный вариант метода сопряженных градиентов с одной точкой синхронизации и возможностью распределения нагрузки между CPU и GPU при решении систем уравнений большой размерности. Численные эксперименты проведены на тестовых матрицах и вычислительных узлах разной производительности гетерогенного кластера, что позволило оценить вклад коммуникационных затрат. Алгоритмы реализованы при совместном использованием технологий MPI, OpenMP и CUDA. Предложенные алгоритмы, помимо сокращения времени выполнения, позволяют решать системы линейных уравнений и большего порядка, для которых не обеспечиваются необходимые ресурсы памяти одним GPU или вычислительным узлом. При этом, конвейерный блочный алгоритм сокращает общее время выполнения за счет уменьшения точек синхронизации и объединения коммуникаций в одно сообщение.
Бесплатно
Параллельные методы и технологии декомпозиции областей
Статья научная
Рассматриваются параллельные методы декомпозиции областей для решения трехмерных сеточных краевых задач, получаемых в результате конечно-элементных или конечно-объемных аппроксимаций. Данные проблемы являются «узким горлышком» среди различных этапов математического моделирования, поскольку современные требования к разрешающей способности сеточных алгоритмов приводят к необходимости решения систем линейных алгебраических уравнений с числом неизвестных в сотни миллионов и с очень плохой обусловленностью, что вызывает экстремальную ресурсоемкость расчетов. Описываются многопараметрические варианты алгоритмов с различной размерностью декомпозиции — одномерной, двумерной и трехмерной, — с пересечением или без пересечения подобластей, при использовании величин перехлеста как оптимизирующих параметров, а также с различными видами внутренних условий сопряжения на смежных границах (Дирихле, Неймана или третьего рода). Исследуются вариационные итерационные процессы крыловского типа в пространствах следов с разными предобуславливающими подходами: операторы Пуанкаре-Стеклова, блочный метод Чиммино, альтернирующий метод Шварца аддитивного типа, а также грубо-сеточная коррекция, являющаяся в определенном смысле упрощенным вариантом алгебраического многосеточного подхода. Проводится сравнительный анализ критериев эффективности распараллеливания на многопроцессорных вычислительных системах.
Бесплатно
Статья научная
В настоящее время во многих предметных областях обработка сенсорных данных в режиме реального времени связана с необходимостью синтеза значения соответствующего временного ряда, которое было пропущено ввиду технического сбоя или человеческого фактора. В данной статье предлагается параллельный алгоритм восстановления пропущенных значений потокового временного ряда в режиме реального времени для многоядерного процессора. Алгоритм использует набор опорных временных рядов, которые имеют семантическую связь с исходным рядом. Алгоритм применяет следующую эвристику: если в опорных рядах имеют место повторяющиеся (схожие) подпоследовательности, то в ряде, содержащем пропущенное значение, повторяющиеся подпоследовательности возникают в тех же временных интервалах. Образцами поиска для каждого опорного ряда полагаются подпоследовательности заданной длины, оканчивающиеся в момент пропуска значения в исходном ряде. Схожесть подпоследовательностей с образцом определяется на основе меры DTW (Dynamic Time Warping), имеющей квадратичную вычислительную сложность относительно длины подпоследовательности. Применяется техника нижних границ схожести, позволяющая отбрасывать подпоследовательности, заведомо непохожие на образец, без вычисления DTW. Нижние границы имеют меньшую, чем у DTW сложность, и вычисляются параллельно. Восстановленное значение вычисляется как среднее арифметическое последних элементов найденных интервалов. В вычислительных экспериментах предложенный алгоритм демонстрирует высокую точность восстановления в сравнении с аналогами и быстродействие, приемлемое для применения алгоритма в режиме реального времени.
Бесплатно
Статья научная
Вычисление матрицы Евклидовых расстояний требуется в широком спектре задач, связанных с интеллектуальным анализом данных. В настоящее время большое количество параллельных алгоритмов решения этой задачи реализовано для графических процессоров. Однако данные разработки не могут быть просто перенесены на многоядерные системы архитектуры Intel Many Integrated Core. В статье предлагается параллельный алгоритм вычисления матрицы Евклидовых расстояний на многоядерном процессоре Intel Xeon Phi поколения Knights Landing для случая, когда входные данные могут быть размещены в оперативной памяти. Данный алгоритм использует блочно-ориентированную схему организации вычислений, которая позволяет эффективно использовать возможности векторизации вычислений Intel Xeon Phi. В алгоритме применена нетривиальная компоновка данных в оперативной памяти для уменьшения количества кэш-промахов процессора во время вычислений. Эксперименты на реальных и синтетических наборах данных показали, что предложенный алгоритм хорошо масштабируется и опережает аналоги в случае прямоугольных матриц с данными малой размерности.
Бесплатно
Статья научная
В данной работе рассматривается построение параллельной версии алгоритма глобальной оптимизации, решающего одновременно множество задач с нелинейными ограничениями и получающего при этом равномерные оценки решений на этом множестве. Последнее свойство позволяет наиболее оптимально распределять вычислительные ресурсы, т.к. в процессе работы алгоритма погрешности численного решения во всех задачах убывают примерно с одинаковой скоростью. Алгоритм присваивает приоритет каждой задаче и на каждой итерации производит вычисления целевых функций в нескольких задачах параллельно. При окончании работы метода в произвольный момент времени во всех задачах из решаемой серии будут получены решения сходного качества. Серии из нескольких задач возникают, если задача глобальной оптимизации имеет дискретный параметр или, например, при решении задачи многокритериальной оптимизации методом свертки критериев. Рассматриваемый алгоритм использует отображения типа кривой Пеано для редукции многомерных задач оптимизации к одномерным. Эффективность реализованного алгоритма протестирована на наборах искусственно сгенерированных задач глобальной оптимизации, а также при решении серии задач, полученной в результате скаляризации задачи многокритериальной оптимизации. Также экспериментально подтверждена равномерная сходимость метода.
Бесплатно
Параллельный алгоритм поиска лейтмотивов временного ряда для графического процессора
Статья научная
Лейтмотив представляет собой пару подпоследовательностей временного ряда, наиболее похожих друг на друга. Задача поиска лейтмотивов встречается в широком спектре предметных областей: медицина, биология, предсказание погоды и др. В работе предложен новый параллельный алгоритм поиска лейтмотива во временном ряде на платформе графического процессора для случая, когда входные данные могут быть размещены в оперативной памяти. Предлагаемый алгоритм использует в качестве основы алгоритм 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 и результаты такого анализа.
Бесплатно
