Preview

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

Расширенный поиск
Том 27, № 6 (2015)
Скачать выпуск PDF
7-20 51
Аннотация
В статье рассматривается проблемы отладки оптимизирующих компиляторов. В качестве эффективного способа повышения надежности производимых компилятором оптимизирующих преобразований автором предлагается новый метод инструментирования кода программы на этапе компиляции. Особенностью описываемого в статье метода является то, что он предназначен в первую очередь для отладки конкретных проблемных оптимизаций, а не самих тестов, и позволяет верифицировать корректность формируемого оптимизацией кода для произвольных входных данных запускаемой задачи. Предлагаемый метод был успешно использован для поиска и выявления нерегулярно проявляющихся ошибок в программах с асинхронно работающим кодом.
21-32 134
Аннотация
JavaScript является одним из наиболее распространенных языков программирования. Однако производительность движков JavaScript не всегда удовлетворительна. Автором разработаны подходы, позволяющие повысить производительность движка V8 на 10% на основных тестовых наборах
33-48 69
Аннотация
В статье предлагаются методы, делающие возможной компиляцию программ на языке JavaScript в статически типизированное представление LLVM. В работе рассматривается многоуровневый динамический компилятор языка JavaScript V8, разработанный компанией Google. Основная цель работы - улучшение производительности программ на языке JavaScript. Для этого предлагается способ добавления в компилятор V8 нового уровня оптимизации, который использует инфраструктуру LLVM для генерации машинного кода. Это позволяет применять имеющиеся в LLVM оптимизации и технологии генерации машинного кода для разных архитектур к программам, написанным на JavaScript.
49-66 25
Аннотация
Эффективность проводимых компилятором оптимизирующих преобразований может быть значительно повышена с помощью получения и использования профильной информации об исполнении программы, такую работу компилятора называют profile guided optimization (PGO). После проведения преобразований, изменяющих граф потока управления, необходимо скорректировать профильную информацию, с целью сохранения ее актуальности для качественной работы последующих оптимизаций. В работе рассматриваются два способа представления профильной информации и переход между ними, описаны возможные причины возникновения дополнительной информации о потоке управления в оптимизируемом коде, требующей изменения профиля. Рассмотрены наиболее часто возникающие задачи проведения коррекции профильной информации и предложены следующие решения: алгоритм коррекции значений счетчиков ациклического участка по значениям счетчиков узлов выхода; алгоритм коррекции значения среднего числа итераций цикла; алгоритм коррекции профиля при обнаружении «противоречивого узла». Доказано, что разработанные алгоритмы коррекции значений счетчиков ациклического участка и числа итераций цикла позволяют минимально изменить соотношение значений счетчиков исходного графа. На их основе описан механизм коррекции профильной и тонкой профильной информации после проведения преобразования открутки итераций цикла. Все предложенные методы реализованы и используются в процессе компиляции оптимизирующими компиляторами lcc, lccs, lfortran, lfortrans для архитектур Эльбрус и Спарк.
67-86 80
Аннотация
Современные виртуальные машины для языка JavaScript используют многоуровневую компиляцию во время выполнения для создания машинного кода. При компиляции во время выполнения нецелесообразно выполнение сложных оптимизаций. Статическая компиляция, наоборот, имеет неограниченные возможности для выполнения сложных оптимизационных преобразований, но не может эффективно применяться к динамическим языкам, таким как JavaScript. В данной работе предлагается общий подход к предварительной компиляции программ на динамических языках, а также применение этого подхода для улучшения двух виртуальных машин - JavaScriptCore и V8. При реализации улучшенной виртуальной машины JavaScriptCore c использованием предварительной компиляции была учтена специфика использования JavaScript-программ в составе локально хранящихся приложений для платформы ARM. Для виртуальной машины V8 для платформы x86-64 в рамках исследования предварительная компиляция была реализована с помощью кэширования в отдельный файл одного из оптимизированных внутренних представлений.
87-96 52
Аннотация
В данной статье рассматриваются техника написания кода, с помощью которой можно сэкономить время для написания определенной программы, техника инструментирования кода на языке высокого уровня C++. Приведены примеры алгоритмов написания кода для системных программ и рассмотрены оптимизированные компиляторы, за счет которых можно сократить время компиляции и ускорить работу программы.
97-110 38
Аннотация
Проблема масштабируемости систем оптимизации времени связывания и систем статического анализа не потеряла своей актуальности в настоящее время: несмотря на рост производительности и увеличении объема памяти компьютеров, программы растут в размерах и сложности пропорционально, особенно когда дело касается таких сложных многомодульных программ, как, например, операционные системы, браузеры и другие. В статье рассматривается подход к масштабированию по памяти системы оптимизаций времени связывания на основе компиляторной инфраструктуры LLVM [1], а также предложен метод применения масштабирования системы статического анализа. Представлены результаты тестирования реализации данного подхода на тестах SPEC CPU2000[2].
111-134 136
Аннотация
В статье описывается практический подход поиска ошибок в исходном коде программ с помощью методов статического анализа. При таком подходе допускается пропуск некоторых дефектов. Целью анализа является поиск как можно большего количества дефектов при минимизации ложных срабатываний и приемлемом времени анализа. Рассмотрены различные методы статического анализа, включая анализ на основе абстрактного синтаксического дерева и анализ потока данных. Все описанные алгоритмы были реализованы в инструменте статического анализа Svace.
135-150 41
Аннотация
В работе выполнено исследование эффективности реализации программной транзакционной памяти (software transactional memory) в компиляторе GCC, предложен метод инструментации параллельных программ, использующих транзакционную память, для осуществления задач профилирования, а также предложен подход к сокращению числа ложных конфликтов, возникающих при выполнении транзакционных секций. Суть подхода заключается в варьировании параметров реализации транзакционной памяти в runtime-библиотеке компилятора GCC по результатам предварительного профилирования программы (profile-guided optimization). Предложенный метод инструментации позволяет оптимизировать динамические характеристики выполнения транзакционных секций. Эффективность подхода к сокращению числа ложных конфликтов исследована на тестовых многопоточных программах из пакета STAMP.
151-158 74
Аннотация
При статическом анализе программ важную роль играет используемое представление программного кода. В статье рассматриваются различные варианты представления программ, которые строятся на различных этапах компиляции, и детекторы программных ошибок, работающие на этих представлениях
159-168 45
Аннотация
В статье предлагается подход к интроспекции виртуальных машин с использованием двоичного интерфейса приложений. Основная цель метода - получать информацию о работе системы, имея минимальные знания об ее внутреннем устройстве. Наша система основана на эмуляторе QEMU и имеет модульное строение, единицей в котором является плагин. Существующие подходы (RTKDSM, DECAF) получают данные из операционной системы с помощью структур ядра. Эти инструменты вынуждены хранить большое количество профилей с данными, потому что все адреса и смещения в структурах меняются от версии к версии. Мы предлагаем использовать редко изменяющиеся части двоичного интерфейса приложений, такие как соглашения о вызовах и номера и параметры системных вызовов. Основная идея метода - перехватывать системные функции и считывать параметры и возвращаемые значения. Для осуществления системного вызова у процессора есть специальная инструкция. Расширив возможности QEMU механизмом инструментирования, мы имеем возможность отслеживать каждую выполняющуюся инструкцию и отфильтровывать нужную. При возникновении системного вызова мы передаем управление в детектор системных вызовов, который проверяет номер произошедшего вызова и, в соответствии с ним, принимает решение какому плагину перенаправить это задание. В механизме перехвата системных вызовов важно не только определить что вызов произошел, но и корректно определить его завершение, чтобы считать значения выходных параметров и возвращаемое значение. Для окончания системного вызова тоже есть специальные инструкции, но нам так же нужно верно сопоставить начало вызова с его концом, для чего мы определяем текущий контекст. Таким образом мы реализовали мониторинг файловых операций, процессов и создали прототип монитора API функций. Мы планируем расширить набор плагинов для анализа и мониторинга. Наша система будет извлекать информацию о загруженных модулях, приложениях, а также отладочную информацию.
169-188 78
Аннотация
Статья содержит обзор и анализ реализаций понятия наследования в современных промышленных языках программирования. Исследуются достоинства и недостатки механизмов наследования в таких языках, как С++, Java, C# и Eiffel и других, анализируются их особенности и ограничения моделей наследования, реализованных в этих языках. На основе проведенного анализа в статье предлагается альтернативный подход к трактовке наследования, который сочетает общность и гибкость множественного наследования и простоту практического применения для целей повторного использования кода. Суть предлагаемого подхода заключается в переносе контроля валидности полного графа наследования на этап обработки обращений к свойствам класса на основе анализа перекрытий (overriding) и контроля подобия (conformance) сигнатур свойств. Предложенный подход может быть реализован как дополнение к какому-либо существующему языковому инструменту, так и в виде независимой реализации.
189-198 50
Аннотация
Достижение высокой производительности на микропроцессорах с VLIW-архитектурой возможно лишь при использовании агрессивной инлайн-подстановки. Предложенный в настоящей работе алгоритм оптимизации явно учитывает время компиляции, что делает его эвристику более сбалансированной и позволяет значительно сократить рост кода и ускорить компиляцию по сравнению с известными алгоритмами. Кроме того, нам удалось достичь высоких показателей производительности благодаря ряду факторов: учёт в эвристике ключевых оптимизаций, использование клонирования функций, частичной инлайн-подстановки и компиляции в режиме «вся программа». Реализация нашего алгоритма в оптимизирующем компиляторе для архитектуры Эльбрус позволила ускорить задачи SPEC CPU2006 в среднем в 1.41 раз.
199-224 87
Аннотация
В этой статье мы обсуждаем подходы к оценке производительности многоуровневых облачных приложений и сравниваем метод, основанный на исчислении реального времени, с двумя классическими аналитическими подходами: основанным на теории очередей и основанным на теории управления. В центре внимания находятся возможности этих подходов для оценки ключевого параметра качества обслуживания - времени отклика приложения.
225-252 236
Аннотация
В статье содержится анализ различных распределенных систем хранения данных и возможных решений основных проблем этой области, в частности, проблем масштабирования систем, согласованности данных, доступности и устойчивости к разделению. Проведенный анализ позволил выявить ряд закономерностей и попытаться классифицировать системы на основе разных параметров, в частности, при наличии или отсутствии специфических функций и механизмов. Варианты выбора распределенных систем хранения данных основываются на анализе и классификации.
253-274 64
Аннотация
В настоящей работе рассматривается подход к расчёту надёжности хранилища данных, учитывающий как явные дисковые сбои, так и скрытые битовые ошибки, а также процедуры их выявления. Для расчёта надёжности предлагается новая математическая модель аналитического описания распределенного хранилища, описывающая динамику потерь и восстановления данных на основе Марковских цепей, соответствующих разным схемам избыточного кодирования. Рассматриваются преимущества разработанной модели по сравнению с классическими моделями для традиционных RAID-массивов. Исследуется влияние скрытых ошибок жестких дисков без учёта других битовых сбоев, возникающих в остальных аппаратных компонентах вычислительной машины. Оценка надёжности осуществляется согласно новым аналитическим формулам на основе критерия среднего времени до отказа, при котором утрата данных превышает порог восстанавливаемости, определяемый параметрами избыточного кодирования. Приводятся новые аналитические зависимости среднего времени жизни хранилища от среднего времени полной проверки данных в нём.
275-284 29
Аннотация
Для эффективного использования ресурсов высокопроизводительных вычислительных систем при реализации методов численного исследования физических, биологических, социальных и др. явлений могут быть использованы подходы предоставления распределенных проблемно-ориентированных вычислительных сред. Они обеспечивают пользователям прозрачный доступ к решению конкретных классов прикладных задач на базе доступных вычислительных ресурсов. Для повышения эффективности таких сред необходимо применение проблемно-ориентированных методов планирования вычислительных задач, использующих информацию о предметной области для прогнозирования вычислительных характеристик задач при планировании и распределении заданий. В статье представлены модели предметной области и проблемно-ориентированной облачной вычислительной среды, ориентированные на поддержку разработки новых проблемно-ориентированных алгоритмов планирования при выполнении расчетов в конкретных предметных областях на базе облачных вычислительных систем.
285-306 157
Аннотация
В условиях развития технологий облачных вычислений актуальной является задача разработки новых фундаментальных подходов и проработки методов прикладной реализации сервис-ориентированных облачных сред, обеспечивающих непрерывное развитие и поддержку крупномасштабных научных исследований. В статье дается краткий обзор облачных информационных технологий, рассмотрены основные модели предоставления услуг облачных вычислений. Исследованы архитектура и особенности реализации моделей облачных вычислений на основе референтной модели NIST. В работе на общесистемном уровне описаны состав, цели и функции акторов облачной вычислительной среды, ориентированных на выполнение и поддержку крупномасштабных научных исследований. Приведены схемы базовых сценариев взаимодействия акторов облачной инфраструктуры.
307-314 61
Аннотация
Данная система предназначена для автоматизированного распределения нагрузки в кластере путем анализа загруженности вычислительных узлов и последующей миграции виртуальных машин с загруженных узлов на менее загруженные. Помимо стабилизации нагрузки рассмотрена возможность снижения энергопотребления путем разгрузки слабонагруженных узлов и перевода их в ждущий режим. Стабилизация нагрузки в кластере ведет к повышению стабильности и сокращению времени выполнения запросов.
315-334 46
Аннотация
Экспоненциальный рост объемов, повышение качества данных в современных и будущих обзорах неба открывают перед астрофизиками новые горизонты, однако требуют применения новых подходов к их обработке, а именно технологий больших данных и облачных вычислений. В работе предлагается подход, основанный на модели MapReduce, для решения одной из самых масштабных и важных вычислительных задач астрофизики - задачи обработки сырых данных астрономических изображений.
335-344 57
Аннотация
Предложены теоретическое обоснование и алгоритмическая реализация спектрально-аналитического метода распознавания повторов в символьных последовательностях. Теоретическое обоснование основывается на теореме об эквивалентном представлении символьной последовательности вектором непрерывных характеристических функций. Сравнение фрагментов характеристических функций производится в стандартной метрике в евклидовом пространстве коэффициентов разложения рядов Фурье по ортогональным многочленам. Существенным свойством данного подхода является способность оценивать повторы на разных масштабах. Другим важным свойством является возможность эффективного распараллеливания по данным. При разработке алгоритмов предпочиталась схема вычислений с минимальным количеством обращений к оперативной памяти, подразумевающая повторяющиеся и отложенные вычисления. В данной парадигме разработан алгоритм вычисления коэффициентов разложения по ортогональным многочленам за счет использования рекуррентных соотношений. Показано, что алгоритм вычисления коэффициентов разложения по ортогональным многочленам может быть эффективно векторизован за счет вычислений с фиксированной длиной вектора. Распараллеливание и векторизация реализованы с использованием стандарта OpenMP и расширения Cilk Plus языка C/C++. Разработанный метод эффективно масштабируется в зависимости от параметров задачи и числа ядер процессора на системах с общей памятью.
345-354 31
Аннотация
Рассмотрены основные принципы и примеры использования облачных вычислительных сред различными научными лабораториями. Описаны работы, проводимые в Объединенном институте ядерных исследований (ОИЯИ) и направленные на развитие имеющейся облачной инфраструктуры, принятые стратегии повышения эффективности, отказоустойчивости и надежности, а также подходы к интеграции с другими ОВС.
355-380 52
Аннотация
В этой статье мы описываем энергосберегающие онлайн-расписания вычислительных задач и механизмы повышения энергоэффективности с учитом конфликтов использования ресурсов. Мы предлагаем модель оптимизации и новый подход к распределению задач, принимая во внимание типы приложений. Разнородные задачи, решаемые на процессорах, включают в себя приложения, интенсивно использующие процессоры, диски, устройства ввода-вывода, память, сети и т.д. Когда задачам одного типа назначается один и тот же ресурс, они могут создать конфликты при использовании CPU, памяти, диска или сети. Это может привести к деградации производительности системы и увеличению потребления энергии. Мы рассматриваем энергетические характеристики приложений и показываем, что умные стратегии распределения задач могут дополнительно улучшить энергопотребление по сравнению с традиционными подходами. Мы предлагаем алгоритмы консолидации разнородных задач и показываем их эффективность на реальных данных в различных сценариях, используя CloudSim для моделирования облачных вычислений. Мы анализируем несколько алгоритмов планирования в зависимости от типа и объема информации, который они используют.
381-394 143
Аннотация
В статье освещается проблематика построения и анализа систем криптографической защиты облачных вычислений на основе гомоморфного шифрования. Рассматриваются минимальные требования, которым должна удовлетворять гомоморфная криптосистема, чтобы быть пригодной для практического использования. Для этого вводится новое понятие - шифрование, стойкое к дерандомизации, а также объясняются связи этого понятия с классическими общепринятыми определениями криптостойкости, а также с защищенностью в целом облачной системы. Показываются примеры простых гомоморфных криптосистем, как удовлетворяющие требованию стойкости к дерандомизации, так и не обладающие этим свойством. В заключение делается вывод о применимости данных криптосистем в облачных вычислительных системах.
395-408 30
Аннотация
В статье обосновывается необходимость применения распределенных вычислительных систем для математического моделирования процесса образования облака зараженного воздуха при возникновении запроектных аварийных ситуаций на техногенных химико-технологических объектах. Проанализирована зависимость скорости изменения концентрации опасной примеси в произвольной точке пространства и приведены математические модели процессов образования облака зараженного воздуха при высокотемпературных выбросах (взрывах, пожарах) и проливах больших количеств токсичных химических веществ на различные поверхности с последующим их испарением. Доказана целесообразность декомпозиции задачи моделирования процесса образования облака зараженного воздуха.
409-420 55
Аннотация
В работе представлены структура и отдельные компоненты облачного сервиса, предназначенного для решения многомасштабных задач нанотехнологии на суперкомпьютерных системах. Мотивацией к созданию именно облачного сервиса была необходимость интеграции идей и знаний по данной прикладной проблеме, специалистов по решению задач данного класса на суперкомпьютерных системах, различных технологий моделирования и множества пакетов прикладных программ, а также различных вычислительных ресурсов, имеющихся у ИПМ и его партнеров. Итогом работы стал прототип облачной среды, реализованный в виде сервиса Мультилогин и прикладного программного обеспечения доступного из виртуальных машин пользователей. Первым приложением сервиса стала параллельная программа Flow_and_Particles для суперкомпьютерных расчетов многомасштабных задач газовой динамики в микроканалах сложных технических систем и визуализатор результатов расчетов Flow_and_Particles_View.
421-440 45
Аннотация
Информационно-аналитические системы поддержки решений во власти и бизнесе, как правило, носят распределенный характер. В них можно выделить два существенно отличающихся контура информационно-аналитического обеспечения. Первый основывается на поддержке процессов сбора, доставки и обработки информации, представленной в базах данных, а второй - обеспечивает собственно процессы принятия решений с анализом мнений экспертов в реальном времени. В работе предлагается проектное решение по созданию фреймворка для интеграции гетерогенных информационно-аналитических средств в облачной среде, обеспечивающее целенаправленную и устойчивую сходимость процессов принятия решений. При этом инструменты могут охватывать процессы сетевой экспертизы, когнитивного моделирования, визуализации и анализа больших данных. Приводятся примеры практической апробации отдельных компонентов.
441-450 41
Аннотация
В работе исследуются особенности синтеза безусловных проверяющих экспериментов для ненаблюдаемых автоматов. Вводится соответствующая модель неисправности, в которой автоматы-реализации перечисляются явно. Показывается, что если автомат-спецификация обладает древовидной структурой, то можно построить проверяющий эксперимент полиномиальной длины, обнаруживающий все неконформные реализации автомат. В качестве неисправностей рассматриваются (одиночные) ошибки переходов и выходов автомата-спецификации.


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


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