State reduction in the exact analysis of fork/join queueing systems with homogeneous exponential servers

A state reduction technique for the exact analysis of fork/join queueing systems is presented in this paper. The technique is based on the standard Markov model and can be applied to systems having K homogeneous exponential servers. For a closed system with M jobs, the technique reduces the size of...

Full description

Saved in:
Bibliographic Details
Main Authors: Yeung, K.H., Yum, T.S.
Format: Conference Proceeding
Language:English
Subjects:
Analytical models
Computational modeling
Multiprocessing systems
Parallel processing
Performance analysis
Queueing analysis
State-space methods
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A state reduction technique for the exact analysis of fork/join queueing systems is presented in this paper. The technique is based on the standard Markov model and can be applied to systems having K homogeneous exponential servers. For a closed system with M jobs, the technique reduces the size of the state space from (M+1)/sup K/-M/sup K/ states to (M+K-1/K-1) states. This amounts to more than five orders of magnitude of state reduction for a typical value of K=M=10. The state reduction technique can also be applied to the analysis of an open fork/join queueing system. It reduces the size of the state space from (B+1)/sup K/ states to (B+K/K) states where B is the maximum number of jobs allowed in the open queueing system. The state reduction amounts to more than six orders of magnitude for a typical value of K=10 and B=500.
DOI:10.1109/ICPADS.1996.517545