+
ЧИСЛЕННАЯ РЕАЛИЗАЦИЯ МЕТОДА ПОВЕРХНОСТНОГО ДВИЖЕНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
стр.5-31
Соколинский Л.Б., Ольховский Н.А., Соколинская И.М.
Работа посвящена численной реализации нового метода линейного программирования, получившего название "метод поверхностного движения". В основе реализации лежит оригинальный алгоритм AlFaMove, который строит на поверхности допустимого многогранника оптимальный целевой путь от произвольной граничной точки до точки, являющейся решением задачи линейного программирования. Оптимальность пути заключается в том, что направление движения по грани многогранника соответствует максимальному увеличению значения целевой функции. Для вычисления оптимального направления движения используется метод, базирующийся на операции построения псевдопроекции на линейное многообразие. Операция псевдопроекции обобщает понятие ортогональной проекции и реализуется с помощью итерационного алгоритма проекционного типа. Доказано, что в случае линейного многообразия, образуемого путем пересечения гиперплоскостей, псевдопроекция совпадает с ортогональной проекцией. Также доказано, что в случае линейного многообразия метод на основе псевдопроектирования вычисляет вектор движения в направлении максимального увеличения целевой функции. Выполнена параллельная реализация алгоритма AlFaMove. Приведены результаты вычислительных экспериментов на кластерной вычислительной системе, демонстрирующие высокую масштабируемость предложенной численной реализации.
Загружаем данные из библиотечной системы...
Ключевые слова
+
ПРОЕКТИРОВАНИЕ ОПТИМАЛЬНОЙ ТРАЕКТОРИИ ПРОВЕДЕНИЯ МОНИТОРИНГА ОБЪЕКТОВ
стр.32-46
Саллам М., Макаровских Т.А.
В статье рассматривается задача разработки системы для моделирования траекторий движения робота, проводящего мониторинг в замкнутой области с земли: осмотр помещений, съемка промышленных объектов, оценка состояния фруктовых деревьев и т.д. Во время мониторинга на пути робота могут возникнуть некоторые препятствия: временно возникшие и устранимые (люди, небольшая мебель, бытовая техника, зона чрезвычайной ситуации) или постоянные (стены, постоянно установленное оборудование, зафиксированная мебель). Управление роботом осуществляется с помощью разработанной авторами программы, в которой хранится база данных маршрутов, успешно преодоленных роботом ранее, для наиболее точного определения траектории движения робота с учетом препятствий, встречающихся вдоль построенного пути. В статье рассматривается алгоритм построения графовой модели области проведения мониторинга для последующего поиска кратчайшего маршрута робота, заключающийся в дискретизации исследуемой области, выявлении возможных путей перемещения робота, анализе имеющихся препятствий и задании расстояний между объектами исследования. Показано, что после построения такого графа возможно применить один из алгоритмов поиска гамильтонова пути. Он соединяет вершины графа, соответствующие точкам проведения мониторинга. Результатом применения алгоритма будет кратчайший маршрут робота, либо сообщение о невозможности проведения мониторинга (частичной или полной неразрешимости задачи), если ряд возникших препятствий не позволяет проложить маршрут, проходящий через некоторые (либо через все) вершины. Выбор наиболее подходящего алгоритма, а также использование методов искусственного интеллекта для классификации препятствий и внесения корректировок в маршруты являются направлениями дальнейших исследований.
Загружаем данные из библиотечной системы...
Ключевые слова
+
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ТРЕМЯ WORK-STEALING ДЕКАМИ В ДВУХУРОВНЕВОЙ ПАМЯТИ
стр.47-60
Аксёнова Е.А., Барковский Е.А., Соколов А.В.
При выполнении параллельных вычислений возникает проблема равномерного разделения задач между потоками. Одним из способов решения этой проблемы является применение распределенной динамической балансировки нагрузки. При таком способе балансировки каждый рабочий поток имеет свою очередь задач и потоки сами занимаются дальнейшем распределением задач. Широкое распространение получил метод балансировки «work-stealing», в котором один поток, у которого закончились задачи, может перехватывать задачи других потоков. Для реализации такого метода у каждого потока должен быть свой специализированный дек, в котором хранятся указатели на задачи. В этой статье предлагается и исследуется новый метод представления трех work-stealing деков в двухуровневой памяти. Рассматривается случай работы с тремя деками, когда в одном разделе быстрой памяти расположены две LIFO-части деков - два стека, которые растут навстречу друг другу, в другом разделе быстрой памяти расположены три FIFO-части, которые объединены в одну FIFO-очередь, из которой элементы только исключаются (кражи), и третья LIFO-часть. Средние части деков находятся в медленной памяти, обращение к ним происходит при переполнении или опустошении LIFO-частей или опустошении FIFO-частей деков, расположенных в быстрой памяти. Рассматривается задача оптимального разделения быстрой памяти для трех деков с заранее заданными вероятностями выполнения операций. Этот выбор зависит от характеристик уровней памяти, вероятностей операций и критерия оптимальности. В качестве критерия оптимальности рассматривается максимальное среднее время работы системы (среднее количество операций) до перераспределения памяти.
Загружаем данные из библиотечной системы...
Ключевые слова
+
TASC SOFTWARE FOR HPC PERFORMANCE ANALYSIS: CURRENT STATE AND LATEST DEVELOPMENTS
стр.61-78
Voevodin V.V., Shaikhislamov D.I., Serov V.A.
To ensure high operating efficiency of modern supercomputers, it is necessary to constantly analyze and control various aspects of their behavior, paying special attention to the flow of supercomputer applications running on these machines. To solve this problem, the TASC (Tuning Applications for SuperComputers) software suite was previously developed. It automatically detects performance issues in HPC applications and evaluates the efficiency of using supercomputer resources, provides supercomputer administrators with a flexible report tool for analyzing different aspects of supercomputer functioning with the desired level of detail, and estimates the noise level on compute nodes. This paper provides full-scale description of current TASC structure and capabilities, including the stages of data processing and storing, as well as performing different types of analysis. It also describes new results obtained and methods developed within one of the main TASC components - assessment system for quick and accurate evaluation of HPC resources usage efficiency.
Загружаем данные из библиотечной системы...
Ключевые слова
+
КЛАССИФИКАЦИЯ ПОТОКОВОГО ВРЕМЕННОГО РЯДА НА ОСНОВЕ НЕЙРОСЕТЕВЫХ ТЕХНОЛОГИЙ И ПОВЕДЕНЧЕСКИХ ШАБЛОНОВ
стр.79-94
В статье представлен метод SALTO (Snippet and Autoencoder-based Labeling of Time series coming Online), позволяющий выполнять классификацию подпоследовательностей временного ряда, элементы которого поступают для обработки непрерывным потоком в режиме реального времени. Областью применения разработанного метода являются приложения персональной медицины, промышленного Интернета вещей и цифровой индустрии, в которых предъявляются высокие требования ко времени реакции системы: не более 10 мс в соответствии со стандартом URLLC (Ultra-Reliable Low Latency Communications, сверхнадежная связь с малой задержкой). Метод SALTO предполагает предварительную обработку предварительно сохраненного репрезентативного фрагмента потокового временного ряда и распознавание подпоследовательностей этого ряда, поступающих в реальном времени, c помощью нейросетевой модели. Предобработка выполняется без участия учителя c помощью параллельного алгоритма, который автоматизирует поиск поведенческих шаблонов (сниппетов) ряда, используемых для формирования обучающей выборки. Нейросетевая классификационная модель использует архитектуру автоэнкодеров. Энкодер модели преобразует входную подпоследовательность в скрытое представление и включает в себя два сверточных слоя и один рекуррентный слой. Декодер модели состоит из одного рекуррентного слоя и двух транспонированных сверточных слоев, зеркально отражающих параметры Энкодера. В вычислительных экспериментах на стандартных тестах метод SALTO более чем в полтора раза опережает в среднем передовые аналоги по быстродействию, вписываясь в рамки стандарта URLLC, и при этом показывает в среднем более высокую точность, чем большинство указанных аналогов.
Загружаем данные из библиотечной системы...
Ключевые слова
