Программирование. Рубрика в журнале - Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование
Распараллеливание рекуррентных циклов с предварительным вычислением суперпозиций
Статья научная
Как правило, именно циклы являются участками кода, вычисление которых занимает много времени. Поэтому, именно на них направляются особые усилия при ускорении программ, в частности, через распараллеливание. В статье описывается алгоритм распараллеливания циклов, вычисляющих элементы рекуррентно заданной последовательности. Рекуррентные циклы, рассматриваемые в статье, непосредственно распараллелены быть не могут. С помощью вспомогательных преобразований иногда их можно привести к циклам, допускающим параллельное выполнение. Ранее автором статьи был опубликован другой алгоритм распараллеливания циклов, вычисляющих элементы рекурсивно заданной последовательности. В современных процессорах время выполнения арифметических операций оказывается на порядок меньше, чем считывание аргументов этих операций из оперативной памяти. В данной статье приводятся оценки сложности по обращению к памяти, для описываемого алгоритма. Представленный в статье параллельный алгоритм оказывается более эффективным по обращениям к памяти, чем алгоритм, описанный автором ранее.
Бесплатно
Статья научная
В статье рассмотрен подход к масштабированию сервиса морфологического разбора слов естественного языка при обработке различных коллекций документов на русском языке. Выполнен обзор и критический анализ существующих решений. Сформированы требования к инструментальной среде словарного морфологического анализатора. Распределенная архитектура Web-сервиса морфологического анализа, предназначенного для обработки крупных коллекций документов на русском языке, представлена в виде структурной модели. Данная архитектура реализована в виде прототипа системы на языке программирования Ruby. Приведена структура используемого морфологического словаря в виде реляционной схемы. Испытания данного метода в распределенной вычислительной среде показали линейную масштабируемость предлагаемого решения. Конфигурация эксперимента включает систему генерации нагрузки в виде HTTP-запросов, систему балансировки нагрузки на рабочие узлы распределенной системы, серверы приложений с функционирующим анализатором и базу данных морфологического словаря, а также кэширующий узел для снижения издержек при выполнении запросов к словарю. Применение данного подхода позволяет получить линейный рост производительности в распределенных системах автоматической обработки больших объемов текста.
Бесплатно
Статья научная
Рациональной альтернативой созданию собственного суперкомпьютерного центра для решения сложных задач инженерного моделирования является аренда вычислительных и программных ресурсов в режиме удаленного доступа у центров коллективного пользования. Однако при этом возникает целый комплекс проблем, связанных с организацией прозрачного и безопасного доступа к таким ресурсам. В статье предложено описание технологии CAEBeans, обеспечивающей автоматизированную генерацию проблемно-ориентированных грид-сервисов, позволяющих использовать программные системы для инженерного проектирования и анализа в распределенных вычислительных средах.
Бесплатно
Статья научная
В статье рассматривается расчет трехмерного магнитного поля системы постоянных магнитов и ферромагнетиков на основе интегрального уравнения намагниченности и модели Джиллса - Аттертона. Предполагается, что магнитная система состоит из постоянных магнитов и конструктивных элементов, выполненных из ферромагнитных материалов с известными характеристиками. Одной из задач является учет влияния магнитного гистерезиса материала каркаса на точность расчета магнитного поля. Для решения интегрального уравнения намагниченности используются метод ячеек и метод итерационной релаксации. Основная кривая намагниченности вычисляется по формуле Ланжевена. В качестве модельной задачи рассматривается расчет магнитного поля, создаваемого прямоугольным постоянным магнитом, расположенным на ферромагнитном основании в виде параллелепипеда. Полученные результаты могут быть использованы также при решении прямых и обратных задач для системы ферромагнитных тел и в тестовых задачах для сравнения с другими методами.
Бесплатно
Расширение DVM-модели параллельного программирования для кластеров с гетерогенными узлами
Статья научная
В статье рассматриваются принципы расширения DVM-модели и построения языка Fortran DVMH для кластеров с гетерогенными узлами. Новые возможности языка позволяют: определить фрагменты программы, которые следует выполнять на том или ином ускорителе; определить данные, необходимые для выполнения заданного фрагмента программы; задать правила отображения витков цикла на ускоритель; управлять перемещением данных между оперативной памятью универсального процессора и памятью ускорителей. Описываются принципы построения компилятора с языка Fortran DVMH и новые функции системы поддержки параллельного выполнения программ Lib-DVMH. Приводятся экспериментальные данные об эффективности выполнения тестовых программ на графических процессорах кластера К-100. Появление компилятора с языка Fortran DVMH не только упростит разработку программ для кластеров с гетерогенными узлами, но и ускорит создание для таких кластеров автоматически распараллеливающего компилятора с языка Fortran, использующего язык Fortran DVMH в качестве выходного языка, на котором программист сможет проводить дополнительную ручную оптимизацию программы.
Бесплатно
Статья научная
В работе рассматривается применение расширенного распараллеливания для расчетов задач газовой динамики и аэроакустики на гетерогенных кластерах с узлами, сочетающими вычислительные элементы принципиально разной архитектуры, CPU и GPGPU. Двухуровневая модель распараллеливания MPI+OpenMP дополняется применением OpenCL для загрузки GPGPU, таким образом, реализуется третий уровень параллелизма. Представлена параллельная модель алгоритма для неструктурированных сеток.
Бесплатно
Реализация и композиция проблемно-ориентированных сервисов в среде MathCloud
Статья научная
В статье рассматриваются принципы реализации и основные компоненты сервис-ориентированной научной среды MathCloud. Целями данной среды являются предоставление унифицированного доступа к проблемно-ориентированным вычислительным сервисам и поддержка интеграции данных сервисов при решении прикладных задач. Во главу предлагаемого подхода к реализации среды MathCloud ставятся удобство разработки сервисов, простота доступа к сервисам пользователей и использование открытых технологий.
Бесплатно
Реализация параллельного алгоритма предсказания в методе градиентного бустинга деревьев решений
Статья научная
Описано несколько параллельных реализаций одного из алгоритмов обучения с учителем - градиентного бустинга деревьев решений (Gradient Boosting Trees) - с использованием библиотеки Intel Threading Building Blocks. Приводятся результаты экспериментального сравнения и анализ производительности различных подходов к распараллеливанию.
Бесплатно
Рекуррентный векторный метод матричных пучков
Статья научная
Метод матричных пучков оценивает параметры входных сигналов, являющихся суммой комплексных экспонент. Метод хорошо работает во многих приложениях (оценка направления прихода сигнала, прогнозирование сигнала во временной области, обработка сигналов кориолисового массового расходомера). Существуют множество модификаций классического метода, например: рекуррентный метод матричных пучков, позволяющий отслеживать параметры сигналов в режиме скользящего окна, и векторный метод, способный оценивать параметры сразу нескольких входных сигналов с одинаковыми полюсами. Подобная задача возникает при оценке параметров измерительных сигналов в кориолисовом массовом расходомере, где пара сигналов с его сенсоров имеет одинаковые частоты для всех мод колебаний. В данной статье представлена новая модификация - рекуррентный векторный метод матричных пучков, который является синтезом двух уже упомянутых методов и позволяет отслеживать параметры нескольких входных сигналов с одинаковыми полюсами в режиме скользящего окна. В статье приведены алгоритмы всех методов и их сравнение с помощью численного моделирования.
Бесплатно
Решение эллиптических уравнений в полигональных областях методом коллокации и наименьших квадратов
Статья научная
В данной работе рассматривается новый вариант метода коллокации и наименьших квадратов (КНК) для численного решения краевых задач для эллиптических уравнений в полигональных областях, в том числе в многосвязных. Возможности этого варианта и численные эксперименты рассмотрены на примерах решения уравнения Пуассона и неоднородного бигармонического уравнения. В качестве приложения решение неоднородного бигармонического уравнения использовано для моделирования напряженно-деформированного состояния (НДС) изотропной упругой тонкой пластинки полигональной формы, находящейся под действием поперечной нагрузки. Новый вариант метода КНК основан на триангуляции исходной области, чем принципиально отличается от предложенных ранее более сложных вариантов метода КНК решения краевых задач для уравнений с частными производными (УЧП) в нерегулярных областях. Установлено, что приближенные решения рассмотренных задач на последовательности измельчающихся сеток сходятся с повышением порядка и с высокой точностью совпадают с тестовыми решениями.
Бесплатно
Статья научная
Построено новое двухпараметрическое семейство разностных схем для численного решения уравнения Хопфа. Исходная задача заменялась задачей для системы двух дифференциальных уравнений на основе различных дивергентных форм уравнения Хопфа. Потоковые члены выражались в виде линейных комбинаций переменных, входящих в разные дивергентные формы. В отличие от большинства работ, использующих методы неопределенных коэффициентов для построения разностных схем, при таком подходе неопределенные коэффициенты возникают при формулировке дифференциальной задачи. Система уравнений сохраняет гиперболический тип при любых значениях параметров. Для численной реализации за основу выбрана известная сеточно-характеристическая схема в инвариантах Римана, которая в случае линейного уравнения с постоянными коэффициентами переходит в схему Лакса - Вендроффа. Проведены расчеты двух тестовых задач - об эволюции гладкого начального условия и формировании разрывного решения и о распространении "ударной волны". По результатам тестовых расчетов подобраны коэффициенты экстраполяции, позволяющие получить хорошее согласие с точным решением. Исследовался апостериорный порядок сходимости к предельной функции для разрывных решений. При удачно подобранных коэффициентах экстраполяции он незначительно превышает единицу в момент градиентной катастрофы. При распространении сильного разрыва на больших временах порядок сходимости падает до 0,76. Остается открытым вопрос о постановке оптимизационной задачи, позволяющей выбирать коэффициенты экстраполяции наилучшим образом, возможно, в зависимости от локальных свойств решения. Также открытым пока остается вопрос о создании гибридных разностных схем с переменными коэффициентами экстраполяции в зависимости от гладкости решения.
Бесплатно
Система обработки изображений с автоматическим распараллеливанием на основе MapReduce
Статья научная
Целью работы является создание системы обработки изображений в параллельном режиме под управлением Apache Hadoop на основе технологии MapReduce, которая скрывает от прикладного программиста детали внутреннего устройства Hadoop и предоставляет простой программный интерфейс для работы с изображением, уже загруженным в память. Основными результатами являются архитектура системы обработки изображений с автоматическим распараллеливанием на основе Hadoop и ее практическая реализация в виде первой очереди комплекса программ. Созданный комплекс программ применен для обработки изображений от системы Particle Image Velocimetry (источник данных - проект PIV Challenge). Тестирование комплекса программ на кластере Hadoop из четырех узлов показало почти линейную масштабируемость. Практическое применение возможно в научной сфере (обработка изображений от физических экспериментальных установок, астрономических наблюдений, спутниковых снимков земной поверхности и т.д.), медицине (обработка изображений, получаемых в результате применения высокотехнологичной медтехники) и коммерческих компаниях (анализ данных с камер видеонаблюдения в системах безопасности, в геоинформационных системах и т.п.). Предложенный подход позволяет повысить производительность обработки изображений за счет применения параллельных вычислительных систем и повышает эффективность работы прикладных программистов, позволяя им концентрироваться на алгоритмах обработки изображений, а не на деталях параллельной реализации.
Бесплатно
Статья научная
Численно моделируется процесс возбуждения и распространения бегущих упругих волн в многослойных анизотропных пластинах. В основу алгоритмов, реализованных в программном комплексе, положены явные интегральные представления решения соответствующих краевых задач и выведенные из них асимптотические представления для дальней от источника зоны. В ближней зоне, в том числе и под источником, амплитудно-частотные характеристики волнового поля определяются с помощью численного интегрирования несобственных контурных интегралов. Рассматриваются три подхода к вычислению волновых полей; на основе численных примеров проводится сравнительный анализ их эффективности.
Бесплатно
Стационарные точки уравнения реакция-диффузия и переходы в стабильные состояния
Статья научная
Рассмотрена бесконечномерная динамическая система, заданная уравнением реакция-диффузия с кубической нелинейностью при краевом условии Неймана и фиксированном значении средней величины. Изложена методика приближенного вычисления бифурцирующих решений при малых и конечных значениях закритического приращения параметра. Предложена также методика трассировки траекторий спуска из произвольного состояния (с произвольной концентрацией) в стабильное состояние (с концентрацией, реализующей минимум функционала энергии). Методика основана на вычислении сужения функционала энергии на линейную оболочку основных собственных функций (мод) оператора Лапласа и приближенном построении трассы спуска в виде последовательности точек, сопровождающих траекторию динамической системы. В случае малого закритического приращения бифуркационного параметра вычислены асимптотические представления бифурцирующих решений. В случае конечного закритического приращения бифуркационного параметра приведены примеры вычисления трассы спуска в точки минимума функционала энергии.
Бесплатно
Трехмерная визуализация модели течения многофазной затопленной струи
Статья научная
Во время добычи нефтепродуктов из недр морского шельфа есть опасность выброса углеводородов в толщу воды в виде многофазной струи. Особенность течения многофазной затопленной струи определяет скорость загрязнения водоема нефтью и зависит от теплофизических характеристик разлива и окружающей среды, в том числе от характера подводного течения. Проведенное исследование позволило выявить необходимость в визуализации многофазных затопленных струй на основе данных математического моделирования. Статья рассматривает возможности визуализации многофазной затопленной струи в пакете трехмерного моделирования Blender3D, для разработанного расширения подробно описано назначение и функциональные возможности. Визуальное отображение траектории струи интерпретирует в цветовом формате изменения температуры и концентрации. Программа позволяет отобразить многофазную затопленную струю в двух режимах: граничном и по объему. Разработанная программа дает возможность расширить представления о разливе согласно начальным и граничным условиям, что позволит в перспективе уменьшить время его ликвидации. Внедрение свободного и открытого ПО, как показывает практика, расширяет производственные процессы и позволяет реализовывать ранее недоступные проекты, при этом сокращая финансовые затраты.
Бесплатно
Статья научная
В статье рассматриваются вопросы автоматической генерации системнодинамической модели на основе данных реляционной модели предметной области. Вводится понятие концептуального шаблона системно-динамической модели. Рассматривается метод синтеза модели на основе группы шаблонов и сопоставленных им SQL-запросов к реляционной СУБД.
Бесплатно
Численное моделирование конвективного тепломассопереноса в сферических координатах
Статья научная
Целью исследования является построение дискретного аналога обобщенного дифференциального уравнения, описывающего конвекцию в вязкой несжимаемой жидкости в сферических координатах. Математическая модель конвективного тепломассопереноса в вязкой несжимаемой жидкости задается системой дифференциальных уравнений, полученных на основе уравнений гидродинамики, тепло- и массообмена. Эти уравнения подчиняются обобщенному закону сохранения, который описывается дифференциальным уравнением для обобщенной переменной. Для дискретизации дифференциального уравнения используется метод контрольного объема. Расчетная область разбивается на множество непересекающихся контрольных объемов с узловой точкой в каждом из них. Дифференциальное уравнение интегрируется по контрольным объемам. В результате получается дискретный аналог, связывающий значение обобщенной переменной в узловой точке с ее значениями в соседних узлах. Метод гарантирует строгое выполнение законов сохранения как во всей расчетной области, так и в любой ее части. Чтобы применять лучшие аппроксимации профилей обобщенной переменной, находятся точные решения уравнений сохранения отдельно по каждой координате. Кратко поясняется физический смысл точных решений. В итоге строится дискретный аналог для обобщенного дифференциального уравнения с использованием полученных аналитических решений.
Бесплатно
Численное решение интегральных уравнений Вольтерра I рода с кусочно-непрерывными ядрами
Статья научная
Интегральные уравнения Вольтерра имеют большое значение при построении математических моделей в физике, экономике, экологии и т.д. Важную роль во многих таких моделях играют рассматриваемые в данной статье линейные интегральные уравнения Вольтерра первого рода, у которых ядра претерпевают разрывы первого рода на определенных кривых, проходящих через начало координат. Приводятся теоретические результаты относительно вопросов существования и единственности решений таких уравнений и их регуляризации. Также для таких уравнений Вольтерра первого рода с кусочно-непрерывными ядрами предлагается эффективный численный метод решения, который основан на использовании квадратурной формулы средних прямоугольников. Указана оценка погрешности предлагаемого метода. Для модельных примеров приведены результаты численных расчетов, содержащие информацию о погрешностях и порядке сходимости.
Бесплатно
Численный анализ линеаризованной одномерной модели гидравлического скачка
Статья научная
В работе численно анализируется одномерная линейная задача о гидравлическом скачке. На основе известных формул решения линейной задачи, выражающих его через параметры модели, производится исследование решения на устойчивость. Построена система расчетов, позволяющих разделить области устойчивости, неустойчивости, и вычислять их общую границу - поверхность нейтральной устойчивости. Для случаев устойчивости и нейтральной устойчивости вычисляются основные асимптотические характеристики гидравлического скачка: асимптотика фронта и, соответственно, первая частота осцилляций. Результаты сопоставляются с имеющимися результатами численных расчетов для решения общей (нелинейной) модели.
Бесплатно
Эффективность модели программирования на базе явного задания легких тредов
Статья научная
Представлены результаты исследования эффективности выполнения параллельных программ, созданных на основе разных моделей программирования. Программы исполняются на SMP, образуемом на материнской плате несколькими многоядерными кристаллами. Одна модель основана на неявном для пользователя распределении порождаемых параллельных тредов по предоставляемым аппаратурой SMP ресурсам и традиционных подходах к синхронизации тредов. Эта модель представлена Open MP. Вторая модель использует явное задание распределения по ресурсам SMP легких тредов с использованием разработанной в Sandia National Laboratory библиотеки Qthreads.
Бесплатно
