Паралельний підсумовуючий пристрій

Паралельний підсумовуючий пристрій, який містить блоки віднімання групи, блок порівняння, блок послідовного підсумовування, причому входи групи пристрою з'єднані з першими входами блоків віднімання групи, другі входи яких з'єднані з виходом блока порівняння, перші виходи підключені до першої групи входів даних блока порівняння і до перших входів ВІДПОВІДНИХ блоків віднімання групи, а другі виходи підключені до ВІДПОВІДНИХ знакових входів групи блока послідовного підсумовування, вхід якого з'єднаний з виходом блока порівняння, а вихід є виходом пристрою, який відрізняється Винахід відноситься до обчислювальної техніки і може бути використаний в обчислювальних пристроях для паралельного підсумовування масиву чисел Відомо підсумовуючий пристрій [а с СРСР №1396139, кл G06F7/50, 1986], який містить постійний запам'ятовуючий блок, першу та другу групи елементів І, групу елементів затримки, перетворювач двійкового коду в ущільнений код, групу елементів НІ, причому перші входи елементів І першої групи підключені до входу синхронізації пристрою, входи першої групи перетворювача двійкового коду в ущільнений код з'єднані з виходами ВІДПОВІДНИХ елементів затримки групи, виходи перетворювача двійкового коду в ущільнений код із п - го по другий(де п = 2 т - 1, т -КІЛЬКІСТЬ операндів) з'єднані з першими входами ВІДПОВІДНИХ елементів І другої групи з (п - 1)-го по перший, причому інформаційні входи пристрою з'єднані з другими входами ВІДПОВІДНИХ елементів І першої групи, входи елементів НІ групи з'єднані з ВІДПОВІДНИМИ виходами перетворювача двійкового коду в тим, що містить вхід синхронізації пристрою, який з'єднаний з тактованими входами блоків віднімання групи і блока порівняння, а також вхід керування пристрою, який підключений до ВІДПОВІДНИХ входів блоків віднімання групи, крім того, другі виходи блоків віднімання групи з'єднані з другою групою входів блока порівняння, причому блок порівняння містить N схем порівняння першого рівня, де N=[n/2], n - розмірність вхідного числового масиву, та вузли порівняння наступних з Іодгп рівнів, причому входи J-OI схеми порівняння першого рівня підключені попарно до першої і другої групи входів блока порівняння, де j = 1,N, а виходи схем порівняння попереднього рівня, починаючи з першого рівня з'єднані попарно з входами вузлів порівняння наступного рівня, причому вихід вузла порівняння останнього (Іод2п)-ого рівня є виходом блока порівняння, а кожна схема порівняння першого рівня містить вузол перетворення і вузол порівняння ущільнений код, виходи елементів НІ групи, крім п - го, з'єднані з другими входами ВІДПОВІДНИХ елементів І другої групи, адресні входи постійного запам'ятовуючого блока з'єднані ВІДПОВІДНО З виходами п - го елемента НІ групи, виходами елементів І другої групи та першим виходом перетворювача двійкового коду в ущільнений код, перший розрядний вихід постійного запам'ятовуючого блока з'єднаний з виходом результату пристрою, а ІНШІ розрядні виходи підключені до входів ВІДПОВІ ДНИЙ елементів затримки групи, виходи елементів І першої групи з'єднані ВІДПОВІДНО З входами другої групи перетворювача двійкового коду в ущільнений код Недоліком відомого пристрою є значний час підсумовування через необхідність виконання таких операцій як перетворення двійкового коду в ущільнений код, а потім в унітарний код та зчитування результату з постійного запам'ятовуючого блока Відомо асоціативний підсумовуючий пристрій [а с СРСР №1424011, кл G06F7/50, 1986], який (О 00 ю ю 55861 містить асоціативний запам'ятовуючий блок, три групи елементів І, елемент І, групу елементів затримки, регістр зберігання переносу, групу регістрів зсуву, регістр проміжного результату та постійний запам'ятовуючий блок, причому вхід молодшого розряду регістра проміжного результату з'єднаний із виходом результату асоціативного запам'ятовуючого блока і з виходом результату двійкового підсумовування пристрою, виходи розрядів регістра проміжного результату з'єднані з першими входами елементів І першої групи, виходи яких підключені до адресних входів постійного запам'ятовуючого блока, перший вихід якого з'єднаний з виходом результату десяткового підсумовування пристрою, ІНШІ виходи постійного запам'ятовуючого блока з'єднані з входами розрядів регістра зберігання переносу, вихід якого підключений до першого входу елемента І, другий вхід якого з'єднаний з першою шиною синхронізації пристрою та тактовими входами регістрів зсуву групи та регістра зберігання переносу, входи розрядів кожного регістра зсуву групи з'єднані з входами розрядів ВІДПОВІДНОГО операнда пристрою, виходи регістрів зсуву групи з'єднані з першими входами елементів І другої групи, другі входи яких підключені до першої шини синхронізації пристрою, виходи асоціативного запам'ятовуючого блока з'єднані через ВІДПОВІДНІ елементи затримки групи з першими входами елементів І третьої групи, виходи яких підключені до перших входів признаку асоціативного запам'ятовуючого блока, другі входи елементів І першої групи з'єднані з другою шиною синхронізації пристрою, виходи елементів І другої групи з'єднані з другими входами признаку асоціативного запам'ятовуючого блока, вихід елемента підключений до третього входу признаку асоціативного запам'ятовуючого блока, тактовий вхід регістра проміжного результату з'єднаний з першою шиною синхронізації пристрою На відомому пристрої виконується одночасне підсумовування багатьох чисел за рахунок лічби КІЛЬКОСТІ одиниць у розрядних зрізах і підсумовування отриманих кодів із зсувом у часі на асоціативному підсумовуючому блоці, що потребує значних часових витрат Найбільш близьким по технічній суті до пристрою, який пропонується, є пристрій [а с СРСР №1119035, кл G06G7/14, 1984], який містить блоки порівняння групи, іміновані в подальшому як блоки віднімання групи, блок порівняння, блок послідовного підсумовування, причому входи групи пристрою з'єднані з першими входами блоків віднімання групи, другі входи яких з'єднані з виходом блока порівняння, перші виходи підключені до ВІДПОВІДНИХ входів блока порівняння і до перших входів ВІДПОВІДНИХ блоків віднімання групи, а другі виходи підключені до ВІДПОВІДНИХ входів групи блока послідовного підсумовування, вхід якого з'єднаний з виходом блока порівняння, а вихід підключений до виходу пристрою Відомий пристрій реалізує паралельне додавання групи операндів, представлених тривалостями часових інтервалів, але час виконання цієї операції залежить від розмірності більшої тривалості і тому може бути значним В основу винаходу поставлено задачу ство рення паралельного підсумовуючого пристрою, в якому за рахунок введення нових елементів та зв'язків МІЖ НИМИ досягається можливість прискорення виконання операції паралельного підсумовування, що призводить до підвищення швидкодії пристрою Поставлена задача вирішується тим, що в підсумовуючий пристрій, який містить блоки віднімання групи, блок порівняння, блок послідовного підсумовування, причому входи групи пристрою з'єднані з першими входами блоків віднімання групи, другі входи яких з'єднані з виходом блока порівняння, перші виходи підключені до першої групи входів даних блока порівняння і до перших входів ВІДПОВІДНИХ блоків віднімання групи, а другі виходи підключені до ВІДПОВІДНИХ знакових входів групи блока послідовного підсумовування, вхід якого з'єднаний з виходом блока порівняння, а вихід є виходом пристрою, введені вхід синхронізації пристрою, який з'єднаний зтактованими входами блоків віднімання групи і блока порівняння, а також вхід керування пристрою, який підключений до ВІДПОВІДНИХ входів блоків віднімання групи, крім того, другі виходи блоків віднімання групи з'єднані з другою групою входів блока порівняння, причому блок порівняння містить N схем порівняння першого рівня, де N = [n/2], n - розмірність вхідного числового масиву, та вузли порівняння наступних з Іодгп рівнів, причому входи J-OI схеми порівняння першого рівня підключені попарно до першої і другої групи входів блока порівняння, де J = 1.Nj a виходи схем порівняння попереднього рівня, починаючи з першого рівня з'єднані попарно з входами вузлів порівняння наступного рівня, причому вихід вузла порівняння останнього (Іод2п)-ого рівня є виходом блока порівняння, а кожна схема порівняння першого рівня містить вузол перетворення і вузол порівняння На фіг 1 представлена структурна схема підсумовуючого пристрою, на фіг 2 подана функціональна схема блока віднімання групи, на фіг 3, 4 5 подано функціональні схеми вузлів блока порівняння, на фіг 6 подана функціональна схема блока послідовного підсумовування Пристрій(фіг 1) містить входи 1 1 , , 1 П , блоки 1 2 , ,2П віднімання, блок 3 порівняння, блок 4 послідовного підсумовування, вихід 5 пристрою Перші входи блоків 21, ,2П віднімання з'єднані з входами 1 1 , , 1 П пристрою і першими виходами б1, ,6П блоків 21, , 2П віднімання ВІДПОВІДНО, другі входи яких підключені до виходу 7 блока 3 порівняння Виходи 81, , 8П блоків 21, , 2П віднімання підключені до групи входів 91, ,9П блока 4 послідовного підсумовування і до групи входів 101, ,10п блока 3 порівняння, а вихід 7 блока 3 порівняння з'єднаний також із входом блока 4 послідовного підсумовування, вихід якого є виходом 5 пристрою Крім того, виходи б1, , 6П блоків 21, , 2П віднімання з'єднані з групою входів 11 1 , ,11 П блока 3 порівняння Тактовані входи блоків 21, , 2П віднімання і блоку 3 порівняння підключені до входу 12 синхронізації пристрою, вхід 13 керування якого з'єднаний з ВІДПОВІДНИМИ входами блоків 21, ,2П віднімання Кожний блок 2і віднімання(фіг 2) містить входи 55861 і 1 , ,1'm і 7-і, ,7 m , мультиплексор 14, групу інверторів 15-І, , 1 5 т , суматор 16 і групу D - тригерів 17і 17 т +і де т - розрядність операндів Входи 7і , 7 т підключені до входів групи інверторів 15і„ , 1 5 т , входи і ' і , , і ' т з'єднані з першою групою входів мультиплексора 14, m виходів якого підключені до першої групи входів суматора 16, виходи групи інверторів 15-І, , 1 5 т з'єднані з другою групою входів суматора 16, на вхід перенесення якого (CR) постійно подається " 1 " через резистор 18 D - входи D - тригерів 17і, , 1 7 т з'єднані з ВІДПОВІДНИМИ виходами суматора 16, а виходи D і - тригерів 17 є виходами б\, ,6' m блока 2 порівняння С - входи D - тригерів 17і 1 7 т підключені до входу 12 синхронізації пристрою, друга група входів мультиплексора 14 з'єднана з виходами б'і, ,6'm D - тригерів 17-І, , 1 7 т , а керуючий вхід мультиплексора 14 підключений до входу керування 13 пристрою D - вхід D -тригера 17 т +і з'єднаний з виходом перенесення (CR1) суматора 16, а а вихід являється виходом 8 і блока 2 і порівняння Блок 3 порівняння(фіг 3) містить N схем 19 порівняння першого рівня, де N = [n/2], n - розмірність вхідного числового масиву, та вузли 20 порівняння наступних з Іодгп рівнів, причому входи J-OI схеми 19 і порівняння підключені до входів 10 ] 10 2) , ZJ |2J 11|2J, 11 Z J , де J - 1 , N , а виходи 21 J схем 19J порівняння з'єднані попарно з входами вузлів 20 порівняння наступного рівня і так далі Вихід вузла 20 порівняння останнього (Іод2п)-ого рівня є виходом 7 блока 3 порівняння Крім того, кожна схема 19 порівняння містить вузол 22 перетворення і вузол 20 порівняння Вузол 22 перетворення блока 3 порівняння(фіг 4) містить входи 10 і . 1 U , 1 "І 1, , 11 m і ,23 і if 1 , 1 1 l + 1 m І ВИХОДИ 23 і 23 I виходи і І+1 причому входи 10 І 1 0 з'єднані з входами елемента РІВНОЗНАЧНОСТІ 24, вихід якого сполучений з D-входом D - тригера 25, а його прямий та інверсний виходи з'єднані ВІДПОВІДНО З входами R груп і D -тригерів 26і ,2б2т і 27-І, 272т Також входи 10 І+1 і 10 з'єднані ВІДПОВІДНО з входами JK -тригера 28 і елемента АБО-НІ 29, крім того входи 1 1 \ , 1 1 ' т , |+1 1+1 11 і, , 1 1 т з'єднані з першими входами елементів І ЗО-і, ,302т та АБО 311, ,312т Вихід елемента АБО-НІ 29 під'єднаний до других входів елементів І ЗОі ,302т, виходи яких з'єднані ВІДПОВІДНО з D - входами групи D - тригерів 26і ,2б2т Прямий та інверсний виходи JK - тригера 28 з'єднані ВІДПОВІДНО з другими входами елементів АБО 311, , 3 1 т , 31 т+1 ,ЗІ2т, Э IX ВИХОДИ З'ЄДНЗНІ ВІДПОВІДНО з D-входами групи D - тригерів 27і ,27 т , 27 т +і, ,272т, С - входи групи D - тригерів 26і ,2б2т і 27-І, ,272т і D - тригера 25 підключені до входу 12 синхронізації пристрою, а виходи груп D - тригерів 26і ,2б2т і 27-І, ,272т під'єднані ВІДПОВІДНО до перших та других груп входів елементів АБО 32і, , 3 2 2 т , виходи 23'і„ ,23' т , 23 І + 1 і , , 2 3 1 + 1 т яких являються виходами вузла 22 перетворення схем 19 порівняння блока 3 порівняння Вузол 20 порівняння блока 3 порівняння(фіг 5) містить входи 23'і ,23 1 m 2 3 | T ' i , , 2 3,1+1 m ' які з'єднанні ВІДПОВІДНО з групою входів двох елементів АБО 34, виходи яких з'єднані з керуючими вхо і І дами мультиплексорів 35 І 3 5 Крім того, вузол 20 порівняння містить групу елементів НІ Збі , Зб2т групу елементів 2АБО-І 37і , 3 7 т групу елементів 2І-АБО 38і , 3 8 т елемент НІ 39, групи елементів І 40-І, , 4 0 т , І 411, , І 41 т , групу елементів АБО 421 , 4 2 т Перший вихід мультиплексора |+1 35 з'єднаний з входом елемента НІ Збі другий вихід з'єднаний з входом елемента НІ Збз і першим входом елемента 2АБО-І 37і третій вихід з'єднаний з входом елемента НІ З65 і першим входом елемента 2АБО-І 37г і т д , а m-й вихід з'єднаний з входом елемента НІ Збгт і і першим входом елемента 2АБО-І 3 7 т і Перший вихід мультиплексора і 35 підключений до першого входу елемента 2ІАБО 38-І, другий вихід підключений до входу елемента НІ Збг і третіх входів елементів 2АБО-І 37і і 21-АБО 38-І, третій вихід підключений до входу елемента НІ З64 і до третіх входів елементів 2АБО-І 372 і 2І-АБО З82 і т д , а m-й вихід підключений до входу елемента НІ Збгт 2 і до третіх входів елементів 2АБО-І 3 7 т і і 21-АБО 3 8 т і Вихід елемента НІ Збі з'єднаний з третім входом елемента 2І-АБО 38і виходи елементів НІ Збгк, де к-1,т 1^ з'єднані з другими входами елементів 2АБО-І 37і , 3 7 т і, а виходи елементів НІ Збгк+і з'єднані з четвертими входами елементів 2АБО-І 37і , 3 7 т і і 2І-АБО З82, , 3 8 т і і п'ятим входом елемента 2І-АБО 38і Виходи елементів 2АБО-І 37і , 3 7 т і підключені до других входів ВІДПОВІДНО елементів 2І-АБО 38і , 3 8 т і , а перші входи елементів 2І-АБО З82, , 3 8 т і з'єднані ВІДПОВІДНО З виходами попередніх елементів 2І-АБО 38і, , 3 8 т Вихід елемента 2І-АБО 3 8 т і групи є виходом схеми для порівняння слів і з'єднаний з першими входами групи елементів І 40і , 4 0 т та через елемент НІ 39 з першими входами групи елементів І 411, , 4 1 т Другі входи груп елементів І 40-І, , 4 0 т та І 411, 4 1 т з'єднані ВІДПОВІДНО З групами виходів мультиплексорів 35 і , 3 5 І + 1 ВИХОДИ груп елементів І 40і , 4 0 т і І 411 , 4 1 т з'єднані ВІДПОВІДНО З першими та другими входами групи елементів АБО 42-І, , 4 2 т , виходи 211, , 2 1 т яких є виходами схеми 19 порівняння блока 3 порівняння Блок 4 послідовного підсумовування(фіг 6) МІСТИТЬ входи 9 1 , ,9 П і входи 7-і, , 7 т , які з'єднані ВІДПОВІДНО з інверсними і прямими з входами груп и ( т + 1)-розрядних елементів І 43і ,43 П , виходи яких з'єднані попарно з входами першої групи суматорів 44-І, ,44[П/2], а виходи яких з'єднані з входами наступної групи суматорів 44і, ,44[п/4] і так далі Остання [Iog2n]-a група складається з одного суматора 44, вихід якого з'єднаний з першим входом суматора 45, другий вхід якого підключений до виходу регістра 46, а вихід до входу регістра 46 Вихід регістра 46 є виходом 5 пристрою Паралельний підсумовуючий пристрій(фіг 1) працює таким чином Розглянемо приклад паралельного підсумовування масиву з п'яти чисел Підсумовуються числа, що дорівнюють 1 1 , 3, 5, 8, 15 П'ять чисел подаються ВІДПОВІДНО на входи 1 1 - 1 5 , утворюючи початковий масив для підсумовування Оскільки В початковому стані на виході блока З присутній нульовий сигнал, то в першій дії підсумовування від кожного початкового числа відніма 55861 ється нуль з блока 3, і на виходах б 1 - б 5 блоків 2 1 2 5 отримують різниці, фактично рівні початковим числам 1 1 , 3, 5, 8, 15, які паралельно подаються по п'яти входах 1 1 1 - 1 1 5 на блок 3, де відбувається виділення найменшого числа з п'яти початкових чисел, яке дорівнює 3, та подається на вхід блока 4 Разом з тим з виходів 8 1 - 8 5 блоків 2 1 - 2 5 на входи 9 1 - 9 5 блока 4 подаються сигнали ознак, що дорівнюють нулю при наявності ненульової додатньої інформації на виходах б 1 - б 5 ВІДПОВІДНИХ блоків 2 1 - 2 , тобто при наявності ненульової додатньої різниці у поточній дії Таким чином, у блоці 4 відбувається інвертування сигналів ознак з входів 9 - 9 5 і утворення п'ятикратного мінімального числа, що дорівнює 15, кратність якого визначається КІЛЬКІСТЮ ненульових додатніх чисел першого масиву В другій дії в блоках 2 1 - 2 5 формуються різниці між початковими числами 1 1 , 3, 5, 8, 15 та мінімальним числом першого масиву, що дорівнює трьом Утворюються різниці 8, 0, 2, 5, 12 другого масиву Найменше ненульове значення числа другого масиву, що дорівнює двом, формується в блоці 3, а далі подається до блока 4, де підсумовується в чотирикратному розмірі, тобто формується часткова сума чисел 8, кратність якої визначається КІЛЬКІСТЮ ненульових додатніх чисел другого масиву Поточна часткова сума додається до попередньої проміжної суми і формується поточна проміжна сума 23 В третій дії в блоках 2 1 - 2 5 формуються різниці між числами 8, 0, 2, 5, 12 другого масиву та мінімальним числом другого масиву Утворюються різниці 6, -2, 0, 3 та 10 третього масиву Мінімальне число третього масиву дорівнює трьом, оскільки від'ємне число не приймає участь у порівнянні Мінімальне число з блока 3 подається до блока 4, де формується поточна сума в трикратному розмірі, що дорівнює 9, кратність якої визначається КІЛЬКІСТЮ ненульових додатніх чисел третього масиву Далі вона додається до попередньої проміжної суми і формується поточна проміжна сума 32 В четвертій дії в блоках 2 1 - 2 5 формуються різниці між числами 6, -2, 0, 3 та 10 третього масиву та мінімальним числом третього масиву, що дорівнює трьом Утворюються різниці 3, -, -, 0, та 7 Далі всі ВІД'ЄМНІ числа, величини яких не мають значення при порівнянні, позначаються рискою Мінімальне число четвертого масиву, що дорівнює трьом, формується в блоці 3, подається до блоку 4, де формується поточна сума в двократному розмірі, що дорівнює 6, а також поточна проміжна сума 38 В п'ятій ДІЇ В блоках 2 1 - 2 5 формуються різниці між числами 3, -, -, 0, 7 четвертого масиву та мінімальним числом 3 четвертого масиву Утворюються різниці 0, -, -, -, 4 п'ятого масиву Мінімальне число п'ятого масиву, що дорівнює чотирьом, формується в блоці 3, подається до блоку 4, де формується поточна сума, що дорівнює 4 Оскільки тепер всі елементи шостого масиву -, -, -, -, 0 дорівнюють нулю або ВІД'ЄМНІ, процес підсумовування припиняється і формується остаточна сума, яка дорівнює 42 Блок 2 і віднімання(фіг 2) працює таким чином 8 Спочатку мультиплексор 14 встановлюється по входу 13 керування для передавання на вхід інформації з m-розрядного входу 1 і пристрою, інформація якого подається на перший вхід суматора 16, на другий вхід якого подається інверсна інформація з виходу 7 блока 3 порівняння Крім того, на вхід перенесення CR суматора 16 завжди подається одиниця Таким чином, суматор 16 працює в режимі віднімання В результаті різниця з виходу суматора 16 подається на інформаційні входи групи D - тригерів 17і , 1 7 т при появі синхроімпульсу на їх С - входах з входу синхронізації пристрою 12 Після ЦЬОГО мультиплексор 14 працює на передавання інформації, що поступає на його другу групу входів з виходів D - тригерів 17-І, , 1 7 т Таким чином, суматор 16 в подальшому формує різницю, де зменшуване є число, що знаходиться в групі D - тригерів 17-І, , 1 7 т , а від'ємником є число, що подається з виходу 7 блока 3 порівняння Крім того, інформація з виходу 6 і групи D - тригерів 17і , 1 7 т подається на вхід 1 1 і блока З порівняння, а вихід D - тригера 17 т +і є виходом 8 і блока 2 і порівняння, на якому формується знак поточної різниці Блок 3 порівняння(фіг 3) працює в такий спосіб Дані з входів 10 1 , , 10 п і 11 1 і ,11 п т надходять на входи групи ( 2 т + 2)-розрядних схем 19 порівняння першого рівня, кожна з яких МІСТИТЬ вузол 22 перетворення і вузол 20 порівняння Спочатку дані обробляються вузлом 22 перетворення, який дані зі знаком "+" залишає незмінними, а дані зі знаком "-" обнуляє, а потім вузлом 20 порівняння, який визначає з двох поточних чисел мінімальне 1 N Виходи схем 19 , ,19 порівняння (де N = [п/2]) попарно під'єднані до входів вузлів 20 порівняння, які в свою чергу також попарно з'єднані Таким чином, дані обробляються на всіх (Іодгп) - рівнях обробки ВИХІД 7 останнього, (Іодгп) - ого вузла20 є виходом блока 3 порівняння Вузол 22 перетворення блока 3 порівняння(фіг4) працює таким чином Спочатку данні з входів 10 і І 10 І + 1 надходять до елемента РІВНОЗНАЧНОСТІ 24, а також на JK - тригер 28 і елемент АБО-НІ 29, на виході якого одиничний сигнал свідчить про те, що дві групи даних 1 1 і і 1 1 | + 1 мають знак "+" 3 виходу елемента АБО-НІ 29 інформація надходить в групу елементів І ЗО-і, ,302т, які перетворюють дані, що надійшли з ВХОДІВ 1 1 ' I ,11'm 11'+ 1 1і'+1т ТЭКИМ ЧИНОМ, ЩО якщо обидві групи даних мають знак "+", то вони залишаються незмшними(перемножуються з одиницею), а в усіх інших випадках обнуляються обидві групи даних Після обробки інформація записується В Групу D-ТрИГЄріВ 26-І, ,2б2т З ВИХОДІВ JK тригера 28 надходить інформація в елементи І 311, , 3 1 m , 31 m +i, ,312т, які перемножують групу даних зі знаком "-" з нулем, а групу даних зі знаком "+" з одиницею Оброблена інформація записується у групу D - тригерів 27і ,272т Елемент РІВНОЗНАЧНОСТІ 24 встановлює рівнозначність або нерівнозначність знаків 10 і І 10 І + 1 , з виходу елемента РІВНОЗНАЧНОСТІ 24 інформація надходить через D - тригер 25, який обнуляє, або на R - входи групи D - тригерів 27-І, ,272т, або на R - входи групи D -тригерів 26-І, ,2б2т, інформація з виходів яких надходить в групу елементів АБО 32і 3 2 т , 55861 1 32m=i, ,322m, виходи яких є виходами 23' і 23' вузла 22 перетворення схем 19 порівняння блока З порівняння 10 Як приклад роботи вузла 22 перетворення розглянемо всі можливі варіанти надходження І+1 інформації на входи 10' і 10 (табл 1) Таблиця 1 Вхід 10' Група входів 1і'і, 0 1 0 1 Додатне m-розрядне Від'ємне т-розрядне Додатне m-розрядне Від'ємне m-розрядне , 1і'т число число число число В першому випадку, коли обидва числа додатІ+ ні на входах 10' і 10 нулі На виході елемента АБО-НІ 29 одиниця, з якою в групі елементів І ЗО перемножуються дані з входів 11' і 11 | + 1 , тобто залишаються незмінними На виході елемента РІВНОЗНАЧНОСТІ 24 також одиниця, яка відтворюється на прямому виході D-тригера 25 і дозволяє запис даних з групи елементів І ЗО до групи D тригерів 26 При цьому нуль на інверсному виході D - тригера 25 скидає в нуль групу D - тригерів 27 В групі елементів АБО 32 дані з групи D-тригерів 26(які в даному випадку є незміненими вхідними даними) складаються з нулями з групи D - тригерів 27, тобто на виходах 23' І 23 |+1 вузла 22 перетворення будуть незмінені ВХІДНІ дані У випадку, коли обидва числа ВІД'ЄМНІ, вузол 22 порівняння працює аналогічно до попереднього випадку, за винятком того, що на виході елемента І-НІ 29 у цьому випадку буде нуль, що дозволяє обнулити в групі елементів І ЗО дані, які надійшли з входів 11' і 11 | + 1 Таким чином, на виходах 23' і 23 |+1 вузла 22 перетворення будуть нулі В третьому випадку перше число додатне, а друге від'ємне На виході елемента РІВНОЗНАЧНОСТІ 24 нуль, який відтворюється на прямому виході D - тригера 25 і скидає в нуль групу D - тригерів 26, при цьому одиниця на інверсному виході D-тригера 25 дозволяє запис інформації у групу D - тригерів 27 Нуль на J-вході і одиниця на К-вході JK - тригера 28 відповідає нулю на прямому і одиниці на інверсному виходах, що дозволяє помножити дані з входів 1і'і і 1 і ' т на одиницю, тобто залишити їх незмінними, а також обнулити дані з групи входів 11|+1і і 1 1 | + 1 т , помноживши їх з нулем В групі елементів АБО 32 дані з груп D - тригерів 26 і 27 логічно додаються Таким чином, на виходах 23' і 23 |+1 вузла 22 перетворення отримаємо незмінені дані зі знаком "+" з входів 11\ і 11 І+ іті Вхід 1 0 Група входів І+1 11 0 1 1 0 1, И т Додатне m розрядне число Від'ємне m розрядне число Від'ємне m розрядне число Додатне m розрядне число нулі замість даних зі знаком "-" з входів 11\ і 1 1 ' т У випадку, коли перше число від'ємне, а друге додатне, вузол 22 перетворення працює аналогічно до попереднього випадку, за винятком того, що тепер на J-вході JK - тригера 28 одиниця, а на Квході - нуль, що дозволяє лишити незмінними дані з входів 11|+1і ,1і' + 1 т і обнулити дані з входів 11'I, ,11'm Таким чином на виходах 23' і 23 |+1 вузла 22 перетворення отримаємо незмінені дані з входів 11|+1і 1 1 | + 1 т і нулі замість даних зі знаком "-" з входів 11'I і 1 і ' т Вузол 20 порівняння(фіг 5) працює таким чином 3 групи входів 23' і 23 |+1 додатні нульові дані надходять на входи групи елементів АБО 34 і мультиплексори 35' і 35 І+1 Виходи елементів АБО 34 під'єднані до керуючих входів мультиплексорів 35' і 35|+1, що дозволяє виключити із оброблення вузлом групи нульових даних Виходи мультиплексорів 35' і 35|+1 з'єднані з групами елементів НІ 36, 2АБО-І 37 і 2І-АБО 38, які складають схему порівняння слів, що реалізує функцію F(X,Y)= М, якщоХ^ [0, якщоХ^ F(X Y ) = x n y n v f n ( x n _ , y n _ 1 v f n _ , ( , vfg^y,))) тобто де f, = (x, v y j x , v y , ) Одиниця або нуль на виході групи елементів 2ІАБО 38, який є виходом схеми порівняння слів, дозволяють залишити незмінними ВХІДНІ дані в групі елементів 1 40 з входу 23' і обнулити дані в групі елементів І 41 з входу 23|+1, або навпаки Після операції логічного додавання даних з групи елементів І 40 і І 41 в групі елементів АБО 42 на виходах 211, ,21 m вузла 20 порівняння отримаємо мінімальне значення В якості прикладу роботи вузла 20 порівняння розглянемо можливі варіанти надходження даних на входи 23' 23|+1(табл 2) Таблиця2 Входи вузла порівняння 23' Х=0 Х*0 Х=0 Х*0 Входи вузла порівняння 23 І + І Y*0 Y=0 Y=0 Y*0 Примітка X - число, що подається на вхід 23' Y - число, що подається на вхід 23 |+1 З табл 2 видно, яким чином групи елементів АБО 34 і мультиплексорів 35' і 35' 1 обробляють Виходи групи мультиплексорів 35' 35 І + І Y Y X X Y X X Y дані для того, щоб виключити можливі нулі в подальшій оброці схемою порівняння слів, яка складається з групи елементів НІ 36, 2 АБО-І 37 і 2ІАБО 38 Приклад подальшої роботи вузла 20 порі 55861 12 11 і І+1 вняння при всіх можливих комбінаціях даних після плексорів 35 І 35 розглянемо втабл З оброблення трупою елементів АБО 34 і мультиТаблиця З Вихід схеми порівняння Входи схеми поСЛІВ(ВИХІД групи елемерівняння СЛІВ нтів 2І-АБО 38) XY 0 X = Y 0 Виходи групи елементів І 40 Виходи групи елементів І 41 X 0 0 0 Y Y і Примітка X - число, що подається на вхід 23 |+1 Y - число, що подається на вхід 23 Блок 4 послідовного підсумовування(фіг 6) 1 П працює так Дані з входів 9 , ,9 і 7і , 7 т надходять ВІДПОВІДНО на інверсні та прямі входи групи ( т + 1) - розрядних елементів І 43і, ,43П, після чого логічно перемножені дані надходять на входи першої групи суматорів 44і 44[П/2], де вони послідовно підсумовуються і так на всіх (log2n) - рівнях обробки, після чого результат у кожній дії пристрою накопичується у регістрі 46 за допомогою суматора 45 і надходить на вихід 5 пристрою Tnlfl=_([log2n] + 1)t n i f l Виходи 211 ,21 m вузла 20 порівняння(виходи групи елементів АБО 42) X Y Y (2) •Vnin ~ 11 гчгпах ~ П ~ ~ де t n o p - час порівняння даних у схемах 19 порівняння на першому рівні блока 3 порівняння, t n e p - час перетворення даних у вузлах 22 перетворення блока 3 порівняння, ТПіД - час підсумовування двох m - розрядних чисел Якщо порівняння і підсумовування у ВІДПОВІДНИХ вузлах виконується послідовно, то величини Тпор і Тпід мають вигляд Тпор= ( n - 1 ) t n O p , Тп,д=(п-1)Ьі,д Час роботи даного пристрою можна визначити в такий спосіб (3) (4) Аналіз співвідношень (1), (2) і (3), (4) свідчить про те, що реалізація блока 3 порівняння і блока 4 послідовного підсумовування у вигляді "піраміди" дозволяє зменшити час обробки до величини O(log2n) замість часу О(п) у пристроїв аналогів і таким чином ПІДВИЩИТИ ШВИДКОДІЮ пристрою паралельного підсумовування масиву вхідної інформації І ~ (щд •*• І пор) •• ( І пор •*• І під)К, ~ * де t B f l - час віднімання двох m - розрядних чисел, Тпор - час порівняння п - мірного масиву m розрядних чисел, ТПід - час підсумовування п - мірного масиву m - розрядних чисел, k - КІЛЬКІСТЬ ЦИКЛІВ підсумовування Отже, Тпор - tnop + [Іодгп] tnep, (1) Фіг.1 13 55861 Фіг.2 Фіг.З Фіг.4 14 15 55861 16 Фіг.5 4* 4 5 J J Фіг.6 Підписано до друку 05 05 2003 р Тираж 39 прим ТОВ "Міжнародний науковий комітет" вул Артема, 77, м Київ, 04050, Україна (044)236-47-24