Spectral performance evaluation of parallel processing systems. (English) Zbl 0981.68056
Summary: The aim of this paper is that spectral determinants are objects that can be effectively used as a performance prediction tool for the modern parallel processing systems. In the aim to confirm this we give the matrix representation of the linear evolution operator of the certain class of parallel processing systems. An explicit polynomial expression of the corresponding spectral determinant has been established and eigenvalues were computed. Derived eigenvalues were validated against the results of the simulation. The strong agreement between computed results and those obtained through the simulation has been found.
MSC:
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 81Q50 | Quantum chaos |
Keywords:
parallel processing systemsReferences:
| [1] | Allen, A. O., Probability, statistics and queueing theory with computer science applications (1978), Academic Press: Academic Press New York · Zbl 0455.60077 |
| [2] | Bak, P.; Tang, C.; Weisenfeld, K., Self-organised criticality, Phys Rev A, 38, 364-374 (1988) · Zbl 1230.37103 |
| [3] | Baskett, F.; Chandy, K. M.; Muntz, R. R.; Palacios, F. G., Open, closed and mixed network of queues with different classes of customers, J Ass Comput Mach, 22 (1975) · Zbl 0313.68055 |
| [4] | Bandrakhar, D. P., Analysis of memory interference in multiprocessors, IEEE Trans Comput, C-24, 9, 897-906 (1975) · Zbl 0308.68051 |
| [5] | Buzen, J. P., Computational algorithms for closed queueing networks with exponential servers, J Ass Comput Mach, 16, 527-531 (1973) · Zbl 0261.68031 |
| [6] | Crovella M, Bianchini MR, LeBlanc T, Markatos E, Wisniewski R. Using communication-to-computation ratio in parallel program design and performance prediction. In: Proceedings of the Fourth IEEE Symposium on Parallel and Distributed Processing. Texas: Dallas; 1992. p. 238-45; Crovella M, Bianchini MR, LeBlanc T, Markatos E, Wisniewski R. Using communication-to-computation ratio in parallel program design and performance prediction. In: Proceedings of the Fourth IEEE Symposium on Parallel and Distributed Processing. Texas: Dallas; 1992. p. 238-45 |
| [7] | Cvitanović, P., Periodic orbits as the skeleton of classical and quantum chaos, Physica D, 51, 138-159 (1991) · Zbl 0744.58013 |
| [8] | Cvitanović, P., Periodic orbit theory in classical and quantum mechanics, Chaos, Solitons & Fractals, 2, 1, 1-4 (1992) · Zbl 1055.37514 |
| [9] | Cvitanović P, Artuso R, Mainieri R, Vatay G. Classical and quantum chaos. http://www.nbi.dk/ChaosBook/; Cvitanović P, Artuso R, Mainieri R, Vatay G. Classical and quantum chaos. http://www.nbi.dk/ChaosBook/ |
| [10] | Demidovich, B. P.; Maron, I. A., Computational mathematics (1981), Mir Publishers: Mir Publishers Moscow · Zbl 0267.65003 |
| [11] | Denning, P. J.; Buzen, J. P., The operational analysis of queueing network models, ACM Comput Surv, 10, 225-261 (1978) · Zbl 0385.68038 |
| [12] | Freeman, W. J.; Yao, Y., Model of biological pattern recognition with spatially chaotic dynamics, Neural Networks, 3, 153-170 (1990) |
| [13] | Geurts F, Flocchini P. Searching for chaos in cellular automata: new tools for classification. In: Stonier RJ, Yu XH, editors. Complex systems: mechanisms of adaptation. IOS Press; 1994. p. 321-28; Geurts F, Flocchini P. Searching for chaos in cellular automata: new tools for classification. In: Stonier RJ, Yu XH, editors. Complex systems: mechanisms of adaptation. IOS Press; 1994. p. 321-28 |
| [14] | Geurts F. Compositional analysis of iterated relations: Dynamics and computations, thése de doctorat. Univ. Cath. de Louvain, Louvain-la-Neuve, Belgique; 1996; Geurts F. Compositional analysis of iterated relations: Dynamics and computations, thése de doctorat. Univ. Cath. de Louvain, Louvain-la-Neuve, Belgique; 1996 |
| [15] | Govindarajan R, Suciu F, Zuberek WM. Timed Petri net models of multithreaded multiprocessor architectures. In: Proceedings of the Seventh International Workshop on Petri Nets and Performance Models (PNPM’97). France: Saint Malo; 1997. p. 153-62; Govindarajan R, Suciu F, Zuberek WM. Timed Petri net models of multithreaded multiprocessor architectures. In: Proceedings of the Seventh International Workshop on Petri Nets and Performance Models (PNPM’97). France: Saint Malo; 1997. p. 153-62 |
| [16] | Halmos, P. R., Finite dimensional vector spaces (1958), Van Nostrand: Van Nostrand New York · Zbl 0107.01404 |
| [17] | Huber P, Jensen K, Shapiro RM. Hierarchies of coloured Petri nets. In: Proceedings of the 10th International Conference of Application and Theory of Petri Nets, Lecture Notes in Computer Science, vol. 483. Berlin: Springer; 1990. p. 313-43; Huber P, Jensen K, Shapiro RM. Hierarchies of coloured Petri nets. In: Proceedings of the 10th International Conference of Application and Theory of Petri Nets, Lecture Notes in Computer Science, vol. 483. Berlin: Springer; 1990. p. 313-43 |
| [18] | Jacqmot C. Load management in distributed computing systems: towards adaptive strategies. thése de doctorat. Univ. Cath. de Louvain, Louvain-la-Neuve, Belgique; 1996; Jacqmot C. Load management in distributed computing systems: towards adaptive strategies. thése de doctorat. Univ. Cath. de Louvain, Louvain-la-Neuve, Belgique; 1996 |
| [19] | Jensen, K., Coloured Petri nets and the invariant method, Theoret Comput Sci, 14, 317-336 (1981) · Zbl 0475.68035 |
| [20] | Joseph DT. MIRAGE: a model for latency in communication. Ph.D. Dissertation. Philadelphia: University of Pennsylvania, PA; 1992; Joseph DT. MIRAGE: a model for latency in communication. Ph.D. Dissertation. Philadelphia: University of Pennsylvania, PA; 1992 |
| [21] | Langton, C. G., Computation at the edge of chaos: phase transitions and emergent computation, Physica D, 42, 1-3, 12-37 (1990) |
| [22] | Li, T.; Yorke, J., Period 3 implies chaos, Am Math Monthly, 82, 985 (1975) · Zbl 0351.92021 |
| [23] | Mandelbrot, B. B., The fractal geometry of nature (1983), Freeman: Freeman New York · Zbl 0504.28001 |
| [24] | Marsan, M. A.; Gerla, M., Markov models for multiple bus multiprocessor systems, IEEE Trans Comput, C-31, 239-248 (1982) · Zbl 0479.68022 |
| [25] | Marsan, M. A.; Balbo, G.; Conte, G.; Gregoretti, F., Modelling bus contention and memory interference in a multiprocessor system, IEEE Trans Comput, C-32, 1, 60-72 (1983) |
| [26] | Marsan MA, Balbo G, Conte G, Donatelli S, Franceschinis G. Modelling with generalized stochastic Petri nets. Wiley series in parallel computing. New York: Wiley; 1994; Marsan MA, Balbo G, Conte G, Donatelli S, Franceschinis G. Modelling with generalized stochastic Petri nets. Wiley series in parallel computing. New York: Wiley; 1994 · Zbl 0843.68080 |
| [27] | Molloy, M. K., Performance analysis using stochastic Petri nets, IEEE Trans Comput, C-31, 9, 913-917 (1982) |
| [28] | Petri CA. Kommunikation mit automaten, Schriften des IIM Nr. 2. Bonn: Institut für Instrumentelle Mathematik; 1962; Petri CA. Kommunikation mit automaten, Schriften des IIM Nr. 2. Bonn: Institut für Instrumentelle Mathematik; 1962 |
| [29] | Ramamoorthy, C. V.; Ho, G. S., Performance evaluation of asynchronous concurrent systems using Petri nets, IEEE Trans Software Eng, SE-6, 5, 440-449 (1980) · Zbl 0444.68044 |
| [30] | Sandler, Y. M., Model of neural networks with selective memorization and chaotic behavior, Phys Lett A, 144, 462-466 (1990) |
| [31] | Sole, R. V.; Miramontes, O., Information at the edge of chaos in fluid neural networks, Physica D, 80, 171-180 (1995) · Zbl 0882.68118 |
| [32] | Strecker WD. Analysis of the instruction execution rate in certain computer structures. Ph.D. Thesis, Pittsburgh, PA: Carnegie-Mellon University; 1970; Strecker WD. Analysis of the instruction execution rate in certain computer structures. Ph.D. Thesis, Pittsburgh, PA: Carnegie-Mellon University; 1970 |
| [33] | Tomić D. Models for the performance evaluation of multiprocessor systems. Master thesis. ETF, Zagreb; 1985; Tomić D. Models for the performance evaluation of multiprocessor systems. Master thesis. ETF, Zagreb; 1985 |
| [34] | Vrsalović D, Siewiorek D. Performance analysis of multiprocessor based control systems. In: Proceedings of the Real-Time Systems Symposium; 1983. p. 73-78; Vrsalović D, Siewiorek D. Performance analysis of multiprocessor based control systems. In: Proceedings of the Real-Time Systems Symposium; 1983. p. 73-78 |
| [35] | Vrsalović, D.; Siewiorek, D.; Segall, Z.; Gehringer, E., Performance prediction and calibration for a class of multiprocessors, IEEE Trans Comput, C-37, 9, 1353-1365 (1988) |
| [36] | Zuberek WM, Bluemke I. Hierarchies of place/transition refinements in Petri nets. In: Proceedings of the Fifth IEEE International Conference on Emerging Technologies and Factory Automation. Hawaii: Kanai; 1996. p. 355-60; Zuberek WM, Bluemke I. Hierarchies of place/transition refinements in Petri nets. In: Proceedings of the Fifth IEEE International Conference on Emerging Technologies and Factory Automation. Hawaii: Kanai; 1996. p. 355-60 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
