Многофункциональное вычислительное устройство Советский патент 1987 года по МПК G06F7/38 

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг.2 - функциональная схема ячейки матрицы; йа фи1 . 3 - схема дополнительной ячейки; на фиг. 4 - схема управляющей ячейки; на фиг. 5 - схема блока выбора максимального числа; на фиг. 6 схема блока формирования сигнала считывания; на фиг. 7 - схема блока синхронизации; на фиг. 8 - алгоритм сортировки.

Устройство содержит ячейки 1 матрицы, дополнительные ячейки 2, управляющие ячейки 3, блок 4 выбора максимального числа, блоки 5 формирования сигнала считывания, элемент ИЛИ 6, триггеры 7, образующие первую и вторую косоугольные матрицы 7.1 и 7.2 триггеров и косоугольную матрицу 7.3 пар триггеров, первую входную шину 8 операнда, вторую входную шину 9 операнда, выходную шину 10 остатка, выходную шину 11 сортировки,.первую t2 и вторую 13 выходные шины результата и выходную шину 14 сигнала считывания устройства, а также блок 15 синхронизации, третью входную шину 16 операнда, входную шину 17 управления умно 18 значения 1.

жением, шину

шину

19 значения О, входную шину 20 кода операции и входную шину 21 общего сброса устройства.

Ячейку 1 образуют триггеры 22 и 23, элементы И 24-26, элемент. ИЛИ

Код О,,,О Множимое Множитель

Константа Со

Делимое

То же То же Делитель

27, элемент ИСКЛЮЧАЮЩЕК ИЛИ 28 и сумматор 29.

Дополнительная ячейка 2 состоит из триггеров 30 и 31, элемента И 32,

элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 33 и сумматора 34.

Управляющая ячейка 3 выполнена на элементах И 35-39 и элементах ИЛИ 40-43„

Блок 4 выбора максимального числа состоит из триггера 44, элемента ИЛИ 45 и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 46.

Блок 5 формирования сигнала считывания содерлсит триггеры 47 и 48, элементы ИЖ 49-51, элемент И 52 и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 53.

Блок 15 синхронизации образуют генератор 54 тактовых импульсов, элементы И 55 и 56, дешифратор 57, дешифратор 58 нуля и двоичный счетчик 59.

В табл. 1 показано состояние управляющих сигналов в зависимости от выполняемой операции, в табл. 2 - состояние информационных входов и выходов устройства в зависимости от выполняемой операции. IТ а б л и ц а 1

Умножение 40 С Со+А В Деление

Извлечение

45

Таблица 2

Произведение старший младший разряд разряд

То же

Частное

Остаток Опервция

Входы

8j 9 I 16

Подкорен- Код 0,.,0 ное выражение

Код числа

Операции умножения и с Со+А К, выполняются аналогично, однако при умножении на входы 8 подают код 0...0, а при второй операции - код константы Со. При,умножении на вто- ром информационном входе ячейки 3 и на третьих управляющих входах 17 ячеек 2 установлен единичный сигнал, а на втором пятом и шестом выходах управляющей ячейки - нулевой. Это позволяет настроить на логическое повторение элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 28 ячеек 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 33 и элемент И 32 ячейки 2 первой строки. На второй информацион- ный вход ячейки 2 и вход 8 устройства подают нулевой код,

В первом такте первое N-раэрядно множимое поступает по шине 9 в триггеры 22 ячеек 1 первой строки. N-й разряд nepBoi o множимого поступает по шине 16 в ячейку 3 и через элемент ИЛИ 41 на первый выхбд и первый управляющий вход первой ячейки 1 первой строки. Значение N-ro разряда множителя устанавливается на первых входах элементов И 25 всех ячеек 1, на вторые входы которых поступают разряды множимого с триггра 22. Остальные разряды множителя по входу 16 записываются в триггеры 7 первого столбца первой косоуго ь- ной матрицы 7.1 триггеров.Частичная сумма образуется на третьих выходах

ячеек 1.

Во втором такте частичная сумма с третьих выходов ячеек 1 первой строки переписывается в триггеры 23 по вторым информационным входам ячеек 1 второй строки и в триггер 31 по второму информационному входу в ячейку 2 старшего разряда. Первое множимое переписывается с триггеров 22 ячеек 1 первой строки в эти же триггеры второй строки по третьим информационным входам (старший разряд через ячейку 3). (N-1)-й разряд множителя с триггера 7 первого ст.олбца первой косоугольной, матрицы

12937274

Продолжение табл.2 Выходы

12 I 13

10 I II

Корень

То же

Код числа

0

c 5

5

0 5

0

1,1 поступает через ячейку 3 второй строки на элементы И 25 ячеек 1 второй строки. Остальные разряды множителя -переписьшаются в триггеры 7 второго столбца первой косоугольной матрицы 7.1.В этом такте во второй строке образуется частичная сумма произведения первого множимого на V (N-1)-й разряд множителя, которая складьгаается с полученной ранее частичной суммой произведения первого множимого на N-й разряд множителя. Одновременно в первой строке формируется значение старшего разряда произведения в ячейке 2: сигнал переноса со второго выхода ячейки 2 второй строки поступает на первый управляющий вход ячейки 2 первой строки и через элементы 32 и 33 на вход сумматора 34.

В третьем такте на втором входе ячейки 3 третьей строки может быть нулевой или единичный сигнал, зависящий от сигнала переноса на втором выходе ячейки 2 второй строки. Однако изменение этого сигнала не влияет на выходные сигналы ячейки 3. В этом такте содержимое триггеров ячеек второй строки переписывается в триггеры ячеек третьей строки, (N-2)-разряд первого множителя переписывается с триггера 7 второго .. столбца первой косоугольной матрицы 7,1 в ячейку 3 и поступает на входы ячеек 1 третьей строки, значение старшего разряда произведения с третье- го выхода ячейки 2 первой строки переписьшается во второй триггер 7 первой пары второго столбца второй строки третьей косоугольной матрицы ,в триггеры ячеек первой строки поступает вторая пара операндов, остальные разряды первого множителя переписываются в триггеры 7 третьего столбца первой косоугольной матрицы 7,1. В этом такте получают в первой строке частичную сумму ripo изведения второго множимого на N-й разряд второго множителя, который

поступает на третий вход ячейки 3 и в ячейки 1 первой строки. Одновременно в третьей строке получают час тичную сумму произведения первого множимного на (К-2)-й разряд первого множителя, которую складывают с полученным ранее результатом. Во второй строке получают вторую цифру старшего разряда произведения.

По истечении 2п+1 тактов работы результат произведения первой пары чисел получают на выходах 13 (старшие разряды) и на выходах 10 (младшие разряды) устройства. Результат произведения следующих пар чисел получают через каждые 3 такта. Старший разряд при операции + А-В формируется на первом выходе 12 устройства.

Операция деления,

В ячейках 3 на входах втором и управления делением установлены единичные сигналы, а на третьих -управляющих входах ячеек 2 - н левые сигналы (табл. 1), Это позволяет настроить на логическое повторение элементы И 25 ячеек 1, оборвать цепь распространения переносов между ячейками 2 и использовать ячейки 2 как ячейки 1.

В первом такте по второму информационному входу ячейки 2, вторым информационным входам ячеек 1 и установочному входу триггеров 7 второй косоугольной матрицы 7.2 и подают 2N разрядов делимого, которые записывают в соответствующие триггеры 31 ячейки 2, триггеры 23 ячеек 1 и соответствующие триггеры 7 второй косоугольной матрицы 7,2. По шине 9 поступают N разрядов делителя, которые записывают в триггеры 22 ячеек первой строки. Использование ячейки 2 в качестве ячейки 1 позволяет сдвинуть делимое на один разря влево относительно делителя. Операция деления производится по алгоритму без восстановления остатка, Вычи таншо из очередного остатка делителя соответствует суммирование дополнительного кода делителя.

Первая цифра первого частного ( формируется на втором выходе ячейки 2 первой строки, единичный (нулевой) сигнал которого свидетельствуе о положительном (отрицательном) текущем остатке. Первый остаток перво

го делимого формируется на третьих выходах ячеек 1 первой строки.

Во втором такте на второй вход второй ячейки 3 может поступить единичный (нулевой) сигнал с второго выхода ячейки 2 первой строки, втором, пятом и шестом на выходах сформируются единичные (нулевые) сигналы, в связи с чем в сумматорах 29

ячеек 1 второй строки может быть осуществлено вычитание (суммирование) из кода текущего остатка. Первую цифру частного с второго выхода ячейки 2 первой строки записывают в первьй триггер 7 первой пары первого столбца третьей косоугольной матрицы 7.3, Первый делитель из триггера 22 ячеек 1 первой строки по четвертому выходу переписывают в аналогичные триггеры ячеек 1 второй строки по третьим информационным входам (в первую ячейку 1 через ячейку 3 второй строки)„ Первый остаток от деления первой пары чисел с третьих выходов ячеек 1 первой строки записывают в триггеры 31 ячейки 2, в триггеры 23 ячеек 1, остальные разряды делимого с триггером 7 первой строки второй косоугольной матрицы 7.2 переписывают в триггеры 7 второй строки той же матрицы и в триггер 23 N-й ячейки 1 второй строки. В ячейках 1 и ячейке 2 второй строки образуется вторая цифра первого частного и второй остаток от деления первой пары чисел. Одновременно по шинам 8 и 9 на первую строку поступает вторая пара операндов и в ячейках первой строки формируются первая цифра второго частного и первьй остаток от деления второй пары чисел,

Результат частного первой пары операндов получают через п тактов на выходах 12, а остаток - на выходах 10. Результат вычислений последующих пар чисел получают на этих выходах через каждый такт, Операция извлечения корня.

Элементы И 25 ячеек 1 установлены на логическое повторение. На входе 17 устройства установлен нулевой сигнал, в связи с чем ячейки 2 участвуют в вычислительном процессе как ячейки 1.

В первом такте по второму информационному входу в ячейку 2 старшего разряда подают нулевой сигнал.

а по шине 8 - (2N-1)-разрядный код мантиссы подкоренного вьфажения, который записывается в триггер 31 ячейки 2, триггеры 23 ячеек 1 и триггеры 7 первой строки второй косоугольной матрицы 7.2. В триггеры 22 ячеек 1 первой строки записывается нулевой код. В вычислительном процессе участвуют лишь ячейка 2 и две ячейки 1 старших разрядов первой строки матрицы, в которых записан код ОС, С . Этот дсод суммируется с кодом 111, который устанавливается на вьжодах элементов 28 и 33 этих ячеек. В результате оп ределяется первая цифра корня,которая формируется на третьих выходах соответствующих ячеек 1.

Во втором такте первая цифра корня Z с второго выхода ячейки 2 первой строки записьгаается в первый триггер 7 первой пары третьего столбца косоугольной матрицы 7.3, . а с третьих выходов соответствующих ячеек 1 матрицы и триггеров 7 первой строки второй косоугольной матрицы 7.2 переписываются цифры первого подкоренного вьфажения в триггеры ячеек второй строки. В вычис- лительном процессе принимают участие ячейка 2 и три первые ячейки 1 второй строки. Остальные ячейки 1 единичным сигналом с второго выхода ячейки 3 настроены на повторе- ние. исходной информации.К сдвинутому остатку справа присоединяются дв следующие цифры подкоренного выражения. Сформированный таким образом код суммируется с другим кодом, также образованньм из двух частей. Первая часть равна поразрядной опера- ции ИСКЛЮЧАЮЩЕЕ ИЛИ цифры Z1 с кодом OZ1и формируется в ячейках 2 и 1 второй строки устройства.Вторая часть равна .коду 11 и формируется во второй и третьей ячейках 1 этой же строки. В результате определяется вторая цифра корня, которая формируется на втором выходе ячейки 2 второй стро- ки, и второй остаток на третьих выходах ячеек 1. Одновременно на первую строку поступает второе подкоренное вьфажение. В дальнейшем извлечение корня осуществляется по ал- горитму без восстановления остатка. В i-M такте к очередному, сдвинутому на 1 разряд влево, остатку справа присоединяются две следующие

цифры подкоренного вьфажения С , С,; и получают код, который суммируется с кодом Zj @ (OZ .. .Zj ) . 11. Действие Zj © О осуществляется на элементах ИСКЛЮЧАЮЩЕЕ ИЛИ 33 ячейки 2, а действие Zj ® (OZ,...Zi) - на элементах 28 ячеек 1. Одновременно на первую строку устройства поступает i-e подкоренное вьфажение,

В N-M такте работы предпоследний остаток объединяется с последней цифрой и суммируется с кодом Z,,.,@ (OZ ...Z.).1,a на первую строку поступает N-e подкоренное вьфажение.

Результат извлечения корня формируется в N-M такте на выходах 12 (результат извлечения корня.) и выходах 10 (остаток). Результат извлечения следующего подкоренного вьфажения получают через один такт.

Операция сортировки.

Перед началом работы от ЭВМ в блок 15 синхронизации поступает сигнал Общий сброс по входной шине 20 устройства. На выходе дешифратора 58 появляется сигнал, которым сбрасываются все триггеры устройства. Тактовые импульсы генератора 54 проходят через элемент И 56 на С- входы и Р-БХоды всех триггеров устройства (нулевой сигнал на выходе дешифратора 58 не мешает их прохождению) . Одновременно тактовые импульсы генератора 54 через элемент И 55 (при сортировке на втором входе элемента И 55 единичный сигнал) поступают на счетчик 59. Когда счетчик отсчитывает N тактов, на выходе дешифратора 58 появляется единичный сигнал, который закрывает элемент И 56 и прекращает дальнейшее поступление тактовых импульсов в устройство. В (N+1)-M такте на выходе управления сортировкой появляется единичный сигнал.

На втором входе ячейки 3 первой строки установлен единичный сигнал. На четвертых входах ячеек 3 всех строк установлены единичные сигналы с первых выходов блоков 5 (с инверсных выходов сброшенных триггеров 48). Так как управляющий вход блока 5 последней строки подключен к нулевой шине, а триггеры сброшены, нулевой сигнал по третьим выходам подается на управляющий вход всех блоков 5, а по вторым выходам - на чету

вертые управляющие входы всех ячеек 1, не разрев1ая считывания содержимого триггеров 22 через элемент И 26 на восьмые выходы ячеек 1 и выход 11 устройства.

Сортировка производится посредством зы бора, в данном случае, максимального числа, отделения его от остальных чисел и дальнейшего выбора наибольшего числа из оставшихся п;о отношению к выбранному максимальному числу. Этот алгоритм, схема которого представлена на фиг, 8, реа

лизован ассоциативным путем.

В первом такте . N-разрядньш код первого сортируемого числа поступает по шине 9 и записывается в триггеры 22 ячеек 1 первой строки.

Во втором такте содержимое триггеров .22 с четвертых выходов ячеек 1 первой строки записывается по соответствующим третьим входам в одноименные триггеры этих же ячеек второй строки, а в триггеры первой строки записывается код второго сортируемого числа.

По истечении N тактов во всех строках устройства будут записаны коды N сортируемых чисел.

Одновременно сортируемые числа проходят через блоки 4 для формирования максимального числа из данных п чисел. В схемах 4 анализируются состояния одноименных разрядов сортируемых чисел. Если в i-м разряде всех кодов содержатся все нули, то в нем устанавливается единичный сигнал, а если хоть одна единица - нулевой сигнал. Перед началом работы триггеры 44 блоков 4 сброшены и на одном из входов элементов ИЛИ 45 установлены О. На вторые входы этих элементов 45 поступают коды сортируемых чисел. В единичные состояния устанавливаются те триггеры 44, на второй вход которых поступает единичный сигнал. В дальнейшем состояние этих триггеров не изменяется. Сформированный код максимального числа за п тактов по выходам блоков 4 поступает на соответствующие входы элементов ИЛИ 27 всех ячеек 1.

В (п+1)-м такте на вход управления сортировкой ячеек 3 всех строк поступает единичный сигнал, который проходит через элемент И 38 на третий управляющий выход ячеек 1 и разрешает просмотр записанного массива

:0

5

0

5

В вертикальном направлении просмотр ведется снизу вверх, т.е. от N-й строки до первой, В горизонталь ном направленш-1 слева направо элементы ИЛИ 27 и элементы И 24 ячеек 1 образуют цепь последовательного просмотра содержимого триггеров 22 этих ячеек. Цель просмотра не прерывается в том случае, если в соответствующих ячейках на третьих информационных входах имеются 1 или если во всех одноименных разрядах всех строк содержатся О. Наличие единичного сигнала на информационном входе схемы 5 свидетельствует о том, что в i-й строке находится максимальное число. Этот единичный сигнал поступает в триггер 47 блока 5 и через элемент И 52 на второй выход, разрешая считывание максимального числа с триггеров 22 ячеек 1 через элемент И 26 по соответствующим восьмым выходам данной строки.

Единичный сигнал на третьем выходе блока 5, где найдено максимальное число, поступает на управляющий вход блока 5 расположенной вьш1е строки. Он запрещает считывание с этой строкиS если на информационном входе также установлена 1, Поэтому сначала считывается максимальное число с низкней i-й строки, а затем с (1-1)-й, (1-2)-й и т.д., если в данном массиве имеется несколько максимальных чисел.

Единичный сигнал с вькода триггера 47 поступает через элемент . ИЛИ 6 на выход 14 и управляет считыванием максимального .числа. В случае наличия нескольких максимальных чисел единичный сигнал на выходе 14 присутствует до тех пор, пока последнее максимальное число не будет считано. Нулевой сигнал на выходе 14 разрешает просмотр следующих чисел,.

Если в триггере 47 i-й строки записана 1 (1 на втором выходе ,

0 и на четвертых управляющих входах ячеек 1) то с этой строки производится считывание максимального числа на выход 11 устройства через элемент И 26 по восьмым выходам ячеек 1

5 строки. Одновременно с триггера 47 единичньй сигнал поступает на элемент ИЛИ 50 и через элемент 53 ИСКЛЮЧАЮЩЕЕ ИЛИ записывается по S- входу в триггер 48. На первом выхо0

5

0

1

де появляется нулевой сигнал, который, поступая на четвертьй вход ячейки 3 этой строки, устанавлива4дкгу| О на четвертом выходе ячейки 3 и исключает данную строку из дальней- шего просмотра. Далее О с четвертого выхода ячейки 3 проходит всю строку, поступает на информационный вход блока 5 этой строки и через элемент ИЛИ 49 по R-входу записывается в триггер 47. Появившийся О на третьем выходе разрешает считывание максимального слова с расположенных выше строк, а О на четвертом выходе свидетельствует об окончании считьшания с данной строки.

Следующий просмотр сортируемых чисел начинается после считывания 20 всех максимальных чисел в данном массиве и появлении нулевого сигнала на выходе 14 элемента ИЛИ 6.

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

55

1 . Многофункциональное вычислительное устройство, содержащее матрицу ячеек, столбец из N управляющих ячеек и столбец из N дополнительных ячеек (N - разрядность операндов) , причем первый управляющий и первый информационный входы п-й ячейки р-й строки матрицы (,2,.. ...,N-1; ,2,,..,N) подключены соответственно к первому и второму выходам (п+1)-й ячейки р-й строки матрицы, первый управляющий и первый информационный входы р-й ячейки N-ro столбца матрицы подключены соответственно к первому и второму выходам р-й управляющей ячейки столб- ца второй выход р-й ячейки первого столбца матрицы подключен к первому информационному входу р-й дополнительной ячейки столбца, второй информационный вход ячейки та-й (т

2,3N) строки и п-го столбца

матрицы подключен к третьему выходу ячейки (та-1)-й строки (п+1)-го столбца матрицы, второй информационный вход р-й ячейки первой строки матрицы является р-м разрядом первой входной шины операнда устройства, третий выход п-й ячейки первого столбца матрицы подключен ко второму информационному входу (п+О-й дополнительной ячейки столбца, третий выход р-й ячейки N-й строки

5о372712

является р-м разрядом выходной шины остатка устройства, третий ир1форма- ционный вход z-й (,2,...,т-2) ячейки т-й строки матрицы подключен к четвертому выходу z-й ячейки (т-1)-й строки, третий информационный вход -и ячейки та-й строки ( m,...,N) подключен к четвертому выходу -и ячейки (п1-1)-й строки, третий информационный вход

30

20

25

,

(т-1)-й ячейки т-й строки матрицы подключен к третьему выходу т-й управляющей ячейки столбца, четвертый выход п- й ячейки п-й строки матрицы подключен к первому входу (п+1)- -й управляющей ячейки столбца, третий информационный вход р-й ячейки первой строки матрицы является р-м разрядом второй входной шины операнда устройства, второй управляющий вход т-й ячейки р-й строки матрицы подключен к пятому выходу (т-1)-й ячейки той же строки матрицы, второй управляющий вход первой ячейки р-й строки подключен к четвертому выходу р-й управляющей ячейки столбца, третий управляющий вход р-й ячейки р-й строки матрицы подключен к пятому выходу р-й управляющей ячейки столбца, третий управляющий вход первой ячейки ш-й строки матрицы подключен к первому выходу т-й дополнительной ячейки столбца, третий управляющий вход i-й ячейки строки матрицы (,...,N; i 2,...,j-1) подключен к шестому выходу (1-1)-й ячейки той же строки матрицы, третий управляющий вход j-й ячейки (-2)-й строки матрицы подключен к второму выходу (-2)-й управляющей ячейки столбца, третий управляющий вход t-й ячейки (л-2)-й строки матрицы (,...,N) подключен к пятому выходу (с-1)-й ячейки той же строки матрицы, второй информационный вход первой дополнительной ячейки столбца является 2N-M разрядом пер вой входной шины операнда устройства, причем ячейка матрицы содержит сумматор, эле- . .:мент ИСКЛЮЧАЮЩЕЕ или и элемент И, причем первый вход элемента ИСКЛЮЧА- РЦЕЕ ИЛИ ячейки является вторым 55 управляющим входом и пятым выходом ячейки матрицы, второй вход элемента ИСКЛЮЧАНЯЦЕЕ ИЛИ ячейки подключен . к выходу элемента И ячейки матрицы, выход элемента ИСКЛЮЧАЩЕЕ ИЛИ ячей35

40

45

50

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

0

5

. 5 0 5 0 5 0 5

ключен к первому входу четвертые элемента И управляющей ячейки, второй вход четвертого элемента И управляющей ячейки подключен к вторым входам первого, второго и третьего элементов И управляющей ячейки и является вторым входом управляющей ячейки, выходы второго и третьего элементов И управляющей ячейки подключены соответственно к второму

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

15

матриць, вход первого триггера п-й строки первой косоугольной матрицы триггеров является (п+1)-м разрядом третьей входной шины операнда устройства, выход п-го триггера п-й строки первой косоугольной матрицы триггеров подключен к третьему входу (п+1)-й управляющей ячейки столбца, выход х-го триггера, где х , (j-1)-й строки первой косоугольной матрицы триггеров подключен ко входу (х+1)-го триггера той же строки первой косоугольной матрицы триггеров, входы первого и второго триггеров п-й пары п-й строки косоугольной матрицы пар триггеров подключены соответственно ко второму и третьему выходам п-й дополнительной ячейки столбца, выход первого триггера п-й пары (Н-1)-й строки косоугольной матрицы пар триггеров является п-м разрядом первой выходной шины результата устройства, выход второго триггера п-й пары (Н-1)-й строки косоугольной матрицы пар триггеров является п-м разрядом второй выходной шины результата устройства, второй выход N-й дополнительной ячейки столбца является N-M разрядом первой выходной шины результата устройства, третий выход N-й дополнительной ячейки столбца является N-разрядом второй выходной шины результата устройства, выходы первого, второго триггеров х-й пары (-2)-и строки косоугольной матрицы пар триггеров подключены к входам соответственно первого и второго триггеров х-й пары (-1)-й строки косоугольной матрицы пар триггеров, вход первого триггера п- го столбца второй косоугольной матрицы триггеров является (N+n)-M разрядом первой входной шины операнда устройства, выход п-го триггера п- го столбца второй косоугольной матрицы триггеров подключен к второму информационному входу N-й ячейки (п+О-й строки матриц, выход х-го триггера (j-l)-ro столбца второй косоугольной матрицы триггеров подключен к входу (х+1)-го триггера то го же столбца второй косоугольной матрицы триггеров, первый выход р- го блока формирования сигнала считывания подключен к четвертому входу р-й управляющей ячейки столбца, второй выход р-го блока формирова-

25

93727 6

ния сигнала считывания подключен к четвертым управляющим входам всех ячеек р-й строки матрицы, управляющий вход п-го блока формирования г сигнала считывания подключен к третьему выходу (n-t-l)-го блока формирования сигнала считывания, управляющий вход N-ro блока формирования сигнала считывания подключен ч шине to значения логического нуля устройства, четвертый выход р-го блока формирования сигнала считывания подключен к р-му входу элемента ИЛИ, входу сброса всех блоков формирова- . t5 ния сигналов считывания подключены к выходу сброса блока синхронизации, выход элемента ИЛИ является выходной шиной сигнала считывания устройства, ,информационный вход р-го бло- 20 ка формирования сигнала считывания подключен к пятому выходу р-й ячейки N-ro столбца матрицы, вход кода операции блока синхронизации является входной шиной кода операции устройства, вход общего сброса блока синхронизации является входной шиной общего сброса устройства, выход тактовых импульсов блока синхронизации подключен к синхровходам всех триггеров устройства, выход сброса блока синхронизации подключен к входам сброса всех триггеров устройств а, выход упразления сортировкой блока синхронизации под- 35 ключей к входам управления сортировкой всех управляющих ячеек столбца, выход управления делением блока синхронизации подключен к входам управления делением всех управ- 0 ляющих ячеек столбца, выход управления извлечением квадратного корня блока синхронизации подключен к входам управления извлечением квад- ратного корня всех управляющих яче- 5 ек столбца, седьмой выход d-й (d 1, ,. . ,N N) ячейки матрицы является d-M разрядом выходной шины сортировки устройства, каждая ячейка матрицы дополнительно- содержит два тригге- 0 ра, элемент ИЛИ и два элемента И, причем второй информационный вход сумматора ячейки ма-трицы подключен к выходу первого триггера ячейки матрицы, установочный вход первого 5 триггера ячейки матрицы является вторым информационным входом ячейки матрицы, установочный вход второго триггера ячейки является тре30

1712

тьим информационным входом ячейки, выход второго триггера ячейки матрицы подключен к второму входу пер- вого элемента И ячейки матрицы, первому входу элемента ИЖ ячейки и первому входу второго элемента И ячейки и является четверть м выходом ячейки матрицы, второй вход второго элемента И ячейки матрицы является четвертым управляющим входом ячейки матрицы, выход второго элемента И ячейки матрицы является седьмым выходом ячейки матрицы, второй вход элемента JiM ячейки матрицы является четвертым информационным входом и восьмым выходом ячейки матрицы, выход элемента ИЛИ ячейки матрицы подключен к первому входу третьего элемента И ячейки матрицы, второй вход третьего элемента И ячейки матрицы является третьим управляющим входом ячейки матрицы, выход третьего элемента И ячейки матрицы является шестым выходом f ячейки матрицы, дополнительная ячейка матрицы содержит два триггера, элемент И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и сумматор, причем выход первого триггера дополнительной ячейки подключён к первому входу элемента И дополнительной ячейки, второй вход элемента И дополнительной ячейки, является первым управляющим входом дополнительно.й ячейки, выход элемента И дополнительной ячейки подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ дополнительной ячейки, второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ дополнительной ячейки является вторым управляющим входом и первым выходом дополнительной ячейки, выход второго триггера дополнительной ячейки подключен к первому информационному входу сумматора дополнительной ячей

ки, вглход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ дополнительной ячейки подключен ко второму информадаонному входу сумматора дополнительной ячейки, вход переноса сумматора дополнительной Ячейки является первым информацион- ным входом дополнительной ячейкИд f выход переноса сумматора дополнительной ячейки, является вторым выходом дополнительной ячейки, выход суммы сумматора дополнительной ячейки является третьим выходом дополнительной ячейки, установочньй вход

второго триггера дополнительной ячей- второй вход элемента ИЛИ подключен

5

5

0

5

0

5 0

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

2, Устройство по п, 1, отли

чающееся тем, что каждый блок выбора максимального числа содержит триггер, элемент ИЛИ и эле- мент ИСКЛЮЧАЮЩЕЕ ИЛИ, причем первьй вход элемента ИЛИ является входом блока выбора максимального числа.

19

к прямому выходу триггера, выход элемента ИЛИ подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход элемента ИСКЛЮЧАЮГЦЕЕ ИЛИ подключен к шине значения логического нуля устройства, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ подключен к установочному входу триггера, инверсный выход триггера является выходом блока выбора максимального числа.

3. Устройство по п. 1, о т л и - чаюп}ееся тем, что каждый блок формирования сигнала считывания содержит два триггера, три элемента

ляется четвертым выходом блока фор мирования сигнала считывания, втор вход второго элемента ИЛИ подключе к прямому выходу второго триггера, выход второго элемента ИЛИ подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход элемента ИС КЛЮЧАЮЩЕЕ ИЛИ подключен к шине значения логической единицы устройства 10 выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ под ключен к входу асинхронной установ ки второго триггера, вход асинхро ного сброса второго триггера объеди нен ср вторым входом первого элепержит два триггера, три элемента -- -

ИЛИ элемент И и элемент ИСКЛЮЧАЮЩЕЕ 5 мента ИЛИ, инверсньш вькод второго

ШЩ, JJlCMcn.„„„„„„ „-оттсютг-о ПРППКТМ ВЫХОПОМ

ИЛИ, причем инверсный вход первою элемента ИЛИ объединен с входом асинхронной установки первого триггера и является информационным входом блока формирования сигнала считывания, прямой вход первого элемента ИЛИ является входом сброса блока формирования сигнала считывания, выход первого элемента ИЛИ подключен к входу асинхронного сброса первого триггера, выход первого триггера подключен к первым входам второго элемента ИЛИ и элемента И и яв20

25

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

93727

ляется четвертым выходом блока формирования сигнала считывания, второй вход второго элемента ИЛИ подключен к прямому выходу второго триггера, выход второго элемента ИЛИ подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ подключен к шине значения логической единицы устройства, 10 выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ подключен к входу асинхронной установки второго триггера, вход асинхронного сброса второго триггера объединен ср вторым входом первого эле -- -

5 мента ИЛИ, инверсньш вькод второго

мента ИЛИ, инверсньш вькод второго

„„„„„„ „-оттсютг-о ПРППКТМ ВЫХОПОМ

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

9 оЗ оЭ

8,

Фиг. 2

Фиг.3

Изобретение относится к области вычислительной техники си может быть использовано для выполнения операций умножения, деления, извлечения квадратного корня и сортировки больших массивов многоразрядных чисел. Цель изобретения - расширение функциональных возможностей устройства за счет выполнения операции сортировки и повышение производительности обработки больших массивов данных. Устройство конвейерно- матричного типа содержит матрицу из N строк и N стлобцов, два дополнительных столбца из N ячеек и N ячеек управления, триггеры, N схем выбора максимального числа, N схем формирования сигнала считывания и элемент ИЛИ, где N - разрядность операндов. Каждая ячейка матрицы и дополнительного столбца содержит два три1 гера, логические элементы и сумматор, а ячейка управления - логические элементы И, ИЛИ. Схема выбора максимально1 о числа содержит последовательно соединенные элемент ИЛИ, элемент ИСКЛЮЧАКЩЕЕ ИЛИ и триггер, а схема формирования сигнала считывания дополнительно к этим элементам включает триггер, два элемента ШШ, элемент И, Эффективность устройства растет с увеличением разрядности чисел и объема обрабатываемой информации. 2 з.п, ф-лы, 8 ил., 2 табл. с S (Л

LM

Фиг.

L3fJ

Фиг.§

Фиг. 6

Фиг,7

Запись соптируемо о массива

Выбор MQKCUMOflbHOW

слова из массива

Конец

Редактор Л. Пчелинская Заказ 387/53

Составитель С. Силаев

Техред И,Попович Корректор Т. Копб

Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно полиграфическое предприятие,, г,Ужгород,ул. Проектная, 4

Фие.8