ПРОГРАММИРОВАНИЕ, 2014, No 5, с. 3 27
ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ
УДК 519.681.2, 519.681.3
АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ ПАРАЛЛЕЛЬНЫХ СИСТЕМ В АЛГЕБРЕ dtsiPBC *
© 2014 т. И.В. Тарасюк1, X. Масиа2, В. Валеро2
1 Институт, систем, информатики им. А. П. Ершова, СО РАН 630090 Новосибирск, пр. Академика Лаврентьева, 6
2
Авенида, де Эспанья, б/и, 02071 Альбасете, Испания E-mail: itar@iis.nsk.su, hermenegilda.macia@uclm.es, valentin.valero@u,clm.es
Поступила в редакцию 10.08.2013
Исчисление боксов Петри РВС — известная алгебра параллельных процессов с семантикой сетей Петри. В статье рассматривается расширение РВС дискретным стохастическим временем и мгновенными мультидействиями, названное дискретно-временным и мгновенным РВС (сИжРВС). В рамках этой алгебры стохастических процессов исследуются методы анализа производительности параллельных и распределенных систем со случайными временными задержками. Устанавливается, что оценка производительности возможна не только на основе полумарковских цепей, соответствующих выражениям сИжРВС, но и с использованием соответствующих дискретно-временных цепей Маркова, что является более оптимальной техникой анализа.
1. ВВЕДЕНИЕ
Алгебраические исчисления процессов — известная формальная модель для спецификации вычислительных систем и анализа их поведения. В таких процессных алгебрах (ПА) системы и процессы описываются формулами, и верификация их свойств выполняется на синтаксическом уровне с использованием эквивалентностей, аксиом и правил вывода. В последние десятилетия были предложены и получили широкое распространение стохастические расширения исчислений процессов. Стохастические процессные алгебры (СПА) не только описывают действия, которые выполняются (качественные свойства) подобно обычным алгебрам процессов, но также связывают некоторые количественные парамет-
* Работа была частично поддержана Испанским правительством, проект "Modeling and formal analysis of contracts and Web services with distributed resources", грант TIN2012-36812-C02-02. Первый автор также был частично поддержан Германским исследовательским обществом (DFG), грант BE 1267/14-1, и Российским фондом фундаментальных исследований (РФФИ), грант 14-01-91334.
ры с действиями (количественные характеристики). Самые известные СПА — MTIPP [1], PEPA [21 и КМ РА [3].
Исчисление боксов Петри РВС (Petri Box Calculus) [4, 5, 6] — гибкая и выразительная ПА, основанная на исчислении CCS [7] и разработанная как средство описания структуры сетей Петри и их взаимосвязей. Целью создания данного исчисления также являлось построение композициональной семантики конструкций высокого уровня языков параллельного программирования посредством элементарных сетей Петри. РВС обладает шаговой операционной семантикой в терминах помеченных систем переходов, основанной на правилах структурной операционной семантики. Денотационная семантика определена на основе подкласса сетей Петри (СП), названного боксами Петри (Petri boxes), сети из которого снабжены интерфейсом для взаимодействия друг с другом и рассматриваются с точностью до изоморфизма.
Стохастическое расширение РВС, названное стохастическим исчислением боксов Петри sPBC (stochastic РВС), предложено в [8]. Только ко-
нечная часть РВС была использована для стохастического обогащения, то есть sPBC не включает в себя операторы детализации, рекурсии и итерации. Исчисление имеет интерливинговую операционную семантику в терминах помеченных систем переходов. Денотационная семантика определена на основе подкласса помеченных непрерывно-временных стохастических СП (ПНВССП), названного стохастическими боксами Петри (s-боксами). Работа [9] описывает введение итерации в sPBC. Оценка производительности в sPBC выполняется исследованием соответствующего стохастического процесса, который является непрерывно-временной цепью Маркова (IIBMH).
В [10] sPBC с итерацией расширено мгновенными мультидействиями. Обозначим получившееся в результате исчисление gsPBC (generalized stochastic РВС). gsPBC обладает интерливинговой операционной семантикой на основе помеченных систем переходов. Денотационная семантика исчисления определена в терминах подкласса помеченных обобщенных стохастических СП (ПОССП), названного обобщенными стохастическими боксами Петри (gs-боксами). Анализ производительности в gsPBC выполняется на соответствующих полумарковских цепях (ИМИ).
В [11, 12] введено дискретно-временное стохастическое расширение dtsPBC (discrete time stochastic РВС) конечного РВС. Шаговая операционная семантика dtsPBC сконструирована с использованием помеченных вероятностных систем переходов. Денотационная семантика исчисления определена посредством подкласса помеченных дискретно-временных стохастических СП (ПДВССП), дискретно-временных стохастических боксов Петри (dts-боксами). В [13] к dtsPBC добавлен оператор итерации для спецификации бесконечных процессов. Для анализа производительности в dtsPBC сконструирован и изучен базовый стохастический процесс, дискретно-временная цепь Маркова (ДВМЦ).
В этой работе описываются методы оценки производительности вычислительных систем в окончательной версии алгебры dtsiPBC (discrete time stochastic and immediate РВС), введенной в [14]. dtsiPBC — расширение dtsPBC с ите-
рацией мгновенными мультидействиями, имеющими нулевую временную задержку. Мгновенные мультидействия увеличивают возможности спецификации: они могут моделировать моментальный вероятностный выбор, а также активности, продолжительность которых незначительна по сравнению с длительностью других, что позволяет получить более простое и ясное представление специфицируемых систем. Таким образом, dtsiPBC обладает параллельной дискретно-временной семантикой с геометрически распределенными (как в dtsPBC) или нулевыми задержками в состояниях алгебраических процессов. В непрерывно-временной семантике, используемой в вРВС и gsPBC, параллелизм моделируется интерливингом, так как для любых двух событий вероятность случиться одновременно равна нулю по свойствам непрерывных распределений вероятностей. Приводится синтаксис исчисления dtsiPBC. Затем конструируются его шаговая операционная семантика на основе помеченных вероятностных систем переходов и денотационная семантика на подклассе помеченных дискретно-временных стохастических и мгновенных СП (ПДВСМСП), названного дискретно-временными стохастическими и мгновенными боксами Петри (сК^-боксами). В качестве формализма для оценки производительности в dtsiPBC находится и исследуется соответствующий обеим семантикам стохастический процесс, являющийся ПМЦ. Также разрабатывается альтернативный и более оптимальный метод решения на основе соответствующей ДВМЦ.
Данная статья является расширенной и модифицированной версией предыдущей работы [15], опубликованной в трудах международного семинара по практическому применению стохастического моделирования, за счет подробного описания синтаксиса и семантики алгебры dtsiPBC, определения и использования дополнительных важных понятий (например, нумерации выражений, функции нумерования и т.д), а также разработки нового альтернативного метода оценки производительности и добавления иллюстративных примеров.
Структура дальнейшего изложения такова. В разделе 2 вводится синтаксис алгебры dtsiPBC. В разделе 3 конструируется операционная семан-
тика, а в разделе 4 — денотационная семантика. Стандартный и альтернативный методы оценки производительности представлены в разделе 5. В заключительном разделе 6 дается обзор полученных результатов и определяются перспективы дальнейших исследований.
2. СИНТАКСИС
В этом разделе вводится синтаксис алгебры сШРВС.
Конечное мультимножество М над множеством X — отображение М : X ^ IV такое, что |{ж е X | М(ж) > 0}| < те. Множество всех конечных мультимножеств над X обозна-
чим Nx. Пусть M, M' G Nf. Мощ ность M есть |M | = xex M (ж). Пишем x G M, если M (x) > 0, и M С M', если Vx G X M (x) < M'(x). Определим (M + M')(x) = M (x) + M'(x) и (M - M' )(x) = max{0, M (x) - M '(x)}. Если Vx G X M (x) < 1, то M можно интерпретировать как обычное множество.
Пусть Act = {a, b,...} — множество элементарных действий. Тогда Act = {a, b,...} — множество парных действий (конъюгатов) таких, что a = и a = a. Пусть A = Act U Act — множество всех действий и L = N^ — множество всех мультидействий. Заметим, что 0 G L соответствует внутренней активности, то есть выполнению мультидействия, не содержащего имен видимых действий. Алфавит, мультидействия a G L определяется как A(a) = {x G A | a(x) > 0}.
Стохастическое мультидействие — пара (a, р), где a G L и р G (0; 1) — вероятность a
претируется как вероятность независимого выполнения стохастического мультидействия в следующий момент дискретного времени. Такие вероятности используются для вычисления вероятностей выполнения (возможно, пустых) мультимножеств стохастических мультидействий после задержки в единицу времени. Мы требуем, чтобы вероятности стохастических
1
чтобы избежать роста сложности используемой модели из-за необходимости присвоения им используемых для выбора весов, когда из некоторого состояния можно выполнить несколько
1
случае возникают проблемы с разрешением конфликтов. Дискуссия об аналогичной ситуации в рамках ДВССП имеется в [16]. Данное решение также позволяет избежать технических сложностей, связанных с вычислением условной
0
С другой стороны, нет смысла рассматривать 0
невозможно будет выполнить. Пусть 5 С — множество всех стохастических мультидействий.
Мгновенное мультидействие — пара (а, 1), где а е Си 1 е IV \ {0} — ненулевой вес мультидействия а. Этот вес интерпретируется как мера значимости, срочности или бонусная премия, связанная с выполнением мгновенного мультидействия в текущий момент дискретного времени. Такие веса используются для вычисления вероятностей моментального выполнения мультимножеств мгновенных мультидействий. Мгновенные мультидействия имеют приоритет над стохастическими. Можно считать, что все мгновенные мультидействия имеют приоритет 1, а все стохастические мультидействия имеют при-0
тором могут быть выполнены оба типа мультидейст
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.