Решение задач на тему: Анализ зависимостей по данным является важнейшим этапом при распараллеливании программ. Данная

Введение

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

Оглавление

- 1 Введение 3

- Параллельное программирование

- Автоматизация распараллеливания

- Статический анализ

- Динамический анализ

- Распараллеливание во время выполнения

- Цель работы

- Постановка задачи

- Зависимости по данным

- Система автоматизации распараллеливания

- Задача анализатора

- Динамический анализ

- Схема работы динамического анализатора

- Динамический анализ с использованием дерева контекстов

- Динамический анализ с использованием глобальных номеров итераций

- Преимущества и недостатки динамического анализа

- Практическая реализация

- Инструментация

- Формат результатов

- Внутреннее устройство анализатора

- Результаты тестирования

- 5 Заключение 30

- 6 Литература 31

Заключение

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

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

В рамках данной работы один из методов динамического анализа был реализован в виде библиотеки на языке С++ (около 2500 строк исходного кода). Проведено тестирование анализатора на наборе программ на языке Си, представляющих собой реализации классических итерационных методов (Якоби, SOR, RedBlack) и метода Гаусса. Тем самым показана возможность применения динамического анализа для поиска зависимостей в программах, требующих распараллеливания.

Список литературы

2. Проект V-Ray [HTML] (http://parallel.ru/v-ray).

3. Jacobson Т., Stubbendieck G. Dependency Analysis оf FOR-Loop Structures for Automatic Parallelization оf С Code [PDF] (http://www.css.edu/depts/cis/mics_2003/MICS2003_Papers/Jacobson.PDF).

4. Karkowski I., Corporaal Н. Overcoming the Limitations оf the Traditional Loop Parallelization // Journal оf Future Generation Computer Systems. 1998. № 13. Р. 407-416.

5. Petersen Р.М. Evaluation оf Programs and Parallelizing Compilers Using Dynamic Analysis Techniques. Champaign, IL, USA: University оf Illinois аt Urbana-Champaign, 1993. 164 р.

6. DVM-система [HTML] (http://www.keldysh.ru/dvm).