Thumbnail
Access Restriction
Subscribed

Author Thomasian, Alexander
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Fork-join queueing system ♦ MapReduce ♦ Markov chain model ♦ RAID5 disk array ♦ Bulk arrivals ♦ Characteristic maximum ♦ Independent server model ♦ Linear programming ♦ Lock contention ♦ Matrix geometric method ♦ Mirrored disk ♦ Order statistics ♦ Parallel processing ♦ Queueing network model ♦ Replicated databases ♦ Serialization delay ♦ Split-merge queueing system ♦ Stream processing ♦ Task systems ♦ Team service model ♦ Vacationing server model
Abstract Fork/join (F/J) requests arise in contexts such as parallel computing, query processing in parallel databases, and parallel disk access in RAID. F/J requests spawn $\textit{K}$ tasks that are sent to $\textit{K}$ parallel servers, and the completion of all $\textit{K}$ tasks marks the completion of an F/J request. The exact formula for the mean response time of $\textit{K}$ = 2-way F/J requests derived under Markovian assumptions $(R^{F/J}_{2})$ served as the starting point for an approximate expression for $R^{F/J}_{K}$ for 2 < $\textit{K}$ ≤ 32. When servers process independent requests in addition to F/J requests, the mean response time of F/J requests is better approximated by $R^{max}_{K},$ which is the maximum of the response times of tasks constituting F/J requests. $R^{max}_{K}$ is easier to compute and serves as an upper bound to $R^{F/J}_{K}.$ We discuss techniques to compute $R^{max}_{K}$ and generally the maximum of $\textit{K}$ random variables denoting the processing times of the tasks of a parallel computation $&Xmacr;^{max}_{K}.$ Graph models of computations such as Petri nets—a more general form of parallelism than F/J requests—are also discussed in this work. Jobs with precedence constraints may require multiple resources, which are represented by a queueing network model. We also discuss various queueing systems related to F/J queueing systems and outline their analysis.
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2014-08-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 47
Issue Number 2
Page Count 71
Starting Page 1
Ending Page 71


Open content in new tab

   Open content in new tab
Source: ACM Digital Library