В данной работе предлагается способ автоматической генерации кода для стандарта OpenCL из гнезд циклов без зависимостей по данным между итерациями для программ на языках Си, Си++ и Фортран. Для генерации используется инфраструктура GRAPHITE компилятора GCC, использующая полиэдральную модель для анализа пространства итераций и пространства данных цикла. Описывается выполненная реализация и проведенные эксперименты, показывающие наилучшие результаты на вычислительных программах, основную часть которых составляют гнезда циклов.

Статический анализ является популярным средством поиска в исходном или двоичном коде программ определенных шаблонов или ситуаций (ошибок стиля кодирования, нарушений проектных соглашений об использовании определенных библиотек или свойств языка программирования, критических ошибок, уязвимостей, закладок). В данной статье предлагается обзор инструмента статического анализа исходного кода программ на языках Си/Си++, разработанного в ИСП РАН для поиска критических ошибок и уязвимостей. Применение межпроцедурного анализа потока данных, не гарантирующего нахождение всех заданных ситуаций, позволяет проводить автоматический анализ с долей истинных предупреждений в 40-80%, что находится на уровне лучших коммерческих инструментов статического анализа.

В ИСП РАН разрабатывается инструмент статического анализа Svace для поиска ошибок в исходном коде программ на языках Си и Си++. Цель Svace - найти как можно больше ошибок при низком количестве ложных срабатываний и разумном использовании имеющихся ресурсов. Важными требованиями, предъявляемыми к системам статического анализа являются масштабируемость и расширяемость. В статье описывается встроенный механизм, поддерживающий включение в систему Svace детекторов новых видов ошибок, сохраняющий ее масштабируемость. Использование механизма иллюстрируется на примере четырёх разработанных детекторов ошибок.

В данной статье рассматривается модификация и применение инструмента Avalanche для проведения динамического анализа и тестирования приложений, получающих входные данные через сокеты. Вводится концепция замены получаемых данных, описывается реализация этой концепции при помощи средств Valgrind. Разбирается перехват и обработка системных вызовов, используемых при работе с сокетами. Рассматривается применение модифицированной версии инструмента для анализа сетевых приложений c открытым исходным кодом, перечисляются обнаруженные во время анализа дефекты.

При построении системы компиляции для языков общего назначения, учитывающей специфические особенности целевой аппаратуры и наиболее вероятный сценарий использования, необходимо применять методы динамической и адаптивной оптимизации. Исследование таких методов удобно проводить в компиляторной инфраструктуре LLVM. Тем не менее, в настоящий момент LLVM не поддерживает динамический сбор профиля и перекомпиляцию, а также содержит лишь одно преобразование, использующее данные профиля. В рамках данной работы, для LLVM была предложена и реализована система сбора профиля аппаратных прерываний и алгоритм, корректирующий переоценку профиля, а также несколько оптимизирующих преобразований с учетом профиля. Выполнена интеграция сбора профиля и динамического компилятора LLVM, что позволило сохранять качество программ при их переносе на другую архитектуру.

В работе рассматриваются методы оценки времени выполнения модели параллельной программы на инструментальном компьютере, которые позволяют достаточно точного предсказывать время реального выполнения параллельной программы на заданном параллельном вычислительном комплексе. Модель разработана для параллельных SPMD программ с явным обменом сообщениями, написанных на языке Java с обращениями к библиотеке MPI, и включена в состав среды ParJava. В модели выделяются определенные виды циклов (однородные, редуцируемые) и производится их оценка на узле целевой вычислительной системы (высокопроизводительного кластера). Это позволяет не только уменьшить погрешность предсказания, но и ускорить время интерпретации модели на инструментальном компьютере.

Условное выполнение - аппаратная возможность, реализованная в некоторых процессорах, позволяющая аннотировать команды условным предикатом, при этом команда исполняется только в случае истинности предиката. В данной работе предлагается метод для поддержки условного выполнения во время планирования команд, а также рассматриваются преимущества данного подхода по сравнению с отдельной оптимизацией, работающей до планирования команд. Предложенный метод был реализован в селективном планировщике в компиляторе GCC. Тестирование реализации показало рост производительности на тестах SPECFP набора SPEC CPU2000 в среднем почти на 2% (и до 16% на отдельных тестах).

В работе описывается метод восстановления локальных переменных из трассы исполнения программы. Метод использует одну из схем анализа потоков данных - достигающие определения. В ней также рассматриваются существующие подходы к решению задачи восстановления переменных

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

В настоящее время все больше растет интерес к использованию платформ виртуализации (VMWare, XEN и др.) в различных сферах, включая консолидацию серверов, организацию хостинга и облачные вычисления. Производительность приложения в виртуальной машине может очень сильно отличаться от производительности вне виртуализованного окружения из-за взаимодействий с гипервизором и другими виртуальными машинами. В этой статье описывается обобщенный подход к оценке требуемых программному обеспечению ресурсов при переносе его в виртуализованное окружение. Основной принцип предложенного подхода заключается в представлении сложной нагрузки в виде комбинации простых задач и замены этих простых задач на синтетические атомарные тесты. Оценка производительности атомарных тестов в среде виртуализации и вне нее позволяет определить накладные расходы на виртуализацию

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

Вводятся основные понятия и свойства рисков комплексов программ. Рассматриваются факторы и виды рисков комплексов программ и систем. Обсуждается подготовка исходных данных для анализа, прогнозирования и сокращения рисков комплексов программ. Описываются выделение, идентификация, анализ угроз и рисков в комплексах программ. Рассматриваются методы сокращения и ликвидации опасных рисков, регистрации и утверждения допустимого интегрального риска программного продукта.

В операторах ограничения предлагается логические выражения интерпретировать как реляционные. Точнее, считается, что операция реляционного ограничения (R WHERE b) над отношением R по некоторому логическому выражению b может быть представлена как соединение (RB) заданного отношения R с реляционным выражением B, полученным из исходного логического выражения b заменой логических операторов AND, OR и NOT на соответствующие реляционные операторы , и . Тогда для некоторого кортежа T определим значение атрибута A как отношение с одним кортежем и одним значением интересующего нас атрибута - RELATION{{a}}. Значение атрибута, указанное как NULL, в качестве значение «неизвестно», определим как отношение с заголовком из интересующего нас атрибута и телом, содержащим всевозможные значения типа атрибута A - RELATION{…}. Сравнение значений атрибутов на равенство будет выглядеть как соединение таких значений атрибутов, представленных отношениями. Кортеж T, который может быть определен как декартовое произведение всех своих атрибутов, будет теперь представлять отношение R_T. Истинность такого кортежа T, представленного отношением R_T, по заданному логическому выражению b, означает истинность квантора всеобщности над значениями R_T по выражению b, что в свою очередь означает равенство соединения (R_T B)и R_T - (R_T B)= R_T.

Объектно-ориентированные СУБД - одно из наиболее перспективных направлений развития современной теории баз данных, наряду с дедуктивными и темпоральными СУБД. Тем не менее, серьёзным препятствием к построению теоретических основ ООСУБД и внедрению действующих ООСУБД является большая разрозненность подходов и отсутствие единого стандарта как в области теории (исчисление объектов, концепции моделей данных), так и в области практики (язык запросов, API для ОО-языков…). Целью данной статьи является анализ существующих на сегодняшний день концепций формального устройства объектно-ориентированных СУБД, начиная с моделей данных и далее переходя к формальным математическим моделям (исчислениям объектов, формализациям объектных языков запросов). В завершение делается заключение о наиболее актуальных проблемах моделирования ООСУБД.

Уровень изоляции Snapshot Isolation (SI) широко используется в коммерческих системах баз данных. Мы разработали простой прокол реализации SI для распределенных СУБД и реализовали его в Apache HBase, распределенном хранилище данных с открытым исходным кодом. В данной работе представлена оценка его производительности в OLAP задачах в распределенном кластере HBase. Для валидации модели были использованы результаты измерений на одно-серверной конфигурации.

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

Большие объемы данных, которые могут быть кластеризованы, хранятся в реляционных базах данных. Алгоритм кластеризации, реализованный на языке SQL, обеспечивает более легкий процесс кластеризации, по сравнению с использованием внешних утилит. В данной статье предложена реализация алгоритма Fuzzy c-Means, адаптированного для реляционной СУБД с открытым исходным кодом PostgreSQL.

Поисковый спам считается одной из основных угроз современным поисковым системам. Спамеры используют разнообразные методы порождения текстов, известные как текстовый спам, чтобы наполнить выдачу поисковых систем низкокачественными страницами. Методы борьбы с текстовым спамом должны основываться на большом количестве текстовых характеристик. В данной статье предлагается набор характеристик текстового разнообразия, основанных на ранговых распределениях для слов и тематик. Предложенные характеристики объединяются с другими факторами, в результате чего получается классификатор поискового спама, превосходящий известные аналоги.

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

Поиск взаимосвязей между словами в тестке и статьями “Википедии”- чрезвычайно популярная задача, известная как викификация. Не смотря на её популярность, до сих пор не существует общепризнанного тестового корпуса для сравнения викификаторов. В данной статье представлен онлайн-инструмент для совместной работы над универсальной коллекцией тестов для двух наиболее сложных задач в викификации – разрешения лексической многозначности и выделения ключевых слов.

В то время как многие исследователи пытаются построить различные онтологии с помощью Википедии, возможность получения качественных предметно-ориентированных подмножеств словаря Википедии остаётся недооценённой. Мы демонстрируем необходимость подобной процедуры и предлагаем соответствующую методику. В результате размер базы знаний нашего фреймворка для обработки текстов уменьшился более чем на порядок, а точность дизамбигуации метаданных музыкальных файлов (ID3-тегов) уменьшилась с 98% до 64%.

В статье описывается разработка информационных систем, которые хранят слабоструктурированные данные и используют эвристические методы для формирования гипотез относительно возможной структуры хранимых данных. Предполагается, что такие системы будут удобны в использовании, так как формализация данных будет производится путем ответов на простые вопросы.

Данная работа посвящена архитектуре и проектированию параллельной системы управления базами данных PargreSQL для многопроцессорных вычислительных систем с распределенной памятью. PargreSQL основана на СУБД с открытым исходным кодом PostgreSQL и использует фрагментный параллелизм.