WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 36 |
Статья Д.Н. Волкова “Вопросы организации распределенного хранения Предисловие данных в системах обработки изображений” содержит анализ методов организации хранения данных в современных фотограмметрических системах.

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

получены в 2002-2003 гг. В статьях обсуждаются как теоретические вопросы, В статье Л.Г. Новака и С.Д. Кузнецова “Свойства схем данных XML” так и аспекты организации прикладных систем.

изучаются свойства XML-схем и методов преобразования схем над моделью В статье И.Б. Бурдонова, А.С. Косачева и В.В. Кулямина “Асинхронные данных XML. Предлагается методика, позволяющая упростить алгоритмы автоматы: классификация и тестирование” предлагается теория конечных управления данными и метаданными XML за счет выделения простых автоматов, которые отличаются от классических автоматов Мили тем, что подклассов из множества XML-схем.

смена состояния автомата происходит либо при приеме входного символа, Статья Д.Р. Ширяева “Автоматическая генерация графических либо при выдаче выходного символа, причем выбор перехода всегда пользовательских интерфейсов доступа к интегрированным данным на основе недетерминирован. Вводится понятие асинхронного автомата, в котором диаграмм классов UML” посвящена описанию выработанной автором допускается смена состояния при отсутствии входного символа. Предлагается технологии автоматического построения графических пользовательских классификация асинхронных автоматов, основанная на реализуемой автоматом интерфейсов к системе интеграции данных на основе представления словарной функции и эквивалентности автоматов с совпадающей словарной глобальной схемы в виде диаграммы классов UML. Используя одно и то же функцией.

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

программы по ее объектному коду – маскировке (obfuscation) программ.

Следует отметить, что многие из работ, представленных в сборнике, Предлагаемый метод маскировки основан, главным образом, на поддерживались грантами РФФИ и других научных фондов.

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

В статье Г.В. Ключникова, А.С. Косачева, Н.В. Пакулина, А.К. Петренко и В.З.

Шнитмана “Применение формальных методов для тестирования реализации IPv6” представлен опыт разработки тестового набора для реализации протокола IPv6. Использовался метод разработки тестовых наборов на основе формальных спецификаций UniTesK, разработанный и развиваемый в ИСП РАН. Объектом тестирования была реализация протокола IPv6, выполненная в Microsoft Research. Описываются организация тестового набора и результаты проекта.

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

Предметом статьи В.В. Кулямина и О.Л. Петренко “Место тестирования среди методов оценки качества ПО” является оценка места тестирования в современном процессе производства программного обеспечения. Исследуются понятия качества ПО и значимости тестирования при обеспечении и контроле качества.

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

О некоторых задачах анализа и Данная работа имеет следующую структуру: в разделе 2 мы рассматриваем задачу автоматического разбиения программы на нити, в разделе трансформации программ* рассматриваются задачи маскировки программ, а в разделе 4 задача автоматического выявления уязвимостей. Далее в разделе 5 кратко описывается интегрированная среда IRE, её состав и внутреннее представление С.С. Гайсарян, А.В. Чернов, А.А. Белеванцев, О.Р. Маликов, MIF, используемое всеми компонентами IRE. Наконец, в разделе 6 мы Д.М. Мельник, А.В. Меньшикова формулируем выводы данной работы и даём направления дальнейших исследований.

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

компьютеры, содержащие несколько центральных процессоров. Массовые многопроцессорные системы обычно содержат 2, 4 или 8 процессоров, 1. Введение работающих над общей памятью с одинаковым для всех процессоров временем В настоящей статье обсуждаются некоторые перспективные направления доступа (SMP). Для максимального использования возможностей SMP-систем исследований, проводимые в отделе компиляторных технологий Института в вычислительно-интенсивных приложениях необходимо максимально системного программирования РАН. Методы анализа и трансформации использовать «легковесные» процессы (нити). В этом случае накладные программ, ранее применявшиеся в основном в оптимизирующих расходы на коммуникацию минимизированы, так как все нити разделяют одно компиляторах, в настоящее время находят применение при решении адресное пространство, а синхронизационные операции выполняются проще и множества смежных задач, таких как обеспечение безопасности программ, быстрее, чем для обычных («тяжелых») процессов.



генерация тестов для программ и т. д.

Известно, что большинство программ при работе демонстрируют хорошую В отделе ведётся работа и в традиционной области оптимизации программ.

локальность, т.е. работают над близко расположенными в памяти данными, Упор делается на разработку новых методов анализа указателей в программах или выполняют одни и те же инструкции. На этом наблюдении основана на языке Си. Также проводятся исследования так называемых работа процессорных кэшей. Для наиболее полного использования «полустатических» (profile-based) методов оптимизации программ. Такие возможностей кэша необходимо улучшать локальность программы.

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

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

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

параллельных приложений. Более того, часть работы по распараллеливанию последовательного кода может быть выполнена компилятором. Существует * много исследований по автоматическому распараллеливанию циклов и Работа поддержана РФФИ, грант 03-01- 7 рекурсивных процедур на таких системах. Некоторые разработки реализованы в промышленных компиляторах, например, IBM Visual Age C++, Intel C++ a = b = с = 1;

Compiler, SGI MIPSPro, REAPAR и других.

В последнее время проводятся исследования по автоматическому распараллеливанию любого последовательного кода. Предложено несколько подходов, таких, как управление выполнением нитей (thread-level speculation) [6], коммутативный анализ, динамическое распределение задач на нити (dynamic task scheduling) [5], автоматическое разделение на нити на этапе компиляции. for (; n > 1; n--) { int fib(int n) Часть предложенных алгоритмов проверена авторами на эмуляторах, часть { реализована в существующих исследовательских компиляторах, например, в int a, b, c;

c = a + b;

компиляторе SUIF Стенфордского университета [7].

a = b = с = 1;

Формализация понятия локальности проведена в [8]. Рассматривается два вида for (; n > 1; n--) { c = a + b;

событий локальности:

a = b;

Событие временной локальности происходит при повторном a = b;

b = c;

доступе к ячейке памяти, уже имеющейся в кэше.

} Событие пространственной локальности происходит при return c;

доступе к ячейке памяти, расположенной в блоке, уже загру} } женном в кэш при обращении к какой-либо другой ячейке.

b = c;

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

1) Группировка инструкций, использующих одни и те же данные (locality grouping), для увеличения количества событий временной локальности.

2) Упаковка данных в памяти (data packing) для увеличения количества событий пространственной локальности.

return c;

3) Перестановка процедур, базовых блоков и т.п.

Целью данной работы является исследование вопроса о том, как может быть Рис. 1. Пример функции и ее DDG.

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





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

описывается сам алгоритм разбиения программ на нити. Подробное описание Представлением, обладающим всеми необходимыми нам свойствами, является алгоритма можно найти в [3]. Алгоритм состоит из трех частей:

иерархический граф зависимостей по данным, используемый в [9] (data Построение ценовой модели, отражающей свойства локальdependence graph, DDG). Узлом такого графа может являться:

ности Простой оператор (сложение, умножение, сравнение, Разбиение программы на нити присваивание и т.д.) Дополнительные оптимизации 9 Все этапы алгоритма разделения на нити, описанные ниже, работают с Более сложный оператор (условный оператор, оператор цикла и представлением программы в виде графа зависимостей по данным.

т.д.) Граф зависимостей по данным следующего уровня, инкапсули2.1.2. Ценовая модель рующий свойства соответствующего программного блока Нашей целью является построение разбиения программы на нити, Дуги графа DDG представляют собой зависимости по данным между узлами.

максимально использующего возникающие события локальности. Чтобы иметь Более формально, пусть u и v – узлы DDG, причем в последовательной возможность судить о степени оптимальности того или иного разбиения, программе u предшествует v. Дуга (u, v) входит в граф тогда и только тогда, необходимо ввести некоторую ценовую модель. Так как мы оптимизируем когда между u и v есть зависимость по данным одного из трех типов:

время выполнения программы, то естественно ввести веса узлов графа «запись-чтение» (в узле v необходимы результаты вычислений зависимости по данным, равные времени выполнения узла в последовательной узла u), программе.

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

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

точно показывает реальное время выполнения программы, но затрудняет Легко заметить, что граф зависимостей по данным является ориентированным эмуляцию кэша на этапе разделения на нити, так как сложно определить, ациклическим графом. Это объясняется тем, что циклы в DDG означают насколько уменьшится время выполнения узла при попадании в кэш наличие циклических зависимостей по данным, возможных, в свою очередь, (возможно, при профилировании это попадание уже произошло).

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

и соответствующая корректировка времени выполнения узла.

Пример функции и ее графа зависимостей по данным приведен на Рис. 1. DDG состоит из трех узлов: двух простых узлов и оператора цикла, 2.1.3. Разбиение на нити раскрывающегося в DDG второго уровня.

На этом шаге производится собственно разбиение графа зависимостей по Граф зависимостей по данным строится для каждой функции программы.

данным на нити. Количество нитей является параметром алгоритма. Так как Алгоритм построения состоит из следующих этапов:

целью разбиения является получение выигрыша по времени, возникающего из Построение графа потока управления программы.

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

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

помощью алгоритма достигающих определений.

Алгоритм разбиения состоит в итерировании списка узлов графа, еще не Если необходимо, продвинуться на следующий уровень назначенных конкретной нити, и определения нити для какого-либо из узлов иерархии и достроить граф.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 36 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.