1.7.7. Реалізація методів прискореного множення в процесорах

Схемні методи вимагають введення надмірності (додаткового обладнання) в операційну частину, а логічні - надмірності в керуючу частину. До схемних методів відносяться методи, які дозволяють зменшити час множення за рахунок зменшення часу підсумовування, поєднання підсумовування і зсуву, обчислення за 1 такт кількох ПП, табличної реалізації множення. До логічних методів відносяться методи, за допомогою яких можна зменшити кількість передач множеного на суматор, виконати за 1 машинний такт множення відразу двох-чотирьох розрядів множника (тобто перейти до множення в 4 -, 8 -, 16-річної СЧ).

Логічні методи прискореного множення

1. Метод Лемана

Cуть: зменшення числа передач множеного на суматор за рахунок перетворення множника в модифікованої двійковій СС (, 0,1).

Нехай у множнику зустрілася група з k одиниць. Нехай виконується множення за III варіантом і в молодшому розряді множника є кілька нулів. Будемо виконувати зсув суматора по нулях множника без передачі множеного на суматор до тих пір, поки у множнику не з'явиться одиниця. Множене передається на суматор із зворотним знаком. Переходимо на зсув суматора по одиницях множника на суматор до тих пір, поки не з'явиться "0" у множнику. При цьому множене передається на суматор з прямим знаком і здійснюється перехід на зсув суматора по нулях. Тобто замість k передач множимо здійснюється тільки дві (інверсна і пряма).

Необхідно цей алгоритм модифікувати тобто, щоб розрізняти ізольовані "0" і "1" від груп. Тому що при комбінації 101010 необхідно робити 6 передач (3 прямі і 3 інверсні), замість трьох. Для цього в процесі множення треба аналізувати не тільки поточний, а й старший сусідній розряд множника. Для того, щоб побудувати блок множення за методом Лемана, необхідно в цей блок включити спеціальний тригер. Перед початком множення в нього записується "0" - режим зсуву суматора по "0" множника. При запису на цей тригер "1" буде здійснено перехід в режим зсуву суматора по "1".

У загальному вигляді алгоритм Лемана представляється таблицею:

Q (t) - стан тригера режиму

T _n-1, T _n - пара аналізованих розрядів множника

ПП - пряма передача

ІП - інверсна передача

Користуючись таблицею можна записати:

ПП=

ІП =

Схема прискореного блоку множення по Леману

2. Методи множення на 2 розряди множника

2.1 Множення з молодших розрядів

Суть: аналіз у кожному машинному такті двох розрядів.

Для реалізації даного алгоритму необхідно включити до складу БО додатковий тригер, який називається тригером інверсної передачі (ІП). Перед початком операції він встановлюється в нуль. У разі виконання інверсної передачі на суматор його встановлюють в одиницю. Одиничний стан може проіснувати 1 або кілька тактів. Реалізація даного алгоритму множення може бути представлена у вигляді таблиці:

У таблиці Т _n і T _{n -1} - пара молодших розрядів множника, Т _ип (t) - поточний стан тригера ІП, Т _ип (t) - подальший стан тригера ІП, М1 - передача Х на суматор, 1 - , М2 - 2Х ..

Блок прискореного множення містить 3 регістри. В РГХ і Рг Z організовані зрушення на два розряди вправо одночасно. Комбінаційний суматор і Рг Z мають подвійну кількість розрядів. Через СПК на суматор можна передавати Х,   і 2Х, тому на її вхід надходять 3 керуючі сигнали М1, 1 і М2. Ці сигнали виробляються за допомогою трьох КС, логіка роботи яких отримана з складеної матриці. 4 ^я КС управляє Т _ІП.

2.2 Універсальний алгоритм множення на 2 розряди множника (алгоритм МакСорні)

Працює для всіх чотирьох варіантів множення.

Т _1, Т ₂ - пара старших розрядів множника,

Т _д - додатковий тригер (запам'ятовує молодший розряд попередньої пари розрядів множника)

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

 

Блок прискореного множення, який реалізує метод МакСорні, містить 3 регістри. Рг Z має подвійну кількість розрядів. В Рг Y реалізовані ланцюги лівого зсуву на 2 розряди. Через СПК на суматор передається подвоєне або почетверене множене в прямій або інверсної формі. Керуючі сигнали - М2 і М4, виходи додаткового тригера, який запам'ятовує молодший розряд пари розрядів множника, який аналізувався на попередньому етапі множення. М2 і М4 виробляються за допомогою КС1 і КС2.

Можлива реалізація і на 3, і на 4 розряди.