Solution of closed, product form, queueing networks via the RECAL and tree-RECAL methods on a shared memory multiprocessor
Pages 127 - 135
Abstract
RECAL is a new recurrence relation for calculating the partition function and various queue length moments for closed, product form networks. In this paper we discuss a number of the issues involved in the software implementation of RECAL on both sequential computers and parallel, shared memory computers. After a brief description of RECAL, we describe software implementing RECAL on a sequential computer. In particular, we discuss the problems involved in indexing and data storage. Next we describe code implementing RECAL on a parallel, shared memory computer. Special attention is given to designing a special buffer for temporary data storage and several other important features of the parallel code. Finally, we touch on software for serial and parallel implementations of a tree algorithm for RECAL.
References
[1]
Conway, A. E. and Georganas, N. D., "RECAL, a new efficient algorithm for the exact analysis of multiple-chain closed queueing networks", j. ACM 33, 4 (October 1986), 768-791.
[2]
McKenna, J. "A new proof and a tree algorithm for RECAL". Stochastic Models, 4, 2 (1988), 235-276.
[3]
Lain, S. S. and Lien, Y. L., "A tree convolution algorithm for the solution of queueing networks". Commun. ACM 26, 3 (March 1983), 203-215.
[4]
Lavenberg, S. S., "Computer Performance Modeling Handbook", Academic Press, New York, 1983.
[5]
McKenna, J. "Calculating joint queue length moments with RECAL". To appear.
[6]
Basket, F., Chandy, K. M, Muntz, R. R. and Palacios, F, G., "Open, closed, and mixed networks of queues with different classes of customers". J. ACM 22, 2 (1975), 248-260.
[7]
Kelly, F.P., "Networks of queues with customers of different types". J. Appl. Prob. 12 (1978), 542-554.
[8]
Kelly, F. P., "Networks of queues". Adv. Appl. Prob. $ (1976), 416-432.
[9]
Nijenhuis, A. and Wilf, S., "Combinatorial Algorithms, second edition", Academic Press, New York, 1978.
[10]
George, A. and Liu, W. L., "Computer Solution of Large Sparse Positive Definite Systems", Prentice Hall, Englewood Cliffs, 1981.
[11]
Gustafson, J.L., Montry, G.R., and Benner, R.E., "Development of Parallel Methods for a 1024-Processor Hypercube," Siam J. Sci. Stat. Comput., 9, 4 (July 1988) 609-638.
[12]
Aho, A.V., Hopcroft, J.E., and Ullman, J.D., "The Design and Analysis of Computer Algorithms", Addison-Wesley Publishing Co., Reading, Mass., 1976.
Index Terms
- Solution of closed, product form, queueing networks via the RECAL and tree-RECAL methods on a shared memory multiprocessor
Recommendations
Solution of closed, product form, queueing networks via the RECAL and tree-RECAL methods on a shared memory multiprocessor
RECAL is a new recurrence relation for calculating the partition function and various queue length moments for closed, product form networks. In this paper we discuss a number of the issues involved in the software implementation of RECAL on both ...
Non-product form equilibrium probabilities in a class of two-station closed reentrant queueing networks
While many single station queues possess explicit forms for their equilibrium probabilities, queueing networks are more problematic. Outside of the class of product form networks (e.g., Jackson, Kelly, and BCMP networks), one must resort to bounds, ...
Comments
Information & Contributors
Information
Published In
Copyright © 1989 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 April 1989
Check for updates
Qualifiers
- Article
Conference
SIGMETRICS89
Sponsor:
SIGMETRICS89: Performance 89 Intl Conference on Measurement & Modeling of Computer Systems
May 23 - 26, 1989
California, Oakland, USA
Acceptance Rates
Overall Acceptance Rate 459 of 2,691 submissions, 17%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations2Total Citations
- 254Total Downloads
- Downloads (Last 12 months)55
- Downloads (Last 6 weeks)6
Reflects downloads up to 01 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in