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