Реалізація степеневої функції з плаваючою комою в неавтономному режимі.



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

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

Implementation ofthe power function with floating point in on-line mode

Zhabin Valeriy Ivanovich

Kokhan Olena Sergiyivna

Tokar Andrey Gennadievich

An algorithm for calculating the function $Z={{X}^{2}}$ with floating point, which enables to overlap processing, bit-by-bit input and output of information from high positions using redundant number system, is proposed. It is shown that the use of computer modules implementing this calculation mode enables you to perform related operations in the concurrent mode and reduces hardware complexity.

Keywords. On-line calculations, operations overlap, power function, flow graph, the system-on-chip.

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

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

Високий рівень розпаралелювання може бути досягнутий при поданні алгоритмів у вигляді графа з дрібнозернистою структурою, коли вершинам графа відповідають окремі операції. При цьому збільшується число паралельних гілок, що дає потенційну можливість використовувати більшу кількість паралельно працюючих обчислювальних модулів (ОМ). Однак, швидкість обробки інформації пов'язана не тільки з мінімізацією часу виконання паралельних гілок, але і мінімізацією витрат на обмін інформацією між ОМ. Виграш в швидкості обчислень при збільшенні рівня розпаралелювання алгоритмів пов'язаний зі зростанням інтенсивності обміну між гілками, що збільшує час вичисленій. Цей фактор є дуже важливим і повинен враховуватися при виборі архітектури ОС. Для реалізації дрібнозернистих алгоритмів недоцільно використовувати класичні багатопроцесорні системи типу MIMD (Multiple Instruction – Multiple Data) [4], оскільки в них використовуються складні процедури обміну інформації, що неприйнятно для обміну на рівні окремих слів.

Реалізація потокових обчислень у неавтономному режимі. Використання сучасної елементної бази (програмованих та замовних НВІС) і технології проектування SoC(System on Chip – система на кристалі) дозволяє побудову систем з різною архітектурою. Для скорочення витрат часу на обмін даними застосовують паралельні системи з безпосередніми зв'язками (ПСБЗ) між обчислювальна модулями(ОМ) [5, 6].

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

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

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

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

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

Реалізація степеневої функції у неавтономному режимі. При вирішенні завдань лінійної алгебри, інтерполяції функцій, перетворення координат, цифрової обробки сигналів використовується одномісна функція $Z={{X}^{2}}$. Розглянемо реалізацію такої функції з плаваючою комою в неавтономному режимі.

Особливість неавтономного режиму полягає в тому, що розряди результату операції формуються з затримкою на $p$ кроків. Тому будемо розглядати функцію $Y={{k}^{-p}}{{X}^{2}}$. У формі з плаваючою комою функцію можна представити як $Y={{2}^{{{P}_{x}}}}\cdot{{M}_{x}}$, ГДж ${{P}_{x}}$ – порядок, ${{M}_{x}}$ – мантиса числа $X.$ Порядок представлений в канонічній двійковій системі числення, а мантиса - в квазіканонічній системі числення з основою $k=2$ і цифрами {-1,0,1}.. Квазіканонічна система є надлишковою, одне і те ж число може мати кілька подань, наприклад, $0,1011=0,11\overline{1}1$. Це дозволяє формувати результат порозрядно без переносів в старші розряди.

Код операнда в квазіканонічній системі має вигляд

\[X=\sum\limits_{i=1}^{n}{{{x}_{i}}\cdot{{k}^{-i}},}\quad\quad\quad(1)\]

де ${{x}_{i}}\in\{-1,0,1\}$.

Оскільки обчислюється функція ${{k}^{-p}}\cdot {{X}^{2}}$, то для функції ${{X}^{2}}$ потрібно змістити кому в результаті на p розрядів вправо. Для отримання n розрядів після коми функції ${{X}^{2}}$ потрібно зробити $m=n+p$ кроків обчислень. Функція $Y$ буде мати вигляд \[Y=\sum\limits_{i=1}^{m}{{{y}_{i}}\cdot{{k}^{-i}},}\] де ${{y}_{i}}\in\{-1,0,1\}$. Операнд X вводиться із старших розрядів. Позначимо за ${{X}_{i}}$ та ${{Y}_{i}}$ коди операнда та функції, що містять тільки i розрядів справа від коми, наприклад ${{X}_{5}}=0,{{x}_{1}}{{x}_{2}}{{x}_{3}}{{x}_{4}}{{x}_{5}}0...0$,${{Y}_{3}}=0,{{y}_{1}}{{y}_{2}}{{y}_{3}}0...0$ .

Після виконання m кроків отримаємо функцію ${{Y}_{m}}=Y$ з похибкою, яка не перевищує ${{k}^{-m-1}}$, якщо на кожному кроці формувати цифру ${{y}_{i}}$ так, щоб виконувалась умова

Якщо ввести заміну

\[{{R}_{i}}=({{k}^{-p}}\cdot X_{i}^{2}-{{Y}_{i}})\cdot{{k}^{i}},\quad\quad\quad(3)\]

то вираз (2) матиме вигляд

\[-\frac{1}{2}\le {{R}_{i}}\quad\quad\quad(4)\]

Нерівність (4) виконується у вихідному стані при ${{R}_{0}}=0$. Будемо вважати, що на (i-1)-му кроці нерівність(4) також виконується, та визначимо при якому мінімальному значенні p співвідношення (4) буде виконуватись на будь-якому наступному кроці.

З використанням виразів (1) та (2) подамо (3) у вигляді

\[{{R}_{i}}=k{{R}_{i-1}}+{{k}^{-p+1}}{{x}_{i}}{{X}_{i-1}}+{{k}^{-p-i}}x_{i}^{2}-{{y}_{i}}.\quad\quad\quad(5)\]

Ввівши заміну

\[{{H}_{i}}=k{{R}_{i-1}}+{{k}^{-p+1}}{{x}_{i}}{{X}_{i-1}}+{{k}^{-p-i}}x_{i}^{2},\quad\quad\quad(6)\]

одержимо (5) у вигляді

\[{{R}_{i}}={{H}_{i}}-{{y}_{i}}.\quad\quad\quad(7)\]

Згідно рівності (7), запишемо (4) у вигляді

\[{{y}_{i}}-\frac{1}{2}\le{{H}_{i}}\quad\quad\quad(8)\]

На основі аналізу нерівності (8) можна визначити мінімальне значення $p$, при якому виконується нерівність (4), а саме

\[p=\left\lfloor {{\log }_{k}}\frac{4}{2-k+1}\right\rfloor .\quad\quad\quad(9)\]

Для основи $k=2$ відповідно з (9) визначаємо $p=2$. Підставляючи в нерівність (8) значення ${{y}_{i}}\in \{-1,0,1\}$ , отримаємо правило формування цифри для функції $Y$

Таким чином, на кожному кроці потрібно по формулі (6) знайти значення ${{H}_{i}}$, згідно якого визначити за допомогою правила (10) цифру ${{y}_{i}}$ функції, та знайти значення ${{R}_{i}}$ для наступного кроку за допомогою формули (7).

Розряди операнду і результату передаються між ОМ за допомогою двох провідників. Цифри з множини {-1,0,1} можуть кодуватись відповідно {10,00,01}.

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

Алгоритм роботи ОМ.

  1. Прийняти порядок ${{P}_{X}}$ в канонічній системі числення з цифрами {0,1}.

  2. Отримати попередній порядок результату за формулою ${{P}_{Y}}=2\cdot {{P}_{X}}+p$.

  3. В кожному циклі обчислень формувати цифру мантиси результату. Починаючи з першого циклу, нульові цифри мантиси не видавати з ОМ. При цьому корегувати порядок наступним чином: ${{P}_{Y}}:={{P}_{Y}}-1$.

  4. При формуванні першої ненульової цифри результату видати із ОМ остаточний порядок ${{P}_{Y}}$ і першу ненульову цифру мантиси результату.

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

На кожному кроці в ОМ вводиться по одному розряду операндів і формується один розряд результату. При цьому розряд проміжного результату, отриманий на $i$-му кроці в одному ОМ при виконанні $j$-ї операції, може бути використаний на ($i$+1)-му кроці в іншому ОМ при виконанні ($j$+1)-ї операції.

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

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

Висновки

ОС на базі квазіпаралельних ОМ використовує істотно менше ресурсів на кристалі (ПЛІС або замовних НВІС), що пов'язано з малим числом зв'язків. Економляться як внутрішні ресурси мікросхем, так і її виводи. Це дає можливість реалізувати на ті й же мікросхемі ряд інших пристроїв, що відносяться до однієї або різних систем.

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

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

Література

  1. Байков В.Д. Решение траекторных задач в микропроцессорных системах ЧПУ / В.Д.Байков, С.Н.Вашкевич. – Л.: Машиностроение,1986.– 105 с.

  2. Сосонкин В.Л. Принципы построения систем ЧПУ соткрытой архитектурой / В.Л.Сосонкин, Г.М.Мартинов // Приборы и системы управления.– 1996. – №8. – С. 18-21.

  3. Благовещенский Ю.В. Вычисление элементарных функций наЭВМ / Ю.В.Благовещенский, Г.С.Теслер. – Киев, «Техника», 1977. – 208 с.

  4. Воеводин В.В. Параллельные вычисления / В.В.Воеводин,Вл.В.Воеводин. – СПб.: БХВ-Петербург, 2002. – 608 с.

  5. Жабин В.И., Жабина В.В., Безгинский М.А. Эффективностьпотоковых вычислений в системах с непосредственными связями, реализованных наПЛИС / В.И.Жабин. В.В.Жабина М.А.Безгинский // Вісник НТУУ "КПІ".Інформатика, управління та обчислювальна техніка: Зб. наук. праць. – К.:

  6. Жабин В.И. Построение быстродействующих специализированных вычислителей для реализации многоместных выражений /В.И.Жабин, В.И.Корнейчук, В.П.Тарасенко. – Автоматика и вычислительная техника.– 1981. – № 6. – С. 18-22.
May 23, 2016