Разветвить очередь – присоединиться к ней

Узел очереди с разветвлением и объединением

В теории массового обслуживания , дисциплине математической теории вероятностей , очередь разветвления-объединения — это очередь, в которой входящие задания разделяются по прибытии для обслуживания многочисленными серверами и объединяются перед отправкой. ^[1] Модель часто используется для параллельных вычислений. ^[2] или системы, в которых продукцию необходимо получать одновременно от разных поставщиков (на складе или в производстве). ^[3]^: 78–80 Ключевой величиной, представляющей интерес в этой модели, обычно является время, необходимое для обслуживания всей работы. Модель была описана как «ключевая модель для анализа производительности параллельных и распределенных систем ». ^[4] Для очередей разветвления и соединения существует мало аналитических результатов, но известны различные приближения.

Ситуацию, когда рабочие места поступают в соответствии с процессом Пуассона , а время обслуживания распределяется экспоненциально, иногда называют моделью Флатто-Хана-Райта или моделью FHW . ^[5]^[6]^[7]

Определение

По прибытии в точку разветвления задание разбивается на N подзаданий, которые обслуживаются каждым из N серверов. После обслуживания подзадание ожидает, пока все остальные подзадания также не будут обработаны. Затем подзадания снова соединяются и покидают систему. ^[3]

Чтобы очередь fork-join была стабильной, скорость ввода должна быть строго меньше суммы скоростей обслуживания на узлах обслуживания. ^[8]

Приложения

Очереди разветвления-объединения использовались для моделирования зональных RAID- систем. ^[9] параллельные вычисления ^[2] и для моделирования выполнения заказов на складах. ^[3]

Время ответа

Время ответа (или время пребывания ^[10]) — общее количество времени, которое задание проводит в системе.

Распределение

Ко и Серфозо дают аппроксимацию распределения времени отклика, когда время обслуживания распределено экспоненциально и задания поступают либо в соответствии с процессом Пуассона. ^[11] или общее распределение. ^[12] Кью, Перес и Харрисон предлагают метод аппроксимации, когда время обслуживания имеет распределение фазового типа . ^[13]

Среднее время ответа

Точная формула среднего времени ответа известна только в случае двух серверов ( N =2) с экспоненциально распределенным временем обслуживания (где каждый сервер представляет собой очередь M/M/1 ). В этой ситуации время ответа (общее время, которое задание проводит в системе) равно ^[14]

{\frac {12-\rho }{8\mu (1-\rho )}}

где

$\rho =\lambda /\mu$ это утилизация.
$\lambda$ — скорость поступления заданий на все узлы.
$\mu$ — скорость обслуживания во всех узлах.

В ситуации, когда узлами являются очереди M/M/1 и N > 2, модификация Варки анализа среднего значения также может использоваться для получения приблизительного значения среднего времени ответа. ^[15]

Для общего времени обслуживания (где каждый узел представляет собой очередь M/G/1 ) Бачелли и Маковски дают границы среднего времени ответа и более высоких моментов этой величины как в переходных, так и в устойчивых ситуациях. ^[16] Кемпер и Манджес показывают, что для некоторых параметров эти границы не являются жесткими, и демонстрируют метод аппроксимации. ^[10] Для гетерогенных очередей с разветвлением (очередей с разветвлением с разным временем обслуживания) Аломари и Менассе предлагают аппроксимацию, основанную на числах гармоник, которую можно расширить для охвата более общих случаев, таких как вероятностные очереди с разветвлением, открытые и закрытые очереди с разветвлением. ^[17]

Рассредоточение подзадач

Дисперсия подзадач, определяемая как диапазон времени обслуживания, может быть рассчитана численно и введена оптимальная детерминированная задержка для минимизации диапазона. ^[18]

Стационарное распределение

В целом стационарное распределение ^{[ сломанный якорь ]} количество заданий в каждой очереди является неразрешимым. ^[11] Флэтто рассмотрел случай двух серверов ( N=2 ) и получил стационарное распределение количества заданий в каждой очереди с помощью методов униформизации . ^[5] Пиноци и Зазанис показывают, что решение в форме продукта существует, когда поступления детерминированы, поскольку тогда длины очередей являются независимыми очередями D/M/1 . ^[7]

Приближение интенсивного трафика/диффузии

Когда сервер сильно загружен (скорость обслуживания очереди лишь немногим превышает скорость поступления), процесс длины очереди можно аппроксимировать отраженным броуновским движением , которое сходится к тому же стационарному распределению, что и исходный процесс организации очереди. ^[19]^[20] При ограничивающих условиях пространство состояний очередей синхронизации схлопывается, и все очереди ведут себя одинаково. ^[21]

Присоединяйтесь к распределению очереди

После выполнения заданий детали снова собираются в очереди на объединение. Нельсон и Тантави опубликовали распределение длины очереди на подключение в ситуации, когда все серверы имеют одинаковую скорость обслуживания. ^[14] Гетерогенные тарифы на обслуживание и асимптотический анализ распределения рассматриваются Ли и Чжао. ^[22]

Сети очередей разветвления-объединения

Приблизительную формулу можно использовать для расчета распределения времени отклика для сети последовательно соединенных очередей разветвления и соединения (одна за другой). ^[23]

Модель разделения-слияния

Родственной моделью является модель разделения-слияния, для которой существуют аналитические результаты. ^[2]^[24] Точные результаты для очереди разделения-слияния дали Фиорини и Липски. ^[25]Здесь по прибытии задание разбивается на N подзадач, которые обслуживаются параллельно. Только когда все задачи завершат обслуживание и снова присоединятся, можно будет начать следующее задание. В среднем это приводит к более медленному времени ответа.

Обобщенная (n,k) система разветвления-соединения

Обобщением системы массового обслуживания fork-join является $(n,k)$ система fork-join, при которой задание выходит из системы при любом $k$ из $n$ задания выполняются. Традиционная система массового обслуживания с разветвлением является частным случаем $(n,k)$ система, когда $k=n$ . Границы среднего времени отклика этой обобщенной системы были найдены Джоши, Лю и Солянином. ^[26]^[27]

Ссылки

^ Ким, К.; Агравала, АК (1989). «Анализ очереди разветвления-соединения». Транзакции IEEE на компьютерах . 38 (2): 250. дои : 10.1109/12.16501 .
^ Перейти обратно: ^а ^б ^с Лебрехт, Эбигейл; Ноттенбелт, Уильям Дж. (июнь 2007 г.). Приближения времени отклика в очередях разветвления (PDF) . 23-й ежегодный семинар по проектированию производительности в Великобритании (UKPEW). Архивировано из оригинала (PDF) 29 октября 2013 года . Проверено 2 июля 2009 г.
^ Перейти обратно: ^а ^б ^с Серфозо, Р. (2009). «Цепи Маркова». Основы прикладных случайных процессов . Вероятность и ее приложения. стр. 1–98. дои : 10.1007/978-3-540-89332-5_1 . ISBN 978-3-540-89331-8 .
^ Боксма, Онно ; Кул, Гер; Лю, Чжэнь (1996). Методы решения теории массового обслуживания для моделей параллельных и распределенных систем (PDF) (Технический отчет). КРИ . BS-R9425.
^ Перейти обратно: ^а ^б Флэтто, Л.; Хан, С. (1984). «Две параллельные очереди, созданные прибывшими с двумя требованиями I». SIAM Journal по прикладной математике . 44 (5): 1041. дои : 10.1137/0144074 .
^ Райт, Пол Э. (1992), «Два параллельных процессора со связанными входами», « Достижения в области прикладной теории вероятностей » , 24 (4): 986–1007, doi : 10.2307/1427722 , JSTOR 1427722 , S2CID 124774848
^ Перейти обратно: ^а ^б Пиноци, Д.; Зазанис, Массачусетс (2005). «Синхронизированные очереди с детерминированными поступлениями». Письма об исследованиях операций . 33 (6): 560. doi : 10.1016/j.orl.2004.12.005 .
^ Константинопулос, Панайотис; Уолранд, Жан (сентябрь 1989 г.). «Стационарность и стабильность сетей с разветвлением соединения» (PDF) . Журнал прикладной вероятности . 26 (3): 604–614. дои : 10.2307/3214417 . JSTOR 3214417 . S2CID 120222029 . Архивировано из оригинала (PDF) 18 марта 2012 года.
^ Лебрехт, А.С.; Дингл, Нью-Джерси; Ноттенбелт, WJ (2009). «Моделирование зональных RAID-систем с использованием моделирования очереди с разветвлением». Инженерия производительности компьютеров . Конспекты лекций по информатике. Том. 5652. стр. 16–29. CiteSeerX 10.1.1.158.7363 . дои : 10.1007/978-3-642-02924-0_2 . ISBN 978-3-642-02923-3 .
^ Перейти обратно: ^а ^б Кемпер, Б.; Манджес, М. (2011). «Среднее время пребывания в системах разветвления с двумя очередями: границы и приближения» . ИЛИ Спектр . 34 (3): 723. doi : 10.1007/s00291-010-0235-y .
^ Перейти обратно: ^а ^б Ко, СС; Серфозо, РФ (2004). «Время отклика в сетях с разветвлением M/M/s». Достижения в области прикладной теории вероятности . 36 (3): 854. doi : 10.1239/aap/1093962238 . S2CID 122581916 .
^ Ко, СС; Серфозо, РФ (2008). «Время пребывания в сетях разветвления G/M/1». Логистика военно-морских исследований . 55 (5): 432. doi : 10.1002/nav.20294 . S2CID 119551482 .
^ Цю, Чжан; Перес, Хуан Ф.; Харрисон, Питер Г. (2015). «За пределами среднего в очередях с разветвлением-объединением: эффективное приближение для хвостов времени ответа» . Оценка производительности . 91 : 99–116. дои : 10.1016/j.peva.2015.06.007 .
^ Перейти обратно: ^а ^б Нельсон, Р.; Тантави, АН (1988). «Приблизительный анализ синхронизации разветвлений/объединений в параллельных очередях». Транзакции IEEE на компьютерах . 37 (6): 739. дои : 10.1109/12.2213 .
^ Варки, Элизабет; Купец Ариф; Чен, Х. «Очередь разветвления-соединения M/M/1 с переменными подзадачами» (PDF) . Архивировано из оригинала (PDF) 5 августа 2010 года . Проверено 29 марта 2009 г.
^ Бачелли, Франсуа; Маковски, А. (1985), Простые вычислимые границы для очереди с разветвлением (PDF) , Технический отчет Национального института исследований в области компьютерных наук и управления , получено 8 июля 2011 г.
^ Аломари, Ф.; Угроза, Д.А. (2013). «Приближения эффективного времени отклика для многоклассовых очередей разветвления и соединения в открытых и закрытых сетях массового обслуживания». Транзакции IEEE в параллельных и распределенных системах . 25 (6): 1437–1446. дои : 10.1109/TPDS.2013.70 . S2CID 422296 .
^ Цимашенко И.; Ноттенбелт, WJ (2013). «Уменьшение дисперсии подзадач в системах fork-join» (PDF) . Инженерия производительности компьютеров . Конспекты лекций по информатике. Том. 8168. стр. 325–336. CiteSeerX 10.1.1.421.9780 . дои : 10.1007/978-3-642-40725-3_25 . ISBN 978-3-642-40724-6 .
^ Тан, X.; Кнесль, К. (1996). «Модель массового обслуживания с разветвлением: диффузионное приближение, интегральные представления и асимптотика». Системы массового обслуживания . 22 (3–4): 287. doi : 10.1007/BF01149176 . S2CID 206789463 .
^ Варма, Субир (1990). «Приближения интенсивного и легкого трафика для очередей с ограничениями синхронизации (кандидатская диссертация)» (PDF) . Университет Мэриленда . Проверено 10 февраля 2013 г.
^ Атар, Р.; Мандельбаум, А.; Звиран, А. (2012). «Управление сетями разветвления-соединения при интенсивном трафике» (PDF) . 2012 50-я ежегодная конференция Allerton по связи, управлению и вычислениям (Allerton) . п. 823. дои : 10.1109/Allerton.2012.6483303 . ISBN 978-1-4673-4539-2 . S2CID 18115820 .
^ Ли, Дж.; Чжао, YQ (2010). «О распределении вероятностей длины очереди соединения в модели разветвления соединения». Вероятность в инженерных и информационных науках . 24 (4): 473. doi : 10.1017/S0269964810000112 . S2CID 124693767 .
^ Ко, СС (2007). «Время цикла в последовательной сети с разветвлением». Вычислительная наука и ее приложения – ICCSA 2007 . Конспекты лекций по информатике. Том. 4705. стр. 758–766. дои : 10.1007/978-3-540-74472-6_62 . ISBN 978-3-540-74468-9 .
^ Харрисон, П .; Зерталь, С. (2003). «Модели массового обслуживания с максимальным временем обслуживания». Оценка производительности компьютера. Методы и инструменты моделирования . Конспекты лекций по информатике. Том. 2794. стр. 152–168. дои : 10.1007/978-3-540-45232-4_10 . ISBN 978-3-540-40814-7 .
^ Фиорини, Пьер М. (2015). «Точный анализ некоторых очередей разделенного слияния». Обзор оценки производительности SIGMETRICS . 43 (2): 51–53. дои : 10.1145/2825236.2825257 . S2CID 26219594 .
^ Джоши, Гаури; Лю, Янпей; Солянин, Эмина (октябрь 2012 г.). Кодирование для быстрой загрузки контента . Аллертонская конференция по связи, управлению и вычислениям. arXiv : 1210.3012 . Бибкод : 2012arXiv1210.3012J .
^ Джоши, Гаури; Лю, Янпей; Солянин, Эмина (май 2014 г.). О компромиссе между задержкой и хранилищем при загрузке контента из кодированного распределенного хранилища . Журнал по избранным областям коммуникаций. arXiv : 1305.3945 . Бибкод : 2013arXiv1305.3945J .

[1] Ким, К.; Агравала, АК (1989). «Анализ очереди разветвления-соединения». Транзакции IEEE на компьютерах . 38 (2): 250. дои : 10.1109/12.16501 .

[rtapprox-2] Перейти обратно: ^а ^б ^с Лебрехт, Эбигейл; Ноттенбелт, Уильям Дж. (июнь 2007 г.). Приближения времени отклика в очередях разветвления (PDF) . 23-й ежегодный семинар по проектированию производительности в Великобритании (UKPEW). Архивировано из оригинала (PDF) 29 октября 2013 года . Проверено 2 июля 2009 г.

[serfozo-3] Перейти обратно: ^а ^б ^с Серфозо, Р. (2009). «Цепи Маркова». Основы прикладных случайных процессов . Вероятность и ее приложения. стр. 1–98. дои : 10.1007/978-3-540-89332-5_1 . ISBN 978-3-540-89331-8 .

[4] Боксма, Онно ; Кул, Гер; Лю, Чжэнь (1996). Методы решения теории массового обслуживания для моделей параллельных и распределенных систем (PDF) (Технический отчет). КРИ . BS-R9425.

[flatto-5] Перейти обратно: ^а ^б Флэтто, Л.; Хан, С. (1984). «Две параллельные очереди, созданные прибывшими с двумя требованиями I». SIAM Journal по прикладной математике . 44 (5): 1041. дои : 10.1137/0144074 .

[6] Райт, Пол Э. (1992), «Два параллельных процессора со связанными входами», « Достижения в области прикладной теории вероятностей » , 24 (4): 986–1007, doi : 10.2307/1427722 , JSTOR 1427722 , S2CID 124774848

[pinotsi-7] Перейти обратно: ^а ^б Пиноци, Д.; Зазанис, Массачусетс (2005). «Синхронизированные очереди с детерминированными поступлениями». Письма об исследованиях операций . 33 (6): 560. doi : 10.1016/j.orl.2004.12.005 .

[8] Константинопулос, Панайотис; Уолранд, Жан (сентябрь 1989 г.). «Стационарность и стабильность сетей с разветвлением соединения» (PDF) . Журнал прикладной вероятности . 26 (3): 604–614. дои : 10.2307/3214417 . JSTOR 3214417 . S2CID 120222029 . Архивировано из оригинала (PDF) 18 марта 2012 года.

[9] Лебрехт, А.С.; Дингл, Нью-Джерси; Ноттенбелт, WJ (2009). «Моделирование зональных RAID-систем с использованием моделирования очереди с разветвлением». Инженерия производительности компьютеров . Конспекты лекций по информатике. Том. 5652. стр. 16–29. CiteSeerX 10.1.1.158.7363 . дои : 10.1007/978-3-642-02924-0_2 . ISBN 978-3-642-02923-3 .

[kemper-10] Перейти обратно: ^а ^б Кемпер, Б.; Манджес, М. (2011). «Среднее время пребывания в системах разветвления с двумя очередями: границы и приближения» . ИЛИ Спектр . 34 (3): 723. doi : 10.1007/s00291-010-0235-y .

[ko-11] Перейти обратно: ^а ^б Ко, СС; Серфозо, РФ (2004). «Время отклика в сетях с разветвлением M/M/s». Достижения в области прикладной теории вероятности . 36 (3): 854. doi : 10.1239/aap/1093962238 . S2CID 122581916 .

[12] Ко, СС; Серфозо, РФ (2008). «Время пребывания в сетях разветвления G/M/1». Логистика военно-морских исследований . 55 (5): 432. doi : 10.1002/nav.20294 . S2CID 119551482 .

[13] Цю, Чжан; Перес, Хуан Ф.; Харрисон, Питер Г. (2015). «За пределами среднего в очередях с разветвлением-объединением: эффективное приближение для хвостов времени ответа» . Оценка производительности . 91 : 99–116. дои : 10.1016/j.peva.2015.06.007 .

[nelson-14] Перейти обратно: ^а ^б Нельсон, Р.; Тантави, АН (1988). «Приблизительный анализ синхронизации разветвлений/объединений в параллельных очередях». Транзакции IEEE на компьютерах . 37 (6): 739. дои : 10.1109/12.2213 .

[15] Варки, Элизабет; Купец Ариф; Чен, Х. «Очередь разветвления-соединения M/M/1 с переменными подзадачами» (PDF) . Архивировано из оригинала (PDF) 5 августа 2010 года . Проверено 29 марта 2009 г.

[16] Бачелли, Франсуа; Маковски, А. (1985), Простые вычислимые границы для очереди с разветвлением (PDF) , Технический отчет Национального института исследований в области компьютерных наук и управления , получено 8 июля 2011 г.

[17] Аломари, Ф.; Угроза, Д.А. (2013). «Приближения эффективного времени отклика для многоклассовых очередей разветвления и соединения в открытых и закрытых сетях массового обслуживания». Транзакции IEEE в параллельных и распределенных системах . 25 (6): 1437–1446. дои : 10.1109/TPDS.2013.70 . S2CID 422296 .

[18] Цимашенко И.; Ноттенбелт, WJ (2013). «Уменьшение дисперсии подзадач в системах fork-join» (PDF) . Инженерия производительности компьютеров . Конспекты лекций по информатике. Том. 8168. стр. 325–336. CiteSeerX 10.1.1.421.9780 . дои : 10.1007/978-3-642-40725-3_25 . ISBN 978-3-642-40724-6 .

[19] Тан, X.; Кнесль, К. (1996). «Модель массового обслуживания с разветвлением: диффузионное приближение, интегральные представления и асимптотика». Системы массового обслуживания . 22 (3–4): 287. doi : 10.1007/BF01149176 . S2CID 206789463 .

[20] Варма, Субир (1990). «Приближения интенсивного и легкого трафика для очередей с ограничениями синхронизации (кандидатская диссертация)» (PDF) . Университет Мэриленда . Проверено 10 февраля 2013 г.

[21] Атар, Р.; Мандельбаум, А.; Звиран, А. (2012). «Управление сетями разветвления-соединения при интенсивном трафике» (PDF) . 2012 50-я ежегодная конференция Allerton по связи, управлению и вычислениям (Allerton) . п. 823. дои : 10.1109/Allerton.2012.6483303 . ISBN 978-1-4673-4539-2 . S2CID 18115820 .

[22] Ли, Дж.; Чжао, YQ (2010). «О распределении вероятностей длины очереди соединения в модели разветвления соединения». Вероятность в инженерных и информационных науках . 24 (4): 473. doi : 10.1017/S0269964810000112 . S2CID 124693767 .

[23] Ко, СС (2007). «Время цикла в последовательной сети с разветвлением». Вычислительная наука и ее приложения – ICCSA 2007 . Конспекты лекций по информатике. Том. 4705. стр. 758–766. дои : 10.1007/978-3-540-74472-6_62 . ISBN 978-3-540-74468-9 .

[24] Харрисон, П .; Зерталь, С. (2003). «Модели массового обслуживания с максимальным временем обслуживания». Оценка производительности компьютера. Методы и инструменты моделирования . Конспекты лекций по информатике. Том. 2794. стр. 152–168. дои : 10.1007/978-3-540-45232-4_10 . ISBN 978-3-540-40814-7 .

[25] Фиорини, Пьер М. (2015). «Точный анализ некоторых очередей разделенного слияния». Обзор оценки производительности SIGMETRICS . 43 (2): 51–53. дои : 10.1145/2825236.2825257 . S2CID 26219594 .

[jls_allerton-26] Джоши, Гаури; Лю, Янпей; Солянин, Эмина (октябрь 2012 г.). Кодирование для быстрой загрузки контента . Аллертонская конференция по связи, управлению и вычислениям. arXiv : 1210.3012 . Бибкод : 2012arXiv1210.3012J .

[jls_jsac-27] Джоши, Гаури; Лю, Янпей; Солянин, Эмина (май 2014 г.). О компромиссе между задержкой и хранилищем при загрузке контента из кодированного распределенного хранилища . Журнал по избранным областям коммуникаций. arXiv : 1305.3945 . Бибкод : 2013arXiv1305.3945J .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

v т и Теория массового обслуживания
Одиночные узлы массового обслуживания	Д/М/1 хвост М/Д/1 хвост М/Д/Ц хвост Очередь М/М/1 Теорема Берка Очередь М/М/Ц Очередь М/М/∞ Очередь M/G/1 Формула Поллачека – Хинчина Матричный аналитический метод Очередь M/G/k Очередь G/M/1 Очередь G/G/1 Формула Кингмана Уравнение Линдли Разветвить очередь – присоединиться к ней Массовая очередь
Процессы прибытия	Точный процесс Пуассона Марковский процесс прибытия Рациональный процесс прибытия
Сети массового обслуживания	Сеть Джексона Уравнения дорожного движения Теорема Гордона – Ньюэлла Анализ среднего значения Алгоритм Бузена сеть Келли G-сеть Сеть BCMP
Политика обслуживания	ФИФО ЛИФО Совместное использование процессора Круговой Самая короткая работа следующая Кратчайшее оставшееся время
Ключевые понятия	Цепь Маркова с непрерывным временем Обозначения Кендалла Закон Литтла Решение в форме продукта Уравнение баланса Квазиобратимость Потоко-эквивалентный серверный метод Теорема о прибытии Метод разложения метод Бенеша
Предельные теоремы	Предел жидкости Теория среднего поля Приближение интенсивного движения Отраженное броуновское движение
Расширения	Жидкая очередь Многоуровневая сеть массового обслуживания Система опроса Состязательная сеть массового обслуживания Сеть потерь Очередь повторных попыток
Информационные системы	Буфер данных Эрланг (единица измерения) Распределение Эрланга Управление потоком (данные) Очередь сообщений Перегрузка сети Сетевой планировщик Конвейер (программное обеспечение) Качество обслуживания Планирование (вычисления) Телетрафик инжиниринг
Категория