포크 결합 큐

Fork–join queue
포크 조인 큐잉노드

확률의 수학적 이론인 큐잉 이론에서 포크 조인 큐는 착신 작업이 다수의 서버에 의해 서비스를 받기 위해 도착 시 분할되고 [1]출발 전에 결합되는 큐입니다.이 모델은 (창고 또는 제조 환경에서)[3]: 78–80 다른 공급업체로부터 제품을 동시에 입수해야 하는 병렬 계산[2] 또는 시스템에 자주 사용됩니다.이 모델의 주요 관심사는 일반적으로 전체 작업에 소요되는 시간입니다.이 모델은 "병렬 [4]분산 시스템의 성능 분석을 위한 핵심 모델"로 설명되었습니다.포크 결합 큐에 대한 분석 결과는 거의 없지만 다양한 근사치가 알려져 있습니다.

포아송 프로세스에 따라 작업이 도착하고 서비스 시간이 기하급수적으로 분산되는 상황을 플랫토라고 부르기도 합니다.Han-Wright 모델 또는 FHW 모델.[5][6][7]

정의.

분기점에 도착하면 작업은 N개의 서브 작업으로 분할되며, 각 서브 작업은 N개의 서버에서 처리됩니다.서비스 후 하위 작업은 다른 모든 하위 작업도 처리될 때까지 기다립니다.그런 다음 하위 작업이 다시 참여되고 시스템을 [3]종료합니다.

포크 조인 큐를 안정시키려면 입력 레이트가 서비스 [8]노드의 서비스 레이트 합계보다 엄격히 작아야 합니다.

적용들

포크 조인 큐는 구역화된 RAID 시스템 모델링,[9] 병렬 계산[2] 및 창고 [3]내 주문 이행 모델링에 사용되어 왔습니다.

응답시간

응답 시간(또는 체류[10] 시간)은 작업이 시스템에서 보내는 총 시간입니다.

분배

Ko와 Serfozo는 서비스 시간이 기하급수적으로 분포되고 작업이 포아송[11] 프로세스 또는 일반 [12]분포에 따라 도착할 때 응답 시간 분포에 대한 근사치를 제공합니다.QIU, Pérez 및 Harrison은 서비스 시간이 위상 유형 [13]분포를 가질 때 근사 방법을 제공합니다.

평균 응답 시간

평균 응답 시간의 정확한 공식은 서비스 시간이 기하급수적으로 분산된 두 서버(N=2)의 경우에만 알려져 있습니다(각 서버는 M/M/1 대기열).이 경우 응답 시간(작업이 시스템에서 보내는 총 시간)은[14] 다음과 같습니다.

어디에

  • = / { \rho = \/ \mu 입니다.
  • \displayda 모든 노드에 대한 작업 도착률입니다.
  • μ{\ 모든 노드의 서비스 레이트입니다.

노드가 M/M/1 이고 N > 2인 상황에서는 평균값 분석에 대한 Varki의 수정도 평균 응답 [15]시간의 대략적인 값을 제공하기 위해 사용할 수 있습니다.

일반 서비스 시간(각 노드가 M/G/1 큐인 경우)에 대해 Baccelli 및 Makowski는 과도 상태 [16]및 정상 상태 상황 모두에서 평균 응답 시간 및 이 양의 높은 모멘트에 대한 경계를 부여한다.Kemper와 Mandjes는 일부 파라미터의 경우 이러한 경계가 엄격하지 않으며 근사 [10]기법을 보여준다.이기종 포크 결합 큐(서비스 시간이 다른 포크 결합 큐)의 경우, 알로마리와 메나체는 확률론적 포크, 오픈 및 클로즈드 포크 결합 [17]큐와 같은 보다 일반적인 경우를 포함하도록 확장될 수 있는 고조파 숫자에 기초한 근사치를 제안한다.

하위 작업 분산

서비스 시간 범위로 정의된 하위 작업 산포를 수치적으로 계산하고 최적의 결정론적 지연을 도입하여 [18]범위를 최소화할 수 있습니다.

고정 분포

일반적으로 각 큐에서 작업 수의 고정 분포는 다루기 어렵습니다.[11]Flatto는 두 개의 서버 (N=2)의 경우를 고려하였고, 균일화 [5]기법을 통해 각 큐의 작업 수에 대한 고정 분포를 도출하였습니다.Pinotsi와 Zazanis는 도착이 확정적일 때 제품 형태 솔루션이 존재함을 보여줍니다. 큐의 길이는 독립적인 D/M/1 [7]큐이기 때문입니다.

대량의 트래픽/확산 근사치

서버의 부하가 높은 경우(큐의 서비스 레이트는 착신 레이트보다 클 뿐) 큐 길이 프로세스는 원래 큐잉 [19][20]프로세스와 동일한 고정 분포로 수렴되는 반사된 브라운 모션을 통해 근사할 수 있습니다.제한 조건에서는 동기 큐의 스테이트 공간이 축소되어 모든 큐가 동일하게 [21]동작합니다.

가입 큐 분산

작업이 처리되면 부품이 조인 큐에서 재조립됩니다.Nelson과 Tantawi는 모든 서버의 서비스 레이트가 [14]동일한 상황에서 가입 큐 길이의 분포를 공개했습니다.이종 서비스 요금과 분포 점근 분석은 Li와 [22]Zhao에 의해 고려되었다.

포크 조인 큐의 네트워크

대략적인 공식을 사용하여 직렬로 결합된 포크 조인 큐의 네트워크에 대한 응답 시간 분포를 계산할 수 있습니다.[23]

분할-합병합

관련 모델은 분석 결과가 [2][24]존재하는 분할-합병 모델입니다.분할 병합 큐에 대한 정확한 결과는 Fiorini와 Lipsky에 [25]의해 제공됩니다.도착 시 작업은 N개의 서브태스크로 분할되어 병렬로 처리됩니다.모든 태스크가 서비스를 완료하고 다시 참여해야 다음 작업을 시작할 수 있습니다.이것에 의해, 평균 응답 시간이 늦어집니다.

범용(n,k) 포크 조인 시스템

A generalization of the fork-join queueing system is the fork-join system where the job exits the system when any out of tasks are served.전통적인 포크 큐잉 시스템은 k {\ ( 의 특수한 경우입니다.이 일반화 시스템의 평균 응답 시간에 대한 경계는 Joshi, Liu 및 Soljanin에 [26][27]의해 발견되었습니다.

레퍼런스

  1. ^ Kim, C.; Agrawala, A. K. (1989). "Analysis of the fork-join queue". IEEE Transactions on Computers. 38 (2): 250. doi:10.1109/12.16501.
  2. ^ a b c Lebrecht, Abigail; Knottenbelt, William J. (June 2007). Response Time Approximations in Fork-Join Queues (PDF). 23rd Annual UK Performance Engineering Workshop (UKPEW). Archived from the original (PDF) on 29 October 2013. Retrieved 2 July 2009.
  3. ^ a b c Serfozo, R. (2009). "Markov Chains". Basics of Applied Stochastic Processes. Probability and Its Applications. pp. 1–98. doi:10.1007/978-3-540-89332-5_1. ISBN 978-3-540-89331-8.
  4. ^ Boxma, Onno; Koole, Ger; Liu, Zhen (1996). Queueing-theoretic Solution Methods for Models of Parallel and Distributed Systems (PDF) (Technical report). CWI. BS-R9425.
  5. ^ a b Flatto, L.; Hahn, S. (1984). "Two Parallel Queues Created by Arrivals with Two Demands I". SIAM Journal on Applied Mathematics. 44 (5): 1041. doi:10.1137/0144074.
  6. ^ Wright, Paul E. (1992), "Two parallel processors with coupled inputs", Advances in Applied Probability, 24 (4): 986–1007, doi:10.2307/1427722, JSTOR 1427722
  7. ^ a b Pinotsi, D.; Zazanis, M. A. (2005). "Synchronized queues with deterministic arrivals". Operations Research Letters. 33 (6): 560. doi:10.1016/j.orl.2004.12.005.
  8. ^ Konstantopoulos, Panagiotis; Walrand, Jean (September 1989). "Stationary and Stability of Fork-Join Networks" (PDF). Journal of Applied Probability. 26 (3): 604–614. doi:10.2307/3214417. JSTOR 3214417. Archived from the original (PDF) on 18 March 2012.
  9. ^ Lebrecht, A. S.; Dingle, N. J.; Knottenbelt, W. J. (2009). "Modelling Zoned RAID Systems Using Fork-Join Queueing Simulation". Computer Performance Engineering. Lecture Notes in Computer Science. Vol. 5652. p. 16. CiteSeerX 10.1.1.158.7363. doi:10.1007/978-3-642-02924-0_2. ISBN 978-3-642-02923-3.
  10. ^ a b Kemper, B.; Mandjes, M. (2011). "Mean sojourn times in two-queue fork-join systems: Bounds and approximations". OR Spectrum. 34 (3): 723. doi:10.1007/s00291-010-0235-y.
  11. ^ a b Ko, S. S.; Serfozo, R. F. (2004). "Response times in M/M/s fork-join networks". Advances in Applied Probability. 36 (3): 854. doi:10.1239/aap/1093962238.
  12. ^ Ko, S. S.; Serfozo, R. F. (2008). "Sojourn times in G/M/1 fork‐join networks". Naval Research Logistics. 55 (5): 432. doi:10.1002/nav.20294.
  13. ^ Qiu, Zhan; Pérez, Juan F.; Harrison, Peter G. (2015). "Beyond the mean in fork-join queues: Efficient approximation for response-time tails". Performance Evaluation. 91: 99–116. doi:10.1016/j.peva.2015.06.007.
  14. ^ a b Nelson, R.; Tantawi, A. N. (1988). "Approximate analysis of fork/join synchronization in parallel queues". IEEE Transactions on Computers. 37 (6): 739. doi:10.1109/12.2213.
  15. ^ Varki, Elizabeth; Merchant, Arif; Chen, H. "M/M/1 Fork-join queue with variable sub-tasks" (PDF). Archived from the original (PDF) on 5 August 2010. Retrieved 29 March 2009.
  16. ^ Baccelli, François; Makowski, A. (1985), Simple computable bounds for the fork-join queue (PDF), National Institute for Research in Computer Science and Control Technical Report, retrieved 8 July 2011
  17. ^ Alomari, F.; Menasce, D. A. (2013). "Efficient Response Time Approximations for Multiclass Fork and Join Queues in Open and Closed Queuing Networks". IEEE Transactions on Parallel and Distributed Systems. 25 (6): 1437–1446. doi:10.1109/TPDS.2013.70.
  18. ^ Tsimashenka, I.; Knottenbelt, W. J. (2013). "Reduction of Subtask Dispersion in Fork-Join Systems" (PDF). Computer Performance Engineering. Lecture Notes in Computer Science. Vol. 8168. pp. 325–336. CiteSeerX 10.1.1.421.9780. doi:10.1007/978-3-642-40725-3_25. ISBN 978-3-642-40724-6.
  19. ^ Tan, X.; Knessl, C. (1996). "A fork-join queueing model: Diffusion approximation, integral representations and asymptotics". Queueing Systems. 22 (3–4): 287. doi:10.1007/BF01149176.
  20. ^ Varma, Subir (1990). "Heavy and Light Traffic Approximations for Queues with Synchronization Constraints (PhD thesis)" (PDF). University of Maryland. Retrieved 10 February 2013.
  21. ^ Atar, R.; Mandelbaum, A.; Zviran, A. (2012). "Control of Fork-Join Networks in heavy traffic" (PDF). 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton). p. 823. doi:10.1109/Allerton.2012.6483303. ISBN 978-1-4673-4539-2.
  22. ^ Li, J.; Zhao, Y. Q. (2010). "On the Probability Distribution of Join Queue Length in a Fork-Join Model". Probability in the Engineering and Informational Sciences. 24 (4): 473. doi:10.1017/S0269964810000112.
  23. ^ Ko, S. S. (2007). "Cycle Times in a Serial Fork-Join Network". Computational Science and Its Applications – ICCSA 2007. Lecture Notes in Computer Science. Vol. 4705. pp. 758–766. doi:10.1007/978-3-540-74472-6_62. ISBN 978-3-540-74468-9.
  24. ^ Harrison, P.; Zertal, S. (2003). "Queueing Models with Maxima of Service Times". Computer Performance Evaluation. Modelling Techniques and Tools. Lecture Notes in Computer Science. Vol. 2794. p. 152. doi:10.1007/978-3-540-45232-4_10. ISBN 978-3-540-40814-7.
  25. ^ Fiorini, Pierre M. (2015). "Exact Analysis of Some Split Merge Queues". SIGMETRICS Performance Evaluation Review. 43 (2): 51–53. doi:10.1145/2825236.2825257.
  26. ^ Joshi, Gauri; Liu, Yanpei; Soljanin, Emina (October 2012). Coding for Fast Content Download. Allerton Conference on Communication, Control and Computing. arXiv:1210.3012. Bibcode:2012arXiv1210.3012J.
  27. ^ Joshi, Gauri; Liu, Yanpei; Soljanin, Emina (May 2014). On the Delay-Storage trade-off in Content Download from Coded Distributed Storage. Journal on Selected Areas of Communications. arXiv:1305.3945. Bibcode:2013arXiv1305.3945J.