
doi: 10.1145/2628913
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 spawnKtasks that are sent toKparallel servers, and the completion of allKtasks marks the completion of an F/J request. The exact formula for the mean response time ofK= 2-way F/J requests derived under Markovian assumptions (RF/J2) served as the starting point for an approximate expression forRF/JKfor 2 <K≤ 32. When servers process independent requests in addition to F/J requests, the mean response time of F/J requests is better approximated byRmaxK, which is the maximum of the response times of tasks constituting F/J requests.RmaxKis easier to compute and serves as an upper bound toRF/JK. We discuss techniques to computeRmaxKand generally the maximum ofKrandom variables denoting the processing times of the tasks of a parallel computationXmaxK. 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.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 56 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
