Устройство для вычисления сумм произведений

Союз СоветскихСоциалистическихРестубттик ВТОРСКОМУ СВИДЕТЕЛЬСТВ-в 1)М. К 9 т 2801/18 оеаинением заявки Эй с при (26) П С Вб Е 7/5 Ъаударственный комнтет СССР оо девам нзобретеннй(72) Авторы изобретени уцкий, А.В. Корочкин, Ю,А. Кулак:.;, и А.Н. Долголенко иевскии ордена м, 50-летия Ве енина политехничекой Октябрьской сволюции ии инст иалисти Зая интел кои т) У Изобретение относится к цивычислительной технике и можисгользовано при построениизированных вычислительных сисИзвестно устройство для выния операций над матрицами иторами, которое содержит регидля занесения слагаемых и сомтелей, а также ряд логическихсвязанных с этими регистрамипрямой и обратной связиОднако в таком устройствеуровень распараллеливания вычний, обусловленный тем, что а Фровой ет Сыть специал ем, олне тры ожи хе изкислеготройном м умножения чисел в этих у ах основан на последовател и з сому,что сомно" множ димы дляИ пар ну" жжит оро жимого и множит значения поразр мое длясомножимнож обрателе плении разрядов одно телей. Это приводит оды устройств новую ей можно принимать н акте, а только через ство тактов, необход отки предыдущей пары СТВО ДЛЯ ВЫЧИСЛЕНИЯ СУМИ ПРОИЗВЕДЕНИ Известны устройства для вычисления сумм произведений, содержащие матричное множительное устройство. Устройства содержат два регистра, накапливающий сумматор, шину тактовых импульсов, шину установки в "0" и матрицу одноразрядных элементов. На входы устройства оба сомножителя принимаются параллельным кодом, причем на каждом следующем такте осуществляется прием новой пары сомножителей 21 и 1,3 .Недостатком этих устройств является то, что после подачи на входы устройств последней пары сомножителей, подлежащей суммированию, пары сомножителей новой суммы могут риниматься только по истеченииекоторого множества И холостых та тов. Холостые такты неэбхоприема на входы устройствлевых значений мнов результате чегоных сумм и переносов выходят иматричного множительного устройства,состоящего из одноразрядных модулей,и суммируются ь накапливающем сумматоре. Так для первого и второгоустройств количество холостых тактов М = 3 и + 1 оуЧ - 1, где и - разрядность операндов, (М) - количество пар сомножителей, подлежащихсложению, в третьем же устройствев связи с применением специальнойсхемы анализа достигается некотороеуменьшение этой составляющеи. Крометого, к недостаткам первого и третьего устройств следует отнести такжеограниченные функциональные возможности, а именно то, что сомножителимогут представлять собой только коды положительных чисел, это существенно снижает область применениятаких устройств,Наиболее близким по техническомурешению к изобретению является устройство для вычисления сумм произведений. 1 О 20 Устройство для вычисления сумм произведений содержит матрицу ьыцислительных элементов, которая содержит и+1 строк, первые три строки имеют (2 и+1). вычислительных элементов, каждая последующая строФа матрицы имеет на один вычислительный элемент меньше, последняя строка содержит (и+3) вычислительных элементов, (и+1)-разрядные первый и второй регистры операнда (где и - разрядность операндов), первую и вторую группу элементов И-НЕ, накапливающий сумматор, причем первая входная шина соединена с информационными входами первого регистра операнда, вторая входная шина соединена с информационными входами второго регистра операнда, вь 1 ходы значащих разрядов первого регистра операнда и второго регистра операнда соответственно соединены с гервыми входами элементов И-НЕ первой и второй групп, вторые входы элементов И-НЕ первой группы соединены с выходом знакового50 разряда второго регистра операнда, вторые входы элементов И-НЕ второй группы соединены с выходом знакового разряда первого регистуа операнда, первые и вторые информационные входы накапливающего сумматора соответ 55 ственно соединены с (и+2) младшими выходами и с (и+2) старшими выходами вычислительных элементов по 144следней строки матрицы, первый управляющий вход накапливающего сумматора подключен к шине установки вноль, выходы накапливающего сумматора соединены с выходной шинойустройства, шина тактовых импульсовсоединена со вторым управляющим входом накапливающего сумматора, суправляющим входом каждого вычислительного элемента матрицы, с угравляющими ьходами первого и второгорегистров операндаС помощью этого устройства возможно вычисление сумм произведений операндов, представленных доголнительным двоичным кодом, На каждом тактена входы устройства осуществляетсяприем параллельных кодов двух оцередных сомножителей. После приемапоследней пары сомножителей на входыустройства в течение ,3 + о 1 М - 1)тактов необходимо подать нулевыесомножители. Таким образом, количество холостых тактов для этого устройства является довольно значительным, цто существенно снижает производительность устройства.Цель изобретения - увеличение производительности устройства.Поставленная цель достигается тем, что в устройство введены первый, второй, третий григгеры, причем первый и второй выходы каждого 1,1)-го вычислительного элемента (. = 1, 2,и;1 = 2, 32 и) соединены соответственно с первым входом 1+1,1-1) - го вычислительного элемента и вторым входом (1+1, 3 +1)-го вычислительного элемента, а выходы поразрядной суммы и переноса соответственно со входом поразрядной суммы (1+1,3) -го вычислительного элемента и входом переноса (1+1, 1-1)-го вычислительного элемента, первый выход каждого (1,1)-го ь,числительного элемента (1 = 1, 2, и,3=1) соединен со вторым входом (1+1, 1) -го вычислительного элемента, а выход поразрядной суммы - со входом поразрядной суммы (1+1,3) -го вычислительного элемента, выход переноса ,1,3)-го вычислительного элемента (1=1,2; 1 - 2 и+1) соединен с входом переноса(1;1,1) -го вычислительного элемента, вход переноса (2 и+1)-го вычислительного элемента второй строки матрицы соединен с выходом. первого триггера, вход переноса (2 и+1)-го вычислительного элемента третьей строки матрицы соединен с выходомв ходом второго .триг- сумматора второй и третий входы кото 1гера, информационформационный вход которого рого соответственно соединены с высоединен с выходом третьего тригге- ходами триггеров поразрядной суммы ра, управляющие входы первого, второ- и переноса, первый выход полусуммаго и третьего триггероверов объединены 5 тора является выходом переноса вычиси подключены к шине т кк ине тактовых импуль- лительного элемента, второй выход сов, первые и вторыее вторые входы вычис- полусумматора является выходом полительных элементов нече ннечетных столб- разрядной суммы вычислительного элецое первой строки матрицы поразрядно связаны соответственно со с выходами 1 О Накапливающий сумматор устройства второго и первого регистров операнда, содержит первую группу из (и+оЯ+2) первые и вторые входе входы вычислительных полусумматоров, вторую группу из элементов четных столбцов первой (й+3 од+1) полусумматоров, первый строки матрицы поразрядно связаны (и+3 оцЯ-разрядный регистр, второй ;оответственно с младшими выходами 15 п+о,8+1)-разрядный регистр, третийго регистра операнда и с и стар- и четвертый (и+2)-разрядные регистпервого реги1 пе ваго шими выходами второго регистра опе- ры, причем тактовые входы и р ранда, входы поразрядной суммы и второго, третьего и четвертого ре" переноса вычислительных элементов гистров объединены и являются вторым с первого по и-й столбец первой 20 угравляющим входом накапливающего строки матрицы поразрядно соединены сумматора, информационные входы соответственно с выходами элемен- третьего и четвертого регистров явтов И-НЕ второй группы и с выходаляются соответственно вторым и перми элементов И-НЕ первой группы, а вым информационными входами накапливходы поразрядной суммы и переноса 25 вающего сумматора, (и+1) младшие развычислительных элементов остальных ряды третьего и четвертого регистров столбцов первой строки матрицы соот- поразрядно соединены с первыми и ветственно с выходом знакового раз- вторыми входами соответствующих ряда первого регистра операнда и с (1+1)-х младших полусумматоров первой выходом знакового разряда второго 30 группы, старшие разряды третьего и регистра операнда, которые соответ- цетвертого регистров соответственно ственно соединены со входами герво- соединены с первым и вторым входами го и третьего триггеров. Д о. + 1)-го полусумматора перьойКаждый вычислительный элемент группы, третьи входы (и+о;Х+1) старустройства содержит полусумматор, З 5 ших полусумматорое гервои группы элемент И, первый, второй триггеры, соединены поразрядно с выходами триггер переноса и триггер поразряд- второго регистра, выходы п д )+2 о 11+1) ной суммы, прицем тактовые входы младших и выходы (и+1 ор+1) стар- первого, второго триггеров, тригге- ших полусумматоров первой группы ров поразрядной суммы и переноса 40 поразрядно соединены с первыми и . объединены и являются управляющим вторыми входами полусумматоров второй входом вычислительного элемента, группы, выходы первого регистра со" информационный вход первого тригге- ответственно соединены с третьими ра является первым входом вычисли- входами 7+орХ) старших полусумма- тельного элемента, информационныи 45 торов второй гру и , д 1 Ры Гп+ЕоаР) вход второго триггера является вто- младших полусумматоров второй групрым входом вычислительного элемента, пы поразрядно соединены с информанформационные входы триггеров по- ционными входами первого регистра, разрядной суммы и переноса являются выходы (и+30 М ) У Уо 1+1) пол с мматоров соо ве ственно входами поразрядной 0 второй группы поразрядно соединеныами вто ого с ммы и переноса вычислительного с информационными входами р суммы и пеэлемента, выход первого триггера сое- регистра и являются выход мхо ами накапдинен с первым входом элемента И и ливающего сумматора, вход установкиго егист а является является первым входом вычислитель- в ноль перво р Р ного элемента, выход второго тригге- первым управляющим входом накаппира соединен со вторым входом элемен- вающего сумматора. та И и является вторым выходом выНа Фиг, 1 представлена стр уктурчислительного элемента, выход элемен- Ф2 ная схема устройства; на Фиг. та И соединен с первым входом полу 90581410 структурная схема вычислительногоэлемента; на фиг. 3 - структурнаясхема накапливающего сумматора,Устройство содержит матрицувычислительных элементов, каждый 5вычислительный элемент включает всебя полусумматор 2, элемент 3 И,триггер 4 поразрядной суммы, триггерпереноса, триггеры 6 и , накапливающий сумматор 8, регистры 9 и10 операнда, первую и вторую группу элементов 11 и 12 И-НЕ,триггеры13-15, накапливающий суматор 8 содержит 1 и+2)-разрядные регистры 16и 17, первую группу полусумматоров 1518, (и+ор М+1)-разрядный регистр19, вторую группу полусумматоров20, (и+3 оМ)-разрядный регистр 21.В устройстве для вычислениясумм произведений первая входная 20шина соединена с информационнымивходами регистра 9 операнда, втораявходная шина соединена с информационными входами регистра 10 операнда,выходы значащих разрядов регистра 9 25операнда и регистра 10 операнда соответственно соединены с первыми входами элементов И-НЕ 11 и 12, вторыевходы элементов И-НЕ 11 соединеныс выходом знакового разряда регистра зо10 операнда, вторые входы элементовИ-НЕ 12 соединены с выходом знакового разряда регистра 9 операнда, первые и вторые информационные входынакапливающего сумматора 8 соответственно соединены с (п+2) младшимивыходами и с (и+2) старшими выходамивычислительных элементов последнейстроки матрицы 1, первый управляющий вход накапливающего сумматора 8 оподключен к шине установки в ноль,выходы накапливающего сумматора 8соединены с выходной шиной устройства, шина тактовых импульсов соединена со вторым управляющим входом 45накапливающего сумматора 8, с управляющим входом каждого вычислительного элемента матрицы 1, с управляющимивходами регистров 9 и 10 операнда,первый и второй выходы каждого+1)-го вычислительного элемента,а выходы поразрядной суммы и переноса - соответственно со входом поразрядной суммы (1+1, 1)-го вычислительного элемента и входом переноса(1+1, -1) -го вычислительного элемента, первый выход каждого (,3)-говычислительного элемента (1=1,2,и, 1=1) соединен со вторым входом(1+1, 1) -го вычислительного элемента, а выход поразрядной суммы - совходом поразрядной суммы (+1,1)-говычислительного элемента, выходпереноса (1,1)-го вычислительногоэлемента (1 = 1,2, 1 = 2 п+1) соединен с входом переноса (1+1,)-говычислительного элемента, вход переноса (2 п+1)-го вычислительного элемента второй строки матрицы 1 соединен с выходом триггера 14, вход переноса (2 п+1)-го вычислительногоэлемента третьей строки матрицы 1соединен с выходом триггера 15, инФормационный вход которого соединенс выходом триггера 13, управляющиевходы триггеров 13-15 объединены иподключены к шине тактовых импульсов, первые и вторые входы вычислительных элементов нечетных столбцовпервой строки матрицы 1 поразрядносвязаны соответственно с выходамирегистров 9 и 10 операнда, первыеи вторые входы вычислительных элементов четных столбцов первой строкиматрицы поразрядно связаны соответственно с п младшими выходами регистра 9 операнда и с и старшими выходами регистра 10 операнда, входы поразрядной суммы и переноса вычислительных элементов с первого по и-йстолбец гервой строки матрицы 1поразрядно соединены соответственнос выходами элементов И-НЕ 12 и свыходами элементов И-НЕ 11, а входыпоразрядной суммы и переноса вычислительных элементов остальных столбцов первой строки матрицы 1 соответственно с выходом знакового разрядарегистра 9 операнда и с выходом знакового разряда регистра10 операнда, которые соответственно соединены со входамитриггера 14 и триггера 13, тактовыевходы триггеров 6 и 7, триггерапоразрядной суммы и триггера 5 переноса объединены и являются управляющим входом вычислительного элемента, информационный вход триггера6 является первым входом вычислительного элемента, информационныйвход триггераявляется вторымвходом вычислительного элемента,информационные входы триггерапоразрядной суммы и триггера 5переноса являются соответственно входами поразрядной суммы и переносавычислительного элемента, выходтри гера 6 соединен с первым входомэлемента И 3 и является первым входом вычислительного элемента матрицы 1, выход триггера 7 соединенсо вторым входом элемента И 3 и является вторым выходом вычислительного 10элемента матрицы 1, выход элемента И3 соединен с первым входом полусумматора 2, второй и третий входы ко,торого соответственно соединены свыходами триггера 1 поразрядной суммы и триггера 5 переноса, первыйвыход полусумматора 2 является выходом переноса вычислительного элемента матрицы 1, второй выход полусумматора 2 является выходом пораз орядной суммы вычислительного элемента матрицы 1, тактовые входы регистров 16, 17, 19 и 21 обьединеныи являются вторым управляющим входом накапливающего сумматора 8, информационные входы регистра 16 ирегистра 17 являются соответственновторым и первым информационными входами накапливающего сумматора 8,(и+1) младших разрядов регистров 16 зои 17 поразрядно соединены с первыми и вторыми входами соответствующих(и+1) младших полусумматоров 18,старшие разряды регистров 16 и 17соответственно соединены с первыми вторым входами ,оуХ+1)-го полусумматора 18, третьи входы (й+ЯоцМ+1)старших полусумматоров 18 соединеныпоразрядно с выходами регистра 19,выходы (И+90."1+1) младших и выходь(и+Во,11+1) старших полусумматоров18 поразрядно соединены с первыми ивторыми входами полусумматоров 20,выходы регистра 21 соответственносоединены с третьими входами45;11+РопМ) старших полусумматоров 20,выходы 111+80;11) младших полусумматоров 20 поразрядно соединены синформационными входами регистра21, выходы (1 гт 41. +1) полусумма Оторов 20 поразрядно соединеныс информационными входами регистра 19 иявляются выходами накапливающегосумматора 8, вход установки в нольрегистра 21 является первым управляющим входом накапливающего суммато. ра 8.Устройство работает следующим образом.В первом такте на входы регистра 9 операнда и на входы регистра 10 операнда принимается первая пара сомножителей, представленная дополнительным двоичным кодом. Во втором такте содержимое укаэанных регистров передается на триггеры 6 и. 7 первой строки матрицы 1 вычислительных элементов, причем благодаря имеющимся жестким связям между регистрами 9 и 10 и матрицей 1 вычислительных элементов в триггеры 6 первой строки матрицы 1 вычислительных элементов передается код Ь а 1) й,1 ,Ь 1,ь , а в триггеры 7 - код1 1вЬ ,овВместе с этим в зависимости от ,знаков сомножителей на триггеры 11 ,поразрядной суммы и триггеры 5 переноса первой строки матрицы 1 вычислительных элементов через первую ,и вторую группы элементов И-НЕ 11, 12 запишутся удвоенные обратные коды содержимого регистров 9 и 10. При этом, если произошла передача удвоенного обратного кода какого- либо из сомножителей на входы матрицы 1, то в триггер 13 или в триггерзаписана единица, предназначенная для формирования удвоенного дополнительного кода этого сомножителя. Передача на входы матрицы 1 вычислительных элементов удвоенного дополнительного кода содержимого регистра 9, если первый сомножитель меньше нуля и наоборот, представляет собой коррекцию результата, так как в результате перемножения в матрице 1 вычислительных элементов сомножителей, представленных дополнительным двоичным кодом, причем знаковые разряды сомножителей участвуют в выполняемой операции наравне со значащими, происходит искажение результата. В этом же такте на входы регистров 9 и 10 операнда принимается новая пара сомножителей. Зависимость результатов от знаков сомножителей представлена таблице.12 905811 Дополнительныекоды А и В Результаты без коррекции Сомножители А и В=Й-21 Р 1+1 А 1 х)В 1+21 А 1+2 В 1 Примечание: прид(Оиэлементов р четверка пр щий разряд,Формирование произведения в виде поразрядных сумм и переносов происходит в результате передачи информации с -ой строки матрицы 1 на (1+1)-ю строку, гри этом 1-е частичное произведение формируется в виде поразрядных коньюнкций содержимого триггеров 6 и 7 1-ой строки матрицы 1, а накопление суммы частичных произведений осуществляется в триггерах 1 поразрядных сумм и триггерах 5 переносов. Содержимое триггера 6 1-ой строки матрицы 1 вычислительных элементов передается в триггеры 6 (1+1)-ой строки со сдвигом на один разряд влево, а содержимое триггеровсо сдвигом на разряд вправо, что обеспечивает формирование всех и+1-х частичных произведений.С выходов последней строки матрицы 1 вычислительных элементов, содержащей (и+3) одноразрядных элемента, значения (и+2)-ух старших поразрядных сумм и (и+2)-ух переносов, представляющих собой (и+2) старших разряда произведения, записываются в регистры 16 и 17 накапливающего сумматора 8. В следующем такте на эти регистры приняты (и+2) старших разряда нового произведения, а в это же время с выходов полусумматоров 20 на входы регистра 21 и регистра 19 записываются и+о 1;И +1 старшие разряды суммы ранее поступивших произведений в виде поразрядных сумм и переносов.Таким образом, при помощи предлагаемого устройства возможно нахождение и+1 о; И+1 старших разрядов суммы произведений И пар операндов,8 (О на выходах матрицы 1 вычислительныхезультат - 2181-21 Д 1+1 А х 81, так какедставляет собой переносы в несуществуюпредставленных дополнительным кодом,при этом на каждом следующем тактена входы устройства может быть принята новая пара сомножителей. ЧерезИ+и+2 такта с выходов полусумматоров20 может быть считан результат ввиде поразрядных сумм и переносов,при этом уже на (И+1)-ом такте накоды устройства могут приниматьсяпары сомножителей следующей последовательности, произведения которыхподлежат сложению, Для получения навыходах устройства результата с распространенными переносами пары сомножителей новой последовательностимогут приниматься только лишь поистечении п+0 одпИ тактов после по" 35дачи последней йары сомножителейпредыдущей последовательности. Втечение п+2 од Л холостых тактовна входы устройств должны записываться нулевые значения сомножителей.40Устройство требует п 9 о 1;И холостых тактов, .в то время как для выполнения тех же функций при помощиизвестного необходимо 3 п+ФоИ холостых тактов. Тем самым достигается существенное увеличение производительности устройства, что имеетважное значение для многих практических приложений, связанных,нагример, с матричной алгеброй.50 формула изобретения1. Устройство для вычисления сумм произведений, содержащее матрицу вычислительных элементов, которая содержит и+1 строк, первые три строки имеют 2 п+1 вычислительных элемен90581 30 50 тов, каждая последующая строка матрицы имеет на один вычислительныйэлемент меньше, последняя строка содержит П+3 вычислительных элементов,.(и+1)-разрядные первый и второй регистры операнда (где и - разрядность операндов), первую и вторуюгруппу элементов И-НЕ, акапливающийсумматор, причем первая входнаяшина соединена с информационными 10входами первого регистра операнда,вторая входная шина соединена с информационными входами второго регистра операнда, выходы значащих разрядов первого регистра операнда и 15второго регистра операнда соответственно соединены с первыми входамиэлементов И-НЕ первой и второй групп,вторые входы элементов И-НЕ первойгруппы соединены с выходом знакового 20разряда второго регистра операнда,вторые входы элементов И-НЕ второйгруппы соединены с выходом знакового разряда первого регистра операнда, первые и вторые информационные входы накапливающего сумматорасоответственно соединены с (и+2)младшими выходами и с (и+2) старшими выходами вычислительных элементов последней строки матрицы,первый управляющий вход накапливающегосумматора подключен к шине установки в ноль, выходы накапливающего сумматора соединены с выходной шинойустройства, шина тактовых импульсовсоединена с вторым управляющим входом накапливающего сумматора, с управляющим входом каждого вычислительного элемента матрицы, с управляющими входами первого и второго регистров операнда, о т л и ч а ю щ е е с ятем, что, с целью повышения производительности устройства, в него введены первый, второй, третий триггеры, причем первый и второй выходы 45каждого (д,1)-го вычислительногоэлемента (1=1п,1=22 п) соединены соответственно с первым входом (1+1, 1-1)-го вычислительногоэлемента и вторым входом (.1.+1,1+1)-го вычислительного элемента,а выходы поразрядной суммы и перено.са соответственно с входом поразрядной суммы (1+1,1)-го вычислительного элемента и входом переноса55(.1+1, 1-1)-го вычислительного элемента, первый выход каждого (1,1) -говычислительного элемента (1.=1,2,п,1=1) соединен с вторым входом 4 14(1+1,) -го вычислительного элемента, а выход поразрядной суммыс входом поразрядной суммы (1+1,1)-говычислительного элемента, выход переноса (1,1) -го вычислительного элемента (1=1,2,1=2 п+1) соединен с входом переноса (+1,1)-го вычислительного элемента, вход переноса(2 п+1) -го вычислительного элементавторой строки матрицы соединен с выходом первого триггера, вход переноса (2 п+1) -го вычислительного элемента третьей строки матрицы соединен с выходом второго триггера,информационный вход которого соединенс выходом третьего триггера, управляющие входы первого, второго итретьего триггеров объединены и подключены к шине тактовых импульсов,первые и вторые входы вычислительных элементов нечетных столбцов первой строки матрицы поразрядно свя,заны соответственно с выходами второго и первого регистров операнда,первые и вторые входы вычислительных элементов четных столбцов первойстроки матрицы поразрядно связанысоответственно с и младшими выходамипервого регистра операнда и с истаршими выходами второго регистраоперанда, входы горазрядной суммыи переноса вычислительных элементовс первого по и-й столбец первойстроки матрицы поразрядно соединенысоответственно с выходами элементовИ-НЕ второй группы и с выходамиэлементов И-НЕ первой группы, авходы поразрядной суммы и переносавычислительных элементов остальныхстолбцов первой строки матрицы соответственно с выходом знаковогоразряда первого регистра операндаи с выходом знакового разряда второго регистра операнда, которые соответственно соединены с входамипервого и третьего триггеров,2, Устройство по и 1, о т л ич а ю щ е е с я тем, что каждыйвычислительный элемент содержитполусумматор, элемент И,первый,второй триггеры, триггер переноса итриггер поразрядной суммы, причемтактовые входы первого, второготриггеров, триггеров поразряднойсуммы и переноса объединены,и являются управляющим входом вычислительного элемента, информационныйвход первого триггера является первым входбм вычислительного элемента,