Арифметическое устройство Советский патент 1977 года по МПК G06F7/38 

где i - номф числа в массиве Y ( ОД,2,.,.,И );

А - адрес ячейки ЗУ, в которой хранится число у. , с применением ускоренного поиска по дихотомическому способу адреса чисел У вычисляются АУ в каждом цикле сравнения чисел X и У- согласно выражению , . A.-MAp6A Jj, (4)

где ИА - исполнительный адрес, формируе мый Б J, -м цикле

( j 1,2,...,м);

5А - базовый адрес массива чисел, Y , равный адресу числа у ;

3.) - индекс.

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

j.j..tAj.,(а)

где лЗ; - приращение индекса, причем

A3.j eMtiQr(.5J (З)

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

3 0; A3 cntiBh (и/г -0.5) (4-)

Знак приращения в каждом цикле, кроме

первого (в первом цикле знак всегда плюс зависит от результата сравнения чисел X и у в схеме сравнения чисел в предыдущем цикле.

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

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

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

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

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

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

На фиг. 1 изображена структурная схема арифметического устройства; на фиг. 2 - таблица циклов работы арифметического устройства.

Арифметическое устройство содержит регистр адреса 1, сумматор 2, индексный регистр 3; блок 4 определения окончания массива, подключенные своими управляющими входами к первому, второму, третьему и четвертому выходам блока управления 5 соответственно, регистр команд 6, первый выход которого подключен к первому входу блока управления 5, второй выход - к первому входу блока 4 определения окончания массива, третий выход - к первому входу индексно1х; регистра 3, а четвертый выход к первому входу сумматора 2. Выход сумматора 2 соединен с первым входом регист ра адреса 1, выход которого соединен с первым выходом устройства. Кроме того, арифметическое устройство содержит регист исполнительного адреса 7, блок 8 определения нулевого приращения, регистр-счетчик 9 и сдвигатель 10, выход которого соединен со входом регистра-счетчика 9. Выход последнего соединен со входом блока 8 определения нулевого приращения и вторым входом сумматора 2, выход которого соединен со вторым входом блока 4 определения окончания массива. Выход блока 4 определения окончания массива соединен с четвертым входом блока управления 5, пятый, второй и третий входы которого соединены со внецшими входами устройства. Шее ТОЙ вход блока управления 5 соединен со вторым выходом индексного регистра 3 и вторым входом сдвигателя 10, Седьмой вход блока управления 5 соединен с выходом блока 8 определения нулевого прирашения. Пятый, шестой и седьмой выходы блока управления 5 соединены с управляющими входами регистра 7 исполнительного адреса регистра-счетчика 9 и сдвигателя 10 соответственно, а восьмой его выход соединен со вторым выходом устройства. Третий вход сумматора 2 соединен с выходом регистра 7 исполнительного адреса, вход которого соединен со вторым выходом регистра команд 6. Четвертый выход регистра команд 6 соединен с третьим входом регистра адреса 1 и третьим входом блока 4 определения окончания массива . Второй вход сумматора 2 соединен со вторым входом индекс ного регистра 3. До начала работы АУ в регистр команд 6 из ЗУ поступает команда, содержащая код операции Оп, признак индексации ПрИ, адрес верхней границы массива А , базовый адрес массива БА и пpиpaщeIiиe индекса vUo (величины представлены позиционным двоичным кодом). Затем А У работает без обращений к ЗУ, причем, поскольку величины представлены позиционным двоичным кодом. ТО при вычислении приращений индекса вместо операции деления на 2, как это требуется в выражениях (З, 4), выполняется сдвиг вправо на 1 разряд, а при выделении целой части к результату операции сдвига добавляется 1, если младший разряд кода до сдвига был равен 1. Работа А У начинается с выдачи блоком управления 5 сигналов, по которым производится передача из регистра команд 6 1ф№ращения индекса дЗд в индексный регистр 3, а базового адреса БА и адреса верхней границы массива А рр в блок 4 определения окончания массива. После этого начинается цикл формирования исполнительного адреса ИА j. В 1-м такте цикла сдвигатель 10 осуществляет сдвиг содержимого индексного регистра 3 вправо на 1 разряд, формируя приращение индекса u3j Во 2-м такте дО; передается из сдвигателя 10 в регистр-счетчик 9. В 3-м такте, если младший разряд индексного регистра 3 равен 1, блок управления 5 выдает сигнал в регистр-счетчик 9, по которому значение дЭ: увеличивается на 1. В 4-м такте первого цикла ( j 1) в сумматор 2 поступают ДЛ из регистрасчетчика 9 и базовый адрес БА из регистра команд 6, и согласна выражениям (1 - 4), производится сложение этих величин: AJ 6А +ДЗ: В четвертом такте всех иослед ющих циклов ( j 2, 3 ... k ) в сумматор 2 из регистра исполнительного адреса 7 поступает исполнительный адрес ИА мированный в предыдущем цикле, и приращение индекса дЭ; из регистра-счетчика 9. Сумматор 2 выполняет сложение или вычитание этих величин в зависимости от результата сравнения чисел х и у. в предыдущем цикле, а Ар( LMAj,-Ajj при Полученная величина А; передается в блок 4 определения окончания массива и в регистр 1. Одновременно с STHMA J из регистра-счетчика 9 передается в индексный регистр 3 и в блок 8 определения нулевого приращения, который при дЗ; О вырабатывает сигнал, поступающий в блок управления 5 и блокирующий выпоянекие послед тощих циклов формирования адресов. В пятом такте цикла блоком 4 определения окончания массива производится проверка нахождения адреса А; внутри граничных адресов массива. Если выполняется соотношение БА 1 гв в о блок 4 определения окончания массива вырабатывает сигнаЛ; сообщающий блоку управления 5 о вьгаолне- НИИ этого соотношения, в результате чего блок управления 5 вырабатывает сигнал, разрещающий выдачу адреса AJ из регистра адреса 1 в ЗУ в качестве исполнительного адреса ИА; и запись этого адреса в регистр исполнительного адреса 7. Если же А; Appg или AJ БА, то по сигналу блока управления 5 адрес перейденной границы массива ( или БА соответственно) засылается из регистра команд 6 в регистр адреса 1, из которого передается в регистр 7 исполнительного адреса и через первый выход устройства - в ЗУ в качестве исполнительного адреса ИА.;. Затем блок управления 5 через второй выход устройства выдает сигнал Конец цикла в схему сравнения чисел, разрешающий выполнение сравнения числа X с числом v считанным из ЗУ по исполнительному адресу ИА;. При этом всегда А liAif Sj). После выполнения операции сравнения пагры чисел из схемы сравнения чисел через входы устройства в блок управления 5 поступает один из сигналов; , , причем сигнал приводит к окончанию работы АУ, поскольку поиск в массиве закончен, так как получено,что л У;.А. При других сигналах происходит переход- к первому такту цикла формирования адреса. Сравнение чисел заканчивается автоматически циклом, при котором содержимое регистра-счетчика 9 равно нулю перед выполнением третьего такта. Равенство нулю содержимого регистра-счетчика 9 обнаруживается блоком 8 определения приращения, который вырабатывает соответствующий сигна поступающий в блок управления 5 для организации завершения работы АУ. Если в послед11ем цикле схема сравнения чисел выдает сигнал X У , это означает выполнение соотношений; .ДVllпpи А. . при А. Сигнал соответствует выполнени соотношений; ,ч Аг1 х у АПпри Ар БА при А БА Как видно, сравнение числа х с массив из h чисел выполняется не более чем за eniieh()+ 2 циклов, причем обращение к ЗУ (чтение команды) производится всего лишь один раз за весь период сравнения чис ла X с массивом Y . Таким образом, непроизводительные затраты рабочего времени А У на обращение к ЗУ за командами, необходимыми для организации изменения прира- шения индекса, сведены к минимуму (одно обращение), так же как и число ячеек ЗУ на запоминание программы поиска (одна ячейка). Следовательно, быстродействие индексно А У выше и, кроме того память ЦВМ исполь зуется экономнее.. Пример. Пусть заданы число 5«- 12 и упорядоченный массив Y , состоящий из 81 числа. Номер наибольшего числа массива П 80 /ЮЮООО/з.. Среди го 96. У 97, чисел массива имеются у, УЗЭ 113, УЗ, 129, 2 155. Поскольку массив упорядочен по возрастанию чисел, все числа у с номерами i 20 меньше j числа с номерами 4 24 больше V, Положение числа X относите но чисел массива V с помошыо арифметического устройства определяется за 8 циклов (см. фиг, 2 таблицу работы А У для этого примера). Формула изобретения Арифметическое устройство, содержащее регистр адреса, сумматор, индексный регистр, блок определения окончания массива, подключенные своими управляющими входами к первому, второму, третьему и четвертому выходам блока управления соответственно, регистр команд, первый выход которого подключен к первому входу блока управления, второй выход - к первому входу блока определения окончания массива, третий выход к первому входу индексного регистра, а четвертый выход - к первому входу сумматора, выход которого соединен с первым входом регистра адреса, выход которого соединен с первым выходом устройства, отличающееся тем, что, с целью повышения быстродействия, оно дополнительно содержит регистр исполнительного адреса, блок определения нулевого приращения, регистр-счетчик и сдвигатель, выход которого соединен со входом регистра-счетчика, выход которого соединен со входом блока определения нулевого приращения и вторым входом сумматора, выход которого соединен со вторым входом блока определения окончания массива, выход которого соединен с четвертым входом блока управления, пятый, второй и третий входы которого соединены со внешними входами устройства, шестой вход блока управления соединен со вторым выходом индексного регистра и вторым входом сдвигателя, седьмой вход блока управления соединен с выходом блока определения нулевого приращения, пятый шестой и седьмой выходы блока управления соединены с управляющими входами регистра исполнительного адреса, регистра-счетчика и сдвигателя соответственно, восьмой выход блока управления соединен со вторым выходом устройства, третий вход сумматора соединен с выходом регистра исполнительного адреса, вход которого соединен с выходом регистра адреса, второй вход которого соединен со вторым выходом регистра команд, четвертый выход которого соединен с третьим входом регистра адреса и третьим входом блока определения окончания массива, второй вход сумматора соединен со вторым входом индексного регистра. Источники информации, принятые во внимание при экспертизе: 1. Авторское свидетельство СССР № 217726, М. Кл.&06 F 9/00, 1969. 2. Справочник по вычислительной технике Под ред. Малиновского Б. Н. Киев, 1974, с, 216, рис. 5.5.

Фиг Z