Geum.ru

Вычислительные процессы взаимодействие и управление процессами

Вид материалаЛекция

Содержание


5.5. Предпосылки создания систем параллельного действия
5.6 Некоторые примеры параллельных программ.
Подобный материал:
1   2   3

5.5. Предпосылки создания систем параллельного действия


 

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

ЭВМ и их МО являются на сегодня, пожалуй, самыми дорогостоящими продуктами производства, поэтому эффективность их применения требует бóльшего внимания. Работа современных ЭВМ в пакетном режиме использует это дорогостоящее оборудование крайне неэффективно. Речь идет не только о том, что простои оборудования в среднем достигают 50 %, но и о том, что половина оставшегося времени идет на отладку программ. Если сюда присовокупить время на процессы трансляции, сборки, редактирования связей – необходимые этапы подготовки задачи к счету, то доля полезного времени для обработки данных по отлаженной программе окажется совсем незначительной.

За время развития вычислительной техники накладные расходы на каждую с пользой выполненную команду программы выросли на 3–4 порядка. (Раньше роль транслятора, сборщика, редактора играл сам программист.) Созданные за это время средства автоматизации проектирования программ и их подготовки к обработке лишь в 40–50 раз повышают производительность работы программиста. Поэтому проблема изменения соотношения времени, затрачиваемого ЭВМ на подготовку задач и на получение "полезных результатов" в пользу последнего, является актуальной. Изменение указанного соотношения можно осуществить через преобразование структуры компьютера.

Для универсальных ЭВМ характерен широкий набор команд и данных. Во время трансляции, например, главным образом используется небольшое подмножество этих команд, связанное с преобразованием текстов. Возможности АУ по выполнению арифметических операций с плавающей точкой и удвоенной точностью не используются, при выполнении вычислений все обстоит наоборот. Что касается операции ввода-вывода, то на разных этапах ее используются только определенные возможности компьютера. Поэтому целесообразно иметь хотя бы два процессора в ЭВМ: один использовать только для обработки данных, а другой – для подготовительных работ. Основная трудность двухпроцессорной организации заключается в сбалансировании ее работы. Аналогичную картину можно проследить с использованием памяти, отдельные участки которой простаивают длительное время из-за отсутствия к ним обращений. При анализе динамики обращений к памяти при решении некоторых классов вычислительных задач было установлено, что ОЗУ активно используется лишь на 10–15 %.

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

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

Пусть надо вычислить значение r по формуле

r = x + y • z.
(*)

Формулу (*) можно рассматривать как некоторый преобразователь чисел x, y, z в некоторое другое число r = x + y • z. Пусть все числа заданы в двоичной форме (на общность рассуждений это не влияет). Таким образом, речь идет о преобразовании некоторого набора нулей и единиц, представляющих собой последовательность чисел x, y, z в некоторый другой набор нулей и единиц для r. Из алгебры логики известно, что для любой функции можно построить дизъюнктивную нормальную форму (ДНФ). В свою очередь, i-й двоичный разряд результата r можно рассматривать как логическую функцию

ri = r (x1, x2, ..., xn, y1, y2, ..., yn, z1, z2, ..., zn),

где xi, yi, zi, – двоичные разряды, представляющие возможные значения x, y, z.

Так как любая функция (вычисление любого разряда ri) i =  может быть представлена ДНФ (через И, ИЛИ, НЕ), то можно построить n схем (n процессоров), которые, работая одновременно, выдают все n разрядов результата r. Ясно, что подобные рассуждения носят абстрактный характер и ими трудно воспользоваться на практике, ибо количество конкретных алгоритмов – бесконечное множество. Но тем не менее подобный подход позволяет рассматривать с общих позиций попытку реализовать вычислительные среды – многопроцессорные системы, динамически настраиваемые на конкретный алгоритм. Принципиальная возможность распараллелить любой алгоритм оправдывает те усилия, которые предпринимаются сегодня для решения этой задачи.

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

Технические предпосылки для создания МВС накапливались постепенно. Скажем, идея комплексирования ЭВМ через общую память была апробирована в многомашинном комплексе "Минск-222" в 1966 г. Внутри машин ряда I серии ЕС ЭВМ были заложены основы комплексирования ЭВМ, правда, с некоторыми ограничениями. Более широкие возможности комплексирования ЭВМ серии ЕС представлены в машинах ряда 2 и 3.

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

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

2. Создание новых структур – МВС. При этом внутреннюю систему команд компьютеров приближают к языкам высокого уровня.

3. Разработка и создание перестраиваемых однородных МВС, пригодных для решения задач, распараллеливаемых на уровне входных алгоритмов. В них, например, центральная ВС может состоять из "однородного управляющего поля" и "однородного решающего поля". Каждое поле представляет собой набор однотипных специализированных блоков, выполненных на микроэлементной интегральной базе. Элементы управляющего поля независимо занимаются обработкой команд. Блоки управляющего поля могут одновременно обрабатывать команды различных программ, выбирая их из разных областей общей памяти. Блок, по существу, представляет собой УУ обычной ЭВМ, которое выбирает команду, дешифрирует ее, вычисляет исполнительный адрес, выбирает операнд и т. д.

Решающее поле состоит из однотипных элементов и представляет собой АУ, способное выполнять арифметические и логические операции над некоторыми типами данных

5.6 Некоторые примеры параллельных программ.

Развитие точных методов в программировании привело к возникновению различных формальных моделей программ, в том числе и моделей параллельных программ.

Рассмотрим модели параллельных программ, прототипом которых явились операторные схемы программ, в частности схемы Янова.

В.Е.Котовым и А.С.Нариньяни была предложена формальная модель параллельных вычислений, названная асинхронной моделью.

Асинхронная программа над памятью M (A-программа) представляет собой множество X блоков и массивов блоков. Блок x образован парой (y, 0), где y – предикат над MCM, MC – управляющая память, O – оператор над памятью M. С O-оператором связаны входные и выходные наборы переменных из М. По входному набору О-оператор вычисляет значение переменных выходного набора. Предикат y– спусковая функция блока x.

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

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

Пусть A– множество операторов над памятью M.

Для каждого момента t множество операторов вычислительного процесса можно разбить на 4 непересекающихся множества:

+At  – включающиеся в t;

-At– выключающиеся в t;

pAt– находящиеся во включенном состоянии;

0At– находящиеся в выключенном состоянии.

Q = {q} – множество состояний метасистемы, q0– начальное состояние.

F– функция, однозначно сопоставляющая каждому множеству   одно из его подмножеств в соответствии с состоянием q.

 – функция, ставящая в соответствие каждому набору   некоторое состояние q ( – предыстория процесса Р до момента t включительно).

Каждому оператору aiA сопоставляется счетчик ci с начальным значением . Текущее значение счетчика ciфиксирует разность между числом имевших место включений и числом имевших место выключений оператора ai.

Тогда модель Котова–Нариньяни можно записать в виде рекурсивных соотношений:

qt = (M0, P||t-1);

At=At-1\+At-1 -At-1;

*At=F1(0At, qt);

+At  *At;

рAt=рAt-1\-At-1 +At;

-At  рAt.

В основу модели Карпа – Миллера легло представление программы как множества элементарных операторов, использующих ячейки памяти и воздействующих на них, для которых указаны правила включения и выключения. Формально параллельная схема программы R = (M, A,  ) определяется следующим образом.

1. М – множество ячеек памяти.

2. A={a,b,...} – конечное множество операторов; для каждого оператора из А заданы:

K(a) – количество символов выключения оператора a (целое положительное число);

Д (а)  М – множество входных ячеек оператора а;

Т (а)  М – множество выходных ячеек оператора а.

3.Четверка Г = (а, q0,,)  – управление схемы,

где  q0– выделенное начальное состояние.

При этом каждому оператору а сопоставлены один символ включения   и множество символов выключения {a1, ..., ak(a)};  

где

,



 – функция переходов – частичная функция из Qx в Q, всюду определенная на Qxt.

Управление Г формирует последовательность выполнения операторов. Элементы из i обозначают акты включения операторов, элементы из t– акты выключения. Включение оператора а допустимо лишь в таком состоянии q, что значение  (q, a) определено. После включения оператора завершение его работы допустимо в произвольном состоянии, поскольку функция  всюду определена на Qxt. При включении оператор а использует значения ячеек из Д (а), при выключении он засылает свои результаты в ячейки из Т(а) и формирует символ выключения, который соответствует одному из K(а) направлений условной передачи.

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

Счетчиковой схемой называется схема R=(M, A, Г ), для которой управление Г задается следующим образом.

Пусть k – целое неотрицательное число;

 – конечное множество;

S – множество с выделенным элементом S0;

k, где k – множество неотрицательных целых чисел;

v – функция из  в k, такая, что если t, то v()0;

: SxS – частичная функция, всюду определенная на Sxt.

Полагая, что значение ((S,x),) определено, если определено (S,) и выполнено x+v()0. Если значение определено, то полагается ((S,x),)=((S,), x+v()).

Более простыми и наглядными являются параллельные операторные схемы – частный случай счетчиковых схем.

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

1) S = {S0};

2) для каждого  значение (S0,) определено;

3) если  – символ выключения, то каждая компонента вектора v() равна 0 или 1;

4) если  – символ включения, то каждая компонента вектора v() равна 0 или -1;

5) для любых двух неравных символов включения ,  из v()i= -1 следует v()i=0.

Параллельную операторную схему можно представить в виде ориентированного графа с операторными вершинами Оа, Оb, Оc,... и вершинами-счетчиками d1, d2, ..., dk. Каждый счетчик di помечается числом i, которое является начальным значением этого счетчика. Дуги графа направлены либо от операторных вершин к счетчикам, либо от счетчиков к операторным вершинам. Дуги сопоставлены ненулевым компонентам векторов v().

Если (v(aj))i=1, то выключение оператора а с символом выключения aj увеличивает значение счетчика i на 1. Если (v())i= –1, то включение оператора а уменьшает значение счетчика i на 1. Условие 5 из определения параллельной операторной схемы означает, что из произвольного счетчика выходит не более чем одна дуга.

Пример. Пусть необходимо перемножить матрицу

  на вектор ,

а результат поместить в (с1, с2).

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

Рассмотрим теперь другие модели программ, которые в меньшей мере опираются на понятие операторных схем программ.

В качестве модели программы иногда предлагается пара R=(M,C), где M определяет ее информационную, а С – управляющую структуру. Для представления информационной структуры М используются простые вычислительные модели, а для представления управляющей структуры – сети Петри. Сеть Петри – двудольный граф, множество вершин которого состоит из переходов tjT и позиций piP. Кроме того, заданы две функции инцидентности:

F : PxT{0,1};

B : TxP{0,1}.

Они задают множество дуг, ведущих из позиций в переходы и из переходов в позиции. N0 : P{0,1,2,...} – начальная разметка сети. Сеть Петри функционирует, переходя от одной разметки к другой. Каждая разметка – это функция N : P{0,1,2,...}. Схема разметок происходит в результате срабатывания одного из переходов. Переход t может сработать, если для него выполнено условие срабатывания (N(p)–F(p,t))0 p. После того как переход t срабатывает, разметка N сменяется разметкой N по следующему правилу:

p(N(p)=N(p)–F(p,t)+B(p,t)).

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

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





Рис. 5.5. Графовые структуры

    безусловные, которые не зависят от текущих значений переменных в исполняемой программе;

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

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