Статьи журнала - Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика
Все статьи: 316
Сравнение областей истинности запросов к реляционной базе данных
Статья научная
В данной статье предлагается описание подходов аналитического сравнения пользовательских запросов к реляционной базе данных. Такое сравнение имеет целью установление возможности частичного или полного использования закэшированных на компьютере пользователя запросов к СУБД и основано на применении аппарата логики предикатов, где в качестве формул выступают логические ограничения SQL, а предикатами служат элементарные операции SQL. В случае, если результат выполнения пользовательского запроса полностью содержится в кэше, то данные можно взять оттуда, минуя запрос к удаленному серверу. Описанные подходы выражены в алгоритме использования кэшированных данных. Предложенный алгоритм также может быть использован для определения недостающих в кэше данных и последующего запроса только на эти данные. Для этого также используются аналитические вычисления, что экономит сетевой трафик и время на выполнение запросов и является принципиальным отличием данной технологии от существующих аналогов.
Бесплатно
Сравнение производительности пакетов симуляции квантовых вычислений QuEST и Intel-QS
Статья научная
В ближайшем будущем появятся квантовые компьютеры, пригодные для практического использования. Разработка квантовых алгоритмов может проводиться с использованием классических компьютеров и специализированного программного обеспечения, позволяющего симулировать работу квантовой схемы. Результаты моделирования могут использоваться для анализа алгоритма, а также способствуют ко-дизайну при разработке квантовых архитектур. Однако при планировании и выполнении численных экспериментов необходимо понимать возможности симуляторов и ограничения на параметры квантовой схемы, накладываемые характеристиками доступных классических вычислительных ресурсов. В работе представлены результаты вычислительных экспериментов по симуляции работы квантовых схем на идеальном квантовом компьютере с использованием пакетов QuEST и Intel-QS, а также собственной «наивной» реализации. Показаны ограничения на размер моделируемой квантовой системы N при использовании вычислительных систем различного класса - виртуальной машины, вычислительного сервера, вычислительного сервера с графическим ускорителем, суперкомпьютера (маскимальный достигнутый размер N = 33). Приведены характеристики производительности и масштабируемости рассматриваемых реализаций на общей и распределенной памяти (наблюдаемая эффективность масштабирования - 30 % и 70 % соответственно). Для пакета QuEST и собственной реализации представлена производительность при использовании графических сопроцессоров.
Бесплатно
Сравнение целевых функций в задаче Прони для аппроксимации данных измерений
Статья научная
В работе проводится сравнение двух целевых функций в задаче Прони аппроксимации данных измерений решениями линейного дифференциального уравнения заданного порядка с постоянными коэффициентами. Целевые функции различаются типом зависимости градиента от коэффициентов уравнения (линейная или со сложной нелинейностью) и являются 1) нормой невязки уравнения (линейный метод наименьших квадратов) или 2) нормой ошибки аппроксимации по А. Хаусхолдеру (вариационный метод идентификации). В последнем случае производится совместная оптимизация коэффициентов дифференциального уравнения и начальных условий решения. Для рассмотренных целевых функций вычислены константы локальной устойчивости решения задачи Прони с использованием локальных разложений зависимостей оптимальных коэффициентов уравнения как неявных функций от данных из условия равенства градиента целевой функции нулю. На этой основе предложен способ определения допустимой погрешности в данных задачи для обеспечения заданного уровня отклонения решения от истинного значения. На примере К. Ланцоша вычисления показателей экспонент по наблюдениям суммы трех экспонент с ошибками округления показано существенное преимущество (с точки зрения допустимой погрешности в данных) использования вариационной целевой функции. Адекватность используемых локальных показателей устойчивости для немалых возмущений проверяется численным экспериментом.
Бесплатно
Статья научная
Проводится сравнение эффективности CPU и GPU реализаций некоторых комбинаторных алгоритмов, используемых в криптоанализе. В частности, анализируются причины, по которым не удается эффективно реализовать на GPU алгоритмы, осуществляющие «интеллектуальный перебор». Показывается, что применение специальных техник трансформации потока управления позволяет существенно компенсировать потери производительности, возникающие из-за неэффективного исполнения условных переходов на SIMD-устройстве. Однако ограничения, которые накладывают механизмы работы с памятью, применяемые в современных GPU, для рассматриваемых алгоритмов оказываются непреодолимыми. В качестве тестовых задач рассматриваются задачи обращения криптографических функций DES и A5/1.
Бесплатно
Краткое сообщение
В работе предложена динамическая модель конкурентного поведения предприятий сотовой связи в виде системы дифференциальных уравнений с запаздыванием. Реализованы численные методы и алгоритмы для решения задачи оптимального управления поведением операторов сотовой связи в условиях конкурентной борьбы за потребителей услуг связи. Сформулирована и решена задача оптимального управления поведением предприятий сотовой связи с постоянным запаздыванием с использованием принципа максимума Понтрягина для систем с постоянным запаздыванием. Получены условия оптимальности для решения задачи управления динамикой развития абонентской базы фирмы № 1. Реализован метод линеаризации системы нелинейных дифференциальных уравнений с запаздыванием и проведен поиск оптимального решения задачи посредством операций улучшения управления, повторяемых в итерационной процедуре, на примере метода Шатровского.
Бесплатно
Статья научная
В статье рассматриваются существующие средства проектирования цифровых устройств в программируемых логических интегральных схемах (ПЛИС), языки программирования реконфигурируемых вычислительных систем и возможность их использования при программировании многокристальных реконфигурируемых вычислительных систем. Также рассмотрены разработанные в НИИ МВС ЮФУ язык программирования высокого уровня COLAMO и комплекс средств разработки многокристальных решений на реконфигурируемых вычислительных системах. Особое внимание уделено новому подходу в программировании, заключающемуся в разработке и использовании настраиваемых проблемно-ориентированных софт-архитектур, которые позволяют сократить количество трансляций конфигурационных файлов ПЛИС при отладке параллельных программ на реконфигурируемых вычислительных системах. Проблемно-ориентированные софт-архитектуры дают возможность без перезагрузки файлов конфигурации ПЛИС вычислительного поля с помощью программной настройки изменять коммутацию между устройствами и создавать необходимые вычислительные структуры для решения прикладных задач пользователя, что существенно сокращает время отладки параллельных прикладных программ.
Бесплатно
Статически-детерминированный метод прогнозирования динамических характеристик параллельных программ
Статья научная
В статье рассматривается задача прогнозирования характеристик параллельных приложений. Изучаются динамические характеристики, описывающие выполнение параллельных приложений - время выполнения, количество операций с плавающей точкой, потребляемая электроэнергия, количество обращений в память и другие. Прогнозирование динамических характеристик позволяет решать многие проблемы, связанные с проектированием новых архитектур, выбором наиболее подходящих конфигураций многопроцессорных систем для решения конкретных задач, портированием приложений на новые системы, планированием потоков задач и многие другие. Задача прогнозирования характеристик активно исследуется. Возрастающая сложность архитектур современных высокопроизводительных систем требует разработки новых методов решения задачи прогнозирования. В статье дается обзор существующих подходов и программных средств для прогнозирования динамических характеристик и предлагается подход, основанный на статическом анализе исходного кода параллельного приложения. На основе текста параллельной программы, формального описания целевой вычислительной платформы и параметров запуска реализован метод, позволяющий прогнозировать время работы, количество выполненных операций вещественной арифметики, обращения к памяти и другие характеристики параллельного приложения. Применимость предложенного подхода продемонстрирована на примере решения тестовой трехмерной задачи численного моделирования на многопроцессорном кластере на базе процессоров IBM Power8.
Бесплатно
Статья научная
При параллельной реализации итерационных численных методов на регулярных сетках возникает необходимость в статической или динамической балансировке вычислительной нагрузки. Для исследования того или иного алгоритма балансировки нагрузки важно проводить его разносторонее тестирование на множестве различных задач рассматриваемого класса с различными конфигурациями вычислителя и различными наборами входных данных задач. В статье представлен тестовый стенд, предназначенный для автоматизации проведения такого тестирования. Он позволяет описать прикладную задачу и подключить реализацию алгоритма статической или динамической балансировки вычислительной нагрузки для последующего тестирования на мультикомпьютере. На выходе стенд предоставляет информацию о том, как происходило исполнение итерационного сеточного метода с точки зрения баланса вычислительной нагрузки. Приведен пример использования стенда для исследования диффузионного алгоритма динамической балансировки нагрузки на процессоры мультикомпьютера.
Бесплатно
Структурно-иерархическая дидактическая модель электронного обучения
Статья научная
В данной статье описывается оригинальная структурно-иерархическая дидактическая (СИД) модель электронного обучения В основе модели лежит четырехуровневая методическая база знаний. Первый уровень включает в себя комплекс электронных учебных энциклопедий по различным областям знаний. Второй уровень включает в себя электронные учебные курсы. Модель поддерживает структурирование электронного учебного курса по дидактическим компонентам (вертикальное слоение) и уровням детализации (горизонтальное слоение). Третий уровень включает в себя комплекс рабочих учебных программ. Четвертый уровень включает в себя комплекс ФГОС ВО. Отличительной особенностью СИД модели является деление образовательных объектов на дидактические компоненты. Это позволит, во-первых, производить автоматическую верификацию дидактической полноты электронного учебного курса. Во-вторых, включать части одного курса в другой без потери дидактической структуры. В-третьих, выделять из электронного учебного курса отдельный дидактический слой и на его основе автоматически формировать специализированные учебно-методические материалы: конспекты лекций, сборники задач, экзаменационные тесты и др. Описаны основные операции СИД модели, на основе которых предложены алгоритмы по анализу образовательных программ и электронных учебных курсов. В заключении дается краткая сводка результатов и направления дальнейших исследований.
Бесплатно
Сходимость метода конечных элементов для краевой задачи с вырождением на всей границе области
Статья научная
В статье рассматривается задача Дирихле с однородным граничным условием для эллиптического уравнения второго порядка с вырождением на всей дважды непрерывно дифференцируемой границе двумерной области Ω. Определяется обобщенное решение этой задачи, которое существует и единственно в весовом пространстве Ŵ12,α(Ω). Для решения сформулированной задачи разработан метод конечных элементов, схема которого построена на основе определения обобщенного решения исходной дифференциальной задачи в пространстве Ŵ12,α(Ω). С этой целью двумерная выпуклая область разбивается на треугольники со специальным сгущением к границе. Далее, введено пространство конечных элементов Vh ⊂ Ŵ12,α(Ω), которое содержит непрерывные функции, линейные на каждом треугольном элементе сеточной области Ωh и равные нулю на множестве Ω' \ Ωh, показана однозначная разрешимость схемы метода конечных элементов. Для обобщенного решения u из подпространства Ŵ22,α-1(Ω) пространства Ŵ12,α(Ω), используя значения в узлах триангулированной области Ωh, строится интерполянт uI∈ Vh, устанавливается факт его сходимости по норме W12,α(Ω). Главным результатом работы является доказательство сходимости приближенного решения предложенного метода к точному решению в весовом пространстве Соболева.
Бесплатно
Тенденции развития вычислительных узлов современных суперкомпьютеров
Статья научная
В данной работе выполнен анализ вычислительных узлов современных суперкомпьютеров с двух точек зрения - аппаратно-компонентной и инфраструктурной. На основании проведённого анализа названы основные конструктивные элементы, которыми должен быть оснащен современный вычислительный узел. В статье приведены классификации архитектур современных универсальных и специализированных ядер с примерами; проведен обзор современных тенденций организации подсистемы памяти и внутриузлового интерконнекта; упомянуты способы использования энергонезависимых устройств хранения на узлах при организации современных высокопроизводительных систем хранения. Также разобраны основные требования к организации инфраструктуры узла современного суперкомпьютера, в частности, дана краткая классификация современных подходов к организации жидкостного охлаждения и мониторинга вычислительных узлов. Выявленные тенденции приводят к основным вариантам дизайна вычислительных узлов, состоящих из энергоэффективного универсального процессора и совокупности энергоэффективных специализированных ускорителей. В статье сделан акцент на современных технологиях, которые достигли стадии выхода в производство или, как минимум, создания рабочих прототипов. Обсуждаются современные суперкомпьютерные задачи и их отображение на архитектуру вычислительных узлов. В заключении приведено кратное обсуждение актуальных технологических проблем и основных направлений для сохранения прогресса в компьютерной отрасли.
Бесплатно
Статья научная
В работе рассматриваются вычислительные технологии решения задач, связанных с моделированием распространения сейсмических волн в неоднородных средах, характерных для вулканических структур, с использованием суперкомпьютерного моделирования в целях создания систем вибросейсмического мониторинга сейсмоопасных объектов. Построена физико-математическая модель магматического вулкана и программная реализация на основе известного численного метода, эффективно использующая архитектуру современного суперкомпьютера, оснащенного GPU. Созданы параллельные 2D и 3D алгоритмы и программы для моделирования распространения упругих волн в сложно построенной среде (2D модель есть сечение исходной 3D модели различными плоскостями и под разными углами) на основе явной конечно-разностной схемы на сдвинутых сетках и метода поглощающих границ CFS-PML. Исследована масштабируемость алгоритмов. Применение разработанной технологии позволяет гораздо эффективней проводить изучение структуры волнового поля, обусловленного геометрией внутренних границ, уточнение его кинематических и динамических характеристик.
Бесплатно
Технология фрагментированного программирования
Статья научная
Кратко представлена технология фрагментированного программирования и реализующие ее язык и система фрагментированного программирования LuNA, разрабатываемые в ИВМиМГ СО РАН. Технология ориентирована на поддержку разработки параллельных программ, реализующих большие численные модели, и их исполнения на суперкомпьютерах. Система LuNA автоматически обеспечивает такие динамические свойства параллельных программ как динамическая настройка на все доступные ресурсы, динамическая балансировка нагрузки, учет динамики поведения моделируемого явления и т.п.
Бесплатно
Топологические резервы «Сплющенных» системных сетей
Статья научная
Рассматривается метод изменения топологии 2-шаговой системной сети «сплющенная бабочка» (Flattened Butterfly), обеспечивающий уменьшение размеров составляющих ее коммутаторов и, как следствие, уменьшение схемной сложности и энергопотребления при сохранении числа абонентов (процессоров), диаметра сети и коммутационных свойств. При сохранении размеров коммутаторов предлагаемый метод позволяет существенно увеличить число абонентов при сохранении диаметра сети.
Бесплатно
Статья научная
В работе рассмотрены схемы второго и четвертого порядков погрешности аппроксимации для решения задачи диффузии-конвекции. Для модельной начально-краевой задачи, в случае когда функции правой части и начального условия представимы конечными суммами рядов Фурье по тригонометрическому базису, исследована точность разностных схем. Установлено, что точность численного решения зависит от количества узлов приходящихся на половину длины волны, соответствующей наиболее высокочастотной гармонике в конечной сумме ряда Фурье, необходимой для описания поведения расчетных объектов. Получены зависимости погрешности аппроксимации диффузионных слагаемых разностными схемами второго и четвертого порядков точности от количества узлов. Выполнено сопоставление результатов расчета двумерной задачи диффузии-конвекции и задачи Пуассона на основе схем второго и четвертого порядков точности. В работе обоснована целесообразность перехода к схемам повышенного порядка точности при решении прикладных задач и из полученных оценок нетрудно получить численные значения выигрышей во времени счета при использовании схем повышенного порядка точности.
Бесплатно
Тэта-функции в математической модели шума квантования
Статья научная
В статье выведена новая формула для двухмерной плотности распределения вероятности шума квантования, которая позволила записать ее с помощью математического выражения, которое состоит только из тэта-функций Якоби. Приведен способ получения данной формулы. Вывод формулы основан на том, что при подходящей замене переменных часть членов двойного ряда уничтожается. Показан принцип получения всех формул данного семейства. Этот принцип основан на свойствах симметрии тэта-функций. Симметрия тэта-функций позволяет выражать одну тэта-функцию через другую тэта-функцию и получать формулы, состоящие только из тэта-функций Якоби. Это семейство формул позволяет получать выражения для организации модельных экспериментов, поддерживаемые основными математическими пакетами. Они позволяют получать и числовые характеристики случайных процессов, как функции параметров, порождающих их случайных процессов гауссовского типа в аналитическом виде. Их применение увеличивает скорость сходимости результатов моделирования. Полученные формулы позволят выполнять синтез нужных выражений в аналитическом виде при функциональных преобразованиях случайных векторов и процессов, при обработке сигналов.
Бесплатно
Удаленная визуализация больших объемов данных
Статья научная
Вычислительные мощности и аппаратные характеристики персональных вычислительных устройств не всегда позволяют обеспечить должный уровень производительности для обеспечения визуализации больших объемов данных, возникающих в результате решения различных задач с использованием суперкомпьютерных вычислительных систем. Для обеспечения прозрачного и удобного доступа к таким данным может применяться подход удаленной визуализации, при котором клиент используется исключительно для отображения видео-информации с одного или нескольких удаленных серверов визуализации. В данной работе рассматриваются виды удаленной визуализации, используемые технологии, для обеспечения взаимодействия между клиентскими приложениями и удаленными серверами, анализируются различные подходы к решению задачи удаленной визуализации.
Бесплатно
Статья научная
Данное исследование направлено на увеличение эффективности методик государственного регулирования рынка естественной монополии. В качестве методов регулирования рассматривается применение неценовых рычагов. Эффективность системы управления, скорость реакции на внешние изменения зависит от адаптивности. Решение проблемы адаптации государства к изменению ситуации на рынке происходит циклически. На каждом шаге решается две задачи: построение модели взаимодействия монополиста и покупателя при заданных корректирующих государственных регуляторах (рынок рассматривается как замкнутая система); построение модели взаимодействия государства с рынком и оценка характеристик адаптивности государства. Решение задачи основано на определении равновесия по Штакельбергу в бескоалиционных играх двух лиц в смешанных стратегиях. При этом скорость, эффективность, оптимальность выбора государством корректирующего варианта и непосредственно момента его выбора характеризует адаптивность государства.
Бесплатно
Условная минимизация слабоунимодальных функций методом бинарного сканирования (бискана)
Статья научная
Предложен метод бинарного сканирования (бискана) для условной минимизации слабоунимодальных функций. Областью приложения данного метода является оптимизация кусочных, ступенчатых, релейных и иных слабоунимодальных функций, экстремум которых может быть локализован, как в узких, так и протяженных областях, включая области постоянства минимизируемой функции. Алгоритм, реализующий метод, представлен двумя процедурами, блок-схемы которых приведены в статье. Для оценки работоспособности бискана был проведен сравнительный вычислительный эксперимент на примерах минимизации ряда слабоунимодальных функций. Установлено, что в сравнении с конкурирующими методами, в частности с методом золотого сечения и методом последовательного перебора, бискан дает лучшие показатели быстродействия. Наибольшее быстродействие метод обеспечивает при минимизации непостоянных монотонных функций. Для определения экстремума требуется лишь пять вычислений такой функции. В сравнении с методом золотого сечения бискан имеет в 1,5 раза большее быстродействие при решении задач данного типа. При минимизации строго слабоунимодальных функций, к которым не применимы известные методы минимизации унимодальных функций, в частности, метод золотого сечения, бискан работает на порядки быстрее конкурирующего метода последовательного перебора.
Бесплатно
Учебный курс «Программирование с использованием модели OneApi»
Статья научная
Современные высокопроизводительные вычислительные системы в массе своей являются гетерогенными. Разработка параллельных программ, способных использовать весь потенциал таких систем, сопряжена со значительными сложностями - требуется не только применять соответствующие языки и технологии программирования, но и учитывать особенности центральных и графических процессоров, влияющие в том числе на схемы организации параллелизма и работу с памятью. На упрощение процесса разработки таких программ направлена модель гетерогенного программирования oneAPI, представленная компанией Intel, и ее ключевой компонент - язык Data Parallel C++, позволяющий разрабатывать переносимые высокопроизводительные программы для CPU, GPU, FPGA и других устройств. В статье представлен учебный курс по oneAPI, разработанный в ННГУ им. Н. И. Лобачевского. Курс направлен на изучение широкого спектра вопросов, связанных с высокопроизводительными вычислениями с использованием моделей, методов и инструментов параллельного программирования на платформах Intel. В статье представлена концепция курса, описана его структура, категории слушателей, которым он может быть интересен, и варианты построения курса в зависимости от уровня подготовки аудитории.
Бесплатно
