Архитектура параллельных вычислений

Parallel Programming Architecture

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

Под средствами реализации параллельности понимаются языки программирования или библиотеки, обеспечивающие инфраструктуру параллельных программ.  К ним можно отнести: Occam, MPI, HPF, Open MP, DVM, Open TS, Boost.Thread, Posix Threads. Сюда также можно отнести библиотеку Integrated Performance Primitives компании Intel.

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

Данная работа состоит  из трех взаимосвязанных тематических разделов.

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

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

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

 

 

 

 

 

Глава 1. Математическое обеспечение параллельных вычислений.

 

1.1 Проблемы разработки параллельных алгоритмов

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

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

1) отсутствие полного  параллелизма в алгоритмах исследования  и  решения задач (некоторые  операции алгоритмов являются  последовательными);

2) неравномерная загрузка  процессоров по числу арифметических  операций (несбалансированность нагрузки  процессоров);

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

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

–  распараллеливание  не только  арифметических действий, а и обменов  данными между  процессорами;

        –   определение топологии и количества  процессоров, необходимых для  эффективного решения задачи;

–  обеспечение равномерной  загрузки всех процессоров, которые  используются для решения задачи;

–  организация обменов  между процессорами;

–  синхронизация обменов  между процессорами;

–  минимизация обменов  между процессорами;

–  распределение исходной информации между процессорами в  соответствии с выбранной конфигурацией  и др.

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

0

1

2

3

0

1

2

3

0

1

2

3

0

1

2

3

0

1

2

3

 
  Рисунок 1                                                      Рисунок 2

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

 

1.2 Представление алгоритма

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

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

Представление алгоритма есть набор , где - конечное множество переменных,   - конечное множество операций. 

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

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

– управление, т. е. множество  ограничений на порядок выполнения операций. Управление может задаваться разными способами, это бинарное отношение частичного порядка на множестве  операций алгоритма .

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

Рисунок 3

Реализацией алгоритма , представленного в форме , называется выполнение операций в некотором произвольном допустимом порядке, который не противоречит управлению . Предполагается, что при любой реализации вычисляется функция , т.е. всегда содержит потоковое управление, которое и гарантирует вычисление . Множество всех реализаций алгоритма , представленного в форме , обозначим через . Если есть одноэлементное множество, то -  последовательное   представление. Будем говорить, что - параллельное представление алгоритма , если множество содержит, более одной реализации.

Пусть , – операции,  ,  ,  . Тогда алгоритм вычисления функции , представлен в параллельной форме , , и – операции. Определим теперь бинарное отношение непроцедурности на множестве представлений алгоритма .  Будем говорить,  что представление алгоритма более непроцедурно, чем , если . 

Представление алгоритма с потоковым управлением и тождественным распределением ресурсов является максимально непроцедурным представлением .

 

1.3 Коммуникационно-замкнутые слои параллельной программы

Это понятие  вводится для упрощения верификации (доказательства правильности) параллельных программ. Основная идея здесь - это разбиение каждого процесса параллельной программы на последовательность его операторов:

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

 

Эту программу можно изобразить матрицей (рис. 4)

Рисунок 4

Каждая -я строка изображает процесс как последовательность    операторов:

 

Параллельная программа  называется -м слоем параллельной программы (-й столбец матрицы). 

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

Тогда последовательность слоев  представляет собой параллельную программу:

,

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

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

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

 

 

 

1.4 Граф достижимости

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

Разметка  называется достижимой, если при некоторой конечной последовательности срабатываний переходов, начиная с начальной разметки , сеть переходит к разметке . Граф достижимости определяет все достижимые разметки и последовательности срабатываний переходов,  приводящих к ним. Его вершинами являются разметки, а дуга, помеченная символом перехода , соединяет разметки и такие, что сеть переходит от разметки к разметке при срабатывании перехода . Любой конечный фрагмент графа достижимости, начинающийся с начальной разметки и до некоторых достижимых разметок, называется разверткой сети.  Множество всех разверток определяет поведение сети Петри. Пример различных разверток сети  показан на рис. 4с. Каждая разметка определяет состояние сети. Состояние сети характеризуется множеством переходов, которые могут сработать в состоянии .

  

Рисунок 5

Сеть на рисунке 5а определяет управление двумя параллельно протекающими процессами с синхронизацией ˗ оба процесса поставляют фишки, необходимые для срабатывания  перехода . Граф достижимости показан на рис. 5b. Он бесконечен, однако после разметки в каждой ветви повторяется один и тот же фрагмент и потому возможно конечное представление графа достижимости  (рис.  5b).  Множество разверток сети  бесконечно,  примеры разверток приведены на рис. 5с.