Metoda generowania struktur logicznych sieci procesorów o łagodnej degradacji typu 4-wymiarowego sześcianu

• Autorzy: Kulesza R. , Zieliński Z.

Warianty tytułu

EN

A method of logical structures generation of 4-dimensional cube type processors' network with soft degradation

• Języki publikacji: PL

Abstrakty

PL

W artykule podano model formalny struktury logicznej sieci procesorów typu sześcian czterowymiarowy oraz zdefiniowano pojęcie klasy kompozycji struktury. Zaproponowano metodę komponowania struktur logicznych sieci o określonych właściwościach za pomocą działań na wprowadzonej skondensowanej postaci struktury. Określono własności takich działań oraz podano zbiór wzorców, które mogą indukować poszukiwane struktury. Wyznaczono liczebności zbiorów spójnych i spójnych cyklicznych struktur etykietowanych oraz spójnych cyklicznych struktur nieetykietowanych, a także etykietowanych drzew o p ∈{4,..., 9} procesorach. W ogólnym zarysie przedstawiono sposób takiej reprezentacji geometrycznej struktury, który zawiera wszystkie procesory i linie transmisji danych oraz ma minimalną liczbę przecięć linii krawędziowych.

EN

A formal model of the logical structure of a 4-dimensional cube-type processor network is presented, and the concept of a composition structure class is defined. The paper proposes a method for creating logical network structures with specific properties with the help of actions on the proposed condensed structure form. Properties of such actions were defined, and a set of patterns were provided which may induce the searched structures. The number of coherent sets and coherent cyclic labelled structures as well as coherent cyclic non-labelled structures, as well labelled and non-labelled trees with processors were determined. The article presents (in general terms) geometric representation of the structure, which contains all the processors and data transmission lines and has a minimal number of intersections of edge lines, which is important for network management.

Słowa kluczowe

PL

informatyka; diagnostyka systemowa; struktura logiczna sieci; sieci typu sześcianu; systemy z tolerancją błędów

EN

informatics; system level diagnosis; network logical structure; hypercube network; fault tolerant systems

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Biuletyn Wojskowej Akademii Technicznej
• Rocznik: 2011
• Tom: Vol. 60, nr 4
• Strony: 245--358
• Opis fizyczny: Bibliogr. 25 poz., tab.

Twórcy

autor

Kulesza R.

autor

Zieliński Z.

• Wojskowa Akademia Techniczna, Wydział Cybernetyki, Instytut Teleinformatyki i Automatyki, 00-908 Warszawa, ul. S. Kaliskiego 2,

Bibliografia

• [1] A. Caruso, S. Chessa, P. Maestrini, P. Santi, Diagnosability of Regular Systems, J. Algorithms, vol. 1, no. 1, 2002, 1-12.
• [2] C. P. Chang, P. L. Lai, J. J. M. Tan, L. H. Hsu, Diagnosability of t-Connected Networks and Product Networks under the Comparison Diagnosis Model, IEEE Trans. Comput., 53, 2004, 1582-1590.
• [3] G. Y. Chang, G. H. Chen, G. J. Chang, (t, k)-Diagnosis for Matching Composition Networks, IEEE Trans. Comput., 55, 1, 2006, 88-92.
• [4] G. Y. Chang, G. H. Chen, G. J. Chang, (t, k)-Diagnosis for Matching Composition Networks under the MM* Model, IEEE Trans. Comput., 56, 1, 2007, 73-79.
• [5] S. L. Hakimi, A. T. Amin, Characterization of Connection Assignment of Diagnosable Systems, IEEE Trans. Comput., 23, 1, 1974, 86-88.
• [6] S. H. Hsieh, Y. S. Chen, Strongly Diagnosable Product Networks Under the Comparison Diagnosis Model, IEEE Trans. Comput., 57, 6, 2008, 721-732.
• [7] R. Kulesza, A. K. Wach, The Determination of a 2-optimal Digraphs Set for a One-Step Diagnosis of System. 9th IMECO TC-10, International Conference on Technical Diagnostics, September 1999, Wrocław, Poland, 153-158.
• [8] R. Kulesza, Z. Zieliński, J. Chudzikiewicz, Reconfiguration of the Ring Structure in a Hypercube Computer Network with Faulty Links, 9th IMEKO TC-10, International Conference on Technical Diagnostics, 22-24 September 1999, Wrocław, Poland, 159-164.
• [9] R. Kulesza, Podstawy diagnostyki sieci logicznych i komputerowych, Instytut Automatyki i Robotyki, Wydział Cybernetyki Wojskowej Akademii Technicznej, Warszawa, 2000, 222.
• [10] R. Kulesza, Metoda przeliczania 1-optymalnych struktur opiniowania diagnostycznego, Biuletyn Instytutu Automatyki i Robotyki, Wojskowa Akademia Techniczna, Warszawa, 2001, 16, 19-34.
• [11] R. Kulesza, Problemy przeliczania optymalnych struktur opiniowania diagnostycznego, Biuletyn Instytutu Automatyki i Robotyki, Wojskowa Akademia Techniczna, Warszawa, 2004, 20, 3-21.
• [12] R. Kulesza, Z. Zieliński, Wnikliwość diagnozowania sieci procesorów metodą porównawczą, Systemy czasu rzeczywistego, Postępy badań i zastosowania, Warszawa, WKŁ, 2009, 199-210.
• [13] R. Kulesza, Z. Zieliński, Diagnosis resolution of processors' network using the comparison method, Przegląd Elektrotechniczny (Electrical Review), 9, 2010, 157-162.
• [14] R. Kulesza, Z. Zieliński, The life period of the hypercube processors' network diagnosed with the use of the comparison method, Technical Approach To Dependability, Oficyna Wydawnicza Politechniki Wrocławskiej, 2010, 65-78.
• [15] P. L. Lai, J. J. M. Tan,C. H. Tsai, L. H. Hsu, The Diagnosability of the Matching Composition Network under the Comparison Diagnosis Model, IEEE Trans. Comput., 53, 8, 2004.
• [16] P. L. Lai, J. J. M. Tan, C. P. Chang, L. H. Hsu, Conditional Diagnosability Measures for Large Multiprocessor Systems, IEEE Trans. Comput., 54, 2, Feb. 2005, 165-175.
• [17] J. Maeng, M. Malek, A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems, Digest Int. I Symp. FTC, 1981, 173-175.
• [18] M. Malek, A Comparison Connection Assignment for Diagnosis of Multiprocessor Systems, Proc. Seventh Int. I Symp. Computer Architecture, 1980, 31-35.
• [19] F. P. Preparata, G. Metze, R. T. Chien, On the Connection Assignment Problem of Diagnosable Systems, IEEE Trans. Comput., 6, 1967.
• [20] A. Sengupta, A. T. Dahbura, On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach, IEEE Trans. Comput., 41, 11, Nov. 1992, 1386-1396.
• [21] A. K. Somani, O. Peleg, On Diagnosability of Large Fault Sets in Regular Topology-Based Computer Systems, IEEE Trans. Comput., 45, 8, 1996, 892-903.
• [22] D. Wang, Diagnosability of Hypercubes and Enhanced Hypercubes under the Comparison Diagnosis Model, IEEE Trans. Comput., 48, 12, 1999, 1369-1374.
• [23] X. Yang, Y. Y. Tang, Efficient Fault Identification of Diagnosable Systems under the Comparison Model, IEEE Trans. Comput., 56, 12, 2007, 1612-1618.
• [24] Z. Zieliński, Algorytm wyznaczania wzorca alternatywnych stanów niezdatności systemu diagnozowanego metodą opiniowania diagnostycznego, Biul. WAT, 4, 2008, 219-232.
• [25] Z. Zieliński, Ł. Strzelecki, R. Kulesza, Diagnosability characterization of the 4-dimensional cube type soft degradable processors' network, Monographs On System Dependability and Modelling, Oficyna Wydawnicza Politechniki Wrocławskiej, 2011, 283-296.