ПЕПА
Процесс исчисления

Алгебра процессов оценки производительности ( PEPA ) — это стохастическая алгебра процессов , разработанная для моделирования компьютерных и коммуникационных систем, представленная Джейн Хиллстон в 1990-х годах. [1] Язык расширяет классические алгебры процессов, такие как CCS Милнера и CSP Хоара, путем введения вероятностного ветвления и синхронизации переходов.

Скорости берутся из экспоненциального распределения , а модели PEPA являются конечными и, таким образом, приводят к стохастическому процессу , в частности, непрерывному процессу Маркова (CTMC). Таким образом, язык может использоваться для изучения количественных свойств моделей компьютерных и коммуникационных систем, таких как пропускная способность , использование и время отклика , а также качественных свойств, таких как отсутствие тупиков . Язык формально определен с использованием структурированной операционной семантики в стиле, изобретенном Гордоном Плоткиным .

Как и большинство алгебр процессов, PEPA является экономным языком. Он имеет только четыре комбинатора: префикс , выбор , кооперацию и сокрытие . Префикс является основным строительным блоком последовательного компонента: процесс ( a , r ). P выполняет действие a со скоростью r, прежде чем эволюционировать и вести себя как компонент P. Выбор устанавливает соревнование между двумя возможными альтернативами: в процессе ( a , r ). P + ( b , s ). Q либо a выигрывает гонку (и процесс впоследствии ведет себя как P ), либо b выигрывает гонку (и процесс впоследствии ведет себя как Q ).

Оператор кооперации требует, чтобы два «кооперанда» объединились для тех действий, которые указаны в наборе кооперации: в процессе P < a , b > Q процессы P и Q должны кооперироваться в действиях a и b , но любые другие действия могут выполняться независимо. Теорема об обратном составном агенте дает набор достаточных условий для того, чтобы кооперация имела форму продукта стационарного распределения .

Наконец, процесс P /{ a } скрывает действие a от просмотра (и не позволяет другим процессам присоединиться к нему).

Синтаксис

Учитывая набор имен действий, набор процессов PEPA определяется следующей грамматикой BNF :

П ::= ( а , λ ) . П | П + В | П Л ▹ ◃ В | П / Л | А {\displaystyle P::=(a,\lambda ).P\,\,\,|\,\,\,P+Q\,\,\,|\,\,\,P{\stackrel {\triangleright \!\!\triangleleft }{\scriptstyle {L}}}Q\,\,\,|\,\,\,P/L\,\,\,|\,\,\,A}

Части синтаксиса приведены в порядке, указанном выше:

действие
процесс может выполнить действие a со скоростью и продолжиться как процесс P. ( а , λ ) . П {\displaystyle (a,\lambda).P} λ {\displaystyle \лямбда}
выбор
процесс P+Q может вести себя как процесс P или как процесс Q.
сотрудничество
Процессы P и Q существуют одновременно и ведут себя независимо для действий, имена которых не появляются в L. Для действий, имена которых появляются в L , действие должно выполняться совместно, а состояние гонки определяет время, которое это займет.
прячется
процесс P ведет себя как обычно для имен действий, не входящих в L , и выполняет молчаливое действие для имен действий, которые появляются в L . τ {\displaystyle \тау}
идентификатор процесса
написать, чтобы использовать идентификатор A для ссылки на процесс P. А = г е ф П {\displaystyle A{\overset {\underset {\mathrm {def} }{}}{=}}P}

Инструменты

  • Плагин PEPA [2] для Eclipse [3]
  • ipc: имперский компилятор PEPA [4] [5]
  • GPAnalyser [6] для анализа жидкостей в массивно-параллельных системах [7]

Ссылки

  1. ^ Хиллстон, Джейн (1996). Композиционный подход к моделированию производительности . Cambridge University Press. ISBN 0-521-57189-8. Получено 21.04.2009 .
  2. ^ «Проект подключаемого модуля PEPA».
  3. ^ Tribastone, M.; Duguid, A.; Gilmore, S. (2009). "Плагин PEPA eclipse" (PDF) . Обзор оценки производительности ACM SIGMETRICS . 36 (4): 28. doi :10.1145/1530873.1530880. S2CID  7715443.
  4. ^ "ipc: Имперский компилятор PEPA" . www.doc.ic.ac.uk.​
  5. ^ Брэдли, Дж. Т.; Дингл, Н. Дж.; Гилмор, СТ.; Кноттенбелт, В. Дж. (2003). "Вывод плотностей времени прохождения в моделях PEPA с использованием ipc: имперский компилятор PEPA" (PDF) . 11-й Международный симпозиум IEEE/ACM по моделированию, анализу и имитации компьютерных телекоммуникационных систем, 2003. MASCOTS 2003. стр. 344. doi :10.1109/MASCOT.2003.1240679. hdl :10044/1/5750. ISBN 0-7695-2039-1. S2CID  97207.
  6. ^ "Архив Google Code — долгосрочное хранилище для хостинга проектов Google Code". code.google.com .
  7. ^ Стефанек, А.; Хейден, Р.А.; Брэдли, Дж.Т. (2011). "GPA - Инструмент для анализа масштабируемости жидкости в массивно-параллельных системах". Восьмая международная конференция по количественной оценке систем 2011 г. стр. 147. doi :10.1109/QEST.2011.26. ISBN 978-1-4577-0973-9. S2CID  10220707.
  • PEPA: Алгебра процесса оценки производительности
Взято с "https://en.wikipedia.org/w/index.php?title=PEPA&oldid=1241386555"