Cистолічні структури для багатооперандної обробки векторних даних

РОЗДІЛ 2
МЕТОДИ ТА ЗАСОБИ БАГАТООПЕРАНДНОЇ ОБРОБКИ ВЕКТОРНИХ ДАНИХ
2.1 Способи обчислення оператора групового підсумовування
Для узагальненого критеріального аналізу алгоритмів багатооперандної обробки необхідно більш детально розглянути варіанти реалізації оператора ГП із застосуванням графічного відображення процесу обробки групи із n k-розрядних операндів. Для більшої деталізації при визначенні часових і апаратних витрат кожного способу реалізації оператора ГП застосовуються відомі функціональні схеми відповідних пристроїв [40], причому подаються найпростіші схеми без наведення вдосконалених варіантів. Спочатку необхідно розглянути групу способів почислового обчислення оператора ГП (табл. 1.1).
Послідовно-послідовний спосіб почислового обчислення оператора ГП [40] реалізується на базі однорозрядного комбінаційного суматора (ОСм) з тригером для запам'ятовування перенесення (Т) і регістром зсуву (Рг) (рис. 2.1). На рис. 2.1,а і подалі, при відображенні функціональних схем використовуються такі позначки: ЗП - запам'ятовувальний пристрій; КП - керувальний пристрій; См - суматор; Рг - регістр; В - вентиль; Т - тригер; ОСм - однорозрядний суматор; Лч - лічильник; БВОС - багатовхідний однорозрядний суматор, S - результат обробки.
На рис. 2.1,б показана потактна послідовність виконання послідовно -послідовного способу на прикладі підсумовування шести 4-х розрядних доданків, тобто при n = 6, k = 4.
З рис. 2.1,б видно, що спочатку підсумовуються два перших операнди а1 і а2 послідовно по розрядах, починаючи з молодшого розряду, і формується поточна сума S1, значення якої підсумовується порозрядно із значенням відповідних розрядів наступного операнда а3, починаючи з молодшого розряду і т.д. Порозрядна обробка виконується в результаті зсуву регістра Рг на один розряд праворуч.
а)б)Рис. 2.1 Послідовно-послідовний спосіб почислового обчислення оператора ГП Послідовно-паралельний спосіб реалізується з використанням комбінаційного k - розрядного суматора і регістра (рис. 2.2,а) [40]. З рис. 2.2,б видно, що спочатку підсумовуються паралельно по розрядах два перших операнди а1 і а2 і формується поточна сума S1. Потім ця сума підсумовується паралельно по розрядах з наступним операндом а3 і т.д.
а) б)Рис. 2.2 Послідовно- паралельний спосіб почислового обчислення оператора ГП Послідовно-змішаний спосіб реалізується аналогічно послідовно-паралельному (рис.2.2,а) з тією різницею, що доданки розбиваються по розрядності на N груп по r розрядів в кожній, тобто
k=N r. (2.1)
Спочатку здійснюється підсумовування молодших r-x розрядів всіх n доданків і т. д. (рис. 2.3). Потім виконується зсув вмісту регістра на r розрядів праворуч і додавання суми подальших r розрядів всіх n доданків.
Рис. 2.3 Послідовно-змішаний спосіб почислового обчислення оператора ГП
Паралельно-послідовний спосіб реалізується за допомогою декількох рядів (дерева) однорозрядних суматорів ОСм (рис. 2.4,а) і S-розрядного регістра, причому результати підсумовування кожного попереднього ряду суматорів підсумовуються попарно суматорами наступного ряду [40].
З рис. 2.4,б видно, що спочатку паралельно попарно підсумовуються усі молодші розряди операндів, і формується поточна сума S1, значення якої підсумовується зі значенням відповідних розрядів наступних пар операндів, починаючи зі молодшого розряду і т.д. Порозрядна обробка виконується в результаті зсуву регістра Рг на один розряд праворуч.
а) б)Рис. 2.4 Паралельно-послідовний спосіб почислового обчислення оператора ГП Паралельно-паралельний спосіб може бути реалізований за допомогою дерева суматорів, аналогічно наведеному на рис.2.4,а з тією лише різницею, що використовуються паралельні k-розрядні комбінаційні суматори См (рис. 2.5,а) [40].
З рис. 2.5,б видно, що спочатку паралельно попарно підсумовуються усі розряди операндів, і формується поточна сума S1, значення якої підсумовується зі значенням наступних пар операндів.
a)
б)Рис. 2.5 Паралельно-паралельний спосіб почислового обчислення оператора ГП Паралельно-змішаний спосіб реалізується аналогічно паралельно-паралельному способу (рис. 2.5,а) з доданням після останнього ряду накопичувального S-розрядного суматора (або S-розрядного комбінаційного суматора і регістра [68]). В даному випадку скорочені r-розрядні суматори виконують підсумовування по r розрядів, починаючи з молодших. Після отримання в накопичувальному суматорі суми r розрядів всіх n доданків виконується її зсув на r розрядів праворуч, обчислення суми r наступних розрядів n доданків і додання її до зсунутої попередньої суми і т.д. (рис. 2.6).
Рис. 2.6 Паралельно-змішаний спосіб почислового обчислення оператора ГП
Змішано-послідовний спосіб реалізується аналогічно паралельно-послідовному (рис.2.4,а) з тією різницею, що послідовні коди доданків надходять на входи дерева однорозрядних суматорів не всі водночас, а М групами по ? доданків в кожній тобто:
n=M ?. (2.2)
Групи обробляються послідовно одна за одною з накопиченням результату (рис. 2.7), для чого необхідно ввести S-розрядний комбінаційний суматор См і регістр зсуву для вирівнювання розрядів в часі.
Рис. 2.7 Змішано-послідовний спосіб почислового обчислення оператора ГП
Змішано-паралельний спосіб реалізується аналогічно паралельно-паралельному способу (рис.2.5,а) з тією різницею, що паралельні коди доданків надходять на входи дерева паралельних суматорів не всі водночас, а групами по ? доданків. Групи обробляються послідовно одна за одною з накопичуванням результату в додатковому накопичувальному суматорі (рис. 2.8).
Рис. 2.8 Змішано-паралельний спосіб почислового обчислення оператора ГП
Змішано-змішаний спосіб реалізується аналогічно паралельно-змішаному (рис. 2.6) або змішано-паралельному (рис. 2.8), відрізняючись від першого тим, що доданки надходять не всі водночас, а групами по ? доданків, а від другого тим, що розряди доданків надходять не паралельно, а групами по r розрядів (р