Аннотация

Цель данной работы - разработка и реализация алгоритмов блока «Эксперт для мультипроцессора» в проекте «Экспериментальная система автоматизации распараллеливания». На основании результатов анализа последовательной программы и характеристик конкретного мультипроцессора «Эксперт» генерирует и оценивает различные варианты распределения вычислений и локализаций данных. После выбора наилучшего варианта он вставляет в последовательную программу директивы OpenMP, посредством которых она превращается в параллельную программу для мультипроцессора. Кроме того, эксперт выдает информацию о прогнозируемой эффективности распараллеливания.

Оглавление

1 Введение.. 4

1.1 Распараллеливание программ.. 4

1.2 Стандарт OpenMP.. 7

1.3 Распараллеливание для OpenMP.. 11

1.4 Cуть и актуальность проблемы.. 12

2 Цели дипломной работы.. 13

2.1 Цели проекта «Система автоматизации распараллеливания» . 13

2.2 Цели «Эксперта для мультипроцессора» . 14

2.3 Входные данные. 14

2.4 Выходные и сохраняемые данные. 15

3 Предыдущие решения «систем автоматизации распараллеливания» .. 16

4 Построение решения задачи.. 17

4.1 Формат входных данных. 17

4.2 Основные аспекты работы эксперта. 17

4.3 Оценочные функции.. 19

5 Пошаговая реализация «Эксперта» .. 21

5.1 Шаг 1. Предварительный анализ. 21

5.2 Шаг 2. Выбор варианта распараллеливания. 22

5.3 Шаг 3. Выбор варианта локализации.. 24

5.4 Шаг 4. Внесение конечных комментариев в Базу Данных и подсчет ускорения. ………………………………………………..25

5.5 Примеры работы алгоритма. 28

5.5.1 Программа «Якоби» . 28

5.5.2 Программа «Sor » . 32

5.5.3 Программа «Модифицированный SOR » . 37

5.5.4 Программа «Модифицированный Якоби» . 39

6 Заключение.. 42

Перечень принятых терминов.. 43

Литература.. 44

1. Введение

   1. Распараллеливание программ

Последние годы во всем мире происходит бурное внедрение вычислительных кластеров. Это вызвано тем, что кластеры стали общедоступными и дешевыми аппаратными платформами для высокопроизводительных вычислений. Одновременно резко возрос интерес к проблематике вычислительных сетей (GRID) и широко распространяется понимание того, что внедрение таких сетей будет иметь громадное влияние на развитие человеческого общества, сравнимое с влиянием на него появления в начале века единых электрических сетей. Поэтому, рассматривая проблемы освоения кластеров необходимо принимать во внимание и то, что они являются первой ступенькой в создании таких вычислительных сетей.

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

Если все входящие в состав вычислительного кластера узлы имеют одну и ту же архитектуру и производительность, то мы имеем дело с однородным вычислительным кластером. Иначе – с неоднородным.

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

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

Тем не менее, любой кластер можно рассматривать как единую аппаратно-программную систему, имеющую единую коммуникационную систему, единый центр управления и планирования загрузки. Вычислительные сети (GRID) объединяют ресурсы множества кластеров, многопроцессорных и однопроцессорных ЭВМ, принадлежащих разным организациям и подчиняющихся разным дисциплинам использования. Разработка параллельных программ для них усложняется из-за следующих проблем.

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

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

С 1992 года, когда мультикомпьютеры стали самыми производительными вычислительными системами, резко возрос интерес к проблеме разработки для них параллельных прикладных программ. К этому моменту уже было ясно, что трудоемкость разработки прикладных программ для многопроцессорных систем с распределенной памятью является главным препятствием для их широкого внедрения. За прошедший с тех пор период предложено много различных подходов к разработке параллельных программ, созданы десятки различных языков параллельного программирования и множество различных инструментальных средств.

На Рис. 1 описаны основные особенности симметричных мультипроцессорных систем (SMP). Для данных систем, как модель программирования для мультипроцессоров, возникла модель параллелизма по управлению (в западной литературе используется и другое название – модель разделения работы, work-sharing model). На мультипроцессорах в качестве модели выполнения используется модель общей памяти. В этой модели параллельная программа представляет собой систему нитей, взаимодействующих посредством общих переменных и примитивов синхронизации. Нить (по-английски ”thread”) – это легковесный процесс, имеющий с другими нитями общие ресурсы, включая общую оперативную память.