Ячейка однородной среды Советский патент 1978 года по МПК G06F7/00 

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

Известна ячейка однородной среды l , содержащая триггер и логические элементы И и ИЛИ.

в устройствах, построенных из известных ячеек, упорядочение информации производится путем выполнения определенной последовательности опросов ассоци.ативной матрицы в соответствии с так называемым алгоритмом СибераЛиндквиста. При этом для упорядочения массива из N элементов информации требуется в среднем 2,9 N .команд.

Для р«иенйя задачи выделения упорядоченного списка элементов в заданных границах Р| А Pj в известных устройствах предварительно в специальный столбец ассоциативной матрицы для всех элементов исходного массива заносятся единицы. Затем проводится упорядоченный поиск (в порядке убывания) всех элементов, начиная с Р и в выделенных строках стираются единицы столбца меток. Аналогично проводится упорядоченный поиск (в порядке возрастания) всех элементов, начиная

с Р:

а также стираются метки. В

результате метки остаются только у тех элементов, которые расположены в заданных границах. После этого проводится упорядоченная выборка всех отмеченных (искомлх) элементов.. Поскольку в общем просматривается весь массив число команд постоянно (2,9 N ) и не зависит от .полезного объема массива NO , т.е. от того, сколько элементов удовлетворяют заданным условиям.

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

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

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

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

Эта цель достигается тем, что в ячейку однородной среды введены пятый этемент И и третий элемент ИЛИ, Первый вход пятого элемента И соединен с выходом третьего элемента И, второй вход - со вторым входом четвертого элемента И, а выход - с первым входом третьего элемента ИЛИ, второй вход которого подключен к пятому входу яче ки. На чертеже приведена логическая сх ма предлагаемой ячейки однородной сре ды, Ячейка 1 имеет входы 2, 3, 4, 5 и 6 переменных Z, X,v,v и U соответственно и выходы 7, 8, 9, Юи 11 переменных z х у/ V и и соответственно и содержит триггер 12 с входными элементами И 13 и 14, элементы И 15, 16 и 17 и элементы ИЛИ 18, 19 и 20. В однородной среде выходы 8 и 9 ка дой ячейки 1 соединены со входами 3 и 4соседней по вертикали ячейки соответственно, а выходы 7, 10 и 11 - со входами 2, 5 и 6 соседней по горизонтали ячейки соответственно. Внутри каждой ячейки 1 первые входы элементов И 15 и 16 соединены со входом 2, выход элемента И 15 - с пер выми входами элементов ИЛИ 18 и И 19, второй вход элемента ИЛИ 18 - со входом 3 ячейки, а второй вход элемента ИЛИ 19 - с выходом элемента И 16, Выход элемента ИЛИ 18 (19) подключен к выходу 8 (7) ячейки. Второй вход элемента И 15 соединен с единичным выходом триггера 12, а второй вход элемента И 16 - со входом 4 и выходом 9 ячейки. Первый вход элемента И 17 сое динен с выходом элемента И 15, второй вход - со входом 4 ячейки, а выход с первым входом элемента ИЛИ 20, второй вход которого соединен со входом 5ячейки, а выход - с выходом 10 ячей ки , Ячейка однородной среды реализует функции , x:Xvaz, (1) z- Z(qvv1, (2) v Vv /qv, (3) 9-, JJ , (4) S-oUv, (5) где C( - состояние триггера 12. Функции (4) и (5) позволяют осуществить парафазную запись информации

в триггер 12, Для этого прямой код записываемой двоичной цифры подается на вход 3, обратный - на вход 4.и одновременно на вход б подается импульс записи. Признак сравнения РР Р2 .,, подается поразрядно на входы у соответствующих столбцов однородной среды в обратном коде.

Функции (1) и (2) совместно обеспечивают выделение максимальных элементов информации,

Для выяснения роли функции (3), которая действует совместно с функцией (2) построим табл... Из этой таблицы видно, что avp I в хех случаях когда с J р , dtp - 1 в том случае, когда

rt Р

Таблица Выражение (2) показывает, что сигнал на выходе Z ячейки равен 1, если имеется сигнал 1 на входе и, кроме того, CJ $ р . Выражение (3) показывает, что сигнал на выходе V ячейки равен 1, если имеется сигнал 1 на входе V либо сигнал 1 на входе Z , и кроме того, о зрДля выполнения операции сравнения на все входы Z левой границы однородной среды подается сигнал 1, а на все входы левой границы - сигнал О, При сравнении произвольных чисел и P-Pi.p2--- возможны три случая: 1,Во всех разрядах . это значит, что А Р . Согласно выражениям (2) и (3) при этом на правой границе вырабатывается сигнал пр 1 и vnp-O, 2,Во всех старших разрядах (до некоторого j -го) р , я, ру (т.е. oi;ti, р г 0), Это значит, что независимо от соотношения дальнейших разрядов. Так как 2,, 1, то, согласно выражениям (2) и (3),в J -и ячейке 2- 1 и . Если во всех дальнейших (младших) разрядах , тог, если же хотя бы в одном разряде то 2пр- 0, 3,- Во всех старших разрядах (до некоторого J -го) а р , « PJ (т.е. ctjOf p.). Это значит, что независимо от соотношения дальнейших разрядов,,, Согласно выражениям (2) и (3), О и : 0. Следовательно и v 0. Результаты приведенного анализа по азаны в табл.2, Таблица2 Таким образом, однородная среда, построенная из предложенных ячеек, обеспечивает решение за одну команду следующих видов информационно-логических задач: 1.Поиск максимального элемента ин формации в массиве. 2.Выделение всех элементов информации, совпадающих с заданным признаком. 3.Разбиение массива на три подмножества, в первое из которых входят все элементы информации, совпадающие с заданным признаком, во второе - все элементы, меньшие заданного признака в третье - все элементы, большие заданного признака. Рассмотрим примеры решения некото рых распространенных информационнологических задач в однородной среде, построенной из предложенных ячеек. 1.Упорядочение информации проводится путем поочередного выделения максимальных элементов информации. В деленные элементы исключаются из дал нейшей обработки (например, путем вы ключения сигнала Z на левой границ соответствующих строк среды). Для упорядочения массива из эле ментов требуется N команд. 2.Выделение упорядоченного списк элементов, расположенных в заданных границах Р А Ра Для решения этой задачи вначале проводится сравнение с признаком PI после чего все элементы, удовлетворяющие условию , исключаются из дальнейшей обработки. Затем проводит ся сравнение с признаком г , и исключаются все элементы А РЗ . В оставшемся подмножестве проводится упо рядочение (см. ВЕЛше) . Таким Образом, для решения этой задачи требуется о+2 команды, где NO - число элементов исходного мас сива, удовлетворяющих заданным усло виям. J. Поиск элемента, ближапшего меньего заданного признака Р. Вначале проводится сравнение с принаком Р и исключаются все элементы А Р. Затем в оставшемся массиве выеляется максимальный элемент, котоый и является искомым. Для решения задачи требуются 2 коанды. 4. Ассоциативная обработка инфорации . Поскольку в однородной среде, потроенной из предлохсенных ячеек, имется операции ассоциативного поиска параллельной записи, она может быть спользована в качестве матрицы-наопителя ассоциативного вычислительного устройства, т.е. обеспечивает эффективную реализацию всех известных алгоритмов ассоциативной обработки информации. Формула изобретения Ячейка однородной среды, содержащая триггер, четыре элемента И и два элемента ИЛИ, причем первый вход ячейки соединен с первыми входами первого и второго элементов И, второй вход первого элемента И подключен ко второму входу ячейки и первому входу первого элемента ИЛИ, торой вход которого соединен с выходом третьего элемента И и первым входом второго элемента ИЛИ, второй вход .которого подключен к выходу четвертого элемента И, первый вход которого соединен с третьим входом ячейки и первым входом третьего элемента И, а второй вход - с четвертым входом ячейки и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера, сг,и ничный вход которого соединен с выходом первого элемента И, а единичный выход - со вторым входом третьего элемента И, отличающаяся тем, что, с целью расширения функциональных возможностей, в нее введены пятый элемент И и третий элемент ИЛИ; причем первый вход пятого элемента И соединен с выходом третьего элемента И, второй вход - со вторым входом четвертого элемента И, а выход - с псрпклм входом третьего элемента ИЛИ, второй вход которого подключен к пятому входу ячейки. Источники информации, принятые во внимание при экспертизе: 1. Патент США № 3320594 , кл . 340-П г, 1972.„,.,,р 2 Авторское свидетельство СССР 424141, кл. G 06 Р 7/00, 1971.