Лекція 17

Помножувачі

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

Існують різні типи однотактних помножувачів. Найбільш розповсюджені матричні помножувачі з однорідною структурою (мал.17.1). У такому помножувачі матриця елементів І одночасно формує розряди усіх часткових добутків, що потім підсумовуються за допомогою матриці однорозрядних суматорів. Кожний рядок однорозрядних суматорів перетворює три вхідні доданки у два вихідні. На виході матриці отримують n молодших розрядів добутку p₀, p₁, …, p_n-1 і проміжні значення старших n розрядів (виходи s суматорів n-1-го рядку) та значення одиниць переносу у цих розрядах (виходи с суматорів n-1-го рядку). Таке уявлення старших розрядів у вигляді двох компонент називають двохрядним кодом добутку. Остаточні значення старших n розрядів формуються шляхом підсумовування компонент цього коду за допомогою n-розрядного суматора (на мал.17.1 у штриховому прямокутнику), що вмикається на виході помножувача.

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

a_n-1 a_n-2 a₁ a ₀ b₀

p₀

b₁

p₁

b₂

p₂

b_n-1

p_n-1

p_2n-1 p_2n-2 p_n+1 p_n

Мал.17.1. Схема матричного помножувача.

Одним з найефективніших алгоритмів матричного множення є модифікований алгоритм Бута, зідно з яким формуються часткові добутки множеного А на двохрозрядні групи множника В = b_n b_n-1 … b₁ b₀ за формулою R_i = A(-b_i+1 2 + b_i + b_i-1)2ⁱ, і = 0, 2, 4, …, n. Застосування цієї формули спрощує обчислення часткових доданків, які можуть приймати значення від - 2А2^і до 2А2^і. При і = 0, b_i-1 = b_-1 = 0. Часткові добутки формуються у додатковому коді. Їх підсумовування здійснюється за допомогою матриці однорозрядних суматорів і суматора двохрядного коду добутка, як у помножувачі на мал.17.1.

Для прикладу виконаємо множення чисел А = a₃ a₂ a₁ a₀ = 1011 і B = b₃ b₂ b₁ b₀ = 1001. Для і = 0 маємо b₁ b₀ b_-1 = 010 і R₀ = A = 1011. Для і = 2 b₃b₂b₁ = 100 і R₂ = A2³ = - 1011000. Додатковий код R₂ - 10101000. Для і = 4 b₅b₄b₃ = 001 і R₄ = A2⁴ = 10110000. У результаті підсумовування отримуємо 00001011 + 10101000 + 10110000 = 01100011 = А х В.

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

Регістрові блоки

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

На мал.10 показана типова структура регістрового блоку (такі блоки часто називають регістровими файлами) з довільним вибиранням, що складається з m n-розрядних регістрів. У режимі запису n-розрядне число D надходить на входи усіх регістрів. Але запис відбувається тільки в один з них, вибір якого здійснюється згідно з надійшовшою адресою (а₀ … а_k-1), де k log₂m. Якщо k = log₂m, використовується повний дешифратор, на одному з виходів якого встановлюється сигнал вибирання y_і = 1. При цьому сигнал дозволу запису ДЗ = 1 надходить на вибраний регістр, у який заноситься число D. Регістри звичайно реалізуються на D-тригерах. Якщо використовуються D-тригери, що синхронізуються рівнем, сигнал ДЗ подається безпосередньо на вхід синхронізації С. Якщо синхронізація виконується фронтом, синхросигнал подається на окремий вхід синхронізації С (штрихові лінії на мал.10). У режимі читання адреса b₀ … b_k-1 потрібного регістра надходить на входи багаторозрядного мультиплексора, на виходах якого встановлюється n-розрядне число Q, прочитане з цього регістра. Зв’язки інформаційних входів мультиплексора з усіма регістрами показані на мал.17.2 штриховими лініями. Буферний каскад (БК) з трьома станами при надходженні сигналу дозволу читання ДЧ = 1 передає прочитане число на вихід блоку. Якщо читання заборонене (ДЧ = 0), виходи блоку відключаються від навантаження (реалізується високоомний вихід).

а₀ а_k-1

y₀ y₁ y_n-1

С

&

&

&

ДЗ

b₀ b_k-1 ДЧ

C C C

Q₀

Q₁

Q_n-1

RG₀ RG₁ RG_m-1 MUX БК

d₀ … d_n-1

Мал.17.2. Регістровий блок з довільним вибиранням.

Регістрові блоки з послідовним вибиранням реалізуються на зсовуючих регістрах статичного або динамічного типу. Приклад такого блоку показаний на мал.17.3. Кількість регістрів дорівнює розрядності чисел n, а кількість розрядів у регістрах – кількості чисел, що можуть одночасно зберігатися у блоці. При ДЗ = 1 число D може заноситися у блок. Занесення відбувається за надходженням фронту синхроімпульсу. Перший синхроімпульс призводить до занесення числа D у перші розряди регістрів. При надходженні наступного синхроімпульсу це число зсовується на один розряд до виходів блоку, а у перші розряди уводиться наступне число. Таким чином уведене число з’явиться на виході через m тактів. При ДЗ = 0 увід наявого числа заборонений, а у перші розряди регістрів переписується число з останніх розрядів. Отже уведені числа можуть зберігатися, циркулюючи у зсовуючих регістрах. Читання певного числа здійснюється, коли воно надходить у останні розряди регістрів. При цьому подається сигнал дозволу читання ДЧ = 1, і число формується на виходах буферного каскаду. При забороні читання (ДЧ = 0) виходи БК переходять у високоомний стан.

  БК

& 1   &

d₀ Q₀ Q₀

С

RG₀

& 1   &

d_n-1 Q_n-1 Q_n-1

С ДЧ

RG_n-1

С

ДЗ

Мал.17.3. Регістровий блок з послідовним вибиранням.

Одним з різновидів регістрових ЗП з послідовним вибиранням є стековий ЗП (мал.17.4). У такому ЗП використовуються реверсивні регістри, а напрямок зсуву залежить від значення сигналу завантаження-розвантаження (ЗР). При дозволі роботи стеку (сигнал ДР = 1) зовнішні синхросигнали С надходять на регістри. У режимі завантаження стеку на блок подається сигнал ЗР = 0, при якому регістри приймають у перші розряди зі входу число D = d₀ … d_n-1, а потім послідовно зсовують його праворуч – на один розряд у кожному такті. Буферний каскад БК при цьому знаходиться у високоомному стані. У режимі розвантаження стеку (ЗР = 1) уведені числа зсовуються ліворуч на один розряд при надходженні кожного сихроімпульсу і послідовно виводяться зі стеку, потрапляючи на виходи БК. У результаті число, прийняте у стек останнім, буде виведено з нього першим. Тому такі ЗП називають стеком типу “останній прийшов – перший пішов” (LIFO: Last In – First Out). На відміну від стеків регістрові ЗП із структурою, показаною на мал.17.3, іноді називають ЗП типу “черга” або “перший прийшов – перший пішов” (FIFO: First In – First Out).

  БК Q₀ Q₀     d₀ С RG₀     Q_n-1 Q_n-1     d_n-1 С RG_n-1 С ДР     ЗР   Мал.17.4 Стековий ЗП.

Дата добавления: 2014-01-13