Арифметическое устройство

 

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

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

Республик

Оп ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6!) Дополнительное к авт. свид-ву— (22) 3аявлено 04.07.74 (21) 2040865/24 с присоединением заявки №(23) Приоритет(43) Опубликовано 25.02.77Бюллетень № 7 (45) Дата опубликования описания 22.04.77 (11) 547764 (5l) М. Кл.в

606 Г 7/38

Государственный комитет

Соввта Министров СССР по делам изобретений и открытий (53) УДК 681.325 (088.8) Н. М. Бондаренко, В. И. Пустоваров, B. И. Сапрыкин и A. И. Флеров (72) Авторы изобретения

Киевский ордена Ленина политехнический институт имени 50-летия Великой Октябрьской социалистической революции впту

f " ц 3HMFpT3q (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО

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

Известны арифметические устройства (АУ) используемые в цифровой вычислительной технике для модификации адресов операндов при обработке информационных массивов (lj

Наиболее близким по технической сущ- 1р ности к предлагаемому является АУ, содержащее регистр адреса, сумматор, индексный регистр, блок определения окончания массива, управляющие входы которых подключены к первому, второму, третьему и четвертому д выходам=блока управления соответственно, регистр команд, первый выход которого подключен к первому входу блока управления, второй выход — к первому входу блока определения окончания массива, третий выход- 20 к первому входу индексного регистра, а четвертый выход — к первому входу сумматора, выход которого соединен с первым входом регистра адреса, выход которого соединен с первым выходом устройства j21. 25

Это АУ входит в состав цифровой вычислительной машины (ЦВИ) и работает совместно с другими устройствами I1BN, а именно, с запоминающим устройством (ЗУ) и схемой сравнения чисел, Под схемой сравнения чисел подразумевается операционная схема со своим устройством управления, выполняющая сравнение кодов числа Х и числа у и формирующая сигналы x < v., Х ., X = y. с

Один из недостатков известного АУ заключается в том, что при реализации способов ускоренной обработки информационных массивов, например, при ускоренном поиске информации по дихотомическому способу, когда вычисляются переменные приращения индекса, имеют место большие непроизводительные затраты рабочего времени АУ на обращение к ЗУ, что снижает его быстродействие.

Действительно, при сравнении числа )( с массивом Y упорядоченных по возрастанию чисел У. для определения соотношений вида

EA ).x. ;,И; 4 =у;й;1 т

547764 где < — номер числа в массиве ((= 0,1,2,..., И);

А; — адрес ячейки ЗУ, в которой хранится число у, с применением ускоренного поиска по дихотомическому способу адреса чисел У, вычисляются АУ в каждом цикле сравнения чисел х и у; согласно выражению

Ai ид; =БА э;, () где ИА — исполнительный адрес, формируе- о мый в -м цикле (j = 1,2,.„rn);

5A — базовый адрес массива чисел, равный адресу числа у

3 — индекс. 35

Индекс J вычисляется по формуле

Л =Э ьЭ.,, (2} где A3 — приращение индекса, причем

, = ««< (»;,/г+о.s) (з)

Начальные значения индекса и приращения задаются соотношениями:

3,=0; Ы =enabler (n/2+0.5) (4)

Знак приращения в каждом цикле, кроме первого (в первом цикле знак всегда "плюс зависит от результата сравнения чисел Х, и 7; в схеме сравнения чисел в предыдущем цикле.

Основной функцией АУ в этой задаче яв- зо ляется вычисление исполнительного адреса

ИА„путем выполнения операций, заданных выражениями (1, 2, 3), но, поскольку в известном АУ не предусмотрено автоматическое изменение приращения индекса в со- Zg ответствии с выражением (3), такое изменение выполняют в каждом цикле по командам, считываемым из ЗУ. Многократное обращение к ЗУ приводит к потерям времени и снижает быстродействие АУ. 40

Таким образом, вследствие ограничения функциональных возможностей известного

АУ, заключающегося в невозможности изменять приращение индекса в соответствии с заданным способом обработки массива, 45 проявляется его недостаток — низкое быстродействие .

Целью изобретения является повышение быстродействия АУ.

Поставленная цель достигается тем, что 5ц

АУ дополнительно содержит регистр исполнительного адреса, блок определения нулевого приращения, регистр-счетчик и сдвигатель, выход которого соединен со входом регистра-счетчика, выход которого соеди- 5 нен со входом блока определения нулевого приращения и вторым входом сумматора, выход сумматора соединен со вторым входом блока определения окончания массива, выход которого соединен с четвертым вхо4 дом блока управления, пятый, второй и третий входы которого соединены со внешними входами устройства, шестой вход блока управления соединен со вторым выходом индексного регистра и вторым входом сдвигателя, а седьмой вход блока управления соединен с выходом блока определения нулевого приращения, пятый, шестой и седьмой выходы блока управления соединены с управляющими входами регистра исполнительного адреса, регистра-счетчика и сдвигателя соответственно, Восьмой выход блока управ ления соединен со вторым выходом устройства. Третий вход сумматора соединен с выходом регистра исполнительного адреса, в вход которого соединен с выходом регистра адреса. Второй вход регистра адреса соединен со вторым выходом регистра команд, четвертый выход которого соединен с третьим входом регистра адреса и третьим входом блока определения окончания массива, второй вход сумматора соединен со вторым входом индексного регистра.

При таком построении схемы АУ автоматическое изменение приращения индекса организуется с помощью лишь одной команды формата, соответствующего структуре регистра команд. Обращение к ЗУ за командой изменения приращения индекса осуществляется всего лишь один раз за весь периОд поиска, благодаря чему время решения задачи поиска уменьшается, и, следовательно, быстродействие АУ увеличивается.

Кроме того, необходимый для решения задачи поиска объем ЗУ значительно уменьшается, поскольку количество дополнитепьных ячеек, необходимых для хранения команд, с помощью которых задается алгоритм изменения приращения индекса, минимально (1 ячейка, длина которой равна разрядности регистра команд АУ), На фиг. 1 изображена структурная схема арифметического устройства; на фиг. 2 - таблица циклов работы арифметического устройства.

Арифметическое устройство содержит регистр адреса 1, сумматор 2, индексный регистр 3. блок 4 определения окончания массива, подключенные своими управляющими входами к первому, второму, третьему и четвертому выходам блока управления 5 соответственно, регистр команд 6, первый выход которого подключен к первому входу блока управления 5, второй выход — к червому входу блока 4 определения окончания массива, третий выход — к первому входу индексного регистра 3, а четвертый выходк первому входу сумматора 2. Выход сумматора 2 соединен с первым входом регисч ра адреса 1, выход которого соединен с

547764 первым выходом устройства. Кроме того, арифметическое устройство содержит регистр исполнительного адреса 7, блок 8 определения нулевого приращения, регистр-счетчик

9 и сдвигатель 10, выход которого соединен со входом регистра-счетчика 9. Выход последнего соединен со входом блока 8 определения нулевого приращения и вторым входом сумматора 2, выход которого соединен со вторым входом блока 4 определе- 0 ния окончания массива. Выход блока 4 определения окончания массива соединен с четвертым входом блока управления 5, пятый, второй и третий входы которого соединены со внешними входами устройства. Шес- 15 той вход блока управления 5 соединен со вторым выходом индексного регистра 3 и вторым входом сдвигателя 10. Седьмой вход блока управления 5 соединен с выходом блока 8 определения нулевого приращения. Пятый, шестой и седьмой выходы блока управления 5 соединены с управляющими входами регистра 7 исполнительного адреса, регистра-счетчика 9 и сдвигателя 10 соответственно, а восьмой его выход соединен 25 со вторым выходом устройства. Третий вход сумматора 2 соединен с выходом регистра

7 исполнительного адреса, вход которого соединен со вторым выходом регистра команд 6. Четвертый выход регистра команд 0

6 соединен с третьим входом регистра адреса 1 и третьим входом блока 4 определения окончания массива . Второй вход сумматора 2 соединен со вторым входом индексного регистра 3.

До начала работы АУ в регистр команд

6 из ЗУ поступает команда, содержащая код операции Оп, признак индексации ПрН, адрес верхней границы массива А, базовый

».B адрес массива БА и приращение индекса йЗ 4о (величины представлены позиционным двоичным кодом). Затем АУ работает без обращений к ЗУ, причем, поскольку величины представлены позиционным двоичным кодом, то при вычислении приращений индекса вмес- 45 то операции деления на 2, как это требуеч ся в выражениях (3, 4), выполняется сдвиг вправо на 1 разряд, а при выделении целой части к результату операции сдвига добавляется 1, если младший разряд кода до сдвига был равен 1.

Работа АУ начинается с выдачи блоком управления 5 сигналов, по которым производится передача из регистра команд 6 приращения индекса ьЭ в индексный регистр 3, а базового адреса EA и адреса верхней границы массива А» в блок 4 определения окончания массива. После этого начинается цикл формирования исполнительного адреса ИА .

В 1-м такте цикла сдвигатель 10 осуществляет сдвиг содержимого индексного регистра 3 вправо на 1 разряд, формируя приращение индекса ь

Во 2-м такте Ь3 передается из сдвигаf теля 10 в регистр-счетчик 9.

В 3-м такте, если младший разряд индексного регистра 3 равен 1, блок управления 5 выдает сигнал в регистр-счетчик 9, по которому зчачение 6 3„увеличивается на

1.

B 4-м такте первого цикла (= 1) в сумматор 2 поступают ЬЛ„из регистрасчетчика 9 и базовый адрес БА из регистра команд 6, и согласно выражениям (1 — 4), производится сложение этих величин:

А = бА+а3

В четвертом такте всех последующих циклов (j = 2, 3 ... k ) в сумматор 2 из регистра исполнительного адреса 7 поступает исполнительный адрес ИА сфорj— - 4 3 мированный в предыдущем цикле, и приращение индекса дД„ из регистра-счетчика S

Сумматор 2 выполняет сложение или вычи= тание этих величин в зависимости от результата сравнения чисел х и и, в предыдущем

< цикле, а име. =-но:

A:ÃÈ А;, а а3; при х - у;

3- (ИА -Л3 при х:у;

Полученная величина А передается в блок 4 определения окончания массива и в регистр 1. Одновременно с этимд3 из регистра-счетчика 9 передается в индексный регистр 3 и в блок 8 определения нулевого приращения, который при д3 = 0 вырабатывает сигнал, поступающий в блок управления

5 и блокирующий выполнение последующих циклов формированця адресов.

В пятом такте цикла блоком 4 определения окончания массива производится проверка нахождения адреса А внутри граничных адi ресов массива. Если выполняется соотношение EA А А„, то блок 4. определения окончания массива вырабать;вает сигнал, сообщающий блоку управления 5 о выполнении этого соотношения, в результате чего блок управления 5 вырабатывает сигнал, разрешающий выдачу адреса А) из регистра адреса 1 в ЗУ в качестве исполнительного адреса ИА ° и запись этого адреса в регистр исполнительного адреса 7. Если же или A> EA, то по сигналу блока управления 5 адрес перейденной границы массива (А„р, или БА соответственно) засылается из регистра команд 6 в регистр адреса 1, из которого перецается в регистр

7 исполнительного адреса и через первый выход устройства — в ЗУ в качестве исполнительного адреса ИА„ . Затем блок управления 5 через второй выход устройства выда547764 ет сигнал "Конец цикла" в схему сравнения чисел, разрешающий выполнение сравнения числа х с числом у; считанным из ()

ЗУ по исполнительному адресу ИА . При этом всегда A i ИЛ (gj ), 5

После выполнения операции сравнения пары чисел из схемы сравнения чисел через входы устройства в блок управления 5 поступает один из сигналов; Х >y, х =у„ х <у;, причем сигнал х=y, приводит к окон- 1о чанию работы АУ, поскольку поиск в массиве закончен, так как получено,что к=y LA l.

Л

При других сигналах происходит переход к первому такту цикла формирования адреса.

Сравнение чисел заканчивается автомати- 15 чески циклом, при котором содержимое регистра-счетчика 9 равно нулю перед выполнением третьего такта. Равенство нулю содержимого регистра-счетчика 9 обнаруживается блоком 8 определения приращения, ко- 26 торый вырабатывает соответствующий сигнал, поступающий в блок управления 5 для организации завершения работы АУ, Если в последнем цикле схема сравнения чисел выдает сигнал X > У;, это означает выполнение соотношений:

У; (А,)(х<у;, fA,+1) при А; А„

Х У;(А„) при А„= А

Сигнал x< y, соответствует выйолнению соотношений:

У;,ГА;-1)<х<у, (ДД при А„ БА

Х<у,;(ДД при А = БА

Как видно, сравнение числа х с массивом из чисел выполняется не более чем за

РЮГЕР (Q0(n)+ 2 циклов, причем обращение к ЗУ (чтение команды) производится всего лишь один раз за весь период сравнения числа х с массивом Y . Таким образом, непроизводительные затраты рабочего времени

АУ на обращение к ЗУ за командами, необходимыми для организации изменения приращения индекса, сведены к минимуму (одно обращение), так же как и число ячеек ЗУ на запоминание программы поиска (одна

45 ячейка).

Следовательно, быстродействие индексного

АУ выше и, кроме того память ЦВМ используется экономнее.

Пример Пусть заданы число х =125 М и упорядоченный массив У, состоящий из 8 1 числа. Номер наибольшего числа массива 6 = 80 = /1010000/ . Среди чисел массива имеются у = 96, У = 97, <о 24 55

11З, У = 129, У = 155. Пос24кольку массив упорядочен по возрастанию чисел, все числа у; с номерами j < 20— меньше У а числа с номерами ) 24— больше У . Положение числа X относительно чисел массива Ч с помощью арифмети60 ческого устройства определяется за 8 циклов (см. фиг. 2 таблицу работы АУ для этого примера) .

Формула изобретения

Арифметическое устройство, содержащее регистр адреса, сумматор, индексный регистр, блок определения окончания массива, подключенные своими управляющими входами к первому, второму, третьему и четвертому выходам блока управления соответственно, регистр команд, первый выход которого подключен к первому входу блока управления, второй выход — к первому входу блока определения окончания массива. третий выход— к первому входу индексного регистра, а четвертый выход — к первому входу сумматора, выход которого соединен с первым входом регистра адреса, выход которого соединен с первым выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно дополнительно содержит регистр исполнительного адреса, блок определения нулевого приращения, регистр-счетчик и сдвигатель, выход которого соединен со входом регистра-счетчика, выход которого соединен со входом блока определения нулевого приращения и вторым входом сумматора, выход которого соедю ен со вторым входом блока определения окончания массива, выход которого соединен с четвертым входом блока управления, пятый, второй и третий входы которого соединены со внешними входами устройства, шестой вход блока управления соединен со вторым выходом индексного регистра и вторым входом сдвигателя, седьмой вход блока управления соединен с выходом блока определения нулевого приращения, пятый шестой и седьмой т выходы блока управления соединены с управляющими входами регистра исполнительного адреса, регистра-счетчика и сдвигателя соответственно, восьмой выход блока управления соединен со вторым выходом устройства, третий вход сумматора соединен с выходом ре гистра исполнительного адреса, вход которого соединен с выходом регистра адреса, второй вход которого соединен со вторым выходом регистра команд, четвертый выход которого соединен с третьим входом регистра адреса и третьим входом блока определения окончания массива, второй вход сумматора соединен со вторым входом индексного регистра.

Источники информации, принятые во внимание при экспертизе:

1. Авторское свидетельство СССР

% 217726, М. Кл. G06 F 9/00, 1969.

2. Справочник по вычислительной технике

Под ред. Малиновского Б. Н. Киев, Техника", 1974, с. 216, рис. 5.5.

547764

Содержимое индексного регисп рап7ора 1 счетчика

АХ;

П 0101 ППП

5A + о1июй

0107000

Х(у@О

О1а 100 а 001 0100

ИД,-ОО101ОО

Х >У20

ОП101ПО

0010 10

О 0001010

ПОП 1010 ияли+ аоп1о1о

Х(У о

ОПООП1

O ППООО1

ИА + ООООО1О поопо>о

Х(уяФ

ПППО01

П ШП00001

ПООООО1

ИЦ вЂ” OOOOO01 х(у, и арапа .„ е эЯФ ппоппоо оапапп1

ИЮ7 - ПППООП7

Х У-22 г» /

K0eevHbI езЦльтаж: (х (у

4иг.2

Составитель Н. Бондаренко

Редактор О. Стенина Гехред М. Ликович Корректор С, цо и

Заказ 877 /101 Тираж 818 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Cm. разрИы

101000

000107 ааа07О

Результат сдоига праоо на 1 разряд а аппп 1о7 1 ППООО10

Содержимою регислра—

0ППО7OZ

Ппооо11

Адрес операнда

ФА ил -аааа101 иА,„- аоооо11

22