ДВОИЧНЫЙ СУММАТОР Советский патент 1974 года по МПК G06F7/50 

1

Предлагаемое изобретение относится к области вычислительной техники и автоматики и может найти применение при построении вычислительных и упраБляюпдих устройств.

Известны двоичные сумматоры, состоящие из т рядов по л. разрядов в каждом, причем каждый разряд сумматора содержит схемы «И, «ИЛИ, «НЕ и триггер, единичный выход которого соединен с первыми входами первой и второй схем «И, а единичный и нулевой входы его соединены соответственно с выходами первой и второй схем «ИЛИ.

Все эти сумматоры в отличие от предлагаемого не могут работать в конвейерном режиме, а также не могут быть разбиты на несколько зон, в каждой из которых может осуществляться как параллельное сложение группы чисел, так и конвейерное сложение многих групп чисел. Это в ряде случаев приводит к неэффективному использованию оборудования и снижает быстродействие сумматора.

Целью изобретения является увеличение производительности сумматора.

Предлагаемый сумматор отличается от известных тем, что в нем первый вход любого разряда соединен со вторым входом первой схемы «И, второй вход - с третьим входом первой схемы «РЬ, третий вход соединен со вторым входом второй схемы «И и через схему «НЕ - с четвертым входом первой схемы «И. Четвертый вход соединен с пятым входом первой схемы «И и с третьим входом второй схемы «И, пятый вход соединен с щестым входом первой схемы «И и с четвертым входом второй схемы «И. Шестой и седьмой входы соединены соответственно с первым и вторым входами первой схемы «ИЛИ, восьмой вход соединен с нервым входом второй

схемы «ИЛИ. Первый выход соединен с нулевым выходом триггера, второй и третий выходы соединены соответственно с выходами первой и второй схем «И и вторым и третьим входом второй схемы «ИЛИ. При этом у

каждого i-ro разряда -го ряда первый вход соединен с первым выходом (t-f 1)-го разряда fe-ro ряда, второй вход - с первым выходом (г-|-1)-го разряда (k-1)-го ряда, третий вход соединен с первым выходом i-ro

разряда ( + 1)-го ряда, четвертый вход соединен с первым выходом i-ro разряда (k-1)-го ряда, пятый вход соединен с управляющим входом устройства, шестой вход соединен со вторым выходом i-ro разряда

(k-1)-го ряда, седьмой вход соединен с третьим выходом (i-1)-го разряда /г-го ряда, а восьмой вход соединен с третьим выходом i-ro разряда (k- 1)-го ряда.

На фиг. 1 приведена логическая схема одиого разряда сумматора; на фиг. 2 - схема соединений входов каждого разряда сумматора с выходами других разрядов сумматора. Логическая схема разряда сумматора содержит шестивходовую схему «И 1, четырехвходовую схему «И 2, схему «НЕ 3, двухвходовую схему «ИЛИ 4, трехвходовую схему «ИЛИ 5 и триггер 6. Единичный выход 7 триггера соединен с первыми входами 8 и 9 первой и второй схем «И 1 и 2. Первый вход 10 разряда соединен со вторым входом 11 первой схемы «И 1, второй вход 12 - с третьим входом 13 первой схемы «И 1, третий вход 14 соединен со вторым входом 15 второй схемы «И 2 и через схему «НЕ - с четвертым входом 16 первой схемы «И 1, четвертый вход 17 соединен с пятым входом 18 первой схемы «И 1 и с третьим, входом 19 второй схемы «И 2, пятый .вход 20 соединен с шестым входом 21 первой схемы «И 1 и с четвертым входом 22 второй схемы «И 2, шестой 23 и седьмой 24 входы соединены соответственно с первым 25 и вторым 26 входами первой схемы «ИЛИ 4, восьмой вход 27 соединен с первым входом 28 второй схемы «ИЛИ 5. Первый выход 29 разряда соединен с нулевым выходом 30 триггера 6, второй 31 и третий 32 выходы соединены соответственно с выходами 33 и 34 первой и второй схем «И и вторым 35 и третьим 36 входами второй схемы «ИЛИ. Пятый вход 20 разряда сумматора соединен с управляющим входом устройства. Разряды сумматора нумеруются справа налево, ряды - снизу вверх. В каждом i-ом разряде 37 k-ro ряда сумматора первый вход 10 соединен с первым выходом 29 (t-|-l)-ro разряда 38 k-ro ряда, второй вход 12 соединен с первым выходом 29 (t+l)-ro разряда 39 (и-1)-го ряда, третий вход 14 соединен с первым выходом 29 i-ro разряда 40 (+1)-го ряда, четвертый вход 17 соединен с первым выходом 29 1-го разряда 41 (k-1)-го ряда, шестой вход 23 соединен с третьим выходом 32 t-ro разряда (k-1)-го ряда, седьмой вход 24 соединен со вторым выходом 31 (i-1)-го разряда 42 k-ro ряда, восьмой вход 27 соединен со вторым выходом 31 i-ro разряда (k- 1)-го ряда. Преобразование информации в сумматоре осуществляется в два такта: в такте считывания информация с триггеров разрядов поступает на комбинационные схемы разрядов, в такте записи информация с выходов комбинационных схем разрядов записывается в триггеры разрядов. Настройка сумматора на тот или иной режим работы {сложение чисел в нескольких независимых зонах, конвейерный режим сложения в нескольких независимых зонах) осуществляется по входам 20 разрядов. В том случае, если на входы 20 всех разрядов подан сигнал «1, сумматор представляет собою одну зону, и алгоритм сложения состоит в преобразовании прямоугольной, бинарной таб- 6 лицы, строки которой являются суммируемыми числами, по таким правилам. В каждом такте преобразования одновременно во всех конфигурациях вида подконфигурация из конфигурации 1) заменяется на конфигурациюа подконфигурация из конфигурации 2) заменлйтся на и т. д. пока такие преобразования возможны. огда такие преобразования невозможны (в аблице нет ни одной конфигурации вида 1, ), это значит, что сумма вычислена. Константы, подаваемые на свободные вхоы крайних разрядов сумматора (на входы 10, 12, 14, 17 поступает сигнал «1, на входы 3, 24, 27 - сигнал «О), связи между логиескими элементами в каждом разряде суматора и связи между разрядами сумматора одобраны так, что сумматор выполняет алоритм сложения, описанный выше. Действиельно, пусть, например, разряды 37-41 суматора образуют конфигурацию 1). Это знаит, что на единичных выходах триггеров разядов 37-41 соответственно сигналы «1, «О, О, «1, «О. В такте считывания информации с триггеров разрядов сумматора на входы 10, 12, 14, 17, 20 i-ro разряда 37 -го ряда и входы 8 и 9 первой и второй схем «И этого разряда поступают соответственно сигналы «1, «1, «О, «1, «1, «1, «1. Легко убедиться, что при таком наборе входных сигналов на выходах 29, 31 и 32 разряда 37 будут соответственно сигналы «О, «1, «О, и в такте записи в триггер разряда 37 будет записан сигнал «О, в триггер разряда 38 - сигнал «1, в триггер разряда 40 - сигнал «О. Это и означает, что произошла замена подконфигурации

на конфигурацию

При рассмотрении работы t-ro разряда k-то ряда не учитывается влияние входов 23, 24 и 27 на состояние триггера этого разряда. На эти входы поступают нулевые сигналы, потому что конфигурации 1), 2) выбраны так, что никакой разряд сумматора не может одновременно входить в две заменяемые подконфигурации.

Аналогичное рассмотрение можно провести для различных наборов состояний i-ro разряда k-TO ряда и его соседей и убедиться что сумматор работает в соответствии с описанным алгоритмом сложения.

Процедуру разбиения сумматора на несколько независимых зон рассмотрим на примере разбиения сумматора с т рядами на две зоны, в нижней из которых 1 рядов. В случае большего числа зон все действия аналогичны. Чтобы осушествить разбиение, на входы 20 разрядов рядов с номерами 1,2,..., (/-1), (/ + 2), (/ + 3), .... (т-1), m подается сигнал «1, на входы 20 разрядов рядов с номерами /, (/-fl) подается сигнал «О. Итак, сумматор настроен. Этот сумматор может одновременно вычислять суммы / слагаемых в нижней зоне и (т-/-1) слагаемых в верхней зоне (слагаемое, записанное в строке (/+1) верхней зоны, для правильной работы сумматора должно быть нулем). Сумма слагаемых нижней зоны получается в /-ой строке, верхней зоны - в т-ой строке сумматора. Легко убедиться, что при такой настройке передача информации из зоны в зону не происходит. Для этого достаточно рассмотреть все возможные расположения конфигураций 1, (2) относительно рядов l(l-i-l).

Наиболее эффективно применение сумматора в конвейерном режиме. Такое применение увеличивает среднюю скорость вычислений и обеспечивает совмещение оборудования. 5 Работа сумматора в конвейерном режиме осуществляется следующим образом.

Первоначально на входы 20 разрядов всех рядов сумматора подан сигнал «О. Первое слагаемое записывается в первый ряд, вто0

во второй, третье - в третий; в морое

мент записи третьего слагаемого на входы 20 разрядов первого ряда сумматора подается сигнал «1, в момент записи четвертого слагаемого на входы 20 второго ряда подается

5 сигнал «1 и т. д., т. е. разряды рядов сумматора вовлекаются в параллельное сложение со скоростью записи информации, другими словами, когда осуществляется запись k-To слагаемого, (k - 2) слагаемых уже участвуют

0 в параллельнол сложении.

Алгоритм сложения таков, что в процесс вычислений ряды освобождаются (обнуляются), начиная снизу, один за другим. Как только освободится первый ряд, на входы 20 всех

5 разрядов этого ряда подается сигнал как только освободится второй ряд, на входы 20 всех разрядов этого ряда полается сигнал как только освободится третий ряд, на входы 20 всех разрядов этого ряда подается

0 сигнал «О. В момент обнуления третьего ряда в первый ряд записывается пепвое слагаемое новой группы слагаемых, и на входы ,0 всех разрядов этого ряда подается сигна.п «1. В момент обнуления четвертого ряда на

5 входы 20 всех разрядов этого ряда подается «О, а во втооой ряп записывается второе слагаемое новой группы слагаемых, и на входы 20 всех разрядов этого ряда подается сигнал «1 и т. д.

0 Итак, в предлагаемом сумматоре ждать получения результата преттыяушего вычисления не нужно: по мере освобождения строк сумматора, до получения этого результата, их можно загружать слагаемыми очередной ГПУП5 пы, которые сразу же вовлекаются в параллельное сложение. Результат сложения последующей группы чисел поллчается в верхней строке сум1 атора по истечении вреитени, необходимого для пара.п;лельного сложения

0 четырех последних чисел из предыдущей группы чисел и никак не зависящего от числа рядов в сумматоре. В сумматоре с достаточпо болыпим числом РЯДОВ т на одном и том же обопудовании олновпеменио вы5 чис.питься СУММЫ многих групп слагаемых, число слагаемых в каждой группе может быть т.

Фиксируя разбиение сумматора на зоны, описанный процесс можно наладить в каждой

зоне сумматора.

Предмет изобретения

Двоичный сумматор, состоящий из т рядов

по п разрядов в каждом, причем каждый раз5 ряд сумматора содержит схемы «И, «ИЛИ,

«НЕ и триггер, единичный выход которого соединен с первыми входами первой и второй схем «И, а единичный и нулевой входы его соединены соответственно с выходами первой и второй схем «ИЛИ, отличающийся тем, что, с целью увеличения производительности, первый вход любого разряда сумматора соединен со вторым входом первой схемы «И, второй вход - с третьим входом первой схемы «И, третий вход соединен со вторым входом второй схемы «И и через схему «ИЕ - с четвертым входом первой схемы «И, четвертый вход соединен с пятым входом первой схемы «И и с третьим входом второй схемы «И, пятый вход соединен с шестым входом первой схемы «И и с четвертым входом второй схемы «И, шестой и седьмой входы соединены соответственно с первым и вторым входами первой схемы «ИЛИ, восьмой вход соединен с первым входом второй схемы «ИЛИ, а первый выход соединен с нулевым выходом триггера, второй и третий выходы соединены соответственно с выходами первой и второй схем «РЪ и вторым и третьим входами второй схемы «ИЛИ, при этом у каждого i-ro разряда -го ряда первый вход соединен с первым выходом (t-j-l)-ro разряда -го ряда, второй вход - с первым выходом (i-fl)-ro разряда (k-I)го ряда, третий вход соединен с первым выходом г-го разряда ()-vo ряда, четвертый вход соединен с первым выходом i-ro разряда (k-1)-го ряда, пятый вход соединен с управляюшим входом устройства, шестой вход

соединен со вторым выходом i-ro разряда (k-1)-го ряда, седьмой вход соединен с третьим выходом (1-1)-го разряда -го ряда, а восьмой вход соединен с третьим выходом г-го разряда (k-1)-го ряда.

)21