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

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

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

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

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

Известная структурно-временная избыточность в форме пассивного запаса времени контроля (ПЗВК) позволяет обнаруживать неисправность в течение некоторого времени - интервала ПЗВК. При вычислении приближенного результата ПЗВК распространяется на каждый неверный разряд как время, в течение которого результат остается достоверным при накоплении ошибок. Такое ПЗВК зависит от веса разряда. Наличие ПЗВК снижает вероятность обнаружения ошибки, необходимую для выявления недостоверного результата. Существуют и другие составляющие ПЗВК, которые снижают вероятность обнаружения ошибки для отдельных сегментов или всех разрядов результата. Обнаружение ошибки с большей вероятностью происходит до завершения интервала ПЗВК, т.е., результат является достоверным, а ошибка - несущественной. Метод рабочего диагностирования, не учитывающий ПЗВК, имеет низкую достоверность.

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

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

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

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

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

– досліджено особливості організації та функціонування сучасних обчислювальних пристроїв, що складають природні ресурси робочого діагностування, включаючи пасивний запас часу контролю (ПЗЧК);

– одержано оцінки ймовірностей виявлення помилки в сегментах результату та підвищення достовірності контролю наближених результатів за рахунок ПЗЧК;

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

– розроблені вертикальні методи вибору контрольних точок сегмента для забезпечення заданих ймовірностей виявлення помилки в сегментах результату з одержанням простих або швидкодіючиих схем;

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

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

Особистий внесок здобувача полягає в розробці посегментного контролю наближених результатів обробки мантис у однотактних матричних обчислювальних пристроях. Основні результати, що виносяться на захист, одержані пошукачем самостійно та опубліковані в 11 наукових роботах. При цьому роботи [4, 6] опубліковані пошукачем особисто. У роботах [1, 4, 11] виконана постановка задачі на посегментний контроль наближених результатів. Достовірність контролю наближених результатів оцінена в [6, 10]. Способи забезпечення заданих ймовірностей виявлення помилки в сегментах результату запропоновані в роботах [2, 6 - 9]. Методи вибору контрольних точок для сегментів результату розроблені в [4 - 6, 11]. Посегментний контроль розроблений для паралельних арифметичних зсувачів у [2, 3], додавачів у [8], однотактних матричних помножувачів у [5, 7] та поділювачів у [9].

Апробація роботи. Результати роботи доповідалися й обговорювалися на семи міжнародних конференціях: Шостій, Сьомій та Восьмій міжнародних науково-практичних конференціях «Сучасні інформаційні та електронні технології» - СІЕТ'2005, СІЕТ'2006 та СІЕТ'2007 (м. Одеса, 2005, 2006, 2007 р.), Міжнародних конференціях по проектуванню та тестуванню «IEEE East-West Design & Test Conference» - EWDTC'05 та EWDTC'06 (м. Одеса, 2005 р., м. Сочі, 2006 р.), Міжнародній науково-технічній «Гарантоздатні системи, сервіси та технології» (м. Кіровоград, 2007 р.), П'ятій міжнародній науково-практичній конференції «Комп'ютерні системи в автоматизації виробничих процесів» - КСАВП-2007 (м. Хмельницький, 2007 р.).

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

Структура дисертації. Дисертаційна робота складається з вступу чотирьох глав, висновків і додатків. Повний обсяг дисертації - 199 стор., з них додатків 37 стор., список літератури - 10 стор. Дисертація містить 31 рисунок, 18 таблиць і посилання на 111 використаних джерел.

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

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

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

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

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

Достовірність контролю результатів оцінюється за формулою

D = P_В P_С+ (1 - P_В) (P_С - 1), (1)

де P_В - ймовірність виявлення помилки методом контролю;

P_С - ймовірність того, що помилка є суттєвою для достовірності результату.

Для точних даних висока виявляючи здатність традиційних методів забезпечує високу достовірність контролю результатів, бо будь-яка помилка робить точний результат недостовірним: P_С = 1 та D = P_В.

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

Арифметичні зсувачі використовуються для денормалізації операндів та нормалізації результатів. При денормалізації операндів мантиса A зсувається праворуч на величину зсуву B із заповненням звільнених позицій знаковим розрядом A {0}. Розряд i = 1 n зсунутої мантиси визначається за формулою

A_С {i} = A{i - B} для i > B,

A_С {i} = A {0} для i B.

Операція нормалізації виконується зсувом коду A{0 n} мантиси A{0 n} 2-ⁿ - ¹ ліворуч на величину B = b₁ + b₂ - 1 із збереженням n старших розрядів. Розряд нормалізованої мантиси A_Н{1 n} 2-ⁿ визначається як

A_Н {i} = A{i + B{1 ч r} + 1} для i < n - B{1 ч r}.

A_Н {i} = A{i + B{1 ч r} + 1 - n} для n - B{1 ч r} i n.

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

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

Однотактні матричні поділювачі мантис обробляють n-розрядні операнди, що доповнюються нульовими знаковими розрядами до (n + 1)-розрядних діленого А{0 n} та дільника B₀{0 n}. Пристрої мають матрицю з n + 1 строк та n + 1 стовпців операційних елементів для обробки окремих розрядів чисел. Кожна строка виконує одну ітерацію ділення.

Поділювач мантис із відновленням остачі на ітерації i = обчислює різницю діленого цієї ітерації та дільника: S_i{0 n} = А_i{0 n} - B₀{0 n}, а також розряд частки Q_i = S_i{0}. За результат ітерації вибирається різниця S_i{0 n} або ділене А_i{0 n} відповідно при Q_i = 1 та Q_i = 0 за формулою R_i{1 n} = А_i{1 n} Q_i S_i{1 n} Q_i. Результат далі подвоюється і стає діленим наступної ітерації А_i{0 n} = R_i{1 n} . 0.

У поділювачі мантис без відновлення остачі дільник одержує у якості знака розряд частки, що обчислюється на попередній ітерації та подається у додатковому коді: B_Д{0 n} = B₀{0 n} Q_i - ₁ + Q_i - ₁, i > 0, де Q- ₁ = 0. Далі обчислюється результат ітерації S_i{0 n} = А_i{0 n} + B_Д{0 n} і визначається розряд частки Q_i = S_i{0}. Результат подвоюється і стає діленим наступної ітерації А_i{0 n} = S_i{1 n} . 0.

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

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

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

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

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

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

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

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

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

Ймовірність виявлення помилки на сегменті i = оцінюється за формулою P_i = ln 2 / T_{i ПЗЧК}, що витікає з відомої оцінки часу виявлення відмови, де T_{i ПЗЧК} - величина ПЗЧК, що визначена для сегмента i, а z - кількість сегментів результату.

Тоді достовірність контролю сегмента за методом з традиційно великою ймовірністю помилки P_В P_i становить D _i = P_i P_С + (1 - P_В) (1 - P_С), що витікає з (1), де добуток P_В P_С замінений на P_i P_С, бо при P_В > P_i помилка є несуттєвою і виявляється до закінчення інтервалу ПЗЧК, коли результат ще обчислюється достовірним. При P_В = 1 достовірність D _i = P_i P_С.

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

D_{i ПК} = P_i P_С + (1 - P_i ) (1 - P_С ),

а величина підвищення достовірності при P_В = 1 становить

D_{i ПК} = (1 - P_i) (1 - P_С ).

D_ПК = D_ПК - D_МОД = .

Вихідними даними для посегментного контролю є ймовірності виявлення помилок P₁, …, P_i, …, P_z в сегментах i = результату та точність m завдання ймовірностей P_i (кількість розрядів після коми у двійковому поданні).

Ймовірності Pi можуть забезпечуватися різними в сегментах результату такими способами:

– використанням для сегментів методів контролю з різними ймовірностями виявлення помилки;

– введенням різних обмежень на виконання контролю сегмента, наприклад,

– за часом, тобто з різною частотою перевірки сегментів;

– обмеженням множини вхідних слів, на яких контролюється сегмент;

– комбінуванням декількох способів.

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

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

Кількість каналів NT визначається кількістю перевірок N на інтервалі часу контролю T за формулою

NT = ] N / T [ = ] PSUM / PD [,

де PSUM = , T = 2^m, PD - ймовірність виявлення помилки за методом контролю сегмента.

Таблиця 1. Масив P розрядів ймовірностей Pi виявлення помилок

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

Перший вертикальний метод виконується за наступним алгоритмом.

1. Визначається кількість одиниць z_j розрядного зрізу j = 1 масиву P.

2. Обчислюється розрядність адреси функції вибору для обробки розрядного зрізу j за формулою v_j = ] log₂ (z_j - z_j - ₁) [, де z₀ = 0 для j = 0.

3. Визначається вибір сегментів за розрядним зрізом j, використовуючи функцію вибору , що обчислює M _j = x_k для = k:

,

де x_k для k < z_j - множина контрольних точок s_i для сегментів, що мають p_{i j} = 1, а також функції вибору, що відмічені у зрізі j одиницями в додаткових строках; , - адреса функції вибору.

4. Визначаються невикористані позиції x_k функції вибору, що знаходяться в межах z_j k < z_j*.

5. Невикористані позиції x_k заповнюються парами однакових контрольних точок s_i для сегментів, що мають розряди p_{i j+1} = 1 у наступному зрізі j+1, в межах

z_j k < z_j + z_j,

де z_j - кількість таких пар контрольних точок s_i сегментів, що визначається з урахуванням обмеженої кількості z_{j + 1} розрядів p_{i j + 1} = 1 у зрізі j+1,

z_j = Int((K - z_j) / 2) для z_j . z _{j + 1}, j < m, z_j = z _{j + 1} для z_j > z _{j + 1}, j < m,

z_j = 0 для j = m, функція Int( ) - ціла частина числа,

6. Залишені позиції x_k = 0 для k z_j + z_j,

7. Якщо v_j + j > m, то з функції вибору M_j утворюється

j* = Int ((z_j - z_j - ₁) / 2 ^{m + 1} - ^j)

вихідних функцій вибору M_{j d} з розрядністю адреси m + 1 - j, де d = 1 j*, та одна функція вибору M_{j d + 1} з розрядністю адреси ] log₂ (z_j - z_j - ₁ - j* 2 ^{m + 1} - ^j) [.

Якщо v_j + j = m + 1 то функція вибору M_j або функції вибору M_{j d} та M_{j d + 1} є вихідними, тобто їхні результати не належать до аргументів інших функцій вибору і є остаточними щодо вибору контрольних точок сегментів результату.

Якщо v_j + j m, то масив p доповнюється строкою для опису входження функції вибору M_j у функцію вибору одиницею в позиції v_j + j.

Якщо j < m, то j = j + 1 та перехід на пункт 1.

Алгоритм закінчено.

1. Встановлюється кількість заповнених позицій першої функції вибору v_j = 0 для розрядного зрізу j = m.

2. Підраховується кількість одиниць z_j в розрядному зрізі j масиву p, кількість позицій u_j = 2 ^{m + 1} - ^j у функціях вибору, що формуються за зрізом j, та кількість v_j* = u_j - v_j незаповнених позицій у першій з них.

3. Якщо z_j < v_j*, то z_j є кількістю невикористаних одиниць зрізу j, а кількість заповнених за цими одиницями позицій функції вибору збільшується до v_j = v_j + z_j.

Якщо z_j v_j*, то формується функція вибору

,

де - множина раніше заповнених позицій функції вибору;

- множина з v_j* контрольних точок s_i для сегментів, що мають p_{i 1} = 1;

C _{m + 1} - _j = c_m, ..., c_j.

За кожними u_j із залишених z_j* = z_j - v_j* одиниць розрядного зрізу j масиву p формується чергова вихідна функція вибору

,

де j* = 1 d, d = Int ( z_j* / u_j);

- контрольні точки s_i сегментів, що мають в масиві p множини з u_j розрядів p_{i j} = 1.

Невикористані одиниці зрізу j вказують на контрольні точки сегментів для заповнення позицій наступної функції вибору. Їхня кількість v_j = z_j* - с_j d.

4. Якщо j > 1, то j = j - 1 та v_j = 2 v_j. Перехід на пункт 2.

5. Якщо v_j > 0, то формується остання функція вибору

,

де - множина заповнених позицій функції вибору;

- заповнення нулями u_j - v_j вільних позицій функції вибору.

Алгоритм закінчено.

Для заданого у табл. 1 масиву p запропоновані методи визначають функції вибору, що розподіляють контрольні точки на інтервалі T = 16 з номерами тактів C = у NT = 3 канали контролю наступним чином (табл. 2 та 3).

Таблиця 3. Послідовності контрольних точок за другим вертикальним методом

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