Методи і засоби підтримки статистичних експериментів з GL-моделями при розрахунку показників надійності відмовостійких багатопроцесорних систем
Вантажиться...
Дата
2011
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 – Комп’ютерні системи та компоненти. Національний технічний університет України «Київський політехнічний інститут», м. Київ, 2011 р.
У дисертаційній роботі досліджуються і пропонуються методи та засоби, застосування яких дозволять підвищити ефективність розрахунку ймовірності безвідмовної роботи (ІБР) відмовостійких багатопроцесорних реконфігуровних систем ВБС управління. В основу такого розрахунку покладено метод статистичних експериментів з графо-логічними моделями (GL-моделями).
На основі порівняльного аналізу за різними параметрами обґрунтовано вибір використання саме 2р-моделі для розрахунку ІБР. Запропоновано модифікацію відомого методу, а також запропоновано новий алгоритм формування функцій базових ребер 2р-моделі, показано, що зазначені методи мають меншу складність.
Запропоновано ряд співвідношень для GL-моделей, що дають можливість прогнозувати складність моделей небазових ВБС ще до проведення процедури модифікації.
18
Пропонується автономний апаратний генератор двійкових векторів заданої ваги, побудований на основі керованих зсувних регістрів. Обґрунтовується доцільність застосування такого рішення для моделювання станів системи.
Запропоновано структуру спеціалізованої обчислювальної системи розрахунку ймовірності безвідмовної роботи ВБС, в якій реалізовані основні результати, отримані в дисертації.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 – Компьютерные системы и компоненты. Национальный технический университет Украины «Киевский политехнический институт», г. Киев, 2011 г. Диссертация посвящена разработке методов, алгоритмических и программно-аппаратных средств повышения эффективности расчета вероятности безотказной работы (ВБР) (за заданный промежуток времени) сложных отказоустойчивых многопроцессорных систем (ВБС) управления ответственными объектами критического применения. В основу указанного расчета положен метод статистических экспериментов с графо-логическими моделями (GL-моделями). В общем виде рассматриваемый метод расчета ВБР проектируемой ВБС состоит из следующих этапов: формирование и преобразование GL-модели на основе анализа параметров системы, формирование потока векторов состояния системы – X, выполнение эксперимента с GL-моделью для определения работоспособности системы на каждом векторе X, определение вероятности появления каждого вектора состояния X, накопление статистики, расчет ВБР и погрешности полученного результата. GL-модель представляет собой неориентированный граф, в котором ребра маркируются булевыми функциями. Ребро исключается из графа, если соответствующая реберная функция принимает нулевое значение на данном векторе X. Реберные функции зависят от индикаторных переменных xi, которые отображают состояние работоспособности соответствующего элемента ВБС. Связность графа GL-модели моделирует работоспособность системы в целом. Таким образом, GL-модель отражает зависимость состояния работоспособности системы от отказов ее элементов. В работе анализируются свойства двух известных GL-моделей циклического типа: канонической и 2р-модели. Исключительной характеристикой 2р-модели базовых систем K(m, n) является потеря только двух ребер при появлении векторов с m+1 нулевой компонентой (n – количество элементов системы, m – базовая степень отказоустойчивости системы). 19 Предложена формализация метода построения канонической GL-модели в виде рекурсивного выражения, для чего разработан способ нумерации множеств индикаторных переменных, отражающих состояние элементов системы. Предложена модификация известного алгоритма формирования реберных функций 2р-модели, в которой исключены сложная процедура минимизации и промежуточное построение канонической GL-модели. Разработан новый алгоритм формирования 2р-модели, в основу которого положено свойство наличия одинаковых составляющих в разных реберных функциях. Определены условия и рекомендации преимущественного использования каждого из методов. Доказано, что оба алгоритма имеют значительное преимущество перед известным аналогом. Получены соотношения для определения количества базовых ребер канонической и 2р-модели. Предложено ряд соотношений, которые позволяют оценить сложность трансформации базовых GL-моделей к небазовым, еще до проведения процедуры модификации, что позволяет разработчику прогнозировать время и оценить ресурсы необходимые для выполнения расчета. Проведен сравнительный анализ канонической GL-модели и 2р-модели по различным параметрам сложности, на основе которого сделан выбор использования именно 2р-модели для статистической оценки ВБР системы. Получил дальнейшее развитие способ предварительного анализа GL-модели на наличие и количество попарных реберных циклов, позволяющий упростить ее трансформацию и оценить сложность после трансформации. Такой анализ производится на основе дерева иерархии реберных функций, алгоритм построения которого предлагается. Выполнен анализ известных средств моделирования состояний системы, отмечены недостатки при использовании их для статистического метода оценки ВБР. Предлагается и обосновывается использование разработанного в диссертации генератора двоичных векторов на основе управляемых сдвиговых регистров. Управление предложенным генератором осуществляется специальным образом выбранными булевыми функциями. Доказано, что существуют такие функции управления, под воздействием которых генератор формирует последовательность векторов заданного веса, максимального периода без повторений своих состояний. Предложены алгоритмы проверки таких функций. Исследованы свойства функций управления, на основе которых показаны возможность упрощения их аналитического представления в виде ДНФ, а также возможность в значительной степени уменьшить сложность их поиска. В работе показано, что применение аппаратного бесповторного генератора позволяет в значительной мере повысить точность расчета ВБР методом статистических экспериментов с GL-моделями. Предложена структура специализированной вычислительной системы расчета безотказной работы ВБС. Описаны функции основных модулей предлагаемой системы. В системе реализованы главные практические результаты, полученные в диссертации.
Dissertation for the scientific degree of Candidate of Technical Sciences on specialty 05.13.05 – Computer systems and components. National Technical University of Ukraine “Kyiv Polytechnic Institute”, Kyiv, 2011. In this thesis the tools that allow efficiency increasing of reliability calculation of fault-tolerant multiprocessor systems (FTMS) are researched and proposed. The reliability calculation is based on the method of statistic experiments with graph-logic models (GL models). Comparative analysis on various parameters demonstrates the benefit of 2r-model usage to calculate the reliability. A modification of the known method, and a new algorithm for forming the basic functions of the 2r–model edges are proposed, the methods mention above have lower complexity. The equations, which enable to prognosis the complexity of the nonbasic FTMS GL-models, before the modification, is proposed. It is proposed autonomous generator of binary vectors of a given weight, based on controllable shift register. The efficiently of using such solution for modelling the system state vector is proved. The structure of a specialized computing system for calculating the reliability of the FTMC, which implements the main results obtained in the thesis is developed
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 – Компьютерные системы и компоненты. Национальный технический университет Украины «Киевский политехнический институт», г. Киев, 2011 г. Диссертация посвящена разработке методов, алгоритмических и программно-аппаратных средств повышения эффективности расчета вероятности безотказной работы (ВБР) (за заданный промежуток времени) сложных отказоустойчивых многопроцессорных систем (ВБС) управления ответственными объектами критического применения. В основу указанного расчета положен метод статистических экспериментов с графо-логическими моделями (GL-моделями). В общем виде рассматриваемый метод расчета ВБР проектируемой ВБС состоит из следующих этапов: формирование и преобразование GL-модели на основе анализа параметров системы, формирование потока векторов состояния системы – X, выполнение эксперимента с GL-моделью для определения работоспособности системы на каждом векторе X, определение вероятности появления каждого вектора состояния X, накопление статистики, расчет ВБР и погрешности полученного результата. GL-модель представляет собой неориентированный граф, в котором ребра маркируются булевыми функциями. Ребро исключается из графа, если соответствующая реберная функция принимает нулевое значение на данном векторе X. Реберные функции зависят от индикаторных переменных xi, которые отображают состояние работоспособности соответствующего элемента ВБС. Связность графа GL-модели моделирует работоспособность системы в целом. Таким образом, GL-модель отражает зависимость состояния работоспособности системы от отказов ее элементов. В работе анализируются свойства двух известных GL-моделей циклического типа: канонической и 2р-модели. Исключительной характеристикой 2р-модели базовых систем K(m, n) является потеря только двух ребер при появлении векторов с m+1 нулевой компонентой (n – количество элементов системы, m – базовая степень отказоустойчивости системы). 19 Предложена формализация метода построения канонической GL-модели в виде рекурсивного выражения, для чего разработан способ нумерации множеств индикаторных переменных, отражающих состояние элементов системы. Предложена модификация известного алгоритма формирования реберных функций 2р-модели, в которой исключены сложная процедура минимизации и промежуточное построение канонической GL-модели. Разработан новый алгоритм формирования 2р-модели, в основу которого положено свойство наличия одинаковых составляющих в разных реберных функциях. Определены условия и рекомендации преимущественного использования каждого из методов. Доказано, что оба алгоритма имеют значительное преимущество перед известным аналогом. Получены соотношения для определения количества базовых ребер канонической и 2р-модели. Предложено ряд соотношений, которые позволяют оценить сложность трансформации базовых GL-моделей к небазовым, еще до проведения процедуры модификации, что позволяет разработчику прогнозировать время и оценить ресурсы необходимые для выполнения расчета. Проведен сравнительный анализ канонической GL-модели и 2р-модели по различным параметрам сложности, на основе которого сделан выбор использования именно 2р-модели для статистической оценки ВБР системы. Получил дальнейшее развитие способ предварительного анализа GL-модели на наличие и количество попарных реберных циклов, позволяющий упростить ее трансформацию и оценить сложность после трансформации. Такой анализ производится на основе дерева иерархии реберных функций, алгоритм построения которого предлагается. Выполнен анализ известных средств моделирования состояний системы, отмечены недостатки при использовании их для статистического метода оценки ВБР. Предлагается и обосновывается использование разработанного в диссертации генератора двоичных векторов на основе управляемых сдвиговых регистров. Управление предложенным генератором осуществляется специальным образом выбранными булевыми функциями. Доказано, что существуют такие функции управления, под воздействием которых генератор формирует последовательность векторов заданного веса, максимального периода без повторений своих состояний. Предложены алгоритмы проверки таких функций. Исследованы свойства функций управления, на основе которых показаны возможность упрощения их аналитического представления в виде ДНФ, а также возможность в значительной степени уменьшить сложность их поиска. В работе показано, что применение аппаратного бесповторного генератора позволяет в значительной мере повысить точность расчета ВБР методом статистических экспериментов с GL-моделями. Предложена структура специализированной вычислительной системы расчета безотказной работы ВБС. Описаны функции основных модулей предлагаемой системы. В системе реализованы главные практические результаты, полученные в диссертации.
Dissertation for the scientific degree of Candidate of Technical Sciences on specialty 05.13.05 – Computer systems and components. National Technical University of Ukraine “Kyiv Polytechnic Institute”, Kyiv, 2011. In this thesis the tools that allow efficiency increasing of reliability calculation of fault-tolerant multiprocessor systems (FTMS) are researched and proposed. The reliability calculation is based on the method of statistic experiments with graph-logic models (GL models). Comparative analysis on various parameters demonstrates the benefit of 2r-model usage to calculate the reliability. A modification of the known method, and a new algorithm for forming the basic functions of the 2r–model edges are proposed, the methods mention above have lower complexity. The equations, which enable to prognosis the complexity of the nonbasic FTMS GL-models, before the modification, is proposed. It is proposed autonomous generator of binary vectors of a given weight, based on controllable shift register. The efficiently of using such solution for modelling the system state vector is proved. The structure of a specialized computing system for calculating the reliability of the FTMC, which implements the main results obtained in the thesis is developed