Синтез реконфигурированих однорідних клітинних мереж із вбудованими засобами тестового діагностування, що реконфігуруються

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

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

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

клітинний автомат інтегральний сигнатурний

Актуальність теми. З розвитком наноелектронних технологій на ринку надвеликих інтегральних схем (НВІС) з'явилися потужні за обчислювальними можливостями програмовані логічні інтегральні схеми (ПЛІС) типу FPGA і CPLD, які дозволяють створювати економічні обчислювальні системи з реконфігурованих однорідних клітинних мереж (ОКМ).

Сьогодні значна увага приділяеться розробці теоретичних і практичних аспектів побудови ОКМ. Із зростанням міри інтеграції і щільності компонування НВІС зростає вірогідність появи різних дефектів у процесі їх виробництва та експлуатації, що в цілому істотно впливає на показники надійності і відмовостійкої ОКМ на ПЛІС. Вагомий внесок у вирішення проблем тестового і функціонального діагностування, генерації тестів і моделювання несправностей, створення вбудованих засобів діагностування зробили вчені: П.П. Пархоменко, Е.С. Согомонян, А.П. Горяшко, В.Г. Тоценко, Л.А. Миронівський, Д.В. Сперанський, та інші.

Незважаючи на наявні досягнення в області тестового і функціонального діагностування, недостатньо відображуються особливості сучасної КМОП нанотехнології, пов'язаних з появою таких класів дефектів, як «замикання сусідніх ліній», «затримка фронту і зрізу» імпульсу, обумовлених сумірністю затримок сигналів у лініях зв'язку й активних елементах. Крім того, в існуючих системах генерації тестів, що перевіряються, і моделювання несправностей, орієнтованих на виявлення класу стійких несправностей константного типу не враховуються вимоги міжнародних стандартів проектування і виробників НВІС до частотних характеристик, і площі, займаної вбудованими діагностичними засобами.

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

Зв'язок роботи з науковими планами, програмами, темами. Розробка основних положень роботи здійснювалася на кафедрі автоматики і управління в технічних системах НТУ «ХПІ» відповідно до планів науково-дослідних робіт у рамках держбюджетної теми МОН України «Розробка методів прийняття рішень в умовах неповної інформації про об'єкт управління» (ДР№0103u001511), проведені роботи з модернізації автоматизованої установки «РОСТ» для вирощування лужно-галоїдних великогабаритних монокристалів відповідно до програми досліджень НАН України (Договір №А/2.2-08 від 31.01.2008 р. відповідно до Державної цільової науково-технічної програми «Розробка і освоєння мікроелектронних технологій, організація серійного випуску приладів і систем на їх основі» на 2008-2011 рр., затвердженої Постановою Кабінету Міністрів Україні від 21.11.2007 р. №1355 і розпорядженням Президії НАН України від 13.12.2007 р. №806 та від 31.01.2008 р. №111), відповідно до договору про творчу науково-технічне співробітництво між ІСМА та НТУ ХПІ, де здобувач був виконавцем окремих етапів.

Мета і завдання дослідження. Метою дисертаційної роботи є розробка та вдосконалення моделей, методів і процедур синтезу реконфігурованих однорідних клітинних мереж із вбудованими засобами тестового та функціонального діагностування, синтезу тестів, які реалізуються на ПЛІС.

Для досягнення сформульованої мети поставлені такі завдання:

- аналіз стану, тенденцій розвитку ОКМ і технологій реалізації систем технічного діагностування, сигнатурного моніторингу в реконфігурованих обчислювальних системах і ОКМ;

- розробка моделей, методів і процедур генерації тестів, що перевіряються для мереж клітинних автоматів (МКА) з врахуванням їх реалізації на ПЛІС і вимог міжнародних стандартів проектування цифрової техніки;

- розробка моделей, методів і процедур синтезу легкотестованих компонентів МКА на базі ПЛІС;

- аналіз і дослідження запропонованих методів генерації тестів і синтезу легкотестованих МКА, оцінка складності їх реалізації;

- розробка методів і процедур оптимального розміщення резервних модулів в одновимірних і двовимірних клітинних мережах з урахуванням апаратно-часових обмежень;

- розробка моделей і методів синтезу вбудованих засобів сигнатурного моніторингу для однорідних клітинних мереж;

- використання розроблених методів генерації тестів і легкотестованих ОКМ в комп'ютерних та інформаційно-управляючих системах.

Об'єкт дослідження - процеси логічного проектування, тестового, функціонального діагностування, реконфігурації та відновлення працездатності клітинних мереж і компонентів на одному кристалі.

Предмет дослідження - моделі, методи і процедури синтезу перевірних тестів і проектування легкотестованих ОКМ з вбудованими засобами сигнатурного моніторингу та відновлення працездатності.

Методи дослідження. Основні теоретичні результати дисертації базуються на основних положеннях: теорії цифрових автоматів, які були використані під час розробки автоматних моделей компонентів ОКМ і модифікації цих моделей для синтезу легкотестованих ОКМ, під час організації діагностичних експериментів і синтезу перевірних тестів з використанням характерних вхід-вихідних послідовностей осередків ОКМ; теорії графів для синтезу перевірних тестів у ОКМ без спостережуваних виходів осередків мережі; методів технічної діагностики для розробки процедур синтезу реконфігурованих ОКМ і розробки апаратних засобів вбудованого самотестування та модулів сигнатурного моніторингу ОКМ. Оцінка достовірності та ефективності результатів досліджень здійснена на основі комп'ютерних експериментів та аналізу даних, отриманих у лабораторних і виробничих умовах.

Наукова новизна отриманих результатів. Полягає в розробці моделей, методів і процедур синтезу реконфігурованих однорідних клітинних мереж на ПЛІС, верифікації їх справності вбудованої діагностичної інфраструктури сигнатурного моніторингу та відновлення працездатності.

Зокрема:

1. Вперше запропоновано і формально обгрунтовано методи синтезу перевірних тестів для одновимірних ОКМ з обмеженою спостережуваністю вихідних реакцій, засновані на використанні відмітних і характеристичних символів автоматної моделі осередки мережі; розроблені процедури генерації перевірних тестів для ОКМ із різними налаштуваннями мережі та визначено верхні межі довжини повних перевірних послідовностей, що дозволило виключити виконання трудомістких процедур моделювання несправностей.

2. Вперше запропоновано метод перетворення автоматних моделей клітинного автомата (КА) і визначений клас легкотестованих ОКМ, що мають відмінні та характеристичні символи для кожного стану КА, визначені необхідні й достатні умови існування відмінних і характеристичних послідовностей, що дозволяє в раз (де - число станів КА) скоротити довжину перевірної послідовності порівняно з канонічними методами синтезу.

3. Набули подальшого розвитку методи тестового діагностування ОКМ, запропоновано єдиний методологічний підхід до синтезу перевірних тестів, заснований на функціональних моделях несправностей, використанні автоматних моделей осередків мережі та методів теорії експериментів з автоматами, що дозволило розширити клас виявлених несправностей.

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

5. Набули подальшого розвитку методи модифікації автоматної моделі осередку ОКМ шляхом введення додаткового вхідного символу і вибору кодів станів, що породжують гамільтонів цикл у послідовності переходів станів КА, що забезпечує С-тестованості ОКМ і незалежність довжини перевіряє послідовності від розмірності мережі.

6. Набули подальшого розвитку методи і процедури синтезу одновимірних і двовимірних ОКМ з резервними ФМ, оптимального розміщення резервних ФМ і вибору маршруту обробки даних у структурі ОКМ із централізованим і розподіленим управлінням та чотирипортовими комутаційними модулями, що забезпечує мінімальність часових витрат на відновлення працездатності ОКМ без деградації продуктивності.

Практичне значення отриманих результатів. Для приладобудування полягає у вирішенні комплексу завдань, пов'язаних з розробкою і проектуванням реконфігурованих мереж клітинних автоматів, що реалізуються на сучасних ПЛІС, відмовостійкість яких забезпечується вбудованими засобами сигнатурної справності та відновлення працездатності однорідних мереж з різною розмірністю клітинних функціональних модулів.

Результати дисертаційної роботи використані під час модернізації багатопроцесорних комп'ютеризованих систем управління (БКСУ) установкою «РОСТ-4» дослідно-промислового виробництва Інституту Сцинтиляційних матеріалів НАН України (м. Харків), новизна яких підтверджена Патентом України UA89312 від 11.01.2010 р. (Бюл. №1, 2010 р.). Управління реалізацією вбудованої системи сигнатурного моніторингу виконана на основі розроблених методів проектування легкотестованих однорідних мереж з виключенням трудомістких операцій синтезу тестів і моделювання виявлених несправностей. Використання розроблених методів синтезу реконфігурованих обчислювальних мереж дозволило підвищити достовірність процедур тестового діагностування БКСУ, скоротити час профілактичного обслуговування системи, підвищити відмовостійкість системи шляхом онлайнової реконфігурації структури та заміни несправних процесорних модулів.

Результати дисертаційної роботи використовуються в навчальному процесі на кафедрі автоматики і управління в технічних системах НТУ «ХПІ» при викладанні дисциплін «Теорія цифрових автоматів» та «Арифметико-логічні основи цифрових систем управління».

Особистий внесок здобувача. Основні результати, що виносяться на захист дисертаційної роботи, отримані здобувачем самостійно. Серед них: методи синтезу перевірних тестів для мереж клітинних автоматів, засновані на використанні автоматних моделей КА і функціональних моделей несправностей; методи синтезу перевірних тестів для одновимірних МКА з використанням відмінних і характеристичних послідовностей; процедури перетворення автоматних моделей осередків МКА в легкотестовану мережу; методи модифікації автоматних моделей МКА, що забезпечують скорочення апаратних витрат на реалізацію модулів вбудованих засобів сигнатурного моніторингу і незалежність довжини перевірних послідовностей від розмірності мережі; процедури розміщення в мережі резервних модулів, що забезпечує мінімальність часових витрат на реконфігурацію системи та відновлення працездатності.

Апробація результатів. Основні наукові положення і результати роботи доповідалися й обговорювалися на: XVI, XVII, XVIII Міжнародних науково-практичних конференціях «Інформаційні технології: наука, техніка, технологія, освіта, здоров'я» (Харків, 2008, 2009, 2010), Міжнародному молодіжному форумі «Радиоэлектроника и молодежь в XXI веке» (Харків, 2008), XXI і XXII - Міжнародна науково-практична конференція «Перспективные компьютерные, управляющие и телекоммуникационные системы для железнодорожного транспорта Украины» (Алушта, 2008, 2009), Другій міжнародній науково-практичній конференції «Методи та засоби кодування» (Вінниця, 2009, 2010); на науково-технічних семінарах кафедри автоматики і управління в технічних системах НТУ «ХПІ».

Публікації. Результати наукових досліджень відображені в 14 друкованих працях, з них 11 у фахових наукових виданнях ВАК України, 1 патент України.

Структура дисертації. Дисертаційна робота складається зі вступу, п'яти розділів, висновків, додатків, списку літератури. Загальний обсяг дисертації становить 200 сторінок; з них 44 рисунків по тексту; 7 рисунків на 5 окремих сторінках; 19 таблиць по тексту; 11 додатків на 26 сторінках; списку використаних літературних джерел з 101 найменувань на 10 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність та доцільність дисертації, сформульовано її мету і задачі дослідження, визначено об'єкт, предмет і методи дослідження, наукову новизну і практичну корисність отриманих результатів.

У першому розділі розглядаються особливості структурної організації та тенденції розвитку реконфігурованих ОКМ у світлі сучасних інтегральних КМОП нанотехнологій і появі на ринку НВІС високопродуктивних ПЛІС типу FPGA (Xilinx Virtex 5, Xilinx Virtex II Pro тощо). Зазначається, що просторова розподіленість конфігурованих логічних блоків (КЛБ) FPGA, паралелізм їх функціонування та можливість програмної реконфігурації з'єднань і налаштувань КЛБ дозволяють вирішувати задачі оптимального розміщення обчислювальних алгоритмів обробки інформації та реконфігурації структури ОКМ з метою заміни несправних ФМ і відновлення працездатності мережі за допомогою вбудованої діагностичної інфраструктури сигнатурного моніторингу.

Розвиток математичної теорії однорідних структур, концептуальних і методологічних основ їх використання в обчислювальній техніці, математичному моделюванні складних динамічних систем і процесів на основі ОКМ, з одного боку, і можливість реалізації високопродуктивних структур ОКМ на основі сучасних мікропроцесорних компонентів з, іншого боку, визначають перспективи побудови машин і МКА.

МКА являє собою впорядкований масив однорідних КА з обмеженою кількістю станів (від 2 до 32), наборів правил і функцій КА і характеризується трьома основними параметрами: геометрією зв'язків сусідніх КА, кількістю станів КА і алгоритмом обчислення наступних станів. Аналізується ефективність використання двовимірних МКА для розв'язання задач розпізнавання образів, моделювання гідродинамічних процесів, рівнянь теплопровідності та інших фізичних явищ.

Внаслідок аналізу структурної організації, методів тестового діагностування однорідних мереж і проектування їх компонентів з вбудованими засобами сигнатурного моніторингу та відновлення працездатності шляхом реконфігурації ОКМ сформульовано задачі досліджень та напрямки їх вирішення.

Другий розділ присвячений розробці методів синтезу перевірних тестів для однорідних МКА. З метою поліпшення показників спостереження та управлiння в процесі діагностичного експерименту (ДЕ) запропоновані: 1) процедура модифікації структури КА шляхом введення додаткових входів і виходів (,) (рис.1), 2) ДЕ виконувати в два етапи відповідно з двома напрямками розповсюдження сигналів. Ці умови легко виконуються шляхом відповідної конфігурації КЛБ ПЛІС. У розділі наведені методи синтезу перевірних тестів для варіанта модифікації структури МКА без спостережуваних виходів .

Рис.1 Структура модифікованої МКА

Розроблено метод синтезу перевірних послідовностей для МКА, заснований на побудові тестового графа (ТГ) пар станів за таблицею переходів-виходів (ТПВ) автоматної моделі КА і знаходженні багатьох фундаментальних циклів у ТГ. Процедура синтезу тестів з ТГ автоматної моделі осередку демонструється на прикладі одновимірної КА. Зазначаються особливості цієї процедури, пов'язані з необхідністю виключення надлишкових тестів, безліччю невизначених переходів, поява яких обумовлена наявністю пар сумісних станів і необхідністю розширення безлічі тестів для виявлення класу - одиночних функціональних несправностей автоматної діаграми КА.

Проведено оцінку трудомісткості процедури синтезу, яка становить . Недоліки процедури синтезу тестів з ТГ осередку мережі можна виключити, якщо під час побудови ДЕ використовувати відмінні та характеристичні символи КА і формувати на їх основі циклічні відмітні і характеристичні послідовності.

Визначення 1. Нехай осередок одновимірної МКА без спостережуваних виходів поданий моделлю автомата Мура , в якому - наступником стану є стан не обов'язково за винятком . Вхідний символ є відмітним символом стану тоді і тільки тоді, якщо не є - наступником для безлічі початкових станів автомата і , де - безліч сумісних станів.

Визначення 2. Нехай осередок МКА поданий моделлю автомата Мура . Безліч вхідних символів називається безліччю вхідних характеристичних символів тоді і тільки тоді, коли для будь-якої пари станів автомата .

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

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

Визначення 3. Циклічна перевідна послідовність, утворена з вхідних відмінних символів попередніх станів КА, називається циклічною відмінною послідовністю (ЦВП).

Показано, що для МКА без спостережуваних виходів , в якій КА з станами має для кожного стану щонайменше один відмінний символ, існує одна циклічна відмінна послідовність (ЦВП).

Визначення 4. МКА називається легкотестованою, якщо для ідентифікації кожного стану , осередку , , достатньо прикласти до МКА один перевірний набір , який відрізняє стан від безлічі за станом спостережуваних виходів мережі.

Для МКА, з ЦВП, розроблена процедура побудови повного перевірного експерименту. Проведено оцінку трудомісткості процедури синтезу перевірних послідовностей, які мають відмінні символи для кожного стану КА. В загальному випадку трудомісткості становить , що в разів менше процедури синтезу тестів на основі використання тестових графів. З метою зниження трудомісткості побудови ДЕ, запропоновано модифіковані ТПВ КА шляхом додаткового вхідного символу і функції переходів

,, (табл. 1).

Таблиця 1

Модифікована ТП КА

			…
			…
			…
…			…		…
			…

Припущена модифікація призводить до додавання для кожного виходу КА мультиплексорів 1 з 2, які управляються вхідним символом . Оскільки є відмітним символом для всіх станів КА, то виключається необхідність побудови характеристичного дерева наступників для знаходження відмінних символів. Перевірка справності всіх () переходів КА алгоритмічно просто виконується тестом типу «біжний символ », що забезпечує простоту реалізації вбудованого генератора тестів СКА на одному зсувному регістрі.

Запропоновано альтернативний підхід побудови діагностичного експерименту в МКА без спостережуваних виходів з використанням характеристичних символів характеристичних шляхів у КА і синхронізуючих послідовностей КА.

Визначення 5. Шлях у синхронізуючому дереві КА, що починається з характеристичного символу і не містить синхронізуючої послідовності, називається характеристичним шляхом.

Обгрунтовано необхідні та достатні умови перевірки справності кожного переходу автоматної діаграми осередку МКА перевірною послідовністю, в якій кожна субпослідовність є характеристичним шляхом.

Розроблено процедуру синтезу повних перевірних послідовностей, що виявляють несправності класу , у МКА не мають відмітних символів на основі побудови характеристичного і синхронізуючого дерев-наступників, визначення з синхронізуючого дерева безлічі характеристичних шляхів, які починаються з кожного характеристичного символу.

Третій розділ присвячений розробці методів синтезу МКА з спостерігаються виходами , які перевіряються тестами циклічними постійної довжини, незалежно від розрядності МКА. Розроблено процедуру побудови повного ДЕ для такого типу МКА за умови, що автоматна модель КА є сильнозв^,язним автоматом і має відмінну послідовність.

Нехай МКА (рис.1) складається з комірок, , ..., входи яких живляться змінними ,,,..... Двійковий вектор , у якому , , ... , де - двійковий вхідний набір. Запропоновано перевірку правильності переходу в ТПВ КА виконувати шляхом прикладання ЦВП у вигляді

, (1)

де - відмінна і переводить послідовність; * - знак ітерації.

Визначено нижні й верхні межі довжини повного перевірного тесту, які визначається нерівністю

(2)

З (2) випливає, що довжина тестової послідовності не залежить від розмірності МКА (кількості осередків мережі) і є С-тестованою.

Розроблено процедуру синтезу перевірних послідовностей для МКА, що мають ЦВП. Зазначено, що циклічний зсув ЦВП, формованих для кожного стану КА , , виявляє клас несправностей і алгоритмічно просто реалізується на зсувних регістрах з циклічним зворотним зв'язком.

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

Визначення 6. Нехай - перехід зі стану в , визначається TПB осередки мережі. Безліччю циклічних характеристичних послідовностей (ЦХП) називатимемо безліч циклічних вхідних наборів виду

, (3)

де - безліч характеристичних символів ТПВ осередку; - мінімальна перевідна послідовність така, що , .

Показано, що, якщо число ЦХП дорівнює , то () циклічних зрушень ЦХП дозволяють активізувати перевірні переходи ТПВ КА , , , і транспортувати стан на спостережувані виходи .

Визначено та обгрунтовано верхню межу довжини повного ДЕ, яка також визначається нерівністю (2). Розроблена процедура синтезу перевірних послідовностей для СКА, що не мають відмінних символів.

Аналіз процедур синтезу перевірних тестів для МКА з виходами , показує, що трудомісткість цих процедур пов'язана з необхідністю побудови відмінних і характеристичних дерев-наступників станів автоматних моделей КА і знаходження відмінних і характеристичних символів. Трудомісткість цих операцій становить ~ . З метою виключення цих операції запропонований метод модифікації ТПВ КА шляхом кодування станів автомата зсувно-реєстровою послідовністю. Якщо станів автомата кодується безліччю станів підграфа «» розрядного зсувного регістра, в якому двійкова послідовність породжує гамільтонів цикл, то введення додаткового стовпця (табл. 2) в ТПВ КА з зсувно-реєстрової функцією переходів і функцією виходів дозволяє отримати в модифікованому КА відмінну послідовність мінімальної довжини .

Запропонований метод модифікації ТПВ КА виключає необхідність виконання процедури знаходження відмінною послідовності, а найбільштрудомістку частину ДЕ - фазу перевірки правильності переходів у кожному КА мережі здійснити тестом «біжучий », на фоні символу , який алгоритмічно просто реалізується на зсувному регістрі з циклічним зворотним зв'язком.

Таблиця 2

Модифікована ТПВ КА

	,
		,
		,
		,
		,

Розроблений метод синтезу легкотестованих МКА застосований під час розробки схеми конвеєрного помножувача із вбудованими засобами тестового діагностування. Знайдено також багато з 8-ми тестових наборів, які забезпечують властивість С-тестованості схеми помножувача і практично 100% покриття функціональних і константних несправностей, що підтверджується результатами моделювання і комп'ютерного експерименту схеми помножувача.

Четвертий розділ присвячений синтезу реконфігурованих ОКМ із ФМ, розмірність яких може змінюватися в широких межах залежно від оброблюваних інформаційних потоків і класу вирішуваних завдань. Якщо ФМ може бути описаний автоматною моделлю, то правила настроювання КА можна обчислити аналітично на основі використання декомпозиційних методів синтезу цифрових пристроїв. Автомат допускає декомпозицію на складові підавтомати на основі використання замкнутої решітки розбиття станів його моделі. Розроблена і подана алгоритмічна процедура знаходження замкнутих розбиттів складного ФМ. Це дозволяє здійснити реалізацію ФМ у вигляді односпрямованої мережі КЛБ FPGA або на основі БМК з мінімальними апаратними витратами.

Розроблені та наведені методи і процедури синтезу одновимірних ОКМ з резервними модулями ФМ із централізованим і розподіленим управлінням реконфігураціею.

При централізованому управлінні реконфігураціею ОКМ взаємозв'язок між HOST комп'ютером і ФМ мережі здійснюється через загальну інтерфейсну шину, а з'єднання між ФМ виконує комутаційна мережа. У цьому підході управління реконфігураціею здійснює HOST комп'ютер з урахуванням кількості резервних модулів, обсягу даних, що пересилаються, складності алгоритму реконфігурації і комутаційної системи.

В іншому підході використовуються шунтуючі комутаційні мережі, в яких реконфігурація здійснюється комутаційними осередками з двома типами з'єднань, що мають по два входи й виходи.

Пересилання великого обсягу даних у разі виявлення несправного ФМ визначає необхідність вирішення задачі оптимального розміщення модулів у структурі ОКМ, що дозволить скоротити кількість пересилань і час реконфігурації. Нехай у ОКМ, що має ФМ і s резервних, які знаходяться в позиціях .

Використання методу дихотомії та ітеративного розбиття вихідної множини функціонуючих і резервних модулів на рівні частини дозволяє отримати функцію середнього числа пересилань даних та ітеративну процедуру обчислення номера розміщення резервних елементів мережі з системи лінійних рівнянь:

(4)

З (4) для обчислення значення - номера розміщення -го резервного модуля отримуємо загальне рівняння у вигляді

. (5)

На основі отриманих результатів розроблена і наведена процедура реконфігурації ОКМ, в якій використовується два характеристичних вектори: вектор станів ФМ та вектор станів комутаційної осередку.

У ОКМ з розподіленим управлінням реконфігураціею шунтуючі комутаційні модулі замінюються системою внутрішньої комутації вхід-вихідних шин, вбудованої в кожен ФМ ОКС (рис. 2). Такий ФМ має чотири маршрути передачі даних, які позначаються: HH, HV, VH, і VV.

Розглянуті та наведені одновимірні і двовимірні структури реконфігурованих ОКМ із вбудованими модулями комутації.

Показано, що для двовимірних ОКМ з прямокутною структурою розмірністю число ФМ, що знаходяться у стані і дорівнює числу ФМ із станом , тобто , а також . Визначено та обгрунтовано нижні й верхні межі станів ФМ маршрутів комутацій у вигляді:

 (6)

Розроблено процедуру реконфігурації двовимірної ОКМ заданої конфігурації. Вхідним параметром, що ініціює початок виконання алгоритму ре конфігурації, є номер несправного ФМ. Здійснюється пошук усіх маршрутів обробки даних, що відповідають кількості справних ФМ і вибирається маршрут, відповідний найменшій кількості пересилань даних. Під час перевірки коректності встановленої конфігурації ОКМ використовуються співвідношення та нерівності (6).

П'ятий розділ присвячений розробці структурно-логічної архітектури легкотестованих ОКМ і модулів вбудованих засобів сигнатурного моніторингу. Запропоновані вище методи модифікації автоматних моделей КА, що поліпшують характеристики керованості і спостережливості модулів ОКМ, дозволяють забезпечити алгоритмічну й апаратну реалізацію вбудованих засобів діагностування ОКМ (рис. 3)

Рис.3 Структурно-логічна архітектура ОКМ із вбудованими засобами діагностування

Перевірка справності зводиться до генерації послідовності станів за допомогою модулів ГС, ГВС, генерації тестових послідовностей на верхніх входах осередків мережі на - розрядному ЗР, у вигляді біжучих символів на фоні відмінних або характеристичних послідовностей і порівняння на кожному такті на бічному спостерігаємому виході станів з вектором правильних станів, які формує ГВС. Запропоновано дві конфігурації КЛБ FPGA з двома правилами налаштування, які ідентифікують справність мережі з «» КА за допомогою восьми ЦВП.

Розглянуто методи побудови ДЕ в ОКМ з процесорних ФМ. Для перевірки справності таких ФМ у процесі функціонування широко використовуються охоронні або діагностичні процесори (ДП), «watchdog» таймери.

Аналіз структури ДП і структурно-логічних схем ОКМ з різною розмірністю ФМ і КА визначають клас модулів сигнатурного моніторингу. До складу вбудованих засобів діагностичної інфраструктури ОКМ входять: лічильникові і рейстрові структури з лінійними і нелінійними зворотними зв'язками, схеми порівняння, синдромно-сигнатурні аналізатори, які легкотестовані і витрати на їх використання, не повинно перевищувати 10 ч 15% вартості функціональної частини НВІС.

Тому в розділі запропоновані й розроблені методи синтезу легкотестованих модулів лічильників і таймерів ДІ ОКМ, що реалізуються на ЗР з нелінійними зворотними зв'язками, оскільки це забезпечує мінімальність відмінних послідовностей модулів, а виключення традиційних методів рахунку в лексикографічній послідовності двійкових чисел не ускладнює процедур ДЕ. Запропоновано реалізацію лічильникових структур, засновани на формуванні в ланцюзі зворотного зв'язку ЗР послідовності, що породжує гамільтонів цикл у графі переходів ЗР на основі використання алгебри р - розбиттів біектівних двоблокових відображень множин станів лічильника. Наведені переваги реалізації лічильникових структур порівняно з традиційними методами проектування.

Запропонована й обгрунтована реалізація синдромно-сигнатурних аналізаторів (ССА) двійкових послідовностей на основі використання розроблених методів синтезу лічильникових структур. Для підрахунку кількості одиниць в ССА використовуються декади послідовно-з'єднаних двійково-десяткових лічильників (ДСч), реалізованих на ЗРНЗЗ (рис. 4).

Розроблено структуру універсального ССА з використанням декад ДСч, яка характеризується простою системою реконфігурації для здійснення синдромного або сигнатурного аналізу, мінімальною довжиною відмінної послідовності,що спрощує процедуру перевірки справності самого ССА. Використання методу синдромно-сигнатурного тестування та універсальних ССА у складі діагностувальної інфраструктури (ДІ) мікроконтролерних систем управління (МКСУ) ростовими установками дозволило підвищити достовірність процедур функціонального і тестового діагностування модулів МКСУ, зберегти час профілактичних робіт і в цілому підвищити ефективність вбудованих засобів ДІ. Новизна та оригінальність запропонованих рішень підтверджена Патентом України на винахід.

а)

б)

Рис. 4. Функціональна схема ССА на ЗРНЗЗ: а) функціональна схема; б) умовне позначення ДСч з

ВИСНОВКИ

Дисертаційна робота присвячена вирішенню науково-прикладної задачі розробки та вдосконалення моделей і процедур синтезу реконфігурованих ОКМ із вбудованими засобами тестового та функціонального діагностування.

Основні наукові та практичні результати полягають у наступному:

1. Проведено аналіз структур і тенденцій розвитку ОКМ, методів і процедур проектування відмовостійких ОКМ із реконфігурованими структурами, методів проектування компонентів МВС з вбудованими інфраструктурами сигнатурного моніторингу та процедурами їх тестового та функціонального діагностування.

2. Розроблено процедури синтезу перевірних тестів для МКА з обмеженою спостережуваністю вихідних реакцій, засновані на використанні тестового графа клітинного автомата і знаходженні багатьох фундаментальних циклів. Отримано оцінки трудомісткості розроблених процедур синтезу тестів.

3. Запропоновано метод і процедуру модифікації автоматної моделі клітинного автомата з метою поліпшення показників керованості МКА в процесі діагностичного експерименту. Визначено клас легкотестованих МКА, що мають відмінні та характеристичні символи для кожного стану КА, визначені необхідні й достатні умови існування в КА циклічних відмітних і характеристичних послідовностей, що дозволяє у разів (де - число станів КА) скоротити довжину перевірної послідовності порівняно з канонічним методом синтезу тестів з автоматних моделей КА і виключити необхідність аналізу повноти тестових послідовностей.

4. Запропонована і розроблена процедура синтезу перевірних тестів для МКА з виходами КА мережі, що спостерігаються. Показано, що МКА з осередками, автоматні моделі яких є сильнозв^,язними автоматами і мають відмінні послідовності, є С-тестованими з довжиною тестової послідовності, що не залежить від розмірності мережі.

Визначено клас ЦХП і процедуру побудови перевірного експерименту на основі використання ЦХП, отримана верхня межа довжини цих послідовностей, довжина яких в ~ (де - число станів осередку МКА) менше довжини послідовностей, синтезованих канонічним методом.

5. Запропоновано метод модифікації автоматної діаграми КА з виходами, що спостерігаються, що передбачає введення додаткового вхідного символу і кодів станів, які породжують гамільтонів цикл у послідовності переходів станів, що забезпечує властивість С-тестованості МКА та регулярність генерації перевірних тестів у вигляді тестової послідовності з «біжучим» вхідним символом, , де - число вхідних символів КА. Отримано оцінку довжини перевірного експерименту, яка ~ 2 рази скорочується порівняно з відомими методами побудови ДЕ в таких МКА.

6. Розроблено методи і процедури синтезу ОКМ з резервними ФМ із централізованим і розподіленим управлінням реконфігураціею. Розв'язано задачу оптимального розміщення резервних модулів у структурі ОКМ на основі критерію мінімальності кількості пересилань даних між ФМ, що забезпечує мінімальність часових витрат на відновлення працездатності ОКМ без деградації продуктивності.

7. Розроблено й обгрунтовано структурно-логічну архітектуру ОКМ із вбудованою діагностичною інфраструктурою сигнатурного моніторингу, в основі якої використовувалися розроблені методи перетворення осередків ОКМ в легкотестовані, що дозволило спростити процедури синтезу перевірних тестів, генераторів тестових послідовностей і синдромно-сигнатурних аналізаторів вихідних реакцій.

8. Використання та впровадження результатів досліджень дисертаційної роботи при модернізації системи технічного діагностування МКСУ установками «РОСТ» на дослідному виробництві з вирощування великогабаритних монокристалів у ICMA НАН України (м. Харків), дозволило підвищити достовірність процедур діагностування, скоротити час і витрати на профілактичні роботи і, в цілому, підвищити якість продукції, що випускається. Результати дисертаційної роботи впроваджені в навчальний процес кафедри автоматики і управління в технічних системах НТУ «ХПІ».

СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Королева Я.Ю Синтез дискретных устройств методом последовательной декомпозиции автоматных моделей / Л.В. Дербунович, М.А. Бережная, Я.Ю. Королева, М.Г. Рыжикова // Вісник НТУ „ХПІ”. - Харків: НТУ „ХПІ”. - 2007. - № 36. - С. 16-25.

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

2. Королева Я.Ю Тестовое диагностирование одномерных однородных структур / Л.В. Дербунович, М.А. Бережная, Я.Ю. Королева, М.Г. Рыжикова // Вісник НТУ „ХПІ”. - Харків: НТУ „ХПІ”.- 2008. - № 31. - С. 49-57.

Здобувачем розроблено процедуру синтезу перевірних тестів для виявлення функціональних несправностей на основі використання багатьох фундаментальних циклів у графі автомата.

3. Королева Я.Ю Синтез проверяющих тестов для однородных структур на основе циклических отличительных последовательностей / Л.В. Дербунович, М.А.Бережная, Я.Ю. Королева, М.Г. Рыжикова // Інформаційно-керуючі системи на залізничному транспорті. - Харків. - 2008. - № 4(72). - С. 29-33.

Здобувачем обґрунтовано необхідні та достатні умови формування перевірних послідовностей з відмінних і характеристичних символів КА.

4. Королева Я.Ю Однородные вычислительные сети с реконфигурируемой структурой / Я.Ю. Королева, М.А. Бережная // Технология приборостроения. - Харьков. - 2008. - №1. - С. 44-48.

Здобувачем запропонована структура реконфігурованої ОКМ на основі шунтової комутаційної мережі з централізованим управлінням реконфігурації.

5. Королева Я.Ю Синтез проверяющих тестов для сетей клеточных автоматов с наблюдаемыми выходами / Я.Ю. Королева, М.А. Бережная, Замирец О.Н. Лебедь В.А. // Технология приборостроения. - Харьков. - 2008. - №2. - С. 20-25.

Здобувачем запропоновано метод модифікації структури КА з КЛБ ПЛІС FPGA, що забезпечує умови керованості та спостережливості в процесі діагностичного експерименту.

6. Королева Я.Ю Характеристические последовательности в конечно-автоматных моделях дискретных устройств / Я.Ю. Королева, М.А. Бережная // Вісник НТУ „ХПІ”. - Харків: НТУ „ХПІ”. - 2008. - № 56. - С. 19-25.

Здобувачем запропоновано метод синтезу перевірних послідовностей на основі використання характеристичних шляхів у синхронізованому дереві-наступників.

7. Королева Я.Ю Синтез тестов для сетей клеточных автоматов на основе характеристических последовательностей / Я.Ю. Королева, М.Г. Рыжикова // Вісник НТУ „ХПІ”. - Харків: НТУ „ХПІ”. - 2008. - №57. - С. 112-123.

Здобувачем запропонована і розроблена процедура побудови характеристичного дерева-наступників, що дозволяє визначити мінімальну безліч характеристичних символів для синтезу повної перевірної послідовності.

8. Королева Я.Ю Синтез проверяющих тестов для сетей клеточных автоматов/ Л.В. Дербунович, М.А. Бережная, Я.Ю. Королева, М.Г. Рыжикова // Інформаційно-керуючі системи на залізничному транспорті. - Харків. - 2008. - № 5-6. - С. 57-65.

Здобувачем запропонована і розроблена процедура синтезу перевірних тестів для МКА без спостережуваних виходів КА на основі використання ЦВП з характеристичних символів.

9. Королева Я.Ю Диагностические эксперименты в системах защиты информации на сетях клеточных автоматов/ М.А. Бережная, Я.Ю. Королева, И.В. Гормакова // Інформаційно-керуючі системи на залізничному транспорті. - Харків. - 2009. - №4. - С. 142-145.

Здобувачем запропонована процедура модифікації комірки МКА, що спрощує побудову двох фаз ДЕ на основі використання циклічних відмінних і характеристичних символів.

10. Королева Я.Ю Синтез проверяющих тестов для однородных схем / Я.Ю. Королева, М.А. Бережная, Г.Г. Четвериков // Біоніка Інтелекту. - Харків. - 2009. - № 2(71). - С. 123-127.

Здобувачем запропоновані необхідні і достатні умови існування в МКА ЦВП та запропоновано спосіб їх знаходження.

11. Королева Я.Ю Однородные сети с распределенной системой реконфигураций / Я.Ю. Королева, М.А. Бережная, Л.В. Дербунович // Вісник НТУ „ХПІ”. - Харків: НТУ „ХПІ”. - 2010. - №20. - С. 71-78.

Здобувачем запропонована процедура реконфігурації двовимірних ОМ з ФМ із вбудованими чотирипортовими комутаційними модулями.

12. Королева Я.Ю Пат. 89312 МПК⁸ G06 F 11/28, С30 В 15/20. Пристрій для діагностування пристрою регулювання росту монокристалів /
Я.Ю. Корольова, М.А. Бережна Л.В. Дербунович, В.С. Суздаль; заявник і патентовласник Інститут Сцинтиляційних Матеріалів НАН України - №200808602; заявл. 01.07.08, опубл. 11.01.2010, Бюл. №1.

Здобувачем запропонована структура - розрядного синдромного аналізатора на декадах двійково-десяткових лічильників.

13. Королева Я.Ю Применение сетей клеточных автоматов в криптографических системах / М.А. Бережная, Я.Ю. Королева, И.В. Гормакова // Тези доповідей другої міжнародної науково-практичної конференції «Методи та засоби кодування» 22-24 квітня Вінниця. - 2009. - С.94-95.

Здобувачем запропоновані структурно-логічні схеми легкотестованих МКА, які використовуються для реалізації блокового і потокового шифрування в криптосистемах.

14. Королева Я.Ю Диагностическая инфраструктура с интеллектуальными свойствами в реконфигурируемых мультипроцессорных системах /
Я.Ю. Королева, М.А. Бережная, Л.В. Дербунович // Тези доповідей міжнародної науково-практичної конференції «Інформаційні технології та комп'ютерна інженерія» 19-21 травня Вінниця. - 2010. - С. 344-345.

Здобувачем запропонована структура вбудованих засобів сигнатурного моніторингу, заснована на процедурі диспетчеризації процедур тестового та функціонального діагностування.

АНОТАЦІЇ

Королева Я.Ю. Синтез реконфигурированих однорідних клітинних мереж із вбудованими засобами тестового діагностування, що реконфігуруються. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - комп'ютерні системи та компоненти. - Національний технічний університет «Харківський політехнічний інститут», Харків 2010.

Дисертація присвячена дослідженню і вдосконаленню моделей, методів і процедур синтезу реконфігурованих ОКМ, перевірних тестів, вбудованих засобів сигнатурного моніторингу та відновлення працездатності. На основі аналізу структур і тенденцій розвитку ОКМ у світлі сучасних наноелектронних КМОП технологій виробництва ПЛІС, обгрунтована необхідність використання вбудованих на кристал або друковану плату діагностичної інфраструктури, що забезпечує виявлення на робочій частоті розширеного класу дефектів, алгоритмічну й апаратну простоту реалізації вбудованих засобів.

Запропоновано метод і процедуру модифікації автоматної моделі КА з метою покращення показників спостереження та управлiння МКА в процесі ДЕ. Визначено клас легкотестованих МКА, що мають відмінні та характеристичні символи, циклічні відмітні і характеристичні послідовності, необхідні і достатні умови існування цих послідовностей. Розроблено процедури синтезу тестів для МКА на основі використання ТГ КА та проведено порівняльний аналіз цієї процедури з методом генерації тестів, заснованих на використанні ЦВП. Отримано оцінки трудомісткості генерації перевірних тестів, які показують, що останній підхід дозволяє в разів виключити трудомістку процедуру моделювання несправностей.

Для МКА з виходами, що спостерігаються, реалізованих на ПЛІС типу FPGA, визначені умови С-тестованості та запропоновано метод модифікації структури КА, що забезпечує регулярність генерації перевірних тестів у вигляді послідовності з «біжучим» вхідним символом і довжиною ДЕ в ~ 2 рази меншою порівняно з відомими методами.

Розроблено методи і процедури синтезу ОКМ з резервними ФМ із централізованим і розподіленим управлінням реконфігурацією. Розроблена та обгрунтована архітектура ОКМ із ДІ сигнатурного моніторингу.

Використання запропонованих рішень дослідної експлуатації при модернізації ДІ МКСУ установками «РОСТ» дозволило підвищити достовірність ДЕ, скоротити час і затрати на профілактичні роботи.

Ключові слова: методи котролю, методи діагностування комп'ютерних мереж, однорідні клітинні мережі, мережі клітинних автоматів, тестовий граф, автоматна модель, багатопроцесорні комп'ютеризовані системи управління, синдромно-сигнатурний аналізатор, діагностична інфраструктура, відмінні та характеристичні послідовності.

Королева Я.Ю. Синтез реконфигурированных однородных клеточных сетей со встроенными средствами тестового диагностирования. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. - Национальный технический университет «Харьковский политехнический институт », Харьков. 2010.

Диссертация посвящена исследованию и совершенствованию моделей, методов и процедур синтеза реконфигурируемых ОКС, проверяющих тестов, встроенных средств сигнатурного мониторинга и восстановления работоспособности. На основе анализа структур и тенденций развития ОКС в свете современных наноэлектронных КМОП технологий производства ПЛИС, микроконтроллеров и других компонентов, обоснована необходимость использования встроенных на кристалл или печатную плату диагностической инфраструктуры, обеспечивающей обнаружение на рабочей частоте расширенного класса дефектов, алгоритмическую и аппаратную простоту реализации встроенных средств.

Предложен метод и процедура модификации автоматной модели КА с целью улучшения показателей управляемости и наблюдаемости СКА в процессе ДЭ. Определен класс легкотестируемых СКА, имеющих отличные и характеристические символы, циклические отличительные и характерные последовательности, необходимые и достаточные условия существования этих последовательностей.

Разработаны процедуры синтеза тестов для СКА на основе использования ТГ КА и нахождении множества фундаментальных циклов. Проведен сравнительный анализ данной процедуры с методом генерации тестов, основанных на использовании ЦОП.

Получены оценки трудоемкости генерации проверяющих тестов, которые показывают, что последний подход позволяет в раз (где - количество состояний автомата) исключить трудоемкую процедуру моделирования неисправностей.

Для СКА с наблюдаемыми выходами, реализуемых на ПЛИС типа FPGA, определены условия С-тестируемости и предложен метод модификации структуры КА, обеспечивающий регулярность генерации проверочных тестов в виде последовательности с «бегущим» входным символом и длиной ДЭ в ~ 2 раза меньше по сравнению с известными методами.

Разработаны методы и процедуры синтеза ОКС с резервными ФМ с централизованным и распределенным управлением реконфигурацией на основе критерия минимальности числа пересылок данных и временных затрат на реконфигурацию. Разработана и обоснована архитектура ОКС с ДИ сигнатурного мониторинга, в которой используются легкотестируемые генераторы тестовых последовательностей и синдромно-сигнатурных анализаторов.

Разработана и обоснована структурно-логическая архитектура ОКС с встроенной диагностической инфраструктурой сигнатурного мониторинга, в основе которой использовались разработанные методы преобразования ячеек

Размещено на Allbest.ru

...