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

(11) 610105 ЕТЕЛЬСТВ ТОРСКОМ ополнительное ав(ЗЗ) Опубликовано 21 2158429/2 Ы 06 У вкн Государственный намнтет Совета Мнннатрав СССР аа делам нзааретеннй н аткрытнй5 ЗЭ етень РЙ 21.78. Бю 325(088.8 5) Дата опбликования описания 15,05,7 72) Автор изобрете я.и. фе(71) Заявите Инсти атематики Сибирского отделения АН СССР(54) ЯЧЕИКА О ОЙ С едной средыогические Изобретение относится к области цифровой вычислительной техники и пр назначено для массовой параллельной обработки информации.Известна ячейка однород (1), содержащая триггер и л элементы И и ИЛИ.В устройствах, построенных из известных ячеек, упорядочение информации производится путем выполнения определенной последовательности опросов ассоциативной матрицы в соответствии с так называемым алгоритмом СибераЛнндквиста. При этом для упорядочения массива из И элементов информации требуется в среднем 2,9 М ,команд.Для решения задачи выделения упорядоченного списка элементов в заданных границах Р, с АРа в известных устройствах предварительно в специальный столбец ассоциативной матрицы для всех элементов исходного массива заносятся единицы. Затем проводится упорядоченный поиск (в порядке убывания) всех элементов, начиная с Р, и в выделенных строках стираются единицы столбца меток. Аналогично проводится упорядоченный поиск (в порядке возрастания) всех элементов, начиная с Рз , а также стираются метки, В результате метки остаются только у тех элементов, которые расположены в заданных границах. После этого проводится упорядоченная выборка всех отмеченных (искомых) элементов,. Поскольку в общем просматривается весь массив, число команд постоянно (2,9 И ) и не зависит от полезного объема массива по , т.е. от того, сколько элементов удовлетворяют заданным условиям.Недостатком таких устройств является большой расход времени при решении инФормационно-логических задачНаиболее близкой по технической сущности к изобретению является ячейка устройства для сортировки информации 21, содержащая триггер, четыре элемента И и два элемента ИЛИ, Первый вход ячейки соединен с первыми входами первого и второго элементов И, Второй вход первого элемента И подключен ко второму входу ячейки и первому входу первого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И и первым входом второго элемента ИЛИ, второй вход которого подключен к выходу четвертого элемента И, первый вход которого соединен с третьим входом ячейки и первым входом третьего элемента И, а второй610105 вход - с четвертым входом ячейки и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера, единичный вход которого соединен с выходом первого элемента И8 а единичный выход - со вторым входом третьего элемента И.Целью изобретения является расширение Функциональных возможностей однородной среды при решении информационно-логических задач,Эта цель достигается тем, что в ячейку однородной среды введены пятый элемент И и третий элемент ИЛИ. Первый вход пятого элемента И соединен с выходом третьего элемента И, второй )6 вход - со вторым входом четвертого элемента И, а выход - с первым входом третьего элемента ИЛИ, второй вход которого подключен к пятому входу ячей. ки.20 в триггер 12. Для этого прямой код записываемой двоичной цифры подается на вход 3, обратный - на вход 4 и одновременно на вход 6 подается и,.1 пульс записи. Признак сравнения Р "Р 1 Р 2.подается поразрядно на входы у соответствующих столбцов однородной среды в обратном кодеФункции (1) и (2) совместно обеспечивают выделение максимальных элементов информации.Для выяснения роли Функции (3), которая действует совместно с функцией (2) построим табл,1. Из этой таблицы видно, что ачР = 1 в тех случаях когда др, ср = 1 в том случае, когдаОР Таблица 1 ч =Очр ачфар 0 0 0 1 1 0 1 1 Выражение (2) показывает, что сигнал на выходе 2 ячейки равен 1, еслиимеется сигнал. 1 на входе Е и, кроме того, ОР . Выражение (3) показывает, что сигнал на выходе ч ячейкиравен 1, если имеется сигнал 1 на входе ч либо сигнал 1 на входе Е , икроме того, а РДля выполнения операции сравненияна все входы 2 левой границы однородной среды подается сигнал 1, а навсе входы ч левой границы - сигнал О,При сравнении произвольных чиселА -о с( и Р . р, рвозможны трислучая:1. Во всех разрядах а Р . Это значит, что А ф Р . Согласно выражениям(2) и (3) при этом на правой границевырабатывается сигнал 2- 1 и ч ррО.12. Во всех старших разрядах (донекоторого ) -го) а р , а,р (т,е,аф 1, Р = 0), Это значит, что АРнезависимо от соотношения дальнейшихразрядов. Так как 2, -. 1, то, согласновыражениям (2) и (3), в-й ячейке2 ф 1 и ч- .1. Если во всех дальнейших (младших) разрядах а - Р , то т,=Весли же хотя бы в одном разряде ар,то 2 р= О,3. Во всех старших разрядах (до некоторого ) -го) а = р, д = р, (т.е.а 1 -.О, р =1) . Это значит, что Арнезависимо от соотношения дальнейшихразрядовСогласно выражениям (2) и (3), ,ф 0и Ч, = О. Следовательно У"р:0 и ч": О,На чертеже приведена логическая схема предлагаемой ячейки однородной средывЯчейка 1 имеет входы 2, 3, 4, 5 и 6 переменных Е Х, У, чУ соответствен,но и выходы 7, 8, 9, 10 и 11 переменных 2, х, у, ч и О соответственно и содержит триггер 12 с входными элементами И 13 и 14, элементы И 15, 16 и 17 и элементы ИЛИ 18, 19 и 20.В однородной среде выходы 8 и 9 каждой ячейки 1 соединены со входами 3 и 4 соседней по вертикали ячейки соответственно, а выходы 7, 10 и 11 - со входами 2, 5 и 6 соседней по горизонтали ячейки соответственно,Внутри каждой ячейки 1 первые входы элементов И 1 5 и 16 соединены со входом 2, выход элемента И 15 - с первыми входами элементов ИЛИ 18 и И 19, 40 второй вход элемента ИЛИ 18 - со входом 3 ячейки, а второй вход элемента ИЛИ 19 - с выходом элемента И 16, Выход элемента ИЛИ 18 (19) подключен к выходу 8 (7) ячейки, Второй вход эле мента И 15 соединен с единичным выходом триггера 12, а второй вход элемента И 16 - со входом 4 и выходом 9 ячейки. Первый вход элемента И 17 соединен с выходом элемента И 15, второй 50 вход - со входом 4 ячейки, а выход - с первым входом элемента ИЛИ 20, второй вход которого соединен со входом 5 ячейки, а выход - с выходом 10 ячейки, г,5Ячейка однородной среды реализует ФункцииХ -Хча (1)1Е = Е (ачба), (2)ч "- чч Уау, (3)с,: оХ, (4)9, Оч, (Е)где О - состояние триггера 12.функции (4) и (5) позволяют осуществить парафазную запись информации ,15Результаты приведенного анализа поазаны в табл.2. Таблица 2 0 дная среда,ных ячеек,одну командуионно-логиче разом, однор из предложе т решение за идов информа ким об оенная ечивае ющих в задач: Поиск ма ции в мас Выделени пост обес след ских1 Форм имального элемента инве.всех элементов инф ор- намации, совпадающих с заданным приз ком.3. Разбиение массива на три подмножества, в первое из которых входят все элементы информации, совпадающие с заданным признаком, во нторое - все элементы, меньшие заданного признака, в третье - все элементы, большие заданного признака.Рассмотрим примеры решения некоторых распространенных информационно- логических задач н однородной среде, построенной из предложенных ячеек.1. Упорядочение информации проводится путем поочередного выделения максимальных элементов информации. Выделенные элементы исключаются из дальнейшей обработки (например, путем выключения сигнала 2 на левой границе соответствующих строк среды). Для упорядочения массива из 1 эл ментов требуется М команд.2. Выделение упорядоченного списка элементов, расположенных в заданных границах Р,АРкДля решения этой задачи вначале проводится сравнение с признаком Р после чего все элементы, удонлетноряющие условию АР 4, исключаются из дальнейшей обработкй. Затем проводится сравнение с признаком, и исключаются все элементы АР 2 , В останшемся подмножестве проводится упорядочение (см. выше),Таким образом, для решения этой задачи требуется И о+2 команды, где)4 о - число элементов исходного маса, удовлетворяющих заданным усло- м есин вия3. Поиск элемента, ближайшего меньшего заданного признака Р.Вначале проводится сравнение с признаком Р и исключаются все элементы АР. Затем в оставшемся массиве выделяется максимальный элемент, который и является искомым.Для решения задачи требуются 2 команды.4. Ассоциат ая обработка информации.Поскольку н однородной среде, построенной из предложенных ячеек, имеются операции ассоциативного поиска и параллельной записи, она может быть использована н качестве матрицы-накопителя ассоциативного вычислительного устройства, т,е. обеспечивает эффективную реализацию всех известных алгоритмов ассоциативной обработки информации. ивн ени ормула из ри пятые 4,кл.3 1972.2. Ав У 424141 ское свидетельство СССРл. 6 06 Р 7/00, 1971. Ячейка однородной среды, содержащая триггер, четыре элемента И и дваэлемента ИЛИ, причем первый вход ячейки соединен с первыми входами первогои второго элементов И, второй вход перного элемента И подключен ко второмувходу ячейки и первому входу первогоэлемента ИЛИ, торой вход которогосоединен с выходом третьего элементаИ и первым входом второго элемента ИЛИ,второй вход которого подключен к выходу четвертого элемента И, первыйвход которого соединен с третьим входом ячейки и первым входом третьегоэлемента И, а второй вход - с четвертым входом ячейки и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера, егиничный вход которого соединен с выходом первого элемента И, а единичныйвыход - со вторым входом третьего элемента И, о т л и ч а ю щ а я с я тем,что, с целью расширения Функционльных возможностей, в нее введены пятыиэлемент И и третий элемент ИЛИ; причем первый вход пятого элемента И соединен с выходом третьего элемент И,второй вход - со вторым входом четвертого элемента И, а выход - с первымвходом третьего элемента ИЛИ, втор.пвход которого подключен к пятому входу ячейки,Источники информации, иннимание при экспертизе:1. Патент США М 332059 40-172,610105 Составитель В.ТарасовРедакто Л,Утехина Тех е Н.Ваб ка Ко екто А. Власен филиал ППП Патен Ужгород Проектн акаэ 3011/37 Тира ЦНИИПИ Государственн по делам 113035 Москва826 Подпис го комитета Совета Ми зобретеннй и открытийЖРа шс б е стро