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

 

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-архитектуры с распределенной памятью нет, а особенностью является медленное сетевое соединение.