Теоретичні основи, методи та засоби функціонального діагностування вузлів обчислювальних пристроїв з використанням природної надмірності при виконанні приблизних обчислень
Створення методів та засобів функціонального діагностування обчислювальних пристроїв для підвищення достовірності контролю результатів при виконанні приблизних обчислень. Розробка порогового та імовірнісного підходу для підвищення точності розрахунків.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | автореферат |
Язык | украинский |
Дата добавления | 06.07.2014 |
Размер файла | 186,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Одеський національний політехнічний університет
Автореферат
дисертації на здобуття наукового ступеня
доктора технічних наук
05.13.05 Елементи та пристрої обчислювальної техніки та систем керування
Теоретичні основи, методи та засоби функціонального діагностування вузлів обчислювальних пристроїв з використанням природної надмірності при виконанні приблизних обчислень
Дрозд Олександр Валентинович
Одеса 2003
Дисертацією є рукопис.
Робота виконана в Одеському національному політехнічному університеті міністерства освіти і науки України.
Науковий консультант: доктор технічних наук, професор Романкевич Олексій Михайлович, Національний технічний університет “КПІ”, професор кафедри “Спеціалізовані комп'ютерні системи”.
Офіційні опоненти: доктор технічних наук, професор Власенко Віктор Олексійович, Університет Ополе, Польща, завідувач кафедри технології; доктор технічних наук, професор Тоценко Віталій Георгійович, Інститут проблем реєстрації інформації НАН України, завідувач відділом надійності та технічної діагностики;
доктор технічних наук, професор Харченко В'ячеслав Сергійович, Національний аерокосмічний університет ім. М.Є. Жуковського “Харківський авіаційний інститут”, завідувач кафедри комп'ютерних систем та мереж.
Провідна установа: Інститут проблем математичних машин та систем, відділ теорії надійності та ефективності засобів обчислювальної техніки, Національна академія наук України, м. Київ.
Захист відбудеться 23 жовтня 2003 р. о 1330 годині на засіданні спеціалізованої вченої ради Д 41.052.01 Одеського національного політехнічного університету за адресою: 65044, м. Одеса, пр. Шевченка, 1.
З дисертацією можна ознайомитись у бібліотеці Одеського національного політехнічного університету за адресою: 65044, м. Одеса, пр. Шевченка, 1.
Автореферат розісланий 16 вересня 2003 р.
Вчений секретар спеціалізованої вченої ради Ямпольський Ю.С.
1. Загальна характеристика роботи
пороговий імовірнісний контроль
Актуальність теми. Функціональне діагностування (ФД) обчислювальних пристроїв (ОП) дає оперативну оцінку їх технічного стану, що відіграє важливу роль у забезпеченні високої достовірності результатів обчислень, є необхідною умовою успішного розвитку обчислювальної техніки (ОТ) у цілому і має особливе значення для спеціалізованих обчислювачів, які вирішують задачі в реальному масштабі часу, наприклад, у цифровій обробці сигналів. Для них засоби ФД в умовах обмеженого часу реалізують основний, якщо не єдиний спосіб оцінки достовірності одержуваних результатів.
Постійне удосконалювання ОП по таких важливих показниках, як продуктивність, діапазон і точність оброблюваних даних, складність технічних рішень і достовірність роботи, відносить ФД до найбільш динамічних напрямків ОТ і пред'являє до методів і засобів ФД високі вимоги.
Розвиток ФД цифрових схем ОП, зобов'язано працям таких учених, як Гуляєв В.А., Діаз М., Зоріан Є., Картер В., Ніколаідіс М., Метц Ж, Романкевич О.М., Пархоменко П.П., Путинцев М.Д., Тоценко В.Г., Селлерс Ф., Согомонян Є.С., Харченко В.С., Шнейдер П., Щербаков М. С. та ін., що зробили значний внесок у теорію і практику технічної діагностики, розробку й оцінку методів і засобів контролю (ЗК) дискретних пристроїв, виявлення й використання природних форм надмірності для підвищення ефективності цих методів.
Із зростанням розмірності обчислювальних задач важливе місце у ОТ займають приблизні обчислення, що суттєво змінюють умови, при яких виконується ФД ОП. Округлення даних приводить до значного зниження впливу несправностей ОП на достовірність результатів приблизних обчислень. Достовірність функціонування ОП перестає адекватно відбивати достовірність результатів, що при справному ОП може бути знижена через втрату точності при округленні даних і підвищується за рахунок одержання достовірних результатів при несправностях ОП. Методи контролю втрачають достовірність, виявляючи нову властивість, яка полягає у відбраковуванні достовірних результатів, що обчислюються при несправностях.
Одночасно збагачується арсенал особливостей організації і функціонування ОП, - різних форм інформаційної, структурний та часової надмірності, що складають природні ресурси контролю (ПРК), виявлення і використання яких особливо важливо для удосконалювання відомих і розробки нових методів і засобів ФД для ОП, орієнтованих на обробку приблизних даних.
Зв'язок роботи з науковими програмами, планами, темами. Дослідження в області ФД ОП виконувалися в рамках госп/д робіт “Черкал-уво-п” (1981 - 1984), “Чехонь-УВО” (1985 - 1986), “705-703-2” (1986 - 1986), “Кора-УВО” (1987) по постанові Ради Міністрів СРСР та інших директивних органів, а також планової науково-дослідної роботи № 329-73 “Апаратні засоби автоматизованих систем. Розробка та дослідження методів та засобів автоматизованих систем” (1997 - 2002 р.) кафедри комп'ютерних інтелектуальних систем та мереж Одеського політехнічного університету, а також договору № 1-ДС/62 “Про співпрацю з розробки обчислювальних пристроїв для цифрової обробки сигналів у системах телекомунікації”, що укладений між ОНПУ й Українським НДІ радіо і телебачення (2002 - 2005 р.). Роль автора в цих науково-дослідних темах складається в розробці теоретичних основ, методів і засобів ФД ОП для обробки приблизних даних.
Мета і задачі дослідження. Метою дисертаційної роботи є розробка теоретичних основ, методів та засобів функціонального діагностування ОП для підвищення достовірності контролю результатів приблизних обчислень, що забезпечується за рахунок виявлення та використання особливостей організації та функціонування ОП, які складають природні ресурси контролю.
Для досягнення мети в дисертаційній роботі вирішені такі задачі:
- одержані оцінки впливу несправностей на достовірність результатів приблизних обчислень та оцінки достовірності контролю результатів методами ФД;
- запропоновані пороговий та ймовірнісний підходи до ФД ОП, що дозволяють підвищити достовірність контролю результатів приблизних обчислень шляхом зниження ймовірності відбраковування достовірних результатів;
- досліджені й узагальнені особливості організації і функціонування ОП, що складають ПРК - засіб для аналізу і синтезу методів ФД ОП;
- визначений клас скорочених арифметичних операцій, що багаторазово знижують ймовірність виявлення помилок у відкинутих розрядах результатів;
- розроблений узагальнений метод контролю за модулем, що забезпечує підвищення достовірності контролю результатів зниженням ймовірності відбраковування достовірних результатів для скорочених операцій;
– розроблені методи контролю за забороненим значенням результатів арифметичних операцій, контролю на обмеженій множині вхідних слів, логарифмічного контролю, контролю по нерівностях та поелементного контролю, що використовують ПРК для спрощення ЗК і підвищення достовірності контролю результатів приблизних обчислень шляхом зниження ймовірності відбраковування достовірних результатів.
Об'єкт досліджень - ОП для обробки приблизних даних.
Предмет досліджень - методи та засоби ФД ОП для обробки приблизних даних
Методи досліджень базуються на теорії проектування ЕОМ, схемотехніки ЕОМ, прикладної теорії цифрових автоматів, теорії помилок, теорії ймовірностей, теорії завадостійкого кодування, теорії чисел, елементах теорії алгоритмів і математичної логіки, а також на розробленому автором оригінальному апараті аналізу приблизних обчислень.
Наукова новизна одержаних результатів полягає в розробці теоретичних основ та методів функціонального діагностування ОП, що базуються на розвитку концепції використання природних ресурсів контролю та підвищують достовірність контролю результатів приблизних обчислень за рахунок зниження ймовірності відбраковування достовірних результатів.
Уперше виявлені фактори, що знижують вплив несправностей ОП на достовірність результатів приблизних обчислень, та одержані оцінки їх дії, що свідчать про багаторазове перевищення кількості несуттєвих помилок над кількістю суттєвих помилок.
Одержали подальший розвиток оцінки достовірності результатів приблизних обчислень та достовірності їх контролю, що вказують на нові умови ФД, при яких достовірність результатів відрізняється від достовірності функціонування ОП, а метод контролю виявляє нову властивість відбраковувати достовірні результати, що знижує ефективність традиційних методів контролю.
Уперше запропоновані пороговий та ймовірнісний підходи до ФД ОП для зниження ймовірності відбраковування достовірних результатів приблизних обчислень шляхом встановлення порогу кількості несуттєвих помилок та зменшення ймовірності їх виявлення, відповідно. В рамках цих підходів обґрунтовано використання методів контролю з високою та низькою ймовірністю виявлення помилок.
Одержали подальший розвиток методи врахування природної надмірності при контролі дискретних пристроїв. Сформульовано концепцію використання природних ресурсів контролю для розробки методів ФД ОП.
Уперше виділений клас скорочених операцій для зниження ймовірності виявлення помилок у відкинутих розрядах результатів приблизних обчислень.
Уперше розроблений метод ФД ОП для виконання скорочених операцій, що базується на запропонованому апараті розбивання матриці кон'юнкцій добутку (МКД) на фрагменти та підвищує достовірність контролю за рахунок зниження ймовірності відбраковування достовірних результатів для скорочених операцій. Метод є узагальненням цілочислового контролю за модулем з його поширенням на приблизні обчислення і включає відомий метод як окремий випадок при кількості виключених стовпців МКД k = 0.
Даний метод заснований на наступних доведених наукових положеннях:
– контрольний код зсіченого добутку визначається сумою контрольних кодів фрагментів, що складають старшу частину МКД (покладено в основу контрольного співвідношення для перевірки скороченої операції);
– мінімальна кількість фрагментів nk=k+1 у розбиванні старшої частини МКД досягається в тому і тільки в тому випадку, якщо усі фрагменти є індексованими (положення забезпечує зниження витрат ЗК з квадратичної залежності від розрядності операндів до лінійної в частині обробки контрольних кодів);
– контрольні коди частин операндів обчислюються в процесі згортки операндів, що виконується для контролю цих операндів (положення забезпечує лінійну залежність витрат ЗК від розрядності операндів у частині формування контрольних кодів);
– схема ЗК є самоперевіряємою для константних одиночних несправностей, що забезпечує контроль ЗК у процесі ФД.
Розроблено методи ФД, що використовують ПРК для спрощення ЗК та підвищення достовірності контролю результатів приблизних обчислень шляхом зниження ймовірності відбраковування достовірних результатів:
– одержали подальший розвиток методи контролю за забороненими значеннями, що поширені на арифметичні операції і знижують ймовірність відбраковування достовірних результатів за рахунок використання їх природної інформаційної надмірності;
– уперше розроблений метод контролю ОП на обмеженій множині вхідних слів, що дозволяє створити інформаційну надмірність результатів арифметичних операцій для зниження ймовірності відбраковування достовірних результатів;
– одержали подальший розвиток метод логарифмічного контролю для ОП із фіксованою точкою та метод контролю по нерівностях, які знижують ймовірність відбраковування достовірних результатів за рахунок особливостей подання даних та виконання операцій, що дозволяють оцінювати величину помилки;
– вперше одержаний метод поелементного контролю, що використовує однорідність елементів і регулярність матричних структур однотактних ОП для виявлення помилок з урахуванням їх величини та зниження ймовірності відбраковування достовірних результатів.
Практичне значення одержаних результатів полягає у застосуванні розроблених теоретичних основ, методів та засобів ФД ОП для підвищення ефективності обробки приблизних даних, поліпшення показників продуктивності та достовірності.
Запропоновані методи ФД ОП з приблизним виконанням операцій впроваджені в серійне виробництво в пристроях обчислювальної техніки, захищених 23 авторськими посвідченнями на винаходи. Впровадження здійснене на кафедрі “Обчислювальні машини” та СПКБ “Дискрет” Одеського політехнічного інституту, у Радіотехнічному інституті АН СРСР і п/с Р-6553 в рамках госп/д робіт “Черкал-уво-п”, “Чехонь-УВО”, “705-703-2”, “Кора-УВО” по постанові Ради Міністрів СРСР та інших директивних органів, а також в Українському НДІ радіо і телебачення при проведенні ОКР, виконуваної за договором з концерном радіозв'язку, радіомовлення та телебачення по розробці устаткування сполучення аналогових радіорелейних ліній з цифровими системами передачі. Результати роботи впроваджені в навчальний процес в Одеському національному політехнічному університеті на кафедрі комп'ютерних інтелектуальних систем та мереж, у Національному технічному університеті України “КПІ” на кафедрі спеціалізованих комп'ютерних систем.
Особистий внесок здобувача складається в розробці теоретичних основ та методів ФД ОП для обробки приблизних даних.
Дисертантом запропоновані базові підходи до ФД ОП для підвищення достовірності контролю результатів [3, 31], клас скорочених арифметичних операцій, основні положення методу їх контролю за модулем і використання методу в ОП [2, 4, 5, 10, 15, 34, 36], теоретичні основи й оцінки методів ФД з низькою ймовірністю відбраковування достовірних результатів [16, 18 - 21, 23, 25 - 27, 29, 32, 33, 35], використання ПРК для підвищення ефективності методів ФД у схемних рішеннях для ОП з обробкою приблизних даних [37 - 67].
Апробація роботи. Результати роботи доповідалися й обговорювалися на щорічній міжнародній школі-семінарі “Перспективні системи керування на залізничному, промисловому і міському транспорті” (Алушта, 1995 - 1997, 2002 р.), міжнародній науково-технічній конференції “Приладобудування - 98” (Євпаторія, 1998 р.), другій міжнародній науково-практичній конференції “Сучасні інформаційні та електронні технології” (Одеса, 2001 р.), міжнародній конференції з управління “Автоматика” (Одеса, 2001 р.), європейських конференціях “European Design & Test Conference” (Париж, 1996 р.), “Design, Automation and Test in Europe” (Париж, 2000 р., Мюнхен, 2001 р., Париж, 2002 р.).
Публікації. До основних публікацій по темі дисертації відноситься 66 друкованих праць, у тому числі 1 монографія, 29 статей у наукових журналах і збірниках наукових праць, (21 з них згідно з переліком ВАК України), 6 матеріалів і тез конференцій, 30 авторських посвідчень на винаходи. 15 робіт опубліковано без співавторів.
Структура дисертації. Дисертаційна робота складається з вступу, п'яти глав, висновків і додатків. Повний обсяг дисертації - 327 стор., з них додатків - 37 стор., список літератури - 19 стор. Дисертація містить 79 рисунків, 9 таблиць і посилання на 194 використаних джерела.
2. Основний зміст роботи
У вступі обґрунтована актуальність теми дисертації, сформульовані мета і задачі досліджень, викладені основні наукові та практичні результати.
В першому розділі проведений аналіз стану справ у ФД ОП, що показує на ріст обсягів приблизних обчислень і відставання в розробці для них методів ФД, формулюються задачі по оцінці і підвищенню достовірності контролю результатів у ОП при виконанні приблизних обчислень.
Розвиток обчислювальної техніки, здійснюваний по шляху підвищення надійності та продуктивності, характеризується розпаралелюванням обчислювальних процесів і підвищенням розмірності розв'язуваних задач, що впливає на ОП, а також методи і засоби їх ФД.
З певним рівнем надійності та продуктивності формується поняття самоперевіряємих схем, що визначає основну задачу ФД як виявлення несправності дискретного пристрою за її першою проявою у вигляді помилки з єдиним підходом до обчислювальних і керуючих схем. Це положення відбиває модель точних обчислень, що ігнорує особливості приблизних даних.
На розвиток методології ФД ОП значно впливає використання різних видів природної структурно-часової надмірності.
Набувають поширення однотактні матричні і порозрядні конвеєрні ОП. Підвищення розмірності задач супроводжується ростом обсягу приблизних обчислень, що мають ряд особливостей, зв'язаних з округленнями.
При виконанні приблизних обчислень порушується асоціативний закон, тобто результат залежить від порядку виконання операцій. Наприклад, додавання мільйона з мільйоном одиниць на бінарних операціях з n-розрядною сіткою мантис, n 20 може дати один чи два мільйони. В першому випадку, мільйон додається мільйон разів до чергової одиниці, що втрачається при вирівнюванні порядків. У другому випадку, складаються пари одиниць, потім двійок і далі - два мільйони. Отже, на справному ОП можна одержати недостовірний результат.
З іншого боку, на несправному ОП може бути отриманий достовірний результат, якщо помилки діють в розрядах, що відкидаються при округленні. У моделі точних обчислень достовірність функціонування ОП ототожнюється з достовірністю результатів обчислень, губиться першорядність достовірності результатів, що стає лише засобом оцінки достовірності функціонування ОП. Обробка приблизних даних суттєво розрізняє ці достовірності, повертаючи достовірності результатів обчислень першорядне положення - при розв'язанні обчислювальної задачі важливий результат, а не технічний стан ОП.
Методи і засоби ФД, що сформувалися в умовах виконання точних обчислень, перестають відповідати сучасним ОП і втрачають свою ефективність. Основний метод - контроль за модулем - у 50% випадків виявлення помилок (що відбувається у відкинутих розрядах) відбраковує правильний результат. Виявлення несправності за її першою проявою у вигляді помилки приводить до необгрунтованих втрат продуктивності ОП.
Таким чином, аналіз ФД ОП свідчить про динамічний розвиток сучасних ОП у напрямку розпаралелювання обчислень та обробки приблизних даних і відставанні в розробці відповідних їм методів і засобів контролю. Назріла необхідність розробки теоретичних основ і методів ФД ОП, спрямованих на вирішення задачі підвищення достовірності контролю результатів при виконанні приблизних обчислень, що містить:
виведення аналітичних залежностей для оцінки достовірності контролю результатів приблизних обчислень методами ФД;
визначення підходів до ФД ОП, що дозволяють підвищити достовірність контролю результатів приблизних обчислень шляхом зниження ймовірності відбраковування достовірних результатів;
розробку методів ФД ОП для зменшення ймовірності відбраковування достовірних результатів при виконанні приблизних обчислень.
У другому розділі викладені теоретичні основи ФД ОП при виконанні приблизних обчислень.
В обчислювальній математиці розрізняють вірні та невірні розряди приблизного числа. До вірних розрядів відносять старші розряди числа, молодший з який має вагу, що перевищує абсолютну величину абсолютної похибки, а під невірними розрядами - всі інші молодші розряди числа. Нехай приблизне число AП представляється в n-розрядній сітці з фіксацією точки після молодшого розряду та масштабуючим коефіцієнтом kМ як A, тоді за абсолютною похибкою
A = AП kМ
A визначається кількість невірних і вірних розрядів запису числа A по формулах
nН = Int (log 2|A|), nВ = n - nН, (1)
де Int (log 2 A) + 1 n, Int(x) - ціла частина (x).
Обчислювальному процесу, виконуваному над приблизними даними, може бути поставлений у відповідність обчислювальний процес, що здійснюється над абсолютними похибками вихідних даних. По обчисленій абсолютній похибці A результату A, згідно з (1), визначаються його вірна A{1 nВ} та невірна A{nВ + 1 n} частини.
Визначення 2.1. Результат, що одержаний на справному ОП, є достовірним, якщо необхідна кількість вірних розрядів nТВ nВ, частково-достовірним при nТВ nВ 0 і недостовірним у випадку nВ = 0.
Достовірність результату обробки приблизних даних, одержаного на справному ОП, може бути охарактеризована коефіцієнтом достовірності KD, що визначається в такий спосіб:
KD = nВ / nТВ для nТВ nВ; KD = 1 для nТВ nВ.
Визначення 2.2. Помилка, що генерована несправністю ОП, називається суттєвою, якщо знижує кількість nВ вірних розрядів при KD 1 чи кількість nТВ необхідних вірних розрядів при KD = 1, і несуттєвою у противному випадку.
Несправність ОП не знижує достовірності результату A, зберігаючи кількість його вірних розрядів, за умови
A + EA w
де EA - несуттєва арифметична помилка, яка генерується несправністю; w - вага молодшого вірного розряду A{nВ} результату. Це вказує на несуттєвий вплив арифметичних помилок у невірних розрядах на достовірність результату.
Вплив несправностей на достовірність результату знижується під дією трьох основних факторів:
– відкидання обчислених молодших розрядів результату операції, що приводить до виключення помилок з округленого результату;
– збільшення розрядності мантис понад кількість необхідних вірних розрядів для виконання асоціативного закону щодо приблизних обчислень;
– вирівнювання порядків (масштабуючих коефіцієнтів) чисел з плаваючою (фіксованою) точкою, що приводить до надлишкової точності обчислень.
Помилка є суттєвої, якщо жоден з факторів не відносить її до несуттєвих помилок. Це дозволяє оцінити ймовірність появи суттєвої помилки (тобто ймовірність того, що помилка, яка з'явилася, є суттєвої) по формулі
KT = K1 K2 K3,
де K1 - ймовірність появи помилки в розрядах результату, що залишаються;
K2 - ймовірність появи помилки у вірних розрядах результату;
K3 - ймовірність збереження помилки при вирівнюванні порядків чисел (масштабуючих коефіцієнтів).
Для матричних ОП ймовірність K1 оцінюється (як далі і ймовірності K2 та K3), виходячи з припущення про рівномірний розподіл несправностей по апаратурі, по формулі
K1 = ОЗАл / ООБч, K1 1
де ООБч та ОЗАЛ - кількість устаткування, несправності якого викликають арифметичні помилки в розрядах результату, що обчислюються та залишаються після округлення.
Для порозрядних конвеєрних ОП коефіцієнт K1 оцінюється (як далі і ймовірності K2 та K3), виходячи з припущення про рівну ймовірність виникненні несправності в будь-який момент часу. Для несправностей типу “збій”, що найбільш часто зустрічаються та виявляються в окремих тактах, можна прийняти рівну ймовірність появи арифметичних помилок в окремих розрядах результату. Тоді
K1 = n / nобч, K1 1
де nобч та n - кількість розрядів, що обчислюються та залишаються після округлення мантиси;
При виконанні повнорозрядних бінарних операцій відкидається, як правило, половина обчислюваного повного 2n-розрядного результату. Для матричних ОП множення (зсуву), ділення
ОЗАЛ = 0,5 ООБч
а для порозрядних конвеєрних ОП nОБч = 2 n, що визначає K1 = 0,5.
Ймовірність K2 для однотактних матричних і порозрядних конвеєрних ОП оцінюється відповідно по формулах
K2 = ОТВ / ОЗАЛ, K2 = nтВ / n, K2 1
ОтВ - кількість устаткування, несправності якого викликають арифметичні помилки у вірних розрядах результату; n - розрядність мантиси, що збільшується для одержання необхідної кількості nТВ вірних розрядів.
Закладені у форматах із плаваючою точкою персональних ЕОМ можливості по збільшенню розрядності мантис у 2,8 разів (від одинарної до подвійної розширеної точності) визначають, зокрема, ймовірність K2 0,36.
При вирівнюванні порядків чи масштабуючих коефіцієнтів виникає надлишкова точність - при зсуві мантис губляться розряди, що обчислювалися точними в усіх попередніх операціях. Тому при відсутності вирівнювання K3 = 1, а в противному випадку
K3 = 1 - 0,5 ОС d / n, де ОС = ОС / ОО;
ОС - кількість устаткування вузлів ОП, що передують зсувачу мантис; ОО - загальна кількість устаткування ОП, d - величина зсуву. Для d = n / 2 ймовірність
K3 = 1 - 2 -2ОС
Для декількох операцій вирівнювання коефіцієнт K3 дорівнює добутку коефіцієнтів, що знайдені для кожної з них.
Отримано оцінку достовірності DР (t) результатів обчислень як ймовірності того, що результат має необхідну кількість вірних розрядів при правильному і неправильному функціонуванні ОП:
DР (t) = (DФ (t) + (1 - DФ (t)) (1 - KT)) KD,
де DФ (t) - достовірність функціонування ОП за період часу t.
Коефіцієнт KD враховує зниження достовірності DР (t), якщо розрядність мантиси не забезпечує необхідну кількість вірних розрядів. При KD = 1, достовірність DР (t) перевищує DФ (t) на величину (1 - DФ (t)) (1 - KT), що враховує зниження впливу несправностей на достовірність результату. Після спрощення
DР (t) = (1 - (1 - DФ (t)) KT) KD
При KD = 1 та KT = 1 формула пертворюється у відому оцінку DР = DФ, що підтверджує її справедливість.
Показник недостовірності контролю результатів оцінений як ймовірність того, що при неправильному функціонуванні ОП може бути пропущена суттєва помилка чи відбракований достовірний результат через несуттєву помилку:
DН КР (t) = (1 - PПФ (t)) (PПР + PОТБ)), (2)
де (1 - PПФ (t)) - ймовірність неправильної роботи ОП;
PПР і PОТБ - ймовірності пропуску суттєвої помилки і відбраковування достовірного результату, відповідно.
PПР = KT (1 - PОБН); (3)
PОТБ = PОБН (1 - KT). (4)
Достовірність контролю результатів DКР (t) = 1 - DН КР (t) визначається як
DКР (t) = PПФ (t) + (1 - PПФ (t)) (1 - PПР - PОТБ). (5)
Максимум достовірності DКР (t) досягається при виключенні будь-якої однієї з умов недостовірності контролю: пропуску суттєвої помилки чи відбраковування достовірного результату. На практиці важливо обмежити прояв кожного з цих недоліків. Тому формула доповнюється двома умовами
PПР PПР Д; PОТБ PОТБ Д, (6)
де PПР Д и PОТБ Д - припустимі значення PПР і PОТБ, відповідно.
При KT = 1 формула (5) перетворюється у відому оцінку достовірності
DКР (t) = PПФ (t)+ (1 - PПФ (t)) PОБН
що підтверджує її справедливість, а при KT 1 демонструє нову властивість методу контролю, що полягає у відбраковуванні достовірних результатів приблизних обчислень.
Нехай метод контролю має високу ймовірність Робн = 0,9. Тоді перехід від точних обчислень (КТ = 1) до приблизних з КТ = 0,1 змінює ймовірності PПР і PОТБ, згідно (3) і (4), відповідно від 0,1 до 0,01 і від 0 до 0,81, погіршуючи показник недостовірності контролю DН КР (t) від 0,1 (1 - PпФ (t)) до 0,82 (1 - PпФ (t)), тобто в 8,2 рази. Це вказує на низьку достовірність відомих методів контролю стосовно до приблизних обчислень.
Задача підвищення достовірності контролю результатів вирішується шляхом зниження ймовірності PОТБ відбраковування достовірних результатів при збереженні рівня вимог до ймовірності PПР, що склалися для точних обчислень. Згідно (4), ймовірність PОТБ може бути знижена двома способами: збільшенням ймовірності КТ та зменшенням ймовірності PОБН.
Перший спосіб припускає втручання в організацію основних обчислень. Найбільш перспективним є збільшення коефіцієнта К1 зменшенням кількості розрядів, що відкидаються у обчисленому результаті. Такі можливості мають скорочені арифметичні операції, але вони не набули належного поширення. Одна з основних причин - відсутність ефективних методів контролю.
Другий спосіб реалізується відповідно до наступної теореми.
Твердження 2.1. Для PОБН + KT 1 ймовірність відбраковування достовірних результатів може бути зменшена використанням як завгодно малої ймовірності PОБН A виявлення помилок без збільшення ймовірності PПР вище значення, досягнутого при точних обчисленнях.
Додаткові можливості зниження ймовірності PПР та підвищення достовірності контролю результатів полягають у розробці методів контролю з різними ймовірностями Pобн С та Pобн НС виявлення суттєвих і несуттєвих помилок, Pобн С Pобн НС. Тоді формули (3) та (4) перетворюються до виду
PПР = KT (1 - PОБН С ); PОТБ = (1 - KT) PОБН НС,
POБН C = / nТ; POБН НС = / (n - nТВ);
POБН (Ei) - ймовірність виявлення помилки Ei, що знаходиться в прямій залежності від її величини Ei;
nТВ - кількість вірних розрядів 1 nТВ результату A{1 n}.
В основі таких методів лежить можливість оцінки величини арифметичної помилки. При співвідношенні
POБ C / POБ НC = KP, KP 1
ймовірність
PОТБ = (1 - KT) PОБН C / KP
тобто зменшується в KP разів без збільшення ймовірності PПР.
Таким чином, задача підвищення достовірності контролю результатів приблизних обчислень містить у собі
визначення базових підходів до ФД ОП для зниження ймовірності відбраковування достовірних результатів;
розвиток концепції використання різних видів природної надмірності як основи для розробки та удосконалювання методів ФД, орієнтованих на оцінку результатів обчислень;
визначення класу скорочених арифметичних операцій, що збільшують ймовірність KT та методу їх контролю для зниження ймовірності відбраковування достовірних результатів;
розробку методів ФД, що знижують ймовірність відбраковування достовірних результатів, зменшенням ймовірності виявлення несуттєвих помилок;
розробку методів контролю, що забезпечують оцінку величини помилки і знижують ймовірність відбраковування достовірних результатів за рахунок різної ймовірності виявлення суттєвих і несуттєвих помилок.
Пропонуються два базові підходи до ФД ОП для зниження ймовірності відбраковування достовірних результатів, що відрізняються способами ідентифікації суттєвих помилок: пороговий і ймовірнісний.
В основу порогового підходу покладене відоме рішення по аналізу апаратури на тип її несправності - збій чи відмова (задача класифікації). Запропонований пороговий підхід безпосередньо спрямований на аналіз помилок з позиції достовірності результатів обчислень, а не працездатності апаратури.
Суть порогового підходу полягає у виявленні помилок, підрахунку їх кількості NE на заданому інтервалі TK часу контролю й оцінці кількості виявлених помилок, що суттєво або несуттєво знижує достовірність результатів обчислень. Оцінка виконується порівнянням NE із заданим пороговим значенням SE. Інтервал TK визначається часом вирішення обчислювальної задачі і з початком наступної задачі відраховується знову. Поріг SE визначається припустимою кількістю помилок на інтервалі TK.
Ймовірність пропуску суттєвої помилки визначається при умовах, що серед SE помилок є суттєва помилка і поріг SE не досягнуто (SE помилок не виявлено), по формулі
PПР = 1 - (1 - КТ) SE (1 - PОБН SE). Для КТ 0 і КТ SE 1
формула спрощується до виду
PПР = КТ SE (1 - PОБН SE). (7)
Відбраковування достовірних результатів відбувається, якщо всі SE помилок є несуттєвими і досягнуто поріг SE (виявлено SE помилок), з ймовірністю
PОТБ = (1 - КТ SE) PОБН SE. (8)
Тоді вимоги (6) виконуються з урахуванням (7) та (8) відповідно при умовах КТ SE (1 - PОБН SE) PПР Д та (1 - КТ SE) PОБН SE PОТБ Д, з яких випливає
PоБН .
При використанні методу контролю з ймовірністю виявлення помилки PОБН 1 порівняння кількості помилок необхідно виконувати зі зниженим пороговим значенням
SE* = SE PОБН, SE* 1
що накладає додаткове обмеження на порогове значення SE 1/ PОБН.
Пороговий підхід спрямований на виявлення кожної помилки, викликаної несправністю, і тому пред'являє до методу контролю вимогу високої ймовірності PОБН, подібно ФД ОП при виконанні точних обчислень. Це дозволяє залучити до контролю приблизних обчислень традиційні методи, включаючи контроль за модулем, що одержав найбільше поширення для повнорозрядних ОП.
Якщо в пороговому підході обмежитися мінімальним значенням порога SE = 1 і час контролю TK прийняти нескінченно великим, то це приводить до якісно інших умов ФД ОП для обробки приблизних даних, покладених в основу ймовірнісного підходу.
Теорема 2.1. Для несправностей з ймовірностями прояву PT 1 і PT 2, PT 1 > PT 2 відношення ймовірностей PH 1 і PH 2 їхнього виявлення збільшується при зменшенні ймовірності PОБН виявлення помилки методом контролю.
Теорема 2.2. Відношення ймовірностей виявлення відмови і збою росте при зменшенні ймовірності PОБН виявлення помилки методом контролю.
Відповідно до теорем 2.1 і 2.2, ймовірнісний підхід спрямований на використання методів контролю з низькою ймовірністю PОБН. Як і в пороговому підході виявляється SЕ-а по рахунку помилка, де SЕ = 1 / PоБН.
Ймовірність пропуску суттєвої помилки визначається з умов, що серед SE помилок є суттєва помилка і жодна з помилок SE не виявлена, по формулі
PПР = КТ SЕ (1 - PОБН) SЕ = КТ (1 - PОБН) 1 / PоБН / PоБН. О
скільки для PОБН 0 виконується
(1 - PОБН) 1 / PоБН = e -1, то PПР = КТ / (e PоБН). (9)
Відбраковування достовірних результатів відбувається, якщо всі SE помилок є несуттєвими і виявлена хоча б одна з помилок SE, з ймовірністю
PОТБ = (1 - (1 - PОБН) SЕ)(1 - КТ SE)
що перетворюється до виду
PОТБ = (1 - e -1) (1 - КТ / PОБН), КТ PОБН. (10)
Вимоги (6) виконуються з урахуванням (9) та (10) при умовах e -1 КТ /
PоБН PПР Д та (1 - e -1) (1 - КТ / PОБН) PОТБ Д
що визначає вибір методу контролю з ймовірністю PоБН, область використання методу контролю за значенням КТ та ймовірнісного підходу по показнику
КP = КТ / PОБН 1:
max(КТ, e -1 КТ / PПР Д) PоБН КТ / (1 - PОТБ Д / (1 - e -1)), PПР Д 0, PОТБ Д e -1;
PоБН (1 - PОТБ Д / (1 - e -1)) КТ min (PоБН, e PоБН PПР Д);
(1 - PОТБ Д / (1 - e -1)) КP min (1, e PПР Д).
DН КР (t) = (1 - e -1 - КP (1 - 2 e -1)) (1 - PпФ (t)).
При КP = 1 визначається нижня границя e -1 (1 - PпФ (t)) показника недостовірності контролю результатів при ймовірнісному підході у випадку відмови, що у порівнянні з цілочисельним контролем за модулем дає виграш у 2,2 рази.
Приблизні обчислення та зростаючий паралелізм апаратних структур створюють можливості для нових рішень у розробці ОП, а також для вдосконалювання методів ФД за рахунок виявлення і використання нових джерел спрощення контролю, що істотно доповнює відзначені раніше види природної надмірності.
Визначення 2.3. Особливості організації та функціонування об'єктів контролю, які необхідні для вирішення основної задачі при використанні по призначенню і виявляють якості, що є корисними для виконання контролю, називаються природними ресурсами контролю (ПРК).
Особливості організації ОП складають ПРК схемного рівня, а особливості функціонування визначають умови використання ОП на системному рівні. На схемному рівні виявляються особливості, що властиві обчислювальній операції, машинному запису числа, структурі ОП, логічним функціям елементів, типам несправностей, та інші ПРК. На системному рівні діють особливості обчислювальних систем - багатокаскадність, природна часова надмірність, особливості обчислювальних процесів, включаючи стійкість результатів до несправностей при обробці приблизних даних.
В умовах переходу від моделі точних обчислень до обробки приблизних даних ПРК здобувають особливе методоутворююче значення, що складається в удосконалюванні відомих методів контролю й одержанні нових рішень.
В третьому розділі визначається клас скорочених операцій як основний метод обробки мантис чисел із плаваючою точкою і пропонується узагальнений контроль за модулем, що поширений на скорочені операції.
Операція множення входить до запису числа в нормальній формі і тому присутня в усіх операціях над мантисами. Вона подвоює розрядність результату стосовно операндів, а формати з плаваючою точкою, підтримують, відповідно до теорії помилок, однакову розрядність n для мантис операндів і результатів. Округлення повного 2n-розрядного результату із втратою половини розрядів указує на збитковість обчислень і можливість їхнього скорочення. Підвищення паралелізму обчислень на схемному та системному рівнях до матричних і конвеєрних структур створюють умови для ефективного використання скорочених операцій у приблизних обчисленнях.
У відомому методі скороченого множення матриця кон'юнкцій добутку (МКД) розподіляється на старшу і молодшу частини. Молодша частина - k стовпців - виключається з обчислень, а по старшій частині обчислюється (2n - k)-розрядний зсічений добуток, n старших розрядів якого складають n-розрядний округлений результат (молодші n - k розрядів відкидаються). Величина k n - log2 n визначається з умови збереження точності обчислень.
Стосовно до обробки нормалізованих мантис - операндів
А = А{1 n} 2-n та В = В{1 n} 2-
n визначаються повний
VF = V{1 2 n} 2-2n,
зсічений
VT = V{1 2n - k} 2-(2n-k)
та округлений
VR = V{1 n} 2-n добутки
У порозрядному конвеєрному помножувачі МКД розвертається в часі, що дозволяє скоротити обчислений результат до зсіченого добутку.
Арифметичний зсув, що виконується у додавачі з плаваючою точкою для денормалізації мантис, описується матрицею зсуву, складеної з варіантів зсунутої мантиси, де A - операнд; da - величина зсуву; AF - повний результат; Ash - результат скороченої операції зсуву. Молодша частина матриці зсуву, що позначена затемненням, вилучається з обчислень.
ОП ділення мантис з відновленням та без відновлення залишку скорочення обчислень відбувається на останніх k ітераціях укороченням дільника B на черговий молодший розряд замість подовження діленого-залишку A. Результат скороченого ділення містить округлену частку
C = C{0 n} 2-n
і зсічений залишок
DT = DT{1 n - k} 2-(2n-k)
Скорочення обчислень у бінарних операціях забезпечує багаторазове зменшення кількості відкинутих розрядів (від n до n - k) і помилок у них, що підвищує ймовірності K1 та KT (а також знижує кількість устаткування) у
KМУ = 1 / (1 - 0,5 k2 / n2) і KКУ = 1 / (1 - 0,5 k / n)
разів для матричних і конвеєрних ОП. Підвищується швидкодія в
T = 1 / (1 - 0,5 k / n) разів.
Зі збільшенням точності обчислень, тобто розрядності n, n / k 1 і kМУ, kКУ, T 2.
При багатооперандній обробці даних скорочення обчислень приводить до багаторазового спрощення ОП, підвищення швидкодії, а також збільшення ймовірності kT, що, згідно (5), є одним зі способів зниження ймовірності відбраковування достовірних результатів і підвищення достовірності контролю результатів приблизних обчислень.
Висока ефективність класу скорочених арифметичних операцій для виконання приблизних обчислень визначають його як основний метод обробки мантис чисел у сучасних ОП.
Відомі методи контролю скорочених операцій, що засновані на їх відновленні до повних операцій чи дублюванні, виключають переваги скорочених обчислень і є основною перешкодою до їх поширення.
Розроблений узагальнений метод контролю вирішує проблему скорочених операцій в рамках порогового підходу, і що важливо, використовуючи широко застосований на практиці підхід до контролю за числовим модулем.
Оригінальні інструментальні засоби методу - розбивання МКД на фрагменти - стали основою для виводу основних положень методу.
Визначення 3.1. Фрагмент Vi - частина МКД, що визначається добутком
Vi = sign Vi Аi Вi,
де sign Vi - знак фрагмента Vi, sign Vi = +1, якщо більшість кон'юнкцій розташована в старшій частині МКД, і sign Vi = -1 у противному випадку;
Аi = A{ai.1 ai.2} 2-ai.2 і Вi = b{bi.1 bi.2} 2-bi.2
операнди А та В або їхні частини, що містять розряди з ai.1 по ai.2 та з bi.1 по bi.2, відповідно.
Перше положення методу визначає контрольне співвідношення для перевірки скороченої операції.
Теорема 3.1. Контрольний код зсіченого добутку визначається сумою контрольних кодів фрагментів, що складають старшу частину МКД.
З теореми випливає контрольне співвідношення
КVR = (КАi КBi Кsgi) - КVC,
де КVR, КАi, КBi, Кsgi і КVC - контрольні коди округленого добутку VR, частин Аi, Bi операндів, знаків signVi фрагментів Vi і відкинутих розрядів VC зсіченого добутку, відповідно;
nk - кількість фрагментів, що складають старшу частину МКД.
Визначення 3.2. Граничні елементи - кон'юнкції, що прилягають до лінії перетину МКД на молодшу і старшу частини.
Фрагмент Vi у межах одного рядка МКД може мати пари граничних елементів або один з них, тобто непарний граничний елемент.
Визначення 3.3. Фрагмент Vi, що містить непарний граничний елемент в одному рядку i, називається індексованим, а сам елемент - індексним.
Друге положення методу визначає нижню межу кількості доданків при обчисленні контрольного коду результату скороченої операції і умову її досягнення.
Теорема 3.2. Старша частина МКД розбивається на мінімальну кількість фрагментів
nk = k + 1
у тому і тільки в тому випадку, якщо всі фрагменти є індексованими.
З теореми 3.2 випливає лінійна залежність витрат устаткування ЗК від розрядності n у частині обробки контрольних кодів.
Визначення 3.4. Розбивання МКД, що складене з індексованих фрагментів, називається нормальним.
Контрольні коди операндів і процес їхнього формування визначаються видом розбивання МКД на фрагменти, наприклад
Фрагменти розбивання описуються наступними формулами:
V1 = -А{5 12} B{5 12} 2-24; V2 = А{5} B{11} 2-16;
V3 = -А{7 10} B{7 10} 2-20; V4 = А{7} B{9} 2-16;
V5 = -А{7, 8} B{7, 8} 2-16; V6 = А{9} B{7} 2-16;
V7 = А{5 10} B{5 10} 2-20; V8 = А{11} B{5} 2-16;
V9 = А{1 12} B{1 12} 2-24.
Визначення 3.5. Фрагмент Vi називається центрально-симетричним, якщо Аi = Вi. Фрагменти Vi і Vj складають пари взаємно-симетричних фрагментів, якщо Ai = Bj і Bi = Aj, що позначається як Vi = Vj* чи Vj = Vi*.
Визначення 3.6. Розбивання, що не змінюється при зміні місць співмножників, називається симетричним.
Симетричне розбивання складається з центрально-симетричних і пар взаємно-симетричних фрагментів, наприклад, розглянуте розбивання.
Визначення 3.7. Розрядність частини Аi або Вi фрагмента Vi називається розміром фрагмента за цією утворюючою, відповідно LAi або LВі, а при LAi = LВі, - розміром Li фрагмента Vi. Наприклад, L1 = 8, L7 = 6, L3 = 4, L5 = 2, L8 = 1.
Контрольні коди КАi, КВi частин операндів Аi, Вi розподіляються на складені та обчислені.
Визначення 3.8. Контрольний код КАi (Квi) частини операнда Аi (Вi) називається складеним, якщо LAi L (LВi L), де L - довжина повного контрольного коду за модулем, а в противному випадку - обчисленим.
Третє положення методу випливає з необхідності контролю операндів і визначає безвитратний спосіб обчислення контрольних кодів частин операндів, що формулюється наступною теоремою.
Теорема 3.3. Обчислені контрольні коди частин операндів для нормального розбивання МКД формуються в процесі згортки операндів, що виконується для їхнього контролю.
З теореми 3.3 випливає лінійна залежність витрат устаткування ЗК від розрядності n у частині формування контрольних кодів.
Контрольне співвідношення та спосіб формування контрольних кодів операндів визначають структуру ЗК для однотактного матричного помножувача мантис зі скороченим виконанням операції.
Схема ЗК містить блоки контролю БКА, БКВ та БКV операндів А, В та результату, а також контрольний блок КБ, що складається з вузлів множення ВМ, вирахування ВВ і формувачів контрольних кодів ФКV, ФКC.
Операнди А, В та їх вхідні контрольні коди КА, КВ перевіряються в блоках БКА, БКВ на порівнянність за модулем, визначаючи коди контролю КА, КВ правильності операндів. У процесі перевірки також формуються контрольні коди КAi та КВi частин Ai та Вi операндів. По них у вузлах ВМ та ФКV обчислюються контрольні коди фрагментів KVi та їхня сума KVT - контрольний код зсіченого добутку. Формувач ФКC обчислює контрольний код KVC відкинутих розрядів VC зсіченого добутку, а вузол ВВ віднімає KVC з KVT, утворюючи контрольний код КVR округленого добутку. Результат VR та обчислений для нього контрольний код КVR порівнюються за модулем в блоці БКV, визначаючи код контролю КV правильності результату.
Контроль ЗК здійснюється шляхом побудови самоперевіряємої схеми.
Теорема 3.4. Схема ЗК є самоперевіряємою в класі константних одиночних несправностей для будь-якого непарного модуля M.
Обчислення контрольних кодів частин операндів може виконуватися за прямим (у напрямку збільшення розрядностей частин операндів) і зворотним порядками - вирахуванням розрядів із вхідних контрольних кодів операндів. Забезпечуване методом спільне використання засобів контролю операндів та результату скорочених обчислень створює додаткові можливості економії устаткування і поліпшення часових параметрів контрольних обчислень.
Використання методу щодо контролю різних ОП ґрунтується на виборі розбивання МКД та використанні визначеного порядку формування контрольних кодів відповідно до особливостей даного класу ОП.
Для матричного помножувача мантис запропоновані нормальні симетричні розбивання МКД із постійним та змінним кроками згортки для вкладених та зовнішніх фрагментів з прямим та зворотним порядками обчислення контрольних кодів частин операндів. Симетричність розбивань МКД дає ефективне рішення для окремого випадку множення - піднесення у квадрат.
Для конвеєрного помножувача мантис розбивання МКД на фрагменти
Vi = A{1]k/2[}B{n+1-i}2-(2n-k) для i = 1]k/2[;
Vi = A{n-k+i-1}B{1n-i+1}2-(2n-k) для i = Int (k/2)+2k+1;
Vi = A{1k}B{1k}2-(2n-k) для i = k/2+1, k - парне число;
Vi = A{1k}B{1k}2-(2n-k)+1 для i = k+2, k - непарне число,
зі зворотним порядком обчислення контрольних кодів частин операндів забезпечують побудову схеми ЗК в умовах безупинної обробки даних.
Для паралельного арифметичного зсувача запропоновані розбивання матриці зсуву на фрагменти забезпечують додаткову економію устаткування чи додатковий виграш у швидкодії
Суттєва економія часу забезпечується методом контролю при використанні арифметичного зсувача для обробки мантис доданків у складі додавача із плаваючою точкою - сполучається в часі обчислення контрольних кодів Каі в блоці БКА й обробка порядків a та b
Для однотактних матричних ОП ділення з відновленням та без відновлення залишку структурна схема ЗК містить блоки контролю БКА, БКВ, формувачі контрольних кодів ФКс і ФКD, контрольні блоки КБ1 і КБ2, що обчислюють
КVT1 = KA - КDT і КVT2 = (КВі КСі signVi),
Розбивання МКД на фрагменти вибирається, виходячи з економії витрат часу на контроль з урахуванням ітераційного характеру основних обчислень.
Метод забезпечує контроль операндів, результату та ЗК, виконуючи виявлення всіх помилок, що викликаються константними одиночними несправностями в матричних ОП, по найбільш простому модулю три. Для порозрядних конвеєрних ОП помилки виявляються в залежності від тривалості прояву несправності. Зі зменшенням тривалості до одного такту ймовірність виявлення за модулем M збільшується від 1 - 1 / M до одиниці.
Розроблений метод забезпечує високу достовірність контролю завдяки суттєвому зменшенню ефекту відбраковування достовірних результатів через помилки у відкинутих розрядах обчислюваного результату. Верхня оцінка знижки ймовірності відбраковування достовірних результатів становить
D = (2n - k) / (n - k) разів
що для n = 32 і n = 64 складає D = 7,4 і D = 11,7.
Для однотактних ОП метод контролю знижує витрати устаткування на контроль з квадратичного рівня до лінійної залежності від розрядності операндів, а витрати часу - до логарифмічної залежності. Усе це створює умови для широкого застосування скорочених операцій як основного методу обробки мантис чисел з багаторазовим зниженням витрат устаткування і підвищенням швидкодії та продуктивності сучасних ОП.
В четвертому розділі пропонуються методи ФД, що використовують ПРК для спрощення ЗК і підвищення достовірності контролю результатів.
Методи контролю за забороненими значеннями використовують природну інформаційну надмірність (ПІН), властиву результатам арифметичних операцій.
Контроль матричного помножувача базуєтья на таких твердженнях.
Твердження 4.1. Прості числа з розрядністю, більшою за n, а також кратні їм числа не є добутками n-розрядних чисел.
Твердження 4.2. Двійкові числа виду k , де
= , k = 1 2 n - 1
складають код G(n, n, …, n) з (g - 1)-кратним повторенням за винятком нульового вектора.
В основу методу покладене виявлення помилок шляхом виявлення заборонених значень добутку як чисел виду k , де - просте число, аналізом коду з повторенням.
Метод виконує перевірку співмножників Ai{1 n}, i = 1 g, на рівність нулю і добутку V{1 g n} на заборонені значення k .
Помилка виявляється, якщо виконується тільки одне з наступних двох умов:
(A1{1 n} = 0) & (A2{1 n} = 0) &... & (Ag{1 n} = 0);
(V{1 n} = V{n + 1 2 n}) &... & (V{n (g - 2) + 1 n (g - 1)} = V{n (g - 1) + 1 g n}).
Схема ЗК містить два блоки, роздільно формуючі розряди коду контролю Е{1, 2},
Е{1} = (Ai{1 n} 0);
Е{2} = (V{n (i - 1) + 1 n i} = V{n i + 1 n (i + 1)}),
Ймовірність виявлення помилки складає
PОБН = (g + 1) 2 - n.
Найбільше практичне значення мають випадки використання методу контролю для g = 2 і розрядностей ОП n = 8 та n = 16, що поширені у ОТ. Для них PОБН = 3 2 - 8 і PОБН = 3 2 - 16.
У порівнянні з показниками цілочисельного контролю за модулем з ймовірністю PОБН = 0,9 розроблений метод знижує показник недостовірності контролю результатів DН КР (t) в 7,5 разів та спрощує ЗК у 9,3 разів.
...Подобные документы
Розробка засобів функціонального діагностування обчислювальних пристроїв із плаваючою точкою. Алгоритми та програми синтезу вузлів контрольного блоку пристрою контролю по модулю три матричного помножувача мантис із скороченим виконанням операції.
курсовая работа [265,5 K], добавлен 12.03.2013Методика обґрунтування раціональної сукупності методів і засобів технічного діагностування складних систем озброєння, що задовольняє задані вимоги до систем технічного діагностування в цілому. Пошук дефекту при мінімальних витратах на реалізацію методів.
статья [28,2 K], добавлен 14.12.2010Підвищення продуктивності мікропроцесорних систем. Основні напрями вдосконалення архітектури сучасних обчислювальних систем. Багатоядерні МП та багатопроцесорні МПС. Конвеєризація та розпаралелювання обчислень. Суперкомп'ютери - надвисоки швидкості.
лекция [408,1 K], добавлен 13.04.2008Дослідження методу сплайнів для вирішення задачі інтерполяції. Вибір методів технічних та інструментальних засобів вирішення задачі, їх алгоритми. Розробка логічної частини програми, результати обчислень. Розв’язання задачі в пакетах прикладних програм.
курсовая работа [278,5 K], добавлен 03.12.2009Мова VHDL. Створення проекту для моделювання цифрових і аналогових схем. Синтез і моделювання комбінаційних пристроїв, заданих в табличній формі, за допомогою системи Active-HDL 6.1. Створення ієрархічних структур при проектуванні складних пристроїв.
реферат [287,3 K], добавлен 14.02.2009Реалізація обчислювальної задачі для кластера при використанні функціонального підходу у програмуванні задач - технології DryadLINQ. Аналіз ефективності роботи DryadLINQ. Обрахунок інтегралу методом Монте-Карло в якості прикладу обчислюваної задачі.
курсовая работа [619,7 K], добавлен 20.04.2011Розробка криптопротоколу двосторонньої автентифікації з використанням цифрового підпису і випадкових чисел. Розрахунок технічних характеристик: часу реалізації криптопротоколу, складності апаратури для обчислень і ємності пам'яті для роботи процесора.
курсовая работа [1,4 M], добавлен 15.02.2012Серверна мова програмування PHP. База даних MySQL. Мова та стандарти XML. Рівні та способи взаємодії засобів розробки. Засоби трансформації XML. Розробка інтернет-додатку з використанням PHP, MYSQL, XML. Розрахунок трудомісткості створення системи.
дипломная работа [1,8 M], добавлен 19.08.2012Концепції об'єктно-орієнтованого програмування. Методи створення класів. Доступ до методів базового класу. Структура даних, функції. Розробка додатку на основі діалогових вікон, програми меню. Засоби розробки програмного забезпечення мовами Java та С++.
курсовая работа [502,5 K], добавлен 01.04.2016Тестування і діагностика є необхідним аспектом при розробці й обслуговуванні обчислювальних мереж. Компанія Fluke Networks є лідером розробок таких приладів. Такими приладами є аналізатори EtherScope, OptіVіew Fluke Networks, AnalyzeAir та InterpretAir.
реферат [370,5 K], добавлен 06.01.2009Ескізний проект програмного забезпечення для 3D-навігації для мобільних пристроїв під управління ОС Android. Розробка прототипу інтерфейсу. Технічний проект програмного забезпечення. Створення діаграми класів, аналізу, розгортання та кооперацій.
курсовая работа [880,5 K], добавлен 09.01.2014Аналіз роботи обчислювальних пристроїв, побудованих за RISC-архітектурою. Центральний процесор і внутрішня пам'ять мікроконтролерів AVR компанії Atmel. Принцип побудови AVR-контролера ATtiny2313: складові частини; програмування пам'ятi мовою Асемблер.
курсовая работа [1,1 M], добавлен 27.07.2015Оцінювання та засоби підвищення надійності інформаційних технологій протягом усього життєвого циклу програмного забезпечення на основі негомогенного пуасонівського процесу та обчислення її параметрів, з урахуванням сучасних тенденцій тестування.
автореферат [52,0 K], добавлен 10.12.2010Призначення менеджеру пристроїв. Обґрунтування вибору мови програмування. Розробка структурної схеми і опис діалогового інтерфейсу програми. Блок-схема програмного додатку, основні функції і алгоритм його роботи. Методики і інструкція його тестування.
курсовая работа [3,4 M], добавлен 17.11.2014Питання, моделі та десять технологічних тенденцій розвитку мережних розподілених обчислень. "Візантійські відмови" і проблема вибору лідера. Рівні архітектури протоколів Грід і їх відповідність рівням архітектури протоколів Інтернет. Структура GRAM.
курс лекций [1,4 M], добавлен 25.08.2014Синтез логічних пристроїв з великою кількістю виходами. Особливості побудови реальних логічних пристроїв. Використання логічних елементів: що мають надлишкове число або недостатню кількість входів. Подання й мінімізація функції за допомогою карт Карно.
лекция [95,3 K], добавлен 13.04.2008Клавіатура як один з найважливіших пристроїв комп’ютера, її призначення та конфігурація. Основні види клавіатури, їх характеристика та відмінні риси, порядок і правила діагностування. Методика пошуку несправностей і ремонту. Побудова миші та трекболів.
курсовая работа [182,2 K], добавлен 24.05.2009Принципи побудови розподілених обчислювальних мереж, зокрема GRID-систем. Існуючи способи планування задач в них. Детальний аналіз Moab Workload Manager, недоліки алгоритму. Розроблення програмного забезпечення щодо більш ефективної його роботи.
дипломная работа [1,7 M], добавлен 13.04.2014Демонстрування можливостей використання калькулятора для матриць. Розробка програми, яка може бути використана для виконання основних арифметичних операцій над матрицями та для перевірки обчислень у розрахункових роботах. Алгоритм створення програми.
курсовая работа [43,2 K], добавлен 12.12.2009Використання ітерацій для обчислення приблизних значень величин. Розробка ітераційних алгоритмів з перевіркою правильності введення даних. Побудова блок-схеми і програмування мовою Turbo Pascal обчислення значення функції, розкладеної в степеневий ряд.
лабораторная работа [197,2 K], добавлен 16.12.2010