Союзная i;: t-v,; rv; -tgt; amp; eokaj, -•••. г.; •lt; if-г-. r, vt: -,; it; fifi

Союз Советских Социалистических Республик360662 ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Зависимое от авт. свидетельства-Заявлено 14.1 тт.1970 (М 143200018-24)с присоединением заявки-Приоритет -Опубликовано 23.Х.1972. Бюллетень36.1. Кл. б 061 750 Комитет по делам изобретений и открытий ори Совете Министров СССРУДК 681.325,5 (088.8) Дата опубликования описания 5.1,1973 Авторизобретения И. П, Егоров Заявитель Ордена Ленина институт проблем управленияУСТРОЙСТВО ДЛЯ УСКОРЕННОГО СУММИРОВАНИЯ ЧИСЕЛ Изобретение относится к области вычислительцой техники и предназначено для ускоренного сложения больших массивов двоичных чисел.Известны устройства для суммирования лп чисел, содержащие сумматоры и элементы задержки, в которых время, затрачиваемое на сложение, пропорционально произведению тп, где п - разрядность чисел.Такие устройства характеризуются низким быстродействием.Цель изобретения - ускорение процесса суммирования больших массивов п-разрядных чисел,Это достигается тем, что в предложенном устройстве выход суммы т-го сумматора (т=1, , п) связан с входом блока сдвига числа через элемент задержки на время (и - т) т, а выход переноса 1-го сумматора соединен с входом (:+1) -го сумматора через элемент задержки ца время т, входы т-го сумматора подклюцены к выходам блока промежуточной памяти через элементы задержки на время (т - 1)На фиг. 1 показано устройство для ускоренного суммирования чисел; на фиг. 2 - пример реализации блока сдвига числа, блока памяти, суммирующего блока,Устройство содержит суммирующий блок 1, блок 2 сдвига числа, блок 3 памяти, сумматоры 4, , 4 п, выход 5 сумматора, на котором формируется сумма, выход б сумматора, на котором формируется перенос, первый вход 7 сумматора, второй вход 8 сумматора, выходы 9 блока 3, вцешцце вхолы 10 блока 3, элемент 1 т 5 задержки на время т; элемент 12 задержки навремя (и - 1) т; =-1, , и; элемент 13 задержки на время (г - 1) т; 1=1, и; схему И 14, схему ИЛИ 15, схему НЕ 1 б, триггер 17 с раздельными входами, триггер 18 со счет О цым входом, внешний вход 19 блока 3, первый.хол 0 триггера 18, второй выход 21 трцг.гера 18 и элемент 22 задержки.Суммирование чисел происходит в блоке1, Рассмотрим работу этого блока на примере сложения пятиразрядных чисел (фиг. 1). В исходном положении на входах 10 и выходах э и б сумматоров присутствуют нулевые сигналы.В процессе сложения на входы 10 черезпромежутки времени т подаются суммируемые числа аь , а,. На протяжении птт тактов блоке 3 входы 8 постоянно соединены с входами 9, а входы 7 - с входами 10 (на фиг. 1 показано пунктиром). В начальный момент на входах 10 появляется числа аЧерез время т это число проходит первый ряд элементов 11 задержки, а на входах 10 появляется число а В момент времени 2 т число а проходит,второй ряд элементов 11 задержки, число а, - первый ряд элементов задержки, а нвходах 10 появляется число ае и т. д, Поскольку на входах 8 сумматоров присутствуют ну. левые сигналы числа, продвигаются по блоку 1 без изменения. В момент времени 4 число а 1 оказывается на входах 5 блока 2.Блок 2 сдвигает пришедшее на его входы число на один разряд вправо при наличии переноса на выходе б сумматора старшего разряда. Если перенос имеет место, что -й разряд числа с выхода 5; поступает через блок 2 на вход 8 (1 - 1)-го сумматора, а сам перенос подается на,вход 8 сумматора старшего разряда, т. е. осуществляется сдвиг вправо на один разряд (см. фиг, 1 дуги, выполненные пунктиром). Когда перенос в старшем разряде отсутствует, -й разряд числа поступает с выхода 5 на вход 8 этого же сумматора, т. е. сдвига числа не происходит (см. фиг, 1 дуги, выполненные сплошной линией),Поскольку число а; прошло через блок 1 без изменения, в момент появления числа а 1 на выходах 5 блока 1 (время 4) на выходе б сумматора 4; переноса не будет, следовательно число а, поступает на входы 8 блока 1 без сдвига. В этот же момент времени цз входах 10 оказывается число ае и происходит суммирование первых разрядов чисел а 1 и ае в сумматоре 4 ь На следующем такте (5) эти два числа проходят первый ряд элементов,11 задержки и в сумматоре 4, осуществляется сложение вторых разрядов чисел а 1 и а, с учетом переноса, сформированного на предыдущем такте от сложения первых разрядов этих чисел. Одновременно (момент 5 т) на входах 8 блока 1 появляется число аь поступившее из блока 2 без сдвига, на входы 10 проходит число ае и происходит суммирование первых разрядов этой пары чисел и т, д. Таким образом, в один и тот же момент времени осуществляется сложение первых разрядов одной пары чисел, вторых разрядов другой пары чисел и т. д., т. е. параллельное суммирование пар чисел, каждая из которых состоит из числа, приходящего с выходов 5 блока 1, и числа, поступающего извне на входы 10.Для сложения полученных частичных сумм достаточно сложить только значащие числа, находящиеся в блоке 1, Суммирование только значащих пар чисел осуществляется с помощью блока 3,Блок 3 работает следующим образом. Начиная с момента 19 т, на входе 19 схемы ИЛИ блока 3 постоянно присутствует нулевой сигнал. При этом, если сумма чисел а,+а,+ам+ав, поступившая в момент 19 г на входы 9 блока 3, является значащим числом (т. е. содержит единицу хотя бы в одном разряде), на выходе схемы ИЛИ появляется единичный сигнал, который переводит триггер 18 со счетным входом в состояние, при котором на его выходе 20 оказывается единичный сигнал, В результате сумма ае+ +а,+а+а 1 е записывается в элемент памяти блока 3 и хранится до прихода слсдующго значащего числа.Допустим, что сумма а 4+ае+ад+ац, при ходящая на входы 9 блока 3 в следующиймомент времени 20 т, является значащим числом. Тогда срабатывает схема ИЛИ и триггер 18 переходит в состояние, при котором на 15 его выходе 21 появляется единичный сигнал.В результате частичная сумма аз+а,+ап+ае поступает из элемента памяти на входы 7 блока 1, а на входы 8 блока 1 подается частичная сумма а 4+ ае+ а 12+ а 1 е. Начинается суммирование этой пары чисел, которое за.канчивается к моменту 24 т. В момент времени 20 т, когда сумма аз+ау+а+ае уходит в блок 1, элементы памяти блока 3 переводятся в исходное состояние с помощью элемента 22 задержки величиной:0,3 г.В момент времени 2 Й на входы 9 блока3 поступает сумма а,+аз+а+аз+а 7, которая записывается в элемент памяти блока 3.Если приходящая в такте 22 сумма а+ае+ +а 1 е+а 14+ае является значащим числом, то на входы 7 и 8 блока 1 поступают сум.мы а+ае+а,+аз+п 17 и а 2+ае+а 1 о+а 14+ае соответственно. Начинается суммирование этой пары чисел, которое заканчивается в момент времени 2 б. Однако раньше (момент 24) на входе 9 блока 1 появляется сумма аз+а,+а+а 1 е +а 4+ав+а+ае которая 4 О записывается в элемент памяти блока 3,и хранится,до прихода суммыа 1+ае+а,+а,е+а,7+а,+ае+ао+а 14+ае (момент 26 т),В момент 26 г эта последняя пара частичных сумм поступает в блок 1 на суммирование, и в момент времени 30 в элементе памяти блока 3 записывается и хранится окончательный результат -а 1.50 1=Процесс сложения частичных сумм осуществляется по принципу дихотомии и поэтому быстро сходится. Время сложения частичных 55 сумм составляет не более п 1 о 2 п тактов. Таккак требуется т тактов для подачи т суммируемых чисел, то общее время сложения составляет не более (т+п 1 од,п) тактов. В среднем на одно число приходится не более бО иОЯ 2 п(1+ ) тактов.тСледовательно, чем больше суммируетсячисел, тем эффективнее используется время сложения, которое в пределе (при т -ж б 5 равно одному такту на число,360662 гЛ Предмет изобретения Устройство для ускоренного суммирования чисел, содержащее сумматоры, элементы задержки, блок сдвига числа и блок промежуточной памяти, отличающееся тем, что, с целью ускорения процесса суммирования больгпих массивов и- разрядных чисел, выход суммы К-го сумматора (с=1, , а) соединен с входом блока сдвига числа через элемент задержки на время 1"и - К) , а выход переноса г-го сумматора соединен с входом (а+1) -го 5 сумматора через элемент задержки на времят, входы -го сумматора соединены с выходами блока промежуточной памяти через элементы задержки на время ( - 1) т.360662 Уиг. 2 алова еда аказ 676/2278 Изд,1803 Тираж 406 ПодписиНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССМосква, Ж-ЗБ, Раушская наб., д, 4/5 п. Харьк. фил. пред. Патент Составитель И. ДолгушеваТехред Т. Миронова орректоры Л. Чуприна и Л. Царькова