Лекции по дисциплине «Теория вычислительных процессов» (стр. 8 )

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

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

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

Иерархическая структура алгоритмов и распространенный принцип вложенности, отображаемый в языках программирования лексико-графическими уровнями, при организации вычислительного процесса порождают понятие стека, определяющего порядок обработки алгоритмических конструкций по уровням вложенности. Это понятие не только распространяется на принцип взаимодействия процедур и процессов, организацию циклов и прерываний, но может отражать и порядок выполнения операций в АЛУ, т. е. определять работы исполнительных устройств решающего поля. Принцип выполнения операций в стеке способствует непрерываемости счета значений арифметических и логических выражений. Он обеспечивает оперативное использование промежуточных результатов, помогает минимизировать число обращений процессоров к общей памяти, обеспечивает опережающую "подкачку" данных. Кроме того, стековый принцип вычислений полнее соответствует записи арифметических и логических выражений на алгоритмических языках, что упрощает трансляцию. Так как решающее поле ВС предназначено для выполнения арифметических и логических операций, то распределение работ между его исполнительными устройствами непосредственно по их записи на алгоритмическом языке или по ее трансформации в запись, отражающую стек, является одной из важных задач оптимизации загрузки решающего поля ВС. Задача заключается в построении алгоритмов распараллеливания в стеке для однородного и неоднородного решающих полей.

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

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

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

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

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

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

Информация обо всех r объектах с которыми имеет дело данная задача обрабатывается по почти одинаковой программе однако некоторые ветви программы для различных объектов различны.

Например: Граф управления программы в соответствии с которым программа обработки информации об объектах до (i - 1) - ого этапа включительно идет для всех объектов одинаково далее объекты классифицируются на mi классов (mi = 2, 3, ... r) и в зависимости от того к какому из классов принадлежит данный объект – i - тый этап выполняется в одном из mi вариантов далее программа вновь идет для всех объектов одинаково вплоть до (j-1) - го этапа включительно затем объекты классифицируются на mi классов и j - i этап программы выполняется в одном из mj вариантов. Предположим, что mk различных вариантов имеется для любого k - ого этапа программы, но для большинства этапов mk = 1. Предположим что длина оператора KSk, где k=1, 2 ... Sk = 1, 2 ... mk, есть lKSk. Длина оператора – это фактически время его исполнения. Для различных вычислительных машин или разных физических реализаций величины lKSk могут быть различны.

Суммарной длинной программы Lå назовем величину Lå =, а средней длинной программы – величину lср, равную lср = 1/r =, где rKSk - количество объектов которые на k - том этапе относятся к Sk - му классу (т. е. для которых исполняется оператор KSk.)

r = для любых k.

Величину расхождения программы D определим как отношение суммарной длины программы к ее средней длине

D = Lå / Lср.

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

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

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

Ветвь программы Y не зависит от ветви X если удовлетворяются четыре условия:

1) между ними нет функциональных связей иначе говоря ни одна из входных переменных для ветви Y не является выходной переменной ветви X либо какой-нибудь ветви зависящей от X

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

3) они не зависимы в программном отношении, т. е. должны выполняться по разным программам

4) они независимы по управлению, иначе говоря, условие выполнения ветви Y не должно зависеть от признаков вырабатываемых при выполнении ветви зависящей от X.

При практическом использовании параллелизма независимых ветвей применяется аппарат ярусно параллельных форм. При этом программа представляется в виде ярусов, причем в 0-ой ярус входят все те ветви программы каждая из которых не зависит ни от одной другой ветви в 1-й ярус ветви зависящие только от ветвей 0-го яруса во 2-й ярус ветви зависящие только от ветвей 1-го яруса и ветвей 0-ого яруса и т. д.

Кружочками обозначены ветви программы внутри кружочков проставлены номера ветвей а рядом с кружками – длины этих ветвей. Если одна и таже ветвь программы может быть исполнена и различными средствами ВС за разные времена то, вместо одного числа обозначающего длину ветви нужно поставить n-мерный вектор. Сплошными стрелками обозначены функциональные связи между ветвями, а штриховыми – связи по управлению. Сплошная стрелка входящая в некоторый кружок обозначает входящую переменную или группу входных переменных для соответствующей ветви. Если эта стрелка не входит ни в ка45ой другой кружок, то она обозначает выходные данные программы. Разветвления стрелок показывают, что одни и те же данные являются входными для двух и более ветвей.

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

bi – ширина i - го яруса т. е. количество независимых ветвей в i-ом ярусе

B – ширина графа ЯПФ – максимальная ширина яруса

li и L – длина яруса и длинна графа

e и q -- коэффициент заполнения ярусов и коэффициент разброса.

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

Суть параллелизма смежных операций состоит в следующем. При исполнении программы довольно часто встречаются ситуации, когда исходные данные для некоторой операции и условия ее выполнения вырабатываются не при исполнении предыдущей операции, а раньше. Если это так, то соответствующее построение ВС может позволить совместить время исполнения i-ой операции с исполнением i-1 или i-2 операции.

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