Смелянский Р.Л. Анализ производительности распределенных микропроцессорных вычислительных систем на основе инварианта поведения программ. / Дисс. на соискание ученой степени доктора физико-математических наук. М.:МГУ, 1990. Глава, посвященная моделированию распределенных систем.

Глава 3. Модель функционирования распределенных вычислительных систем

3.1. Введение

Цель этой главы - построение математической модели динамики функционирования распределенных вычислительных систем. Под этими словами мы понимаем разработку согласованной системы математических понятий и взаимосвязей между ними, адекватно описывающих характерные особенности функционирования распределенных вычислительных систем (РВС). На качественном уровне эти особенности были рассмотрены в предыдущей главе, здесь мы их лишь перечислим:

Ни одна из известных на сегодня теорий Ч.Хоара[2], Р.Милнера[3], Г.Дегано и У.Монтанари[4], М.Найвта[5], Капитоновой Ю.В. и Летичевского А.А. [6], Миренкова Н.Н. [15] не охватывают все эти особенности. Упомянутые теории создавались прежде всего с целью построения математического аппарата для спецификации поведения программ и исследований их эквивалентных преобразований. В них либо не разделяют программу и физическую среду ее исполнения, либо физическая среда, а, следовательно, и время, как метрическая величина, отсутствует. Во всех указанных работах используется только одна семантика параллелизма - чередование. Наша цель - количественный и алгоритмический анализы распределенных вычислительных систем (подробно об этих видах анализа см.[7]). Предлагаемая ниже модель охватывает не только поведение программ, но и характеристики аппаратуры и того программного окружения, которое обеспечивает выполнение программы: она описывает влияние аппаратуры на динамику взаимодействия программ: содержит множественное время как количественную сущность: отражает иерархичность и структурность организации вычислительных систем.

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

3.2. Основные представления

Динамику функционирования распределенной вычислительной системы определяет взаимодействие процессов прикладной программы с логической средой и исполнителем. Прообразом последнего является физическая среда. Схематично наше представление об этом взаимодействии можно описать так. Каждый последовательный процесс определяет логическую последовательность действий. Часть этих действий есть обращение к динамическим логическим ресурсам, а часть - к статическим. (Эти виды логических ресурсов, равно как и само понятие логического ресурса были введены в разделе 2.2.3.) Обращения к динамическим логическим ресурсам сопровождаются передачей сообщений надлежащего типа.

Сообщение суть совокупность параметров обращения. Тип сообщения - класс эквивалентности на множестве допустимых сообщений. Каждый динамический ресурс для нас есть процесс с известным поведением.

Передачу и управления и сообщения осуществляет нечто называемое последовательный наблюдатель. Это внешняя для процессов и исполнителя сущность. По отношению к нему мы определяем "степень прозрачности" процесса, эквивалентность процессов, типов сообщения и т.п.. Передача управления от процесса А к процессу В означает, что ресурсы исполнителя и логической среды начинает использовать процесс В. Исполнитель выполняет внутренние действия (те, что образуют статический логический ресурс), определенные процессом. Эти действия невидимы для наблюдателя. На временной оси исполнителя отмечаются события, соответствующие действиям процесса В. "Предельная" степень прозрачности процесса для наблюдателя - атомарные процессы, то есть те неделимые, элементарные действия, которые может выполнять исполнитель (прообраз атомарного процесса - команда процессора). Результатом выполнения этих действий с точки зрения наблюдателя является сообщение определенного типа и имя процесса (динамического логического ресурса), которому наблюдатель должен передать управление и это сообщение.

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

Исполнители делятся на распределенные и последовательные. Последовательный исполнитель в одно и то же время может выполнять действия, запрошенные только одним последовательным процессом. Один последовательный исполнитель может в режиме разделения времени обслуживать несколько последовательных процессов.

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

На одном исполнителе процессы могут выполняться как последовательно, так и параллельно. Дело в том, что слово "параллельно" часто трактуется в двух смыслах: в одно и тоже время, совместно: либо в смысле - независимо. В последнем случае неважно развиваются ли процессы в одно и то же время или нет.

Везде далее мы будем предполагать

  1. Каждый последовательный исполнитель связан с определенным набором других последовательных исполнителей. Их набор ограничен, фиксирован и не изменяется в ходе работы прикладной программы.

  2. Каждый последовательный процесс программы связан с определенными другими процессами. Их набор также фиксирован и не меняется со временем.

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

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

3.3. Поведение

3.3.1. Понятие шага

Обозначим:

Mmsg - конечное множество типов сообщений;

Mps- конечное множество процессов наблюдаемых в системе, причем Mps = Mle P и Mle P = Æ , где

Mle - множество процессов логической среды;

P - множество процессов программы.

Поведение процесса будем описывать как структуру над множеством шагов. Шаг s определим как выражение вида a -q ® b p,

где a ,b Î Mmsg; pÎ Mps,qÎ Q* .. Он состоит из:

в о з д е й с т в и я - получения сообщения типа a и управления от другого процесса;

р е а к ц и и - посылки сообщения типа b и передачи управления процессу p:

т е л а - последовательности внутренних действий

q1 ,q2 ,...,qn, множество которых обозначим через Q;

Q* - конечное замыкание Q, т.е. множество цепочек символов qiÎ Q конечной длины.

Итак, шаг есть элемент множества

S = Mmsg ´ Q* ´ (Mmsg ´ Mps),

где ´ - декартово произведение.

В дальнейшем будем использовать следующие обозначения: S(P)× (S(pi)) - множество шагов программы P(процесса pi); infl(s), rpl(s), bod(s) - воздействие, реакция, внутренниe действия шага s соответственно.

Тело шага - величина, позволяющая определить время выполнения внутренних действий шага на конкретном исполнителе. Для этого зададим отображение тела на множество векторов трудоемкости (см. раздел 2.3.5) через однозначную вектор-функцию, которую назовем функцией трудоемкости (подробно о ней см. раздел 2.3.5):

сwm: : Q*→ {(n1 ,n2 ,...,nk)j},

где;(n ,n ,...,nk) - вектор трудоемкости

ni - количество выполнений i-го атомарного процесса исполнителем при реализации тела шага (подробно об атомарных процессах будет сказано в разделе "Исполнитель").

Считаем, что эта функция обладает следующими свойствами:

w(Æ )=(0,...,0) ,

где Æ - отсутствие внутренних действий, и

сwm(q1, q2 ,...,qm )=сwm(qi).

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

vlm(x)=n, где xÎ Mmsg, nÎ N.

Два шага s1 и s2 равны, если infl(s1)=infl(s2) и rpl(s1)=rpl(s2), (мы пока не требуем равенства сложности шагов).

Историей процесса p назовем не пустую конечную последовательность его шагов замкнутую слева, т.е.

если h(p)=s1 ,s2 ,...,sk - история, то

" i: i£ k Þ s1 , s2 ,...,si -история.

Будем обозначать через |h(p)| число шагов в истории h(p) и назовем это число длиной истории h(p).

Две истории h1(p) и h2(p) равны если |h1(p)|=|h2(p)| и

" i: 1£ i£ |h(p)| Þ s1,i = s2,i , где si,j - i-й шаг j-го процесса.

Подысторией ~h(p) назовем любой постфикс истории h(p).

Цепь - это любое подслово слова h(p).

3.3.2. Поведение процесса

Поведением процесса p назовем множество всевозможных историй этого процесса, которое мы будем обозначать bh(p). Исследуем структуру bh(p) с целью его описания. Для этого введем на множестве S (p) - множество шагов процесса и их последовательностей две операции ":" - следования и "+" - альтернативы.

Цепь l=l1 ;l2 есть цепь l такая, что |l|=|l1|+|l2| и l1 - префикс, а l2 - постфикс l, т.е. операция следования есть конкатенация цепей, рассматриваемых как последовательности символов в алфавите S(p). Выражение вида h(p)= h(p1);~h(p2) означает, что процесс p сначала ведет себя в соответствии с историей h(p1), а затем - в соответствии с подысторией ~h(p2). Нетрудно видеть, что ":" ассоциативна, но не коммутативна.

Выражение вида h1(p)+h2(p) описывает поведение процесса p, который может развиваться в соответствии либо с историей h1(p), либо с историей h2(p). Правило выбора конкретной истории эта операция не определяет. Свойства операции "+":

  1. l1 + l2 = l2 + l1 ,
  2. (l1 + l2 ) + l3 = l1 + (l2 + l3 ),
  3. l1 ; (l2 + l3 ) = l1 ; l2 + l1 ; l3 ,

т.е. это коммутативная, ассоциативная и дистрибутивная справа относительно ";" операция.

Везде далее выражение вида l1 +l2 +...+lr будем кратко записывать в виде .

Теорема 1. " p: h(p) представима в виде h(p)=h1(p);~h(p), где h1(p)Î bh(p).

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

Теорема 2. Пусть bh'(p)={hi'(p) | " i: hi'(p)=h0 ;~hi'(p)},

где ~hi'(p)Î ~bh'(p) и ~bh'(p) - множество подысторий историй из bh'(p).

Тогда представима bh'(p)=h0 ;.

Доказательство. Для доказательства этого факта достаточно воспользоваться дистрибутивностью ":" относительно "+", согласно которой

,

но по условию

" i : h0 ; ~hi(p)Î bh¢ i(p).

Обозначим b*h0(p)={h(p)|h(p)=h0; ~h(p), где h(p)Î bh(p)}.

Теорема 3. Для любого фиксированного h0Î bh(p) представление b*h0(p)Î bh(p) в виде

h0 ;.

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

Доказательство. Если предположить существование h"(p)Î b*h0(p), но не представимого в указанном виде, то придем к противоречию.

Действительно,: в этом случае у h"(p) не будет префикса h0 .

 

Следствие. Префикс h'(p) любой истории из bh(p) задает на bh(p) класс эквивалентности

b*h'(p) = {h(p)|h(p)=h'(p);~h(p)}.

Причем для " h'(p),h"(p) из bh(p) таких, что

h'(p)¹ h"(p) следует b*h'(p) b*h"(p) =Æ .

Введем однозначную процедуру построения по bh(p) некоторой структуры. Согласно теореме 3 поведение любого процесса представимо в виде

bh(p)=b*si (p).

Этому выражению сопоставим некоторое число вершин равное числу шагов si , с которых могут начинаться истории процесса p, и вершины · - фиктивная вершина, вводимая в интересах построения и называемая начальной. Соединим · с каждой вершиной si дугой, т.е. дуга (· ,s ) существует если si - префикс хотя бы одной истории из bh(p).

Далее " i: b*si = si

Сопоставим каждому из этих ˜b*sj множество вершин и дуг, по выписанным выше правилам. В качестве начальной вершины возьмем вершину, помеченную соответствующим si, при построении на предыдущем шаге. Если si последний шаг истории, то добавляем к нему дугу вида (si ,J ), где J специальный символ, обозначающий окончание наблюдения истории.

Полученную в результате указанной процедуры структуру обозначим Tbh(p).

Теорема 4. Пусть bh(p) поведение процесса p.

Тогда Tbh(p) - дерево, между множеством путей которого и множеством историй из bh(p) существует взаимно однозначное соответствие.

Доказательство. Наше доказательство построим из двух частей:

  1. сначала докажем, что Tbh(p) - дерево;
  2. затем покажем, что " L:LÎ Tbh(p)Þ $ !h(p)Î bh(p), где L - путь в Tbh(p).

Это и даст справедливость сделанного утверждения.

1. Докажем что Tbh(p) - дерево. Для этого достаточно доказать, что два пути L1 ,L2 Î Tbh(p), с одинаковыми начальной и конечной вершинами, совпадают. Этого достаточно в силу справедливости следующего утверждения [16];

граф T - дерево тогда и только тогда, когда любые L1 и L2 пути в нем, имеющие общие начальную и конечную вершины, совпадают (L1 =L2 ).

Индукцией по длине путей L1 и L2 можно показать, что если на каком-то шаге индукции предположить несовпадение вершин в L1 и L2 , то, согласно выше изложенной процедуре построения, не совпадут их концевые вершины.

2. Взаимная однозначность между Tbh(p) и bh(p) следует из построения Tbh(p) и доказательства свойства (1). Итак, bh(p) представимо в виде дерева, которое впредь будем обозначать Tbh(p):

Tbh(p)=(V,S(p),lp(v),Ebh(p)), где

V - множество вершин;

S(p) - множество шагов процесса p;

lp(v):V ® S(p) функция разметки;

Еbh(p) - множество дуг.

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

Одной из основных особенностей поведения параллельных программ является недетерминизм. Мы выделили два его вида: внутренний и внешний (подробнее см.[1] и раздел 2.2.3). Будем говорить что выражение si + sj описывает внешний недетерминизм, если infl(si)¹ infl(sj), и внутрениий - если infl(si)=infl (sj), но rpl(si)¹ rpl(sj). Это определение недетерминизма позволяет оценить его количественно.

Скажем, что процесс p1 более недетерминирован, чем p2 если их поведения таковы, что: " i:˜ b*s1i Í ˜b*s2i, где s1i Î S(p1 ) и s2i Î S(p2 ).

3.3.3. Поведение программы

Определим поведение программы как множество поведений процессов, ее образующих:

Bh(P) =.

Структура Bh(P) - это лес из деревьев Tbh(p), который мы будем обозначать FBh(P). Множество шагов S(P) в поведении Bh(P) частично упорядоченно. Это отношение отражает взаимодействия между процессами и порядок следования шагов в истории каждого процесса. Рассмотрим это отношение подробнее, поскольку оно описывает причинно-следственные связи на множестве действий программы. От него зависит семантика параллелизма.

Обозначим

RL (p) ={(si , sj)| si , sj Î h(p) & h(p) = h΄(p); si :sj: ~;h(p) }.;

sj назовем причиной, а sj - следствием.

Это отношение определяет причинно-следственные связи на S(p), где pÎ P.

Будем писать sk* si, если (sk , si)Î R*L(p), где R*L(p) - транзитивное замыкание RL(p), т.е. существует множество

и .и s m1 = s k

Теперь распространим отношение RL(p) на случай событий. Событие - это либо воздействие, либо реакция. Обозначать событие будем буквой e с надлежащим индексом. По определению:

eiej Û $ sk : (ei =infl(sk) e × ej =rpl(sk) либо

$ sl : ei Î sk e ej Î sl e (sk ,sl )Î RL(p).

Выражения вида ei =infl(s), ej =rpl(s) означают, что эти события соответствуют воздействию, реакции соответственно.

Для описания взаимодействия между процессами введем вспомогательное отношение на множестве шагов программы

R~(P)={(si,sj )|si Î S(p) & sj Î S(q) &pÎ P&qÎ P Þ infl(sj ). q=rpl(si )}.

Взаимодействие между процессами определим через отношение R f (P):

R f (P)= { (si,sj)} если

  1. $ h(p1), $ h(p2):siÎ h(p1)e sjÎ h(p2)e rpl(si)=p2 . infl(sj);
  2. $ skÎ h(p1), $ sqÎ h(p2): sk* si e (sk ~ sq V sq ~ sk )

e (si ~ sj V sj ~ si) e sj* sq}

т.е. реакция на шаге si в поведении процесса p1 есть обращение к шагу sj в поведении процесса p2 (смысл пункта 2 разъясним чуть позже.).

Если (si,sj) Î R f (P), то этот факт будем записывать в форме si, f sj .

Отношение Rf (P) несимметрично, иррефлексивно.

По аналогии с ранее сделанным, распространим отношение R f (P) на случай событий:

ei f ej Û $ sk , $ sm : (sk , sm )Î R f (P) e ei Î sk e ej Î sm .

Это отношение обозначим Re f (P).

Обозначим R® (P) = Rf (P) È {RL(pi)}piÎ P . Не трудно показать,что это отношение несимметрично, иррефлексивно. Теперь разъясним п. 2 в определении отношения Rf (P); благодаря этому ограничению, отношение R® (P)P) не содержит "зацикливающих" связей вида а) и б) из рисунка 3.1.

рис 3.1

Историей выполнения программы H(P) назовем тройку

H(P)=({h(pi)}piÎ P, {a i }, Rf (P)),

т.е. это совокупность историй процессов - {h(pi)}piÎ P, удовлетворяющих отношению Rf (P);{a i} - начальные воздействия, которые определяют первые шаги в тех процессах, с которых начинается выполнение программы.

3.3.4. Взаимосвязь логической среды и программы

Рассмотрим различия в описаниях поведений процессов логической среды и программы.

  1. В поведении прикладных процессов по аналогии с [2] вместо некоторого шага может быть указано имя прикладного процесса. Это означает, что процесс, начиная с этого места, ведет себя также как тот, чье имя указано. (Так можно описывать процесс с "рекурсивным поведением").

  2. Процессы прикладной программы представлены в поведениях процессов из логической среды с помощью переменных с именами специального вида, которые могут встречаться в реакциях шагов, и которые мы будем обозначать dmi , а их множество Dm. Множество значений dmi - множество S(p) надлежащего p. Реакция, в которой указано dmi означает передачу управления прикладному процессу, сопоставленному этому имени. Соответствие между именами из Dm и процессами из P устанавливает взаимнооднозначное отображение Shd: P ® Dm. Здесь мы предполагаем, что Shd от времени не зависит. Однако, наделяя Shd различными свойствами, например, введя зависимость от времени, можно описывать динамику порождения и уничтожения процессов.

  3. Считаем, что множества Dm и Mle фиксированы. Ясно, что введение Dm ограничивает множество допустимых к рассмотрению программ, а именно: |Dm|³ |P|. Везде далее мы предполагаем, что программы отвечают этому ограничению.

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

{s.pi | sÎ bh(pi)}pi.Î P

Для работы с ней есть две функции put - запомнить и get - выдать значение.

3.3.5. Виды параллелизма и их семантика

Для описания ранее введенных двух видов параллелизма введем две операции композиции процессов: p1 ~p2 - совместно независимое выполнение; p1||p2 - истинно параллельное выполнение. Есть два основных способа описания параллелизма: недетерминированное чередование (interleaving) и частичное упорядочение. Первый часто используется при описании семантики языков программирования, например, CSP [9],CCS [3], COSY [10], семантики описания операторов работы с разделяемыми переменными [11]. Последний чаще используется в теории сетей [12,13].

Для совместного независимого исполнения процессов будем использовать семантику чередования (interleaving). Это означает, что события, определяемые h(p1) и h(p2) образуют цепочку, в которой они не имеют предпочтения в порядке следования между собой. Ограничения на чередование определяет некоторое отношение независимости, задаваемое на S(P). Такая семантика учитывает единство временной оси исполнителя. Это выражается в том, что все события, происходящие на данном исполнителе, собираются в цепочку.

Семантику истинно параллельного выполнения процессов будем описывать отношением частичного порядка на множестве их событий. Запись p1||p2 означает, что цепочка событий, определяемая историей h(p1), появляется между точками взаимодействия отдельно и независимо от цепочки, определяемой историей h(p2). Естественно возникает вопрос о взаимосвязях этих видов описания параллелизма и особенно их эквивалентности, который мы рассмотрим в разделе 3.5.4.

3.4. Исполнитель

3.4.1. Последовательный исполнитель

Определим последовательный исполнитель как:

SEx = < (Mprim,vt(a)), C(e), (Stg(p),N), Cr, F >,

где (Mprim,vt(a)) - набор атомарных процессов;

C(e) - функция времени;

(Stg(p),N) - память;

Cr - носитель;

F - арбитр.

vt(a):Mprim

Ниже дано подробное и строгое определение этих понятий.

Атомарные процессы. Mprim - множество атомарных процессов. Атомарный процесс - это частичное отображение Mmsg ® Mmsg. vt(a)- функция, определяющая время выполнения атомарного процесса a. Она определена на Mprim, с областью значений - целые числа. Целое число обозначает количество так'ов - единиц времени по часам SEx. vt(a) задана в виде вектора, который будем называть вектором технической производительности данного исполнителя).

Основные свойства атомарных процессов таковы:

  1. " ai :$ a :$ !b : aiÎ Mprim & a ,b Î Mmsg Þ a(a )=b .

Для любого aiÎ Mprim определено множество входных типов сообщений и множество сообщений-результатов. Между ними ai определяет однозначное соответствие. Недетерминизма на уровне исполнителя нет.

  1. " ai :$ K: aiÎ Mprim & КÎ N & K>1 Þ vt(ai)<K.

Время выполнения любого aiÎ Mprim конечно, постоянно и равно vt(ai).

  1. Выполнение атомарного процесса не прерываемо, т.е. начавшись, атомарный процесс не может быть приостановлен и будет закончен через vt(ai) так'ов. Иными словами, исполнитель становится не восприимчивым к внешним воздействиям на период выполнения атомарного процесса.

  2. Поведение атомарного процесса ai описывает дерево вида

Напомним, что переменная back представляет имя процесса , инициировавшего этот атомарный процесс. Это означает, что после выполнения атомарный процесс всегда возвращает управление тому процессу, который инициировал его выполнение, если ему на вход поступило сообщение допустимого типа

  1. У атомарного процесса моменты передачи сообщения-результата и момент возврата управления совпадают: если управление передано, то сообщение - доступно.

Свойства функции C(e). Эта функция сопоставляет событию количество так'ов, наступивших к моменту его возникновения на данном исполнителе. Моментом наступления события считается время начала выполнения первого атомарного процесса надлежащего действия. Функция C(e) определена на множестве всех событий в процессах, приписанных данному исполнителю. Область ее значений - множество натуральных чисел.

Будем писать ei *ej,если (ei ,ej ) Î R*L(p),где R*L(p) -транзитивное замыкание RL(p).

Постулируем свойства функции C(e):

П1: " ei,ej:ei,ej Î bh(pm) & ei* ej Þ C(ei )<C(ej ),

т.е. в одном процессе причина наступает всегда раньше следствия.

П2: " ei,ej:ei Î S(pk)&ej Î S(pm) & ei f ej & pk~pm Þ C(ei)<C(ej),

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

Следствия:

  1. Между двумя последовательными событиями одного процесса (между причиной и следствием) всегда проходит хотя бы одна единица времени.

  2. " ei,ej:ei,ej Î S(p) ei*× ej Þ C(ei)<C(ej);

    Любой процесс исполняется последовательно.

  3. " ej : e0,ej Î S(p) & e0 *× ej Þ C(e0)<C(ej);

    Обращение к процессу всегда наступает раньше (по часам данного исполнителя), чем возникнет какое-либо событие в этом процессе.

  4. " ei ,ej : ei Î S(pk) & ej Î S(pm) & pk ⌡ pm Þ C(ei)<C(ej) Ú C(ei)>C(ej);

    Все процессы на одном исполнителе выполняются последовательно.

  5. " ei,ej:(ei,ej)Î R*f (P)&ei Î pk & ej Î pm & pk~pmÞ C(ei)<C(ej),

где R*f (P) - транзитивное замыкание Rf (P). Если два события, связанные причинно-следственной связью, принадлежат разным процессам, исполняемым одним и тем же исполнителем, то причина всегда наступает по часам этого исполнителя раньше следствия.

Теорема 5. C(e) не нарушает отношения причинно-следственности на множестве процессов, исполняемых одним исполнителем:

(ei,ej)Î R® (P) Þ C(ei)<C(ej)

где ei - причина; ej - следствие.

Доказательство. Справедливость этого утверждения следует из того факта, что функия C(e) монотонная. В свою очередь этот факт есть тривиальное следствие п.п.1-5.

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

Расширим область определения функции C(e), а именно обозначим C(t) - количество так'ов наступивших к моменту t. При этом постулируем следующее свойство C(t):

П3: $ r," t," D :r,t,D Î R &0<D <rÞ C(t+r) - C(t)=1& C(t+D )-C(t)=0,

т.е. часы "тикают" с постоянной скоростью r. На практике r флюктуирует. Поэтому ослабим постулат П3:

П3': $ r': $ e :" D :" r: e ,r,r'>0 & 0<D <(r'-e ) & r'-e <r<r'+e Þ

C(t+D )-C(t)=0 e C(t+r)-C(t)=1.

Теперь обеспечить однозначность показаний часов в различных экспериментах мы можем лишь в течении определенного периода наблюдений d t, такого что |[d t/(r-e )]|=|[d t/(r+e )]|, где |[ . . . ]| - взятие целой части. Отсюда, зная r и e , можно вычислить d t, либо, зная необходимый d t, - определить характеристики часов.

Память. Набор (Stg(p),N,R) определяет объем памяти, регистровую и стековую структуру исполнителя:

Stg(p) - это функция, определенная на множестве процессов Mps с областью значений целые числа (т.е. количество единиц памяти, необходимое для хранения процесса p);

N - максимальное количество единиц памяти у данного исполнителя. На данном исполнителе может выполняться такое множество процессов Mps', чтобы

.

В предельном случае N>max{Stg(ai)}, где aiÎ Mprim, т.е. исполнитель способен хранить только одну команду с операндами.

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

Cr - носитель. Понятие носителя является основным средством для описания структуры исполнителя. Носитель последовательного исполнителя (или просто последовательный носитель) будем обозначать SCr. По определению:

SCr = <Ent, s n , Ext, x k >,

где: Ent - множество полюсов, которые будем называть входами;

s n - разметка входов: однозначное отображение [1,n]`→Ent, где [1,n]Ì N;

Ext - множество полюсов, называемых выходами; Ent Ç Ext = Æ .

x k -разметка выходов: однозначное отображение Ext® [1,k], где [1,k]Ì N.

По определению считаем, что SCr1 =SCr2 Û

  1. Ent1 =Ent2 ;

  2. Ext1 =Ext2 ;

  3. s n1 =s n2 ;

  4. x k1 =x k2 .

Полюса exti Î Ext обеспечивают передачу воздействий на процессы, размещенные на других исполнителях. Каждому exti заранее сопоставлен атомарный процесс (обозначим его p_exti ). Длительность срабатывания exti полагаем равной vt(p_exti). С каждым exti связана функция

c i(n): N® {0,1}; c i(n)=1 если nÎ [C(t0),C(t0)+vt(p_exti)],

в противном случае - 0. Здесь C(t0)= C(e*), где e* - воздействие на p_exti .

Назовем ее характеристической. Если c i(n)=1, то будем говорить, что соответствующий выход возбужден. Один ext может быть соединен с несколькими entrj своего либо других исполнителей. Всем этим entrj одновременно будет передано одно и то же сообщение. Время достижения сообщением надлежащего entrj определяют характеристики соответствующей связи. (Способ ее задания будет определен позднее.) Объем и тип сообщения, единовременно передаваемого за одно обращение к exti , определяет атомарный процесс p_exti .

Каждому entr можно сопоставить (способ сопоставления будет уточнен позднее) только один выход своего либо другого исполнителя; и один процесс из Mps, управление которому будет передано, если данный entr возбужден и он выиграл арбитраж. Вход возбужден если c i(n)=1 у выхода, связанного с этим входом.

Арбитр F - однозначный функционал, описывающий арбитраж на входах последовательного исполнителя. Область определения F - C(t) данного исполнителя и множество характеристических функций выходов, связанных с его входами; область значений - имена процессов, сопоставленных входам. По истечении vt(ai),т.е. времени реализации очередного а процесса, на данном исполнителе, F выбирает один из возбужденных в этот момент входов. Если время возбуждения выхода, возбудившего этот вход исполнителя, не истекло раньше, чем завершилось выполнение очередного а процесса. Этот вход и будет определять внешнее воздействие на исполнитель.

3.4.2. Распределенный исполнитель

DEx = < {SExi}, DCr, W > - распределенный исполнитель, где

{SExi} - множество последовательных исполнителей;

DCr - распределенный носитель;

W - поток.

Распределенный носитель DCr - это гиперграф, множество вершин которого образуют подмножества полюсов носителей SCri, входящих в состав SExi , образующих данный DExi:

DCr = < { SCri }, E, s n, x j >,

где {SCri} - множество последовательных носителей, которое обозначим V. По существу, множество V:

V = È {Exti È Enti | Exti Î SCri & Enti Î SCri }.

E - множество дуг, которые мы будем обозначать Arc:

E = { Arcj | Arcj Î V & " j:$ !extÎ Arcj },

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

s n - функция разметки входов DCr: ent - вход в DCr если

$ SCrj : SCrj Î DCr Þ " Arc:ent Ï Arc & entÎ Entj & Entj Î SCrj ;

т.е. это один из входов SCr, не использованных в дугах DCr. Заметим, что теперь мы не требуем однозначности s n , но полагаем, что она имеет обратную функцию, которая однозначна.

Причем:

" i: Ø $ SCr: SCrÎ DCr & s (i)=entk & s (i)=entn & entk , entnÎ SCr ,

т.е. в точках неоднозначности s (i) не может иметь значений в Ent одного итого же SCr.

x j - однозначная функция разметки выходов DCr: extj - выход DCr, если

$ SCrj : extj Î Extj & Extj Î SCrj Þ " Arc: extj Ï Arc ,

т.е. это один из выходов SCr, не использованный в дугах DCr. x j такова, что

" k: Ø $ i: i¹ k e x j (extk)= x j (exti) e extk Î SCr1 e exti Î SCr2 ,

т.е. на выходах разных SCr x j обязательно имеет разные значения.

Поток W - это отображение множества дуг из DCr на множество пар вида (v,wd), где v - время передачи одного блока (в тактах источника); wd - размер блока (одновременно передаваемых данных) в битах. Пару (v,wd) будем называть задержкой. Считаем, что сопоставленный возбужденному и выигравшему арбитраж входу, получит сообщение через тактов. Отметим, что мы считаем здесь v постоянной. Однако, определив ее как функцию, например, от числа активных входов и выходов, времени и т.п., мы сможем описывать достаточно "тонкие" случаи из практики, например, мультиплексирование.

3.4.3. Алгебра носителей

Определение распределенного исполнителя из предыдущего раздела не дает конструктивного правила для описания его структуры и манипулирования ею. С этой целью построим алгебру носителей. Обозначим Ì Â множество носителей:

Ì Â = Ñ Ì Â È S Ì Â ,

где: S Ì r - множество последовательных носителей;

Ñ Ì Â - множество распределенных носителей;

Будем обозначать:

S Ì Â (m,n) - множество последовательных носителей, имеющих не более n-входов и m-выходов (далее мы не всегда будем указывать n и m).

SCr(i,j) - последовательный носитель с i входами и j выходами. Последовательный носитель вида SCr(1,1) будем обозначать Plug.

Будем говорить, что DCr1 = DCr2 , если

  1. " SCr1,i : SCr1,i Î DCr1 Þ $ SCr2,j :SCr2,j Î DCr2 e SCr1,i = SCr2,j ;

  2. E1=E2 ;

  3. n1=n2 ;

  4. j1=j2 ;

т.е. равенство с точностью до изоморфизма.

Определим на Ñ Ì Â операции объединения, слияния входов, композиции и замыкания носителей. Везде далее считаем заданными носители Cr1 =(V1 ,E1 , s n1 , x k1 ) и Cr2 =(V2 ,E2 , s n2 , x k2 ) и Cr1, Cr2 Î Ì Â .

Oбъединение носителей. Объединением Cr1 и Cr2 - " Cr1+Cr2 " будем называть носитель Cr3 = (V3 ,E3 , s n3 , x k3 )Î Ñ Ì Â n , такой что:

  1. V3 = V1 È V2 ;

  2. E3 = E1 È E2 ;

  3. n3 = n1 +n2 ;

  4. k3 = k1 +k2 ;

5.

6.

Графически эту операцию иллюстрирует рис.3.2. Обозначать ее будем знаком "+".

Рис. 3.2

Теорема 6. Если Cr1Î å Ì r и Cr2Î å Ì r, то Cr3Î Ñ Ì r.

Доказательство. Справедливость этого утверждения следует из определения распределенного исполнителя.

Теорема 7. Операция объединения ассоциативна и коммутативна. Доказательство. Это так в силу определения равенства распределенных носителей и определения операции объединения носителей.

W(Plug)=(v,wd)i , если PlugÎ Arci.

Слияние входов носителей. (Oграничение |Ent1|=|Ent2|) Результат операции слияния входов "Cr1 #Cr2 " есть

носитель Cr3 =(V3 ,E3 , s n3 , x k3 )Î Ñ Ì Â такой, что:

V3 = Ent È {Ext1 È Ext2 };

E3 = E1 È E2 ;

s n3(i) = s n1(i) e s n2(i);

Рис. 3.3

Суть этой операции в том, что входы Cr1 отождествляют с входами Cr2 , тем самым в Cr3 допустима операция типа broadcasting, т.е. возбуждение "композиционного" входа передается как Cr1, так и Cr2 . Графически эту операцию иллюстрирует рис.3.3.

Теорема 8. Если Cr1Î å Ì r и Cr2Î å Ì r, то Cr3= Cr1 #Cr2 Î Ñ Ì r.

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

Теорема 9. Операция слияния ассоциативна и коммутативна. Доказательство. Это утверждение также есть простое следствие из определений равенства распределенных носителей и операции слияния входов.

Композиция носителей. Результат операции композиции "Cr1 * Cr2 " есть носитель Cr3 = (V3 ,E3 , s n3 , x k3 )Î Ñ Ì r , такой, что:

Ent3=Ent1 ;

Ext3=Ext2 ;

s n3=s n1 (n1=n3) ;

x k3=x k2 (k2=k3) ;

E3 = E1 È E2 È (x k1 (1), s n2(1)) È ... È (x k1(k1), s n2 (k1)), где k1=n2.

Эта операция определена только для тех операндов, у которых число выходов первого равно числу входов второго. Графически эту операцию иллюстрирует рис.3.4.

Рис. 3.4

Теорема 10. Если Cr1Î Ì r и Cr2Î Ì r, то Cr3= Cr1 * Cr2 Î Ñ Ì r.

Доказательство. Аналогично доказательству теорем 8,9.

Теорема 11. Операция композиции ассоциативна и не коммутативна.

Доказательство. Не коммутативность этой операции следует из несимметричности вхождения ее операндов в ее определение.

Замыкание носителя. Обозначим g(i) целочисленнозначную частичную функцию с областью определения DgÍ {1,...,k} и с областью значений ImgÍ {1,...,n}. Замыканием Cr1 по g(i) назовем носитель

Cr2 =[Cr1]g(i) = (V2 ,E2 , s n2 , x k2), такой что:

Ext2=Ext1\{exti | x k1(exti)Î Dg};

Ent2=Ent1\{enti | enti = s (m), где mÎ Img};

E2 =E1 È {( exti , s n1 (g(x k1(exti))) | exti : x k1(exti)Î Dg};

s n2(i)=s n1(j), где j>i e " k:j>k>i Þ kÎ Img, jÎ Img, n2=n1-|Img|;

x k2 определяется аналогично, т.е. происходит перенумерация с уплотнением: отбрасываются замкнутые входы и выходы. Графически эту операцию иллюстрирует рис.3.5.

Теорема 13. Если Cr1Î å Ì r то Cr2 = [Cr1]g(i)Î å Ì r;

Если Cr1Î Ñ Ì r то Cr2= [Cr1]g(i)Î Ñ Ì r.

Доказательство. Эта теорема прямое следствие определения последовательных и распределенных носителей и операции замыкания.

Рис. 3.5

3.4.4. Свойства алгебры носителей

Из определений носителя и операций объединения, слияния, композиции и замыкания следует, что структура < Ì Â , +, #, *, [ ] > - частичная алгебра.

Теорема 14. При любых фиксированных m и n для любого носителя из Ñ Ì Â существует разложение на последовательные носители из å Ì Â с помощью операций объединения, слияния, композиции и замыкания.

Доказательство. Возьмем произвольный носитель

Cr = (V ,E , s n , x k )Î Ñ Ì r,

так как для носителей из å Ì r эта теорема есть тавтология. Доказывать существование разложения мы будем по следующей схеме: глядя на Cr, построим по строго определенным правилам носитель DCr0 ; для DCr0 докажем его равенство Cr. В силу произвольности Cr мы сможем утверждать существование разложения по указанным правилам для любого носителя из Ñ Ì r .

  1. Построим DCr' = å SCri = (V` ,E` , s n` , x k` )такой,

    SCri DCr

    что E'¹ Æ , V'=V. Такой носитель построить можно по определению множества Ì r и операции объединения носителей.

  2. Построим носитель PLUG по следующему правилу:

  1. Для каждой Arci Î E построим носитель, который обозначим Plugi(j) вида:

Plugi(j)= Plug1#Plug2#...#Plugj , где j=|Arci |;

  1. Объединим все Plugi(j), полученный носитель обозначим PLUG, то есть:

PLUG = å Plugi(j).

ArciÎ E

  1. Из построения носителей DCr' и PLUG следует:

    |Ext'|=|Ent"| ,

    где Ent" - множество входов PLUG;

    Еxt' - множество выходов DCr';

    |Ext"|=|Ent'| ,

    где Ext" - множество выходов PLUG;

    Еxt' - множество входов DCr'.

    Следовательно, и к DCr" и к PLUG применима операция композиции. Построим DCr":

    DCr"=DCr'*PLUG.

  2. Построим однозначную, целочисленную функцию g(i) (подстановку) по следующему правилу:

  1. Dg = {1,...,|Ext"|}; Im = Ds n' ;

  2. значения этой функции определяются следующим:

" i: iDg e x "(ext)=i Þ (s '(g(i)),ext)Î Arc.

  1. Так как |Ent"|>1 и |Ext"|>1, то к DCr" применима операция замыкания. Построим:

DCr0 = [DCr"]g(i),

где i пробегает все значения из Dg.

DCr0 = (V0 ,E0 , s n0 , x k0), из построения DCr0 следует n0 =n, k0 =k.

Поэтому можем определить s n0 и x k0 так, что:

s n0 = s n ; и x k0 = x k .

Теперь переходим к доказательству того, что DCr0=Cr.

Согласно определению для этого надо доказать что:

  1. V0=V;

  2. E0=E; и n0=n и k0=k. Мы докажем более сильное утверждение, а именно что

  3. s n0 = s n ;

  4. x k0 = x k .

Пункты (3),(4) - истины по построению. (1) - истино в силу пункта 1. (2) - истино в силу пунктов 2 и 4. Действительно, предположим, что в E: $ i:(ext,ent)Î Arci , но (ext,ent)Ï E0 . Однако, это противоречит 2.1.

Итак, " Cr: CrÎ Ñ Ì r может быть представлен в форме

Cr =[ (å SCri ) * (å # Plugi(j))]g ,

SCri Cr SCri Cr j |Arc |

где ArciÌ EÎ Cr. (Доказательство окончено.)

Эта теорема гарантирует нам выразимость структуры любого исполнителя из Ñ Ì Â в виде алгебраического выражения над å Ì Â . Доопределим понятие исполнителя на случай алгебраического описания его структуры. Основную проблему доопределения представляет переопределение потока W на случай носителей типа Plug, а не дуг Arc. Напомним, что W определена на множестве E - дуг гиперграфа DCr. Напомним: эта функция каждой дуге сопоставляет задержку - пару (v,wd). Переопределим W на случай носителя Plug следующим образом:

Будем говорить, что

PlugÎ Arci , если его выход ext' замкнута; вход entr', такой, что пара (ext',entr')Î Arci .

Теперь постулируем свойство функции Ci(e) на случай распределенного исполнителя:

П4: " Ci(e): Ci(e)Î SExi Î DEx Þ Ci(t0+v) - Ci(t0)³ 1 ,

где t0 - момент астрономического времени начала передачи единичного блока (момент начала передачи - возврат управления от процесса сопоставленного ext); время передачи сообщения длины l равно (l/wd)v.

3.5. Функционирование распределенной вычислительной системы

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

3.5.1. Связь логической среды и исполнителя

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

Bind: LE Ext È Entr È {SExi} ,

где LE={bh(p)|pÎ Mle};

{SExi}Î DEx.

Exti = {exti |$ SEx: SExÎ DEx e exti Î SEx};

Entr={extj |$ SEx: SExÎ DEx e extj Î SEx}.

Свойства отображения Bind:

  1. одному входу - один процесс;

  2. нет двух или более исполнителей, которым приписан процесс с одним и тем же именем;

  3. если p q и $ siÎ bh(p), $ sjÎ bh(q): (si,sj)Î R f (P)Þ

Bind(p)=ext1 e Bind(q)=entr2 e $ Arc:(ext1 ,entr2 )Î Arc.

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

  1. Bind не меняется в течении всего периода наблюдения.

 

3.5.2. Наблюдатель

Теперь мы можем дать математическое определение понятиям вычислительной системы и вычислительной среды. Вычислительной системой назовем тройку:

CS = <Bh(P),Shd,CE>

где: Bh(P) - поведение программы (см.раздел 3.3.3);

Shd - функция распределения процессов программы в логической среде: взаимно-однозначное отображение P ` Dm, свойства которого были указанны в разделе 3.3.4;

CE - вычислительная среда:

CE = <LE,Bind,DEx>,

где: LE - поведение процессов логической среды

(см.раздел 3.3.3);

Bind - привязка процессов логической среды к исполнителю

(см.раздел 3.5.1);

DEx - распределенный исполнитель

(см.раздел 3.4.2).

Свойства всех этих объектов были определены.

Исполнение программы P на CS есть исчисление, которое будем называть распределенным наблюдателем. Зададим его в виде набора идентичных алгоритмов и правил взаимодействия между ними. Эти алгоритмы будем называть последовательными наблюдателями (или просто наблюдателями если это не вызывает неоднозначности). Каждый из этих алгоритмов определяет выбор очередного шага из поведений процессов прикладной программы и логической среды, надлежащего последовательного исполнителя. Каждому последовательному исполнителю сопоставлен свой последовательный наблюдатель.

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

Mmsg ´ Mps ´ F i ` S,

которое можно описать так:

Obsi (s* , F i ) = s,

где sÎ bh(p) и s, p определяются следующими условиями:

  1. Если F i ¹ 0, то p=Bind-1(F i) e sÎ bh(Bind-1(F i)),

т.е. выбираем шаг из процесса, сопоставленного возбужденному входу, выигравшему арбитраж. Этот шаг соответствует воздействию, поступившему на вход F i . Если таких шагов несколько, то выбор случаен. При этом, если

p*Î Mle, то put(p*. s* ); если p* Î Mpr, то dmj := p* . s* ,

где p* =Shd-1(dmj ), и put(dmj ).

  1. Если F i = 0, то

  1. если dmk Î rpl(s*), то p=Shd-1(dmk) и выбирается шаг, следующий за указанным в dmk и воздействие на котором соответствует rpl(s*) (если таких шагов несколько, то выбор случаен).

  2. если backÎ rpl(s*), то p=get(back) и выбирается шаг, следующий за указанным в back и воздействие на котором соответствует rpl(s*) (если таких шагов несколько, то выбор случаен).

  3. если pÎ rpl(s*), то sÎ bh(p) (выбираем текущий шаг процесса p, по значению переменной p и воздействие у которого соответствует реакции rpl(s*), если таких шагов несколько, то выбор случаен) и back:= p*. s* , где s*Î bh(p*).

  4. если rpl(s*) содержит обращение к атомарному процессу, то сообщение в rpl(s*) преобразуется согласно определению этого атомарного процесса и следующим будет выбран шаг, следующий за s* в поведении того процесса, которому принадлежит данный s*.

  5. если в выбранном процессе нет шага с воздействием, соответствующим rpl(s*), то работа данного Obsi блокируется.

Текущим значением p* становится s*.

3.5.3. Свойства наблюдателя

Исследуем свойства наблюдателя с целью обоснования его корректности. Под корректностью наблюдателя мы будем понимать то, что та совокупность цепочек шагов, которую будут порождать {Obsi}, будет историей программы, т.е. удовлетворять отношению R® (P)=R f (P) È RL(P).

Пусть S*(P) - множество цепочек в алфавите S(P) и wÎ S*(P). Обозначим [w]pi , где pi Î P, последовательность только тех шагов из w, которые принадлежат S(pi), и в том порядке, в каком они расположены в w; т.е. [w] pi Î S*(pi). Назовем [w]pi - проекцией w на pi .

Для обоснования корректности наблюдателя надо доказать,что " i: piÎ P, " j:Obsj порождает:

  1. цепочку шагов, в которой не нарушены ни RL(pi) (причинно-следственные связи на bh(pi) ), ни R f (P) (причинно-следственные связи между процессами), т.е. w удовлетворяет R® (P), и " pi , $ h(pi):[w]pi=h(pi), где w - цепочка шагов, получаемая при интерпретации. Таким образом, это будет означать, что Obsi корректно воспроизводит параллельное выполнение процессов в форме чередования:p1~p2 .

  2. если процессы прикладной программы P распределены между двумя и более последовательными исполнителями SExi , то совокупности цепочек {wk}, порождаемых надлежащими Obsi , обладают тем свойством, что

" pi: piÎ P, $ wk: [wk]pi =h(pi) e ({wk} удовлетворяют R f (P) ),

т.е. множество Obsi корректно воспроизводит истинный параллелизм: pi pj .

3.5.4. Взаимосвязь двух видов параллелизма

Для обоснования корректности наблюдателя нам надо разобраться во взаимосвязи двух видов параллелизма: чередования и истинного. Первый строится на основе отношения независимости: шаги разных процессов могут чередоваться, если они удовлетворяют отношению независимости. Основу второго составляет отношение частичного-порядка на множестве шагов процессов, которое определяет упорядоченность шагов как внутри процессов, так и при межпроцессных взаимодействиях. Все шаги, которые несравнимы в этом отношении, считаются одновременными, а, стало быть, параллельными. Обозначим: R*® (P) - транзитивное замыкание R® (P);

^R*® (P) - симметричное замыкание R*® (P), т.е.

" a,bÎ S(P):(a,b)Î R*® (P) Þ (b,a)Î ^R*® (P) e (a,b) )Î ^R*® (P)

B = ^R*® (P) È diag(S(P)),

где diag(S(P))={(a,a)|aÎ S(P)} - диагональ в S(P)´ S(P). Это отношение назовем отношением связанности. Будем говорить, что a и b связаны, если (a,b)Î B.

I = S(P)´ S(P)\B - отошение независимости.

Лемма. B - рефлексивно и симметрично;

I - иррефлексивно и симметрично.

Доказательство. B симметрично так как ^R*® (P) симмметрично и ^R*® (P)Ì B.

B рефлексивно так как diag(S(P))Ì B.

I симметрично так как если (a,b)Î I, но (b,a)Ï I, то следовательно (b,a)Î R*® (P). Отсюда получаем, что (a,b)Î B, но I Ç B = Æ . Пришли к противоречию.

I иррефлексивно по определению, так как diag(S(P))Ì B.

Теорема 15. " a,b: (a,b)Î I Þ в FBh(P) нет пути из a в b (напомним,что FBh(P) - лес из Tbh(pi) по всем pi из P).

Доказательство. " a,b: (a,b)Î I Þ (a,b)Ï R*® (P), но по построению R*® (P) содержит все пути из FBh(P).

Тройку <S,I,B> назовем опорной структурой и будeм обозначать • = <S,I,B>. Для сравнения цепочек из шагов, образованных параллельным выполнением нескольких процессов в форме чередования, введем отношение, которое будем обозначать R » (• ).

Пусть • - опорная структура. По определению считаем, что

(w,u)Î R» (• ) Û w=u, либо

$ w1,w2Î S*(P), $ a,b:(a,b)Î I( ) e [w=w1 abw2 e u=w1baw2].

т.е. две цепочки удовлетворяют R » (• ), если одна может быть получена из другой допустимой перестановкой соседних символов. Перестановка допустима, если эти соседние символы удовлетворяют отношению I.

Обозначим R@ ( ) - минимальное транзитивное замыкание R» (• ), т.е. если (w,u)Î R@ ( ), то u может быть получено из w конечной последовательностью перестановок независимых символов, т.е. символов, удовлетворяющих отношению I.

Теорема 16. R@ ( ) - отношение эквивалентности на S*(P).

Доказательство. Для доказательства этого утверждения надо показать, что R@ ( ) - рефлексивно, симметрично и транзитивно.

  1. Оно рефлексивно, так как " u:uÎ S*(P) по определению (u,u)Î R Rf (” ) Þ (u,u)Î R@ ( ).

  2. Оно симметрично, так как " u,w: (u,w) Î R@ ( ) Þ $ a,b:a,bÎ S(P) e (a,b)Î I Þ (b,a)Î I Þ (w,u)Î R@ ( ).

  3. Оно транзитивно по определению.

Пусть wÎ S*(P). Обозначим класс эквивалентности на S*(P), содержащий w,: Tr(w)={wi|wiÎ S*(P) e (wi , w)Î R@ ( )}.

Будем говорить, что w - представитель Tr(w) Û wÎ Tr(w).

Поясним введенные выше понятия на примере. Пусть даны:

S={a,b,c,f,k,g};

B={(a,k),(a,f),(a,g),(b,c),(c,g),(b,k)} È diag(S);

I={(a,b),(a,c),(f,b),(f,c),(g,b),(c,k),(f,g),(f,k),(g,k)}.

Тогда:

(abgc,agbc), (fcak,fakc), (gbfac,bgcfa) Î R@ ( );

Tr(gbfac)={gbfac;gfbac;gfbca;gbfca;gbcfa;bgcfa;bgfca}.

Теорема 17. Пусть “ - опорная структура, тогда:

  1. " w,u:wÎ S* , uÎ S* e (w,u)Î R@ ( ) Þ |w|=|u|;

  2. " w1 ,w2 ,u1 ,u2 : w1 ,w2 , u1 ,u2 Î S* e [(w1 ,w2)Î R@ ( ) e (u1 ,u2) Î R@ ( )] Þ (w1 u1, w2 u2 ) Î R@ ( ),

где wu - конкатенация строк w и u.

Доказательство.

  1. Если предположить что |w| ¹ |u|, то из этого предположения будет следовать, что число символов в этих строках различно. Следовательно u нельзя получить из w только перестановкой независимых символов, а поэтому (w,u)Î R@ ( ) не может быть, что противоречит исходной посылке.

  2. Возьмем строку w1 u1 , так как $ w2: w1=w2 Þ есть последовательность допустимых перестановок, преобразующая w1 в w2 , следовательно w1 u1 = w2 u1. Рассуждая аналогично, можно показать что w2 u1 = w2 u2, что в силу транзитивности отношения R@ влечет w1 u1 = w2 u2. (Доказательство закончено.)

Каждая строка wÎ S* может быть охарактеризована ориентированным, размеченным ациклическим графом. Идея его построения заключается в следующем: возьмем число вершин по числу символов в w и расположим их в том порядке, в каком они встречаются при движении вдоль w слева направо. Две вершины мы будем соединять дугой тогда и только тогда, когда они удовлетворяют отношению R® (P), т.е. ориентированному подмножеству B.

Пусть “ =(S,I,B) - опорная структура и wÎ S*. Характеристическим графом для w назовем

Г“ (w)=({1...n},E,S,l),

где l: {1...n} ` S;

E={(i,j)|1£ i, j£ n e i<j e l(i)=si e l(j)=sj e (si ,sj )Î R® (P)}.

Теорема 18. Пусть ” - опорная структура и w,uÎ S* . Tr(w)=Tr(u) Û Гš (w) и Г— (u) изоморфны.

Прежде чем приступить к доказательству этой теоремы разъясним ее важность для нас. Эта теорема определяет взаимосвязь между строками, эквивалентными в смысле некоторого отношения независимости, и совокупностью строк {[Tr(w)]pi}, связанных определенным отношением частичного порядка R® (P). Она утверждает, что если отношения независимости и частичного порядка связаны так, как это было сделано выше, то для сравнения структур из строк нам не надо предварительно преобразовывать чередованием каждую структуру в одну строку, а затем сравнивать строки между собой. Достаточно убедиться в том, что частичные порядки, которые отражают причинно-следственные связи в этих структурах, изоморфны. В этом случае и сами структуры и получаемые из них строки будут эквивалентны. Отсюда следует, что для установления взаимосвязи двух видов параллелизма надо рассмотреть то, как соответствующее исчисление сохраняет отношения частичного порядка на множестве S(P) шагов программы.

Доказательство.

  1. Пусть Tr(w)=Tr(u), докажем что в этом случае Г“ (w) и Г“ (u) изоморфны. Из посылки теоремы следует существование конечной допустимой перестановки символов в w, в результате которой w преобразуется в u. В следствии этого и теоремы о том, что если (w,u)Î R@ ( ), то |w|=|u| следует, что существует такая перенумерация вершин в Г“ (w), в результате которой Г“ (w) становится конгруэнтным Г“ (u). Эта перенумерация определяет изоморфизм между Г“ (w) и Г“ (u). Существование такой перенумерации влечет существование изоморфизма между Г“ (w) и Г“ (u).

  2. Пусть теперь Г“ (w) изоморфен Г“ (u), докажем что в этом случае (w,u)Î R@ ( ), а следовательно Tr(w)=Tr(u). Изоморфизм графов Г“ (w) и Г“ (u) означает существование такой перенумерации j вершин графа, в результате которой структуры их становятся конгруэнтными, а разметки + удовлетворяют соотношению lw(i)=lu(j (i)). Отсюда следует, что если переставить симовлы в строке w в соответствии с перестановкой (j (1),j (2),...,j (n)), то получим строку u. (Доказательство закончено.)

Для обоснования корректности наблюдателя надо доказать, что " i: Obsi не нарушает отношения R® (P). Отсюда, как следствие теоремы 10, будет следовать, что для любых Shd и Bind множество {Obsi} порождает корректную историю программы.

Теорема 19. " i: Obsi сохраняет R® (P) (т.е. Obsi реализует изотонное отображение).

Доказательство. Обозначим Trci - цепочку шагов, полученных в ходе интерпретации Obsi за период наблюдения. Тогда [Trci]pj - проекция Trci на j-ый процесс.

Докажем что " p: [Trci]p P (bh(p), то есть Obsi не нарушает R`(p). Предположим, что [Trc]p Ï bh(p). Это возможно в двух p случаях:

  1. $ s:sÎ [Trci]p e sÏ S(p);

  2. $ si ,si+1 :( si , si+1 )Î [Trci]p , но (si , si+1)Ï R`(p).

Рассмотрим первый случай. Он возможен, когда среди S(p) нет шага либо с infl(s), либо с rpl(s). Если допустить, что среди S(p) нет шага с infl(s), то согласно алгоритму, определяющему Obsi, такое воздействие должно вызвать остановку интерпретации. Поэтому никакого Trci мы бы не получили. Случай существования rpl(s), не принадлежащего S(p), не возможен по определению Obsj : интерпретируются шаги только из bh(p). Теперь разберем случай (2). Раз (si , si+1)Ï R`(p) Þ либо (si , si+1)Î R f (P), либо (si , si+1)Î I - но ни в первом, ни во втором случаях эта пара не может принадлежать [Trci]p. В первом случае потому, что из определения R0(P) следует; s mS(p); во-втором: потому, что согласно теореме о взаимосвязи отношения I и леса FBh(P), нет пути в FBh(P) между si и si+1. Поэтому этот случай так же не возможен.

Теперь докажем, что Obsj не нарушает R f (P). Рассмотрим [Trci]pk,pm . Пусть $ sq ,sj Î [Trci]pk,pm такие, что sqÎ S(pk), sjÎ S(pm), но (sq ,sj)Ï R f (P) , (где sq sj - цепочка из двух символов). Здесь возможны случаи: (sq,sj)Î I, либо (sj,sq)Î R f (P)и (sq,sj)Î {^R* (P)\R* (P)}.

В первом случае мы можем переставить эти шаги. Такие перестановки мы сможем делать до тех пор пока либо не кончится цепочка шагов, что будет означать отсутствие взаимодействия между pk и pm , либо пока не встретим шаг s' такой, что (s',sj )Ï I. Это означает, что s' либо из S(pk), который в паре с sj принадлежит R f (P), что дает нам доказываемое утверждение, либо s'Î S(pm ), то есть (s',sj) Î R (pm). Это значит, что на данном локальном участке не было взаимодействия, что в силу произвольности выбора пары (sq,sj) фактически означает отсутствие взаимодействия между pk и pm .

Случай sq,sj Î [Trci]pk`,pm` но (sj,sq)Î R f (P) означает следующее. Если рассматривать FBh(P), как неориентированную структуру, то в ней есть путь из sq в sj. Причем на этом пути есть хотя бы одна дуга, вдоль которой мы должны пройти в направлении противоположном ее ориентации, то есть нарушить причинно-следственную связь между шагами. Это противоречит процедуре, определяющей отображение Obsi , так как в ней везде указан переход от причины к следствию. Таким образом мы опять пришли к противоречию, что означает справедливость доказываемого утверждения. Итак, корректность Obsi гарантирует нам сохранение всех причинно-следственных связей в программе вне зависимости от используемого вида параллелизма. Использование исчисления, определяемого Obsi , в инструментальной вычислительной среде гарантирует нам независимость получаемых результатов анализа от степени параллелизма, используемого в этой среде.

3.5.5. Недетерминизм поведения распределенных программ

В главе 2 был дан качественный анализ особенностей поведения распределенных программ. Основной особенностью, определяющей сложность анализа поведения программ, был назван недетерминизм. Там же были выделены две его формы; внешний и внутренний (см. раздел 2.2.4), дана классификация поведений программ и сформулированы в форме гипотез некоторые утверждения о связях различных форм недетерминизма и поведений программ различных классов (см.раздел 2.2.5).

Цель данного раздела дать математическое определение разным формам недетерминизма, в терминах этих определений сформулировать и доказать высказанные ранее утверждения о связях разных форм недетерминизма с разными классами поведения программ. (Способы описания разных форм недетерминизма были даны в разделе 3.3.2.)

Будем рассматривать дерево поведения программы Tbh(p) в ярусной форме. В обозначении шага будем использовать два нижних индекса; первый - номер яруса, на котором расположен шаг, второй - номер этого шага на ярусе.

Разделим множество сообщений на подмножества двух типов: множество сообщений-данных - ; и множество синхро-сообщений - . Сообщения-данные - это элементы множества , которые процесс использует исключительно как данные и не использует для целей синхронизации. Это означает, что если воздействие на шаге принадлежит множеству , то реакция этого шага не зависит от того, с какой скоростью развивались вычисления в других процессах, когда формировалось это воздействие. Под синхронизацией мы понимаем ограничения на порядок выполнения процессов программы. Множество синхро-сообщений - это подмножество , элементы которого процесс использует в msg целях синхронизации.

Будем говорить, что в bh(p) есть внутренний недетерминизм, если:

  1. $ sj,k ,sj,m Î S(p): расположенные на одном и том же ярусе j и имеющие общего предшественника на ярусе j-1;

  2. infl(sj,k)=infl(sj,m) и infl(sj,k),infl(sj,m)Î ;

  3. rpl(sj,k) ¹ rpl(sj,m ).

Внутренний недетерминизм в поведении процесса описывает только влияние данных, полученных в других процессах, на последовательность вычислений в данном процессе. При этом, то от какого конкретного процесса получены эти данные, на эту последовательность вычислений влияния не оказывает. Другими словами, выбор одного из шагов sj,k , sj,m не зависит от скорости продвижения вычислений в других процессах. Будем говорить, что в bh(p) есть сильный внешний недетерминизм, если:

  1. $ sj,k ,sj,m Î S(p) и расположенные на одном и том же ярусе j, и имеющие общего предшественника на ярусе j-1;

  2. infl(sj,k) ¹ infl(sj,m) и infl(sj,k),infl(sj,m)Î ;

  3. rpl(sj,k) ¹ rpl(sj,m).

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

  1. rpl(sj,k) = rpl(sj,m).

Слабый внешний недетерминизм позволяет описывать стационарное поведение программ (см.раздел 2.2.5).

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

Скажем, что Bh(P) соответствует LE если:

  1. множество процессов, указанных в реакциях шагов из S(P) есть подмножество MLE ;

  2. сообщения, указанные в rpl(s) где sÎ S(P), является приемлемыми воздействиями для шагов в поведениях процессов из MLE ;

  3. воздействия на процессы из P, указанные в реакциях шагов процессов из MLE , являются приемлемыми для процессов из P.

Воздействие a приемлемо для bh(p) если $ sÎ S(p): infl(s)=a .

Теорема 20. Если " pÎ P: bh(p) обладает только внутренним недетерминизмом, то " LE, которой Bh(P) будет соответствовать, при фиксированном начальном воздействии на P, H(P) будет постоянной.

Доказательство. Возьмем LE1 и LE2 , которым соответствует Bh(P). Зададим начальное воздействие {a i}. Пусть мы получим в LE1 историю H1(P), а в LE2 - H2(P). Надо доказать что H1(P)= H2(P). В силу произвольности выбора {a i}, LE1 и LE2 это и будет служить доказательством утверждения теоремы.

Допустим, что утверждение теоремы не верно. Следовательно, для некоторого pÎ P: h1(p)¹ h2(p). Это значит, что существует r: sr,h1 ¹ sr,h2 , но " i:1£ i<r Þ sr,h1 = sr,h2 . Такой случай может возникнуть, если воздействия в Tbh(p) на r-ом ярусе в LE1 и LE2 были разные. Для того чтобы bh(p) на r-ом ярусе были приемлемы разные воздействия необходимо в силу определения внутреннего недетерминизма, чтобы шаги si,h1 и si,h2 имели разных предшественников на ярусе r-1. В этом случае в H1(P) и в H2(P) должны не совпадать и sr-1,h1 ¹ sr-1,h2. Пришли к противоречию.

В разделе 2.2.5 было высказано в форме гипотезы утверждение о взаимосвязи внешнего недетерминизма и нестационарности поведения программ. Напомним, что нестационарным мы назвали поведение процесса, зависящее от скорости вычислений в других процессах. Конкретизируя эту формулировку в терминах введенных понятий, мы можем сказать, что эта зависимость проявляется в том, что в Tbh(p) некоторые шаги будут иметь несколько преемников с разными воздействиями и разными реакциями. Эти воздействия принадлежат и инициируют их разные процессы. Только что сказанное ничто иное, как переформулировка определения сильного внешнего недетерминизма, которая была дана выше. Таким образом, справедлива следующая теорема:

Теорема 21. Если в поведении bh(p) процесса p есть зависимость от скорости вычислений в других процессах pÎ P, то в этом bh(p) есть сильный внешний недетерминизм. Заметим, что обратное утверждение не верно. А именно, если в bh(p) есть сильный внешний недетерминизм, то он может возникать из-за чувствительности поведения bh(p) к разным наборам данных, особенностям поведений процессов из LE.

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

3.6. Построение временного профиля

В разделе 1.1 мы сделали заключение о том, что все известные виды производительности могут быть получены на основе временной диаграммы работы вычислительной системы. (То как это делать мы подробно рассмотрим в разделе 3.7.) Поэтому, заключили мы там, нашей целью является получение временной диаграммы работы системы. Эту диаграмму мы будем описывать с помощью временного профиля.

Временным профилем работы вычислительной системы CS назовем вектор-функцию

G(t) = (g1(t), g2(t),...,gn(t)),

где " i: 1£ i£ n и gi(t) - временной профиль последовательного исполнителя SExiÎ CE.

Временным профилем последовательного исполнителя SExi назовем однозначную функцию gi(t), определенную на R, с областью значений - множество кортежей вида

<p, s, q, ai >

где, pÎ P, sÎ S(p), qÎ cx(s), aiÎ w(qi).

В терминах введенных понятий нашу основную задачу из раздела 1.2 можно сформулировать так: пусть задана вычислительная система

CS = <Bh(P), Shd, CE>.

Требуется найти временной профиль G(t) системы CS. Задача построения G(t) разбивается на две:

  1. Для каждого SExi определить последовательность выполняемых им действий;

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

3.6.1. Определение последовательности действий и времени их выполнения

Последовательность действий для SExi на уровне шагов i процессов определяет последовательный наблюдатель Obsi . Каждый шаг состоит их последовательности действий q=cx(s), а каждое действие qiÎ cx(s) есть последовательность атомарных процессов, множество которых определяет функция сложности w(qi)=(n1 ,n2 ,...,nk ).

Предположим на время, что нам известна упорядоченность набора w(qi). (Позднее мы вернемся к этой задаче определения упорядочения набора действий, в том числе и атомарных процессов.) С использованием этого предположения для построения gi(t) достаточно модифицировать интерпретацию Obsi следующим образом: Obsi анализирует состояние Фi не между шагами sÎ S(P), а после выполнения каждого атомарного процесса текущего шага. При наличии возбуждения входа (Фi ¹ 0) в dmi и back запоминается имя процесса, шаг, выполняемое qi и цепочку невыполненных атомарных процессов. Значением gi(t) в течении vt(ai) тактов полагаем равным имени текущего процесса, шага, внутреннего действия qi и атомарного процесса ai . Таким образом, gi(t) - это есть значение Obsi в момент t. Напомним, что в течении vt(ai) тактов , где ai - атомарный процесс SExi не реагирует на внешние воздействия и не может выполнять других действий.

Эта модификация не нарушает логической корректности Obsi . Это действительно так, поскольку она сводиться к замене в определении Obsi шагов sÎ S(P) на атомарные процессы, которые также можно рассматривать как шаги.

3.6.2. Упорядоченность действий

Здесь мы рассмотрим задачу об упорядочении действий, задаваемых вектором трудоемкости (n1 , . . . ,nk ). Один из способов решения этой задачи уже был дан в разделе 2.2.6. Предложенное там решение опиралось на технику генерации кода и определенную модель вычислителя. Оно годится для случая, когда упорядочиваемыми действиями являются атомарные процессы, а вычислитель соответствует модели. Однако представляется полезным уметь упорядочивать не только атомарные, но и более сложные действия, когда достаточных сведений о вычислителе еще нет. (Такие ситуации достаточно часто возникают при проектировании вычислительных систем.) Здесь мы рассмотрим именно этот случай задачи об упорядочении действий.

Пусть нам задан набор действий в виде вектора (n1 , . . . ,nk ), которые должны быть выполнены. Здесь ni - число действий i-го типа. Время выполнения действия каждого типа известно. По существу это вектор трудоемкости для случая не атомарных действий. Известно, что эти действия будут выполнены в определенном порядке, который заранее нам не известен. Назовем для определенности это упорядочение натуральным.

Надо так упорядочить эти действия, чтобы окончание j-го действия при нашем упорядочении, как можно меньше отклонялось от момента окончания j-го действия при натуральном упорядочении, которое может быть получено, например, с помощью генератора кода транслятора. Назовем это упорядочение искусственным.

В математическом виде нашу задачу можно переформулировать так:

дано: множество {l1 , l2 , ... ,lk } из соизмеримых отрезков k видов (вид отрезка определяет его длина). Это множество упорядочено так, что

" i,j: 1£ i<j£ k Þ li £ lj и li Î N.

Набор L=(n1 , . . . ,nk) из этих отрезков, в котором nj отрезков j-го вида. Отрезки из L расположены вдоль прямой в стык друг к другу.

Обозначим Yi точку на прямой, в которую попадает правый конец i-го по порядку отрезка (отрезки пронумерованы слева направо) при натуральном упорядочении. Это размещение нам не известно.

требуется: так разместить отрезки из набора L вдоль прямой, чтобы правый конец i-го отрезка, обозначим Xi точку на прямой, в которую он попадает, как можно меньше отклонялся от Yi (размещаем и нумеруем отрезки слева направо).

Предполагаем, что натуральное размещение становиться нам известно, только после того, как построено искусственное.

Обозначим fi(x), где xÎ R функционал вида

fi(x) = Еr (x,Yi |xi-1 =Xi-1 , xi-2 =Xi-2 ,...,x1=X1)= lå L P(x= Xi-1+l | xi-1=Xi-1 , x i-2 =Xi-2 ,..., x1 =X1 ) r (x, Yi),

где r (x,y) - метрика, P(x=X | xi-1=Xi-1 , ... ) - условная вероятность.

С помощью функционала f(x) критерий оптиммзации в нашей задаче можно сформулировать так:

" i: iÎ [1...N-1], где , надо выбрать Xi*Î L* так, чтобы

Xi*= argminfi(X), где XÎ L*,

где L* множество отрезков, построенных из отрезков из L.

Нашу задачу рассмотрим для r (x,y) вида:

r (x,y) = |x-y|a .

Согласно [17] наиболее распространенными вариантами этой метрики являются:

  1. a =1, т.е. fi(x)=Е|X-Yi|;

  2. a =2, т.е. fi(x)=Е|X-Yi|2;

  3. a =0, т.е. fi(x)=
Е|X-Yi|a .

Минимум в каждом из этих трех случаев достигается в следующих точках [17]:

  1. a =1 - argmin Е|X- Yi|=med X, где XÎ L* ;

  2. a =2 - argmin Е|X- Yi|2=ЕX, где XÎ L* ;

  3. a =0 - argmin
Е|X- Yi|2=mod X, где XÎ L, и a =0.

Теперь рассмотрим подробно выбор отрезков в каждом из этих трех случаев и оценим ошибку в каждом из них.

3.6.2.1. Случай a =1

По определению

med X = inf {a | P(X ³ a)³ e P(X £ a) ³ }.

Найдем med X1 . Распределение случайной величины ( везде далее просто с.в.) X1 известно, а именно:

P(X =l1)=n1/N, ... , P(X =li)=ni/N, ...,

где и P(X1=li)=1.

Тогда med X1=lj1 , где j1= min {j | 1 £ j £ k и }.

Оценим ошибку на первом шаге:

Е|Y1 - lj1 | = P(Y1 =li , X1=lj1) |li - lj1 | =

= P(Y1 =li | X1 =lj1 ) P(X1 =lj1 ) | li - lj1 | =

= P(Y1 =li | X1 =lj1 ) | li - lj1 | =

= | ,

где D max = max | li - lj |.

li , lj L

Найдем выражение для X2 :

med X=lj2 , где XÎ L2 =L\lj1 ;

j2 = min {j|1£ j£ k и P(X2 =li | X1 =lj`1 ) ³ },

где P(X2 =li | X1 = lj`1 )= + (1 ± sign(i-j1)) .

Оценим ошибку на этом шаге:

Е(|Y2 - lj2 | |X1 =medX) = P(Y2 = li , X2 =lj2 |X1 =lj1 ) |li - lj2 |.

P(Y2 = li | X2 =lj2 , X1 =lj1 ) P(X2 =lj2 |X1 =lj1 ) | li - lj2 | =

= P(Y2 = li , X2 =lj2 |X1 =lj1 ) .

По аналогии с предыдущим найдем выражение для X3=lj3 :

j3 = min {j | 1 £ j £ k и P(X3 =li | X2 =lj`2 ) , X1 =lj1 ) ³ },

= min{j | +(1 ± sign(i-j1)) +

+ (1 ± sign(i-j2)) }.

Или в общем случае:

jq = min {j| +(1± sign(i-ji)) }.

Итак, ошибка на каждом шаге не более .

3.6.2.2. Случай a =2

Рассмотрим критерий min Е|X-Yi|2 , где XÎ L*.

Поскольку argmin Е|X-Yi|2 = ЕX, где XÎ L* , то

X1 = ЕX = P(Y1 =li) li = .

Так как X1 может не принадлежать L, то lj1 выберем из условия

min| X1 - lj |= min| - lj |= min { },

где минимум берется по ljÎ L .

Оценим ошибку на первом шаге:

P(Y1 =li , X1=lj1) |li - lj1 | =

= P(Y1 =li | X1 =lj1 ) P(X1 =lj1 ) | li - lj1 | =

= P(X1 =lj1) | li - lj| = |EX - lj1 | P(X1 =lj1) ,

откуда следует, что

Теперь рассмотрим выбор lj2 :

X2 = Е(X|X1 = lj1) = P(X1 =li |X1 =lj1) li =

=

=

Отсюда получаем:

lj2 = argmin|X2 -li | = argmin| - li |,

где минимум берется по liÎ L2 = L1\lj1 .

Оценим ошибку на втором шаге:

P(Y2=li , X2=lj2) , X1=lj1) | li - lj2 | =

= P(Y2=li | X2 =lj2 ) P(X2 =lj2 | X1=lj1) P(X1=lj1) | li - lj2 | =

= = P(X2 =lj2 | X1=lj1) P(X1=lj1) | li - lj2| £ a 2 D max ,

где 0<a <1/2.

По аналогии, делая выкладки для других шагов, получим

D q(2) < a q D max .

Таким образом, второй метод точнее первого.

3.6.2.3. Случай a =0

Проанализируем случай метрики fi(X)=Е|X-Yi|a (это, так называемая, метрика Хевисайда). У этой метрики

argmin fi(X)=modX , где XÎ L* .

По определению modX= argmaxF(X), где F(X) функция распределения с.в.X, т.е. это точка с максимальной вероятностью. Следовательно:

X1=lj1 , где lj1 таково, что nj1=max{ni};

ni L

X2=lj2 , где lj2 таково, что nj2=max{ni} и т.д.

ni L2

Оценим ошибку на первом шаге:

P(Y1=li , X1=lj1) , | li - lj1 | =

= P(Y1 =li | X1 =lj1 ) P(X1 =lj1 ) | li - lj1 | =

= | li - lj | = |EX - lj1 | ,

что явно больше , так как = max P(X1=li) ,

li L

Оценим ошибку на втором шаге:

P(Y2=li , X2=lj2 , X1 =lj1) | li - lj2 | =

= P(Y2=li | X2 =lj2 ) P(X2 =lj2 | X1 =lj1)P(X1 =lj1) | li - lj2 | =

= |EX- lj2| .

что опять-таки больше, чем и т.д. В общем случае

,

где ljq = modX и XÎ Lq .

Из проведенного анализа следует, что наиболее точным является метод с метрикой r (x,y) = |x-y|2 . Ошибка при упорядочении по этому методу на шаге q не превышает величину a qmax|ЕX-li|, где a Î [0,1]. Поэтому, если рассматриваемыми действиями являются атомарные процессы и для любого последовательного исполнителя справедливо, что если

vt(p_exti)> a max|ЕX-li| ,

li L

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

3.7. Связь временного профиля с основными видами производительности

Здесь мы рассмотрим, как, зная временной профиль поведения системы, можно получить оценки разных видов производительности, а также выведем ряд соотношений, связывающий основные формы производительности с различными количественными характеристиками функционирования систем. (Подробно эти соотношения рассмотрены в [18].)

Пусть дана распределенная вычислительная система CS,состящая из Q последовательных исполнителей (например, процессоров). Введем следующий набор переменных, характеризующих функционирование CS:

T - длина периода наблюдения за работой CS по астрономическому времени;

J - число услуг, выполненных CS за период наблюдения. Услугу можно понимать как выполнение программы, функции, шага, команды и т.п.

Обозначим:

X = J/T - пропускную способность системы CS;

Ui - количество астрономического времени, которое i-ый последовательный исполнитель из CS, был занят выполнением услуг из J;

Wi = Ui/T - загрузку i-го исполнителя;

Ni - общее количество действий (действие - это нечто, что образует услугу), выполненных i-м последовательным исполнителем в течении периода наблюдения T.

Pwi = Ui/Ni - среднее время действия на i-ом последовательном исполнителе (это вычислительная мощность исполнителя);

Eni = Ni/J - среднее число действий i-го устройства на одну услугу из J.

В этих обозначениях справедлива следующая теорема.

Теорема 22. (о пропускной способности). " i: 1 £ j £ Q Þ X= .

Доказательство: .

Следствие: " i,j: 1 £ i,j £ Q = .

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

Рассмотрим некоторые актуальные применения этого закона. Постараемся определить соотношение между мощностью последовательного вычислителя Pwi , числом Ni выполняемых им действий при решении задачи и отношением времени счета Ui к времени обмена

Oi : l i= Oi/Ui, где T³ Oi+Ui .

Так как услугой теперь является решение одной задачи, то J=1 и

X= .

Так как Ui £ T - Oi, то

l i < 1/Wi ≈1 Wi £ 1/(l i +1).

Откуда T/(l i +1) ³ Pwi Ni или

(*).

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

Oi = Oti m ,

т.е. разобьем время обмена на m частей. В наших обозначениях мы хотим определить

Тогда из (*) получим:

откуда

или .

Откуда, выражая g , получаем:

.

Теперь задачу о распараллеливании на заданной вычислительной системе CS можно сформулировать так:

дано N - общее количество действий, которые надо выполнить за время Т;

надо так распределить эти действия по Q процессорам чтобы:

или ³ Ni(l i +1) ,

где и и T ³ Oi + Ui .

Теперь покажем то, как можно получить набор операционных переменных W, Ni , J и T, зная временной профиль G(t). Возьмем в качестве услуги выполнение процесса программы, а в качестве действия - атомарный процесс последовательного исполнителя. Тогда:

J= , где (tk - момент окончания процесса, например, обращение к Stop в профиле gi ).

Ui = , где c p(t) - характеристическая функция шага процесса p, т.е. c p(t)=1 если gi(t)=p.s.d.a, где pÎ P или c p(t)=0 в противном случае.

Ni = , где d i(t) - функция, которая принимает значение 1 в момент изменения значения gi(t) и равна 0 в остальные моменты времени.

Теперь рассмотрим другой важный вид производительности - время отклика. Пусть на CS расположено N процессов, к которым поступают запросы. В качестве ранее упоминавшихся услуг возьмем выполнение j-м процессом (1£ j£ N) запроса. Предполагаем, что N не меняется в течение периода наблюдения. Введем следующие обозначения:

J - число запросов, выполненных за период наблюдения Т.

r(k) - общее время, потраченное k-ым процессом на удовлетворение услуги k-го типа (т.е. время полезной работы k-го процесса). В этих обозначениях среднее время удовлетворения услуги можно выразить так:

R = .

J' - число запросов на услуги, поступившие в систему за период наблюдения (|J-J'|<N).

z(k)= T - r(k), т.е. время "простоя" k-го процесса.

В этих обозначениях среднее время ожидания запроса можно выразить так:

Z = .

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

Теорема 23 (о времени отклика): .

Доказательство: " k:1£ k£ N Þ z(k) + r(k) = T. Отсюда

+ = NT.

В случае, когда CS - последовательный исполнитель

£ T.

Далее

+ .

или, используя ранее введенные обозначения, можно записать

,

откуда получаем утверждение теоремы

.

Следствие: Используя теорему о пропускной способности, получаем:

.

В случае N<<J:

.

Теперь рассмотрим связь этих двух видов производительности с характеристиками, которые описывают использование памяти в системе. Пусть функция Stg(p,t) определяет количество единиц памяти, занимаемой процессом p в момент t. Обозначим:

mt(p) = и Str = ,

где N - это число процессов, которые присутствовали в момент t=0, т.е. мы не учитываем динамики порождения процессов, а сумма берется по всем p в системе. Тогда количество памяти, используемой в системе в момент t равно

m(t) = Stg(p,t) .

В этих обозначениях среднее количество используемой памяти в системе можно выразить как

M = .

или, используя выражение для m(t),

M = =

=.

Откуда получаем

M = X Str (*).

Используя формулы времени отклика и подставив в нее выражение X из (*), получим

.

Приведенные соотношения позволяют количественно оценить параметры вычислительной системы, которая должна обладать желаемой пропускной способностью и временем реакции. Приведенные здесь соотношения также оказались полезны при проверке корректности имитационных моделей [19].

3.8. Выводы

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

В рамках этой теории:

 

 

ЛИТЕРАТУРА К ГЛАВЕ 3

  1. Смелянский Р.Л. Подход к описанию и измерению поведения программ в распределенных вычислительных средах// Программирование (в печати)

  2. Hoare C.A.R. Communicating sequential process.Prentis-Hall.1985.

  3. Milner R. A calculus of communication system.1980.LNCS.92.

  4. Degano G., Montanary U. Distributed system, partial ordering of events, and events structures // Control flow and Data flow: concepts of distrebuted programming. Springer-Verlag, 1986.P.7-106.

  5. Nivat M. Behaviors of processes and synchronizing system of process //Theor. Found. Program. Methodology. N.-H. Press, 1982.P.473-550.

  6. Летичевский А.А., Капитонова Ю.В. Математическая теория проектирования вычислительных систем. Мюб1988.

  7. Молонов В.Г. Смелянский Р.Л. Комплексный подход к моделированию распределенных вычислительных систем//Программированиею Т1ю 1988юС.57-67

  8. Смелянский Р.Л. Об инварианте поведения программ// Вестн.Моск.ун-та.Сер. 15. Вычисл. матем. и киберн.N4,1990.

  9. Plotkin G. An operational semantics for CSP //Formal description of programming conceps.11&N.-H. Press, 1983.P.199-223.

  10. Lauer P.E., Shields M.W., Best E. Formal theory of the basic COSY notation //Acta informatica.1979.12.P.109-158.

  11. Hennesy M.,Plotkin G. Full abstraction for simple programming language//LNCS.1979. 74.P.108-120.

  12. Genrich H.J., Lautenbach K., Thiagarajan P.S. Elements of general net theory//LNCS.1980. 84.P.21-163.

  13. Goldz U.,Reising W. The non-sequantial behavior of Petry net//Information and Control.N5.1983.P.125-147.

  14. Котов В.Е. Сети Петри. М.,Наука, 1984.

  15. Миренков Н.Н. Параллельное программирование для многомодульных вычислительных систем.М.,1989.

  16. Кристофидес Н. Теория графов% алгоритмический подход. М.Мир.1978.

  17. Леман Э. Проверка статистических гипотез. М.Наука, 1979

  18. Смелянский Р.Л. Операционные характеристики функционирования вычислительных систем.