Ячейка однородной среды

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОИ:КОМУ СВИ ИЗЛЬСТВУ

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

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

Республик

<о851398 (61) Дополнительное к авт. сеид-ву 9 610105 (22) Заявлено 13.11.79 (21) 2859793/18-24 с присоединением заявки йо (23) Приоритет (я)м. к .з

G 06 F 7/00

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

СССР яо яелам нзобретеянй я открытмя

Опубликовано 300781. бюллетень Н9 28 (53) УДК 681. 3 (088. 8) Дата опубликования описания 30. 07. 81 (72) Автор изобретения

Я.И. Фет

>

Институт математики Сибирского отделения

AH СССР (71) Заявитель (54) ЯЧЕЙКА ОДНОРОДНОЙ СРЕДЫ

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

По основному авт.св. Р 610105 известна ячейка однородной среды содержащая триггер, пять элементов И и три элемента ИЛИ, причем первый вход ячейки, соединен с первыми входами первого и второго элементов И. второй вход первого элемента Й под-. ключен ко второму входу ячейки и пер вому входу первого элемента ИЛИ, выход которого соединен с первым выходом ячейки,а второй вход первого элемента ИЛИ - с выходом третьего элемента И и первым входом второго элемента ИЛИ, выход которого подключен ко второму выходу ячейки, а второй вход - к выходу пятого элемента И, первый вход которого соединен с третьим входом ячейки и первым входом третьего элемента И,.а второй вход - с четвертым входом ячейки> вторым входом четвертого элемента И и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера, единичный вход которого соединен с выходом первого эле» мента И, а единичный выхсд — со вторым входом третьего элемента И, выход четвертого элемента И подключен fc первому входу третьего элемента ИЛИ, выход которого соединен с третьим выходом, а второй вход— с пятым входом ячейки. двумерная однородная структура, построенная из таких ячеек, обеспечивает выполнение за одну команду ряда простых информационно-логических операцийт поиск максимального элемента информации в массиве, выделенив всех элементов информации,сов15 падающих с заданным признаком, разбиение массива на три подмножества, s первое из которых входят все элементы, совпадающие с заданным признакоы, во второе - все элементы, 20 меньшие заданного признака, в тре- .. тье - все элементы, больше заданного признака (11.

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

Так, например, для поиска всех эле30 ментов информации А, расположенных

851398 в заданных границах (Q 4 A„6 P) г тРебуется последовательность из двух команд: в первой команде выделяются все элементы, удовлетворяющие усло-, вию А 6 Q, во второй — все элементы, удовлетворяющие условию А„ Ъ Р, Оставшиеся элементы образуют результирующий массив.

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

Укаэанная цель достигается тем, что в ячейку однородной структуры по авт.св. Р 610105 введены шестой, седьмой и восьмой элементы H и чет- 15 вертый элемент ИЛИ, причем первые входы шестого и седьмого элементов И соединены с шестым входом ячейки, второй вход шестого элемента И подключен к нулевому выходу триггера, 2О а второй вход седьмого элемента Ик седьмому входу ячейки и первому входу восьмого элемента И, выход которого соединен с третьим входом третьего элемента ИЛИ, второй вход восьмого элемента И соединен с выходом шестого элемента И и первым . входом четвертого элемента ИЛИ,второй вход которого подключен к выходу седьмого элемента И, а выход соединен с четвертым выходом ячейки °

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

На чертеже приведена функциональная схема ячейки однородной среды. 40

Ячейка имеет входы 1-7 переменных х, у,у, „ z,u 7 соответственно и выходы 8-14 переменных x,y,y,z",,u,v соответственно и содержит триггер 15 со входными элементами 4$

И 16 и 17, элементы И 18-23 и элементы ИЛИ 24-27.

В однородной структуре выходы 8-10 каждой ячейки соединены со входами

1-3 соседней по вертикали ячейки соответственно, а выходи 11-14 — со входами 4-7 соседней по горизонтали ячейки соответственно.

Внутри каждой ячейки первые входы . элемейтов И 18 и 20 соединены со входом 4 ячейки, выход элемента,И 18 с первыми входами элемента И 19 и элементов ИЛИ 24 и 25,. а выход элемента И 20 — со вторым входом элемента

ИЛИ 25. Второй вход элемента И 18 соединен с единичным выходом тригге- 4 ) ра 15, а вторые входы элементов И

19 и 20 — с первым входом элемента

И 17 и со входом 2 ячейки. Второй вход элемента ИЛИ 24 подключен к первому входу элемента И 16 и ко 65

1 входу 1 ячейки, а вторые входы элементов И 16 и 17 — ко входу 6 ячейки. Первые входы элементов И 21 и

22 соединены со входом 5 ячейки, выход элемента И 21 — с первыми входами элементов И 23 и ИЛИ 27. Второй вход элемента И 21 подключен к нулевому выходу триггера 15, а вторые входы элементов И 22 и 23 — ко входу

3 ячейки. Второй вход элемента ИЛИ

27 соединен с выходом элемента И 22.

Первый, второй и третий входы элемента ЙЛИ 26 соединены соответственно со входом 7 ячейки и с выходами элементов И 19 и 23. Выходы,элементов ИЛИ 24-27 подключены соответственно к выходам 8,11,14 и 12 ячейки.

Ячейка однородной среды реализует следующие функции

x = xvaz (1)

z (avy, ) (2)

z (ачу ) (31

V "- ччХ,О vz og (4) (5)

У< (6) где а - состояние триггера 15.

Функции (5) и (6) позволяют осуществить запись информации в триггер 15 со входов х и у а Функция (1) " считывание содержимого триггера 15 по выходу х1 . Функции (1), (2) и (4) обеспечивают работу устройства во всех режимах. При этом признак сравнения должен подаваться поразрядно (в обратном коде) на входы, столбцов однородной структуры, а. на все входы должны подаваться константы l =О.

Для выполнения поиска всех элементов, расположенных в заданных границах, используются функции (2), (3) и (4). При этом признак Р=,Й «, соответствующий верхней границе, подается поразрядно (в обратном коде) на входы, столбцов однородной структуры, а признак Cl =- +„gq> соответствующий нижней границе, подается поразрядно на входы ., На входы

z,, z и ч левой границы однородной структуры во всех строках подаются . константы Х„ 1, х = 1, Ч = 0

В каждой строке однородной структуры с помощью цепи м производится поразрядное сравнение (начиная со старших разрядов) хранимого и запоминающих элементах данной строки числа А+ = а-, а„.;. с верхним граничным признаком Р = р, р, ... и одновременно с помощью цепи z сравнение AÄ = aÄ, а; с нижним гранияным признаком Q q q и

Еак показывает анализ, при сравнении А„ с P сигнал v на правой границе однородной структуры в соответствии с выражениями (2) и (4) принимает значение V 1 только в том случае, когда A„ 7 Р, т.е. находится

851398 ничного признака использовать число большее, чем максимальное возможное значение элемента массива, то выделятся все A„- > Q. Если задать P.-Q=R, то выполнится поиск по совпадению

Q-R°.

ТакиМ образом, область применения предлагаемой ячейки расширяется по сравнению с известной а структура, построенная из таких ячеек, становится более быстродействующей.

Ì5

0 0 СА,"С P

0=А.СР

ОQсА->Р

1 Q A;-= Р

Комбинируя сигналы Y X,, и Q можно с помощью однородной структуры, построенной из данных ячеек, за одну команду выполнить различные варианты поиска в заданных границах. Например, комбинация ч Z, = 3 соответствует поиску Q < А с Р а комбиНара@ v %I 1 rtoacx y Q, < А c P. 5

Если в качестве нижнего граничного признака Q использовать число. меньшее, чем минимальное возможное значение элемента массива, то в устройстве за одну команду выделятся все 40

А; а Р. Если в качестве верхнего гравне заданного интервала. Аналогично при сравнении А с Q в соответствии с выражениями (3) и (4) сигнал Ч на правой границе принимает значение с = 1 только в том случае, когда А А Я, т.е. находится вне заданного интервала. Следовательно, только ситуация 4 = 0 свидетельсУвует о том, что число, записанное в данной строке, удовлетворяет критерию поиска (Q 4 А 4С P).

Характер неравенства на границах заданного интервала может быть при этом определен по сигналам Z и Z

4 на праной границе в соответствии с таблицей.

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

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

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

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

Ф 610105, кл. G 06 F 7/00, 1975 (прототип), 851398

Х

Составитель B. Кайданоз редактор H. Безродная Техред,H. Еелушак Корректор В. Синицкая

Заказ 63бО/б9

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

Е7

«т

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

ВНИИПИ Государственного комитета CCCP по делам изобретений и открытий, 113035, Москва, %-35, Раушская наб., д. 4/5