Пристрій для обчислення скалярного добутку

Реферат: Пристрій для обчислення скалярного добутку належить до обчислювальної техніки і може бути використаний у спеціалізованих комп'ютерних системах, системах цифрової обробки сигналів та нейромережах з вертикальною обробкою даних. Пристрій містить 2m однорозрядних інформаційних входів, перший тактовий вхід, другий тактовий вхід, вхід початкової установки, m блоків формування часткових добутків, m -входовий суматор, конвеєрний регістр, суматор, регістр результату, вихід результату, регістр розрядів множника, регістр множеного, дешифратор, перший елемент АБО, другий елемент АБО, третій елемент АБО, четвертий елемент АБО, комутатор. Технічним результатом є підвищення швидкодії при обчисленні скалярного добутку, зменшення кількості макрочасткових добутків та орієнтування структури пристрою на реалізацію у вигляді надвеликої інтегральної схеми. UA 101922 C2 (12) UA 101922 C2 UA 101922 C2 5 10 15 20 25 30 35 40 45 50 55 Винахід належить до обчислювальної техніки і може бути використаний у спеціалізованих комп'ютерних системах, системах цифрової обробки сигналів та нейромережах з вертикальною обробкою даних для підвищення їхньої швидкодії при обчисленні скалярного добутку. Відомий пристрій для обчислення сум парних добутків [Цмоць І. Г., Стрямець С. П. Паралельні алгоритми та НВІС-структури обчислення суми парних добутків // Вісник НУ "Львівська політехніка" "Комп'ютерна інженерія та інформаційні технології" № 496, Львів 2003. С 255-263. Рисі.], який містить 2m регістрів, де m - кількість пар добутків, формувач часткових добутків, (m  1) -входовий суматор і регістр суми. Однак даний пристрій для свої реалізації вимагає великих затрат обладнання і великої кількості входів. Найбільш близьким до запропонованого пристрою для обчислення скалярного добутку є пристрій [Патент на корисну модель №66138, кл. G06F 7/38, 2011], який містить m однорозрядних інформаційних входів, де m - кількість пар добутків, перший тактовий вхід, другий тактовий вхід, вхід початкової установки, конвеєрний регістр, суматор, регістр результату, вихід результату, при цьому другий тактовий вхід з'єднаний з тактовими входами конвеєрного регістра та регістра результату, вхід початкової установки з'єднаний із входами скиду конвеєрного регістра та регістра результату, вихід конвеєрного регістра з'єднаний з першим входом суматора, вихід якого з'єднаний з входом регістра результату, вихід якого з'єднаний з виходом результату та зі зсувом на один розряд праворуч з другим входом суматора. Даний пристрій обчислює скалярний добуток за (n  2) тактів, де n - розрядність множників. В основу винаходу поставлено задачу створити пристрій для обчислення скалярного добутку, у якому введення нових елементів і зв'язків між ними дозволило б збільшити швидкість обчислення скалярного добутку та орієнтувало його структуру на реалізацію у вигляді надвеликої інтегральної схеми (НВІС). Поставлена задача вирішується тим, що пристрій для обчислення скалярного добутку, який містить m однорозрядних інформаційних входів, де m - кількість пар добутків, перший тактовий вхід, другий тактовий вхід, вхід початкової установки, конвеєрний регістр, суматор, регістр результату, вихід результату, при цьому другий тактовий вхід з'єднаний з тактовими входами конвеєрного регістра та регістра результату, вхід початкової установки з'єднаний із входами скиду конвеєрного регістра та регістра результату, вихід конвеєрного регістра з'єднаний з першим входом суматора, вихід якого з'єднаний з входом регістра результату, вихід якого з'єднаний з виходом результату та зі зсувом на два розряди праворуч з другим входом суматора, згідно з винаходом додатково містить m однорозрядних інформаційних входів, mвходовий суматор та m блоків формування часткових добутків, кожен з яких містить регістр розрядів множника, регістр множеного, дешифратор, чотири елементи АБО, комутатор, ,..., причому у кожному j -му ( j  1 m) блоці формування часткового добутку перший та другий інформаційні входи регістра множеного з'єднані відповідно з (2 j  1) -м та 2 j -м однорозрядними інформаційними входами, тактовий вхід регістра множеного з'єднаний з першим тактовим входом, тактовий вхід регістра розрядів множника з'єднаний з другим тактовим входом, вхід скиду регістра розрядів множника з'єднаний з входом початкової установки, прямі виходи регістра множеного з'єднані з першими інформаційними входами комутатора та із зсувом на один розряд ліворуч з другими інформаційними входами комутатора, інверсні виходи регістра множеного з'єднані з третіми інформаційними входами комутатора та із зсувом на один розряд ліворуч з четвертими інформаційними входами комутатора, п'яті інформаційні входи комутатора з'єднані з лог. 0, перший та другий інформаційні входи регістра розрядів множника з'єднані відповідно з 2 j -м та (2 j  1) -м однорозрядними інформаційними входами, перший вихід регістра розрядів множника з'єднаний з першим входом дешифратора та з третім інформаційним входом регістра розрядів множника, другий та третій виходи регістра розрядів множника з'єднані відповідно з другим та третім входами дешифратора, перший та другий входи першого елемента АБО з'єднані відповідно з другим та третім виходами дешифратора, перший та другий входи другого елемента АБО з'єднані відповідно з шостим та сьомим виходами дешифратора, перший та другий входи третього елемента АБО з'єднані відповідно з першим та восьмим виходами дешифратора, перший вхід четвертого елемента АБО з'єднаний з виходом другого елемента АБО, другий вхід четвертого елемента АБО з'єднаний з п'ятим виходом дешифратора, перший вхід управління комутатора з'єднаний з виходом першого елемента АБО, другий вхід управління комутатора з'єднаний з четвертим виходом дешифратора, третій вхід управління комутатора з'єднаний з виходом другого елемента АБО, четвертий вхід 1 UA 101922 C2 управління комутатора з'єднаний з п'ятим виходом дешифратора, п'ятий вхід управління комутатора з'єднаний з виходом третього елемента АБО, вихід четвертого елемента АБО з'єднаний з (n  2) -м входом j -ї групи входів m -входового суматора, де n - розрядність 5 10 ,.., множеного, i -й вихід комутатора j -го блока формування часткового добутку (i  1 n  1) з'єднаний з i -м входом j -ї групи входів m -входового суматора, вихід якого з'єднаний з входом конвеєрного регістра. Введення в пристрій m однорозрядних інформаційних входів, m -входового суматора та m блоків формування часткових добутків, кожний з яких містить регістр розрядів множника, регістр множеного, дешифратор, чотири елементи АБО та комутатор забезпечило зменшення в два рази кількості макрочасткових добутків, що вдвічі зменшило час обчислення скалярного добутку і орієнтувало структуру пристрою на реалізацію у вигляді надвеликої інтегральної схеми (НВІС). На кресленні представлена схема пристрою для обчислення скалярного добутку, де: 11,...12m  2m 15 20 однорозрядних інформаційних входів, 2 - перший тактовий вхід, 3 - другий тактовий вхід, 4 - вхід початкової установки, 5i ,...5m , блоків формування часткових добутків, 6- m входовий суматор, 7 - конвеєрний регістр, 8 - суматор, 9 - регістр результату, 10 - вихід результату, 11 - регістр розрядів множника, 12 - регістр множеного, 13 - дешифратор, 14 перший елемент АБО, 15 - другий елемент АБО, 16 - третій елемент АБО, 17 -четвертий елемент АБО, 18 - комутатор. Пристрій для обчислення скалярного добутку містить 2m однорозрядних інформаційних входів 11,...12m , перший тактовий вхід 2, другий тактовий вхід 3, вхід початкової установки 4, m блоків формування часткових добутків 5i ,...5m , m -входовий суматор 6, конвеєрний регістр 7, суматор 8, регістр результату 9, вихід результату 10, регістр розрядів множника 11, регістр множеного 12, дешифратор 13, перший елемент АБО 14, другий елемент АБО 15, третій елемент АБО 16, четвертий елемент АБО 17, комутатор 18. 25 5 У кожному j -у блоці формування часткових добутків j ,- перший та другий інформаційні входи регістра множеного 12 з'єднані відповідно з (2j  1) -м та 2j -м однорозрядними 1 30 35 1 40 45 50 1 інформаційними входами 2 j 1 та 2 j , тактовий вхід регістра множеного 12 з'єднаний з першим тактовим входом 2, тактовий вхід регістра розрядів множника 11 з'єднаний з другим тактовим входом 3, вхід скиду регістра розрядів множника 11 з'єднаний з входом початкової установки 4, прямі виходи регістра множеного 12 з'єднані з першими інформаційними входами комутатора 18 та із зсувом на один розряд ліворуч з другими інформаційними входами комутатора 18, інверсні виходи регістра множеного 12 з'єднані з третіми інформаційними входами комутатора 18 та із зсувом на один розряд ліворуч з четвертими інформаційними входами комутатора 18, п'яті інформаційні входи комутатора 18 з'єднані з лог. 0, перший та другий інформаційні входи регістра розрядів множника 11 з'єднані відповідно з 2j -м та (2j  1) -м однорозрядними 1 інформаційними входами 2 j та 2 j 1 , перший вихід регістра розрядів множника 11 з'єднаний з першим входом дешифратора 13 та з третім інформаційним входом регістра розрядів множника 11, другий та третій виходи регістра розрядів множника 11 з'єднані відповідно з другим та третім входами дешифратора 13, перший та другий входи першого елемента АБО 14 з'єднані відповідно з другим та третім виходами дешифратора 13, перший та другий входи другого елемента АБО 15 з'єднані відповідно з шостим та сьомим виходами дешифратора 13, перший та другий входи третього елемента АБО 16 з'єднані відповідно з першим та восьмим виходами дешифратора 13, перший вхід четвертого елемента АБО 17 з'єднаний з виходом другого елемента АБО 15, другий вхід четвертого елемента АБО 17 з'єднаний з п'ятим виходом дешифратора 13, перший вхід управління комутатора 18 з'єднаний з виходом першого елемента АБО 14, другий вхід управління комутатора 18 з'єднаний з четвертим виходом дешифратора 13, третій вхід управління комутатора 18 з'єднаний з виходом другого елемента АБО 15, четвертий вхід управління комутатора 18 з'єднаний з п'ятим виходом дешифратора 13, п'ятий вхід управління комутатора 18 з'єднаний з виходом третього елемента АБО 16, вихід четвертого елемента АБО 17 з'єднаний з (n  2) -м входом j -ї групи входів m -входового ,..., суматора 6, i -й вихід комутатора 18 у-го блока формування часткового добутку 5j(i  1 n  1) з'єднаний з i -м входом j -ї групи входів m-входового суматора 6, вихід якого з'єднаний з входом конвеєрного регістра 7, вихід якого з'єднаний з першим входом суматора 8, вихід якого з'єднаний з входом регістра результату 9, вихід якого з'єднаний з виходом результату 10 та зі 2 UA 101922 C2 зсувом на два розряди праворуч з другим входом суматора 8, другий тактовий вхід 3 з'єднаний з тактовими входами конвеєрного регістра 7 та регістра результату 9, вхід початкової установки 4 з'єднаний із входами скиду конвеєрного регістра 7 та регістра результату 9. Пристрій для обчислення скалярного добутку працює наступним чином. m Z 5 A B j j  A 1B1  A 2B 2  ...  A mBm j i Обчислення скалярного добутку здійснюється за два  n  1 r   2  тактів (де n - розрядність операндів A j і B j , етапи. На першому етапі за   - операція округлення до найближчого більшого цілого числа), починаючи з молодших розрядів, A 10 виконується накопичення множених j по два розряди за такт у регістрах множеного 12. ,..., На другому етапі у кожному g  y (g  1 r ) такті роботи відбувається формування макрочасткових добутків шляхом додавання часткових добутків, що формуються у кожному блоці формування часткового добутку 5 за модифікованим алгоритмом Бута. За даним Bj алгоритмом множники розбиваються на групи з трьох розрядів так, що сусідні групи мають B 15 один спільний розряд. Розбиття множника j на групи здійснюється з молодших розрядів, причому молодший розряд наймолодшої групи завжди доповнюється нулем. Множення чисел за алгоритмом Бута виконується так: r C 2  2(r  g) A(B 2(r  g 1)  2  B 2(r  g 1) 1B 2(r  g 1) ) g 1 . Для кожної g-ї групи розрядів множника Aj добутку здійснюється множенням визначається як сума ваг 20 (B2(r  g 1)  2B2(r  g 1) 1B2(r  g 1) ) де (B2(r  g 1)  2B2(r  g 1) 1B2(r  g 1) ) формування часткового Kg K на відповідний коефіцієнт . Значення коефіцієнта g ненульових цифр групи розрядів множника B 2(r  g 1)  2 має вагу мінус два, а B 2(r  g 1) 1 та B 2(r  g 1) - одиницю, відповідно до виразу: 2, колиB 2(r  g 1)  2  0, B 2(r  g 1)  2  1;   1, колиB 2(r  g 1)  2  0, B 2(r  g 1) 1  B 2(r  g 1) ;   K g   0, коли, B 2(r  g 1)  2  B 2(r  g 1) 1  B 2(r  g 1) ;   1, колиB , 2(r  g 1)  2  1 B 2(r  g 1) 1  B 2(r  g 1) ;   2, колиB 2(r  g 1)  2  1, B 2(r  g 1) 1  B 2(r  g 1)  0.  Операція множення на два реалізовується зсувом на один розряд ліворуч, а зміна знаку інверсією всіх розрядів множеного з наступним додаванням одиниці до молодшого розряду. 25 Формування макрочасткового добутку Pg здійснюється шляхом додавання m всіх m m Pg  часткових добутків Pig P jg j 1 згідно з формулою . Обчислення результату скалярного P добутку Z здійснюється шляхом накопичення макрочасткових добутків g згідно з формулою Z g  2 2 Z g 1  Pg 30 . Перед початком роботи імпульсом початкової установки, який надходить із входу початкової установки 4, конвеєрний регістр 7, регістр результату 9 та регістри розрядів множника 11 у всіх 5 блоках формування часткових добутків j встановлюються в нуль. На першому етапі роботи в кожному g -y такті на перший та другий інформаційні входи 5 регістра множеного 12 j -гo блока формування часткових добутків j надходять (2g  1) -й та 2g A 35 j й розряди множених , починаючи з молодших розрядів. Тактовим імпульсом із першого тактового входу 2 здійснюється запис та зсув даних у регістрі множеного 12. Після r тактів у регістрах множених 12 кожного блока формування часткових добутків множені Aj . 3 5j будуть записаніUA 101922 C2 На другому етапі роботи у кожному блоці формування часткових добутків 1 5j в g -y такті 1 інформація із однорозрядних інформаційних входів 2 j та 2 j 1 , а також із першого виходу регістра розрядів множника 11, записується відповідно у перший, другий та третій розряди регістра розрядів множника 11. Дана інформація ( 2g -й, ( 2g -й та ( 2g  2 )-й розряди множника j ) надходить на входи дешифратора 13, який формує сигнали управління комутатором B 5 18  10000(B 2(r  g 1)  2  0,B 2(r  g 1) 1  B 2(r  g 1) ) 01000(B 2(r  g 1)  2  1,B 2(r  g 1) 1  B 2(r  g 1) ) 00001(B 2(r  g 1)  2  B 2(r  g 1) 1  B 2(r  g 1) ) 01000(B 2(r  g 1)  2  0,B 2(r  g 1) 1  B 2(r  g 1)  1) , 00010(B 2(r  g 1)  2  1 B 2(r  g 1) 1  B 2(r  g 1)  0) , , і Комутатор 18, у залежності від сигналів, які надходять на його входи управління, встановлюється в положення, коли на його вихід надходить значення 10 , (сигнал управління - 10000) або значення 2A j (сигнал управління - 01000), або значення ( Aj A j ) 2A j (сигнал управління - 00100), або значення ( ) (сигнал управління - 00010), або значення логічного нуля (сигнал управління - 00001). На виході елемента АБО 17 формується сигнал логічного нуля (при сигналах управління 10000, 01000, 00001) або логічної одиниці (при сигналах управління 00100 і 00010). На виході m - входового суматора 6 шляхом додавання 15 інформації з виходів блоків формування часткових добутків 5j (інформації з комутатора 18 та P елемента АБО 17) формується g -й макрочастковий добуток g . Сформований макрочастковий добуток записується у конвеєрний регістр 7. Інформація з виходів конвеєрного регістра 7 додається на суматорі 8 до раніше накопиченої суми зсунутої на два розряди праворуч. Результат обчислення скалярного добутку отримаємо на виході 10 після ( r  2 ) тактів. 20 ФОРМУЛА ВИНАХОДУ 25 30 35 40 45 50 Пристрій для обчислення скалярного добутку, який містить m однорозрядних інформаційних входів, де m - кількість пар добутків, перший тактовий вхід, другий тактовий вхід, вхід початкової установки, конвеєрний регістр, суматор, регістр результату, вихід результату, при цьому другий тактовий вхід з'єднаний з тактовими входами конвеєрного регістра та регістра результату, вхід початкової установки з'єднаний із входами скиду конвеєрного регістра та регістра результату, вихід конвеєрного регістра з'єднаний з першим входом суматора, вихід якого з'єднаний з входом регістра результату, вихід якого з'єднаний з виходом результату та зі зсувом на два розряди праворуч з другим входом суматора, який відрізняється тим, що додатково містить m однорозрядних інформаційних входів, m - входовий суматор та m блоків формування часткових добутків, кожен з яких містить регістр розрядів множника, регістр множеного, дешифратор, чотири елементи АБО, комутатор, причому у кожному j -му ( j  1,..,m) блоці формування часткового добутку перший та другий інформаційні входи регістра множеного з'єднані відповідно з (2 j  1) -м та 2 j -м однорозрядними інформаційними входами, тактовий вхід регістра множеного з'єднаний з першим тактовим входом, тактовий вхід регістра розрядів множника з'єднаний з другим тактовим входом, вхід скиду регістра розрядів множника з'єднаний з входом початкової установки, прямі виходи регістра множеного з'єднані з першими інформаційними входами комутатора та із зсувом на один розряд ліворуч з другими інформаційними входами комутатора, інверсні виходи регістра множеного з'єднані з третіми інформаційними входами комутатора та із зсувом на один розряд ліворуч з четвертими інформаційними входами комутатора, п'яті інформаційні входи комутатора з'єднані з лог. 0, перший та другий інформаційні входи регістра розрядів множника з'єднані відповідно з 2 j -м та (2 j  1) -м однорозрядними інформаційними входами, перший вихід регістра розрядів множника з'єднаний з першим входом дешифратора та з третім інформаційним входом регістра розрядів множника, другий та третій виходи регістра розрядів множника з'єднані відповідно з другим та третім входами дешифратора, перший та другий входи першого елемента АБО з'єднані відповідно з другим та третім виходами дешифратора, перший та другий входи другого елемента АБО з'єднані відповідно з шостим та сьомим виходами дешифратора, перший та другий входи третього елемента АБО з'єднані відповідно з першим та восьмим виходами дешифратора, перший вхід четвертого елемента АБО з'єднаний з виходом другого елемента 4 UA 101922 C2 5 АБО, другий вхід четвертого елемента АБО з'єднаний з п'ятим виходом дешифратора, перший вхід управління комутатора з'єднаний з виходом першого елемента АБО, другий вхід управління комутатора з'єднаний з четвертим виходом дешифратора, третій вхід управління комутатора з'єднаний з виходом другого елемента АБО, четвертий вхід управління комутатора з'єднаний з п'ятим виходом дешифратора, п'ятий вхід управління комутатора з'єднаний з виходом третього елемента АБО, вихід четвертого елемента АБО з'єднаний з (n  2) -м входом j -ї групи входів m -входового суматора, де n - розрядність множеного, i -й вихід комутатора j -го блока формування часткового добутку (i=1,…, n+1) з'єднаний з i -м входом j -ї групи входів m - входового суматора, вихід якого з'єднаний з входом конвеєрного регістра. Комп’ютерна верстка Л. Бурлак Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5