
We present an exact solution technique for analyzing the performance of such applications. Formally, the problem can be stated as follows: A job arrives at a system with \(M\) identical servers in a Poisson fashion. After some initial computation, the job spawns \(K\) statistically identical subtasks. All these subtasks can be executed in parallel but only one of them is required to complete in order to complete the entire job. The service times are assumed to be exponentially distributed. The solution is obtained by defining a set of partial generating functions and exploiting their properties. The solution technique appears to be applicable for the general problem, but we have the formal proofs of correctness only for the cases where \(K=M\) and when the mean service demands of the initial computation and the subtasks are the same. For these cases, the results show that the average number of busy processors is independent of \(K\) while the job response time decreases with \(K\). Some conjectures are presented for more general situations.
Rouché theorem, task graph, Markov chain, generating functions, Parallel algorithms in computer science, Searching and sorting, Performance evaluation, queueing, and scheduling in the context of computer systems, stability condition
Rouché theorem, task graph, Markov chain, generating functions, Parallel algorithms in computer science, Searching and sorting, Performance evaluation, queueing, and scheduling in the context of computer systems, stability condition
| 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). | 2 | |
| 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. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
