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

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

Одеський Національний політехнічний університет

УДК 681.325.5

Метод та засоби логарифмічного контролю

обчислювальних пристроїв для обробки

мантис чисел із плаваючою точкою

05.13.05 ѕ Елементи та пристрої обчислювальної техніки

та систем керування

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Мохамад Зуда

Одеса ѕ 2003



Дисертацією є рукопис.

Робота виконана в Одеському Національному політехнічному університеті міністерства освіти і науки України.

Науковий керівник кандидат технічних наук, доцент Дрозд Олександр Валентинович, Одеський Національний політехнічний університет, професор кафедри “Комп'ютерні інтелектуальні системи та мережі”

Офіційні опоненти:

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

кандидат технічних наук, доцент Павленко Віталій Данилович Одеський Національний політехнічний університет, доцент кафедри “Комп'ютеризовані системи управління”

Провідна установа Інститут проблем реєстрації інформації НАН України, м. Київ

Захист відбудеться “ 6 ” березня 2003 року о 1330 годині на засіданні спеціалізованої вченої ради Д 41.052.01 Одесьского Національного політехнічного університету за адресою: 65044, м. Одеса, пр. Шевченка, 1.

З дисертацією можна ознайомитись у бібліотеці Одеського Національного політехнічного університету за адресою: 65044, м. Одеса, пр. Шевченка, 1.

Автореферат розісланий “ 6 ” лютого 2003 року.

Вчений секретар

спеціалізованої вченої ради Ямпольський Ю.С.



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

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

Дисертація присвячена питанням робочого діагностування сучасних обчислювальних пристроїв для обробки мантис чисел із плаваючою точкою. Розроблено метод логарифмічного контролю арифметичних операцій над мантисами в матричних обчислювальних пристроях. Виявлено природну інформаційну збитковість форматів із плаваючою точкою. Визначено контрольний код мантиси та контрольні співвідношення для перевірки операцій зсуву, додавання, множення та ділення мантис. Розроблено засоби логарифмічного контролю обчислювальних пристроїв для обробки мантис. Складність контрольних обчислень знижена в 1,5 ѕ 6 разів у порівнянні з контролем за модулем. Метод виключає виявлення помилок у розрядах, що відкидаються при округленні мантис чисел.

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



Mohamad Zoudeh. Method and means of logarithm checking for computing devices processing mantissas of floating-point numbers. ѕ Manuscript.

The thesis for obtaining candidate of science degree on speciality 05.13.05 ѕ Elements and devices of computer engineering and control systems. ѕ Odessa national polytechnic university. Odessa, 2003.

Dissertation is devoted to questions of on-line testing for modern computing devices processing mantissas of floating-point numbers. The logarithm checking method for arithmetical operations with mantissas in iterative array computing circuits is designed. The natural information redundancy of floating-point formats is found. This is used for definition check code of mantissa and checked equations for verify of shift, addition, multiplication and division with mantissas. The means of the logarithm checking for computing circuits processing mantissas are designed. The check computation complexity is reduced for 1,5 ѕ 6 times in comparison with residue checking. The method excludes error detection in the bits restricted in mantissa rounding case.

Key words: computing devices, on-line testing, processing of mantissas for floating-point numbers, logarithm checking



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

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

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

Рост объемов обработки действительных чисел в форматах с плавающей точкой обращает внимание на недостаточную эффективность традиционных методов контроля ѕ по паритету и по модулю. Эти методы обнаруживают ошибки в отбрасываемых разрядах мантисс. При отбрасывании половины разрядов мантисса результата вычислений не содержит ошибок в половине случаев их обнаружения. Этот эффект снижается при сокращенном выполнении операций, но при этом многократно увеличиваются относительные затраты на контроль. Известный логарифмический контроль, разработанный для обнаружения отказов в ВУ с фиксированной точкой, преодолевает эти недостатки. Однако фиксированная точка менее эффективна для обработки действительных чисел. Поэтому исследования посвящены разработке логарифмического контроля ВУ для выполнения операций над мантиссами чисел с плавающей точкой.

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

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

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

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

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

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

Для проверки контрольных соотношений разрабатываются математические модели контрольных вычислений и реализующие их устройства с получением решений, альтернативных по сложности и продолжительности вычислений. Сравнение контрольных кодов левой и правой частей контрольных соотношений выполняется с точностью g = 0, 1, 2. Схемы блока сравнения строятся самопроверяемыми в классе константных одиночных неисправностей, что обеспечивает самопроверяемость разработанных средств логарифмического контроля ВУ.

Ошибки обнаруживаются с вероятностью, которая увеличивается с ростом величины ошибки. Для арифметических сдвигателей денормализации и нормализации мантисс, сумматора, умножителя и делителя мантисс чисел вероятность обнаружения ошибки в разряде j составляет Pсдв д ”

(1 - j / n) 2-1, Pсдв Н ” (1 - j / n) 2-j-1, Pсум ” 2- j (1 - j / n), Pум = 0,58 Ч 2- j, PДЕЛ = 0,29 Ч 2- j.

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

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

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



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

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

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

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

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

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

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

ѕ доведено технічну доцільність логарифмічного контролю ОП для обробки мантис чисел із плаваючою точкою;

ѕ розроблено модель подання мантис у форматах із плаваючою точкою, що виявляє природну інформаційну збитковість форматів із плаваючою точкою;

ѕ визначено контрольний код мантиси, що враховує виявлену природну інформаційну збитковість форматів із плаваючою точкою;

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

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

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

Об'єкт досліджень ѕ ОП для обробки мантис чисел із плаваючою точкою.

Предмет досліджень ѕ метод і засоби логарифмічного контролю для робочого діагностування ОП, що виконують обробку мантис чисел.

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

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

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

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

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

Вперше розроблено модель обчислень та на її підставі самоперевіряєма (у класі константних одиночних несправностей) схема блоку порівняння контрольних кодів мантис при припустимому розходженні кодів на g = 0, 1, 2, що забезпечує самоперевіряємість розроблених засобів логарифмічного контролю.

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

Результати роботи впроваджені в навчальний процес в Одеському Національному політехнічному університеті на кафедрі “Комп'ютерні інтелектуальні системи та мережі”.

Особистий внесок здобувача полягає в розробці логарифмічного контролю операцій над мантисами в ОП із плаваючою точкою.

Дисертантом виявлена природна інформаційна збитковість форматів із плаваючою точкою [6], визначено контрольний код мантиси [8], запропоновані альтернативні рішення по формуванню контрольних кодів мантис [2, 4], виведені контрольні співвідношення й отримані моделі контрольних обчислень для перевірки цих співвідношень у пристроях додавання [3], множення [4] та ділення [5] мантис чисел.

Апробація роботи. Результати роботи доповідалися й обговорювалися на другій міжнародній науково-практичній конференції “Сучасні інформаційні й електронні технології” (м. Одеса, 2001 р.), міжнародної конференції по управлінню “Автоматика” (м. Одеса, 2001 р.), 15-й міжнародній школі-семінарі “Перспективні системи управління на залізничному, промисловому та міському транспорті” (м. Алушта, 2002 р.).

Публікації. По темі дисертації опубліковано 8 друкованих праць, у тому числі 5 статей у збірниках наукових праць, згідно переліку ВАК України, і 3 матеріалів і тез конференцій.

Структура дисертації. Дисертаційна робота складається з вступу чотирьох глав, висновків і чотирьох додатків. Повний обсяг дисертації ѕ 182 стор., з них додатків ѕ 18 стор., список літератури ѕ 7 стор. Дисертація містить 48 малюнків, 10 таблиць і посилання на 87 використаних джерел.

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

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

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

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

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

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

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

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

Додавання чисел із плаваючою точкою

Апл = А Ч 2а, Впл = В Ч 2b; Sпл = Апл + Впл; Sпл = S Ч 2s

передбачає вирівнювання порядків а та b, обчислення максимального з них s = max (а, b) і вирівнюючих різниць



da = s - a, db = s - b.

Над n-розрядними мантисами

А = А{1 ё n} Ч 2-n і В = В{1 ё n} Ч 2-n

виконуються операції арифметичного зсуву відповідно на da та db позицій праворуч:

Азсв = А Ч 2-da, Bзсв = B Ч 2-db,

а також додавання зрушених мантис

S = Азсв + Bзсв.

Нормалізація мантиси

S = S{0 ё n} Ч 2-n

результату виконується зсувом ліворуч на d* = 0 ё n позицій.

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

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

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

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

Дійсні числа, як правило, представляються у форматах даних із фіксованою та плаваючою точкою, що описують числа з використанням мантиси m, порядку p чи характеристики і прийнятою за замовчуванням основою q позиційної системи числення по формулі

A = m Ч q p

Для плаваючої точки мантиса m подається у нормалізованому вигляді:

Q - 1 Ј m < 1.

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

Таким чином, до основних положень, що визначили вибір напрямку досліджень, варто віднести:

ѕ зростання значення обробки дійсних чисел;

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

ѕ недостатня ефективність традиційних методів контролю по паритету і по модулю для робочого діагностування ОП із плаваючою точкою у частині мантис чисел;

ѕ можливості логарифмічного контролю підвищити ефективність робочого діагностування ОП із плаваючою точкою.

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

Загальна методика проведення дисертаційних досліджень містить:

ѕ розробку моделі запису мантис чисел у розрядній сітці для виявлення природної інформаційної збитковості форматів із плаваючою точкою;

ѕ визначення контрольного коду мантиси числа і розробку математичної моделі та пристроїв його формування;

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

ѕ розробку моделей процесів виявлення помилок, розробку й оцінку засобів контролю ОП.

В третьому розділі викладено метод логарифмічного контролю ОП для обробки мантис чисел. Він ґрунтується на природній інформаційній збитковості форматів із плаваючою точкою.

Запропоновано модель подання мантис у розрядній сітці форматів із плаваючою точкою що виділяє інформативну частину AK = A{n1 +1 ё n} та виявляє природну інформаційну збитковість у полі A{2 ё n1}, розташованому між старшим значущим розрядом A{1} та наступною значущою цифрою

A{n1 + 1}, n1 Ј n

На основі виявленої збитковості визначається контрольний код мантиси числа:

Ka = E (log 2 aK) + n + 1 для aK > 0; Ka = 0 для aK = 0, де aK = a - 2-1 ѕ

контрольна частина мантиси a; 2-1 Ј A < 1. Контрольний код має розрядність r = ] log 2 n [.

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

У першій дії виконується послідовно-групове обчислення коду Y{2 ё n} по формулах

Y{j} = A{2} Ъ ... Ъ A{ j};

Y{(u - 1) (i + 1) + j} = Y{i (u - 1)} Ъ A{i Ч u + 2} Ъ ... Ъ A{i Ч u + j};

де u ѕ максимальний коефіцієнт об'єднання по АБО;

j = 2 ё u ѕ номер розряду в групі;

i = 0 ё ] (n - 2) / (u - 1) [ - 1 ѕ номер поточної групи, i (u - 1) + j Ј n.



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

u ( u - 1) / (4 u - 6) разів

Розряди коду Y {2 ё n} визначаються по наступному алгоритму:

begin

z = u - 2; u1 = u - 3; i = 3;

Y{2} = A{2};

while z і 0 do

for j = i to i + z - 1 do Y{j} = Y{j - 1} Ъ A{j};

Y{i + z} = Y{i - 1} Ъ A{i} ... Ъ A{i + z};

i = i + z + 1;

if n - i Ј (u - 1) u / 2 + u1 then z = z - 1;

end;

end.

Отримано оцінки складності (по Квайну) та тривалості обчислень, що дозволяють вибирати найкращі рішення серед рішень, що є альтернативними за цими показниками.

Підрахунок кількості одиниць у коді Y{2 ё n} визначає розряди контрольного коду KA{1 ё r} по формулі

KA{i} = (Y{2i-1 Ч (n - 2j + 2} Щ Ш Y{2i-1 Ч (n - 2j + 1}) Ъ Y{2i} Ч ni,

де i = 1 ё r; yi = E ((n - 1) / 2i);

j = 1 ё yi; ni =((n - 1) / 2i-1) mod 2.

Теорема 1. Усі розряди контрольного коду KA{1 ё r} вибираються чи з перших

Y{2} ё Y{n - 2 r-1 + 1}

чи з наступних

Y{n - 2 r-1 + 2} ё Y{n} розрядів коду Y{2 ё n}.

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

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

Контрольний код мантиси, поданої в оберненому коді, формується після її перекладу в прямий код AУІ умовним інвертуванням (інвертуванням при її знаку Зн = 1). Для додаткового коду мантиси отриманий у такий спосіб контрольний код може бути збільшений на одиницю додаванням розряду

z ДП = Зн ЩШ AУІ {i} ЩШ AУІ {i + 1}.



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

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

Теорема 2. Нехай A 1 K, …, A i K, …, A m K ѕ контрольні частини мантис A 1, …, A i, …, A m і 0, тоді для контрольної частини

S K =

мантиси S контрольний код KS = max (KA1, …, KA i, …, KA m) + g, де g = 0, 1, …, ] log 2 m [; KA1, …, KA i, …, KA m ѕ контрольні коди мантис A 1, …, A i, …, A m.

Визначено умови

kR < n - j + 1 і kR = n - j + 1

виявлення помилок двох видів: викривлення незначущих і значущих цифр мантиси результату R. Умови реалізуються при виникненні помилок відповідно в полі збитковості та на межі контрольної частини мантиси, що призводить до різних значень контрольних кодів KL та KR мантиси R{1ёn} результату.

Ймовірність виявлення помилок



P = V / V0,

де V ѕ кількість випадків виявлення помилок; V0 ѕ загальна кількість випадків виявлення і невиявлення помилок. Величина V оцінюється кількістю різних значень мантиси, при яких виконується умова виявлення помилки, а величина V0 ѕ кількістю різних значень мантиси.

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

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

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

n - d = KAзсв

величину зсуву d для одержання контрольного коду KAзсв зсунутої мантиси, як числа з фіксованою точкою.

Ймовірність виявлення помилок у розряді j результату визначається з умови рівної ймовірності різних значень величини зсуву d та знака мантиси і складає

Pзсв д = (n - j + 2) / (2n + 2).

Складність контрольних обчислень



Oзсв д = 8n + 8r - 19

менше в 4 рази складності схем контролю по модулю три, виконаного на 2,5 n повних додавачах складністю q = 14.

Логарифмічний контроль арифметичного зсувача на d* позицій для нормалізації мантис чисел визначає контрольний код KAзсв н зсунутої мантиси Aзсв н за мантисою операнда А{0 ё n} шляхом виключення першого розряду її контрольної частини. Розряд виключається логічним множенням розрядів А0{2 ё n} прямого коду мантиси А0{1 ё n} операнда на розряди отриманого для неї коду Y{1 ё n - 1}, що зміщаються на одну позицію праворуч, по формулі

А'{i} = А0{i} Щ Y{i - 1}, i = 2 ё n.

Контрольне співвідношення порівнює контрольні коди мантиси результату по формулі

KAзсв н = KА' + d*.

Ймовірність виявлення помилки

Pзсв Н = (1 - j / (2n + 2)) 2-j.

Складність контрольних обчислень

O зсв н = 16 n + 21 r - 26

у 1,5 рази простіше контролю по модулю три, що вимагає більш ніж 2n повних додавачів.

Для додавача із плаваючою точкою доведена теорема.

Теорема 3. Нехай Ka, Kb і KS ѕ контрольні коди мантис доданків A і 0, B і 0 і суми S, а z ѕ знак різниці а - b, що обчислюється при одержанні порядку s результату, тоді виконується наступне контрольне співвідношення

KS* + b = KS,

Де KS* = max (Ka, n - db) для z = 0;

KS* = max (Kb, n - da) для z = 1;

b = 0, 1.

Доказ випливає з методу виконання додавання і теореми 2.

Урахування знаків Зн A, Зн B і Зн S доданків і суми виконується шляхом перейменування контрольних кодів мантиси суми й одного з доданків. При цьому за знак суми використовується Зн Sа№ b = Ш S{1}.

Роль контрольних кодів зрушених мантис доданків виконують коди

na = n - da; nb = n - db.

Для перейменованих контрольних кодів виконується

max (KbR, KAR) + b = KSR.

Перейменовані контрольні коди KAR, KBR і KSR доданків і суми визначаються, виходячи з табл. 1, по наступних формулах:

KAR = KA Щ UA - A Ъ KB Щ UA - B Ъ na b Щ UA - n;

KBR = KB Щ UB - B Ъ na b Щ UB - n Ъ KS Щ UB - S;

KSR = KA Щ US - A Ъ KB Щ US - B Ъ na b Щ US - n Ъ KS Щ US - S,

де ЗнAB = Зн A Е Зн B; ЗнBS = Зн B Е Зн Sа№ b; ЗнAS = Зн A Е Зн Sа№ b;

UA - A = Ш z Щ Ш ЗнBS; UA - B = z Щ ЗнBS; UA - n = Ш(UA - A Ъ UA - B );

UB - B = z Щ Ш ЗнAB; UB - S = ЗнAB; UB - n = Ш z Щ Ш ЗнAB;

US - A = Ш z Щ ЗнBS; US - B = z Щ ЗнAS; US - S = Ш ЗнAB;

US - n = UAB Ъ Ш z Щ ЗнAB; na b = z Щ na Ъ Ш z Щ nb.

Блок порівняння контрольних кодів мантис результату. Для порівняння кодів ks* і Ks з точністю b обчислюється код різниці

C{1 ё r} = ks*{1 ё r} + Ш Ks{1 ё r}.

При відмінності порівнюваних кодів ks* та Ks на b обчислюються нульовий чи одиничний (складений із всіх одиниць) набори. Ці набори ідентифікуються шляхом попарного порівняння розрядів коду C{1 ё r} з інверсією одного з розрядів пари. Для цього використовуються самоперевіряємі (у класі константних одиночних несправностей) вузли порівняння на чотири входи, що стискають дві пари взаємо-інверсних розрядів в одну пару. Однак такий відомий підхід не забезпечує виконання на двох робочих наборах умови самотестування вузлів порівняння і відповідно їхньої самоперевіряємості. Для побудови самоперевіряємої схеми блоку порівняння окремі пари, наприклад, C{i} та C{i + 1}, перетворюються на елементах нерівнозначності з використанням додаткових розрядів xi, i = 1 ё r - 2 по формулах

C*{i} = C{i} Е xi;

C*{i + 1} = C{i + 1} Е xi.



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

У ланцюговому з'єднанні вузлів порівняння використовується один додатковий розряд x1 для перетворення першої пари розрядів коду C{1 ё r}.

Для прискорення обчислень запропоновані також альтернативні рішення з пірамідальною структурою блоку порівняння і з реалізацією в два рівні елементів І, АБО, що використовують

(r - 1) / 2

r - 2 додаткових розрядів, відповідно.

Помилки в розряді j мантиси суми виявляються із ймовірністю

Pсум = 1,12 Ч 2 - j ( n - j + 0,33) / (n + 1).

Складність пристрою для контролю додавача мантис чисел O СУМ =18 n + 32 r - 7 простіше контролю по модулю три в 2 ё 2,5 рази для розрядності n = 8 ё 32.

Контроль помножувача мантис чисел Контрольне співвідношення, що зв'язує контрольні коди мантис співмножників і добутку визначається наступною теоремою.

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

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

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

Спроектовано формувачі контрольних кодів мантис, поданих у прямому, оберненому і додатковому кодах, для коефіцієнта об'єднання по входах u = 2 ё 5, при послідовно-груповій організації обчислень і при послідовному з'єднанні елементів у групах.

Проектування виконано на ліцензійному програмно-апаратному комплексі Xilinx Foundation Series з використанням програмувальних логічних інтегральних схем FPGA ХС4000 фірми Xilinx у рамках договору “про співпрацю з розробки обчислювальних пристроїв для цифрової обробки сигналів у системах телекомунікації”, що укладений між Одеським Національним політехнічним університетом й Українським науково-дослідним інститутом радіо і телебачення.

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

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

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

Наукові результати роботи використовуються в навчальному процесі Одеського Національного політехнічного університету в курсі лекцій по дисципліні “Діагностика комп'ютерних систем”, що читається студентам спеціальності 7.091501 на кафедрі “Комп'ютерні інтелектуальні системи та мережі”.



ВИСНОВКИ

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

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

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

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

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

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

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

5. Розроблено логарифмічний контроль додавача мантис чисел. Отримано контрольне співвідношення, модель виконуваних у ньому контрольних обчислень і реалізуючі їх засоби контролю, що простіші, ніж при контролі по модулю в 2 ё 2,5 рази.

6. Розроблено логарифмічний контроль помножувача мантис чисел. Доведено контрольне співвідношення і розроблена модель обчислень для його перевірки, а також пристрій контролю, що для множення в прямому і додатковому коді простіше, ніж при контролі по модулю в 6 та 3 разів.

7. Розроблено логарифмічний контроль поділювача мантис чисел. Доведено контрольне співвідношення і розроблена реалізуюча його модель обчислень, а також пристрій контролю, що простіший, ніж при контролі по модулю в 3 рази.

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

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

10. Спроектовано формувачі контрольних кодів мантис, поданих у прямому, оберненому і додатковому кодах, на програмувальних логічних інтегральних схемах FPGA ХС4000 фірми Xilinx та виділені кращі рішення для коефіцієнта об'єднання по входах u = 4. Правильність формування контрольних кодів підтверджено функціонально-логічним моделюванням. Наукові результати роботи використовуються в навчальному процесі Одеського Національного політехнічного університету.

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

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



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

1. Мохамад Зуда. Логарифмический контроль операции арифметического сдвига в устройствах с плавающей точкой // Тр. Одес. политехн. ун-та. ѕ Одесса, 2001. ѕ Вып. 2 (14). ѕ С. 93 ѕ 95.

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

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

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

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

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

7. Мохамад Зуда. Логарифмический контроль вычислительных устройств // Тр. второй международ. научно-практической конференции “Современные информ. и электрон. технологии. ѕ Одесса, 2001. ѕ С. 79.

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

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

...