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

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с.

 

1.5 Сети Петри

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

Определение сети Петри дадим  в три приема. Сеть есть двудольный ориентированный граф. Напомним, что  двудольный граф – это такой граф, множество вершин которого разбивается  на два подмножества и не существует дуги, соединяющей две вершины  из одного подмножества. Итак, сеть –  это набор

, 

где

 – подмножество  вершин, называющихся переходы, – подмножество вершин, называющихся местами, –множество ориентированных дуг. 

По определению, ориентированная  дуга соединяет либо место с переходом либо переход с местом. Состояние сети в каждый текущий момент определяется системой условий. Для того, чтобы стало возможным и удобным задавать условия типа “в буфере находится три значения” в определение сети Петри добавляются фишки (размеченные сети). Фишки изображаются точками внутри места. В применении к программированию можно представлять себе переходы как процедуры, а места – как переменные.

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

 

1.6 Задача взаимного исключения

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

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

Рисунок 6

Итак, два процесса (переходы t3 и t5) запрашивают единственный экземпляр  ресурса  но только одному процессу ресурс может быть выделен. Во множестве поведение сети на рис. 6 нет такой развертки сети, которая бы привела к одновременному срабатыванию переходов и .

Сеть Петри не определяет, какой именно из двух конкурирующих  процессов получит доступ к ресурсу.  Она лишь описывает ограничение на доступ к ресурсу - только один процесс получает доступ к ресурсу . Как следствие,  при таком задании управления возможна ситуация,  когда доступ к ресурсу будет постоянно получать один и тот же процесс, например ,  а процесс останется “навечно” ожидать выделения ему ресурса .

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

Другой  способ выделения  ресурса  -  устройство очереди.  Все запросы ресурса выстраиваются  в очередь к ресурсу и процесс, раньше все запросивший ресурс,  получит его первым  (дисциплина обслуживания FIFO - First_In - First_Out).

 

1.7 Динамические и итерационные вычислительные модели с массивами

Для ограничения вычислений нужны дополнительные средства, которые  и вводятся в вычислительных моделях  с массивами. Вначале определяются динамические вычислительные модели с  массивами (ВММ), а затем итеративные

Пусть заданы:

1.  Множество переменных  , где и Y—те же множества простых переменных и компонентов массивов, а —конечное множество переменных, называемых счетчиками, ; каждому массиву соответствует счетчик из , который обозначается .

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

а)  если —массовая операция,  то(.); 

б)  в множестве существует только одна такая простая операция , что

Счетчики являются особыми  переменными, значение счетчика определяет число компонентов массива (допускаются только такие интерпретации). Массивы называются динамическими массивами.

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

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

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

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

На рис. 7. показана массовая операция a итеративной ВММ, ,  план, вычисляющий массив x , содержит все термы вида . При должной интерпретации алгоритм, заданный планом, может считывать в оперативную память все записи файла.

 

Рисунок 7

На рис.8а показана структурированная итеративная ВММ .  Структурная интерпретация массовых операций и приведена на рис. 8б и 8в. Операциям и ВММ (рис. 8а) соответствуют ВММ (см.  рис. 8б) и (см. рис. 8в); ; переменные—это счетчики , а — массивы в ВММ   и .

Рисунок 8а.

Рисунок 8б.

Рисунок 8в.

Если содержательно интерпретировать:

: (цельное положительное  число),

; ввод )),

(ввод)), : (ввод),

 

 

; печать (),

: (печать (),

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

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

 

 

Глава 2. Аппаратное обеспечение параллельных вычислений.

 

2.1 Классификация  Флинна

Одной из наиболее известных схем классификации компьютерных архитектур является таксономия Флинна, предложенная Майклом Флинном в 1972 году. В ее основу положено описание работы компьютера с потоками команд и данных. В классификации Флинна имеется четыре класса архитектур:

1. SISD (Single Instruction Stream — Single Data Stream) — один поток   команд и один поток данных.

2. SIMD (Single Instruction Stream — Multiple Data Stream) — один  поток команд и несколько потоков данных.

3. MISD (Multiple Instruction Stream — Single Data Stream) — несколько  потоков команд и один поток данных.

4. MIMD (Multiple Instruction Stream — Multiple Data Stream) —  несколько потоков команд и несколько потоков данных.

Рассмотрим  эту классификацию более подробно.

SISD-компьютеры (рис. 9) — это обычные  последовательные компьютеры, выполняющие  в каждый момент времени только  одну операцию над одним элементом  данных. Большинство современных  персональных ЭВМ принадлежат  именно этой категории.

 

Рисунок 9

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

SIMD-компьютеры (рис. 10 и 11) состоят  из одного командного процессора (управляющего модуля), называемого  контроллером, и нескольких модулей обработки данных, называемых процессорными элементами (ПЭ). Количество модулей обработки данных таких машин может быть от 1024 до 16 384. Управляющий модуль принимает, анализирует и выполняет команды. Если в команде встречаются данные, контроллер рассылает на все ПЭ команду, и эта команда выполняется либо на нескольких, либо на всех процессорных элементах. Процессорные элементы в SIMD-компьютерах имеют относительно простое устройство, они содержат арифметико-логическое устройство (АЛУ), выполняющее команды, поступающие из устройства управления (УУ), несколько регистров и локальную оперативную память. Одним из преимуществ данной архитектуры считается эффективная реализация логики вычислений. До половины логических команд обычного процессора связано с управлением процессом выполнения машинных команд, а остальная их часть относится к работе с внутренней памятью процессора

Рисунок 10

Рисунок 11

и выполнению арифметических операций. В SIMD-компьютере управление выполняется  контроллером, а "арифметика" отдана процессорным элементам. Подклассом SIMD-компьютеров  являются векторные компьютеры. Пример такой вычислительной системы — Hitachi S3600.

Другой пример SIMD-компьютера — матричные процессоры (Array Processor). В качестве примера можно привести вычислительную систему Thinking Machines CM-2, где 65 536 ПЭ связаны между собой сетью коммуникаций с топологией "гиперкуб". Часто компьютеры с SIMD-архитектурой специализированы для решения конкретных задач, допускающих матричное представление. Это, например, могут быть задачи обработки изображений, где каждый модуль обработки данных работает на получение одного элемента конечного результата.

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

Рисунок 12

MIMD-компьютеры. Этот класс архитектур (рис. 13 и 14) наиболее богат примерами успешных реализаций. В него попадают симметричные параллельные вычислительные системы, рабочие станции с несколькими процессорами, кластеры рабочих станций и т. д. Довольно давно появились компьютеры с несколькими независимыми процессорами, но вначале на них был реализован только принцип параллельного исполнения заданий, т. е. на разных процессорах одновременно выполнялись независимые программы. Разработке первых компьютеров для параллельных вычислений были посвящены проекты под условным названием СМ* и С.ММР в университете Карнеги (США). Технической базой для этих проектов были процессоры DEC PDP-11. В начале 90-х годов прошлого века именно MIMD-компьютеры вышли в лидеры на рынке высокопроизводительных вычислительных систем.

Рисунок 13

Рисунок 14

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

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