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

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