Using excess code to design fault-tolerant topologies

Размещено на http://www.allbest.ru/

USING EXCESS CODE TO DESIGN FAULT-TOLERANT TOPOLOGIES

Heorhii Loutskii, Artem Volokyta,

Pavlo Rehida, Olexandr Goncharenko

Annotation

Urgency of the research. The task of increasing fault tolerance is one of the key tasks in constructing a computing system and in modernizing an already existing one. Particular attention is paid to it when building multicomputer systems or clusters. The most interesting ways to increase fault tolerance is to use the topological structure of the system to bypass the malfunction and use one or another element of the system to replace the faulty. Of course, this requires the development of a specific topology. The article deals with the development offault-tolerant versions of popular topologies, such as quasiquantum and hypercube, based on the excess code 0/1 /-1.

Target setting. An important part of any multicomputer system or cluster is its topological structure. This structure defines the routing of messages in the system, speed of message transmission, and level offault-tolerance of a system. The article proposes a method for increasing fault-tolerance based on the use of excess code. topology binary code tolerant

Actual scientific researches and issues analysis. Synthesis of topologies such as the hypercube or the de Bruin topology is well studied and described now, there are papers consider methods for increasing the fault-tolerance that based on usage of additional nodes that duplicate current nodes. Other papers consider using a tree-based routing to improve fault-tolerance of the system.

Uninvestigated parts of general matters defining. Now the possibilities of using excess code 0/1/-1 for creating new fault-tolerant topologies based on existing synthesis methods are unconsidered.

The research objective. The task is to describe the synthesis offault tolerant topologies, the consideration of the possibilities of using their features and the analysis of the main characteristics in comparison with each other and with classic versions based on binary code.

The statement of basic materials. The synthesis of hypercube and de Bruin topology is described on the basis of the usual binary code and the redundant code 0/1 / -1, the possibilities of using redundancy are considered, first of all, to increase the fault-tolerance, a comparative analysis of all of these topologies is carried out.

Conclusions. The analysis of characteristics is performed, the main advantages and disadvantages of the proposed topological structures are highlighted, suggestions for their improvement are made.

Keywords: fault tolerance; de Bruin; hypercube; excess code.

Fig.: 13. Table: 7. References: 8.

Анотація

Георгій Луцький, Артем Волокита, Павло Регіда, Олександр Гончаренко

ВИКОРИСТАННЯ НАДЛИШКОВОГО КОДУ ДЛЯ ПОБУДОВИ ВІДМОВОСТІЙКИХ ТОПОЛОГІЙ

Актуальність теми дослідження. Завдання підвищення відмовостійкості є одним із головних завдань при побудові обчислювальної системи і при модернізації вже існуючої. Особливу увагу їй приділяють при побудові мульти- комп'ютерних систем чи кластерів. Найбільш цікавими способами збільшення відмовостійкості є використання топологічної структури системи для обходу несправності та використання того чи іншого елемента системи для заміщення несправного. Звісно, це потребує розробки специфічної топології. У статті розглянуто розробку відмо- востійких версій популярних топологій, таких як квазіквантова та гіперкуб, на основі надлишкового коду 0/1/-1.

Постановка проблеми. Важливою частиною будь-якої мультикомп 'ютерної системи є її топологічна структура. Від неї залежить маршрутизація повідомлень у системі, швидкість передачі повідомлень і відмовостійкість. У статті запропоновано метод для підвищення відмовостійкості, що ґрунтується на використанні надлишкового коду.

Аналіз останніх досліджень і публікацій. Нині добре описано синтез таких топологій, як гіперкуб чи топологія де Бруйна, є роботи, що розглядають методи збільшення відмовостійкості за допомогою дублювання обчислювальних елементів. Також наявні роботи, що розглядають використання маршрутизації на основі дерев для покращення відмовостійкості системи.

Виділення недосліджених частин загальної проблеми. Не розглянутими на сьогодні залишаються можливості застосування надлишкового кодування 0/1/-1 для створення нових відмовостійких топологій на основі вже існуючих.

Постановка завдання. Завданням є опис синтезу відмовостійких топологій, розгляд можливостей використання їхніх особливостей та аналіз основних характеристик у порівнянні між собою та з класичними версіями на основі двійкового коду.

Виклад основного матеріалу. Описано синтез гіперкуба та топології де Бруйна на основі звичайного двійкового коду та надлишкового коду 0/1/-1, розглянуто можливості використання надлишковості, передусім для підвищення відмовостійкості, проведено порівняльний аналіз усіх згаданих топологій.

Висновки відповідно до статті. Виконано аналіз характеристик, виділено основні переваги та недоліки запропонованих топологічних структур, висунуто пропозиції щодо їх покращення.

Ключові слова: відмовостійкість; де Бруйн; гіперкуб; надлишковий код.

Рис.: 13. Табл.: 7. Бібл.: 9.

Target setting

An important part of any multicomputer system or cluster is its topological structure. It describes how computing elements are interconnected. This structure defines the routing of messages in the system, speed of message transmission, and level of fault- tolerance of a system. Level of fault-tolerance represents the ability of the system to function correctly in the failure of its constituent parts. Therefore, we propose a method to improve fault tolerance, based on the usage of excess code.

Actual scientific researches and issues analysis

Synthesis of topologies such as the hypercube or the de Bruin topology (also called quasi-quantum) is well studied and described. Many papers consider methods for increasing the fault-tolerance that based on usage of additional nodes that duplicate current nodes. Other papers consider using a tree-based routing to improve fault-tolerance of the system and to prevent locks.

Uninvestigated parts of general matters defining. Now the possibilities of using excess code 0/1/-1 for creating new fault-tolerant topologies based on existing synthesis methods are unconsidered.

The research objective

The purpose of the research is a synthesis of new topologies based on quasi-quantum and hypercube topologies using an excess code for encoding nodes numbers. Also, it is necessary to make a detailed analysis of the system's characteristics and routing capabilities. Special attention will be paid to the issues of fault-tolerance.

The statement of basic materials

The task of topology synthesis defined: there are M nodes, their numbers are encoded by some code. Usually, M = B^N, where B - the basis of the chosen numeral system or code, N - a numeral bit capacity of nodes numbers. One of the goals of this task to get for each node all codes of its neighbors. To achieve that some transformation with node's code is used.

Basic definitions

De Bruin topology and the hypercube are quite convenient in terms of routing. In the classic version [1-4], the binary numeral system is used for encoding of nodes numbers. It means, the maximal count of nodes for N - bit code is 2^N The difference between these topologies is as follows: to synthesis de Bruin topology Shuffle transformation is used, and to synthesis hypercube Exchange is used. In the binary numeral system, these approaches looks like shift and bit's inversion respectively.

Synthesis of topology using binary code. Below, the synthesis process for each of the selected topologies in the case of N=2 and N=3 is shown.

In de Bruin topology getting of neighbor node's code performs through shifts on left and right with insertion 0 or 1 in released bit. Table 1 shows synthesis of this topology for case N = 2, table 2 - for N = 3.

Table 1

De Bruin topology synthesis for 2-bits binary code