Продуктово-форменное решение

Форма решения в теории вероятностей

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

П ( х 1 , х 2 , х 3 , … , х н ) = Б ∏ я = 1 н П ( х я ) {\displaystyle {\text{P}}(x_{1},x_{2},x_{3},\ldots ,x_{n})=B\prod _{i=1}^{n}{\text{P}}(x_{i})}

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

Равновесные распределения

Первые решения в форме произведения были найдены для равновесных распределений цепей Маркова . Тривиально, модели, состоящие из двух или более независимых подкомпонентов, демонстрируют решение в форме произведения по определению независимости. Первоначально этот термин использовался в сетях очередей , где подкомпонентами были отдельные очереди. Например, теорема Джексона дает совместное равновесное распределение открытой сети очередей как произведение равновесных распределений отдельных очередей. [1] После многочисленных расширений, в основном сети BCMP, считалось, что локальный баланс является требованием для решения в форме произведения. [2] [3]

Модель G-сети Геленбе была первой, показавшей, что это не так. Мотивированный необходимостью моделирования биологических нейронов, которые имеют точечно-процессное поведение, подобное спайковому, он представил предшественника G-сетей, назвав его случайной нейронной сетью . [4] Введя «отрицательных клиентов», которые могут уничтожать или устранять других клиентов, он обобщил семейство сетей формы продукта. [5] Затем это было дополнительно расширено в несколько этапов, сначала «триггерами» Геленбе, которые являются клиентами, которые имеют право перемещать других клиентов из одной очереди в другую. [6] Другой новой формой клиента, которая также привела к форме продукта, было «удаление партии» Геленбе. [7] Это было дополнительно расширено Эролом Геленбе и Жаном-Мишелем Фурно с типами клиентов, называемыми «сбросами», которые могут моделировать исправление сбоев: когда очередь достигает пустого состояния, представляя (например) сбой, длина очереди может вернуться назад или быть «сброшена» до своего устойчивого распределения прибывающим сброшенным клиентом, представляющим исправление. Все эти предыдущие типы клиентов в G-сетях могут существовать в одной и той же сети, в том числе с несколькими классами, и все они вместе по-прежнему приводят к решению в форме продукта, выводя нас далеко за пределы обратимых сетей, которые рассматривались ранее. [8]

Решения в форме продукта иногда описываются как «станции независимы в равновесии». [9] Решения в форме продукта также существуют в сетях массовых очередей . [10]

Дж. М. Харрисон и Р. Дж. Уильямс отмечают, что «практически все модели, которые были успешно проанализированы в классической теории сетей массового обслуживания, являются моделями, имеющими так называемое стационарное распределение в форме произведения» [9]. Совсем недавно были опубликованы решения в форме произведения для алгебр марковских процессов (например, RCAT в PEPA [11] [12] ) и стохастических сетей Петри . [13] [14] Теорема Мартина Файнберга о нулевом дефиците дает достаточное условие для того, чтобы сети химических реакций демонстрировали стационарное распределение в форме произведения. [15]

Работа Геленбе также показывает, что продукт формы G-сетей может быть использован для моделирования импульсных случайных нейронных сетей , и, более того, такие сети могут быть использованы для аппроксимации ограниченных и непрерывных функций с действительными значениями. [16] [17]

Распределение времени пребывания

Термин «форма произведения» также использовался для обозначения распределения времени пребывания в циклической системе массового обслуживания, где время, проведенное заданиями в узлах M , задается как произведение времени, проведенного в каждом узле. [18] В 1957 году Райх показал результат для двух очередей M/M/1 в тандеме, [19] позже расширив его до n очередей M/M/1 в тандеме [20] , и было показано, что он применим к путям без обгона в сетях Джексона . [21] Уолранд и Варайя предполагают, что отсутствие обгона (когда клиенты не могут обогнать других клиентов, выбрав другой маршрут через сеть) может быть необходимым условием для сохранения результата. [21] Митрани предлагает точные решения для некоторых простых сетей с обгоном, показывая, что ни одна из них не демонстрирует распределения времени пребывания в форме произведения. [22]

Для закрытых сетей Чжоу показал, что результат справедлив для двух узлов обслуживания [23] , который позже был обобщен на цикл очередей [24] и на пути без обгона в сетях Гордона–Ньюэлла . [25] [26]

Расширения

  • Приближенные решения в форме произведения вычисляются с учетом независимых предельных распределений, что может дать хорошее приближение к стационарному распределению при некоторых условиях. [27] [28]
  • Решения в форме полупродукта — это решения, в которых распределение можно записать в виде продукта, где члены имеют ограниченную функциональную зависимость от глобального пространства состояний, которое можно аппроксимировать. [29]
  • Решения в форме квазипродукта являются либо
    • решения, которые не являются произведением предельных плотностей, но предельные плотности описывают распределение в стиле произведения [30] или
    • Приближенная форма для распределений вероятностей переходных процессов, которая позволяет аппроксимировать переходные моменты. [31]

Ссылки

  1. ^ Джексон, Джеймс Р. (1963). «Системы очередей типа Jobshop». Management Science . 10 (1): 131– 142. doi :10.1287/mnsc.10.1.131.
  2. ^ Бушери, Ричард Дж.; ван Дейк, Н. М. (1994). «Локальный баланс в сетях очередей с положительными и отрицательными клиентами». Annals of Operations Research . 48 (5): 463– 492. doi :10.1007/BF02033315. hdl : 1871/12327 . S2CID  15599820.
  3. ^ Чанди, К. Мани ; Говард, Дж. Х. Мл.; Тоусли, Д. Ф. (1977). «Форма продукта и локальный баланс в сетях массового обслуживания». Журнал ACM . 24 (2): 250–263 . doi : 10.1145/322003.322009 . S2CID  6218474.
  4. ^ Геленбе, Эрол (1989). «Случайные нейронные сети с отрицательными и положительными сигналами и решение в форме продукта». Neural Computation . 1 (4): 502– 510. doi :10.1162/neco.1989.1.4.502. S2CID  207737442.
  5. ^ Геленбе, Эрол (1991). «Сети очередей в форме произведения с отрицательными и положительными клиентами». Журнал прикладной вероятности . 28 (3): 656– 663. doi :10.2307/3214499. JSTOR  3214499.
  6. ^ Геленбе, Эрол (1993). «G-сети с инициированным движением клиентов». Журнал прикладной вероятности . 30 (3): 742– 748. doi :10.2307/3214781. JSTOR  3214781.
  7. ^ Геленбе, Эрол (1993). «G-сети с инициированным движением клиентов». Вероятность в инженерных и информационных науках . 7 (3): 335– 342. doi :10.1017/S0269964800002953.
  8. ^ Геленбе, Эрол ; Фурно, Жан-Мишель (2002). «G-сети со сбросами». Оценка производительности . 49 (1): 179– 191. doi :10.1016/S0166-5316(02)00127-X.
  9. ^ ab Harrison, JM ; Williams, RJ (1992). «Броуновские модели сетей очередей прямого распространения: квазиобратимость и решения в форме произведения». Annals of Applied Probability . 2 (2): 263– 293. CiteSeerX 10.1.1.56.1572 . doi :10.1214/aoap/1177005704. 
  10. ^ Хендерсон, У.; Тейлор, П. Г. (1990). «Форма продукта в сетях очередей с пакетным прибытием и пакетным обслуживанием». Системы очередей . 6 : 71– 87. doi :10.1007/BF02411466. S2CID  30949152.
  11. ^ Хиллстон, Дж.; Томас, Н. (1999). "Решение формы продукта для класса моделей PEPA" (PDF) . Оценка производительности . 35 ( 3–4 ): 171–192 . doi :10.1016/S0166-5316(99)00005-X. hdl : 20.500.11820/13c57018-5854-4f34-a4c9-833262a71b7c .
  12. ^ Harrison, PG (2003). «Возвращение времени вспять в алгебре марковских процессов». Теоретическая информатика . 290 (3): 1947– 2013. doi : 10.1016/S0304-3975(02)00375-4 . Архивировано из оригинала 2006-10-15 . Получено 2015-08-29 .
  13. ^ Марин, А.; Бальзамо, С.; Харрисон, П. Г. (2012). «Анализ стохастических сетей Петри с сигналами». Оценка производительности . 69 (11): 551– 572. doi :10.1016/j.peva.2012.06.003. hdl : 10044/1/14180 .
  14. ^ Mairesse, J.; Nguyen, HT (2009). "Deficiency Zero Petri Networks and Product Form". Applications and Theory of Petri Nets . Lecture Notes in Computer Science. Vol. 5606. p. 103. CiteSeerX 10.1.1.745.1585 . doi :10.1007/978-3-642-02424-5_8. ISBN  978-3-642-02423-8.
  15. ^ Андерсон, ДФ; Крачун, Г.; Курц, ТГ (2010). «Стационарные распределения в форме продукта для сетей химических реакций с нулевым дефицитом». Бюллетень математической биологии . 72 (8): 1947–1970 . arXiv : 0803.3042 . doi : 10.1007/s11538-010-9517-4. PMID  20306147. S2CID  2204856.
  16. ^ Геленбе, Эрол (1993). «Обучение в рекуррентной случайной нейронной сети». Neural Computation . 5 (1): 154– 164. doi :10.1162/neco.1993.5.1.154. S2CID  38667978.
  17. ^ Геленбе, Эрол ; Мао, Чжи-Хун; Ли, Ян-Да (1991). «Аппроксимация функций с помощью случайной нейронной сети». Труды IEEE по нейронным сетям . 10 (1): 3– 9. CiteSeerX 10.1.1.46.7710 . doi :10.1109/72.737488. PMID  18252498. 
  18. ^ Boxma, OJ ; Kelly, FP ; Konheim, AG (январь 1984). «Форма продукта для распределений времени пребывания в циклических экспоненциальных очередях». Журнал ACM . 31 (1): 128– 133. doi : 10.1145/2422.322419 . S2CID  6770615.
  19. ^ Райх, Эдгар (1957). «Время ожидания, когда очереди расположены тандемом». Анналы математической статистики . 28 (3): 768– 773. doi : 10.1214/aoms/1177706889 .
  20. ^ Райх, Э. (1963). «Заметка об очередях в тандеме». Анналы математической статистики . 34 : 338–341 . doi : 10.1214/aoms/1177704275 .
  21. ^ ab Walrand, J. ; Varaiya, P. (1980). «Времена пребывания и условие обгона в сетях Джексона». Advances in Applied Probability . 12 (4): 1000– 1018. doi :10.2307/1426753. JSTOR  1426753.
  22. ^ Митрани, И. (1985). «Проблемы времени отклика в сетях связи». Журнал Королевского статистического общества. Серия B (методологическая) . 47 (3): 396– 406. doi :10.1111/j.2517-6161.1985.tb01368.x. JSTOR  2345774.
  23. ^ Chow, We-Min (апрель 1980 г.). «Распределение времени цикла экспоненциальных циклических очередей». Журнал ACM . 27 (2): 281– 286. doi : 10.1145/322186.322193 . S2CID  14084475.
  24. ^ Шассбергер, Р.; Дадуна, Х. (1983). «Время кругового обхода в цикле экспоненциальных очередей». Журнал ACM . 30 : 146–150 . doi : 10.1145/322358.322369 . S2CID  33401212.
  25. ^ Дадуна, Х. (1982). «Время прохождения для путей без обгона в сетях Гордона-Ньюэлла». Advances in Applied Probability . 14 (3): 672– 686. doi :10.2307/1426680. JSTOR  1426680.
  26. ^ Келли, Ф. П.; Поллетт, П. К. (1983). «Время пребывания в закрытых сетях очередей». Advances in Applied Probability . 15 (3): 638– 656. doi :10.2307/1426623. JSTOR  1426623.
  27. ^ Baynat, B.; Dallery, Y. (1993). "Единый взгляд на методы аппроксимации в форме произведения для общих замкнутых сетей очередей". Оценка производительности . 18 (3): 205– 224. doi :10.1016/0166-5316(93)90017-O.
  28. ^ Dallery, Y.; Cao, XR (1992). «Операционный анализ стохастических замкнутых сетей очередей». Оценка производительности . 14 : 43–61 . doi :10.1016/0166-5316(92)90019-D.
  29. ^ Томас, Найджел; Харрисон, Питер Г. (2010). "Зависящие от состояния ставки и полупродуктовая форма через обратный процесс". Computer Performance Engineering . Lecture Notes in Computer Science. Vol. 6342. p. 207. doi :10.1007/978-3-642-15784-4_14. ISBN 978-3-642-15783-7.
  30. ^ Дебицкий, К.; Дикер, А. Б.; Рольски, Т. (2007). «Квазипродуктовые формы для сетей жидкости, управляемых Леви». Математика исследования операций . 32 (3): 629– 647. arXiv : math/0512119 . doi : 10.1287/moor.1070.0259. S2CID  16150704.
  31. ^ Angius, A.; Horváth, AS; Wolf, V. (2013). "Approximate Transient Analysis of Queuing Networks by Quasi Product Forms". Analytical and Stochastic Modeling Techniques and Applications . Lecture Notes in Computer Science. Vol. 7984. p. 22. doi :10.1007/978-3-642-39408-9_3. ISBN 978-3-642-39407-2.
Получено с "https://en.wikipedia.org/w/index.php?title=Product-form_solution&oldid=1186333939"