Вилка – присоединение к очереди - Fork–join queue

Узел очереди fork-join

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

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

Определение

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

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

Приложения

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

Время отклика

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

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

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

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

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

${displaystyle {frac {12-ho }{8mu (1-ho )}}}$

куда

• ${displaystyle ho =lambda /mu }$ это использование.
• ${displaystyle lambda }$ - скорость поступления заданий на все узлы.
• ${displaystyle mu }$ скорость обслуживания по всем узлам.

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

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

Разброс подзадач

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

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

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

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

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

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

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

Сети очередей fork – join

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

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

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

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

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

Рекомендации

1. Kim, C .; Агравала, А. К. (1989). «Анализ очереди fork-join». Транзакции IEEE на компьютерах. 38 (2): 250. Дои:10.1109/12.16501.
2. Лебрехт, Абигейл; Knottenbelt, Уильям Дж. (Июнь 2007 г.). Приближение времени отклика в очередях Fork-Join (PDF). 23-й ежегодный семинар по проектированию производительности в Великобритании (UKPEW). Архивировано из оригинал (PDF) 29 октября 2013 г.. Получено 2 июля 2009.
3. Серфозо Р. (2009). «Цепи Маркова». Основы прикладных случайных процессов. Вероятность и ее приложения. С. 1–98. Дои:10.1007/978-3-540-89332-5_1. ISBN  978-3-540-89331-8.
4. Боксма, Онно; Куле, Гер; Лю, Чжэнь (1996). Теоретико-массовые методы решения моделей параллельных и распределенных систем (PDF) (Технический отчет). CWI. BS-R9425.
5. Flatto, L .; Хан, С. (1984). «Две параллельные очереди, созданные прибывшими с двумя требованиями I». Журнал SIAM по прикладной математике. 44 (5): 1041. Дои:10.1137/0144074.
6. Райт, Пол Э. (1992), «Два параллельных процессора со связанными входами», Достижения в прикладной теории вероятностей, 24 (4): 986–1007, Дои:10.2307/1427722, JSTOR  1427722
7. Pinotsi, D .; Зазанис, М.А. (2005). «Синхронизированные очереди с детерминированными поступлениями». Письма об исследованиях операций. 33 (6): 560. Дои:10.1016 / j.orl.2004.12.005.
8. Константопулос, Панайотис; Вальран, Жан (Сентябрь 1989 г.). «Стационарность и устойчивость разветвленных сетей» (PDF). Журнал прикладной теории вероятностей. 26 (3): 604–614. Дои:10.2307/3214417. JSTOR  3214417. Архивировано из оригинал (PDF) 18 марта 2012 г.. Получено 8 июля 2011.
9. Lebrecht, A. S .; Dingle, N.J .; Knottenbelt, W. J. (2009). «Моделирование зонированных RAID-систем с использованием имитации очереди с вилочным объединением». Инженерия производительности компьютеров. Конспект лекций по информатике. 5652. п. 16. CiteSeerX  10.1.1.158.7363. Дои:10.1007/978-3-642-02924-0_2. ISBN  978-3-642-02923-3.
10. Kemper, B .; Манджес, М. (2011). «Среднее время пребывания в системах вилочного соединения с двумя очередями: границы и приближения». ИЛИ Спектр. 34 (3): 723. Дои:10.1007 / s00291-010-0235-у.
11. Ko, S. S .; Серфозо, Р. Ф. (2004). «Время отклика в сетях M / M / s fork-join». Достижения в прикладной теории вероятностей. 36 (3): 854. Дои:10.1239 / aap / 1093962238.
12. Ko, S. S .; Серфозо, Р. Ф. (2008). «Время пребывания в разветвленных сетях G / M / 1». Логистика военно-морских исследований. 55 (5): 432. Дои:10.1002 / nav.20294.
13. Цю, Чжань; Перес, Хуан Ф .; Харрисон, Питер Г. (2015). «За пределами среднего в очередях fork-join: эффективное приближение для хвостов времени отклика». Оценка эффективности. 91: 99–116. Дои:10.1016 / j.peva.2015.06.007.
14. Nelson, R .; Тантави, А. Н. (1988). «Приблизительный анализ синхронизации fork / join в параллельных очередях». Транзакции IEEE на компьютерах. 37 (6): 739. Дои:10.1109/12.2213.
15. Варки, Елизавета; Торговец, Ариф; Чен, Х. «Очередь Fork-join M / M / 1 с переменными подзадачами» (PDF). Архивировано из оригинал (PDF) 5 августа 2010 г.. Получено 29 марта 2009.
16. Баччелли, Франсуа; Маковски, А. (1985), Простые вычислимые границы для очереди fork-join (PDF), Национальный институт исследований в области компьютерных наук и управления, технический отчет, получено 8 июля 2011
17. Alomari, F .; Менасе, Д. А. (2013). «Эффективное приближение времени отклика для многоклассовых разветвлений и очередей соединения в открытых и закрытых сетях массового обслуживания». Транзакции IEEE в параллельных и распределенных системах. 25 (6): 1437–1446. Дои:10.1109 / TPDS.2013.70.
18. Цимашенко, И .; Knottenbelt, W. J. (2013). «Снижение разброса подзадач в вилочно-соединительных системах» (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. Tan, X .; Кнессл, К. (1996). «Модель массового обслуживания fork-join: диффузионное приближение, интегральные представления и асимптотика». Системы массового обслуживания. 22 (3–4): 287. Дои:10.1007 / BF01149176.
20. Варма, Субир (1990). «Аппроксимации интенсивного и легкого трафика для очередей с ограничениями синхронизации (кандидатская диссертация)» (PDF). Университет Мэриленда. Получено 10 февраля 2013.
21. Atar, R .; Mandelbaum, A .; Цвиран, А. (2012). «Контроль разветвленных сетей в условиях интенсивного трафика» (PDF). 2012 50-я ежегодная конференция Allerton по коммуникациям, управлению и вычислениям (Allerton). п. 823. Дои:10.1109 / Allerton.2012.6483303. ISBN  978-1-4673-4539-2.
22. Li, J .; Чжао, Ю.К. (2010). «О распределении вероятностей длины очереди присоединения в модели вилочного присоединения». Вероятность в технических и информационных науках. 24 (4): 473. Дои:10.1017 / S0269964810000112.
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. Дои: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.
26. Джоши, Гаури; Лю, Янпэй; Солянин, Эмина (октябрь 2012 г.). Кодирование для быстрой загрузки контента. Конференция Allerton по коммуникациям, управлению и вычислениям. arXiv:1210.3012. Bibcode:2012arXiv1210.3012J.
27. Джоши, Гаури; Лю, Янпэй; Солянин, Эмина (май 2014 г.). О компромиссе между задержкой и хранением при загрузке контента из закодированного распределенного хранилища. Журнал по избранным направлениям коммуникаций. arXiv:1305.3945. Bibcode:2013arXiv1305.3945J.