Методи і засоби побудови моделей поведінки небазових відмовостійких багатопроцесорних систем
| dc.contributor.author | Морозов, Костянтин В’ячеславович | |
| dc.date.accessioned | 2021-04-08T09:16:07Z | |
| dc.date.available | 2021-04-08T09:16:07Z | |
| dc.date.issued | 2021 | |
| dc.description.abstracten | The thesis is devoted to the problem of building graph-logical models (GL models) of non-basic fault-tolerant multiprocessor systems (FTMS) for calculating their reliability parameters by means of carrying out statistical experiments with the above mentioned models. A method for transforming of GL-models by modifying the expression of any edge function of so-called MLE-model is proposed. The method is based on changing either any one or both two fragments of the edge function’s expression and allows modifying the model so that on some system state vectors, it starts to show an operable and/or inoperable state in contrast to the original one. The boundaries of influence for general case of modification of both single and several edge functions on change of the behavior of the model is analyzed. For the first time, an analytical apparatus that allows to determine the state vector of t-diagnosable FTMS based on the results of mutual testing of processors, according to the Preparata-Metze-Chen model (PMC-model), for arbitrary topology of connections between them has been proposed. For the first time, a method of building GL-models of so-called weighted systems, in which each component has a certain weight that characterizes its contribution to the performance of the system as a whole as well as a generalization of method of building GL-models, based on the usage of multivalued logic edge functions allowing them to be used as models of systems for which, as well as for their components, more than two states of operability are available are proposed. A method of building GL-models of hierarchical systems by means of composition of several MLE-models as well as a method of building models of systems consisting of several subsystems and having a sliding reserve are proposed. | uk |
| dc.description.abstractru | Диссертация посвящена проблеме построения графо-логических моделей (GL моделей) небазовых отказоустойчивых многопроцессорных систем (ОМС) в целях расчета их параметров надежности путем проведения статистических экспериментов с вышеупомянутыми моделями. ОМС, состоящая из n процессоров и остающаяся работоспособной при выходе из строя не более, чем m любых из них называется базовой. Все остальные системы, не соответствующие данному критерию, называются небазовыми. Один из эффективных методов расчета параметров надежности ОМС, в том числе небазовых, основан на проведении статистических экспериментов с так называемыми графо-логическими моделями, описывающими поведение системы в потоке отказов. Графо-логическая модель представляет собой неориентированный граф, ребрам которого соответствуют булевы реберные функции, зависящие от так называемого вектора состояния системы, каждый элемент которого соответствует состоянию одного из процессоров системы и принимает значение 1, если тот является работоспособным и 0 в противном случае. Если реберная функция принимает нулевое значение, соответствующее ей ребро, исключается из графа модели. Связность последнего характеризует состояние системы в потоке отказов: потеря связности графом соответствует потере работоспособности системой. Известен ряд методов, позволяющих строить различные GL-модели, каждая из которых имеет свои преимущества и недостатки. В частности, так называемые МВР-модели (минимум выпадающих ребер) имеют такое свойство: они теряют минимальное число ребер на векторах с кратностью отказов, на единицу превышающей степень отказоустойчивости системы. Кроме того, они базируются на циклических графах, процесс определения связности которых является тривиальным. Однако, алгоритм построения этой разновидности моделей (как и некоторых других) применим только для базовых ОМС. Построение GL-модели для небазовой системы может происходить путем модификации некоторой базовой модели, достаточно близкой к искомой, в результате чего на некотором множестве так называемых блокируемых векторов поведение моделей начинает отличаться. Такая модификация может происходить путем изменения структуры графа модели (проведение дополнительных ребер), изменения выражений реберных функций, или путем сочетания этих подходов. В работе рассматривается второй подход, основанный на модификации только выражений реберных функций, в результате чего граф модели остается циклическим. В результате анализа алгоритма построения реберных функций МВР-модели замечено, что их выражения состоят из двух частей. Предложен метод преобразования GL-моделей за счет модификации выражения любой реберной функции МВР-модели. Метод основан на изменении как одной, так и обеих частей выражения реберной функции и позволяет модифицировать модель так, что на некоторых векторах состояния системы она, в отличие от оригинальной, начинает показывать работоспособное и/или неработоспособное состояние. Проанализированы свойства модифицированных моделей, сформулированы и доказаны утверждения, позволяющие определять количество и множество блокируемых векторов в соответствии с параметрами модификации и вида модифицируемой функции. Также выполнен анализ влияния модификации на поведение МВР-модели для случая, когда модифицированная модель используется в качестве вспомогательной при ее построении. Получена оценка максимального количества векторов, которые могут быть блокированы предложенным методом. Определены функции и параметры их модификации, которые позволяют достичь этого количества блокируемых векторов. Проанализированы границы влияния для общего случая модификации как одной, так и нескольких реберных функций на изменение поведения модели. Впервые выполнен анализ необходимости модификации нескольких функций МВР-модели. Обнаружено, что в случае одновременной модификации нескольких реберных функций может проявляться побочный эффект в виде блокировки векторов с повышенной кратностью отказов. Получены критерии, позволяющие избежать его в общем случае, а также критерии выбора пар функций для случая модификации двух реберных функций. Впервые предложен аналитический аппарат, позволяющий определять вектор состояния t-диагностируемой ОМС на основе результатов взаимного тестирования процессоров, согласно модели Препараты-Метце-Чена (ПМЧ-модель), для произвольной топологии связей между ними. Метод основан на формировании и преобразовании булевого уравнения специального вида. Сформулированы рекомендации относительно возможных стратегий выбора пар процессоров для проведения дальнейших тестов. Получена оценка эффективности предложенного метода для заданного множества тестовых проверок, которое может быть представлено с помощью диагностического графа. Впервые предложен метод построения моделей так называемых взвешенных систем, в которых каждый компонент имеет некоторый вес, характеризующий его вклад в работоспособность системы в целом. В частности, взвешенная базовая система (или взвешенная k-из-n система) остается работоспособной до тех пор, пока суммарный вес всех ее работоспособных компонентов остается не меньшим некоторого порогового значения. Предложенный метод построения GL-моделей таких систем на базе МВР моделей основан на ni-кратном дублировании соответствующих элементов вектора состояния системы, выбирая значения ni пропорциональными весам соответствующих компонентов системы. Метод может быть применен для случаев весов, представленных как целыми, так и рациональными числами. Впервые предложено обобщение метода построения GL-моделей, основанное на использовании в качестве реберных функций многозначной логики. Это позволяет использовать их для построения моделей систем, для которых, как и их компонентов характерны более двух состояний работоспособности. То есть, в случаях, когда кроме полностью работоспособного и неисправного имеют место дополнительные состояния частичной работоспособности. Причем количества таких состояний как у системы, так и у каждого из ее компонентов могут различаться между собой. Предложен метод построения GL-моделей иерархических систем путем композиции нескольких МВР-моделей, а также метод построения моделей систем, состоящих из нескольких подсистем, и имеющих скользящий резерв, основанный на построении вспомогательных моделей для каждой из подсистем с последующим сочетанием значений их реберных функции во входном векторе результирующей модели. Разработано программное обеспечение, позволяющее выполнять эксперименты с модифицированными GL-моделями, а также определять вектор состояния системы согласно результатам тестовых проверок, согласно предложенному в работе методу. Получены экспериментальные данные, подтверждающие достоверность теоретически полученных результатов. | uk |
| dc.description.abstractuk | Дисертація присвячена проблемі побудови графо-логічних моделей (GL-моделей) небазових відмовостійких багатопроцесорних систем (ВБС) з метою розрахунку їх параметрів надійності шляхом проведення статистичних експериментів із вищезгаданими моделями. Запропоновано метод перетворення GL-моделей за рахунок модифікації виразу будь-якої реберної функції так званої МВР-моделі. Метод базуються на зміні як однієї, так і обох частин виразу реберної функції та дозволяє модифікувати модель так, що на деяких векторах стану системи вона, на відміну від оригінальної, починає показувати роботозданий і/або нероботоздатний стан. Проаналізовано межі впливу для загального випадку модифікації як однієї, так і кількох реберних функцій на зміну поведінки моделі. Вперше запропоновано аналітичний апарат, що дозволяє визначати вектор стану t-діагностованої ВБС на основі результатів взаємного тестування процесорів, згідно із моделлю Препарати-Метца-Чена (ПМЧ-модель), для довільної топології зв’язків між ними. Вперше запропоновано метод побудови GL-моделей так званих зважених систем, в яких кожний компонент має деяку вагу, що характеризує його вклад в роботоздатність системи в цілому, а також узагальнення методу побудови GL-моделей, що базується на використанні в якості реберних функцій багатозначної логіки та дозволяє використовувати їх для побудови моделей систем, для яких, як і їх компонентів характерні більше двох станів роботоздатності. Запропоновано метод побудови GL-моделей ієрархічних систем шляхом композиції декількох МВР-моделей, а також моделей систем, що складаються з кількох підсистем та мають ковзний резерв. | uk |
| dc.format.page | 30 с. | uk |
| dc.identifier.citation | Морозов, К. В. Методи і засоби побудови моделей поведінки небазових відмовостійких багатопроцесорних систем : автореф. дис. … канд. техн. наук. : 05.13.05 – комп’ютерні системи та компоненти / Морозов Костянтин В’ячеславович. – Київ, 2021. – 30 с. | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/40486 | |
| dc.language.iso | uk | uk |
| dc.publisher | КПІ ім. Ігоря Сікорського | uk |
| dc.publisher.place | Київ | uk |
| dc.subject | відмовостійкі багатопроцесорні системи | uk |
| dc.subject | графо-логічні моделі | uk |
| dc.subject | надійність | uk |
| dc.subject | модель Препарати-Метце-Чена | uk |
| dc.subject | зважені k-з-n системи | uk |
| dc.subject | ієрархічні системи | uk |
| dc.subject | ковзний резерв | uk |
| dc.subject | fault-tolerant multiprocessor systems | uk |
| dc.subject | graph-logical models | uk |
| dc.subject | reliability | uk |
| dc.subject | Preparata-Metze-Chen model | uk |
| dc.subject | weighted k-out-of-n systems | uk |
| dc.subject | hierarchical systems | uk |
| dc.subject | sliding reserve | uk |
| dc.subject | отказоустойчивые многопроцессорные системы | uk |
| dc.subject | графо логические модели | uk |
| dc.subject | надежность | uk |
| dc.subject | модель Препараты-Метце-Чена | uk |
| dc.subject | взвешенные k-из-n системы | uk |
| dc.subject | иерархические системы | uk |
| dc.subject | скользящий резерв | uk |
| dc.subject.udc | 004.05 | uk |
| dc.title | Методи і засоби побудови моделей поведінки небазових відмовостійких багатопроцесорних систем | uk |
| dc.type | Thesis | uk |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- Morozov_aref.pdf
- Розмір:
- 945.59 KB
- Формат:
- Adobe Portable Document Format
- Опис:
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 9.01 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: