Аннотация

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

Оглавление

1 Введение. 3

1.1 Параллельное программирование. 3

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

1.3 Статический анализ. 6

1.4 Динамический анализ. 8

1.5 Распараллеливание во время выполнения. 9

1.6 Цель работы.. 10

2 Постановка задачи. 11

2.1 Зависимости по данным. 11

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

2.3 Задача анализатора. 13

3 Динамический анализ. 14

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

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

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

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

4 Практическая реализация. 22

4.1 Инструментация. 22

4.2 Формат результатов. 24

4.3 Внутреннее устройство анализатора. 26

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

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

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

1. Введение

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

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

Параллельным программированием будем называть процесс написания программы для многопроцессорной системы. Разумеется, параллельное программирование имеет ряд особенностей по сравнению с традиционным последовательным программированием. Кроме того, в зависимости от типа многопроцессорной системы применяются различные средства программирования:

Системы с общей памятью (SMP) – набор параллельно работающих процессоров, имеющих доступ к общей для всех процессоров памяти, причем скорость доступа к памяти одинакова для всех процессоров. Применяется программирование в модели общей памяти, как правило, с использованием интерфейса OpenMP.

Системы с неоднородным доступом (NUMA) – набор блоков, содержащих несколько процессоров и общую для них память. При этом допускается обращение любого процессора к удаленной памяти, т.е. памяти другого блока, но обращение происходит медленнее, чем обращение к локальной памяти. При программировании применяется, например, система Shmem.

Системы с распределенной памятью (MPP) – набор узлов, состоящих из процессора и памяти, и коммутационной среды для связи между узлами. Каждый процессор имеет непосредственный доступ только к своей локальной памяти. При программировании применяется модель передачи сообщений, используются библиотеки MPI, PVM и др.

Смешанные системы – набор SMP-узлов, соединенных коммутационной средой. Применяется комбинация моделей передачи сообщений и общей памяти. ............