Preview

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

Расширенный поиск
Том 28, № 1 (2016)
Скачать выпуск PDF
5-20 29
Аннотация
Язык JavaScript является одним из самых популярных языков для разработки веб-приложений. В связи с ростом производительности персональных компьютеров, мобильных и встраиваемых систем использование JavaScript стало возможным также и в масштабных приложениях. Более того, в настоящее время язык JavaScript активно используется в операционных системах в качестве одного из основных языков для создания пользовательских приложений. Примерами таких систем являются Tizen OS и Firefox OS. С ростом популярности языка многие крупные компании выпустили свои реализации JavaScript, в которых для генерации машинного кода в основном используется многоуровневая динамическая компиляция. В данной работе описываются разработанные методы оптимизации динамических многоуровневых компиляторов с учетом информации о профиле выполнения программы. Метод был реализован в динамическом компиляторе языка JavaScript V8, разработанном компанией Google. Использование профиля выполнения программы позволяет оптимизировать программу для конкретных входных данных. Это особенно актуально в связи с использованием JavaScript в операционных системах. Сценарий использования оптимизации на основе профиля программы в операционных системах следующий: на этапе тестирования программного обеспечения можно организовать сбор информации о профиле программы и использовать его для оптимизации приложений под конкретные случаи выполнения. Одним из новых применений использования информации о профиле программы может быть обеспечение немедленного переключения выполнения часто исполняющихся участков кода на уровень оптимизирующего компилятора. Другое применение - удаление обратных переходов на неоптимизирующие уровни выполнения.
21-40 37
Аннотация
В работе рассмотрены различные аспекты статического анализа программ на языке C# с целью обнаружения максимального количества ошибок за минимально приемлемое время. Описан полный цикл статического анализа программного обеспечения, при этом основное внимание уделяется особенностям, возникающим при анализе языка C#. Рассмотрены методы, позволяющие учитывать популярные возможности языка на всех уровнях анализа: построение графа вызовов и графа потока управления, проведение анализа потоков данных и чувствительного к контексту и путям межпроцедурного анализа. Предлагается метод символьного исполнения, основанный на таких работах, как Bounded Model Checking и Saturn Software Analysis Project. В статье описана организация модели памяти, позволяющая как проводить точный внутрипроцедурный анализ, так и создавать компактные представления для привязанных к функциям условий, используемые при межпроцедурном анализе. Особое внимание уделяется теме оптимизации возникающих на этапе чувствительного к путям анализа условий. Условия необходимо оптимизировать как по размеру, поскольку при межпроцедурном чувствительном к путям анализе необходимо сохранять большое количество условий для каждой проанализированной функции, так и по сложности, поскольку время анализа ограничено. Решение условий производится при помощи современных SMT-решателей, таких как Microsoft Z3 Prover. В статье также рассмотрены различные подходы к моделированию поведения библиотечных функций: при помощи резюме в виде набора признаком или в виде упрощенных реализаций на языке C#. Все приведённые решения реализованы в инструменте статического анализа SharpChecker и протестированы на наборе проектов различного объема (от 1.5 тыс. до 1.35 млн. строк кода) с открытым исходным кодом.
41-62 37
Аннотация
Описывается методика, позволяющая реализовать поиск дефектов достаточно общего и произвольного вида при использовании межпроцедурного анализа методом резюме при анализе исходного кода программы на высокоуровневых языках программирования, таких как C и C++. Основное внимание уделено трудностям, возникающим при построении и применении резюме в процессе анализа исходного кода (по сравнению с анализом низкоуровневого представления программы), а также достижению гибкости метода анализа, необходимой для поиска дефектов произвольного вида.
63-80 21
Аннотация
В статье рассматривается подход к оптимизации вызовов внешних функций в позиционно-независимом коде, основанный на выдаче вызовов непосредственно через глобальную таблицу смещений (GOT), минуя таблицу компоновки процедур (PLT). Стандартные механизмы кодогенерации на операционной системе Linux предполагают создание PLT не только для основного модуля (который является позиционно-зависимым и полагается на механизм PLT для вызовов внешних процедур), но и для динамических библиотек, где PLT используется также для организации ленивого связывания; однако использование PLT требует дополнительной инструкции перехода, может иметь низкую локальность по кешу и на некоторых архитектурах накладывает дополнительные ограничения на работу компилятора в месте вызова. Реализация вызовов внешних функций в виде косвенных переходов на адреса, загруженные непосредственно из GOT в месте вызова, позволяет избежать недостатков вызовов через PLT ценой отказа от возможности ленивого связывания и, возможно, увеличения размера кода. Была исследована реализация этой оптимизации для архитектур x86 и ARM в компиляторе GCC. Было обнаружено, что на архитектуре ARM отсутствуют типы релокаций, которые позволили бы генерировать оптимальный код для загрузок из GOT. Для решения этой проблемы в GCC и Binutils (в ассемблере и компоновщике) были реализованы недостающие типы релокаций, позволяющие построить адрес позиции в GOT относительно счетчика команд, используя инструкции movt, movw. Проведенное тестирование свидетельствует, что предложенная оптимизация позволяет получить увеличение производительности, несмотря на увеличение размеров динамических библиотек.
81-92 12
Аннотация
Методы подпространства Крылова, такие как метод сопряжённых градиентов и стабилизированный метод бисопряжённых градиентов, давно используются для решения симметричных и несимметричных систем линейных алгебраических уравнений. Это находит широкое применение при численном решении дифференциальных уравнений, которые возникают, например, в задачах вычислительной физики. Однако при увеличении размеров расчетной сетки и, соответственно, количества вычислительных процессов значительную часть времени работы могут занимать коммуникации, во время которых расчёты простаивают. Это происходит из-за того, что в оригинальных формулировках методов результат скалярного произведения, которое требует редукции, требуется уже на следующем шаге метода, что приводит к барьерной синхронизации всех потоков. При значительном количестве итераций это может привести к деградации производительности. В статье рассматривается использование альтернативных формулировок методов подпространства Крылова, позволяющих перекрыть часть вычислений и параллельных коммуникаций, часто за счет увеличения объема вычислений. Нами предложены собственные реализации этих подходов для использования гибридного решателя с графическими ускорителями, использующими технологию CUDA, в рамках программного пакета OpenFOAM, а также описаны особенности их переноса на акселераторы. Для дальнейшей оптимизации используются асинхронные коллективные операции, предоставленные стандартом межпроцессного взаимодействия MPI-3, которые позволяют избавиться от барьерной синхронизации и снизить латентность операций обмена. Представлены результаты тестирования нашего подхода на одной из станадартных задач пакета OpenFOAM с расчётными сетками в 2 и 4 миллиона ячеек c использованием нескольких графических ускорителей.
93-102 17
Аннотация
В данной статье рассматривается задача максимального увеличения пропускной способности сетевого стека при взаимодействии с аппаратно-программным ядром для обеспечения стабильности работы физического сервера. Разработаны алгоритмы и программные коды для оптимизации распределения нагрузки на центральные процессоры методом параллелизации ядра. Также рассмотрены статистические данные повышающейся мощности распределенных атак, влияющих на сетевую инфраструктуру. Показано влияние приложений, имеющих выход во внешнюю глобальную сеть, на производственную часть физического сервера, представляемую в виде физических ресурсов. С помощью разработанного и реализованного алгоритма (на языке « BASH »), произведено распределение нагрузочной способности по физическим ядрам сервера с целью дальнейшего снижения нагрузочной способности на вычислительную мощность центрального процессора. Продемонстрированы блок-схемы алгоритмов, а также итоговые результаты тестирования каждого этапа разработки. Реализована оптимизация сетевого режима « AF_PACKET », благодаря которой появилась возможность принимать внешние сетевые пакеты без каких-либо блокировок, что, в свою очередь, повышает эффективность достижения заданной цели (при запросе от сервера к клиенту). Анализируется возможность принимать до десяти миллионов входящих сетевых пакетов с помощью программных средств физического сервера, что позволяет обеспечить стабильную обработку информации для бесперебойной работы при DDoS -атаках « SYN -флуда», у которых реализована возможность перегрузки многомиллионными сетевыми пакетами. Подобное количество входящих сетевых пакетов может привести к заполнению внешнего сетевого канала с последующим повышением нагрузочной способности сетевого TCP/IP стека, что перекрывает возможность зоны удаленного управления физическим сервером в кратчайшие сроки, а также нарушает работоспособность рабочей среды.
103-130 10
Аннотация
Статья посвящена проблеме тестирования составных систем, компоненты которых моделируются конечными автоматами, а взаимодействие между ними - обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершины которого соответствуют автоматам компонентов, а дуги - каналам связи. Предполагается выполненной следующая гипотеза о связях: граф связей статический, а отображаемая им структура связей не содержит ошибок. Автомат, находящийся в вершине графа, в каждом состоянии может принимать несколько сообщений по входным дугам (не более одного по каждой дуге) и посылать несколько сообщений по выходным дугам (не более одного по каждой дуге). Целью тестирования является покрытие переходов автоматов компонентов, которые достижимы при работе этих автоматов в системе. Предполагается, что при тестировании возможно наблюдение изменения состояний автоматов в вершинах графа и сообщений на дугах графа. Сначала рассматривается упрощённая модель системы, в которой циркулирует только одно сообщение. На её примере показывается, что гипотеза о связях позволяет существенно сократить время тестирования. Полное тестирование системы автоматов без учёта гипотезы о связях может потребовать число тестовых воздействий порядка произведения чисел состояний автоматов компонентов, а с учётом гипотезы о связях - порядка суммы этих чисел. При равном числе состояний всех автоматов это даёт экспоненциальное уменьшение числа тестовых воздействий. Затем рассматривается более общая модель, когда в системе может быть одновременно много сообщений, но не более одного на каждой дуге. Определяется композиция автоматов системы и показывается, при каких ограничениях на автоматы их композиция детерминирована. Для детерминированной композиции предлагается алгоритм генерации тестов, основанный на фильтрации тестов, генерируемых для покрытия всех переходов композиции. Тест отбрасывается, если он покрывает только такие переходы в компонентах системы, которые покрываются остающимися тестами. В заключение определяются направления дальнейших исследований.
131-150 10
Аннотация
Статья посвящена проблеме моделирования и композиции составных систем. Компоненты системы моделируются конечными автоматами с несколькими входами и выходами, а взаимодействие между ними - обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершина которого соответствует автомату компонента, а дуга - каналу связи, соединяющему выход одного автомата со входом другого автомата. Автомат в вершине графа в каждом состоянии может принимать несколько сообщений по своим входам (не более одного по каждому входу) и посылать несколько сообщений по своим выходам (не более одного по каждому выходу). Входы (выходы) автоматов, которые не соединяются с выходами (входами) автоматов, являются внешними, через них осуществляется связь системы с её окружением. Автоматы системы работают синхронно: на каждом такте каждый автомат выполняет один переход. Переход автомата, предъявляя требования к состоянию всех входов и выходов автомата (указываются сообщения на них), отдельно указывает ту часть входов и выходов, по которым сообщения соответственно принимаются и посылаются, соответственно. Синхронность взаимодействия автоматов означает, что для каждого соединения требования автоматов, связанных этим соединением, должны быть согласованы. Это даёт возможность описывать более широкий спектр поведений автомата. Например, приоритетный приём сообщений: если на входах автомата имеется несколько сообщений, автомат может принять сообщения с наивысшим приоритетом, не принимая остальные сообщения. Также это позволяет автомату выполнять приём сообщений независимо от того, удаётся или не удаётся одновременно послать некоторое сообщение на некоторый выход. Определяется композиция автоматов системы по графу связей и доказывается её ассоциативность. В заключение определяются направления дальнейших исследований.
151-184 10
Аннотация
Статья посвящена проблеме тестирования составных систем, компоненты которых моделируются конечными автоматами с несколькими входами и выходами, а взаимодействие между ними - обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершина которого соответствует автомату компонента, а дуга - каналу связи, соединяющему выход одного автомата со входом другого автомата. Предполагается выполненной следующая гипотеза о связях: граф связей статический, а отображаемая им структура связей не содержит ошибок. Автомат, находящийся в вершине графа, в каждом состоянии может принимать несколько сообщений по своим входам (не более одного по каждому входу) и посылать несколько сообщений по своим выходам (не более одного по каждому выходу). Определяется ассоциативная композиция автоматов системы. Показывается, при каких ограничениях на автоматы и граф связей их композиция, т.е. сама система, детерминирована. Целью тестирования является покрытие переходов автоматов компонентов, которые достижимы при работе этих автоматов в системе. Предполагается, что при тестировании возможно наблюдение изменения состояний автоматов системы и передаваемых между ними сообщений. Полное тестирование системы автоматов без учёта гипотезы о связях может потребовать число тестовых воздействий порядка произведения чисел состояний автоматов компонентов, а с учётом гипотезы о связях - порядка суммы этих чисел. При равном числе состояний всех автоматов это даёт экспоненциальное уменьшение числа тестовых воздействий. При условии выполнения гипотезы о связях для детерминированной системы предлагается алгоритм генерации тестов, основанный на фильтрации тестов, генерируемых для покрытия всех переходов композиции. Тест отбрасывается, если он покрывает только такие переходы в компонентах системы, которые покрываются остающимися тестами. В заключение определяются направления дальнейших исследований.
185-196 16
Аннотация
Работа посвящена построению модели и численному исследованию течения в прямоугольном канале с неглубокими лунками. Математическое моделирование выполняется на базе дифференциальных уравнений движения, энергии и состояния. Численное решение получено с использованием метода конечных объемов на базе программного пакета с открытым программным кодом Code Saturne. Построение сетки, учитывающей особенности течения вблизи лунок, выполнено в программном пакете Salome со свободной лицензией. В работе рассмотрены вопросы создания сетки, показана зависимость получаемого решения от размерности сетки, проведен анализ влияния типа сетки на время ее генерирования и качество получаемого численного решения для течения в прямоугольном канале с неглубокими лунками.
197-206 29
Аннотация
МГД управление сверхзвуковым потоком является важной проблемой в современных аэрокосмических исследованиях. На основе центральных разностных схем Балбаса и Тадмора был разработан OpenFOAM-солвер, способный решать задачи моделирования сверхзвукового МГД потока. С его помощью была решена задача обтекания твердого тела в форме сферически затупленного конуса. Получаемое решения оказывается устойчивым для потоков с числом Стюарта не более 0.2. В дальнейшем планируется улучшение устойчивости солвера и совершенствование математической модели.
207-220 18
Аннотация
Представлены результаты численного моделирования течений непрерывно стратифицированной жидкости, которые характеризуются широким диапазоном значений внутренних масштабов, отсутствующих в однородной жидкости. Поставленная задача решалась с использованием метода конечных объемов в открытом пакете OpenFOAM. Тестирование разработанной модели проводилось для течений непрерывно стратифицированных жидкостей около неподвижного и движущегося клиновидного тела с прямыми и искривленными гранями. Расчеты, проведенные с использованием вычислительных ресурсов web-лаборатории UniHUB, показали сложную структуру течений, включающую высокоградиентные прослойки около неподвижного препятствия и присоединенные внутренние волны вблизи острых кромок движущегося препятствия.
221-242 8
Аннотация
Метод погруженных границ LS-STAG и его модификации для решения сопряженных задач гидроупругости c использованием моделей турбулентности Смагоринского, Спаларта - Аллмараса, , и SST в рамках RANS, LES и DES подходов к моделированию турбулентности реализованы в программном комплексе «LS-STAG_turb» для моделирования движения профилей в потоке вязкой несжимаемой среды. Комплекс позволяет моделировать обтекание движущихся профилей произвольной формы и систем из любого числа профилей, имеющих одну или две степени свободы, например, авторотацию роторов ветроэнергетических установок, ветровой резонанс систем профилей. Для сокращения затрат машинного времени на проведение расчетов разработана параллельная версия алгоритмов и проведена оптимизация участков последовательного кода. Использованы такие технологии параллельного программирования, как Intel® Cilk™ Plus, Intel® Threading Building Blocks и OpenMP.
243-258 17
Аннотация
Задачи течения вязкой несжимаемой жидкости со свободной поверхностью представляют собой отдельный класс задач механики сплошной среды и имеют большую практическую значимость. При моделировании таких процессов исследователь сталкивается с достаточно большим числом особенностей и ограничений, критически важных для получения корректного решения. Целью данной работы является обзор существующих численных методов, которые можно применить к решению задач течения жидкости со свободной поверхностью, и программных комплексов с открытым исходным кодом, в которых эти методы реализованы, а также выявление границ применимости рассмотренных программных комплексов. Были рассмотрены несколько численных методов (Volume of Fluid, Smoothed Particle Hydrodynamics, Particle Finite Element Method v.2), реализованные в пяти разных пакетах программ с открытым исходным кодом: OpenFOAM, Gerris, pySPH, DualSPHysics, Kratos. В качестве тестовых задач были выбраны следующие примеры: обрушение колонны жидкости и падение капли в слой жидкости. Решения, полученные в выбранных пакетах, были сопоставлены с известными результатами экспериментов. Проводилось сравнение времени, затраченного на решение задач в различных пакетах. Наилучшие результаты для выбранных тестов показали пакеты OpenFOAM и Gerris: в них содержатся необходимые для решения задач инструменты - возможность расчета задач в двумерной, трехмерной либо осесимметричной постановке, а также корректный учет поверхностного натяжения жидкости. При этом пакет Gerris дает существенное ускорение решения "крупных" задач за счет использования динамически перестраиваемых сеток. Пакет DualSPHysics направлен на решение задач прибрежной инфраструктуры, где рассматривают, как правило, трехмерные задачи и нет необходимости учета поверхностного натяжения. Пакет pySPH разрабатывался с целью наглядной демонстрации работы численного метода SPH, поэтому исходный код записан на языке Python без оптимизации. Пакет Kratos, в частности, модуль PFEM-2, в настоящий момент находится в разработке, поэтому некоторые возможности в нем еще не реализованы.
259-274 13
Аннотация
Основная вычислительная сложность при использовании вихревых методов сосредоточена в вычислении конвективных и диффузионных скоростей всех вихревых элементов. Рассматривается один из эффективных способов ускорения вычислений в методе вихревых элементов - алгоритм типа Барнса - Хата. Метод основан на построении иерархической структуры областей (дерева). При вычислении конвективных скоростей вихревых элементов данный метод позволяет учитывать взаимное влияние вихревых элементов, находящихся далеко друг от друга, приближенно по формуле, полученной с помощью разложения выражения для конвективной скорости в ряд Тейлора. Влияние вихревых элементов, находящихся в ближней зоне, рассчитывается напрямую по закону Био - Савара. При реализации данного алгоритма возникают параметры, влияющие на вычислительную трудоемкость и точность решения задачи: - количество уровней дерева и - параметр дальности ячеек. Влияние вихревых элементов на диффузионные скорости друг друга экспоненциально затухает с увеличением расстояния между ними. Поэтому для вычисления диффузионных скоростей также построен алгоритм, позволяющий с помощью использования структуры дерева находить вихревые элементы, находящиеся в ближней зоне и вычислять влияние только от них. На основе решения модельных задач получены оценки вычислительной сложности алгоритмов вычисления конвективных и диффузионных скоростей, которые зависят от параметров алгоритма и количества вихревых элементов. Также получены оценки погрешности вычисления конвективных и диффузионных скоростей в зависимости от параметров алгоритма. На практике эти оценки позволяют выбирать оптимальные значения параметров алгоритма и добиваться максимального ускорения вычислений при заданном уровне допустимой погрешности расчета.
275-282 9
Аннотация
Проведено прямое численное моделирование распространения внутренних волн и образования волновых аттракторов в трапецеидальном контейнере, заполненном устойчиво стратифицированным раствором соли с постоянной частотой плавучести. Левая вертикальная стенка контейнера совершает монохроматические колебания в форме половины косинусоиды на высоту контейнера, правая стенка расположена под углом к вертикали и обеспечивает фокусировку внутренних волн, две другие границы горизонтальны. На верхней границе задано условие отсутствия касательных напряжений, на остальных условие прилипания. Рассчитываются уравнения Навье-Стокса в приближении Буссинеска в трёхмерной и двумерной постановке. Прямое численное моделирование проведено с помощью метода спектральных элементов 8-го порядка и модифицированного кода nek5000. С помощью применения преобразований Гильберта и частотно-временных диаграмм к результатам численного моделирования аттракторов внутренних волн удалось получить временные и пространственные волновые характеристики, в частности волновые векторы, соответствующие временным частотам, полученным с помощью частотно-временных диаграмм. При этом используется преобразование Гильберта с фильтрацией по узкому диапазону частот. Частотно временные диаграммы для режимов со слабой надкритичностью показывают возникновение дочерних волн на частотах, соответствующих триадному волновому резонансу. Выполнение триадного резонанса для дочерних частот демонстрируется с помощью биспектров, на которых произведение амплитуд показано на декартовом произведении частотных диапазонов. После фильтрации пространственных полей горизонтальной компоненты скорости по полученным частотам получены соответствующие волновые векторы, также удовлетворяющие условиям триадного резонанса волновых векторов. Результаты хорошо соответствуют данным экспериментов, проводимых в ENS de Lyon.


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


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