Однозначность и семантика вычислений в модели обмена сообщениями
РАЗДЕЛ 2. СОБЫТИЙНЫЕ И ПОТОКОВЫЕ МОДЕЛИ ОБМЕНА СООБЩЕНИЯМИ
Процессы, события, сообщения
Таксономия систем взаимодействующих процессов. В начале данного раздела конкретизируем общие требования к моделям распределенных вычислений в масштабируемых системах. Вычислительный процесс представляет собой некоторую последовательность действий (операций), связанную с выполнением программы или ее отдельных фрагментов (участков кода). Далее фрагмент программы будем называть оператором, понимая под ним, в зависимости от уровня анализа, команду, линейный участок кода, подпрограмму и т.д. При реализации распределенных программ, как правило, говорят о системе процессов, взаимодействующих посредством передачи сообщений либо разделения общей памяти. Огромное разнообразие моделей параллельных вычислений не всегда гарантирует их адекватность множеству практических задач, с которыми приходится сталкиваться при разработке распределенных приложений. Причина заключается в противоречивости требований к этим моделям и важности представления тех или иных особенностей функционирования вычислительных систем.
Прямое следствие масштабирования архитектуры – это распределенность обработки и данных, в свою очередь, определяющая недетерминированный характер вычислений. Например, различные истории выполнения распределенных программ на одних и тех же исходных данных могут быть вызваны ожиданием наступления внешних событий, арбитражем при доступе к разделяемым ресурсам, обменом сообщениями между процессами и т.д. Нас, главным образом, будут интересовать два аспекта, обусловленных распределенностью вычислений в масштабируемых системах. Во-первых, недетерминизм, означающий произвольные последовательности формирования компонентов структурированных данных. Главная проблема – как при этом обеспечить однозначность результата вычислений, когда любому допустимому набору входных данных соответствует один и только один набор выходных данных. Во-вторых, неоднородность, или произвольная структурированность, данных, которыми обмениваются взаимодействующие процессы. Неоднородность сообщений означает, что процессы могут передавать и принимать данные порциями произвольного размера. Основная проблема, которая при этом возникает, заключается в возможности блокировок вычислений, когда процессы-потребители не могут быть инициированы, не имея достаточного количества требуемых данных от процессов-производителей.
|
|
|
В основу описания свойств и систематики моделей распределенных вычислений могут быть положены следующие таксономические признаки.
|
|
|
Характеристика семейства процессов, а именно, способ их порождения и ограничение на число процессов. Известны различные программные средства создания параллельных процессов, например, операторы fork, join; cobegin, coend и их модификации. Так, поддержка паралеллизма в стандарте OpenMp основывается на операторах fork (разветвление) и join (объединение). Основная нить (мастер), с которой начинается выполнение программы, порождает параллельную область – совокупность нитей. При этом исполняется оператор fork. При выходе из параллельной области (исполнении оператора join) продолжает работать только нить-мастер. В свою очередь, нити параллельных областей могут порождать разветвления и реализовывать объединения. Это приводит к вложенности параллельных областей. Управлять обработкой вложенных областей можно с помощью переменной OMP_NESTED и функции OMP_SET_NESTED.
Под способом порождения мы понимаем статическое или динамическое задание совокупности совместно протекающих процессов. Статический механизм при запуске параллельной программы создает фиксированное число процессов, не изменяемое при выполнении программы. Первая версия интерфейса MPI поддерживает только статическую модель параллельной программы, с не изменяемым числом процессов. В некоторых парадигмах программирования, например, SPMD, процессы могут быть идентичными, т.е. они выполняют одну и ту же программу над разными данными и различаются лишь идентификаторами. Один и тот же код исполняют все порожденные нити параллельной области в рамках стандарта OpenMP. Реализация динамического механизма предполагает выполнение некоторых условий, в частности, наступление событий, при которых возможно создание и уничтожение процессов в ходе вычислений. Так, модель CSP поддерживает динамическое порождение процессов без ограничения их числа. В противоположность ей, потоковая модель SDF представляет статическое задание ограниченного числа процессов. В языке Occam, воплощающем идеи CSP, число процессов ограничивается. В модели Кана обеспечивается статическое порождение процессов с неограниченным уровнем рекурсивного параллелизма. Вторая версия системы программирования MPI предусматривает возможность динамического создания процессов. Здесь реализуются специальные механизмы, устанавливающие соответствие между работающими и вновь порождаемыми процессами. В стандарте OpenMP нити могут создаваться динамически при выполнении некоторого условия с помощью директивы
|
|
|
|
|
|
!$OMP PARALLEL IF (условие)
Число нитей в параллельной области можно изменять с помощью функции OMP_SET_NUM_THREADS. При входе в параллельную область программы эта функция, изменяя значение переменной OMP_NUM_THREADS, задает число порождаемых нитей.
Поведение процессов . Это понятие включает несколько аспектов: детерминированный или недетерминированный характер процессов; способ описания поведения (например, выделяется ли состояние процесса, ограничивается ли мощность пространства состояний); степень детализации представления процесса (в частности, является ли он последовательным либо параллельным). Так, CSP описывает поведение последовательных недетерминированных процессов, причем недетерминизм означает произвольное независимое чередование процессов. Модели SDF и Кана – совокупность последовательных детерминированных процессов. С одной стороны, поддержка недетерминизма является ценным свойством моделей вычислений и систем программирования. Оно может использоваться, как уже говорилось, для адекватного представления особенностей работы распределенных систем, для написания программ, выполнение которых устойчиво по отношению к случайным внешним событиям, для отдельных этапов программирования, когда некоторые части программы представлены лишь спецификацией, и т.п. С другой стороны, помимо проблемы однозначности результата, недетерминизм влечет за собой ряд других побочных проявлений, влияющих на эффективность вычислений. Так, например, при программировании с помощью системы MPI некоторые процессы могут сколь угодно долго находиться в ожидании приема сообщения от передающего процесса, если существует какой-либо другой процесс, постоянно посылающий вызовы MPI_Recv тому же процессу-отправителю.
Организация взаимодействия процессов . Прежде всего, это – принимаемая модель обмена данными: разделение общей памяти или передача сообщений. Далее, сюда включаются механизмы взаимодействия, в частности, способ посылки сообщений (синхронный, асинхронный), а также среда взаимодействия процессов: ограничения на емкость буфера, дисциплина упорядочения сообщений (например, FIFO), особенности доступа к каналу для передачи сообщений (проблема "писателей" и "читателей") и т.д. Как уже отмечалось в п. 1.2 раздела 1, синхронная (безбуферная) однонаправленная посылка сообщений обеспечивается в модели CSP, асинхронная однонаправленная с ограничением на емкость буфера FIFO – в модели SDF. В той и другой модели реализуется доступ "один писатель – один читатель". В процессах Кана емкость буфера (длина очереди в канале) не ограничивается, а доступ к каналу для однонаправленной передачи асинхронных сообщений реализуется по принципу "много читателей – один писатель".
Развитые возможности не только для описания взаимодействий "точка-точка" (пар процессов), но и для организации коллективных взаимодействий всех процессов коммуникатора предоставляет интерфейс MPI. Правда, нужно заметить, что безблокировочные коллективные операции обмена первая версия MPI не поддерживает. Необходимо учитывать и то, что коллективные взаимодействия в общем случае недетерминированы в том смысле, что разными процессами коммуникатора коллективная операция завершается в произвольные моменты времени. Теги сообщений не используются. Пример коллективного обмена – функция широковещательной рассылки сообщения от одного, корневого процесса source всем остальным процессам коммуникатора comm:
MPI_Bcast (buf, count, datatype, source, comm),
где buf – начальный адрес буфера процесса-отправителя; count – число передаваемых элементов; datatype – тип данных.
Предусмотрена функция сборки данных от всех процессов коммуникатора comm в буфере с начальным адресом rbuf корневого процесса-получателя dest:
MPI_Gather (sbuf, scount, stype, rbuf, rcount, rtype, dest, comm)
Здесь sbuf – начальный адрес буфера передающего процесса; scount – число элементов данных в посылаемом сообщении; stype – тип данных в посылаемом сообщении; rcount – число элементов данных в принимаемом сообщении; rtype – тип данных в принимаемом сообщении. Корневой процесс собирает данные в буфере в порядке возрастания номеров процессов коммуникатора.
Функция передачи данных является по своему действию обратной функции MPI_Gather и имеет следующий вид:
MPI_Scatter (sbuf, scount, stype, rbuf, rcount, rtype, source, comm)
Корневой процесс source рассылает данные из буфера с начальным адресом sbuf всем процессам коммуникатора. Остальные параметры этой функции аналогичны параметрам функции MPI_Gather. Предполагается, что эти функции реализуют передачу и прием данных одинаковыми порциями.
С помощью функций MPI_Gatherv и MPI_Scatterv можно организовать обмен массивами произвольных размеров. Таким образом поддерживается неоднородность сообщений, которыми обмениваются процессы.
В MPI существует еще целый ряд функций для коллективного взаимодействия процессов, в частности, редукционные операции, сборка данных с раздачей результата всем процессам, раздача/сборка данных для всех процессов коммуникатора. Во второй версии MPI коллективные операции расширяются. Например, появляется возможность взаимодействия процессов, входящих в разные коммуникаторы, внутри коммуникатора допускается совмещение входных и выходных буферов. Кроме этого, вводится схема однонаправленной посылки сообщений по принципу Put/Get, когда активным является лишь процесс-отправитель. Эта схема весьма напоминает идею почтового ящика и применима, если известны процесс-получатель и область размещения передаваемых данных.
Достоинства обмена сообщениями уже обсуждались выше. В некотором смысле соответствующая модель является более "универсальной" по сравнению с моделью общей памяти, поскольку может быть надстроена над любой из рассматриваемых в разделе 1 архитектур. Известно также, что в ряде случаев затраты на систему синхронизации процессов снижают эффективность параллельных вычислений. Асинхронные вычисления на основе событийного и потокового взаимодействия процессов, чему и посвящен настоящий раздел, могут рассматриваться как альтернатива использованию систем синхронизации. Понимается это следующим образом. Наступление события подразумевает выполнение условий готовности как логических функций от некоторых других событий. Условия готовности проверяются динамически и разрешают, но не предписывают выполнение соответствующих действий программы. Потоковое управление означает, что действие программы может выполняться, если готовы все необходимые для него операнды, т.е. условие готовности неявно подразумевается. Именно в этом смысле событийно-потоковое управление является альтернативой управлению процессами на основе явных средств синхронизации. Далее будет также показано, каким образом модель обмена сообщениями согласуется с реализацией общей распределенной памяти. Учитывая вышерассмотренные таксономические признаки, можно сформулировать следующее общее описание свойств, которыми должны обладать модели распределенной обработки в масштабируемых системах: поддержка недетерминизма неограниченного числа динамически порождаемых процессов, взаимодействующих посредством асинхронной посылки сообщений.
Событийное описание взаимодействующих процессов. Пусть 
– необязательно конечное множество состояний процесса, а 
– множество тегов (меток). Состояние может трактоваться как выполнение некоторого оператора программы, а тег как метка оператора. На множестве задан нестрогий порядок 
(рефлексивное, транзитивное и антисимметричное бинарное отношение). Будем считать множество тегов частично упорядоченным, что наиболее адекватно описанию распределенных систем с асинхронными процессами. В системах с так называемым "единым временем" – упорядоченное множество, в котором каждый тег – метка времени.
Событие определим как пару 
, где 
, 
. С событием может ассоциироваться срабатывание помеченного оператора, формирование операндов и т.д.
Обозначим через 
квазипорядок на множестве 
событий. Это рефлексивное и транзитивное отношение, представляющее множество причинно-следственных связей (переходов) между событиями. Если 
, то существует переход от события 
к событию 
, или наступление события 
влечет за собой наступление события 
.
Процессом 
будем называть частично упорядоченное множество 
. Два перехода и 
, где 
, называются сопряженными.
История 
– это последовательность событий, соответствующих сопряженным переходам процесса .
Здесь необходимо сделать небольшое отступление и дать соответствующие пояснения. Дело в том, что различные формы понятия "история" давно и широко используются в теории и практике программирования. Если между действиями программы устанавливаются связи логические, по управлению, то говорят об операционной или операционно-логической истории. Часто ее представляют графом, дуги которого соответствуют передаче управления между операторами, а вершины обозначают срабатывание операторов. Тогда операционная истории программы – путь от начальной вершины к конечной. Иногда используют понятие протокола выполнения программы, связывая с меткой оператора или меткой соответствующей вершины стандартной (операторной) схемы состояние ее памяти, т.е. значения переменных. В операционных историях учитывается срабатывание и преобразователей (операторов присваивания), и распознавателей (альтернативных операторов). Когда принимаются во внимание лишь преобразователи, а также информационные связи между ними, то соответствующая модель называется историей реализации программы. Ее можно представить ориентированным бесконтурным графом, являющимся подграфом информационного графа программы. Вершины обозначают срабатывание операторов-преобразователей, дуги – передачу информации. Нужно заметить, история реализации в общем случае, в отличие от операционной истории, не является единственным путем между некоторыми выделенными вершинами. Когда мы говорим об истории процесса, то имеем в виду слово, т.е. последовательность символов, в алфавите событий. Природа связей между событиями может конкретизироваться в зависимости от решаемой задачи. В частности, если событие – это срабатывание того или иного оператора, то наступление этого события может быть вызвано передачей управления или информации. В графическом представлении история процесса – ориентированный бесконтурный граф, вершины которого соответствуют событиям, а дуги – непосредственным переходам между событиями. При этом, квазипорядок порождает на множестве событий отношение эквивалентности 
, разбивающее процесс на непересекающиеся истории семейства 
. Смысл обозначения 
заключается в переходе от события к событию с историей , которая может интерпретироваться как "имя" перехода.
Рассмотрим следующий пример. Пусть необходимо вычислить квадратный корень из неотрицательного числа А, используя метод Ньютона. Ниже приведена соответствующая программа на языке Fortran:
1 S=A
2 T=(S+A/S)*0.5
3 IF(ABS((T-S)/T).LE.0.1)6
4 S=T
5 GO TO 6
6 T=S
Операторы с метками 1, 2, 4, 6 являются преобразователями, а операторы с метками 3 и 5 – распознавателями. Вычисление производится с относительной погрешностью, не превышающей 0.1, требуемое условие завершения счета проверяется при выполнении оператора с меткой 3. Со срабатыванием каждого из операторов свяжем событие, обозначаемое меткой 1, ..., 6. В основу выполнения перехода между событиями в одном случае положим связи по управлению, в другом – информационные связи. Соответствующие истории процесса будем называть операционной и информационной. На рис. 2.1 показаны операционные истории процесса вычисления квадратного корня из А для разных исходных данных: А=1 (см. рис. 2.1, а) и А=2 (см. рис. 2.1, б). В одном случае программа останавливается с результатом Т=1, в другом – Т=1.5.
а)
б)
Рис. 2.1. Операционные истории процесса
На рис. 2.2 представлены информационные истории процесса вычисления для А=1 (см. рис. 2.2, а) и А=2 (см. рис. 2.2, б).
а)
б)
Рис. 2.2. Информационные истории процесса
Как видно из рис. 2.1 и рис. 2.2, для двух разных значений исходного числа А процесс вычислений представлен двумя различными множествами непересекающихся историй (классами эквивалентности). Для операционных историй отношение переходов строится на передаче управления, для информационных историй переходы между событиями обуславливаются передачей данных.
Таким образом, истории процессов представляют собой некоторые "срезы" поведения программы для разных входных данных. Какую из форм представления истории использовать, как уже говорилось, зависит от преследуемых целей. Так, например, для распараллеливания программы в духе парадигмы SPMD, для распределения задач по процессорам, наибольший интерес представляет история реализации программы или информационная история ее процессов. Когда же причинно-следственные связи между событиями на уровне переходов установлены, то от природы этих связей (по управлению или по данным) можно уже абстрагироваться. В этом и состоит главное различие между историей реализации программы, иногда еще называемой графом алгоритма, операционной историей программы и историями процесса программы, несмотря на имеющееся сходство между этими понятиями. Суть этого различия заключается в том, что отношения передачи управления и информации не являются транзитивными отношениями. Этим отношениям соответствуют непосредственные переходы между событиями, например, на рис. 2.1, а это переходы 1®2, 2®3, 3®6. Отношение переходов является транзитивным, т.е. из того, что выполнимы переходы 1®2, 2®3, следует, что выполнимым является переход 1®3 с историей 123. При этом переход однозначно характеризуется своей историей, в частности, переход 1®6 на рис. 2.1, б имеет "имя" 12345236. На рис. 2.2 показаны два различных перехода 1®2, идентифицируемых "именами" 12 (см. рис. 2.2, а) и 1242 (см. рис. 2.2, б). Именно свойство транзитивности переходов, как будет показано в п. 2.2, играет решающую роль в обеспечении однозначности вычислений в условиях, когда для одних и тех же входных данных возможны разные истории процессов. Далее мы будем использовать понятие истории, связывая с ним переходы между событиями, процессы вычислений, т.е. выполнение программы, всегда помня о транзитивности отношения переходов.
Пусть 
, 
,..., 
– отдельные процессы, где 
– соответствующие множества событий, а 
– отношения квазипорядка на . Композиция процессов программы – это такой процесс 
, что 
и 
, где 
– класс эквивалентности в 
. Это означает, что в композиции 
выполнимы переходы с одним и тем же "именем" , представляющим собой историю выполнения программы из 
-наборов событий.
С помощью понятий события и перехода можно формально представить причинно-следственные связи между процессами. Процессы 
, 
, которым соответствуют множества 
, 
событий, назовем взаимодействующими, если на множестве 
задано отношение переходов, причем 
(либо 
), 
, 
(либо 
), где 
– теги событий 
. Если теги 
и 
совпадают, то события 
и 
являются синхронизированными. Равенство 
формально представляет взаимодействие процессов в синхронных каналах, например, механизм рандеву процессов , в моделях CSP и CCS. При этом события процессов , , не связанные с рандеву, частично упорядочены в соответствующих множествах , . В асинхронных каналах с неблокирующим обменом взаимодействие процессов , представляется переходом (либо ), причем 
(либо 
).
В системах с "единым временем" процесс можно определить как функцию 
из в , измеримую относительно , задав на множестве допустимых процессов операции последовательной и параллельной композиции. Пусть 
– длительность процесса . Последовательная композиция процессов 
представляет собой такой процесс 
, 
, что
Отношение порядка на множестве моментов времени естественным образом распространяется на множество процессов: 
, причем 
, т.е. начало любого допустимого процесса 
является допустимым.
Параллельной композицией процессов 
одинаковой длительности называется процесс 
такой, что
Обобщенная параллельная композиция 
процессов разной длительности определяется следующим образом. Положим, 
. Тогда
либо
На рис. 2.3 приведены примеры композиции процессов в "едином времени": 
, 
, 
, 
, 
, 
, 
. Рассмотренные операции "временной" композиции представляют, по сути, синхронизацию событий, соответствующих началу и завершению процессов. При этом лишь последовательная композиция явно отражает причинно-следственную связь между процессами. Например, наступление события 
влечет наступление событий 
и 
(см. рис. 2.3), причем все три события синхронизированы во времени. Однако при этом не ясно, существует ли причинная связь между событиями 
и 
, можно лишь утверждать, что они синхронизированы. Более того, положим, результат процесса 
порождает процесс 
путем посылки сообщения. Рассмотренные операции "временной" композиции этого взаимодействия не охватывают. Тем не менее его легко представить с помощью понятия перехода между событиями: 
.
Рис. 2.3. Примеры композиции процессов в "едином времени"
Отношение переходов необходимо отличать от отношения 
предшествования событий. Так, 
. Отношение предшествования так же, как и отношение переходов, частично упорядочивает множество событий. Однако запись 
не означает, что наступление 
влечет за собой наступление 
. Например, на рис. 2.3 процессы 
и 
не связаны операцией композиции, но при этом для событий, соответствующих завершению и началу справедливо: 
. С другой стороны, 
и соответствующие события, как сказано выше, могут быть связаны переходом. С помощью отношения предшествования событий можно формально описать совместное исполнение процессов над общей памятью в принятой модели согласованности (см. п. 1.2 раздела 1).
Асинхронный обмен сообщениями и связанные с ним проблемы. Сначала договоримся, что мы будем понимать под сообщением. Атомарное, неделимое значение данных назовем токеном. В зависимости от требований, предъявляемых к модели обработки, токен может быть словом, кэш-строкой, страницей, пакетом и т.д. Сообщение – структурированная совокупность токенов и, в общем случае, это – набор, каждый из компонентов которого, в свою очередь, является вектором связанных токенов. Асинхронная передача сообщения требует его сохранения в буфере. В общем случае процессы могут иметь как входные, так и выходные буферы. Однако с позиций анализа однозначности и отсутствия блокировок вычислений соответствующие модели являются семантически эквивалентными. Различие между ними, как будет показано ниже, проявляется при "надстройке" над той или иной моделью согласованности памяти в DSM-архитектурах.
Будем считать, что с каждым процессом связано 
входных буферов, где – число компонентов входного сообщения 
. Число токенов в компонентах 
будем называть шириной соответствующего буфера. Глубина буфера (число входных сообщений) в общем случае может быть и не ограничена. Каждому входному сообщению 
соответствует выходное сообщение 
, где 
– число компонентов, или число выходных буферов процесса. Будем полагать, как только сформированы токен либо компонент выходного сообщения процесса-производителя, они сразу же пересылаются в буфер процесса-потребителя. Доступ к любому буферу сразу нескольких производителей исключается. Чтение из пустых буферов блокируется. Любой из процессов инициируется после формирования входного сообщения . При этом наступает одно из начальных событий подмножества 
. Токен в 
ассоциируется с одним из особых событий подмножества 
. После окончания формирования выходного сообщения наступает заключительное событие из 
.
Подобный механизм пересылки сообщений аналогичен энергичной модели свободной согласованности памяти (ERC). Токены выходного сообщения пересылаются во входные буферы процессов-потребителей вне зависимости от того, когда они будут востребованы (аналог передачи модифицированных данных при выполнении операции release). При наличии у процесса, помимо входных, выходных буферов (по числу компонентов выходного сообщения), может быть реализован механизм обмена, эквивалентный ленивой модели свободной согласованности (LRC). При этом токены выходного сообщения пересылаются при обращении к соответствующим выходным буферам процесса-производителя со стороны процессов-потребителей (аналог передачи модифицированных данных при выполнении операции acquire).
О п р е д е л е н и е 2.1. Процесс является детерминированным, если любому начальному событию 
соответствует не более одного заключительного события 
, т.е. определено частичное отображение из 
в 
.
О п р е д е л е н и е 2.2. Процесс является недетерминированным, если начальному событию может соответствовать некоторое подмножество множества 
особых событий, т.е. определено частичное отображение из в 
.
О п р е д е л е н и е 2.3. Пусть 
и 
– множества входных и выходных сообщений процесса . Процесс является однозначным, если существует отображение из в .
Два однозначных процесса функционально эквивалентны, если оба они реализуют одно и то же отображение из в .
Очевидно, что в соответствии с определениями 2.1, 2.3, если существует переход 
, то детерминированный процесс является однозначным. Согласно определениям 2.2, 2.3 однозначный процесс может быть и недетерминированным: токены выходного сообщения могут появляться в произвольной последовательности и любое из особых событий может стать заключительным. Понятно, что если отдельные процессы композиции являются недетерминированными, то и композиция в целом также недетерминирована.
Итак, недетерминизм вычислительного процесса означает, что любой паре, состоящей из входного и выходного сообщений, может соответствовать более одной истории выполнения программы. Недетерминизм процессов обуславливает различные последовательности формирования компонентов сообщения. Тем самым обеспечивается динамический механизм порождения процессов по готовности входных данных, а число процессов, связанное с выполнением конкретной программы, в общем случае не ограничивается. Основные вопросы, которые при этом возникают, заключаются в следующем.
Вопрос первый: при каких условиях результат вычислений является однозначным?
Далее, "внешнее" описание поведения композиции процессов в терминах сообщений определяет так называемую денотационную семантику модели. К понятию денотационной семантики обычно прибегают в теории функционального программирования. При этом точно специфицируется, что является величиной любого исходного выражения, а выполнение функциональной программы представляется как вычисление математических функций. Денотационная семантика определяет отображение, которое связывает с каждым синтаксически корректным выражением определенную величину, т.е. выражения, по сути, обозначают (denote) некоторые величины. Нужно заметить, что идеи функционального программирования могут использоваться и для организации параллельных вычислений так, например, как это реализуется в Т-системе. Говоря о денотационной семантике, мы подразумеваем существование некоторого отображения 
, сопоставляющего входному сообщению процесса определенное выходное сообщение.
Учет недетерминизма процессов, т.е. "внутреннее" представление поведения на уровне событий, вводит операционную семантику. Операционная семантика предписывает, как выполняется программа (вычисляются выражения) в терминах переходов между выделенными состояниями или событиями. Таким образом, исполнение программы представляет собой некоторую последовательность действий, связанных отношением переходов. Допустим, мы имеем некоторый язык программирования, частью определения свойств которого является денотационная семантика. Мы хотим на этом языке писать корректные программы, выполнение которых описывается операционной семантикой языка. При этом возникает проблема, относящаяся к числу фундаментальных в теоретическом программировании. Суть ее заключается в следующем: согласованы ли, т.е. соответствуют ли одна другой, операционная и денотационная семантики языка. Иногда говорят об их эквивалентности.
Поэтому вполне естественным является вопрос второй: согласованы ли однозначность вычислений (денотационная семантика) и недетерминизм модели (операционная семантика)? Поиску ответов на эти два вышесформулированных вопроса и посвящен следующий параграф.
Однозначность и семантика вычислений в модели обмена сообщениями
Достаточное условие однозначности результата вычислений. Переход между событиями процесса однозначно идентифицируется своим "именем" – историей. При этом еще раз подчеркнем, что отношение переходов, в отличие от отношений управления и информационной связи, является транзитивным. Поэтому на отношения переходов формально распространяются свойства транзитивных бинарных отношений. В частности, переход с историей 
является транзитивным относительно перехода с историей 
, если имеет место
, 
и 
, 
.
Переходы с историями , будем называть взаимно транзитивными, если каждый из них транзитивен относительно другого. Взаимная транзитивность переходов содержательно может быть интерпретирована следующим образом: любой из допустимых процессов программы может быть началом или окончанием другого допустимого процесса.
Для того чтобы недетерминированный процесс 
был однозначным (см. определение 2.3), достаточно, чтобы любой из переходов, связанный с начальным событием , приводил к одному и тому же подмножеству множества особых событий, соответствующих определенному выходному сообщению. При этом вполне возможно, что паре, состоящей из входного и выходного сообщений, соответствует более одной истории выполнения программы в силу недетерминированного характера поведения ее процессов. Обозначим через 
объединение историй в 
. Отношение переходов с историями из – это рефлексивно-транзитивное отношение, совпадающее со своим транзитивным замыканием.
Выберем произвольно подмножества 
, 
. Положим, имеют место переходы 
, где 
, а 
, где 
– заключительное событие, после наступления которого никакие переходы не выполнимы. Тогда в силу взаимной транзитивности переходов с историями из и 
получаем, что 
и 
. Теперь рассмотрим переходы 
, где 
, а 
, где 
– заключительное событие. При этом опять-таки 
и 
. В силу того, что процесс 
недетерминирован, в общем случае 
, но 
, где 
(см. определение 2.2). Поскольку подмножества историй , выбирались совершенно произвольно, то любой переход, связанный с событием 
, приводит в одно и то же подмножество . Иллюстрируется это следующими диаграммами:
Для того чтобы детерминированный процесс 
был однозначным, достаточно, чтобы любой переход из начального события приводил к одному и тому же заключительному событию (см. определение 2.1). Обозначим через 
объединение историй 
. Выберем произвольно два подмножества историй , 
. Тогда имеет место следующая коммутативная диаграмма:
Действительно, 
. Таким образом, доказана следующая
Т е о р е м а 2.1. Пусть переходы процесса взаимно транзитивны. Тогда – однозначный вычислительный процесс.
Следовательно, взаимная транзитивность переходов является достаточным условием однозначности результата вычислений даже если процесс является недетерминированным, т.е. возможны различные истории выполнения программы на одних и тех же исходных данных.
Взаимная транзитивность переходов детерминированного, в соответствии с определением 2.1, процесса влечет наличие у него свойства так называемой конфлюэнтности – аналога свойства Черча – Россера в смысле, определенном Р. Келлером.
Теорема Черча – Россера относится к числу фундаментальных положений в лямбда-исчислении, разделе математической логики, на котором основаны многие теоретические результаты в области языков функционального программирования. По сути, лямбда-исчисление представляет собой средство для описания свойств математических ("чистых") функций и их обработки с помощью специальных правил. Лямбда-выражения преобразуются, "упрощаются" на основе процесса, называемого редукцией и приводящего к нормальной форме выражения, когда нельзя применить никакое правило редукции. Теорема Черча – Россера утверждает: если выражение может быть приведено двумя различными способами к двум нормальным формам, то эти нормальные формы являются алфавитно-эквивалентными, т.е. эквивалентными с точностью до обозначения переменных. Отсюда следует единственность нормальной формы, а также идентичность результатов вычислений при любом порядке редукций.
Келлер построил абстрактную модель асинхронных параллельных вычислений, которую он назвал именованной системой переходов. Это – тройка, содержащая множество состояний, бинарное отношение на этом множестве (множество переходов) и множество "имен" переходов (слов некоторого алфавита). Именованная система переходов описывается такими свойствами, как детерминизм, коммутативность и устойчивость вычислений. Детерминизм означает, что не существует более одного перехода с одним и тем же "именем" из некоторого заданного состояния. Под коммутативностью понимается следующее. Пусть из заданного начального состояния выполнимы два перехода такие, что их "имена" образуются конкатенацией (приписыванием) двух составляющих слов в разных последовательностях. Тогда существует, по крайней мере, одно общее заключительное состояние, в которое ведут оба перехода из заданного начального состояния. Устойчивость вычислений трактуется так: осуществление перехода с "именем" не может сделать невозможным переход с "именем" , если последний также выполним. Иными словами, условие "переход с "именем" возможен" имеет место (сохраняет устойчивость) до тех пор, пока не начнется его выполнение, причем ему предшествует переход с "именем" . Это свойство можно сформулировать и так: окончание любого допустимого процесса является допустимым.
Если именованная система переходов обладает свойствами детерминизма, коммутативности и устойчивости, то параллельные асинхронные вычисления, описываемые такой моделью, являются локально конфлюэнтными. Это свойство может быть описано таким образом. Пусть два промежуточных состояния достижимы из некоторого начального состояния с помощью непосредственных, атомарных переходов. Тогда существует заключительное состояние, достижимое из обоих промежуточных путем непосредственных переходов. Непосредственные переходы могут быть элементами составных, более сложных переходов между состояниями. Из локальной конфлюэнтности вычислений вытекает конфлюэнтность глобальная, когда достижимость промежуточных и заключительного состояний из некоторого начального подразумевает конечные последовательности непосредственных переходов. Заметим, что в отличие от свойств детерминизма, коммутативности и устойчивости, понятия локальной и глобальной конфлюэнтности определяются независимо от "имен" переходов. Конфлюэнтность аналогична свойству Черча – Россера, поскольку означает, что окончательный результат вычислений не зависит от способа (последовательности) промежуточных вычислений.
Теперь посмотрим, действительно ли из взаимной транзитивности переходов детерминированного процесса следует его конфлюэнтность. Имеют место следующие свойства для переходов между событиями:
а) детерминизм, или
, 
(здесь 
– класс эквивалентности в 
);
б) коммутативность, или
, 
, 
,
где 
обозначает выполнимость переходов, связанных с событием , а 
, 
– конкатенацию "имен" переходов;
в) устойчивость, или
, 
, 
.
Отсюда следует локальная конфлюэнтность, т.е. если обозначает непосредственный переход между событиями 
, то 
, 
, 
, 
. Следовательно, имеет место и свойство конфлюэнтности, или 
, 
, 
, где * обозначает конечную последовательность событий.
Таким образом, понятие взаимной транзитивности переходов детерминированного процесса является не менее общим, чем совокупность вышерассмотренных условий а), б), в). Что же касается недетерминированного процесса, то взаимной транзитивности, согласно теореме 2.1, достаточно для обеспечения однозначности результата вычислений. Очевидно также, что недетерминированная композиция однозначных процессов является однозначной. Итак, получен ответ на первый из поставленных в п. 2.1 вопросов.
Операционная семантика вычислений. Формализуем операционную семантику рассматриваемой модели вычислений с помощью алгебры событий.
История 
процесса или программы, представляющая собой слово в алфавите , полностью описывает последовательность сопряженных переходов между событиями множества . Число событий (символов) в слове будем называть длиной истории и обозначать ее 
. На мощность множества никаких ограничений не накладывается, а длина истории не обязательно конечна. Последнее предположение означает, во-первых, возможность протекания процессов не обязательно конечной длительности, а во-вторых, отсутствие ограничений на число динамически порождаемых процессов при выполнении программы. Слово может быть и пустым, т.е. не содержать ни одного символа. Будем говорить, что ему соответствует пустое событие (процесс нулевой длительности), которое обозначим через 
.
Рассмотрим класс 
, включающий в себя следующие события.
1. Объединение 
конечной или бесконечной последовательности событий 
, представляющее собой событие, которое состоит в наступлении, по крайней мере, одного из событий
2. Совмещение 
двух событий 
и , которое является событием, состоящим из наступления и , и .
3. Дополнение ù события , т.е. событие, заключающееся в наступлении любого другого события класса , но не события .
4. Достоверное событие 
, т.е. осуществление хотя бы одного из событий класса .
5. Пустое событие , которое состоит в том, что не наступает ни одного из событий класса .
Нетрудно заметить, что приведенное выше определение формально ничем не отличается от определений алгебры множеств или алгебры событий (исходов идеализированных наблюдений), принятых в вероятностных моделях. Подчеркнем лишь то, что совмещение событий вовсе не означает их синхронизации, т.е. совпадения тегов 
. Далее, – дистрибутивная решетка с дополнением или, иными словами, булева алгебра с операциями объединения и совмещения событий, которая обладает нижеперечисленными свойствами.
Для 
имеет место:
1) замкнутость : 
;
2) коммутативность: 
, 
;
3) ассоциативность: 
, 
;
4) дистрибутивность: 
,
;
5) 
, 
, 
, 
;
6) 
, 
.
При этом операции объединения и совмещения являются идемпотентными ( 
) и выполняются свойство совместимости ( 
), законы двойного отрицания, поглощения и де Моргана. Более того, булева алгебра событий является вполне аддитивной, поскольку любое бесконечное объединение событий есть элемент .
Т е о р е м а 2.2. Класс событий есть алгебра меры 
, где – длина истории выполнения программы на множестве 
событий.
Д о к а з а т е л ь с т в о. Пусть 
– множество событий 
-го процесса, а 
– семейство событий, соответствующее выполнению программы. Напомним, что отношение переходов (квазипорядок на ) порождает отношение 
эквивалентности. При этом процесс 
представляется в виде семейства 
непересекающихся множеств переходов (историй). Значит, – измеримое множество, для которого лебеговой мерой 
является суммарная длина 
историй переходов между событиями. При этом 
, а 
. Множество событий программы – это 
, причем – последовательность попарно непересекающихся измеримых множеств, для которой выполняется свойство счетной аддитивности, или 
-аддитивности: 
, 
, 
, 
. При этом элементы и 
– суть объединение и совмещение событий соответственно в классе . Таким образом, есть -алгебра с единицей , а функция 
является -аддитивной, что и требовалось доказать.
При доказательстве теоремы 2.2 никаких специальных предположений ни о конечном числе процессов, ни о конечной длине истории выполнения программы (соответственно, завершении процессов в течение некоторого конечного интервала времени) не делалось. Разумеется, результат, устанавливаемый теоремой 2.2, распространяется и на конечное (фиксированное) число процессов конечной длительности и будет нам полезен в следующем разделе данного параграфа.
Инварианты в поведении программ. Масштабируемость аппаратных средств, а также переносимость и масштабируемость параллельных программ являются тесно взаимосвязанными проблемами, от решения которых зависит эффективность параллельных вычислений. Функционально эквивалентные (выполняющие одинаковые вычисления) программы с неодинаковой степенью параллелизма, естественно, характеризуются различным временем выполнения на соответствующих платформах. При этом практически полезным, например, с точки зрения удобства отладки, было бы наличие у программ некоторых общих свойств, инвариантных относительно реализации. Так, последовательная программа, отлаживаемая на инструментальной однопроцессорной системе, может быть "превращена" в параллельную для целевой системы с помощью расстановки в определенных местах текста директив стандарта OpenMP. С другой стороны, параллельная OpenMP-программа может выполняться и на однопроцессорной платформе. При этом "последовательный" компилятор попросту проигнорирует, не заметит комментарии OpenMP, такие как !$OMP для языка Fortran или "#pragma omp" для языка С. Что же общего, помимо функциональной эквивалентности, есть в действиях (поведении) последовательной и параллельной программ либо параллельных программ, выполняемых на различных платформах?
Представим некоторую программу 
моделью (частным случаем алгебраической структуры) вида 
, где 
– множество всех допустимых историй выполнения программы, а 
представляет операцию конкатенации слов, соответствующих историям в алфавите событий программы. Формально – полугруппа с единицей (моноид), где – операция полугруппового умножения, а единица – это пустое слово, соответствующее пустому событию (этот же символ будем использовать и для пустого слова).
Рассмотрим две функционально эквивалентные программы 
, 
, реализуемые соответственно на инструментальной и целевой системах и представленные моделями 
, 
с историями на множествах событий 
, 
. Будем говорить, что программа воспроизводит поведение программы , если существует отображение 
: 
такое, что
(2.1)
,
.
Отображение (2.1) будем называть динамическим гомоморфизмом (подобием поведений) программ , , смысл которого заключается в том, что для каждого события в и истории в 
существуют соответствующие "аналоги" в и 
. Выражение (2.1) естественным образом продолжается до отображения вида:
. (2.2)
Соотношения (2.1), (2.2) означают, что образ любого допустимого процесса программы является допустимым процессом в программе . Обозначим число исполняемых операторов или число процессов в конкретной реализации программы через 
. Отображение (2.2) по индукции продолжим до следующего отображения:
, (2.3)
где 
.
При этом с учетом (2.1) 
. В соответствии с теоремой 2.2 и соотношением (2.3) для суммарной длины историй 
процессов инструментальной программы справедливо очевидное соотношение:
. (2.4)
Согласно (2.4) динамической гомоморфизм (2.1) сохраняет суммарную длину историй процессов программы в любой из реализаций при отображении ее на целевую систему. В этом смысле суммарная длина историй инвариантна по отношению к способу реализации целевой программы , например, степени ее параллелизма и вида аппаратной платформы, на которой она выполняется. Пусть 
– число процессов или исполняемых операторов программы , соответствующих согласно (2.3) процессам или операторам с историями 
при некоторой реализации программы . Из (2.1)-(2.4) вовсе не следует, что в общем случае суммарная длина историй 
процессов программы в соответствующей реализации совпадает с . Инвариантность предполагает возможность установления соответствия между событиями при выполнении и такого, что любое событие из имеет свой "аналог" в множестве 
событий программы для целевой системы. За отображением динамического гомоморфизма (2.1) стоит знание правил, приемов сопоставления кодов инструментальной и целевой вычислительных систем, что практически далеко не просто. Эти вопросы рассматриваются в разделе 4 данного курса. А сейчас обратимся к примерам интерпретаций динамического гомоморфизма программ и практическому использованию понятия истории.
Возьмем программу на языке Fortran для вычисления числа 
, составленную в соответствии со стандартом OpenMP:
DOUBLE PRECISION W,X,SUM,PI,F,A
F(A)=4.D0/(1.D0+A*A)
W=1.0D0/N
SUM=0.0D0
!$OPM PARALLEL DO PRIVATE(X), SHARED(W)
!$OPM&REDUCTION(+:SUM)
DO I=1,N
X=W*(1-0.5D0)
SUM=SUM+F(X)
ENDDO
PI=W*SUM
PRINT *, 'PI=',PI
STOP
END
Последовательная программа преобразуется в параллельную добавлением в текст двух директив: $OPM PARALLEL DO и $OPM&REDUCTION. Атрибут REDUCTION дает возможность компилятору создавать систему кэширования данных, исключающую их некорректное разделение разными нитями. До упомянутых выше директив программа исполняется нитью-мастером как последовательная. Параллельная область программы порождается с помощью оператора PARALLEL DO. Индекс цикла I является локальной переменной для каждой нити в параллельной области, где I имеет свое уникальное значение. В этой программе N – целочисленный параметр. Выполнение параллельной области заканчивается оператором ENDDO. Далее продолжает работу только нить-мастер. При выполнении этой программы как последовательной, на однопроцессорной платформе, директивы OpenMP просто не будут восприниматься компилятором. Пусть событие представляет собой выполнение оператора. Тогда любое событие последовательной программы имеет свой образ-событие в программе параллельной, что говорит о том, что эти программы связаны отображением динамического гомоморфизма. При этом в параллельной программе "сохраняется" суммарная длина историй процессов последовательной программы с учетом того, что в параллельной области OpenMP-программы выполняется N параллельных нитей.
Рассмотрим еще один пример. Пусть известен объем вычислений, связанный с выполнением каждого оператора последовательной программы на некотором процессоре. Положим, эта программа допускает распараллеливание на SMP-архитектуре, построенной на процессорах, идентичных процессору последовательной платформы. При этом параллельная вычислительная система не ограничивает хода вычислений, т.е. если может выполняться N операторов параллельно, то число процессоров не меньше N, а общая память имеет достаточную емкость. Требуется определить суммарный объем вычислений при выполнении параллельной программы, зная объемы вычислений при выполнении операторов функционально эквивалентной ей последовательной программы.
Положим, некоторая модель, например граф, параллельной программы преобразована в соответствующую модель (граф) последовательной программы так, что не нарушен порядок передачи управления между операторами и для каждого оператора обеспечивается своевременное вычисление операндов. Тогда любому развитию вычислений в модели параллельной программы однозначно соответствует некоторое развитие вычислений в модели последовательной программы. При этом каждому событию (срабатыванию оператора) при последовательном вычислении соответствует событие при параллельном счете. Это означает, что и в той и другой модели каждый оператор либо не выполняется, либо выполняется одинаковое число раз. Положим, что число операторов в обоих моделях одинаково. Это допущение, конечно, нужно принимать с определенной условностью, поскольку системы параллельного программирования вносят в текст последовательной программы некоторую избыточность в виде специальных директив (OpenMP), функций передачи сообщений (MPI), операторов оценки производительности (mpC) и т.д. Но если предположить, что число операторов для выполнения "содержательных" вычислений в обоих программах одинаково, то можно утверждать, что они выполняют и одинаковые суммарные объемы вычислений. Примерно такая цепочка рассуждений приводит к известному факту, состоящему в том, что в некоторых случаях задача определения объема вычислений параллельной программы сводится к определению объема соответствующей ей последовательной программы. История выполнения последовательной программы может быть использована для определения объема вычислений, а динамический гомоморфизм последовательной и параллельной программ, по сути, представляет изоморфизм, т.е. взаимно однозначное соответствие между их действиями.
Согласованность операционной и денотационной семантик вычислений. Теперь рассмотрим вопрос о том, как может быть определена денотационная семантика вычислений в модели обмена сообщениями и как она согласуется с операционной семантикой, выраженной через алгебру событий, в которых совместно протекают процессы.
Пусть 
– множество сообщений процесса, включая пустое сообщение 
, не содержащее данных, а 
– законченный частичный порядок, т.е. множество последовательностей сообщений из , в котором для каждой последовательности 
существует наименьшая верхняя грань 
. Положим, что процесс однозначен, а на функция из в не определена. Тогда существует функция 
, которая непрерывна, если 
. В соответствии с первой теоремой Клини о рекурсии непрерывная функция 
имеет наименьшую неподвижную точку 
, т.е. 
, причем любая последовательность – префикс . Процесс, для которого определена такая функция , назовем непрерывным. Композиция непрерывных процессов (аналог суперпозиции непрерывных функций) также является непрерывным процессом. Итак, "внутренний" недетерминизм однозначных процессов (см. определения 2.2 и 2.3) может не нарушать свойства непрерывности процессов, в отличие от недетерминизма "внешнего". "Внешний" недетерминизм проявляется в том, что последовательность выходных сообщений не определяется однозначно последовательностью входных сообщений. Иными словами, процессы вычислений не является однозначными. Применительно к сетям процессов Кана, например, "внешний" недетерминизм означает, что истории внутренних и выходных каналов сети не полностью определяются историями входных каналов.
Как отмечалось выше, денотационная семантика ("внешнее" описание) определяется в понятиях сообщений, а операционная ("внутреннее" описание) – в понятиях событий. На основе операционной семантики формулируются требования к реализации композиции процессов: для того, чтобы композиция была однозначной, достаточно чтобы переходы процессов были взаимно транзитивными. Если композиция однозначных процессов непрерывна, то ее денотационная семантика – это семантика наименьшей неподвижной точки. Свойство непрерывности процессов вычислений обеспечивает существование конструктивного приема нахождения неподвижной точки программ как наименьшей верхней грани на законченном частичном порядке из входных и выходных сообщений. Монотонность функции на законченном частичном порядке также обеспечивает существование наименьшей неподвижной точки, однако не дает некоторого конструктивного приема для ее нахождения. Часто теорему о неподвижной точке связывают с именами Б. Кнастера и А. Тарского, которые изучали проблему применительно к решеткам, а не законченному частичному порядку. Поэтому иногда и соответствующую семантику называют семантикой Тарского.
Таким образом, если реализация языка программирования допускает "внутренний" недетерминизм процессов, обеспечивая их однозначность и непрерывность, то денотационная семантика, являющаяся частью определения языка, точно специфицирует, что является результатом вычисления. Это – ответ на второй из поставленных в п. 2.1 вопросов.
Итак, мы рассмотрели модель распределенных вычислений, существенным отличием которой от известных моделей является сочетание недетерминизма процессов и асинхронного обмена разнородными сообщениями. Теорема 2.1 обосновывает достаточное условие однозначности вычислений. Операционная семантика вводится на основе алгебры событий, являющейся алгеброй меры – длины истории выполнения программы (см. теорему 2.2). Операционная и детонационная семантика модели согласованы. Рассмотренная модель является весьма гибкой. Не накладывается никаких ограничений на конкретную реализацию процессов: концепция событий допускает как функциональный, на уровне сообщений, так и процедурный, на уровне состояний, подходы. Глубина буферов процессов может быть ограничена. Тогда доминирует смещение модели в сторону аппаратной поддержки обмена сообщениями. Если множество тегов является упорядоченным, а сообщения процессов согласованы так, что глубина буферов всех процессов рассчитана на одно сообщение, то может быть реализовано так называемое событийное (имитационное) моделирование. Подобный подход реализован в языке CSIM, являющемся расширением языка С для имитационного моделирования, когда процессы асинхронно обмениваются сообщениями по принципу "много писателей – много читателей". Таким образом, рассмотренная в этом параграфе модель вычислений применима в широком спектре приложений, связанных с распределенными системами и средами.
Дата добавления: 2021-07-19; просмотров: 144; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!