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

ряда третьего коммутатора 1-го решающего блока соединен с входом k-ro разряда первого регистра (i+1)-го

решающего блока, инверсный выход знакового разряда i-ro решающего блока соединен с входом п-го разряда третьего регистра (i+l)ro решающего блока, в k-M решающем блоке инверсные выходы всех разрядов второго регистра, кроме (k+l)-ro, соединены с второй группой входов сумматора, отличающееся тем, что, с целью расширения функциональных возможностей за счет выполнения операции сортировки, в него введен блок управления, включающий генератор, тактовы} импульсов, элементы И, ИЛИ, триггер, счетчик, дешифраторы и п узлов анализа, каждый из которых содержит триггеры, элементы ИЛИ, И, в каждый решающий блок введены четвертый и пятый коммутаторы, причем в каждом решающем блоке инверсные выходы второго регистра соединены с соответствующими информационными входами первой группы четвертого коммутатора, информационные входы второй группы которого подключены к инверсным выходам пятого коммутатора п-го решающего блока, первый и второй управляющие входы i-ro разряда четвертого коммутатора подключены к выходу (i+l)-ro разряда четвертого коммутатора и к первому управляющему входу i-ro разряда пятого коммутатора, первый информационный вход k-ro разряда пятого коммутатора подключен к инверсному выходу k-ro разряда второго регистра, вторые управляющие и информационный входы k-ro разряда пятого коммутатора (i+l)-ro решающего блока объединены и соединены с прямым выходом fk-ro разряда пятого коммутатора -j-ro решающего блока, в первом решающем блоке вторые информационные и управляющие входы пятого коммутатора объединены и соединены с шиной нулевого потенциала устройства, подключенной также к пятому информационному входу k-разряда пятого коммутатора, выход k-ro разряда пятого коммутатора i-ro решающего блока подключен к пятому информационному входу k-ro разряда пятого коммутатора (i+l)-ro решающего блока, в блоке управления выход генератора тактовых импульсов соединен с

первыми входами первого и второго элементов И, второй вход элемента И соединен с выходом Сортировка первого дешифратора, входы которого подключены к входам кода операции устройства, вь1ход первого элемента И подключен к счетному входу счетчика, выходы разрядов которого соединены с соответствующими входами второго дешифратора, выход которого подключен к первым входам установки в нулевое состояние первого и третьего регистров всех решающих блоков информационному входу триггера, первому входу элемента ШШ и второму входу второго элемента И, выход которого подключен к входам разрешения записи регистров всех решающих блоков, вход общего сброса /устройства соединен с входом установки в нулевое состояние счетчика и вторым входом элемента ИЛИ, первыми входами первых элементов ИЛИ всех узлов, анализа и вторыми входами установки в нулевое состояние регистров всех решающих блоков, выход элемента ИЛИ блока управления подключен к входу . установки в нулевое состояние триггера, выход которого соединен с первыми входами первых элементов И узлов анализа, выходы которых соединены с объединенными управляющими входами п разрядов четвертых коммутаторов и к первому управляющему входу п-го разряда пятого коммутатора соответствующего решающего блока, в каждом узле анализа выход первого элемента ШШ соединен с входом установки в нулевое состояние первого триггера, выход которого соединен с первыми входами второго и третьего элементов ШШ и второго элемента И и единичным входом второго триггера, инверсный выход которого соединен с вторым входом первого элемента И, а прямой выход - с вторым входом первого элемента ИЛИ, выход второго элемента ИЛИ а-го узла анализа соединен, с третьим входом первого элемента ИЛИ и вторым входом второго элемента ИЛИ ( + 1)-го узла анализа, в первом узле анализа третий вход первого элемента ИЛИ и второй вход третьего элемента ИЖ объединены и подключены к шине нулевого потенциала устройства, выход третьего элемента ИЛИ Я-го узла анализа подключен к дополнительному

управляющему входу третьего ком 1утатора решающего блока, выход первого разряда четвертого коммутатора k-ro решающего блока соединен с входом установки в единичное состояние первого триггера узла анализа, выходы Деление и Умножение сортировка первого дешифратора блока управления соединены с управляющими входами соответственно первых и вторых элементов И узлов управления записью операндов, выход Деление, извлечение корня первого дешифратора блока управления соединен с первыми управляющи-г

ми входами третьих ко14мутаторов всех решающих блоков, вторые управляющие входы которых соединены с выходом Умножение первого дешифртора блока управления, выход Сортировка которого соединен с третьими управляющими входами третьих коммутаторов всех решающих блоков, первые и вторые управляющие входы первых коммутаторов всех решающих блоков подключены соответственно к выходам Извлечение корня -, и Деление, умножение первого дешифратора блока управления.

АРИФМЕТИКО-ЛОГИЧЕСКОЕ УСТ- : РОЙСТВО, содержащее п последовательно соединенных решающих блоков, где п- разрядность операндов, каждый из которых включает три регистра, сумматор, три коммутатора и п узлов управления записью операндов, которые включают элемент ИЛИ и два элемента И, выходы которых соединены с входами элемента ШШ причем первая группа информационных входов устройства соединена с входами первого регистра первого решающего блока, вторая группа информационных входов устройства подключена к первым входам элементов И узла управления записью операнда соответствующего разряда, выходы элементов ИЛИ узлов управления записью операндов соединены с соответствующими входами второго.регистра первого решающего блока, третья группа информационных входов устройства соединена с входами третьего регистра первого решающего блока, выходы разрядов первого регистра k-ro решающего блока, где ,2,...,n, соединены с первой группой входов сумматора, прямые выходы разрядов второго регистра i-ro решающего блока, где ,2,..., (п-1), соединены с входами второго регистра (i+l)-ro разрешающего блока,инверсный ипрямой выходы (i)-го разряда второго регистра k-ro решающего блока соединены с информационными входами первого коммутатора, выход первого коммутатора соединен с вторым входом (i+l)-ro разряда сумматора k-ro решающего блока, прямые выходы k-x разрядов третьего регистра i-ro решающего блока соединены с входами (k-l)-x разрядов треi тьего регистра (i+l)-ro решающего блока, выход второго коммутатора (Л i-ro решающего блока соединен с входом разряда второго регистра (i+l)-ro решающего блока, первый и второй информационные входы второго коммутатора k-ro решающего блока соединены соответственно с прямым выходом к-го разряда второго ре sj гистра и с инверсным выходом знаОд кового разряда сумматора k-ro решаСО N9 ющего блока, в каждом решающем бло-ке информационные входы с первого по четвертый k-ro разряда третьего коммутатора соединены соответственно с выходом (k-l)-ro разряда первого регистра, выходом (k+l)-ro разряда первого регистра, выходом (k-l)-ro разряда сумматора, выходом (k+l)-ro разряда сумматора, управляющие входы третьего коммутатора соединены соответственно с прямым и инверсным выходами знакового разряда сумматора и первого разряда третьего регистра, выход k-ro раз

1

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

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

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

Устройство (фиг. 1) содержит п решающих блоков 1, калодый из которых имеет регистры 2, 3 и 4, сумматор 5 и коммутаторы 6, 7,и 8, п логических узлов 9 управления запиг СЬЮ операндов, содержащих элементы И .10, 11 и элементИЛИ 12, входные шины 13, 14 и 15, управляющие шины 16-23. В каждом решающем. блоке 1 имеется также п коммутаторов 24, t коммутаторов 25, п входов 26,п входов 27, п выходов 28. Выходами устройства являются шины 29-32. Имеется таклсе блок 33 управления с выходами 34 и 35, и . входами 36 и 37. Коммутаторы б, 24 и 25 являются ti-разрядными, коммутаторы 7 и 8 - одноразрядными.

Блок 33 управления фиг. 2) содержит генератор 38 тактовых импульсов, элементы И 39, 40, элемент ИЛИ 41, триггер 42, счетчик 43, дешифраторы 44, 45 и п узлов 46 анализа, каждый из которых содержит триггеры 47 и 48,.элементы И 49, 50 и элементы ИЛИ 51, 52 и 53,

Арифметико-логическое устройство работает следующим образом.

Перед началом работы по шине 37 поступает сигнал Общий сброс от ЭВМ, сбрасывающий все триггеры блока 33 и регистры 2, 3 и 4 блоков 1 ..

Генератор 38 вырабатывает тактовые импульсы,-которые при выполнении всех операций, кроме сортировки, поступают через элементы И40 на выход 34 блока управления, т.е. на все регистры 2, 3 и 4 блоков 1. Сигнал О на выходе 23. дешифратора 45 не позволяет проходить синхроимпульсам через элемент И 39, работать счетчику 43 и дешифратору 44. Нулевой потенциал на выходе дешифратора 44 не разрешает проходить сигналу Сброс на выход 35 и не препятствует прохождению синхроимпульсов.через элемент И 40. Сигнал О на выходе дешифратора 44 также держит закрытыми элементы И 50 через триггер 42, кото- рый установлен в О по R-входу сиг-; налом с шины 37, хотя на вторых входах элементов И 50 установлены 1 по инверсным выходам триггеров 48. Сигнал О на выходе элемента И 39 держит закрытыми элементы И 49 всех . узлов 46 анализа и не позволяет про3

ходить 1, которые могут появиться на шине 28 и через элементы 47, 48 и 50 пройти на шину 27.

При выполнении сортировки тактовые импульсы поступают через элемент И 40 на выход 34 и одновременно через элемент И 39 при сигнале 1 на выходе 23 на вход счетчика 43 и дешифратора 44. По завершении отсчета счетчиком 43 П тактов на выходе дешифратора 44 появляется 1 которая закрывает элемент И 40 и прекращает дальнейшее поступление тактовых импульсов на выход 34 и регистры 2, 3 И 4 блоков 1, сбрасывае fi О по выходу 35 содержимое регисров 2 и регистров 4, исключая первы разряды регистров 4, установленные сигналом 23 в 1. Триггер 42 по Sйходу устанавливается в , открывает элементы И 50, и на шине 27 . появляются единичные сигналы. Единичный потенциал на выходе элемента И 39 также снимает запрет на прохождение сигналов через элементы И 49.

Если на выходе 28 какого-либо решающего блока 1 появляется сигнал 1, то он устанавливает в I по S-входу триггер 47 соответствующего узла 46. Через элемент ИЛИ 53 1 поступает на соответствующую шину 18 данного блока 1, и срдержимое сумматора 5 этого решающего блока считывается через коммутатор 6.

Задним фронтом этого же импульса поступающего через элемент И 49 на С-вход триггера 48 под управлением прямого выхода триггера 47, единица с выхода триггера 47 переписывается в триггер 48 и через элемент ИЛИ 51 по R-входу сбрасывает триггер 47. В дальнейшем триггер 47 не сможет установиться в 1, пока не будет сброшен триггер 48 при последующем поступлении сигнала Общий сброс по шине 37, образом, в следующих тактах по шине 27 на соответствуюш 1й решающий блок 1 подается О с инверсного выхода триггера 48 через элемент И 50. Сигнал О исключает из дальнейшего просмотра слово, записанное в регистре 3, т.е. слово, которое в предащудем такте считано как максимальное. При поиске максимума воз можно появление 1 на нескольких

63214

шинах 28 при наличии нескольких одинаковых слов, являющихся максимальньши. При этом считывается и исключается из дальнейшего просмотра первое (сверху ) из них. Для этого в блок 33 управления введена схема выборки первого ответчика, состоящая из элементов ИЛИ 52. Если на одном из триггеров 47 установлена 1, то она проходит через все элементы ИЛИ 52 и через элемент ИПИ 51 сбрасывает в О по R-входу триггеры 47 последующих (нижних) ячеек, т.е.. для тех решающих блоков,

5 кроме первого сверху, для которых значение, записанное в регистр 3, также выбрано как максимальное.

При умножении в первом такте первое множимое, поступающее по шине

0 14, проходит на регистр 3 через

элементы И 11, ИЛИ 12, а первый множитель - по шине 15 на регистр 4, причем первый разряд регистра 4 является младшим разрядом множителя.

5 Содержимое регистра 3 (инверсные выходы) блока 1.1 проходит на сумматор 5, где складывается с нулевыми значениями регистра 2. Инверсные

значения .2-го разряда регистра 3 блоI -

0 ка 1.1, 3-го разряда регистра 3 блока 1.2 и т.д. проходят через коммутатор 7 по сигналу с шины 21. Если первый разряд множителя регистра 4 равен 1, то коммутатор 6 пропускает ра регистр 2 блока 1.2 сдвинутые (k + I )-е разряды сумматора 5. Если первый разряд множителя равен .О, то коммутатор 6 пропускает те же разряды регистра 2 блока 1.1. Во

0 втором такте в блок 1.1 поступает вторая пара операндов и в сумматоре 5 получают сумму произведения второй пары чисел. В блоке 1.2 частичную сумму произведения первой пары чисел

5 регистра 2 складывают в сумматоре 5 с содержимым регистра 3, при этом инверсное значение 3-го разряда регистра 3 проходит через коммутатор 7. В зависимости от значения второго разряда первого множителя (регистр 4) в сумматоре 5 получают вторую частичную сумму произведения первой пары чисел (производится сложение или г сдвиг операндов).

5 При n-разрядных входных операндах результат вычислений первой пары чисел получают на выходе 29 сумматора 5 блока 1.П через n тактов, а всех

последующих пар чисел - через один такт.

При делении первое делимое запип сывают в регистр 2, а первый делитель - по шине 14 в регистр 3 через элементы И 10, ИЛИ 12 (прямые значения ). Деление выполняют с восстановлением остатка,

В первом такте в сумматоре 5 блок 1.1 вычитшот из первого делимого инверсные значения первого делителя. При этом инверсное значение 2-го разряда регистра 3 блока 1.1 проходит через коммутатор 7 при управлении сигналом с шины 21. Если остаток полозкителен, разряд частного равен 1 и коммутатор 6 пропускает сдвинутые (1t-l )-е разряды сумматора 5 под управлением инверсного выхода знакового разряда сумматора 5 и сигнала с шины 19. Если остаток отрицателен, выход частного равен О, коммутатор 6 пропускает (1с-1 )-е разряды регистра 2 под управлением прямого выхода знакового разряда сумматора 5 и сигнала с шины 19.

Во втором такте первый остаток от деления первой пары чисел переписывается в регистр 2 блока 1.2 из коммутатора 6, первый делитель переписывается в регистр 3, а первая цифра частного - в п-й (старший ) разряд регистра 4 блока 1.2 как значение инверсного выхода знакового разряда сумматора 5 блока 1.1. В сумматоре 5 блока 1.2 получают второй остаток от деления первой пары чисел и вторую цифру частного. Одновременно в регистры 2 и 3 блока I.I записьшают вторую пару операндов и получают первый остаток от деления второй пары операндов и первую цифру частного.

Результат вычислений первой пары чисел получают на выходах 31 и 32 (последний разряд ) регистра 4 блока 1.п через п тактов, а результат вычислений последующих пар чисел через каждьй такт.

При извлечении квадратного корня в первом такте первое подкоренное выражение поступает в регистр 2 по шине 13, а затем в сумматор 5, где происходит вычитание инверсных значений регистра 3 с пропуском 2-го разряда, поступающего через коммутатор 7 при управлении сигналом с шины 20, т.е. вычитание числа .... Если остаток сумматора 5 положителен (знак сумматора равен нулю ), информация с выходов (Ic-l )-х разрядов сзгмматора 5 поступает на коммутатор 6 под управление инверсного выхода знакового разряда сумматора 5 и сигнала с шины 19, т.е. со сдвигом вправо. При это первое число результата равно I и записывается через коммутатор 8 как., прямое значение 1-го разряда регистра 3 блока I.1 при управляюще сигнале с шины 20 в первый разряд регистра 3 блока 1.2 Если остаток сумматора 5 отрицателен, происходит восстановление остатка и сдви его вправо аналогично операции деления за счет пропускания через коммутатор 6 содержимого регистра 2 под управлением сигнала с шины 19. При этом число результата равно О

Во втором такте содержимое блока 1.1 переписывается в регистр 2 блока 1.2, а в регистр 2 блока I.Г запсывается второе подкоренное выражение . В блоке 1.1 вычисляют первый частный результат второго операнда, а в блоке I.2 вычисляют второй частный результат первого подкоренного выражения. Окончательный результат получают на выходе 30 блока 1. f в прямом коде.

При сортировке используется алгоритм упорядочения на основе базовой операции Поиск максимума. Перед началом работы сбрасьюаются все регистры сигналом с шины 37, а в первые разряды регистров 4 всех решаю1цих блоков I записывается I сигналом с шины 23. Информа- . цирнный массив поступает по шине 14 через элементы ИИ, ИЛИ 12 логических узлов 9 на входы регистра 3 блока 1.1.

В первые п тактов производится запись массива из п слов в регистры 3 всех решаю1цих блоков 1 путем их последовательной потактовой передачи через 1«-ые прямые выходы регистров 3. Тактовые импульсы поступают по шине 34. В (п+1 )-м такте прекращается подача тактовых импульсов и по шине 27 на все решаюпще блоки поступает сигнал I.

В горизонтальном направлении (справа налево )коммутаторы 24 образуют цепь, просматривакицую последовательно содержимое разрядов регистра 3 и продолжающую этот просмотр, если в данном разряде содержится Г либо если во всех одн именных разрядах регистров 2 всех решающих блокозв содержатся нули. Эта цепь реализует функцию 2Hv(), где Z. - сигнал на выходе . раз ряда коммутатора, 24; Z. - сигнал на выходе ()-го разр1яда коммутатора 24; а, - содержимое Jc-ro разряда регистра 3; у. - значение инверсного выход fc-ro разряда коммутатора в блоке 1. п (сигнал 26.1) Сигнал на шине 26.1 вырабатывае вертикальная цепь, состоящая из ,Jcразрядов коммутаторов 25 всех решающих блоков. Значение этого с.игнала может быть равным 1 только в том случае, если в fc-x разрядах 1 егистров 3 всех решающих блок09, подлежащих просмотру (.сигнал на ши не 27 равен 1), содержатся О. Эта цепь реализует функцию . 4,1c,, ; :, . где х - сигнал на выходе k-ro раз ряда коммутатора 25 решающего блока 1 ; X. . - сигнал на выходе -го раз ряда коммутатора 25 решаю щего блока l.(i-ll. Сигнал на пшне 26.k .п 8 1 сигнал на инверсном выходе 1«-го разряда коммутатора 25 блока 1.п. Наличие на выходе 28. i решающегоблока 1.1 сигнала 1 говорит о том, что слово, содержащееся в регистре 3 этого блока, является максимальным. Это слово суммируется на сумматоре 5 с нулевым значением регистра . 2 и считывается через коммутатор 6 этого же решающего блока под управлением сигнала с шины 18, а далее под управлением : сигнала с шины , 23 через коммутаторы 6 доследующих решающих блоков. В следующем (м+2 )-м такте по шине 27 на все решающие блоки поступает 1, кроме первого сверху, для которого на выходе 28 в предыдущем тактеустановился сигнал 1, т.е. значение регистра 3 которого было считано в предьщущем такте как максимальное. Это слово в дальней ших тактах не просматривается, поскольку По входу 27 на этот решаюпщй. блок подается О. Дальнейшее описание работы айаЛогично описанию для ( такта. Для сортировки массива из г слов требуется 2п тактов, из которых первые ,п тактов требуются для записи массива в регистры 3, Б каждом последующем таКте выбирается и считьшается максимальное из просматриваемых слов. Считанные в предыдущих тактах слова в. последующих тактах не просматриваются.

35

L

AL

4 i W4U4.4-i4

7iff Z7 lemmsKSJUi ---ax-- J7 ifTjmmisjas J5 I/J J7 I

/4

ngfer-t--ж

c5fo ±3//

a f j7