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

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

Контроль ОП для зведення в ступінь. Метод контролю ґрунтується на аналізі заборонених значень залишку за модулем результату операції.

Твердження 4.3. Для цілих g виконується (M - A) g mod M = (-1) g A g mod M.

З твердження випливає наявність ПІН для парних g, тому що не менш M / 2 значень залишків A mod M є забороненими, і для непарних g та M = 2 g 1, оскільки в діапазоні A = 0 M знаходиться не менш двох залишків 1.

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

Використання всієї множини заборонених значень результату забезпечує максимальну ймовірність виявлення помилок з пороговим підходом до ФД. Аналіз підмножини заборонених значень з мінімальною ймовірністю виявлення найбільш ймовірних помилок виконується за ймовірнісним підходом.

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

Ймовірність PоБН оцінюється по частоті переходу з дозволеного значення x у заборонене z під дією помилки y = 2 r з умови (x + y) mod M = z mod M.

Наприклад, для однотактних ОП для зведення в квадрат і куб вибір M = 7 і M = 15 визначає ймовірності PоБН = 0,33 0,67 і PоБН = 0,15 0,75, відповідно. При мінімальних значеннях PоБН ймовірність PОТБ знижується до значень 0,15 і 0,3, а показник недостовірності контролю результатів - у 2,3 і 3,7 разів.

У порівнянні з контролем за модулем заощаджується 1 / (g + 1)-а частина устаткування на згортку операнда, що для ОП зведення в квадрат і куб спрощує ЗК на 33% і 25%, відповідно.

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

Метод виконує ідентифікацію дозволених вхідних слів, контроль спрощеної операції з урахуванням ПІН і визначення коду контролю по результату спрощеної операції на дозволених вхідних словах.

Контроль помножувача чисел. Метод визначає дозволені вхідні слова при рівних за модулем три операндах A і B. Для вихідних слів код 102 є забороненим значенням залишку за модулем три результату спрощеної операції піднесення у квадрат.

Дозволені вхідні слова ідентифікуються на u перших розрядах операндів вхідного слова за умовою

A{1 u} = B{u 1},

де u - парне число, u n, і на u + 1 n розрядах співмножників за умовою

A{u + 1 n} mod 3 = B{u + 1 n} mod 3

По цих умовах для значення u* параметра u виконується контроль результату.

Схема ЗК є самоперевіряємою для константних одиночних несправностей.

Ймовірність

PОБН = 2-u-u* / 9

У порівнянні з контролем за модулем ЗК спрощуються в середньому в 1,7 разів, а показник недостовірності контролю результатів зменшується у 7,8 разів.

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

Визначення 4.1. Контрольний код КА числа А з фіксованою точкою дорівнює кількості розрядів значущої частини цього числа:

КА = Int (log 2 А) + 1 для А 0; КА = 0 для А = 0.

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

Теорема 4.1. Контрольні коди g операндів визначають контрольний код результату арифметичної операції з відхиленням на :

– для суми S = виконується KS*1 = KS*2 + ,

де KS*1 =; KS*2 = ; g1 + g2 = g + 1; 1 g1 g2 g;

KBj і KGl - контрольні коди чисел Bj і Gl;

= -]log2 g1[ ]log2 g2[;

Bj - числа S 0 і Ai 0 чи S 0 і Ai 0, якщо їхня кількість g1 g / 2, і інші числа Ai 0 для S 0 і Ai 0 для S 0 у противному випадку;

Gl - числа S 0 і Ai 0 чи S 0 і Ai 0, якщо їхня кількість g2 g / 2, і інші числа Ai 0 для S 0 і Ai 0 для S 0 у противному випадку;

– для добутку V = , Аi 0, виконується КV = КP* + ,

де КP* = ; = 1 - g 0; - ознака нуля операнда Аj.

– для частки Q = / виконується КQ = КQ* + ,

де КQ* = - ;

= 1 - g1 g2, і - ознаки нуля операндів Аj і Аi.

Додавання даних довільних знаків приводиться до додавання позитивних чисел зміною місць доданка і суми.

Контрольні співвідношення для бінарних операцій множення і ділення мають вид

KV* = KA1+ KA2, = -1, 0; КQ* = KA1 - KB1, = 0, 1.

Схеми ЗК є самоперевіряємими для константних одиночних несправностей.

Ймовірність виявлення помилки в -му розряді результату арифметичної операції

PОБН = KAO 2-(n - )

де KAO = 1, KAO = 0,75, KAO = 0,5, відповідно для операцій додавання множення і ділення з нумерацією розрядів = 1 n, починаючи від першого, молодшого розряду.

У порівнянні з контролем за модулем ЗК, що зосереджені в блоках формування контрольних кодів чисел, спрощуються в 4,7 разів, а показник недостовірності контролю результатів знижується в 8,2 разів.

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

Контроль ОП для піднесення в ступінь і вилучення кореня визначений для мантиси операнда x, 1/2 x < 1.

Для y = x g, g = 2, 3 …, верхня границя

yВ = (2 - 21 - g) x + (21 - g - 1)

описується лінійною функцією, яка проходить через точки функції y: x=2 -1, y=2 -g і x=1, y=1, а нижня границя

yН = (2 - 21 - g) x + (21 - g - 1) - cВН

рівнобіжна лінії yВ і проходить через точку торкання xк =

; yк = ()

g функції y або нижче її з мінімальною різницею

cВН = yВ (xк Н) - y (xк Н),

що може бути подана з розрядністю n.

Для організації почергового порівняння результату з його границями вводиться параметр C, обчислюється поточна границя

yВН = yВ - cВН C

і перевіряється нерівність

y + C 2 - n < yВН,

де C = 0 і C = 1 при порівнянні результату з верхньою і нижньою границями, 2 -n - вага молодшого розряду чисел, що коректує нижню границю при перевірці помилкової умови y < yН.

Код контролю E{1, 2} приймає взаємо-інверсні значення розрядів

E{1} = C; E{2} = (y yВ + C (1/16 + 2-n-1))

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

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

yВ = ky x + 1 - ky + ky cВН, yН = ky x + 1 - ky, де ky = 2 g - 1 / (2 g - 1).

Почергове порівняння результату з його границями виконується по нерівності

(2 g - 1) yНВ + C 2 - n (2 g - 1) yН + ky cВН.

Ймовірність POБН залежить від величини помилки Е. Для ОП піднесення в квадрат і вилучення квадратного кореня

POБН = 1 -, еВ 2 - 4; POБН = 4 , 2 - 4 і POБН = 2 , еВ 2 - 3/3; POБН = 1 - , 2 - 3/3,

де е = еВ для е > 0, е = еН для е < 0.

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

У порівнянні з контролем за модулем ЗК спрощені більш ніж у 1,3 рази, а показник недостовірності контролю результатів - у 10,2 рази.

Контроль додавача. Метод використовує той факт, що доданки Аi, i = 1 g не можуть бути одночасно менше або більше g-ї частини суми

S =

Контрольні нерівності, що виявляють помилки, мають вид S g А1 і S g Аi для i = 2 g. Результати порівняння

E{1} = (S g А1); E{2} = (S g А2); …

E{g} = (S g Аg)

утворюють код порівняння E{1 g}, що ідентифікує помилку, приймаючи в усіх розрядах однакове значення 0 або 1.

Для g = 2 код контролю збігається з кодом порівняння E{1, 2} і приймає значення 012 та 102 при S 2 А1, S 2 А2 та S 2 А1, S 2 А2, що відповідає правильній роботі додавача, і значення 002 та 112, якщо S 2 А1, S 2 А2 та S 2 А1, S 2 А2, тобто при помилковій роботі додавача.

Роздільне обчислення розрядів коду контролю забезпечує самоперевіряємість схеми ЗК. Ймовірність виявлення арифметичної помилки еА оцінюється по формулі

POБН = (2 n - еА ) (2 еА - 1) / 2 2n.

У порівнянні з контролем за модулем показник недостовірності контролю для n = 16 і n = 32 знижується в 9 - 10 разів, а ЗК спрощуються в 5 разів.

Контроль помножувача мантис Аi, 2 -1 Аi < 1, i = 1 g. З метою одержання простих контрольних обчислень верхня і нижня границі результату V визначаються з використанням функцій з лінійною залежністю від мантис Аi.

Верхня границя

VВ = (Аi)

результату V визначається по верхніх границях операндів, а нижня границя - по нижніх границях

VН = А1 + A2 - 1

що отримані за умови (1 - А1) (1 - А2) 0 для окремих пар мантис Аi і далі для нижніх границь у ролі мантис співмножників.

Для g = 2 результат перевіряється його почерговим порівнянням з верхньою і нижньою границями у виді поточної границі

VBH=F(D1 A1+D2 A2), де D1 = C D3, D2 = C D3, D3 = (A < B), F (*)

дробова частина числа, VBH = VB для C = 0 та vBH = VН для C = 1.

Код контролю обчислюється по формулах

E{1} = (V < (VBH + C 2-n)), E{2} = C.

Помилки виявляються з ймовірністю, що збільшується від 0,5 до 1 з ростом величини помилки від 0 до 0,25. Схема ЗК помножувача відноситься, до одновихідних схем, що самоперевіряються з керуючим розрядом C.

У порівнянні з контролем за модулем показник недостовірності контролю результатів знижується в 1,2 разів, а ЗК спрощуються в 1,3 разів.

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

Схема ЗК ОП містить блоки БВО та БВР вибору елементів по входах та виходах, блоки БКЕ контролю елемента, а також блок БУС управління і синхронізації, єдиний для декількох типів елементів або ОП

Контроль додавача. Однотактний додавач з фіксованою точкою складається з однакових елементів - повних двійкових додавачів.

При виборі за елемент одного розряду ОП, перевіряється співвідношення a b = s c, що зв'язує розряди доданків a, b, суми s і перенесення c повного додавача. Елементи вибираються на мультиплексорах з підключенням їх n інформаційних входів до даних n елементів додавача, а блок БКЕ обчислює розряди коду контролю

E{1} = (a b) та E{2} = s c.

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

Твердження 4.4. Нехай для розрядів ai і bi n-розрядних доданків А і В, ,

i = 1 n - 1 виконується ai = bi, тоді si si+1= (ai+1 bi+1), де si і si+1 - i-й і (i+1)-й розряди суми s = А + В.

Твердження 4.5. При введенні додаткової умови ai+1 = bi+1, контрольне співвідношення приймає вид si = si+1.

Схеми ЗК виконують стиск кодів C{1, 2} і Eел1{1, 2} чи C{1, 2}, C1{1, 2} і Eел2{1, 2} на схемах стиску, що самоперевіряються, відповідно при реалізації твердження 4.4 чи 4.5, де

C{1} = ai, C{2} = bi, C1{1} = ai+1, C1{2} = bi+1, Eел1{1} = ai+1 bi+1, Eел1{2} = si si+1, Eел2{1} = si, Eел2{2}= si+1.

Ймовірність виявлення помилки, викликаної збоєм ОП, оцінюється для розглянутих варіантів ЗК як

Pc0 = 1 / n, Pc1 = 1 / (2 (n - 1)) і Pc2 = 1 / (4 ( n - 1)).

Схеми ЗК самоперевіряються для константних одиночних несправностей.

Кількість устаткування на контроль ОП в основному зосереджена у блоці вибору елемента - 4 n-розрядних мультиплексорів у першому рішенні і 6 n/2-розрядних мультиплексоров у двох інших рішеннях, що в 3 і 4 рази простіше, ніж при контролі за модулем.

Показник недостовірності контролю результатів зменшується у 8,2 разів.

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

Для сигнального процесора, розробка якого виконувалася в рамках г/д робіт “Черкал-уво-п”, “Чехонь-уво”, “705-703-2”, “Кора-уво” по постанові Ради Міністрів СРСР та інших директивних органів, була виконана система ФД сигнального процесора із використанням порогового підходу. Арифметичні блоки процесора перевіряються за модулем три з використанням запропонованого методу контролю скорочених операцій для підвищення достовірності контролю результатів. Метод поелементного контролю використаний для налагодження на робочих вхідних послідовностях сигнального процесора (елементами є обчислювачі швидкого перетворення Фурьє), а також блоків цифрових затримок і блоків пам'яті числових даних.

Засоби контролю за модулем одержали суттєве спрощення - зниження витрат устаткування і підвищення швидкодії, а також додаткові можливості для перевірки правильності обробки даних за рахунок використання ПРК.

У блоках обчислення модуля комплексного числа, додавачах з плаваючою точкою, зсувачах і ОП інтегрування ЗК спрощені за рахунок виконання спільних контрольних обчислень для варіантів результату, що заготовлені для прискорення операцій. Використання єдиних інтегральних контрольних кодів за модулем для мантис дійсної і мнимої частин комплексних чисел та їх порядків спростили ЗК у блоках комплексного множення. Контроль порядку проходження числових даних у блоках цифрової затримки виконано перевіркою за модулем чисел та викоистанням ПРК, включаючи часову надмірність. Розроблена система ФД впроваджена у складі сигнального процесора в серійне виробництво на підприємстві п/с Р-6533, що відбито у 23 авторських посвідченнях на використані винаходи.

В рамках д/б роботи кафедри “Комп'ютерні інтелектуальні системи і мережі” ОНПУ № 329-73 “Апаратні засоби автоматизованих систем. Розробка та дослідження методів та засобів автоматизованих систем”, а також договору № 1-ДС/62 “Про співпрацю з розробки обчислювальних пристроїв для цифрової обробки сигналів у системах телекомунікації”, що укладений між ОНПУ й Українським НДІ радіо і телебачення виконане проектування ЗК для помножувачів мантис чисел зі скороченим виконанням операції.

На кафедрі “Комп'ютерні інтелектуальні системи і мережі” ОНПУ отримані наукові результати використовуються при вивченні дисциплін “Арифметичні основи обчислювальної техніки”, “Надійність, контроль, діагностика й експлуатація ЕОМ”, “Спеціалізовані архітектури ЕОМ”, і “Діагностика комп'ютерних систем”.

Наукові результати використовуються також у навчальному процесі Національного технічного університету України “КПІ” на кафедрі “Спеціалізовані комп'ютерні системи” у курсі лекцій по дисципліні “Надійність, контроль, діагностика й експлуатація ЕОМ”.

Висновки

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

Перехід від моделі точних обчислень, що склалася історично в силу обмежених стартових можливостей ОТ, до обробки приблизних даних суттєво змінює умови ФД ОП. Достовірність функціонування ОП перестає відбивати достовірність результатів приблизних обчислень, що виявляють стійкість до дії несправностей. Втрачають ефективність традиційні методи ФД ОП, демонструючи нову властивість відбраковувати достовірні результати, що визначає важливу науково-технічну проблему створення теоретичних основ і методів ФД ОП для підвищення достовірності контролю результатів приблизних обчислень, яка вирішується у дисертації.

Основні результати роботи

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

2. Отримано оцінки достовірності результатів приблизних обчислень і достовірності їх контролю методами ФД ОП, що вказують на наступне: достовірність функціонування ОП не дає адекватної оцінки достовірності результатів приблизних обчислень; використовувані методи ФД мають низьку достовірність контролю унаслідок відбраковування достовірних результатів.

3. Запропоновано пороговий та ймовірнісний підходи до організації ФД, що дозволяють підвищити достовірність контролю результатів приблизних обчислень шляхом зниження ймовірності відбраковування достовірних результатів. Пороговий підхід установлює поріг кількості несуттєвих помилок. Обґрунтовано використання в рамках даного підходу методів контролю з високою ймовірністю виявлення помилки, традиційної для точних обчислень, що дозволяє використовувати відомі методи ФД. Ймовірнісний підхід ідентифікує суттєві помилки по частоті їхньої появи. Доведено ефективність використання методів контролю з низькою ймовірністю виявлення помилки, що також сприяє використанню ПРК для спрощення ЗК.

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

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

6. Розроблено узагальнений метод контролю за модулем, який виконує ФД ОП, що реалізують скорочені арифметичні операції, і містить у собі цілочисельний метод контролю за модулем в окремому випадку відсутності скорочених обчислень. У матричних ОП кількість устаткування на контроль знижується від рівня квадратичної залежності від розрядності операндів до лінійної залежності: у 3,9, 5,3 і 4,2 разів відповідно для помножувача, зсувача та дільника мантис (з розрядністю n = 32). Метод забезпечує високу достовірність контролю за рахунок зменшення ймовірності відбраковування достовірних результатів: до 2,2 і 3,7 разів для матричних і конвеєрних ОП, відповідно (n = 32).

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

7.1. У методі контролю за забороненим значенням використання ПІН, що властива результатам обчислювальних операцій, забезпечує спрощення ЗК помножувача в 9,3 разів і зниження показника недостовірності контролю в 7,5 разів. Для ОП піднесення в квадрат і куб ЗК спрощуються на 33% і 25%, а показник недостовірності контролю знижується в 3,7 і 2,3 рази.

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

7.3. Метод логарифмічного контролю враховує ПІН у формі недовикористаних старших позицій у розрядних сітках форматів чисел з фіксованою точкою, що спрощує ЗК у 4,7 разів. Метод забезпечує виявлення помилок у залежності від їх величини і знижує показник недостовірності контролю в 8,2 разів.

7.4. Метод контролю по нерівностях, що визначає границі результату з урахуванням особливостей арифметичних операцій, забезпечує виявлення помилок з урахуванням їх величини. Схеми ЗК ОП для піднесення в квадрат, вилучення квадратного кореня і помножувача спрощуються в 1,3 рази, а додавача - у 5 разів. Показник недостовірності контролю знижується для помножувача в 1,2 разів, а для інших ОП у 9 - 10 разів.

7.5. Метод поелементного контролю використовує регулярність структури матричних ОП, що забезпечує спрощення ЗК додавача в 3 рази, а разом з контролем ОП на обмеженій множині вхідних слів - у 4 рази. Показник недостовірності контролю знижується в 8,2 разів.

8. Розроблено систему ФД сигнального процесора, впровадженого в серійне виробництво на п/с Р-6553 у рамках госпдоговорних робіт з постанови Ради Міністрів СРСР і інших директивних органів. Розроблені ЗК помножувача мантис у складі цифрового фільтра при проведенні ДКР за договором між УНДІРТ і Концерном радіозв'язку, радіомовлення і телебачення.

Список основних праць, опублікованих автором по темі дисертації

1. Дрозд О.В. Контроль за модулем обчислювальних пристроїв. Навч. посібн. для студ. спеціальності 7.091501 - “Комп'ютерні та інтелектуальні системи та мережі” / Одеськ. нац. політехн. ун-т. - Одеса: АО Бахва, 2002. - 144 с. - ISBN 966-7079-69-4.

2. Drozd A. V., Lobachev M. V. Efficient on-line Testing Method for Floating-Point Adder // Proc. Design, Automation and Test in Europe Conf. - Munich (Germany). - 2001. - P. 307 - 311.

3. Дрозд А.В., Аль-Аззех Р. функциональное диагностирование сбоенечувствительных вычислительных устройств // Тр. Одес. политехн. ун-та. - Одесса, 1996. - Вып. 2. - С. 18 - 20.

4. Дрозд А.В., Лобачев М.В., Хассонах У. функциональное диагностирование арифметических устройств с сокращенным выполнением операций // Тр. Одес. политехн. ун-та. - Одесса, 1996. - Вып. 2. - С. 20 - 22.

5. Дрозд А.В., Лобачев М.В. функциональное диагностирование параллельного арифметического сдвигателя // Тр. Одес. политехн. ун-та. - Одесса, 1997. - Вып. 2. - С. 27 - 29.

6. Дрозд А.В. функциональное диагностирование сбоенечувствительных вычислительных устройств с неявной идентификацией неисправностей // Сб. “Обработка информации и обеспечение надежности СУ”. - Харьков: НАНУ, ХВУ. - 1997. - С. 27 - 29.

7. Дрозд А.В. Сканирующий контроль вычислительных устройств // Тр. Одес. политехн. ун-та. - Одесса, 1998. - Вып. 2. - С. 34 - 35.

8. Дрозд А.В. Контроль по модулю операции сокращенного деления // Тр. Одес. политехн. ун-та. - Одесса, 1998. - Вып. 2. - С. 36 - 38.

9. Дрозд А.В. Контроль вычислительных устройств по неравенствам // Ученые записки Симферопольс. гос. ун-та. - Винница-Симферополь, 1998. - Спецвып. - С. 237 - 240.

10. Дрозд А.В., Лобачев М.В. Контроль по модулю операции сложения чисел с плавающей точкой // Придніпровський науковий вісник. - Дніпропетровськ. - Червень 1998. № 55 (122). - С. 76 - 83.

11. Дрозд А.В. Использование логарифмического контроля для обнаружения отказов арифметических устройств // Вісн. НТУУ “КПІ”. Інф., упр. та обчисл. техніка. - К., 1998. - Вип. 31. - С. 224 - 231.

12. Дрозд А.В. Контроль по модулю операции сокращенного деления без восстановления остатка // Вісн. НТУУ “КПІ”. Інф., упр. та обчисл. техніка. - К., 1998. - Вип. 31. - С. 232 - 237.

13. Дрозд А.В. Контроль по модулю однотактного умножителя с сокращенным выполнением операции // Электронное моделирование. Том 20. - 1998. - № 3. - С. 90 - 98.

14. Дрозд А.В. Особенности контроля приближенных вычислений // Тр. Одес. политехн. ун-та. - Одесса, 1999. - Вып. 1(7). - С. 209 - 211.

15. Дрозд А.В., Лобачев М.В. Контроль по модулю конвейерного умножителя с сокращением вычислений // Тр. Одес. политехн. ун-та. - Одесса, 1999. - Вып. 2(8). - С. 157 - 158.

16. Дрозд А.В., Аль-Аззех Р., Лобачев М.В. Контроль квадратора с использованием естественной информационной избыточности // Тр. Одес. политехн. ун-та. - Одесса, 1999. - Вып. 3 (9). - С. 123 - 125.

17. Drozd A.V. Control in modulus of the single-cycle multiplier with abridged mode of operation // Engineering Simulation. - V. 16. - 1999. - P. 377 - 385.

18. Дрозд А.В., Лобачев М.В., Р. Аль-Аззех функциональное диагностирование сумматора по неравенствам // Тр. Одес. политехн. ун-та. - Одесса, 2000. - Вып. 1 (10). - С. 100 - 102.

19. Дрозд А.В., Зуда М., Дрозд Ю.В. Повышение быстродействия логарифмического контроля вычислительных устройств // Тр. Одес. политехн. ун-та. - Одесса, 2000. - Вып. 3(12). - С. 92 - 94.

20. Дрозд А.В., Зуда М., Лобачев М.В. Использование логарифмических оценок в функциональном диагностировании вычислительных устройств с плавающей точкой // Тр. Одес. политехн. ун-та. - Одесса, 2001. - Вып. 1 (13). - С. 93 - 96.

21. Бадр Я., Дрозд А.В. Организация сканирования в поэлементном контроле вычислительных устройств // Тр. Одес. политехн. ун-та. - Одесса, 2001. - Вып. 2 (14). - С. 90 - 92.

22. Дрозд А.В. Сокращенные операции и контроль в многооперандной обработке чисел // Тр. Одес. политехн. ун-та. - Одесса, 2001. - Вып. 4 (16). - С. 97 - 100.

23. Дрозд А.В., Огинская Е.В., Николенко И.Н. Возможности повышения обнаруживающей способности контроля по неравенствам // Тр. Одес. политехн. ун-та. - Одесса, 2002. - Вып. 1 (17). - С. 107 - 110.

24. Дрозд А.В. естественные ресурсы контроля приближенных вычислений в функциональном диагностировании вычислительных устройств // Тр. Одес. политехн. ун-та. - Одесса, 2002. - Вып. 2 (18). - С. 90 - 93.

25. Дрозд А.В., Зуда М., Николенко И.Н. Логарифмический контроль сумматора с плавающей точкой // Тр. Одес. политехн. ун-та. - Одесса, 2002. - Вып. 2 (18). - С. 93 - 96.

26. Дрозд А.В., Бадр Я. Поэлементный контроль сумматора с плавающей точкой // Радіоелектроніка та інформатика. 2002. N 2. - С. 59 - 63.

27. Дрозд А. В., Зуда М. Логарифмический контроль деления мантисс чисел в вычислительных устройствах с плавающей точкой // Радіоелектроніка та інформатика. - 2002. - № 3. - С. 75 - 78.

28. Дрозд А. В. Достоверность рабочего диагностирования вычислительных устройств для обработки приближенных данных // Зб. наукових праць Харківського військового ун-ту НАНУ. Системи обробки інформації. - Харків, 2002. - Вип. 4 (20). - С. 8 - 13.

29. Дрозд А.В., Огинская Е.В., Контроль по неравенствам умножителя мантисс чисел с плавающей точкой // Вісн. НТУУ “КПІ”. Інф., упр. та обчисл. техніка. - К., 2002. - Вип. 38. - С. 34 - 40.

30. Дрозд А.В. Базовые концепции функционального диагностирования вычислительных устройств для приближенной обработки данных // Электронное моделирование. Том 25. - 2003. - № 1. - С. 73 - 79.

31. Дрозд А.В., Зуда М., Яароб Б., Огинская Е.В. Контроль приближенных вычислений // Материалы международ. конференции “Автоматика - 2001”. - Одесса, 2001. - С. 85 - 86.

32. Дрозд А.В., Огинская Е.В., Лобачев М.В. Использование неравенств для контроля вычислительных устройств // Тр. второй международ. научно-практической конференции “Современные информ. и электрон. технологии. - Одесса, 2001. - С. 80.

33. Дрозд А. В., Яароб Б., Зуда М. Огинская Е.В. Функциональное диагностирование вычислительных устройств для приближенной обработки данных // Інформаційно-керуючі системи на залізничному транспорті. 2002. № 4, 5 (37). - С. 25.

34. Drozd A. V., Lobachev M. V., Hassonah W. Hardware check of Arithmetic Devices with Abridged Execution of Operations // Proc. The European Design & Test Conf. - Paris (France). - 1996. - P. 611.

35. Drozd A. V. Efficient Method of Failure Detection in Iterative Array Multiplier // Proc. Design, Automation and Test in Europe Conf. - Paris (France). - 2000. - P. 764.

36. Drozd A. V., Lobachev M. V., Drozd J. V. Efficient on-line Testing Method for a Floating-Point Iterative Array Divider. - Proc. Design, Automation and Test in Europe Conf. - Paris (France). - 2002. - P. 1127.

37. Устройство для вычисления модуля комплексного числа. А. c. 1001085 СССР, МКИ G 06 F 7/38 / А.В. Дрозд, Е.Л. Полин, И.Ф. Муравинец, А.Н. Романов, В.А. Соколов (СССР). - № 3343240/18-21; Заявлено 12.10.81; Опубл. 28.02.83, Бюл. № 8. - 4 c.

38. Устройство для вычисления модуля комплексного числа. А. c. 1104505 СССР, МКИ G 06 F 7/38 / А.В. Дрозд, Е.Л. Полин, Л.А. Волощук, А.Н. Романов, И.Ф. Муравинец (СССР). - № 3495086/18-24; Заявлено 27.09.82; Опубл. 23.07.84, Бюл. № 27. - 4 c.

39. Запоминающее устройство с самоконтролем. А. с. 1105944 СССР, МКИ G 11 C 29/00 / Е.Л. Полин, А.В. Дрозд, А.Г. Шипита, В.П. Карпенко, В.А. Минченко, В.Ф. Стручев (СССР). - № 3594228/18-24; Заявлено 23.05.83; Опубл. 30.07.84, Бюл. № 28. - 3 c.

40. Устройство для сдвига информации. А. с. 1109807 СССР, МКИ G 11 C 19/00 / А.В. Дрозд, Е.Л. Полин, А.М. Романкевич, В.Н. Валуйский, И.Ф. Муравинец, А.Н. Романов (СССР). - № 3570735/18-24; Заявлено 02.04.83; Опубл. 23.08.84, Бюл. № 31. - 4 c.

41. Устройство для сдвига информации. А. с. 1173447 СССР, МКИ G 11 C 19/00 / А.В. Дрозд, Е.Л. Полин, В.Л. Панченко, А.Е. Малярчук, В.Ф. Стручев (СССР). - № 3713982/24-24; Заявлено 27.03.84; Опубл. 15.08.85, Бюл. № 30. - 4 c.

42. Устройство для сдвига числа. А. c. 1177808 СССР, МКИ G 06 F 7/38 / Е.Л. Полин, В.А. Минченко, Ю.Г. Клименко, А.В. Дрозд, В.Л. Панченко, В.Ф. Стручев (СССР). - № 3713983/24-24; Заявлено 27.03.84; Опубл. 07.09.85, Бюл. № 33. - 2 c.

43. Устройство для контроля умножения чисел по модулю m. А. c. 1177814 СССР, МКИ G 06 F 11/08 / А.В. Дрозд, Е.Л. Полин, В.Л. Панченко, В.А. Минченко, Ю.Г. Клименко (СССР). - № 3716973/24-24; Заявлено 27.03.84; Опубл. 07.09.85, Бюл. № 33. - 3 c.

44. Запоминающее устройство с самоконтролем. А. с. 1188789 СССР, МКИ G 11 C 29/00 / А.В. Дрозд, Е.Л. Полин, В.Л. Панченко, В.В. Лебедь, О.П. Гусева (СССР). - № 3738865/24-24; Заявлено 27.03.84; Опубл. 30.10.85, Бюл. № 40. - 2 c.

45. Устройство для программируемой задержки информации. А. С. 1193653 СССР, МКИ G 06 F 1/04 / Е.Л. Полин, Е.Б. Великая, А.В. Дрозд, Л.А. Волощук, В.А. Кравцов, В.Ф. Стручев (СССР). - № 3739648/24-24; Заявлено 11.05.84; Опубл. 23.11.85, Бюл. № 43. - 3 c.

46. Устройство для вычисления модуля комплексного числа. А. c. 1193662 СССР, МКИ G 06 F 7/38 / А.В. Дрозд, Е.Л. Полин, В.Л. Панченко, В.А. Соколов, В.Ф. Стручев (СССР). - № 3756907/24-24; Заявлено 11.05.84; Опубл. 23.11.85, Бюл. № 43. - 3 c.

47. Устройство для синхронизации импульсных последовательностей. А. c. 1221727 СССР, МКИ H 03 K 5/13 / Е.Л. Полин, С.А. Нестеренко, А.В. Дрозд, В.П. Карпенко, В.А. Соколов (СССР). - № 3792916/24-21; Заявлено 21.09.84; Опубл. 30.03.86, Бюл. № 12. - 3 c.

48. Запоминающее устройство. А. с. 1233212 СССР, МКИ G 11 B 21/00 / Е.Л. Полин, Е.Б. Великая, А.В. Дрозд, Ю.Г. Клименко, В.С. Волощук (СССР). - № 3793037/24-24; Заявлено 21.09.84; Опубл. 23.05.86, Бюл. № 19. - 4 c.

49. Устройство задержки импульсов. А. c. 1246352 СССР, МКИ H 03 K 5/13 / Е.Л. Полин, В.П. Карпенко, А.В. Дрозд, В.А. Кравцов, А.Е. Малярчук (СССР). - № 3841117/24-21; Заявлено 09.01.85; Опубл. 23.07.86, Бюл. № 27. - 4 c.

50. Устройство для контроля умножения чисел по модулю. А. c. 1259269 СССР, МКИ G 06 F 11/08 / А.В. Дрозд, Е.Л. Полин, В.П. Карпенко, А.Г. Шипита, В.А. Соколов (СССР). - № 3873966/24-24; Заявлено 22.03.85; Опубл. 23.09.86, Бюл. № 35. - 5 c.

51. Оперативное запоминающее устройство. А. c. 1264240 СССР, МКИ G 11 C 11/00 / Е.Л. Полин, В.А. Минченко, А.В. Дрозд, В.В. Лебедь, В.В. Шабадаш (СССР). - № 3896413/24-24; Заявлено 16.05.85; Опубл. 15.10.86, Бюл. № 38. - 5 c.

52. Устройство для сдвига числа с контролем. А. c. 1277116 СССР, МКИ G 06 F 11/10 / А.В. Дрозд, Е.Л. Полин, В.Л. Панченко, В.В. Лебедь, В.П. Карпенко (СССР). - № 3873952/24-24; Заявлено 22.03.85; Опубл. 15.12.86, Бюл. № 46. - 6 c.

53. Устройство для сдвига информации с контролем. А. c. 1282135 СССР, МКИ G 06 F 11/10 / А.В. Дрозд, Е.Л. Полин, В.Л. Панченко, Ан.В. Дрозд, В.А. Минченко (СССР). - № 3884664/24-24; Заявлено 09.01.85; Опубл. 07.01.87, Бюл. № 1. - 4 c.

54. Устройство для задержки информации. А. c. 1287137 СССР, МКИ G 06 F 1/04 / А.В. Дрозд, Е.Л. Полин, А.Е. Малярчук, В.Н. Лацин (СССР). - № 3873967/24-24; Заявлено 22.03.85; Опубл. 30.01.87, Бюл. № 4. - 4 c.

55. Устройство для сложения операндов с плавающей точкой с контролем. А. c. 1310826 СССР, МКИ G 06 F 11/10, 7/50 / А.В. Дрозд, Е.Л. Полин, В.А. Кравцов, В.С. Волощук, А.Г. Шипита (СССР). - № 4030818/24-24; Заявлено 31.01.86; Опубл. 15.05.87, Бюл. № 18. - 6 c.

56. Запоминающее устройство. А. c. 1319077 СССР, МКИ G 11 C 7/00 / А.В. Дрозд, В.П. Карпенко, В.В. Лебедь, А.Е. Малярчук, В.А. Минченко, В.В. Шабадаш (СССР). - № 4015799/24; Заявлено 31.01.86; Опубл. 23.06.87, Бюл. № 23. - 3 c.

57. Устройство для контроля по модулю m=2l-1 умножения матриц чисел. А. c. 1339565 СССР, МКИ G 06 F 11/08/ А.В. Дрозд, Е.Л. Полин, В.В. Шабадаш, В.А. Минченко и Е.В. Годелевич (СССР). - № 3975516/24-24; Заявлено 14.11.85; Опубл. 23.09.87, Бюл. № 35. - 5 c.

58. Устройство цифрового интегрирования. А. c. 1345192 СССР, МКИ G 06 F 7/64 / Е.Л. Полин, А.В. Дрозд, В.В. Лебедь, В.А. Соколов, В.С. Волощук (СССР). - № 4015960/24-24; Заявлено 31.01.86; Опубл. 15.10.87, Бюл. № 38. - 6 c.

59. Устройство для суммирования чисел с плавающей точкой. А. c. 1348825 СССР, МКИ G 06 F 7/50 / А.В. Дрозд, О.Н. Паулин, Е.Л. Полин, Н.И. Синегуб (СССР). - № 4047238/24-24; Заявлено 08.01.86; Опубл. 30.10.87, Бюл. № 40. - 4 c.

60. Запоминающее устройство с самоконтролем. А. с. 1368921 СССР, МКИ G 11 C 29/00/ А.В. Дрозд, Е.Л. Полин, В.А. Соколов, В.А. Минченко, В.П. Карпенко (СССР). - № 3975474/24-10; Заявлено 14.11.85; Опубл. 23.01.88, Бюл. № 3. - 5 c.

61. Матричное устройство для возведения в квадрат. А. c. 1439583 СССР, МКИ G 06 F 7/552 / А.В. Дрозд, Е.Л. Полин, В.Н. Лацин, В.А. Соколов, В.Л. Панченко (СССР). - № 3992917/24-24; Заявлено 14.11.85; Опубл. 23.11.88, Бюл. № 43. - 2 c.

62. Матричное устройство для возведения в квадрат. А. с. 1520512 СССР, МКИ G 06 F 7/552 / А.В. Дрозд, Е.Л. Полин, А.М. Романкевич, В.Н. Валуйский, С.А. Нестеренко (СССР). - № 4401437/24-24; Заявлено 31.03.88; Опубл. 07.11.89, Бюл. № 41. - 3 c.

63. Устройство для возведения в квадрат. А. c. 1534458 СССР, МКИ G 06 F 7/552 / А.В. Дрозд, Е.Л. Полин, Г.П. Баранникова, Ю.В. Дрозд (СССР). - № 4413555/24-24; Заявлено 21.04.88; Опубл. 07.01.90, Бюл. № 1. - 5 c.

64. Матричное устройство для возведения в квадрат. А. с. 1608653 СССР, МКИ G 06 F 7/552 / А.В. Дрозд, Е.Л. Полин, А.С. Попов, Ю.В. Дрозд (СССР). - № 4610062/24-24; Заявлено 22.11.88; Опубл. 23.11.90, Бюл. № 43. - 7 c.

65. Устройство для контроля умножения двоичных чисел по модулю три. А. c. 1651288 СССР, МКИ G 06 F 11/08 / А.В. Дрозд, Е.Л. Полин, А.С. Попов, О.Н. Паулин, Ю.В. Дрозд (СССР). - № 4433718/24; Заявлено 30.05.88; Опубл. 23.05.91, Бюл. № 19. - 4 c.

66. Устройство для контроля умножения двоичных чисел по модулю три. А. c. 1774337 СССР, МКИ G 06 F 11/08 / А.В. Дрозд, Е.Л. Полин, А.С. Попов, Ю.В. Дрозд (СССР). - № 4495390/24; Заявлено 17.10.88; Опубл. 07.11.92, Бюл. № 41. - 4 c.

Анотація

Дрозд Олександр Валентинович. Теоретичні основи, методи та засоби функціонального діагностування вузлів обчислювальних пристроїв з використанням природної надмірності при виконанні приблизних обчислень. - рукопис. Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 05.13.05 - Елементи і пристрої обчислювальної техніки та систем керування. - Одеський національний політехнічний університет, Одеса, 2003.

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

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

Abstract

Drozd Alexander Valentinovich. Theoretic Bases, Methods and Means for On-line Testing of Computing Devices Units with use of natural redundancy in Approximated Calculations Execution. - Manuscript. Thesis for claiming Doctor of Science degree (techn.) in speciality 05.13.05 - Elements and devices of computer's equipment and control systems. - Odessa national polytechnic university. Odessa, 2003.

Dissertation is devoted to creating of the theoretic basis, methods and means of on-line testing (OT) for modern computing devices (CD) executed approximated calculations. Estimations which testify to essential lowering reliability of results checking for the modern on-line testing methods showing new property to reject authentic results of approximate calculations are obtained. Threshold and probability approaches for rise of results checking reliability are offered. The concepts of natural check recourses (NCR) implementation is defined. The class of truncated arithmetic operations is selected and the generalized residue checking method distributed on them with rise of results checking reliability is developed. The on-line testing methods using NCR for simplification of means for a check and rise of results checking reliability are proposed.

Key words: on-line testing, computing devices, approximated calculations.

Аннотация

Дрозд Александр Валентинович. Теоретические основы, методы и средства функционального диагностирования узлов вычислительных устройств с использованием естественной избыточности при выполнении приближенных вычислений. Рукопись.

Диссертация на соискание ученой степени доктора технических наук по специальности 05.13.05 - элементы и устройства вычислительной техники и систем управления. - Одесский национальный политехнический университет, Одесса, 2003.

Диссертация посвящена разработке теоретических основ и методов функционального диагностирования (ФД) вычислительных устройств (ВУ) для повышения достоверности контроля результатов приближенных вычислений. Получены оценки достоверности результатов приближенных вычислений и достоверности их контроля, свидетельствующие о новых условиях ФД, при которых достоверность функционирования ВУ перестает адекватно отражать достоверность результатов, а метод контроля проявляет новое свойство отбраковывать достоверные результаты, существенно снижающее эффективность используемых методов контроля ВУ.

Предложены два подхода к ФД ВУ для повышения достоверности контроля результатов приближенных вычислений путем снижения вероятности отбраковки достоверных результатов - пороговый и вероятностный. Пороговый подход устанавливает порог количеству несущественных ошибок. Обосновано использование в рамках данного подхода методов контроля с высокой вероятностью обнаружения ошибки, традиционной для точных вычислений. Вероятностный подход идентифицирует существенные ошибки по частоте их появления. Доказана эффективность использования методов контроля с низкой вероятностью обнаружения ошибки. Исследованы и обобщены особенности организации и функционирования ВУ, составляющие естественные ресурсы контроля (ЕРК). Сформулирована концепция использования ЕРК и определена их ведущая роль в разработке методов ФД ВУ.

Выделен класс сокращенных операций умножения, сдвига и деления. Доказана целесообразность использования сокращенных операций как основного метода обработки мантисс чисел с плавающей точкой - без потери точности вычислений почти двукратно уменьшается количество оборудования и повышается быстродействие ВУ, многократно снижается количество отбрасываемых разрядов, ошибки в которых снижают достоверность контроля.

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

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

Разработаны методы ФД с низкой вероятностью отбраковки достоверных результатов, использующие вероятностный подход и ЕРК для упрощения СК и повышения достоверности контроля результатов приближенных вычислений. Показатель недостоверности контроля снижается до 2,2 раз в случае серий ошибок при отказах и многократно для отдельных ошибок, вызванных сбоями. Методы сравниваются с известным контролем по модулю.

В методе контроля по запрещенным значениям использование естественной информационной избыточности (ЕИИ), присущей результатам вычислительных операций, обеспечивает упрощение СК умножителя в 9,3 раз и снижение показателя недостоверности контроля в 7,5 раз. Для ВУ возведения в квадрат и куб СК упрощаются на 33% и 25%, а показатель недостоверности контроля снижается в 3,7 и 2,3 раз.

Контроль ВУ на ограниченном множестве входных слов направлен на создание искусственной информационной избыточности на входах ВУ и ведет к упрощению СК умножителя в среднем в 1,7 раз и снижению показателя недостоверности контроля в 7,8 раз.

Логарифмический контроль, учитывающий ЕИИ в форме недоиспользованных старших позиций в разрядных сетках форматов чисел, упрощает СК в 4,7 раз и, оценивая величину ошибки, снижает показатель недостоверности контроля в 8,2 раз.

Контроль по неравенствам использует особенности арифметических операций для определения границ результата, упрощая СК ВУ для возведения в квадрат, извлечения квадратного корня и умножителя в 1,3 раза, а сумматора - в 5 раз. Показатель недостоверности контроля снижается для умножителя в 1,2 раз, а для остальных ВУ в 9 - 10 раз.

Поэлементный контроль использует регулярность структуры матричных ВУ и обеспечивает упрощение СК сумматора в 3 раза, а совместно с контролем ВУ на ограниченном множестве входных слов - в 4 раза. Показатель недостоверности контроля снижается в 8,2 раз.

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

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

...