Zdolność sieci procesorów typu sześcian 4-wymiarowy do lokalizacji dwóch niezdatnych procesorów metodą porównawczą

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

Warianty tytułu

EN

Capability of 4-dimensional cube type degradable processors' network to identify two faulty processors

• Języki publikacji: PL

Abstrakty

PL

W artykule opisano model formalny struktury logicznej sieci procesorów typu sześcian 4-wymiarowy oraz właściwości diagnozowania sieci metodą porównawczą MM*. Określono wpływ stopnia degradacji sieci na zmianę jej 2-diagnozowalności, jak również na zmianę jej zdolności do lokalizacji dwóch niezdatnych procesorów. Posługując się zbiorem węzłów wewnętrznie stabilnych struktury cyklicznej o p procesorach (p ≥ 6), określono warunek konieczny i wystarczający, aby struktura ta nie była strukturą 2-diagnozowalną i wyznaczono zbiór takich struktur. Określono częstość zdarzenia, że diagnozowanie metodą porównawczą MM* cyklicznej sieci typu sześcian 4-wymiarowy o p procesorach, która nie jest siecią 2-diagnozowalną, nie zapewni zlokalizowania dwóch niezdatnych procesorów sieci.

EN

The paper gives a formal model of a logical structure of the 4-dimensional cubic-type processor network. It describes the rules of diagnosing the network using the comparison method MM*. The known conditions of the diagnosability of the network (for this method) for the general case perspective were given. In the article, the influence of the degree of degradation of the network on the changes of its 2-diagnosibility for testing with the MM* method was investigated. In the summary, the conclusions arising from the results presented in this article have been formulated.

Słowa kluczowe

PL

informatyka; diagnostyka systemowa; model porównawczy; struktura logiczna sieci; sieci procesorowe typu sześcian

EN

informatics; comparison diagnosis; network logical structure; hypercube network

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

Twórcy

autor

Zieliński Z.

autor

Strzelecki Ł.

autor

Kulesza R.

• 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, 1, 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 -1O, 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, WAT, Warszawa, 16, 2001, 19-34.
• [11] R. Kulesza, Problemy przeliczania optymalnych struktur opiniowania diagnostycznego, Biuletyn Instytutu Automatyki i Robotyki, WAT, Warszawa, 20, 2004, 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, Monographs On System Dependability Technical Approach To Dependability, Oficyna Wydawnicza Politechniki Wrocławskiej, 2010, 65-78.
• [15] R. Kulesza, Z. Zieliński, Metoda generowania struktur logicznych sieci procesorów o łagodnej degradacji typu 4-wymiarowego sześcianu, Biul. WAT, 60, 4, 2011.
• [16] 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.
• [17] 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, 2005, 165-175.
• [18] J. Maeng, M. Malek, A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems, Digest Int'l Symp. FTC, 1981, 173-175.
• [19] M. Malek, A Comparison Connection Assignment for Diagnosis of Multiprocessor Systems, Proc. Seventh Int'l Symp. Computer Architecture, 1980, 31-35.
• [20] F. P. Preparata, G. Metze, R. T. Chien, On the Connection Assignment Problem of Diagnosable Systems, IEEE Trans. Comput., 6, 1967.
• [21] A. Sengupta, A. T. Dahbura, On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach, IEEE Trans. Comput., 41, 11, 1992, 1386-1396.
• [22] 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.
• [23] D. Wang, Diagnosability of Hypercubes and Enhanced Hypercubes under the Comparison Diagnosis Model, IEEE Trans. Comput., 48, 12, 1999, 1369-1374.
• [24] X. Yang, Y. Y. Tang, Efficient Fault Identification of Diagnosable Systems under the Comparison Model, IEEE Trans. Comput., 56, 12, 2007, 1612-1618.
• [25] Z. Zieliński, Algorytm wyznaczania wzorca alternatywnych stanów niezdatności systemu diagnozowanego metodą opiniowania diagnostycznego, Biul. WAT, 4, 2008, 219-232.
• [26] Z. Zieliński, Ł. Strzelecki, R. Kulesza, Diagnosability characterization of the 4-dimensional cube type soft degradable processors' network, Monographs On System Dependability - Problems of Dependability and Modelling, Oficyna Wydawnicza Politechniki Wrocławskiej, 2011, 283-296.