Performance evaluation of multistage interconnection networks with blocking--discrete and continuous time Markov models

• Autorzy: Badrah A. , Czachórski T. , Domańska D. , Fourneau J.-M. , Quessette F.
• Języki publikacji: EN

Abstrakty

EN

We analyse the performances of building blocks of multistage interconnection networks with blocking. Both continuous and discrete time Markov models are used to study the behavior of such entities in presence of various types of input streams. It is shown that the states of the queues within the entity are correlated due to the blocking phenomena.

PL

Artykuł opisuje użycie łańcucha Markowa do analizy wydajności bloków, z których zbudowana jest wielostanowiskowa sieć połączeń z blokowaniem. Tego rodzaju sieć połączeń spełnia ważną rolę w procesie projektowania efektywnych architektur wieloprocesorowych. Jednakże duży rozmiar takich sieci, jak również charakterystyczne dla ich pracy zjawisko blokowania powodują, że są one bardzo trudne do analizy. Modele takich wielopoziomowych sieci są z reguły oparte na dekompozycji - poszczególne przełączniki rozważane są osobno, a prawdopodobieństwa blokowania uzyskuje się na drodze iteracyjnego dochodzenia do punktu zbieżności. W artykule zaproponowano metodę analizy opartą na dekompozycji na podsieci większe od pojedynczego przełącznika. Opisano ciągły i dyskretny model Markowa rozważanej podsieci oraz przedstawiono uzyskane wyniki numeryczne.

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Archiwum Informatyki Teoretycznej i Stosowanej
• Rocznik: 2002
• Tom: T. 14, z. 2
• Strony: 145--161
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Badrah A.

• PRiSM, University de Versailles Saint-Quentin 45 Av. des Etats Unis, 78035 Versailles, France

autor

Czachórski T.

• Institute of Theoretical and Applied Informatics Polish Academy of Sciences 44-100 Gliwice, Bałtycka 5, Poland

autor

Domańska D.

• Institute of Theoretical and Applied Informatics Polish Academy of Sciences 44-100 Gliwice, Bałtycka 5, Poland

autor

Fourneau J.-M.

• PRiSM, University de Versailles Saint-Quentin 45 Av. des Etats Unis, 78035 Versailles, France

autor

Quessette F.

• PRiSM, University de Versailles Saint-Quentin 45 Av. des Etats Unis, 78035 Versailles, France

Bibliografia

• [1] Bermond J.C. and Fourneau J.M., Independent Connection : an easy characterization of Baseline- equivalent networks. Int. Conf. Parallel Processing, USA, 1988.
• [2] Feng, T. and Wu, C. On a Class of Multistage Interconnection Networks, IEEE Trans, on Computers, Vol. C29, pp. 694-702, 1980.
• [3] Lawrie, D. H. Access and Alignment of Data in an A.P., IEEE Trans.on Computers, Vol. C24, pp. 1145-1155, 1975.
• [4] Mokdad L., Méthodes et outils pour l'évaluation des performances des réseaux informatiques. Phd thesis, PRiSM, UniversitVe de Versailles, 1997.
• [5] Plateau B., On the Stochastic Structure of Parallelism and Synchronization Models for Distributed Algorithms, Proc. ACM Sigmetrics Conference on Measurement and Modelling of Computer Sys¬tems, Austin, Texas, August 1985.
• [6] Plateau B., Fourneau J.M., Lee K.H. PEPS: A Package for Solving Complex Markov Models of Parallel Systems, Proceedings of the 4th Int. Conf. on Modelling Techniques and Tools for Computer Performance Evaluation, Palma de Majorca, Spain. Sept. 1988.
• [7] Plateau B., Fourneau J.M., Solving complex Markov models of parallel systems, Journal of Parallel and Distributed Computing, Vol 12, N4, P370-387, 1991.
• [8] Saad Y., Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 29(1): 208-227, Febr. 1992.
• [9] Sidje R. B., Parallel Algorithms for Large Sparse Matrix Exponentials: application to numerical transient analysis of Markov processes, PhD thesis, University of Rennes 1, July 1994.
• [10] Stewart W.J., An Introduction to the Numerical Solution of Markov Chains, Princeton Academic Press, 1994.
• [11] Stewart W. J. MARCA: Markov Chain Analyzer, IRISA Publication interne no. 45, Rennes. Juin 1976.
• [12] Stewart W. J. MARCA: Markov Chain Analyzer, IEEE Computer Repository, No. R 76 323, 1976.
• [13] Woodward M. E. Communication and Computer Networks - Modelling with discrete-time queues, Pentech Press, London 1993.