Арифметическое устройство для выполнения операций над несколькими числами
Союз Советс»нк
Соцналнстнчес»нк
Ресаубпн» (63) Дополнительное к авт. сеид-ву (22) Заявлено 01,08р6 (21) 2392196/18-24 (51) М. Ел.2 с присоединением заявки Н©G 06 F 7/38
Государстаеииый комитет
СССР но деяаи изобретений и открытий (23) Приоритет (53) УД (681,325. .5 (088.8) Опубликовано 1505.79. Бюллетень М 18
Дата опубликования описания 15.0579 (72) Авторы
ИЗОбрЕтЕНИя В.и.жабин, В.И.Корнейчук и В.П.Тарасенко/
Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (71} Заявитель (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ
ОПЕРАЦИЙ НАД" НЕСКОЛЬКИМИ ЧИСЛАМИ
И з обрет ени е отн осит с я к вычисли тельной технике и может быть применено в специализированных и универсальных вычислительных машинах, а также в многопроцессорных вычисли тельных системах, построенных на основе больших интегральных схем.
Известно арифметическое устройство, содержащее сумматор, несколько регистров и логические элементы. В один момент времени в известном арифметическом устройстве может выполняться только одна операция над двумя операндами. В связи с этим устройство имеет невысокое быстродействие- при выполнении последовательности нескольких операций. Наиболее близким к изобретению по технической сущности является арифметичес-2р кое устройство, содержащее И решающих блоков для выполнения операций над двумя числами, коммутатор, блок сравнения кодов, регистр конца операции, выходы которого подключены к первой 25 группе входов коммутатора, блок уп.равления, первая группа выходов которого соединена с тактирующими входами решающих блоков для выполнения операций над двумя числами, а два ин-30
2 формационных входа первого решающего блока для выполнения операций над двумя чйслами подключены к входным шинам соотнетственйо первого и второго операндов. В том случае, когда
I процесс вычисления может быть распараллелен во Времени, в решающих блоках этого устройства могут выполнять ся различные операции в бдин момент времени ° Однако и это известное устройство имеет невысокое быстродействие при выполнении последовательности нерасйараллеливаемых операций (результат j-й операции является операндом для (j+1)-й операции), поскольку в указанном случае нельзя выполнять операции в режиме совмещения.
Время выполнения послЕдовательности, включающей k операций, для известного устройства определяется выражением к .Е t), ) 1 где ) - время выполнения 5- и операции. Например, если каждая опе-, рация требует.п тактов вычисления (n — разрядность операндов), то для получения окончательного результата необходимо выполнить kn тактов.
3 66293 мо;х
Целью изобретения является увеличение быстродействия. В предлагаемом устройстве это достигается тем, что оно содержит блок формирования результата, регистр сдвига и N-1 эле-ментон еадержии, причем вход j-го (3=1, N — l ) элемента задержки соединен с входной шиной (j+2) -ro оне1ранда, а выход — с первым информационным входом (j+1) -ro решающего блока для выполнения операций над двумя числами, выход которого соединен со вто-10 рым информационным входом (j+2)-ro решающего блока для выполнения операций над двумя числами и соответствующим входом второй группы коммутатора, причем Выход N-ro решающего блока для 15 выполнения операций над двумя числами соединен с третьим информационным входом первого решающего блока для выполнения операций над двумя числами, выход коммутатора соединен с первым 20 входом блока формирования результата, ко второму входу которого подключен выход блока управления, к третьему входу подключен выход блока сравнения кодов, первая группа входов которого соединена с выходами регистра конца операции, вторая группа входов соединена с соответствующими выходами регистра сдвига и управляющими входами решающих блоков для выполнения операций над двумя числами, вход регистра сдвига соединен с выходом блока управления.
На чертеже представлена структурHBH схема предлагаемого арифметического устройства.
Оно содержит N решающих блоков
11- 1 для выполнения операций над двумя числами, блок управления 2, коммутатор 3, N-разрядный регистр 4 конца операции, блок 5 сравнения ко- 40 дав, N-разрядный регистр сдвига 6, блок 7 формирования результата, N-1 элемецтов задержки 81-8 g g управляющую шину 9 и входные шины операндов
101-10 < . В качестве решающих бло- 45 ков 1 -.11 применяют блоки, позволяющие совмещать во времени процессы по разрядного ввода операндов и поразрядного формирования результата, начиная со старших разрядов. Для пред- Q) ставления результата в решающих бло- . ках 11-lN применяют избыточйую бднородную позиционную систему счисления,цифры которой кодируются неизбы;т)очным двоичным кодом (0,1 .Цифры из- 5 быточной системы счисления представляются на выходах решающих блоков 11-1 единичными или нулевыми сигналами на
Q--glog g(различных шинах, где с(.количество цифр (символов) избыточной системы счисления. Например, для двоичной системы счисления с цифрами
Г
1,0, 1) имеет место (}=11од2 3(=2. Число решающих блоков ие зависит от числа операций „образующих последова-! тельность, и определяется выражением 65
6, 4 . (и+ h1
N=j ), где п-разрядность операнЬ й: дсв, а h — задержка формирования первого разряда результата (выраженная в числе тактов) в решающих блоках
1 -1N после ввода первых разрядов операндов . Например, если h=2, то после ввода первых разрядов операндов на первом такте вычисления пер-. вый разряд результата получают через два такта, т.е. на третьем такте.
Выходы каждого решающего блока 1 (j=1,, N-1) подключены к группе входов решающего блока i i, а выходы решающего блока l соединены с группой входов решающего блока 1. Группа выходов блока управления 2 подключена к тактирующим входам блока 7 формирования результата и к тактирующим входам решающих блоков 11-1, выходы которых через коммутатор 3 соединены с информационными входами блока 7 формирования результата, а к управляющему входу последнего подключен выход блока 5 сравнения кодов. Выходы регистра 4 конца операции подключены к управляющим входам коммутатора 3 и к одной группе информационных входов блока 5 сравнения кодов, вторая группа информационных входов которого соединена с выходами регистра сдвига 6. Выход каждого j-ro разряда регистра сдвига 6 (j=1,N) подключен к управляющему входу решающего блока 1, а управляющий вход регистра сдвига 6 соединен с одним выходом блока управления 2. Входные шины
Операндов 101 и 102 подключены к двум соответствующим информационным входам решающего блока li, а к одному информационному входу каждого решающего блока 1 (j=2,N) через элементы задержки 8j i подключены входные шины операндов 10j 1 . Управляющая шина 9 подключена к цепи выдачи кода регистра 4 конца onåðàöèè . Блок 7 формирования результата является преобразователем чисел, представленных последовательным избыточным кодом, в неизбыточную (каноническую} систему счисления.
Допустим, необходимо выполнить последовательность, состоящую из k двухместных операций. Если число операций, образующих последовательность, равно числу решающих блоков, т.е. k=N, то последовательность опе- раций выполняется за один цикл..
Если же k)N, то процесс вычисления условно разбивается на несколько циклов, в каждом из которых выполняется не более N операций. В первом цикле вычислений на входные шины операндов 101 -10 1 поступает первая группа, включающая N+1 операндов, представленных последовательным кодом. В последующих циклах на входные шины операндов 102 -10gig поступают
5 662936 группы иэ N операндов (в последнем цикле число операндов может быть меньше N).
В исходном состоянии в первом разряде регистра сдвига 6 записана единица, а в регистре 4 конца операции единица записана в разряде с номером 5 к(тос К),ее и к(пос1М) <();
И, ecnu к (mod N) = g.
В каждом i-м такте первого цикла на, 10
° входные шины операндов 101-10 1 поступают i-е разряды соответствуюащх операндов. Каждый решающий блок 11 "1H выполняет определенную операцию, а тактирующие сигналы для них вырабатывает блок управления 2. После выполнения первых h+1 тактов на выходах решающего блока 11 присутствует первый разряд избыточного кода первого промежуточного результата.
В (h+2) -м такте этот разряд начинает обрабатываться в решающем блоке 12, для которого данный разряд является первым разрядом одного операнда. Одноименный разряд неизбыточного кода другого операнда для решающего блока
1 2 поступает с выхода элемента задержки 81,который задерживает разряды операнда на такое же число тактов, как и решающий блок 11, т е. íà h+1 тактов. В дальнейшем разряд промежу- 30 точного результата, полученный в решающем блоке 12, в следующем такте начинает обрабатываться в Решающем блоке 15 и т.д., т.е. разряд промежуточного Результата, полученный в i-м 35 такте на выходах решающего блока 1j, используется в качестве очередного разряда операнда в решающем блоке 1 1 на (i+1) -м такте. Каждый элемент задержки 8 задерживает разряды соответствующиХ операндов íà j (h+1) тактов, обеспечивая тем самым подачу разрядов операндов на вход решающего блока 1 +1 одновременно с разрядом промежуточного результата, сформированного в решающем блоке 1, который поступает на другие информационные входы решающего блока 1 +1 . После . выполнения первых n+h тактов решающий блок 11 выдает на входы решающего блока 12 и-й(последний) разряд первого промежуточного результата, т.е. освобождается от выполнения возложенной на него операции . B последующих тактах решающий блок 11 может обрабатывать разряды промежуточного ре-. 55 зультата, формирующиеся в решающем блоке 1 (.
Число N выбрано таким, что к моменту появления первого разряда промежуточного результата на выходах 60
Решающегб блока 1 (решающий блок 11 оказывается свободным.
На этом заканчивается первый цикл вычислений.
Второй цикл вйчислений начинается с момента поступления первого (старjaего) разряда промежуточного результата с выходов решающего блока 1 (на входы решающего блока 11. Одновременно с этим на входные шины операндов
102 -10N,начинают поступать разряды операндов следующей группы. Циклы работы устройства повторяются до тех пор, Пока на входные шины операндов
10 не будут приняты операнды всех
k операций.
Одновременно с подачей последней группы операндов на управляющую шину
9 поступает си,гнал, действующий до окончания работы устройства и осуществляющий выдачу кода регистра 4 конца операции. Номер с6 разряда регистра 4 конца операции, в котором записана единица перед, началом вычислений, соответствует номеру решающего блока, который в последнем цикле выполняет
k-ю операцию в заданной последователь ности операЦий.
В каждом цикле вычислений после выполнения h+1 очередных тактов по сигналу блока управления 2 осуществляется сдвиг единицы в регистре сдви,га б на один разряд вправо и в результате этого на управляющий вход решающего блока 1j поступает единичный сигнал с выхода j- ãî разряда регист ра сдвига 6. Этот сигнал тактируется сигналами блока управления 2, поступающими на определенные тактирующие шины решающих блоков 11-1, в результате чего решающий блок 1) устанавли- вается в исходное состояние для вы- полнения определенной операции непосредственно перед тактом поступления на его входы первых разрядов операндов данной операции.
Таким образом, в момент формирования первого разряда промежуточного результата в решающем блоке 1 присутствует единичный сигнал на выходе
j-ro разряда регистра сдвига б. В последнем цикле работы после сдвига единицы в разряд с номером о6 регистра сдвига 6 решающий блок 10, начинает выйолнять последнюю операцию в задан:ной последовательности и íà его выходах в каждом последующем такте присутствуют очередные разряды окончательного результата. Так как в исходном состоянии в регистре 4 конца операции записана единица в разряде с номеромса,то после сдвига единицы в регистре сдвига б в разряд с номе ром g блок 5 сравнения кодов выдает на управляющий вход блока 7 формирования результата сигнал, соответствую. щий равенству кодов, который иниции-. рует начало работы блока 7 формирования результата. В этом случае очередные разряды окончательного результата с выходов решающего блока 1,через коммутатор 3, которым управляет регистр 4 конца операции, поступают на информационные входы блока 7 формирорания результата, где осуществляется преобразование последовательного иэ662936 формула изобретения
35 ЦНИИПИ Заказ 270 l j50 Тираж 779 Подписное филиал ППП Патент,г.ужгород,ул.Проектная.4 бытфтчжого кода окончатель фго результата в неизбыточный параллельный код (найример, путем суммирования кодов цифр избыточной системы счисления с учетом из весов по правилам неизбыточной системы счисления, т.е. с
"расйрбстрайением переносов в старшие 5 разряды результата) .
Работа блока 7 формирования результата тактируется сигналами блока управления 2 Общее число тактов, необхоДймсЖ для получения и разрядов (} о кончательного, результата в предлагаемом устройстве равно k(h+1)+n-1.
Если каждая из операций, обраэую}цих йоследовательностb, выполняетс я.. в решающих блоках известного устрой- }5 стВа за и тактов, то выигрыш в быстродействий при использовании предла- . гаемого устройства определяется откп ношением „,,, r, которое с увелик Н+ 1)+и -1
И. чением. )с приближается к значению- -;—
Например, при h=2 и n=30 это состав ляет величину 10.
Таким обраэом; предлагаеМое уст- ройство позволяет уменьшить время вы25 .полнения последовательности операций;Кроме того, благодаря поразрядному вводу и выводу информации решающие бйоки предлагаемого устройства имеют . небольшое число входов и .выходов, что Э0 существенно упрощает их реализацию. в виде ббльших интегральных схем, Арифметическое устройство для" вы" йолнения" операций над несколькими числами, содержащее N решающих блоков для выполнения операций кад" двумя числами,, коммутатор, блок сравне10 ния колов регистр конца операции выходы которого подключены к первой группе входов коммутатора, блок управления, первая группа выходов которого соединена с тактирующими входами решающих, блоков для выполнения операций над двумя числами, а два информационных входа первого решающего блока для выполнения операций над двумя числами подключены к входным шинам соответственно первого и второго операндов, о т л и ч а ющ е е с я тем, что, с целью увеличения быстродействия, оно содержит блок формирования результата, регистр сдвига и N-1 элементов задержки, причем вход j-го (j=l,N-l) элемента задержки соединен с входной шиной ()+2)-гo oп@pандa,-а выход - с первым информационным входом (}+1)-го решающего блока для выполнения операций над двумя числами, выход которого соединен со вторым инФормационным входом (j+2)-го решающего блока для вы- . полнения операций над двумя числами и "соответствующим входом второй группы коммутатора, причем выход N-ro реШающего блока для выполнения операций над двумя числами соединен с третьим информационным входом первого решаю его блока Для выполнения операций кад двумя числами, выход коммутатора соединен с первым входом блока форми рования результата, ко второму входу которого подключен выход блока управления, к третьему входу подключен выход блока сравнения кодов,.первая группа входов которого соединена с выходами регистра конца операции, вторая группа входов соединена с соот ве ствуюмИми выходами регистра сдвига и управляв}щими входами решающих блоков для выполнения операций над двумя числами, вход регистра сдвига соединен с выходом блока управления.