Союзная i;:t--v,^;rv;!-t>&e^^?okaj^,-•••. '.г- .; •< if-- -г-'-.' *r,'vt:-,\,;it'/; f~i^fi

 

Союз Советских

Социалистических

Республик

360662

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Зависимое от авт. свидетельства ¹â€”

Заявлено 14.11)к1970 (М 1432000 18-24) с присоединением заявки №вЂ”

Приоритет—

Опубликовано 23.Х.1972. Бюллетень № 36.11. Кл. б OGf 7 50

Комитет по делам изобретений и открытий ори Совете Министров

СССР

УДК 681.325.5 (088.8) Дата опубликования описания 5.1.1973

Автор изобрс тения

И. П, Егоров

Заявитель

Ордена Ленина институт проблем управления (автоматики и телемеханики) УСТРОЙСТВО ДЛЯ УСКОРЕННОГО СУММИРОВАНИЯ ЧИСЕЛ

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

Известны устройства для суммирования ит чнсел, содержащие сумматоры и элементы задержки, в которых время, затрачиваемое на сложение, пропорционально произведению mn, где n — разрядность чисел.

Такие устройства характеризуются низким быстродействием.

Цель изобретения — ускорение процесса суммирования больших массивов п-разрядных чисел.

Это достигается тем, что в предложенном устройстве выход суммы т -го сумматора (i=1, ..., n) связан с входом блока сдвига числа через элемент задержки на время (n — i) т, а выход переноса i го сумматора соединен с входом (т+1) -го сумматора через элемент задержки на время i, входы i-ro сумматора подклю.ены к выходам блока промежуточной памяти через элементы задержки на время (i — 1) т.

На фиг. 1 показано устройство для ускоренного суммирования чисел; на фиг. 2 — пример реализации блока сдвига числа, блока памяти, суммирующего блока.

Устройство содержит суммирующий блок 1, блок 2 сдвига числа, блок 3 памяти, сумматоры 4, ..., 4 и, выход 5 сумматора, на котором формируется сумма, выход б сумматора, на котором формируется перенос, первый вход 7 сумматора, второй вход 8 сумматора, выходы 9 блока 3, внешние входы 10 блока 3, элемент 1т задержки на время т; элемент 12 задержки на

«ремя (n — i) т; i=-1, ..., и; элемент 13 задержки на время (i — 1) т; i=1,... и; схему «И» 14, схему «ИЛИ» 15, схему «НЕ» 1б, триггер 17 с раздельными входами, триггер 18 со счетным входом, зпешний вход 19 блока 3, первый

«.-..ход 0 триггера 18, второй .выход 21 трнг гера 18 и элемент 22 задержки.

Суммирование чисел происходит в блоке

1. Рассмотрим работу этого блока на примере сложения пятиразрядных чисел (фиг. 1). В исходном положении на входах 10 и выходах э и б сумматоров присутствуют нулевые сигналы.

В процессе сложения на входы 10 через промежутки времени т подаются суммируемые числа аь ..., а„,. На протяжении птт тактов

«блоке 3 входы 8 постоянно соединены с входами 9, à входы 7 — с входами 10 (на фиг. 1 показано пунктиром). В начальный момент на входах 10 поя вляется числа al. Через время т это число проходит первый ряд элементов

11 задержки, а на входах 10 появляется число а.. В момент времени 2т число al проходит;второй ряд элементов 11 задержки, число а, — первый ряд элементов задержки, а н»

360662 входах 10 появляется число а8 и т. д. Поскольку на входах 8 сумматоров присутствуют нулевые сигналы числа, продвигаются по блоку

1 без изменения. В момент времени 4 число

ai оказьпвается на входах 5 блока 2.

Блок 2 сдвигает пришедшее на его входы число на один разряд вправо при наличии переноса на выходе б сумматора старшего разряда. Если перенос имеет место, что i-й разряд числа с выхода 5; поступает через блок 2 на вход 8 (— 1) -го сумматора, а сам перенос подается на,вход 8 сумматора старшего разряда, т. е. осуществляется сдвиг вправо на один разряд (см. фиг. 1 дуги, выполненные пунктиром). Когда перенос в старшем разряде отсутствует, i-й разряд числа поступает с выхода 5 на вход 8 этого же сумматора, т. е. сдвига числа не происходит (см. фиг, i дуги, выполненные сплошной линией) .

Поскольку число а; прошло через блок 1 без изменения, в момент появления числа ai на выходах 5 блока 1 (время 4 ) на:выходе б сумматора 4; переноса не будет, следовательно число а, поступает на входы 8 блока

1 без сдвига. B этот же момент времени нз входах 10 оказывается число а; и происходит суммирование первых разрядов чисел а и а8 в сумматоре 4ь На следующем такте (5 ) эти два числа проходят первый ряд элементов,11 задержки и в сумматоре 4, осуществляется сложение вторых разрядов чисел а и а8 с учетом переноса, сформированного на предыдущем такте от сложения первых разрядов этих чисел. Одновременно (момент

5 ) на входах 8 блока 1 появляется число а, поступившее из блока 2 без сдвига, на входы

10 проходит число а8 и происходит суммирование первых разрядов этой пары чисел и т. д. Таким образом, в один и тот же момент времени осуществляется сложение первых разрядов одной пары чисел,:вторых разрядов другой пары чисел и т. д., т. е. параллельное суммирование пар чисел, каждая из которых состоит из числа, приходящего с выходов 5 блока 1, и числа, поступающего извне на входы 10.

Для сложения полученных частичных сумм достаточно сложить только значащие числа, находящиеся в блоке 1. Суммирование только значащих пар чисел осуществляется с помощью блока 8.

Блок 3 работает следующим образом. Начиная с момента 19, на входе 19 схемы

«ИЛИ» блока 3 постоянно присутствует нулевой сигнал. При этом, если сумма чисел

a8+а +ап+ад, поступившая в момент 19г на входы 9 блока 8, является значащим числом (т. е. содержит единицу хотя бы в одном разряде), на выходе схемы «ИЛИ» появляется единичный сигнал, который переводит триггер 18 со счетным входом в состояние, при котором на его выходе 20 оказывается единичный сигнал. В результате сумма а8+

+а,+ам+агв- ЗаПИСЫВаЕтСЯ В ЭЛЕМЕНТ ПаМЯтп блока 8 и хранится до прихода слсдующго значащего числа.

Допустим, что сумма а4+а8+ад+а 8, приходящая на входы 9 блока 8 в следующий момент времени 20, является значащим числом. Тогда срабатывает схема «ИЛИ» и триггер 18 переходит в состояние, при котором на его выходе 21 появляется единичный сигнал.

В результате частичная сумма а8+а7+ап+а 8 поступает из элемента памяти на входы 7 блока 1, а на входы 8 блока 1 подается частичная сумма а4+ а8+ а + а 8. Начинается суммирование этой пары чисел, которое за канчивается к моменту 24 . В момент времени 20т, когда сумма а8+ау+ам+а 8 уходит в блок 1, элементы памяти блока 8 переводятся в исходное состояние с помощью элемента 22 задержки величиной =0,3 .

В момент времени 2й на входы 9 блока

3 поступает сумма а +а,+a +a 8+a, которая записывается в элемент памяти блока 8.

Если приходящая в такте 22 сумма а +а8+

+а о+а 4+а 8 является значащим числом, то на входы 7 и 8 блока 1 поступают суммы а +а8+а8+а 8+a» и а +а8+а 8+а 4+а 8 соответственно. Начинается суммирование этой пары чисел, которое заканчивается в момент времени 2б . Однако раньше (момент 24 ) на входе 9 блока .1 появляется сумаз+а7+ам+ a15 +a4+a8+a12+al6 которая

4О записывается в элемент памяти блока 8, и хранится,до прихода суммыа +а8+а8+ад+ а 7+а +а8+а,о+а 4+а 8 (момент 26 ).

B момент 26 эта последняя пара частичных сумм поступает в блок 1 на суммирование, и в момент времени 30 в элементе памяти блока 8 записывается и хранится оконча18 тельный результат — g aj.

1 =l

Процесс сложения частичных сумм осуществляется по принципу дихотомии и поэтому быстро сходится. Время сложения частичных

55 сумм составляет не более nlog n тактов. Так как требуется m тактов для подачи т суммируемых чисел, то общее время сложения составляет не более (m+nlog>n) тактов. В среднем на одно число приходится не более бО n l ogden (1+ ) тактов. т

Следовательно, чем больше суммируется чисел, тем эффективнее используется время сложения, которое в пределе (при т — сл

6> равно одному такту на число, 3606б2

L с

I !

l

10 10

«Рир /

f0

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

Устройство для ускоренного суммирования чисел, содержащее сумматоры, элементы задержки, блок сдвига числа и блок промежуточной памяти, отличающееся тем, что, с целью ускорения процесса суммирования больгпих массивов и- разрядных чисел, выход суммы -го сумматора (i =1, ..., n) соединен < входом блока сдвига числа через элемент задержки на время (и — i), а выход переноса

i-го сумматора соединен с входом (+1) -го сумматора через элемент задержки на время

, входы i-го сумматора соединены с выходами блока промежуточной памяти через элементы задержки на время (— 1) .

I !

1 !

I !

1 !

V ! ! ! ! !

I !

360662

2

1

Редактор Рыбалова

Тип. Харьк. фил. пред. «Патент»

Составитель И. Долгушева

Техред T. Миронова Корректоры Л. Чуприна и Л. Царькова

Заказ 676/2278 Изд. № 1803 Тираж 406 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Ж-35, Раушская наб., д. 4/5

I

I

1

1

/О

I

I

I !

Ф еУ

1

I