|
 ABSTRACT
The new class of queuing models, called Synchronized Queuing Networks, is proposed for evaluating the performance of multiprogrammed and multitasked multiprocessor systems, where workloads consists of parallel programs of similar structure and where the scheduling discipline is first-come-first-serve.
Pathwise evolution equations are established for these networks that capture the effects of competition for processors and the precedence constraints governing tasks executions.
A general expression is deduced for the stability condition of such queuing networks under general statistical assumptions (basically the stationarity and the ergodicity of input sequences), which yields the maximum program throughput of the multiprocessor system, or equivalently, the maximum rate at which programs can be executed or submitted. The proof is based on the ergodic theory of queues.
Basic integral equations are also derived for the stationary distribution of important performance criteria such as the workload of the queues and program response times. An iterative numerical schema that converges to this solution is proposed and various upper and lower bounds on moments are derived using stochastic ordering techniques.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
|
| |
2
|
BACCELLI, F. Two parallel queues created by arrivals with two demands: The M/G/2 symmetrical case. INRIA Rapport de Recherche, No. 426. INRIA, Valbonne, France, July 1985.
|
| |
3
|
BACCELLI, F., AND BRI~MAUD, P. Palm probabilities and stationary queues. In Lecture Notes in Statistics, No. 41. Springer-Verlag, New York, 1987.
|
| |
4
|
BACCELLI, F., AND LIU, Z. On the stability condition of a precedence-based queueing discipline. Adv. Appl. Prob. 21 (1989), 883-887.
|
| |
5
|
BACCELLI, F., AND LIU, Z. On a class of stochastic evolution equations. Ann. Prob., to appear.
|
| |
6
|
BACCELLI, F., AND MAKOWSKI, A. Simple computable bounds for the fork-join queue. In Proceedings of the Conference for Information Science Systems. Johns Hopkins Univ., Baltimore, Md., March 1985, pp. 436-441.
|
| |
7
|
BACCELLI, F., MAKOWSKI, A., AND SHWARTZ, A. Fork-join queue and related systems with synchronization constraints: Stochastic ordering, approximations and computable bounds. J. Adv. Prob. 21 (1989), 629-660.
|
| |
8
|
|
| |
9
|
|
| |
10
|
BARLOW, R., ANO PROSCHAN, F. Statistical Theory of Reliability and Life Testing. Holt, Rinehart and Winston, New York, 1975.
|
| |
11
|
CHEN, W. K. Applied graph theory. In Applied Mathematics and Mechanics, H. A. Lauwerier and W. T. Koiter, eds. North-Holland, New York, I971.
|
| |
12
|
CHU, W. W., AND LEUNO, K.K. Module replication and assignment for real-time distributed processing systems. Proc. IEEE 75, 5 (May 1987), 547-562.
|
| |
13
|
|
| |
14
|
COSNARD, M., AND ROBERT, Y. Algorithmique Parallble: Une E, tude de ComplexitY. Techniques et Sciences Informatiques, Paris, France, 1987.
|
| |
15
|
DEVROVE, L.P. Inequalities for the completion times of stochastic PERT networks. Math. Oper. Res. 4 (1980), 441-447.
|
| |
16
|
DODIN, B. Bounding the project completion time distribution in PERT networks. Oper. Res. 33, 4 (July-Aug. 1985), 862-881.
|
| |
17
|
DUNCAN, T., AND HUEN, W.H. Software structure of no. 5 ESS-A distributed telephone switching system. IEEE Trans. Commun. COM-30, 6 (1982), 1379-1385.
|
| |
18
|
ELMAGHRABY, S.E. On the expected duration of PERT type networks. Manage. Sci. 13 (1967), 469-481.
|
| |
19
|
FLATTO, L., AND HAHN, S. Two parallel queues created by arrivals with two demands. SIAM J. AppL Math 44 (1984), 1041-1053.
|
| |
20
|
GELENBE, E., AND LIU, Z. Performance analysis approximations for parallel processing on multiprocessor systems. In IFIP Working Conference on Parallel Processing (Pisa, Italy, Apr.) North-Holland, New York, 1988, pp. 363-375.
|
| |
21
|
|
| |
22
|
GELENBE, E., NELSON, P., PHILIPS, T., AND TANTAWI, A. The asymptotic processing time for a model of parallel processing. In Proceedings of the National Computer Conference (Las Vegas). 1986.
|
| |
23
|
|
| |
24
|
|
| |
25
|
|
| |
26
|
|
| |
27
|
KINGMAN, J. F.C. The ergodic theory of subadditive stochastic processes. J. Roy. Statist. Soc. Set. B 30 (1968), 499-510.
|
| |
28
|
KINGMAN, j. F.C. Subadditive ergodic theory. Ann. Prob 1 (1973), 883-909.
|
| |
29
|
KINGMAN, J. F. C. Subadditive processes. In I~cole d'Et6 de Probabilit6 de Saint-Hour, P.-L. Hennequin, ed. Lecture Notes in Mathematics, vol. 539. Springer-Verlag, New York, 1976, 165-223.
|
| |
30
|
|
| |
31
|
LIU, Z. Evaluation des performances d~applications parallrles sur des systrmes multiprocesseurs. Rapport de DEA, Univ. of Paris-Sud, Paris, France, Sept. 1986.
|
| |
32
|
LOYNES, R.M. The stability of queues with non independent inter-arrival and service times. Proc. Cambridge Ph. Soc. 58 (1962), 497-520.
|
| |
33
|
MARSAN, M. A., BALBO, G., CONTE, G., AND GREGORETTI, F. Modeling bus contention and memory interference in a multiprocessor system. IEEE Trans. Comput. C-32, 1 (Jan. 1983), 60-71.
|
| |
34
|
MARSAN, M. A., AND GREGORETTI, F. Memory interference models for a multiprocessor system with a shared bus and a single external common memory. Microproc. Microprog. 7 (1981), 124-133.
|
| |
35
|
MILUTINOVI(;, V., FORTES, J. A. B., AND JAMIESON, L.H. A multimicroprocessor architecture for real-time computation of a class of DFT algorithms. IEEE Trans. ASSP ASSP-34, 5 (1986), 1301-1309.
|
| |
36
|
|
| |
37
|
|
| |
38
|
SIGMAN, K. Regeneration in queues with regenerative input. Queue. Syst., to appear.
|
| |
39
|
|
| |
40
|
STOYAN, D. Comparison Methods for Queues and Other Stochastic Models (English translation), D. J. Daley, ed. Wiley, New York, 1984.
|
| |
41
|
|
| |
42
|
|
| |
43
|
|
| |
44
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
G.2