Preview

Труды Института системного программирования РАН

Расширенный поиск
Том 31, № 2 (2019)
Скачать выпуск PDF
7-13 135
Аннотация

В этом специальном выпуске содержатся избранные статьи, представленные в Труды Института системного программирования Российской академии наук. Тринадцать материалов из девяти стран (Англии, Мексики, Китая, Уругвая, Испании, Пакистана, Кубы, Доминиканской Республики и России) охватывают несколько важных тем в быстро расширяющейся области исследований и разработок, связанных с продвинутыми компьютерными методами. Авторы демонстрируют спектр подходов для решения сложных задач, таких как  ориентированное на данные планирование, потоки научных работ, облачные вычисления, эволюционные алгоритмы, сети распространения контента, мягкие вычисления, модели параллельного программирования для многоядерных машин, высокопроизводительные вычисления, интеллектуальный анализ данных, защита авторских прав на программное обеспечение, обнаружение аномалий, групповая робототехника, нейронные сети, машинное обучение, безопасность, схемы разделения секрета, гетерогенные распределенные вычисления и Интернет вещей.

15-20 107
Аннотация

В данной статье представлено применение мягких вычислительных методов для решения задачи проектирования и оптимизации облачных сетей распространения контента (CDN). Для решения проблемы выделения ресурсов для построения сетевой инфраструктуры применяется многоцелевой подход с учетом цели минимизации стоимости виртуальных машин, сети и хранилища, а также максимизации качества обслуживания, предоставляемого конечным пользователям. Предлагается конкретная модель посредничества, которая позволяет одной облачной CDN размещать нескольких поставщиков контента, применяющих стратегию совместного использования ресурсов. На основе предложенной модели посредничества изучаются три многоцелевых эволюционных подхода оффлайновой оптимизации предоставления ресурсов, а для решения проблемы онлайновой маршрутизации контента предлагается жадный эвристический метод. Экспериментальная оценка предложенного подхода выполняется на наборе реалистичных частных случаев. Полученные экспериментальные результаты показывают, что предложенный подход эффективен для проектирования и оптимизации облачных сетей распространения контента: общие затраты снижаются на 10,34% при сохранении высокого уровня качества обслуживания.

21-31 92
Аннотация

В этой статье представлено применение метода Виртуального Эрудита (Virtual Savant) для решения проблем распределения ресурсов, широко изученной области с несколькими реальными приложениями. Virtual Savant – это новый метод мягких вычислений, в котором используются методы машинного обучения для вычисления решений данной проблемы оптимизации. Цель Virtual Savant – научиться решать данную проблему с помощью решений, рассчитанных по эталонному алгоритму, а его дизайн позволяет использовать преимущества современных параллельных вычислительных инфраструктур. Предложенный подход оценивается на решении задачи о рюкзаке, которая моделирует различные варианты задач распределения ресурсов, учитывая набор экземпляров разного размера и сложности. Экспериментальный анализ проводился на многоядерном сервере Intel Xeon Phi. Результаты показывают, что Virtual Savant способен вычислять точные решения, демонстрируя хорошие свойства масштабируемости при увеличении объема используемых вычислительных ресурсов.

33-39 76
Аннотация

Раннее оповещение во время обзора неба дает важную возможность обнаруживать одиночные планеты с малой массой. В статье представлен гибридный метод, в котором комбинируется модель ARIMA (интегрированная модель авторегрессии – скользящего среднего) и рекуррентные нейронные сети (RNN) LSTM (нейронная сеть с блоками долго-кратковременной памяти) и GRU (управляемый рекуррентный нейрон), обеспечивающий возможность поиска кратковременных событий микролинзирования (ML) в режиме реального времени на основе данных, получаемых путем высокочастотной широкоугольной съемки звездного неба. Метод обеспечивает мониторинг всех наблюдаемых кривых блеска и выявление событий ML на ранних стадиях. Экспериментальные результаты показывают, что гибридные модели обеспечивают большую точность и требуют меньше времени на настройку параметров. ARIMA + LSTM и ARIMA + GRU могут повысить точность на 14,5% и 13,2% соответственно. При обнаружении аномалий в кривых блеск, GRU может достичь почти того же результата, что и LSTM, затрачивая на 8% меньшее время. Те же модели применимы и к набору данных ЭКГ в базах данных MIT-BIH по аритмии с похожим паттерном аномалий, и в обоих случаях мы можем сократить на 40% временя, которое требуется исследователям для настройки модели, с сохранением 90% точности.

41-52 101
Аннотация
В статье рассматривается вопрос поиска глобального экстремума при обучении искусственных нейронных сетей с помощью корреляционного показателя. Предложенный метод базируется на математической модели искусственной нейронной сети, представленной в виде системы передачи информации. Эффективность предлагаемой модели подтверждается широким применением ее в системах передачи информации для анализа и восстановления полезного сигнала на фоне различных помех: гауссовых, сосредоточенных, импульсных и т.п. Проводится анализ сходимости обучающей и полученной экспериментально последовательностей на основе корреляционного показателя. Подтверждается возможность оценки сходимости обучающей и экспериментально полученной последовательностей на основе взаимно-корреляционной функции как мере их энергетической схожести (различия). Для оценки предложенного метода проводится сравнительный анализ с используемыми в настоящее время целевыми показателями. Исследуются возможные источники ошибок метода наименьших квадратов и возможности предлагаемого показателя по их преодолению.
53-66 81
Аннотация

Беспроводные локальные сети (WLAN) 802.11 могут поддерживать несколько скоростей передачи данных на физическом уровне с использованием схемы адаптивной модуляции и кодирования (AMC). Однако эта возможность поддержки разных скоростей передачи данных вызывает в WLAN серьезную аномалию производительности. В сети, состоящей из нескольких узлов с разными скоростями передачи, узлы с более низкой скоростью передачи данных (медленные узлы) ухудшают пропускную способность узлов с более высокими скоростями передачи (быстрые узлы). Основным источником этой аномалии является механизм доступа к каналу WLAN, который обеспечивает долгосрочную равную вероятность доступа к каналу для всех узлов независимо от их скоростей передачи. В этой работе мы исследуем использование адаптируемого разделения на каналы по ширине, чтобы минимизировать влияние этого явления на производительность. Отмечается, что ширина канала, избыточная из-за более низкой скорости передачи медленных узлов, может быть назначена быстрым узлам, подключенным к другим точкам доступа (AP), что может существенно увеличить общую пропускную способность всей сети. Мы предлагаем алгоритм предотвращения аномалий на уровне управления доступом к среде (MAC), который назначает ширину канала узлам, связанным с различными точками доступа, на основе их скорости передачи. Мы смоделировали эффект адаптивного разделения на каналы и установили нижнюю и верхнюю границы пропускной способности в различных сетевых сценариях. Наши эмпирические результаты указывают на возможное увеличение пропускной способности сети более чем на 20% при использовании предложенного алгоритма MIAP.

67-81 131
Аннотация
В настоящее время искусственный интеллект и групповая робототехника становятся широко распространенными и используются в гражданских задачах. Основная цель статьи – показать возможность использования знаний о совместном окружении группы роботов при решении задачи навигации путем обеспечения передачи данных между роботами. В методике, представленной в статье, рассматривается комплекс задач, выполнение которых улучшает результаты роботизированной групповой навигации. Исследование затрагивает проблемы робототехнического зрения, планирования путей, хранения и обмена данными. В статье описывается структура лазерной системы технического зрения реального времени как основного инструмента взаимодействия роботов с окружающей. В системе зрения используется принцип динамической триангуляции. В статье приведены примеры полученных данных, методы сохранения разрешающей способности сканирования на расстоянии и контроля скорости. В соответствии с данными, полученными с помощью предоставленной системы зрения, было решено использовать матричный подход для планирования пути роботов, что позволяет решать задачи дискретизации окружения и аппроксимации траектории. Сравниваются два типа структуры сети для передачи данных. Авторы предлагают методологию формирования динамической сети на основе системы смены лидеров. Для апробации теории было разработано программное обеспечение для моделирования группы роботов. Полученные результаты показывают, что обмен знаниями внутри группы может значительно улучшить планирование траекторий движения роботов.
83-96 92
Аннотация

В статье представлен новый подход к решению важных практических проблем комплексной отладки, совместного тестирования и анализа времени выполнения версий программных модулей в распределенной вычислительной среде. Эти проблемы возникают в процессе поддержки непрерывной интеграции функционального наполнения (прикладного программного обеспечения) распределенных пакетов прикладных программ (научных приложений). Исследование ориентировано на пакеты, которые используются для проведения крупномасштабных экспериментов, осуществляемых в рамках междисциплинарных исследований, в гетерогенных распределенных вычислительных средах, интегрирующих Grid и облачные вычисления. Научная новизна предложенного подхода заключается в объединении методологии создания распределенных пакетов прикладных программ с современной практикой разработки программного обеспечения на основе его непрерывной интеграции с использованием знаний о специфике решаемых задач. Средства непрерывной интеграции, разрабатываемые в рамках предложенного подхода, существенно расширяют спектр ее возможностей применительно к процессам создания и использования таких пакетов в сравнении с известными инструментами. Фундаментальной основой их функционирования является концептуальная модель, в рамках которой осуществляется спецификация, планирование и выполнение процессов непрерывной интеграции прикладного программного обеспечения с привязкой к конкретным предметным данным и решаемым задачам. Использование разрабатываемых средств на практике ведет к снижению числа ошибок и сбоев прикладного программного обеспечения при разработке и применении пакетов, что, в свою очередь, существенно сокращает время проведения крупномасштабных вычислительных экспериментов и повышает эффективность использования ресурсов гетерогенной распределенной вычислительной среды. Результаты практических экспериментов по применению прототипа системы непрерывной интеграции прикладного программного обеспечения показывают его высокую эффективность.

97-120 71
Аннотация

Модель Multi-Bulk Synchronous Parallel (Multi-BSP) - это модель параллельного программирования для многоядерных машин, которая расширяет классическую модель Bulk Synchronous Parallel. Multi-BSP направлена на поддержку разработки алгоритмов и оценки времени их работы. Эта модель в значительной степени опирается на правильное вычисление параметров, которые характеризуют оборудование. Конечно, использование оборудования также зависит и от особенностей задач и алгоритмов, применяемых для их решения. В этой статье представлен полуавтоматический подход к решению задач с применением параллельных алгоритмов на основе модели Multi-BSP. Во-первых, характеристики конкретного многоядерного компьютера определяются путем применения автоматической процедуры. После этого аппаратная архитектура, обнаруженная на предыдущем этапе, применяется для разработки переносимого параллельного алгоритма. Наконец, выполняется точная настройка параметров для повышения общей эффективности. Мы предлагаем тестовый набор для измерения параметров, которые характеризуют расходы на связь и синхронизацию в конкретном оборудовании. Наш подход обнаруживает иерархическую структуру многоядерной архитектуры и вычисляет параметры для каждого уровня. Вторым вкладом нашего исследования является предложение о системе поддержки Multi-BSP. Она позволяет разрабатывать алгоритмы, применяя рекурсивную методологию к иерархическому дереву, уже построенному с помощью тестового набора.

121-135 80
Аннотация

Облачные вычисления – одна из наиболее распространенных парадигм параллельных и распределенных вычислений. Они используются для поддержки огромного количества научных и бизнес-приложений. В частности, на основе облачных вычислений могут выполняться крупномасштабные научные приложения, которые организованы как потоки научных работ. Потоки научных работ являются приложениями, интенсивно использующими данные, поскольку один поток научных работ может состоять из сотен тысяч задач. Дополнительные затруднения могут вызываться сбоями при выполнении задач, ограничениями по срокам, бюджетными ограничениями и неправильным управлением задачами. Поэтому обеспечение отказоустойчивых методов с использованием ориентированного на данные планирования является важным подходом для поддержки выполнения потоков научных работ в облачных средах. В этой статье мы представляем усовершенствованный механизм планирования, ориентированного на данные, с использованием отказоустойчивой техники динамической кластеризации (EDS-DC) подходом для поддержки выполнения потоков научных работ в облачных средах. Для оценки эффективности EDS-DC, мы сравниваем его результаты с тремя хорошо известными политиками эвристического планирования: (a) MCT-DC, (b) Max-min-DC и (c) Min-min-DC. В качестве примера мы рассматриваем поток научных работ CyberShake, потому что он обладает большинством характеристик потоков научных работ, таких как интеграция, дезинтеграция, параллелизм и конвейеризация. Результаты показывают, что EDS-DC позволил сократить время цикла обработки на 10,9% по сравнению с MCT-DC, на 13,7% по сравнению с Max-min-DC и на 6,4% по сравнению с политикой планирования Min-min-DC. Аналогично, EDS-DC позволил снизить стоимость на 4% по сравнению с MCT-DC, на 5,6% по сравнению с Max-min-DC и на 1,5% по сравнению с политиками планирования Min-min-DC. При использовании EDS-DC по отношению к временным и стоимостным ограничениям не нарушается SLA, в то время как оно нарушается несколько раз при применении политик планирования MCT-DC, Max-min-DC и Min-min-DC.

137-152 96
Аннотация
В этой статье приводится обзор экологических аспектов перемещения, кормодобывания и кормления крупного рогатого скота, а также технологий датчиков, которые могут быть встроены в основанную на Интернете вещей платформу для поддержки точного животноводства. Всего были проанализированы 43 рецензированных журнальных статьи, проиндексированных Web of Science. Во-первых, были идентифицированы сенсорные технологии (например, RFID, GPS или акселерометр), используемые авторами каждой статьи. Затем документы были классифицированы в соответствии с их применимостью к экологическим исследованиям в области кормодобывания и кормления скота
153-169 96
Аннотация

Мобильные неиерархические сети (MANET) требуют особых подходов к проектированию и выбору алгоритмов передачи данных и обеспечения безопасности. Мобильность узлов и динамическая топология порождают две ключевые проблемы: сложность обеспечения конфиденциальности при передаче данных через сеть и сложность организации надежной передачи данных. В данной работе предлагается новый подход к организации передачи данных в MANET, базирующийся на многопутевой маршрутизации с разделением узлов и кодированием информации в системе остаточных классов. Распределенное кодирование позволяет использовать схемы разделения секрета, с одной стороны, для обеспечения конфиденциальности и с другой – для помехоустойчивого кодирования. В работе предлагается использовать вычислительно стойкую схему разделения секрета на основе системы остаточных классов, которая обеспечивает конфиденциальность данных и надежность их передачи и позволяет сбалансировать нагрузку в сети.

171-185 85
Аннотация
Расширение числа и ассортимента компонентов программного обеспечения в значительной степени подчеркивает необходимость защиты прав интеллектуальной собственности (IPR), затрудняемую компьютерным, для борьбы с которым требуются эффективные меры. Маркировка происхождения программного обеспечения предназначена для противодействия незаконному заимствованию права собственности на программное обеспечение путем выявления его происхождения. В этой статье предлагается новый подход к маркировке происхождения, основанный на сочетании методов интеллектуального анализа текстов и графов. Элементы кода программы и их связи с другими элементами идентифицируются на основе их особенностей (конструкций кода) и преобразуются в конструкции языка манипулирования графами. Характерные особенностейа программного обеспечения, выводимые путем исследования теоретических свойств графа (на основе коэффициента кластеризации), используются для установления сходства или различия двух программ. Предложенная методика была оценена по показателям достоверности, устойчивости, заимствования методов, обнаружения модифицированного кода и самокопирования. Результаты подтверждают эффективность предложенного подхода для противодействия незаконному заимствованию права собственности. Сравнительный анализ предложенного подхода с современными решениями показывает лучшие результаты при выявлении свойств и связей узлов программы и при использовании динамических методов анализа графов без дополнительных накладных расходов (таких как увеличение размера программы и затрат на обработку).
187-201 84
Аннотация
Операция сравнения чисел широко используется при реализации большинства современных алгоритмов. Реализация алгоритма сравнения чисел в системе остаточных классов (СОК) состоит из двух этапов. Первый этап – вычисление позиционной характеристики  модулярного числа. Второй этап – сравнение позиционных характеристик модулярных чисел в позиционной системе счисления. В статье предлагается новый эффективный алгоритм вычисления позиционной характеристики числа в СОК, основанный на использовании приближенного метода. Использование этого метода не требует дорогостоящих модульных операций, которые заменяются быстрыми битовыми операциями сдвиг вправо и взятия младших бит. Доказано, что в случае, когда динамический диапазон СОК является нечетным числом, размер операндов уменьшается на размер модуля. Если одно из оснований СОК является степенью двойки, то размер операндов меньше динамического диапазона.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)