БУМАГА

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

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

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

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

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

Синтаксис [ править ]

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

P::=(a,\lambda ).P\,\,\,|\,\,\,P+Q\,\,\,|\,\,\,P{\stackrel {\triangleright \!\!\triangleleft }{\scriptstyle {L}}}Q\,\,\,|\,\,\,P/L\,\,\,|\,\,\,A

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

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

Инструменты [ править ]

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

Ссылки [ править ]

^ Хиллстон, Джейн (1996). Композиционный подход к моделированию производительности . Издательство Кембриджского университета. ISBN 0-521-57189-8 . Проверено 21 апреля 2009 г.
^ «Проект плагина PEPA» .
^ Трибастон, М.; Дугид, А.; Гилмор, С. (2009). «Плагин PEPA eclipse» (PDF) . Обзор оценки производительности ACM SIGMETRICS . 36 (4): 28. дои : 10.1145/1530873.1530880 . S2CID 7715443 .
^ «ipc: Имперский компилятор PEPA» . www.doc.ic.ac.uk.
^ Брэдли, Джей Ти; Дингл, Нью-Джерси; Гилмор, Северная Каролина; Ноттенбелт, WJ (2003). «Вывод плотности времени прохождения в моделях PEPA с использованием ipc: имперский компилятор PEPA» (PDF) . 11-й Международный симпозиум IEEE/ACM по моделированию, анализу и симуляции компьютерных телекоммуникационных систем, 2003 г. MASCOTS 2003 . п. 344. дои : 10.1109/MASCOT.2003.1240679 . hdl : 10044/1/5750 . ISBN 0-7695-2039-1 . S2CID 97207 .
^ «Архив кода Google — долгосрочное хранилище для хостинга проектов Google Code» . code.google.com .
^ Стефанек, А.; Хайден, РА; Брэдли, Джей Ти (2011). «GPA - инструмент для гибкого анализа масштабируемости массово параллельных систем». 2011 Восьмая Международная конференция по количественной оценке систем . п. 147. дои : 10.1109/QEST.2011.26 . ISBN 978-1-4577-0973-9 . S2CID 10220707 .

Внешние ссылки [ править ]

PEPA: Алгебра процесса оценки эффективности

[1] Хиллстон, Джейн (1996). Композиционный подход к моделированию производительности . Издательство Кембриджского университета. ISBN 0-521-57189-8 . Проверено 21 апреля 2009 г.

[2] «Проект плагина PEPA» .

[3] Трибастон, М.; Дугид, А.; Гилмор, С. (2009). «Плагин PEPA eclipse» (PDF) . Обзор оценки производительности ACM SIGMETRICS . 36 (4): 28. дои : 10.1145/1530873.1530880 . S2CID 7715443 .

[4] «ipc: Имперский компилятор PEPA» . www.doc.ic.ac.uk.

[5] Брэдли, Джей Ти; Дингл, Нью-Джерси; Гилмор, Северная Каролина; Ноттенбелт, WJ (2003). «Вывод плотности времени прохождения в моделях PEPA с использованием ipc: имперский компилятор PEPA» (PDF) . 11-й Международный симпозиум IEEE/ACM по моделированию, анализу и симуляции компьютерных телекоммуникационных систем, 2003 г. MASCOTS 2003 . п. 344. дои : 10.1109/MASCOT.2003.1240679 . hdl : 10044/1/5750 . ISBN 0-7695-2039-1 . S2CID 97207 .

[6] «Архив кода Google — долгосрочное хранилище для хостинга проектов Google Code» . code.google.com .

[7] Стефанек, А.; Хайден, РА; Брэдли, Джей Ти (2011). «GPA - инструмент для гибкого анализа масштабируемости массово параллельных систем». 2011 Восьмая Международная конференция по количественной оценке систем . п. 147. дои : 10.1109/QEST.2011.26 . ISBN 978-1-4577-0973-9 . S2CID 10220707 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

v т и Параллельные вычисления
Общий	Параллелизм Управление параллелизмом Параллельные структуры данных Параллельные хэш-таблицы Одновременные пользователи Неопределенность Линеаризуемость
Процесс исчисления	CSP CCS АШП ЛОТОС π-исчисление Окружающее исчисление API-исчисление БУМАГА Джойн-исчисление
Классические задачи	проблема ABA Проблема курильщиков сигарет Тупик Проблема обедающих философов Проблема производителя и потребителя Состояние гонки Проблема читателей и писателей Проблема со спящим парикмахером
Категория: Параллельные вычисления