Preview

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

Расширенный поиск
Том 24 (2013)
Скачать выпуск PDF
110
Аннотация
В данной работе описаны основные проблемы, возникающие при переносе высокопроизводительных вычислений в облако. Рассматривается подход к организации высокопроизводительного облачного сервиса с использованием виртуализации. Описана архитектура разработанной системы «виртуальный суперкомпьютер», основанной на облачной платформе OpenStack и системе виртуализации KVM/QEMU. Компоненты системы ВСК доработаны для учета специфики высокопроизводительных вычислений, в частности, выполнена доводка и настройка системы виртуализации, что позволило достичь уровня накладных расходов не более 10% при использовании по крайней мере 1024 процессорных ядер.
65
Аннотация
Для эффективного решения высокопроизводительных задач в облаке необходимо планирование виртуальных машин на серверах, учитывающее особенности высокопроизводительных вычислений, чтобы уменьшить потери производительности, связанные с задержками в сети. В данной работе рассматривается подход к планированию, основанный на оценке размещения с помощью Hop-Byte метрики. Для конкретного варианта коммуникационной среды (сети Infiniband с топологией «толстое дерево») производится подсчет Hop-Byte метрики в предположении, что взаимодействие между виртуальными машинами одинаково. На основе полученных результатов разработан алгоритм планирования, выполнена его реализация в облачной системе OpenStack. Показано, что для отдельных тестов удается получить прирост производительности, при этом существенно снижается разброс значений при повторных запусках.
36
Аннотация
В данной статье рассматриваются шаблоны в параллельных программах, приводящие к потере производительности. Рассматриваются шаблоны как в параллельных MPI приложениях для вычислительных систем с распределенной памятью, так и в параллельных UPC программах для систем с разделенным глобальным адресным пространством (PGAS). В работе предложен метод автоматизированного обнаружения шаблонов неэффективного поведения в параллельных MPI приложениях и UPC программах. Это позволяет сократить время доводки параллельных приложений.
53
Аннотация
Для выбора оптимального в смысле вычислительной эффективности итерационного метода решения систем линейных алгебраических уравнений, возникающих при дискретизации дифференциальных уравнений в частных производных, помимо скорости сходимости следует учитывать такие характеристики системы и метода, как число обусловленности, коэффициент сглаживания, показатель «затратности». Последние две характеристики вычисляются по коэффициентам усиления гармоник, которые позволяют судить о сглаживающих свойствах итерационного метода и его «затратности», т.е. о том, насколько медленнее метод подавляет низкочастотные компоненты ошибки по сравнению с высокочастотными. Предложен способ определения коэффициентов усиления гармоник, основанный на использовании дискретного преобразования Фурье. В качестве примера приведён анализ эффективности метода BiCGStab c ILU и многосеточным предобуславливанием при решении разностных аналогов уравнений Гельмгольца и Пуассона, возникающих при моделировании течения вязкой несжимаемой жидкости в квадратной каверне
26
Аннотация
В работе представлен авторский опыт использования технологической платформы UniHUB при численном моделировании и проведении расчетов течений непрерывно стратифицированной жидкости с применением свободных прикладных вычислительных пакетов OpenFOAM, Salome и ParaView. Внимание уделяется вопросам построения высокоразрешающих расчетных сеток, постановки сложных граничных с помощью встроенных и расширенных утилит пакета OpenFOAM, разработки собственных решателей, обработки и визуализации расчетных данных, а также проведения расчетов в параллельном режиме на вычислительном кластере МСЦ РАН. Демонстрируются некоторые результаты численных расчетов - картины стратифицированных течений около непроницаемых наклонной и горизонтальной пластин, симметричного клина, горизонтального диска и кругового цилиндра. Приводятся сравнения данных аналитического, численного и лабораторного моделирования стратифицированных течений около различных препятствий, оговариваются условия согласия и расхождения результатов, обсуждаются проблемы переноса данных моделирования на природные системы.
98
Аннотация
В данной статье рассматривается передача данных по шине PCI Express с одновременным участием нескольких ПЛИС. В компьютерной системе, к PCI Express шине которой подключено несколько (в нашем случае 8) оконечных устройств (PCIe endpoints) ПЛИС запускается одновременно несколько транзакций передачи данных двух типов: А) DMA передача между ОЗУ и ПЛИС (чтение/запись) и Б) прямая передача данных между двумя ПЛИС (запись). Используя соединение PCI Express x4 Gen 2.0 при обращении в память была получена скорость записи 1451 МБ/с (90% от максимальной). Скорость записи данных между ПЛИС была равна 1603 МБ/с (99 % от максимальной) при длине пакетов 128 байт и 1740 МБ/с (99% от максимальной) при длине пакета 256 байт. Латентность передачи данных между ПЛИС зависит от количества промежуточных коммутаторов, и была равна 0,7 мкс для одного коммутатора и 1 мкс для трех. Также показано, что при одновременных передачах через общий канал скорость отдельных передач не уменьшается до тех пор, пока суммарная скорость передачи не превышает пропускную способность общего канала; затем канал используется на 100%, а его пропускная способность делится поровну между устройствами.
44
Аннотация
В статье рассматриваются методы оптимизации Си/Си++ приложений, применяемые в системе двухэтапной компиляции, позволяющей распространять такие приложения в промежуточном представлении LLVM [1]. Рассматривается методика замещения кода функций во время исполнения, реализованная в динамическом компиляторе LLVM, позволяющая осуществлять динамическую оптимизацию программ. Описывается метод статического инструментирования с неполным покрытием всех дуг потока управления программы и последующей его коррекцией для сбора профиля, позволяющий получать профиль сравнимый по качеству с классическим подходом, но при этом обеспечивающий существенное снижение накладных расходов на сбор профиля. Помимо этого описывается разработанная и реализованная методика конвертации динамически собираемого профиля, для статически скомпилированного приложения в формат, используемый LLVM для машинно-независимых оптимизаций. Описываются как существующие в LLVM оптимизации, модифицированные для использования профиля, так и предлагаются новые. Предлагается метод позволяющий использовать команды предвыборки для повышения эффективности кода обработки массивов. Описывается подход к построению специализированного облачного хранилища приложений, позволяющего решать вопросы оптимизации и защиты программ, а также обеспечивающий снижение накладных расходов на компиляцию и оптимизацию приложений в облачной инфраструктуре.
58
Аннотация
Целью работы является разработка программного обеспечения, проводящего деобфусцирующие преобразования. Основная область применения - это анализ запутанного кода вредоносного программного обеспечения. Потребность в подобного рода продуктах возникла в связи с ростом популярности методик запутывания кода для сокрытия алгоритмов работы. Основным инструментом аналитика является дизассемблер, осуществляющий преобразование бинарного кода в читаемый человеком текст, но не проводящий его верификацию и упрощение. Ранее для «чистки» запутанного кода хватало удаления бесполезного кода по шаблонам, но применяемые методики запутывания усложняются, и для распутывания требуются средства, использующие более прогрессивные методы анализа и упрощения кода. В связи со схожестью проблем, стоящих перед оптимизирующим компилятором и деобфускатором, было опробовано использование компиляторной инфраструктуры LLVM в качестве ядра деобфускатора. Основным различием является то, что оптимизатор компилятора работает в условиях полного знания о программе, в то время как деобфускатор обладает неполной информацией, извлеченной непосредственно из участка анализируемого кода. По результатам испытаний, в связи с высокой зашумленностью выходного кода, было принято решение разработать свою инфраструктуру, которая позволяет добиться более чистого выходного кода. Тем не менее, применение LLVM или аналогичной разработки остается одним из перспективных направлений при разработке деобфусцирующего программного обеспечения.
138
Аннотация
Тема статьи - вывод типов для программного кода на языке Python. Сначала производится обзор описанных в научной литературе алгоритмов вывода типов для языков с параметрическим полиморфизмом. Затем даётся описание нового алгоритма, являющегося модификацией одного из предыдущих: алгоритма декартова произведения. Показывается, как модуль вывода типов, использующий новый алгоритм, анализирует различные конструкции языка Python. Представляются результаты работы над прототипом.
51
Аннотация
В данной статье рассматривается задача автоматического поиска ошибок синхронизации при проведении динамического анализа приложений в рамках платформы Android. Приводится теоретический обзор существующих методов проведения подобного анализа, затем рассматриваются основные особенности приложений платформы Android с точки зрения применения данных методов. Приводится обзор существующих инструментов для анализа компонентов Android-приложений как в нативном кода на языке Си, так и реализованных на языке Java. Также в статье описан механизм обнаружения ошибок синхронизации, используемый инструментом динамического анализа байт-кода Coffee Machine и его основные аспекты: инструментирование, генерация трассы отношений предшествования и использование инструмента ThreadSanitizer Offline для обнаружения состояния гонок по сгенерированной трассе для платформы Android.
39
Аннотация
UniTESK - технология тестирования, основанная на формальных моделях (или спецификациях) требований к поведения программных или аппаратных компонентов. В статье описываются наиболее значимые применения технологии UniTESK в промышленных проектах, суммируется их опыт и оцениваются перспективные направления развития компонентных технологий тестирования на основе моделей.
74
Аннотация
Точность, полнота и масштабируемость применяемых на практике инструментов статической верификации значительно возросла за последнее десятилетие. В частности, успешный автоматизированный анализ программных систем среднего размера с использованием проверки моделей, получаемых при помощи предикатной абстракции, стал возможен благодаря развитию метода уточнения абстракции по контрпримерам - CEGAR (Counter Example Guided Abstraction Refinement). Этот метод так или иначе используется в таких инструментах, как SLAM, BLAST, SATABS и CPAchecker. В рамках данной статьи мы рассмотрим метод CEGAR в том виде, как он реализован в инструментах статической верификации BLAST и CPAchecker.
40
Аннотация
Одним из наиболее перспективных методов поиска ошибок в программах в настоящее время является статическая верификация. Для успешного применения существующих инструментов к ядру операционной системы Linux приходится проводить верификацию покомпонентно. При этом инструментам необходимо предоставлять модель окружения, отражающую реальное окружение компонентов достаточно точно. Разработка полной модели окружения для компонентов ядра Linux является очень трудоемкой задачей, поскольку программных интерфейсов в ядре очень много и они не являются стабильными. В статье предлагается новый подход к построению спецификаций программных интерфейсов, который позволяет достаточно эффективно применять инструменты статической верификации для проверки выполнения правил использования программных интерфейсов в условиях неполноты модели окружения.
94
Аннотация
В настоящей работе представлен process mining алгоритм, предназначеный для применения в инструментированной распределенной системе. Подразумевается, что система инструментирована таким образом, что взаимодействия между модулями системы проходят через единую шину, связывающую все компоненты системы. Записанные при обработке на шине события анализируются представленным в работе алгоритмом, результатом работы которого является модель взаимодействий между модулями системы. Полученная модель используется для разработки покрывающего регрессионного тестового набора.
116
Аннотация
В современном мире всё острее встает проблема работы с огромными объемами данных и большими нагрузками. Крупные Web-приложения, социальные сети, различные научные исследования, бизнес-аналитика, а также множество других областей, так или иначе, сталкиваются с проблемами управления и анализа данных большого объема («big data»). Кроме анализа уже накопленного объема данных, возникают задачи манипулирования данными под большой нагрузкой, характерные, например, для Web-приложений. В таких проектах большое количество пользователей одновременно читают и пишут информацию, что требует от системы управления данными не только большой пропускной способности и низких задержек, но и масштабируемости, надежности и определённых гарантий согласованности данных. Несмотря на большую популярность, опыт применения и универсальность, традиционные SQL-ориентированные СУБД зачастую не могут удовлетворить требования современных приложений, что привело к появлению большого числа специализированных распределённых систем, способных лучше справляться с возникающими задачами. В данной статье предлагается обзор некоторых современных решений, обеспечивающих масштабируемость при работе с большими объемами данных под высокими нагрузками.
51
Аннотация
В статье предлагается комбинированный подход к оценке качества научно-технических документов, учитывающий различные категории автоматически рассчитываемых характеристик качества документов - как существующие библиометрические и наукометрические характеристики (рассчитываемые на основе сведений из «цитатных» баз), так и новые типы характеристик, основанные на семантическом анализе текстов научно-технических документов, применении эвристических правил, а также на применении методов оценки наличия прямых текстовых заимствований (плагиата). На основе полученных базовых оценок формируется интегральный показатель оценки качества научно-технических документов с использованием методов машинного обучения аналогично решению задачи ранжирования в информационном поиске. Представлена разработанная экспериментальная система, основанная на предложенном подходе, а также приводятся экспериментальные исследования разработанной системы, направленные на проверку точности оценки научно-технических документов. Проведённый в статье анализ состояния исследований в РФ и за рубежом в области методов оценки качества научно-технических документов показал, что предложенный в статье подход на основе автоматического расчета базовых оценок из указанного «расширенного» набора групп никем не рассматривалась в настолько широкой постановке и в целом является новаторским.
26
Аннотация
Статья посвящена современным методам поиска и индексации многомерных данных применительно к задачам моделирования больших динамических сцен. Подобные задачи имеют разнообразные приложения в компьютерной графике и анимации, мультимедийных базах данных, системах виртуальной и дополненной реальности, системах автоматизированного проектирования и производства, робототехнике, геоинформационных системах, системах комплексной инженерии и управления проектами, однако их решение часто оказывается невозможным из-за высокой вычислительной сложности алгоритмов пространственно-временной локализации объектов сцен и требует применения специальных схем индексации многомерных данных. В статье обсуждаются два фундаментальных подхода к организации подобных схем, а также проводится их сравнительный анализ в контексте комплексных требований, предъявляемых к приложениям обсуждаемого класса.
25
Аннотация
В данной статье изложены материалы сравнения и критики SQL по поводу соответствия операторов SQL реляционной модели данных. Рассмотрены особенности табличных выражений в стандарте SQL и показаны случаи, в которых эти выражения противоречат реляционной модели. Приведены варианты использования таких табличных выражений в SQL, которые наиболее точно отражают концепции реляционной модели.
26
Аннотация
Построение системы управления для нестационарных объектов - это дальнейшее развитие подхода к управлению объектами по прецедентам, разработанного в рамках более ранних работ авторов, применительно к нестационарным объектам с неполным описанием. Подход к управлению на основе прецедентов в виде цикла из трёх составляющих (оценка состояния объекта, выработка управляющего воздействия, оценка состояния после воздействия) для нестационарного объекта потребовал существенной доработки из-за неоднозначности в оценке объекта. За время оценки и выработки адекватного управляющего воздействия состояние объекта может самопроизвольно измениться, и заранее подготовленное воздействие станет непригодным. На нынешнем этапе упор сделан на разработку методики, позволяющей снизить неоднозначность оценки объекта до и после воздействия. Источником дополнительной информации может служить предыдущее поведение объекта.
25
Аннотация
Системы поддержки принятия решений, в которых результаты вывода по правилам дополняют результаты рассуждений по прецедентам - очередной шаг вперед по сравнению с моделями, поддерживавшими только одну из парадигм знаний. В существующих на данный момент гибридных системах основным инструментом вывода являются порождающие правила, а прецеденты используются лишь для обработки исключений. В описываемом подходе к поддержке решений для второй очереди исследовательской системы ИСП РАН и созданной на ее основе системе поддержки врачебных решений «Спутник Врача», рассуждения по правилам и прецедентам дополняют друг друга в условиях неоднозначной оценки неполностью описанного случая. Отсутствие существенного признака для одного из правил зачастую делает непригодным применение самих порождающих правил. На текущем этапе проекта разработана методика двухэтапной оценки случая, где сначала используется прецедентный подход с целью получить представление о возможной принадлежности случая тому или иному классу (так называемый дифференциальный ряд состояний случая). На основе этой информации, на втором этапе, уже по правилам вывода проводится обратный логический вывод от возможного заключения, как гипотезы, - к фактам, подтверждающим эту гипотезу. Это снижает затраты на поиск недостающих признаков и существенно ограничивает перебор ветвей при движении по цепи правил.
23
Аннотация
В 1993 году Коффман и Шор предложили онлайновый алгоритм упаковки прямоугольников в полосу с оценкой O(n^{2/3}) для математического ожидания незаполненной площади полосы в стандартной вероятностной модели. С тех пор вопрос о возможности улучшения этой оценки в классе онлайновых алгоритмов оставался открытым. В данной работе проанализирован принципиально новый онлайновый алгоритм упаковки, предложенный ранее автором. Для него доказана оценка O(n^{1/2} (\log n)^{3/2}) для математического ожидания незаполненной площади полосы


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


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