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

) (и 4 6 06 Г,7/ ИТЕТ С й и отнр судАРственны ПО ДЕЛАМ ИЗОБРЕИЗОБРЕТЕНИЯ РСНОМУ СВИ Т(56) Авторское свидетельство СССР Ф 610105, кл, С 06 Г 7/00, 1975,Авторское свидетельство СССР Ф 851398, кл. О 06 Г 7/00, 1979,Авторское свидетельство СССР У 1013943, кл. О 06 Г 7/00, 1982,Фет Я.И, Параллельные процессоры для управляющих систем. М,: Энергоиздат, 1981; с. 41. (54) ЯЧЕЙКА ОДНОРОДНОЙ СРЕДЫ (57) Изобретение предназначено для использования в ассоциативных параллельных процессорах для обработки и преобразования структур данных, Цель изобретения - повьппение быстродействия за счет выделения в одной микрооперации элементов массива, попадающих в заданный числовой интервал, равных границам интервала, больших верхней границы интервала, меньших нижней границы интервала. Ячейка однофазной среды содержит триггер, шесть элементов И, два элемента НЕ, три элемента ИЛИ, элемент И-ИЛИ и коммутатор, Ячейка однородной среды выполняет следующие виды информационного поиска за одну микрооперацию: а) поиск элементов массива, попадающих в,заданный числовой интервал Х , Х , равных границам интервала, н пфбольших верхней границы интервала Х, меньших нижней границы интервала Х 1 б) поиск максимального и миннимального элементов в двух массивах в) поиск всех больших, меньших, равных элементов массива по отношению ко входной переменной Х. 2 ил, 1260942Изобретение относится к цифровойвычислительной технике и может бытьиспользовано в ассоциативных парал-.лельных процессах для обработки данных, 5Целью изобретения является повышение быстродействия ячейки однородной среды за счет выделения в одноймикрооперации элементов массива, попадающих в заданный числовой интервал, равных границам интервала, больших верхней границы интервала, меньших нижней границы интервала.На. Фиг. 1 приведена Функциональная схема предлагаемой ячейки од- .нородной среды; на Фиг. 2 . графикизменения значений сигналов 77, Ы.Ячейка включает: элементы НЕ 1 и2, элементы И 3-8; триггер 9, элементы ИЛИ 10-12, коммутатор 13, элемент И-ИЛИ 14, настроечные входы 1517, вход записи 18, информационныеходы 1922, настроечные выходы 2325 информационные выходы 26-27,При формировании из предлагаемыхячеек однородной структуры размеромила, где и - количество столбцов, ав - количество строк. настроечныевыходы 23-25 каждой ячейки соединяются с настроечными входами 17, 16,15 соответственно соседней справаячейки, а информационные выходы 26и 27 - с информационными входами29 и 19 соответственно соседней снисзу ячейки. Информационные входы 21и 22 являются общимп для всех ячеек,образующих столбец, а вход записи18 является общим для всех ячеек,образующих строку. 40Предлагаемая ячейка однороднойсредь реализует Функции:2-;. Х 7, аг;И;= а, а,,аД, занимающего строку длиной и однородной структуры, старшимиразрядами слева);Х , Х - соответственно значения снфразрядов нижней Х=Х;,=-(Х ,Х Х , границ интервала, подаваемые наинформационные входы 21 и22 ячеек однородной структуры, всегда Х Х,;27 ,Ч - значения переменных насоответствующих настроечных входах 17, 15, 16 ячейки;ЕЕ ,Ч - значения переменных на соответствующих настроечныхвыходах 23, 25 24 ячейки,"УУ - значения переменных наинформационных входах 19и 20 соответственноУУ - значение переменных на информационных выходах 27 и26 соответственно,Входы У, и У ячеек первой строки однородной структуры являютсяустановочными и;на них постоянно подан сигнал "О".Ячейка однородной среды при выполнении микроопераций работает следующим образом,Запись информации, Прямой кодзаписываемого двоичного слова А подается поразрядно на входы 21, а инверсный код . - на входы 22 соответствующих столбцов однороднойструктуры. Одновременно на входызаписи 18 всех ячеек выбранной строки подается сигнал записи,Считывание информации. Для выполнения считывания необходимо в каждом столбце однородной структурысоединить выход 26 (У ) самой ниж 2ней ячейки через схему НЕ с входами22 всек ячеек этого столбца, а выход27 (У ) - с входами 21 всех ячеекэтого столбца. Ячейка позволяетпроизводить считывание информацииодновременно из двух строк однород 1ной структуры на выходах У, и Упоследней строки, причем на выходах1информация в инверсном коде, НаЯвходы 17, 15, 16 крайнего левогостолбца однородной структуры подаются граничные сигналы Е, =1, 7,=У=О(выход у ) и 2,=И=О, Е =1 (выход М, )для считываемых строк и граничныесигналы 7.,=7. =И=О или И= для остальных строк однородной структурыРазбиение массива издвоичныхслов А на подмножества, в которыевходят А)ХА(Х , Х А(Х 8, А=ХА=Хе.В этом случае на входы 17, 15и 16 всех ячеек первого (крайнего1260942 АХвА(Х;ХАХ,;ХнА=ХЬ В=001,В=101,В=000,В=100,В=010,25 30 2,=2 =1, Ч=О,а,В=001,В=101,В=110,А)Х;А(Х;А=Х 40 левого) столбца однородной структуры соответственно подаются граничные сигналы 2=2 =1, Ч=О; на входы 21 и 22 ячеек каждого столбца соответственно границы интервала Х, 5 Хв, поразрядно, старшими разрядами слева. Каждая ячейка однородной сре/ ды может изменять значения 2 , 21 ф 21 Ч на своих выходах (Аиг, 2) в соответствии с выражениями (1) -(3)Таким образом, после окончания переходных процессов на выходах 23, 25, 24 ячеек последнего столбца однородной структуры появятся вектора признаков В=2,2 ,Ч , которые указывают на принадлежность двоичных слов А одному из подмножеств Поиск всех больших, меньших и равных сводится к предыдущему разбиению массива из н двоичных слов А, если положить Х=Хв=Х. На входы 17, 15, 16 всех ячеек первого столбца однородной структуры соответственно подаются граничные сигналы а на входы 21 и 22 ячеек каждогостолбца поразрядно - значение Х.Тогда после окончания переходных про-З 5цессов на выходах 23, 25, 24 ячеек.последнего столбца вектор В имеетследующие значения:=1,п, то в цели 2 появляется сигнал "О" и данная строка исключается из поиска. Ситуапия а, =0 Х = возникф 61 нуть не может, так как если о, -м столбце однородной структуры хотя бы в одной ячейке а =О, то на входеФ1 22 всех ячеек столбца Х = У =О, ТогЬ 1 2 да после окончания переходных процессов на выходах 23, 25, 24 ячеек последнего столбца вектор В имеет следующие значения: В=01 Х 1 двоично" го слова А, имеющего минимальное значение в массиве из п, В=ООХ У всех остальных слов массива, где Х - неанализируемое значение разряда. На выходах 26 ячеек самой нижней строки находится инверсное значение минимального элемента в массиве из Я.Поиск максимального элемента в массиве из ш двоичных слов А. На входы 17, 16, 15 всех ячеек первого столбца однородной структуры соответственно подаются граничные сигналы 2=1, Ч=2 =О. Если а. =0; Х; =1,то в цепи Ч йоявляется сигнал "1", который так же сохраняется в цепи 2, и данная строка исключается из поиска. Ситуация а. =1; Х, =0 воэник 1нуть не может, так как если в 1 -м столбце однородной структуры хотя бы в одной ячейке а=1, то на входе 21 всех ячеек столбца Х, = У, =1 . Тогда после окончания переходных процессов на выходах 23, 25, 24 ячеек последнего столбца вектор В имеет следующие значения: В=100 у двоичного слова А, имеющего максимальное значение в массиве из ш, В=101 у всех остальных слов массива. На выходах 27 ячеек самой нижней строки. находится значение максимальногоПоиск минимального и максимального элементов массива. Для выполнениягэтой микрооперации необходимо в каж дом столбце однородной структуры выходы 26 и 27 самой нижней ячейки соединить соответственно с входами 22 через схему НЕ всех ячеек того же столбца и с входами 21 всех ячеек 50 того же столбца.Существуют модификации этой микрооперации,Поиск минимального элемента в массиве из н двоичных слов А. На входы 55 17, 16, 15 всех ячеек первого столбца однородной структуры соответственно подаются граничные сигналы 21=Ч=О, 2, =1. Если а; =1, Х;=О, 1 щ элемента в массиве из ш,Поиск максимального в массиве из р и минимального в массиве из г элементов, р+г=ш. Поиск максимального элемента осуществляется подачей на входы 17, 1 б, 15 ячеек первого столбца однородной структуры, принадлежащих массиву р элементов, граничных сигналов 2,=1, Ч=2 =0Поиск минимального элемента осуществляется подачей на входы 17, 16, 15 ячеек первого столбца однородной структуры, принадлежащих массиву г элементов, граничных сигналов 2,=Ч=О, 2 д=1. Выполнение данной микро- операции аналогично предыдущим двум,30 Вщц=101, Вчет=000 Ан Хи в нА (Х55 3 12 б 09которые выполняются в двух массивахриг,Поиск ближайшего большего и ближайшего меньшего. Первой выполняетсямикрооперация поиска всех двоичныхслов А больших, меньших и равныхвходной переменной Х. Затем средибольших находят минимальное двоичное слово А а среди меньших максимальное двоичное слово А выполнением микрооперации поиска минимального и максимального элементов массива. Таким образом, за две микрооперации находятся ближайшие большее(А,) и меньшее (А ) к входной переменной Х двоичные слова А в массивеиз щ.Классификация чисел (определениепринадлежности входной переменнойХ интервалу). Если предположить,чтов нечетных строках однородной структуры хранятся нижние границы А, ав четных - верхние границы Ав интервалов, причем всегда А 3 А, то, выполняя микрооперацию поиска всех 25больших, меньших и равных элементовв строках однородной структуры относительно входной переменной Х, можно осуществлять операцию определения принадлежности входной переменной Х интервалу, В этом случаеанализируется результат операции -вектор В сразу в двух соседних строк ах, хр аня 1 цих один инт ерв а иА ,В =101; В, =001, для А (Х(АПри других комбинациях векторов В,В , входная переменная Х не попадает в интервалА, А 1, включая иего границы.Пересечение интервалов, Если пред положить так же, что в нечетныхстроках однородной структуры хранят. ся нижние границы А, а в четных -верхние границы А интервалов, то,выполняя микрооперацию разбиения массива строк однородной структуры намодмножества относительно границ интервалаХ, Х 3 1 входных переменных), можно определить пересечение интерваловХ, Х 1 иАч 50А 3. Вектор В на выходах строк однородной структуры анализируетсясразу в двух соседних строках, хранящих один интервалА, Аз 1 42 6А 1 П(Х ь Х 1 (Аню А) 1 (А, А )П Х, Х 1 "ф.Число ситуаций пересечений интерваловА, А ),Х, Х 1 легко расширить на случаи совпадения границ интервалов. Однородная структура, собранная на предлагаемых ячейках, обладает повьшенным быстродействием, так как позволяет выделять за одну микрооперацию элементы массива, попадающие в заданный числовой интервал, равные границам интервала, большие верхней границы интервала, меньшие нижней границы интервала. Кроме того, данная однородная структура дает возможность проводить поиск максимального или минимального элемента массируй, поиск максималь ного или минимального элементов в двух раздельных массивах одновременно, поиск всех больших, меньших и равных элементов массива по отношению к входной переменной Х, одновременный поиск ближайшего большего и ближайшего меньшего к входной переменной Х элементов массива за две микрооперации. Если положить, что в каждой паре соседних строк (нечетной, четной) хранятся соответственно нижние А и верхние Аб границы интерваловА , А, то однородная структура позволяет выполнять операцию классификации чисел, т.е. определять принадлежность входной переменной Х=Х=ХВ интервалам А, А 83, Х(А А), а также операцию нахождения пересечений интерваловА, А ), хранящихся в строках однородной структуры и входного интервала (Х, Хв), (А, А)П(Х, Х) причем устанавливается не только факт пересечения, но и все возможные виды пересечений. Формула изобретенияЯчейка однородной среды, содержащая первый, второй, третий и четвертый элементы И, первый, второй, третий элементы ИЛИ, первый элемент НЕ и триггер, причем первый информационный вход ячейки соединен с входом первого элемента НЕ, выход которого соединен с первым7входом первого элемента И, второй вход которого соединен с первым настроечным входом ячейки, а третий вход первого элемента И соединен с прямым выходом триггера, инверсный .выход которого соединен с первым входом второго элемента И, второй вход которого соединен с вторым информационным входом ячейки, второй настроечный вход которой соединен с третьим входом второго элемента И выход которого соединен с первым входом первого элемента ИЛИ; второй вход которого соединен с выходом первого элемента И, а третий вход первого элемента ИЛИ соединен с третьим настроечным входом ячейки, первый настроечный выход которой со динен с выходом первого элемента ИЛИ, о т л и ч а ю щ а я с я тем, что, с целью увеличения быстродейст вия ячейки, в нее введены второй элемент НЕ, пятый и шестой элементы И, элемент И-ИЛИ и коммутатор, причем вход записи ячейки соединен с первыми входами третьего и четверто го элементов И, вторые входы которых соединены с первым и вторым информационными входами ячейки соот ветственно, выходы третьего и четвертого элементов И соединены с ну левым и единичным входами триггера соответственно, прямой выход которо . го соединен с первым входом пятого элемента И, второй вход которого соединен с вторым настроечным.входом ячейки, третий настроечный вход которой соединен с входом второго 1260942 8элемента НЕ, выход которого соединенс третьим входом пятого элемента И,выход которого соединен с первымвходом второго элемента ИЛИ, второйвход которого соединен с третьиминформационным входом ячейки, четвертый информационный вход которойсоединен с первым входом третьегоэлемента ИЛИ, второй вход которого10 соединен с выходом шестого элементаИ, первый вход которого соединен спервым настроечным входом ячейки,второй вход шестого элемента И соединен с инверсным выходом триггера15 и первым входом элемента И-ИЛИ,второй вход которого соединен с вы-.ходом первого элемента НЕ, третийе- и четвертый входы элемента И-ИЛИсоединены с первым настроечным вхо 20 дом ячейки, первый информабионныйвход которой соединен с пятым входом элемента И-ИЛИ, шестой вход которого соединен с прямым выходомтриггера, а выход элемента И-ИЛИ25 является вторым настроечным вы - ходом ячейки, третий настроечныйвыход которой соединен с выходомкоммутатора, управляющие входы ко"торого соединены с инверсным выходомЗО триггера, вторым информационным итретьич настроечным входами ячейкисоответственно, информационные входы коммутатора соединены с вторымнастроечным входом ячейки, первый ывторой информационные выходыкоторой соединены с выходамивторого и третьего элементовИЛИ,1260942 а=Х Фиг Составитель 0 Техред А.Кра ерезиковак Корректо актор Т.Парфенов а Тираж б 71 Подп ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 3035, Москва, Ж, Раушская наб д, 4/5