Тема 10. Арифметико-логические устройства

Арифметико-логические устройства АЛУ (ALU, Arithmetic-Logic Unit) вы­полняют над словами ряд действий. Основой АЛУ служит сумматор, схема которого дополнена логикой, расширяющей функциональные возможности АЛУ и обеспечивающей его перестройку с одной операции на другую Обычно АЛУ четырехразрядны и для наращивания разрядности объединя­ются с формированием последовательных или параллельных переносов. Логические возможности АЛУ разных технологий (ТТЛШ, КМОП, ЭСЛ) сходны. В силу самодвойственности выполняемых операций условное обо­значение и таблица истинности АЛУ встречаются в двух вариантах, отличающихся взаимно инверсными значениями переменных АЛУ (рис. 2.35) имеет входы операндов А и В, входы выбора операций S, вход переноса Ci и вход М (Моdе), сигнал которого задает тип выполняе­мых операций: логические (М = 1) или арифметико-логические (М = 0). Ре­зультат операции вырабатывается на выходах F, выходы G и Н дают функции генерации и прозрачности, используемые для организаций параллельных пе­ реносов при наращивании размерности АЛУ. Сигнал Со выходной пере­нос, а выход А = В есть выход сравнения на равенство с открытым коллек­тором. Рисунок 10.1 Условнее обозначение АЛУ

Перечень выполняемых АЛУ операций дан в табл Для краткости дво­ичные числа s 3 s 2 s 1 s 0 представлены их десятичными эквивалентами. Под утолщенными обозначениями 1 и 0 следует понимать наборы 1111 и 0000, входной перенос поступает в младший разряд слова, т. е. равен 000С i. Логи­ческие операции поразрядные, т. е. операция над словами А * В означает, что а; * Ь; при отсутствии взаимовлияния разрядов. При арифметических операциях учитываются межразрядные переносы. Таблица 2.13.

Шестнадцать логических операций позволяют воспроизводить все функции двух переменных. В логико-арифметических операциях встречаются и логи­ ческие и арифметические операции одновременно. Запись типа А\/В + АВ следует понимать так: вначале поразрядно выпол­няются операции инвертирования (В), логического сложения (А\/В) и ум­ножения (АВ), а затем полученные указанным образом два четырехразряд­ных числа складываются арифметически. При операциях над словами большой размерности АЛУ соединяются друг с другом с организацией последовательных (рис. 2.36, а) или параллельных (рис. 2.36, б) переносов. В последнем случае совместно с АЛУ применяют микросхемы блоки ускоренного переноса (СRU, Саrrу Unit), получающие от отдельных АЛУ функции генерации и прозрачности, а также входной перенос и вырабатывающие сигналы переноса Шестнадцать логических операций позволяют воспроизводить все функции двух переменных. В логико-арифметических операциях встречаются и логи­ ческие и арифметические операции одновременно. Запись типа А\/В + АВ следует понимать так: вначале поразрядно выпол­няются операции инвертирования (В), логического сложения (А\/В) и ум­ножения (АВ), а затем полученные указанным образом два четырехразряд­ных числа складываются арифметически. При операциях над словами большой размерности АЛУ соединяются друг с другом с организацией последовательных (рис. 2.36, а) или параллельных (рис. 2.36, б) переносов. В последнем случае совместно с АЛУ применяют микросхемы блоки ускоренного переноса (СRU, Саrrу Unit), получающие от отдельных АЛУ функции генерации и прозрачности, а также входной перенос и вырабатывающие сигналы переноса

Рисунок 10.2 Схемы наращивания АЛУ при последовательном (в) и параллельном (б) переносах и реализация функций компаратора для группы АЛУ (в)

Блок СКГ вырабатывает также функции генерации и прозрачности для всей группы обслуживаемых им АЛУ, что при необходимости позволяет органи­зовать параллельный перенос на следующем уровне (между несколькими группами из четырех АЛУ). На рис. 2.36, в показаны способы выработки сигналов сравнения слов для группы АЛУ. Выход сравнения на равенство выполняется по схеме монтаж­ной логики для выходов типа ОК. Комбинируя сигнал равенства слов с сиг­ налом переноса на выходе группы при работе АЛУ в режиме вычитания, легко получить функции FAB и FAB. Если А В), то по­ дучим FAB = 1. Блок СКГ вырабатывает также функции генерации и прозрачности для всей группы обслуживаемых им АЛУ, что при необходимости позволяет органи­зовать параллельный перенос на следующем уровне (между несколькими группами из четырех АЛУ). На рис. 2.36, в показаны способы выработки сигналов сравнения слов для группы АЛУ. Выход сравнения на равенство выполняется по схеме монтаж­ной логики для выходов типа ОК. Комбинируя сигнал равенства слов с сиг­ налом переноса на выходе группы при работе АЛУ в режиме вычитания, легко получить функции FAB и FAB. Если А В), то по­ дучим FAB = 1.

Матричные умножители

Микросхемы множительных устройств появились в 1980-х годах, когда дос­тигнутый уровень интеграции позволил разместить на одном кристалле дос­таточно большое количество логических элементов. Структура матричных умножителей тесно связана со структурой математических выражений, описывающих операцию умножения. Пусть имеются два целых двоичных числа без знаков Аm = аm-1...ао и Вn = bn-1...bо, Их перемножение выполняется по известной схеме "умножения столбиком". Если числа четырехразрядные, т. е. m = n = 4, то

Произведение выражается числом Рm+n = Рm+n-1 Pm+n-2 … Ро. Члены вида аibj, где i = 0... (m-1) и j = 0... (n-1) вырабатываются парал­лельно во времени конъюнкторами. Их сложение в столбцах, которое мож­ но выполнять разными способами, составляет основную операцию для ум­ножителя и определяет почти целиком время перемножения. Матричные перемножители могут быть просто множительными блоками (МБ) или множительно- суммирующими (МСБ), последние обеспечивают удобство наращивания размерности умножителя. МСБ реализует операцию Р = Аm х Вn + Сm + Dn, т. е. добавляет к произ­ведению два слагаемых: одно разрядности m, совпадающей с разрядностью множимого, другое разрядности n, совпадающей с разрядностью множителя. Произведение выражается числом Рm+n = Рm+n-1 Pm+n-2 … Ро. Члены вида аibj, где i = 0... (m-1) и j = 0... (n-1) вырабатываются парал­лельно во времени конъюнкторами. Их сложение в столбцах, которое мож­ но выполнять разными способами, составляет основную операцию для ум­ножителя и определяет почти целиком время перемножения. Матричные перемножители могут быть просто множительными блоками (МБ) или множительно- суммирующими (МСБ), последние обеспечивают удобство наращивания размерности умножителя. МСБ реализует операцию Р = Аm х Вn + Сm + Dn, т. е. добавляет к произ­ведению два слагаемых: одно разрядности m, совпадающей с разрядностью множимого, другое разрядности n, совпадающей с разрядностью множителя.

Множительно-суммирующие блоки Множительно-суммирующий блок для четырехразрядных операндов без набо­ра конъюнкторов, вырабатывающих члены вида аibj, показан на рис. 2.37, а, где для одноразрядного сумматора принято обозначение (рис. 2.37, б). Для построения МСБ чисел равной разрядности потребовалось n2 конъюнк­торов и n2 одноразрядных сумматоров. Множительно-суммирующий блок для четырехразрядных операндов без набо­ра конъюнкторов, вырабатывающих члены вида аibj, показан на рис. 2.37, а, где для одноразрядного сумматора принято обозначение (рис. 2.37, б). Для построения МСБ чисел равной разрядности потребовалось n2 конъюнк­торов и n2 одноразрядных сумматоров.

Рисунок 10.3 Схема множительно-суммирующего блока для четырехрезрядных сомножителей (а), обозначение одноразрядного сумматоре для данной схемы (б) а б

Рисунок 10.4 К пояснению принципа наращивания размерности множительных устройств (в), условное обозначение множительно-суммирующего блока

Рисунок 10.5 схема умножителя 4x4", построенная на множительно- суммирующих блоках "4 х 2" (в)

Максимальная длительность умножения сумма задержек сигналов в конъюнкторах для выработки членов аibj и задержки в наиболее длинной цепочке передачи сигнала в матрице одноразрядных сумматоров, равной 2n - 1 (m + n - 1 в общем случае). Таким образом, tМРL = tк + (2n - 1)tsм,Максимальная длительность умножения сумма задержек сигналов в конъюнкторах для выработки членов аibj и задержки в наиболее длинной цепочке передачи сигнала в матрице одноразрядных сумматоров, равной 2n - 1 (m + n - 1 в общем случае). Таким образом, tМРL = tк + (2n - 1)tsм, Схема множительного блока отличается от схемы МСБ тем, что в ней отсут­ствуют сумматоры правой диагонали, т. к. при Сm = 0 и Dn = 0 они не тре­буются.Схема множительного блока отличается от схемы МСБ тем, что в ней отсут­ствуют сумматоры правой диагонали, т. к. при Сm = 0 и Dn = 0 они не тре­буются. Построение умножителей большей размерности из умножителей меньшей размерности на основе МБ требует введения дополнительных схем, называе­мых "деревьями Уоллеса", которые имеются в некоторых зарубежных сериях. При использовании МСБ дополнительные схемы не требуются. Принцип на­ращивания размерности умножителя иллюстрируется на рис. 2.38, а на примере построения МРЬ "4 х 4" из МСБ "4 х 2". На поле частичных произве­дений выделены зоны, воспроизведение которых возможно на блоках раз­мерности 4x2 (это две первые строки и две последние).Построение умножителей большей размерности из умножителей меньшей размерности на основе МБ требует введения дополнительных схем, называе­мых "деревьями Уоллеса", которые имеются в некоторых зарубежных сериях. При использовании МСБ дополнительные схемы не требуются. Принцип на­ращивания размерности умножителя иллюстрируется на рис. 2.38, а на примере построения МРЬ "4 х 4" из МСБ "4 х 2". На поле частичных произве­дений выделены зоны, воспроизведение которых возможно на блоках раз­мерности 4x2 (это две первые строки и две последние). Перемножение в пределах зон дает частичные произведения р1 = Р51Р41РЗ1Р21Р11Р01 и Р2 = Р52Р42Р32Р22Р12Р02. Для получения конечного значения произведения эти частичные произведения нужно сложить с учетом их взаимного положения (сдвига одного относительно другого).Перемножение в пределах зон дает частичные произведения р1 = Р51Р41РЗ1Р21Р11Р01 и Р2 = Р52Р42Р32Р22Р12Р02. Для получения конечного значения произведения эти частичные произведения нужно сложить с учетом их взаимного положения (сдвига одного относительно другого). Схема, реализующая указанный принцип, изображена на рис. 2.38, в. В ней использовано условное обозначение МСБ (рис. 2.38, б). Для общности оба блока размерности 4x2 показаны как МСБ, хотя первый может быть про­сто множительным блоком, т. к. для него слагаемые С и D имеют нулевое значение.Схема, реализующая указанный принцип, изображена на рис. 2.38, в. В ней использовано условное обозначение МСБ (рис. 2.38, б). Для общности оба блока размерности 4x2 показаны как МСБ, хотя первый может быть про­сто множительным блоком, т. к. для него слагаемые С и D имеют нулевое значение. Максимальная длительность умножения сумма задержек сигналов в конъюнкторах для выработки членов аibj и задержки в наиболее длинной цепочке передачи сигнала в матрице одноразрядных сумматоров, равной 2n - 1 (m + n - 1 в общем случае). Таким образом, tМРL = tк + (2n - 1)tsм,Максимальная длительность умножения сумма задержек сигналов в конъюнкторах для выработки членов аibj и задержки в наиболее длинной цепочке передачи сигнала в матрице одноразрядных сумматоров, равной 2n - 1 (m + n - 1 в общем случае). Таким образом, tМРL = tк + (2n - 1)tsм, Схема множительного блока отличается от схемы МСБ тем, что в ней отсут­ствуют сумматоры правой диагонали, т. к. при Сm = 0 и Dn = 0 они не тре­буются.Схема множительного блока отличается от схемы МСБ тем, что в ней отсут­ствуют сумматоры правой диагонали, т. к. при Сm = 0 и Dn = 0 они не тре­буются. Построение умножителей большей размерности из умножителей меньшей размерности на основе МБ требует введения дополнительных схем, называе­мых "деревьями Уоллеса", которые имеются в некоторых зарубежных сериях. При использовании МСБ дополнительные схемы не требуются. Принцип на­ращивания размерности умножителя иллюстрируется на рис. 2.38, а на примере построения МРЬ "4 х 4" из МСБ "4 х 2". На поле частичных произве­дений выделены зоны, воспроизведение которых возможно на блоках раз­мерности 4x2 (это две первые строки и две последние).Построение умножителей большей размерности из умножителей меньшей размерности на основе МБ требует введения дополнительных схем, называе­мых "деревьями Уоллеса", которые имеются в некоторых зарубежных сериях. При использовании МСБ дополнительные схемы не требуются. Принцип на­ращивания размерности умножителя иллюстрируется на рис. 2.38, а на примере построения МРЬ "4 х 4" из МСБ "4 х 2". На поле частичных произве­дений выделены зоны, воспроизведение которых возможно на блоках раз­мерности 4x2 (это две первые строки и две последние). Перемножение в пределах зон дает частичные произведения р1 = Р51Р41РЗ1Р21Р11Р01 и Р2 = Р52Р42Р32Р22Р12Р02. Для получения конечного значения произведения эти частичные произведения нужно сложить с учетом их взаимного положения (сдвига одного относительно другого).Перемножение в пределах зон дает частичные произведения р1 = Р51Р41РЗ1Р21Р11Р01 и Р2 = Р52Р42Р32Р22Р12Р02. Для получения конечного значения произведения эти частичные произведения нужно сложить с учетом их взаимного положения (сдвига одного относительно другого). Схема, реализующая указанный принцип, изображена на рис. 2.38, в. В ней использовано условное обозначение МСБ (рис. 2.38, б). Для общности оба блока размерности 4x2 показаны как МСБ, хотя первый может быть про­сто множительным блоком, т. к. для него слагаемые С и D имеют нулевое значение.Схема, реализующая указанный принцип, изображена на рис. 2.38, в. В ней использовано условное обозначение МСБ (рис. 2.38, б). Для общности оба блока размерности 4x2 показаны как МСБ, хотя первый может быть про­сто множительным блоком, т. к. для него слагаемые С и D имеют нулевое значение.

Схемы ускоренного умножения Для ускорения умножения разработан ряд алгоритмов, большой вклад в эти разработки внес Э. Бут (Е. Вооt). Рассмотрим процесс умножения по гак называемому модифицированному алгоритму Бута (умножение сразу на два разряда). Из изложенного выше видно, что основную задержку в процесс выработки произведения вносит суммирование частичных произведений. Уменьшение их числа сократило бы время суммирования. К этому приводит алгоритм, основанный на следующих рассуждениях. Пусть требуется вычислить произведение (a)(a) (a)(a)

Непосредственное воспроизведение соотношения (а) связано с выработкой частичных произведений вида Abj2i (i = 0...n - 1). Число таких произведе­ний равно разрядности множителя n. Выражение (а) можно видоизменить с помощью соотношения (б) справедливость которого очевидна. Это соотношение позволяет разреживать последовательность (спектр) сте­пеней в сумме частичных произведений. Можно, например, исключить чет­ные степени, как показано на рис. 2.39, а. Исключение четных (или нечет­ных) степеней не только изменяет значения оставшихся частичных произве­дений, но и сокращает их число примерно вдвое, что, в конечном счете, ус­коряет выработку произведения. Для того чтобы "разнести по соседям" член со степенью 2°, расширим разрядную сетку, введя слагаемое b-12-1 (нулевой разряд с номером -1). Оставшиеся частичные произведения имеют вид Так как число частичных произведений уменьшилось примерно вдвое, при применении этого алгоритма говорят об умножении сразу на два разряда.

Рисунок 10.6 К пояснению принципа быстрого умножения "срезу на два разряда" (в) и схема быстрого умножения (б)

Для всех возможных сочетаний bi+1, bi, bi- 1 можно составить таблицу (табл. 2.14) частичных произведений.

Пример Пусть требуется умножить на 01112, т. е. 10 х 7. При разреживании час­тичных произведений оставим только нечетные, как показано на рис. 2.39, а Расширив разрядную сетку множителя, имеем В = b4b3b2b1b0b-1b-2 = Первому частичному произведению соответствует тройка b0b- 1b-2 = 100. Из табл получаем, что этой тройке соответствует частичное произведение -2А 2-1 = - А. для получения которого требуется перевести А в дополнительный код. Сама величина А в пределах разрядной сетки произведения должна быть записана как , ее обратный код и дополнительный код Второму частичному произведению соответствует тройка b2b1b0 =111. следо­вательно, второе частичное произведение равно нулю (табл. 2.14). Третьему частичному произведению соответствует тройка b4b3b2 = 001, следо­вательно, оно имеет вид А 23 = Для получения результата заданного умножения требуется сложить частичные произведения: Пусть требуется умножить на 01112, т. е. 10 х 7. При разреживании час­тичных произведений оставим только нечетные, как показано на рис. 2.39, а Расширив разрядную сетку множителя, имеем В = b4b3b2b1b0b-1b-2 = Первому частичному произведению соответствует тройка b0b- 1b-2 = 100. Из табл получаем, что этой тройке соответствует частичное произведение -2А 2-1 = - А. для получения которого требуется перевести А в дополнительный код. Сама величина А в пределах разрядной сетки произведения должна быть записана как , ее обратный код и дополнительный код Второму частичному произведению соответствует тройка b2b1b0 =111. следо­вательно, второе частичное произведение равно нулю (табл. 2.14). Третьему частичному произведению соответствует тройка b4b3b2 = 001, следо­вательно, оно имеет вид А 23 = Для получения результата заданного умножения требуется сложить частичные произведения:

Схема, реализующая алгоритм быстрого умножения сразу на два разряда, показана на рис. 2.39, б. Множимое А поступает в этой схеме на ряд преобразователей, заготавли­ вающих все возможные варианты частичных произведений (-2А, -А, 2А), кроме самого А и нуля, которые не требуют схемной реализации. Множи­тель В поступает на логический преобразователь ЛП, который анализирует тройки разрядов, декодирует их и дает мультиплексорам сигналы выбора того или иного варианта частичных произведений. Окончательный результат получается суммированием частичных произведений с учетом их взаимного сдвига в разрядной сетке. Размерность умножителя "4 х 4". Приведенные выше примеры множительных устройств касались операций с прямыми кодами. В этом случае умножение знакопеременных чисел сведется только к выработке знакового разряда как суммы по модулю 2 знаковых раз­ рядов сомножителей. Если же числа представлены не прямыми колами с зна­ ковыми разрядами, а, например, дополнительными кодами, то, имея рассмот­ ренные выше умножители, можно дополнить их преобразователями дополни­ тельного кода в прямые на входах и преобразователем прямого кода в допол­ нительный на выходе или использовать схемы, непосредственно реализующие алгоритмы умножения дополнительных кодов (см., например, [37]). Разработке матричных умножителей уделяют внимание многие фирмы. В оте­ чественных сериях МИС/СИС имеются умножители малой размерности (2 х 2, 4 х 4, 4 х 2 и др.). В сериях БИС размерности умножителей знвчительно боль­ше. В серии 1802, например, имеются умножители 8x8, 12x12, 16x16 (ВРЗ, ВР4 и ВР5 соответственно). В схемотехнике ЭСЛ выполнен умножитель 1800ВР1 (8 х 8 за 17 нc). Зарубежные фирмы разработали умножители (фирмы BIT, Нitachi и др.) размерностями 16 х 16 и более с временами умножения нc. Несколько лет назад предприятие "Интеграл" (г. Минск) выпустило ум­ножитель КА1843ВР1 размерностью 32 х 32 со временем умножения 250 нс в корпусе с 172 выводами. Схема, реализующая алгоритм быстрого умножения сразу на два разряда, показана на рис. 2.39, б. Множимое А поступает в этой схеме на ряд преобразователей, заготавли­ вающих все возможные варианты частичных произведений (-2А, -А, 2А), кроме самого А и нуля, которые не требуют схемной реализации. Множи­тель В поступает на логический преобразователь ЛП, который анализирует тройки разрядов, декодирует их и дает мультиплексорам сигналы выбора того или иного варианта частичных произведений. Окончательный результат получается суммированием частичных произведений с учетом их взаимного сдвига в разрядной сетке. Размерность умножителя "4 х 4". Приведенные выше примеры множительных устройств касались операций с прямыми кодами. В этом случае умножение знакопеременных чисел сведется только к выработке знакового разряда как суммы по модулю 2 знаковых раз­ рядов сомножителей. Если же числа представлены не прямыми колами с зна­ ковыми разрядами, а, например, дополнительными кодами, то, имея рассмот­ ренные выше умножители, можно дополнить их преобразователями дополни­ тельного кода в прямые на входах и преобразователем прямого кода в допол­ нительный на выходе или использовать схемы, непосредственно реализующие алгоритмы умножения дополнительных кодов (см., например, [37]). Разработке матричных умножителей уделяют внимание многие фирмы. В оте­ чественных сериях МИС/СИС имеются умножители малой размерности (2 х 2, 4 х 4, 4 х 2 и др.). В сериях БИС размерности умножителей знвчительно боль­ше. В серии 1802, например, имеются умножители 8x8, 12x12, 16x16 (ВРЗ, ВР4 и ВР5 соответственно). В схемотехнике ЭСЛ выполнен умножитель 1800ВР1 (8 х 8 за 17 нc). Зарубежные фирмы разработали умножители (фирмы BIT, Нitachi и др.) размерностями 16 х 16 и более с временами умножения нc. Несколько лет назад предприятие "Интеграл" (г. Минск) выпустило ум­ножитель КА1843ВР1 размерностью 32 х 32 со временем умножения 250 нс в корпусе с 172 выводами.