Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Равновесные распределения [ править ]

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

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

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

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

Работа Геленбе также показывает, что форма продукта G-Networks может использоваться для моделирования случайных нейронных сетей с пиками , и, кроме того, такие сети могут использоваться для аппроксимации ограниченных и непрерывных функций с действительными значениями. [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). «Системы массового обслуживания по типу рабочих мест». Наука управления . 10 (1): 131–142. DOI : 10.1287 / mnsc.10.1.131 .
  2. ^ Бушери, Ричард Дж .; ван Дейк, Н.М. (1994). «Локальный баланс в сетях массового обслуживания с положительными и отрицательными заявками» . Анналы исследований операций . 48 (5): 463–492. DOI : 10.1007 / BF02033315 . ЛВП : 1871/12327 . S2CID 15599820 . 
  3. ^ Чанди, К. Мани ; Ховард, Дж. Х. младший; Тоусли, Д. Ф. (1977). «Форма продукта и локальный баланс в сетях массового обслуживания». Журнал ACM . 24 (2): 250–263. DOI : 10.1145 / 322003.322009 . S2CID 6218474 . 
  4. ^ Gelenbe Эрол (1989). «Случайные нейронные сети с отрицательными и положительными сигналами и решение формы продукта». Нейронные вычисления . 1 (4): 502–510. DOI : 10.1162 / neco.1989.1.4.502 . S2CID 207737442 . 
  5. ^ Gelenbe Эрол (1991). «Продуктовые сети массового обслуживания с отрицательными и положительными потребителями» . Журнал прикладной теории вероятностей . 28 (3): 656–663. DOI : 10.2307 / 3214499 . JSTOR 3214499 . 
  6. ^ Gelenbe Эрол (1993). «G-сети с триггерным движением клиентов». Журнал прикладной теории вероятностей . 30 (3): 742–748. DOI : 10.2307 / 3214781 . JSTOR 3214781 . 
  7. ^ Gelenbe Эрол (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. ^ а б Харрисон, JM ; Уильямс, RJ (1992). «Броуновские модели сетей массового обслуживания с прямой связью: квазиобратимость и продуктовые решения». Анналы прикладной теории вероятностей . 2 (2): 263–293. CiteSeerX 10.1.1.56.1572 . DOI : 10.1214 / aoap / 1177005704 . 
  10. ^ Хендерсон, В .; Тейлор, PG (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 .
  12. Перейти ↑ Harrison, PG (2003). «Обращение вспять в алгебре марковских процессов» . Теоретическая информатика . 290 (3): 1947–2013. DOI : 10.1016 / S0304-3975 (02) 00375-4 . Архивировано из оригинала на 2006-10-15 . Проверено 29 августа 2015 .
  13. ^ Марин, А .; Balsamo, S .; Харрисон, PG (2012). «Анализ стохастических сетей Петри с сигналами». Оценка производительности . 69 (11): 551–572. DOI : 10.1016 / j.peva.2012.06.003 . hdl : 10044/1/14180 .
  14. ^ Mairesse, J .; Нгуен, HT (2009). «Сети Петри с нулевым дефицитом и форма продукта». Приложения и теория сетей Петри . Конспект лекций по информатике. 5606 . п. 103. CiteSeerX 10.1.1.745.1585 . DOI : 10.1007 / 978-3-642-02424-5_8 . ISBN  978-3-642-02423-8.
  15. ^ Андерсон, Д. Ф.; Craciun, G .; Курц, Т.Г. (2010). "Стационарные распределения продукта-формы для сетей химической реакции с нулевым дефицитом". Вестник математической биологии . 72 (8): 1947–1970. arXiv : 0803.3042 . DOI : 10.1007 / s11538-010-9517-4 . PMID 20306147 . S2CID 2204856 .  
  16. ^ Gelenbe Эрол (1993). «Обучение в повторяющейся случайной нейронной сети». Нейронные вычисления . 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 ; Келли, ФП ; Konheim, AG (январь 1984 г.). "Форма продукта для распределения времени пребывания в циклических экспоненциальных очередях". Журнал ACM . 31 (1): 128–133. DOI : 10.1145 / 2422.322419 . S2CID 6770615 . 
  19. ^ Райх, Эдгар (1957). «Время ожидания при тандемных очередях» . Летопись математической статистики . 28 (3): 768–773. DOI : 10.1214 / АОМ / 1177706889 .
  20. ^ Райх, Э. (1963). «Примечание об очередях в тандеме» . Летопись математической статистики . 34 : 338–341. DOI : 10.1214 / АОМ / 1177704275 .
  21. ^ a b Walrand, J .; Варайя, П. (1980). «Времена пребывания и условия обгона в Джексоновских сетях». Достижения в прикладной теории вероятностей . 12 (4): 1000–1018. DOI : 10.2307 / 1426753 . JSTOR 1426753 . 
  22. ^ Митрани, И. (1985). «Проблемы времени отклика в сетях связи». Журнал Королевского статистического общества. Серия Б (Методическая) . 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. ^ Schassberger, R .; Дадуна, Х. (1983). «Время для обхода в цикле экспоненциальных очередей». Журнал ACM . 30 : 146–150. DOI : 10.1145 / 322358.322369 . S2CID 33401212 . 
  25. ^ Дадуна, Х. (1982). «Время прохождения путей без обгона в сетях Гордона-Ньюэлла». Достижения в прикладной теории вероятностей . 14 (3): 672–686. DOI : 10.2307 / 1426680 . JSTOR 1426680 . 
  26. ^ Келли, FP ; Поллетт, ПК (1983). «Время пребывания в закрытых сетях массового обслуживания». Достижения в прикладной теории вероятностей . 15 (3): 638–656. DOI : 10.2307 / 1426623 . JSTOR 1426623 . 
  27. ^ Байнат, В .; Даллери Ю. (1993). «Единый взгляд на методы аппроксимации продуктовой формы для общих замкнутых сетей массового обслуживания». Оценка производительности . 18 (3): 205–224. DOI : 10.1016 / 0166-5316 (93) 90017-O .
  28. ^ Dallery, Y .; Цао, XR (1992). «Оперативный анализ стохастических замкнутых сетей массового обслуживания». Оценка производительности . 14 : 43–61. DOI : 10.1016 / 0166-5316 (92) 90019-D .
  29. ^ Томас, Найджел; Харрисон, Питер Г. (2010). «Зависящие от государства ставки и полуфабрикат с помощью обратного процесса». Инженерия производительности компьютеров . Конспект лекций по информатике. 6342 . п. 207. DOI : 10.1007 / 978-3-642-15784-4_14 . ISBN 978-3-642-15783-7.
  30. ^ Debicki, K .; Dieker, AB; Рольски, Т. (2007). «Формы квазипродукта для жидкостных сетей, управляемых Леви». Математика исследования операций . 32 (3): 629–647. arXiv : математика / 0512119 . DOI : 10.1287 / moor.1070.0259 . S2CID 16150704 . 
  31. ^ Angius, A .; Horváth, AS; Вольф, В. (2013). «Приближенный переходный анализ сетей массового обслуживания по формам квазипродуктов». Методы и приложения аналитического и стохастического моделирования . Конспект лекций по информатике. 7984 . п. 22. DOI : 10.1007 / 978-3-642-39408-9_3 . ISBN 978-3-642-39407-2.