Побудова арифметико-логічного пристрою для виконання операції множення цілих чисел
АЛП - основний операційний блок мікропроцесора і призначений для наступних груп операцій:
Арифметичні операції з цілими операндами.
Під операндами розуміються N розрядне двійкове слово, яке може бути розміщене в регістрах мікропроцесора і піддано обробки в АЛП.
До складу арифметичних операцій з цілими операндами входять:
Короткі операції: додавання, віднімання, алгебраїчне додавання.
Довгі операції: множення, ділення цілих чисел.
Логічні:
Диз'юнкція.
Кон'юнкція.
Операція порівняння на рівність.
Арифметичні операції чисел з плаваючою точкою:
Алгебраїчне додавання.
Множення.
Розподіл.
Група спеціальних арифметичних операцій:
Зсувні операції.
Арифметичні або логічні.
При арифметичному зсуві знак числа, що розміщується у першому бите поля, не піддається зрушення, а при логічному зсувається.
Операції індексного арифметики:
Виконуються при формуванні виконавчих адрес з урахуванням різного складу регістрів.
АЛП можуть реалізовуватися як послідовно, так і паралельно.
У послідовному АЛУ обробка операндів виконуються послідовно за розрядами операнда. Очевидно, що збільшення довжини операнда призводить до збільшення точності обробки, але вимагає додаткових апаратних витрат і збільшується час виконання обробки.
У паралельних АЛУ в кожен момент часу відбувається обробка більше одного розряду операнда аж до обробки всіх розрядів відразу. Вони високопродуктивні і дороги.
За часом виконання операцій АЛУ діляться на асинхронні і синхронні.
В асинхронних АЛУ тривалість виконання операцій залежить від змісту і довжини операнда.
У синхронних АЛУ тривалість виконання операції визначається імпульсами синхронизируемое таймера (генератора) і має функціональну тривалість не залежну від операндів.
Операційні компоненти АЛП можуть бути виконані у вигляді сукупності функціональних блоків, або у вигляді одного багатофункціонального блоку, який налаштовується на виконання відповідної операції за результатами декодування ходу операції.
Другий варіант дозволяє виконати або частини однієї операції, або кілька операцій паралельно, тим самим збільшити продуктивність АЛП.
У сучасних мікропроцесорах типу Pentium розміщується кілька АЛП, що дозволяє збільшити продуктивність за рахунок паралельної обробки різних команд виконуваної програми.
До складу АЛУ входять:
багаторозрядних суматор
сукупність регістрів з ланцюгами зсуву та зворотними зв'язками
Будь-яка виконувана операція в АЛП представляється послідовністю мікрооперацій пристроєм управління, відповідно до коду операції поточної команди.
До складу входять:
робочий регістр - регістр, що має N розрядів
робочий регістр суматора
паралельний комбінаційний N розрядний суматор
вихідний N розрядний регістр суматор
Логічна схема Пр, формує ознаки результатів виконання операцій.
Кожен регістр оснащується схемами управління, які дозволяють підключити вхідні кола до розрядів регістрів для їх установки, або вихідні ланцюги для зчитування вмісту розрядів регістрів (регістр суматор). Інформація з регістра 1 може передаватися в регістр А, або з використанням прямих кодів, які з основних виходів тригерів у складі регістрів, або з використанням інверсних кодів, які з інверсних виходів відповідних тригерів
Вхідні операнди представляються позиційними входами:
,
де
Xi - значення i-того розряду.
- Старший розряд двійкового поля, що виділяється для зберігання знака.
Для представлення двійкових чисел може використовуватися прямий код, зворотний і додатковий.
Прямий код:
Використовуючи 4-х розрядне бітове поле, десяткове число 3 можна представити в наступному вигляді:
3пр = 0011
-3пр = 1011
Старший розряд визначає знак числа, а числові розряди визначають значення числа.
Для виконання арифметичних операцій з операндами, представленими у вигляді двійкового поля, що мають однаковий код виробляється підсумовування числових розрядів операторів. Знак результату збігається зі знаком операнда.
Якщо операнди мають різні знаки, то необхідно визначити спочатку операнд з великими значеннями, з якого відняти числові розряди операнда з меншим значенням. Знак результату збігається зі знаком операнда, більшого за модулем.
Як випливає з опису операції з операндами, представленими в прямому коді, операція має досить високу трудомісткість. Тому з метою економії апаратних та часових ресурсів для представлення негативних операндів використовують зворотний або додатковий коди. Зворотний код для визначення негативних чисел записується як доповнення до числа, яке може бути розміщене в числових розрядах відповідного числа.
Xобр X <0
Щоб отримати зворотний код достатньо кожен розряд двійкового поля замінити інверсним значенням:-3обр = 1100
Всі невід'ємні числа представляються прямим кодом, а негативні - додатковим або зворотним. При використанні зворотних кодів виникає одна неприємність, пов'язана з позитивним і негативним нулем. Цього недоліку не мають додатковий код від'ємних чисел.
Додатковий код виходить як додаток до числа 2 n Xдоп . Т.О. щоб отримати додатковий код числа потрібно інвертувати кожен розряд числа і додати до результату одиницю.
Вказана властивість додаткових кодів для представлення негативних чисел дозволяє замінити операцію віднімання операцією додавання, яку нам представляє суматор.
Для перетворення негативного числа в додатковому коді в прямий код достатньо виконати зворотну дію, тобто інвертувати кожен розряд числа (і знаковий) і додати одиницю до молодшого розряду. При складанні позитивних чисел, представлених прямим кодом і негативних чисел представлених зворотним кодом, може виконуватися кругової перенесення. При цьому якщо виникає перенесення з знакового розряду, то він додається до молодшого розряду числа.
На практиці використовується прямий код для представлення невід'ємних чисел, і додатковий - для представлення негативних. Це дає можливість отримувати результат у прямому коді, якщо він позитивний, і в додатковому, якщо він негативний.
У результаті операції можуть виникнути такі ситуації:
Перенесення з знакового розряду при відсутності переносу в знаковий розряд (ця ситуація відповідає негативному переповнення розрядної сітки)
Наявність перенесення в знаковий розряд при відсутності при відсутності переносу в знаковий розряд (позитивний перенос).
За відсутності загальних переносів, або при їх обох наявностей, результат розміщується в розрядній сітці.
Таким чином наведена схема формує відповідно до алгоритму: z = x
y. Виконання операції відповідає додаванню операндів год і зв. Виконується прийом першого операнда в регістр В. Виконується прийом другого операнда в регістр А.
Другий операнд передається в РДА в коді, який відповідає виконаній операції:
1) прямий при додаванні
2) інверсний при вирахуванні
Суматор виконує додавання кодів, при виконанні операції із зворотним кодом оператора молодшого розряду додається 1. Результат операції розміщується в регістрі суматора. Якщо результат позитивний, то він представляється прямим кодом, якщо негативний, то додатковим кодом.
Крім цього логічна схема Пр формується ознаками результатів виконання операції
n1 n2
0
1 z = 0
0 z <0
1 січня z> 0
Зазначені умови перевіряються відповідними логічними схемами, які забезпечують формування сигналів n1 і n2 надходять на пристрій керування.
Операція множення - послідовність операцій додавання і зсуву. При цьому результат операції при розмірності операндів числові розряди (n-1). Розмірність результату (2n-1) - числовий розряд. Якщо операнди - виконавчі слова, то результат теж. Оскільки в розпорядженні є апаратні засоби, у вигляді суматорів і ланцюгів зсуву по розрядній сітці, то операція множення представляється як результат послідовного аналізу цифр множника і додавання до поточного значення суми часткових творів з первинним нульовим значенням множимо, якщо аналізована цифра множника дорівнює одиниці. Після цього суму часткових творів чи множимое слід зрушити по розрядній сітці для виконання чергової ітерації., По суті операція множення - в трактованої змісті відповідає множенню «у стовпчик».
Варіанти множення.
Всі компоненти мають однакову розмірність, відповідну речі, оброблюваному в АЛП. Регістр множника повинен мати ланцюга зсуву вправо. Суматор часткових творів повинен мати також ланцюги зсуву вправо. Причому, молодші розряди з'єднуються зі старшими розрядами регістра множника. У результаті виробляється аналіз молодшої цифри множника після чого, якщо рівні «1», то до поточного значення суми часткових привидів (який спочатку дорівнює «0») додається вміст регістра множимо. Якщо, аналізована цифра дорівнює «0», то операція додавання не виконується після цього вміст регістра множника зсувається вправо на один розряд і в звільнився старший розряд регістра множника переноситься молодший розряд суми часткових творів, в результаті зсуву її вправо по розрядній сітці. Далі триває з аналізу розряду. У результаті після закінчення операції в регістрі множника: молодший розряд результату, а в суматорі - старша частина розряду.
У даному варіанті використовується подвійна розмірність суматора часткових творів і подвійна розмірність регістру множимо. Як і в 1-му варіанті регістр множника має ланцюга зсуву вправо по розрядній сітці, а регістр множимо - вліво по розрядній сітці. Суматор часткових творів не оснащений ланцюгами зсуву. Аналогічно проводиться аналіз молодшого розряду множника, і якщо він дорівнює «1», то проводиться твір поточної суми та вмісту регістра множимо. Після цього виробляється зрушення вправо вмісту регістра множника і зрушення вліво вмісту регістра множимо. Аналогічно розглядаються варіанти зі старшим розрядом.
Суматор часткових творів має ланцюга зсуву вліво і регістри множника теж. Дії аналогічно. Якщо аналізована цифра множника дорівнює «1», то до поточного значення суми часткових творів додаються вміст регістра множимо. Виконується зсув вліво по розрядній сітці та вмісту суматора і всі до закінчення аналізу всіх розрядів множника. У результаті твір розміщується в суматорі часткового твори.
Суматор часткових творів і регістр множимо має подвійну довжину (подвійну розрядність), регістр множника - ланцюги зсуву вліво, регістр множимо - вправо. Проводиться аналіз старшого числового розряду множника, якщо він дорівнює «1», то до поточного значення суми часткових творів додається вміст регістра множимо. Вміст регістра множника зсувається вліво, а регістр множимо - вправо на один розряд. Процес триває до аналізу останнього молодшого розряду множника.
Переваги I, II, IV - можливість більш ефективно реалізовувати операцію ділення. Крім того II, IV варіанти, що мають нерухому суму часткових творів дозволяють паралельно виконувати операцію підсумовування і зсуву, що є продуктивніше.
Будемо розглядати I варіант.
Алгоритм операції множення.
Будемо вважати, що операнди представлені прямим кодом, тобто старший розряд знаковий, решта - числові.
Беруться модулі від співмножників;
Сума часткових творів покладається рівною нулю;
Аналізується молодший розряд множника, якщо значення «1», то до поточного значення суми часткових творів додається множимое;
Вміст регістра множника і суматора часткових творів зсувається вправо на одну поділку;
п.3 і п.4 повторюються для всіх розрядів множника.
Для остаточного розміщення результату в двійковому вигляді виробляють зрушення вправо на 1 розряд.
Знак результату покладається «0», якщо співмножники мають однаковий знак і «1» (негативний результат), якщо співмножники мають різні знаки. Операція не проводиться, якщо один з «0», і результат дорівнює «0».
Основа для алгоритму є: Z = X (множимое) * Y (множник)
Y - представимо як відповідні ступені
Y = ± y n-2 2 n-2 + y n-3 2 n-3 + y 0 2 0, тоді
Z = x * (y n-2 2 n-2 + y n-3 2 n-3 + y 0 2 0) = x * 2 n-1 (y n-2 2 -1 + y n-3 2 - 2 + y 0 2 - (n - 1)) =
= 2 n-1 ((..( 0 + x * y 0) z - 1 + x * y 1) * 2 - 1 + ... + x * y n-1) 2 -1 = A * 2 n -1.
Поточного значення суми часткових творів додається множимое, якщо відповідний розряд дорівнює «1» і далі суми часткових творів зсуваються вправо і т.д. Перенісши умовну крапку вправо через (n-1) розряд ми отримаємо результат.
Рг1 для прийому множимо; Рг2 для прийому множника. Вхідний РДА суматора для розміщення в ньому черговий додається компоненти до суми часткових добутків. Вхідний РДБ См використовується для розміщення поточного значення суми часткових творів. Рг2 'використовується для формування зсуву множника вправо по розрядній сітці. Вихідний РгСм, в якому формуються поточне значення суми часткових творів. Лічильник циклів використовується для відображення кількості оброблюваних розрядів множника.
На 1-му етапі виконується розміщення множимо в Рг1. Множимое може передаватися в РДА у прямому чи інверсному кодах. На 2-му етапі в Рг2 розміщується множник, що надходить по ШД. Обнуляється вміст РГВ, використовуване ви як початкове значення суми часткових творів. Далі аналізується молодша цифра множника в Рг2. Якщо вона = 1, то в РДА передається вміст Рг1 і на виході См формується поточне значення суми часткових творів. Одночасно передають множник для аналізу черговий цифри. Для цього його вміст передається в Рг2 'з зсувом вправо на 1 по розрядній сітці. У вільний розряд Рг2 'поміщається молодший розряд з входу Див Решта розряди См віддаються в РгСм із зсувом управо на 1 розряд. Після цього значення РгСм розміщується в РГВ. Вміст Рг2 'розміщується в Рг2 і значення СчЦ зменшується на 1 по відношенню до початкового значення, рівній кількості числових розрядів.
Процес триває для наступної цифри множника. Коли вміст СчЦ стає = 0, процес аналізу завершується з отриманням в РгСм старших розрядів і в Рг2 молодших розрядів твори. Після цього виконується ще 1 цикл з 0 значенням РДА для правилноє розміщення результату в розрядній сітці подвійного слова.
До цих пір ми вважали, що перемножуємо цілі невід'ємні числа. Для множення чисел із знаками, можна окремо множити модулі чисел, якщо вони записані в прямому коді, і потім формувати знак результату. Якщо негативні числа представлені у зворотному або додатковому коді, то для взяття модулів використовується додаткова операція, пов'язана з додаванням 1. Тому для множення чисел із знаками використовується практично той же алгоритм з деякими модифікаціями.
Алгоритм множення цілих чисел з використанням прямого коду для позитивних чисел і додаткового для негативних.
1.Фіксіруется знак співмножників у спеціальних тригерах.
2.Сумма часткових творів покладається = 0.
3.Аналізіруется молодша цифра множника. Якщо вона = 1, то до суми часткових добутків додається множимое в тому коді, в якому воно представлено. Якщо вона = 0, то додавання не проводиться.
4.Виполняется зрушення вправо суми часткових творів на 1 розряд, причому, якщо значення суми ≥ 0, то проводиться звичайний зрушення. Якщо поточне значення суми часткових творів <0, то проводиться модифікований зрушення з занесенням 1 в знаковий розряд.
5.Пункти 3 та 4 повторюються для всіх числових розрядів множника.
6.Якщо множник ≥ 0, то поточне значення суми часткових творів являє собою результат у прямому коді для позитивного значення і в додатковому коді для від'ємного значення. Якщо множник <0, то до поточного значення суми часткових творів необхідно додати множимое з протилежним знаком.
7.Размещеніе результатів у форматі подвійного слова шляхом зсуву суми часткових добутків вправо на 1 розряд.
Z = X * Y, Y> 0
Алгоритм той же, за винятком модифікованого зсуву. При цьому може виникнути таке: якщо молодший розряд множника = 0, а множимое <0, то немає необхідності виконувати модифікований зсуву (не можна), оскільки сума часткових творів = 0, а нуль в додатковому коді знака не має. І лише тільки з появою від'ємного значення суми часткових творів зсув повинен бути модифікованим.
Y <0
Y доп = 2 n - | Y |
Ваговий коефіцієнт: 2 n-1. Тому, якщо обчислити псевдопроізведеніе:
Z '= X * (2 n-1 - | Y |) =-X * | Y | + X * 2 n-1
Z 'більше дійсного значення на величину множимо, тому на завершальному етапі перед розміщенням результатів у форматі подвійного слова перед останнім зрушенням необхідно з результату відняти множимое. Тому при СчЦ = 0 до поточного значення суми часткових творів додають множимое з протилежним знаком.