УДК 681.325

АЛГОРИТМИ ТА МАТРИЧНІ НВІС-СТРУКТУРИ ПРИСТРОЇВ ДІЛЕННЯ ДЛЯ КОМП’ЮТЕРНИХ СИСТЕМ РЕАЛЬНОГО ЧАСУ

Цмоць І.Г.

Вступ

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

де k – кількість каналів надходження даних; n – розрядність даних; F_d - частота надходження даних [1-3].

Для НВІС-реалізацій ефективність використання обладнання - це інтегральний параметр, який зв'язує продуктивність пристрою з витратами обладнання на його реалізацію та дає оцінку елементам (вентилям) НВІС за продуктивністю [4-8]. Кількісна величина ефективності використання обладнання визначається наступним чином:

де W – витрати обладнання на НВІС-пристрій; Т – час виконання операції.

Для забезпечення ділення у реальному часі необхідно узгодити інтенсивність надходження даних P_d з пропускною здатністю НВІС-пристрою ділення D_к=F_кmп, де F_к – тактова частота роботи конвеєра, m - кількість трактів оброки. У випадку коли m і п величина постійна, то таке узгодження досягається шляхом зміни частоти роботи конвеєра F_к. Задача проектування матричних НВІС-структур ділення з високою ефективністю використання зводиться до мінімізації апаратних затрат при забезпечені режиму реального часу. Для переходу від алгоритмів ділення до НВІС-реалізацій пристроїв ділення у реальному часі використовуються методи просторово-часового відображення алгоритмів у матричні структури, пропускна здатність яких узгоджена з інтенсивністю надходження даних. Процес відображення алгоритмів ділення у матричні НВІС-структури реального часу з високою ефективністю використання обладнання є складним і вимагає взаємної адаптації як алгоритмів, так і структур.

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

1. Алгоритми ділення

Для НВІС-реалізацій необхідно, щоб алгоритми ділення базувались на елементарних арифметичних операціях та були рекурсивними і локально залежними. Із множини апаратно-орієнтованих алгоритмів ділення таким вимогам найбільше відповідають алгоритми ділення чисел в доповняльному коді (разом зі знаковими розрядами) без відновлення залишку [9-13]. Особливістю таких алгоритмів є те, що обчислення розрядів частки здійснюється послідовно розряд за розрядом, а точність результату залежить від числа розрядів h частки, тобто від кількості виконаних циклів (базових операцій). Для запобігання переповнення розрядної сітки при реалізації таких алгоритмів повинна виконуватися наступна умова |А|<|В|, де А і В відповідно ділене і дільник. У результаті виконання операції ділення визначається частка Y і залишок R у відповідності з рівнянням А=ВY+R. Базова операція алгоритму ділення чисел з фіксованою комою в доповняльному коді без відновлення залишку виконується за наступними виразами:

,                                              (1)

,                                                             (2)

де i=0,1,...,h, R_і – і-ий залишок, у_і – і-ий розряд частки, 2R_0-1=A, ЗнR_0-1=ЗнА.

Прискорити виконання операції ділення можна шляхом одночасного отримання двох і більше розрядів g³ 2 частки за один цикл. Для виконання такого ділення пропонується використати метод вибору залишку, за яким у кожному циклі паралельно обчислюються 2^g-1 залишків та на їх основі визначаються g розрядів частки і залишок для наступного циклу ділення. Для формування кратних дільника додатково необхідно виконати 2^g-1-1 додавань. Обчислення залишків для g=2 здійснюється за наступними виразами:

,                                            (3)

,                                         (4)

,                                         (5)

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

,                                  (6) ,                                               (7)

де у_і у_і+1 – і -ий та (і+1)-ий розряди частки,  - (і+1)-ий залишок після віднімання кратного дільника,  - (і+1)-ий залишок після додавання кратного дільника, 2R₀=A, 4R₀=2A, ЗнR₀=ЗнА.

Алгоритми ділення з одночасним визначенням трьох і чотирьох розрядів частки вимагають у кожному циклі паралельного обчислення відповідно 7 і 15 залишків та додаткового виконання відповідно 3 (g=3) і 7 (g=4) додавань для формування кратних дільника.

2. Структури пристроїв ділення

Аналіз існуючих високопродуктивних пристроїв ділення (ПД) показує, що всі вони зводяться до матричних структур, які апаратного відображають графи алгоритмів ділення [14-16].Для забезпечення високої ефективності використання обладнання матричних ПД необхідно узгодити їх пропускну здатність з інтенсивністю надходження даних. При діленні одиночних даних використовуються однотактні швидкодіючі матричні структури, а при ділені неперервних потоків даних – конвеєрні матричні ПД.

Базова структура однотактного матричного ПД наведена на рис.1, де БПО – блок попередніх обчислень для формування кратних дільника, ПЕ – процесорні елементи обчислення базових операцій ділення.

Рис.1 Базова структура однотактного матричного пристрою ділення

Основними компонентами матричного ПД є ПЕ, які реалізують базові операції алгоритмів ділення. З’єднання ПЕj із ПЕj+1 , де j=1,...,m, у такому ПД здійснюється із зсувом вліво на g розрядів. Необхідна кількість ПЕ для синтезу матричного ПД залежить від алгоритму та точності ділення і визначається так m=ù h/g é, де h - розрядність частки; g – кількість розрядів частки, які обчислюються за один цикл. БПО використовується при апаратні реалізації алгоритмів ділення з обчисленням у одному циклі двох і більше розрядів частки, тобто коли g³ 2.

Однотактні матричні пристрої ділення. Однотактні матричні ПД будуються на базі комбінаційних ПЕ, які реалізують базові операції алгоритмів ділення. Структура ПЕ, що реалізує базову операцію алгоритму ділення з обчисленням у циклі одного розряду g=1 частки, наведена на рис.2, де СВ – суматор-віднімач.

Рис.2 Структура ПЕ, що реалізує базову операцію ділення для g=1

У такому ПЕ_і обчислюється залишок R_i для наступного циклу ділення, визначається розряд частки у_і та сигнал управління СВ  (=0 - додавання, =1 - віднімання) для наступного циклу обчислення. Кількість ПЕ, що використовується для побудови однотактного матричного ПД визначається розрядністю частки h. Формули для обчислення часу ділення та апаратних затрат на побудову матричного ПД з обчисленням одного розряду g=1 частки у циклі наведені в таблиці 1, де п – розрядність діленого і дільника; t_CBп – час додавання (віднімання); t_BикАБО – час спрацювання логічного елементу виключне АБО; W_CBп і W_ВикАБО – апаратні затрати відповідно на п-розрядний суматор-віднімач і логічний елемент виключне АБО.

Використання алгоритмів ділення з визначенням двох розрядів g=2 частки для реалізації матричного ПД дозволяє зменшити час обчислення частки. Структура ПЕ, який реалізує базову операцію такого алгоритму ділення, наведена на рис.3.

Рис. 3 Структура ПЕ, що реалізує базову операцію ділення для g=2

У такому ПЕ два розряди частки у_і у_і+1, залишок R_i+1 і код операції  для наступного циклу ділення визначаються за результатами одночасно обчислення трьох залишків . На виходах комутаторів Км1 і Км2 формуються кратні дільника, які використовуються для обчислення залишків відповідно  і , а на виходах Км3 – залишок R_i+1 для наступного циклу ділення. На виходах логічних елементів виключне АБО отримуємо два розряди частки у_і у_і+1. Формули для обчислення часу ділення та апаратних затрат на матричний ПД, в якому ділення виконується за алгоритмом з визначенням двох розрядів g=2 частки, наведені в таблиці 1, де t_Км2-1 – час затримки на двох входовому комутаторі; W_Км2-1 – апаратні затрати на двоходовий комутатор.

Збільшення кількості розрядів g частки, які визначаються у одному циклі, веде до зменшення часу ділення та збільшення апаратних затрат на їх реалізацію. Однотактні матричні ПД, які реалізують алгоритми ділення з визначенням трьох g=3 і чотирьох g=4 розрядів частки, будуються на базі ПЕ, які реалізують базові операції даних алгоритмів ділення. За структурою такі ПЕ близькі до розглянутих структур з g=1 і g=2. Формули для обчислення часу ділення та апаратних затрат на побудову матричних ПД з визначенням у циклі трьох g=3 і чотирьох g=4 розрядів частки наведені в таблиці 1, де W_Км4-1, W_Км8-1 – апаратні затрати відповідно на чотири і восьми входові комутатори.

Табл.1

Формули для оцінки основних характеристик однотактних матричних ПД

Конвеєрні матричні пристрої ділення. Конвеєрні матричні ПД можна розділити на дві групи: з лінійними і нелінійними зв’язками. У лінійних конвеєрних ПД передача інформації здійснюється в одному напрямку, а у нелінійних – як у прямому, так і в зворотному напрямку за допомогою системи обернених зв’язків. Конвеєрні ПД з лінійними зв’язками отримуються з однотактних матричних ПД шляхом розбиття їх на сходинки за допомогою регістрів. Кількість сходинок, на які розбивається ПД і їх складність, визначається з умови узгодження пропускної здатності ПД з інтенсивністю находження вхідних даних. Пропускна здатність конвеєрних ПД визначається тактом роботи конвеєра, який може змінюватися від T_max=h(t_Рг+t_CВп+ t_ВикАБО) до T_min= t_Рг+t_CВп+ t_ВикАБО, де t_Рг – час запису в регістр.

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

,

де g – кількість розрядів частки, які обчислюються в циклі; h – кількість розрядів частки.

Найбільша пропускна здатність та ефективність використання обладнання досягається при конвеєризації матричного ПД з визначенням у циклі одного розряду g=1 частки. Конвеєрний ПД з лінійними зв’язками будується на базі ПЕ (рис.2), який доповнюється трьома вхідними регістрами і тригером. Такт роботи конвеєра такого ПД обчислюється за формулою:

T₁= t_Рг+t_CВп+ t_ВикАБО.

Для побудови конвеєрних ПД з нелінійними зв’язками використаємо алгоритм ділення з визначенням у циклі одного розряду g=1 частки, який зводиться до h-кратного виконання базові операції, заданої формулами 1 і 2. Структура ПЕ, який реалізує р ітерацій базової операції алгоритму ділення з g=1, наведена на рис.4, де СВ – суматор-віднімач; Тг – тригер; Рг –регістр; Км – комутатор; У1 – сигнал керування; ТІ1 і ТІ2 – тактові імпульси.

Рис. 4 Структура ПЕ конвеєрного ПД з нелінійними зв’язками

Нелінійний ПЕ будується на базі лінійного шляхом доповнення його трьома регістрами, тригером і двома комутаторами, перший з яких забезпечує подачу коду операції  для наступного циклу обчислення, а другий – подачу зсунутого вліво на один розряд залишку R_j. Керуванням роботою ПЕ здійснюється сигналом У1, який задає режим роботи регістра Рг1 (У1=0 – паралельний запис; У1=1 – послідовний запис з зсувом вліво) та управляє комутаторами Км1 і Км2 (У1=0 – передача інформації з перших входів; У1=1 – передача інформації з других входів). Сигнал У1 тільки перед приходом тактового імпульсу ТІ2 рівний нулю, а в інший час - одиниці. Час виконання однієї ітерації базової операції алгоритму ділення у ПЕ дорівнює періоду тактових імпульсів ТІ1 і обчислюється за наступною формулою:

.

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

,

а кількість таких ПЕ визначається так:

,

де P_d – інтенсивність надходження даних; D_к – пропускна здатність конвеєра, F_d – частота надходження операндів, F_к – частота роботи макроконвеєра, яка визначається наступним виразом F_к=1/Т_ТІ2=1/pT_ТІ1.

Необхідні апаратні затрати на побудову конвеєрного ПД з нелінійними зв’язками обчислюються за формулою:

.

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

Оцінка параметрів розроблених ПД. Для оцінки основних параметрів розроблених структур ПД за одиницю виміру витрат обладнання та часу обчислення візьмемо логічний вентиль і час його затримки. Аналітичні вирази для розрахунку основних характеристик розроблених структур ПД ґрунтуються на аналітичних виразах визначення швидкодії та витрат обладнання на функціональні вузли з роботи [4]. Отримані аналітичні вирази оцінки основних характеристик ПД, наведені в таблиці 2, де ; п – розрядність операндів; h – розрядність частки; g – кількість розрядів частки, які обчислюються в циклі; р – кількість ітерацій алгоритму, що виконуються у ПЕ.

Табл. 2

Аналітичні вирази для оцінки основних параметрів

Рис. 5 Діграми витрат обладнання на ПД

Рис. 6 Діаграми ефективності використання обладнання ПД

На основі аналітичних виразів, наведених у табл. 2, побудовано діаграми витрат W (рис.5) та ефективності (рис.6) використання Е обладнання для ПД у залежності розрядності п операндів, де W₁, W₂, W₃ і W₄– витрати обладнання на однотактні ПД, що працюють за алгоритмами з визначенням у циклі відповідно g=1, g=2, g=3 і g=4 розрядів частки; W_k1 - витрати обладнання на конвеєрний ПД; Е₁, Е₂, Е₃, Е₄ – ефективність використання обладнання ПД, що працюють за алгоритмами з визначенням у циклі відповідно g=1, g=2, g=3 і g=4 розрядів частки. З аналізу наведених діаграм випливає, що найменші витрати обладнання на реалізацію однотактних ПД досягаються при використанні алгоритму ділення з визначенням у циклі одного розряду частки, а найбільшу ефективність використання обладнання з однотактних ПД мають пристрої з визначенням у циклі двох розрядів частки.

Висновки:

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

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

                        Алгоритми ділення з одночасним визначенням у циклі g розрядів частки вимагають додаткового виконання 2g-1-1 додавань для формування кратних дільника та у кожному циклі паралельного обчислення 2g-1 залишків.

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

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

1.С.Кун. Матричные процессоры на СБИС:-М.:Мир,1991.-672 с.

2.Паралельная обработка информации: Т.4. Высокопроизводительные системы паралельной обработки информации /Под ред. В.В. Грицыка — Киев: Наук. думка, 1988. — 272с.

3.Грушицкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем на микросхемах программируемой логики. – СПб.: БХВ-Петербург, 2002. – 608с.

4. Цмоць І.Г. Принципи розробки і оцінка основних характеристик високопродуктивних процесорів на надвеликих інтегральних схемах/ Вісник ДУ “Львівська політехніка”, №349, Львів, 1998 - с.5-11.

5. Коуги П.М. Архитектура конвейерных ЭВМ.: Пер. с англ. – М.: Радио  и связь, 1985. – 360 с.

6. Цмоць І.Г. Особливості проектування спеціалізованих комп’ютерних систем для обробки інтенсивних потоків інформації // Збірник наук. праць ІПМЕ НАН України: "Моделювання та інформаційні технології", - Київ, Вип. 8. 1999. – с.143-149.

7. Каневский Ю.С. Систолические процессоры. — К: Техніка, 1991. — 173с.

8.Шалыто А.А. Методы аппаратной и программной реализации алгоритмов. – СПб.: Наукка,200. – 780 с. Коуги П.М. Архитектура конвейерных ЭВМ.: Пер. с англ. – М.: Радио  и связь, 1985. – 360 с.

9.Савельев А.Я. Арифметические и логические основы цифровых автоматов. М.: Высш. школа,  1980. – 225 с.

10.             Соловьев Г.Н. Арифметические устройства ЭВМ. М.: Энергия, 1978. – 176 с.

11.             Карцев М.А. Арифметика цифровых машин - М.,Наука, 1969.

12.             Карцев М.А., Брик В.А. Вычислительные системы и синхронная арифметика. - М.: Радио и связь, 1981. - 360с.

13.             Прикладная теория цифровых автоматов. К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйский, Ю.С. Каневский, М.М. Пинкевич.-К.: Вища шк. Головное из-во, 1987.- 375.

14.             Цмоць І.Г. Особливості проектування алгоритмічних операційних пристроїв високопродуктивних процесорів цифрової обробки сигналів. Збірник наукових праць Інституту проблем моделювання в енергетиці НАН “Моделювання та інформаційні технології” Випуск 5, Київ 2000. 147-154с

15.             А.с. 1711149 (СССР). Устройство для деления. Е.Я. Ваврук, И.Г. Цмоць., – Опубл. в Б.И., 1992, №5.

16.             1705820 (СССР). Вычислительное устройство. Е.Я. Ваврук, И.Г. Цмоць. – Опубл. в Б.И., 1992, №2.