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

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

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

На фиг 1 приведена функциональная схема предлагаемой ячейки од- - нородной средыj на фиг, 2 - график изменения значений сигналов 7 , Z,, W.

Ячейка включает: элементы НЕ 1 и 2j. элементы И 3-8; триггер 9j эле- менты ИЛИ 10-12, коммутатор 13, элемент И-ИЛИ 14 настроечные входы 15 17, вход записи 18, информационные входы 19-22s настроечные выходы 23- 25s информационные вькоды 26-27,

При формировании из предлагаемых ячеек однородной структуры разгаром nxrrij где п - количество столбцов5 а m - количество строкj настроечные выходы 23-25 каждой ячейки соединя- ются с настроечными входами 17, 16, 15 соответственно соседней справа ячейки, а информационные выходы 26 и 27 - с информационными входами 29 и 19 соответственно соседней сни зу ячейки. Информационные .входы 2 и 22 являются общими для всех ячеек образующих столбец, а вход записи 18 является общим для всех ячеек j, образующих строку,

Предлагаемая ячейка однородной среды реализует функции:

,,vZ-ivZ,-W;(1)

z;-Z.,.aXsVZ,.,5Xg;(2)

, aXnVZ aX ;, (3)

Y;-Y, vZ, Wa;(k)

Y;.V,vZ,i;(5)

где a состояние триггера 9 (разряд двоичного слова А {а ,a,j,...,, занимающего строку длиной п однородной структуры, старшим разрядами слева);

Хц - соответственно значения разрядов нижней , XH,...,XKH) и верхней Х (Xg,X8,..-,,XgJ границ,

0

5

интервала, подаваемые на информационные входы 21 и 22 ячеек однородной структуры, всегда Z ,Z,W - значения переменных на

соответствз тощих настроечных входах 17, 15, 16 ячейки;

Z,,Z,j,W - значения переменных на со ответствующих настроечных выходах 23, 25, 24 ячейки; Y, ,Y - значения переменных на

информационных входах 19 и 20 соответственно; -У, ,У - значение переменных на информационных выходах 27 и 26 соответственно Входы Y и Y ячеек первой стро-. ки однородной структуры являются установочными Илна них постоянно подан сигнал О.

Ячейка однородной среды при выполнении микроопераций работает следующим образом.

Запись информации. Прямой код записываемого двоичного слова А подается поразрядно на входы 2 а инверсный код -- на входы 22 соответствующих столбцов однородной структуры. Одновременно на входы записи 18 всех ячеек выбранной строки подается сигнал записи,

Считывание информации. Для выполнения считывания необходимо в каждом столбце однородной структуры соединить выход 26 (Y ) самой нижней ячейки через схему НЕ с входа -ш 22 все« ячеек этого столбца, а выход 27 (Y ) - с входами 21 всех ячеек этого столбца. Ячейка позволяет производить считьюание информации одновременно из двух строк однородной структуры на вЕзгходах Y и Y последней строки, причем на выходах У информация в инверсном коде На входы-17, 15, 16 крайнего левого столбца однородной структуры подаются граничные сигналы Z,1, Z, (выходу ) и Z,, Z,, 1 (выход V ) для считываемых строк и граничные сигналы Z, или для остальных строк однородной структуры, Разбиение массива из m двоичных слов А на подмножества, в которые

55 входят , , , ,, ,

В этом случае на входы 17, 15 и 16 всех ячеек первого (крайнего

левого) столбца однородной структуры соответственно подаются граним- ные сигналы на входы 21 и 22 ячеек каждого столбца соответственно границы интервала Х„, X., поразрядно, старшими разрядами слева. Каждая ячейка однородной среды может изменять значения Z , ZJ, W на своих выходах (фиг. 2) в соответствии с выражениями (1)-(3).

Таким образом, после окончания переходных процессов на выходах 23, 25, 24 ячеек последнего столбца однородной структур появятся вектора признаков jZ,j,W } , кото- рые указывают на принадлежность двоичных слов А одному из подмножеств

6 н

, -

Поиск всех больших, меньших и равных сводится к предыдущему раз- биению массива из t-n двоичных слов А, если положить , На входы 7, 15, 16 всех ячеек первого столбца однородной структуры соответст- венно подаются граничные сигналы

Z,, ,a,

а на входы 21 и 22 ячеек каждого столбца поразрядно - значение X. Тогда после окончания переходш 1Х про цессов на выходах 23, 25, 24 ячеек последнего столбца вектор В имеет следующие значения:

, , ,

Поиск минимального и максимального элементов массива. Для выполнения этой микрооперации необходимо в каж- 45 дом столбце однородной структуры выходы 26 и 27 самой нижней ячейки соединить соответственно с входами 22 через схему НЕ всех ячеек того же столбца и с входами 21 всех ячеек зо того же столбца.

Существуют модификации этой микрооперации.

Поиск минимального элемента в массиве из W1 двоичных слов А На входы 55 17, 16, 15 всех ячеек первого столбца однородной структуры соответственно подаются граничные сигналы , Z,. Если , Х.0; 1

5

5

20

25 30

5

0

5 о

5

1,п, то в цепи Z 2 появляется . сигнал О и данная строка исключается из поиска, Ситуапия а. 0, Х 1 возникнуть не может, так как если Ь,-м столбце однородной структуры хотя бы в одной ячейке а.0, входе 22 всех ячеек столбца - да после окончания переходных процессов на выходах 23, 25, 24 ячеек последнего столбца вектор В имеет следующие значения: Y двоичного слова А, имеющего минимальное значение в массиве из vn, Y всеу остальных слов массива, где X - неанализируемое значение разряда. На выходах 26 ячеек самой нижней строки находится инверсное значение минимального элемента в массиве из т..

Поиск максимального элемента в массиве из m двоичных слов А. На входы 17, 6, 15 всех ячеек первого столбца однородной структурь соответственно подаются граничные сигна лы , . Если а. 0; Х, 1 , то в цепи W появляется сигнал I, который так же сохраняется в цепи Z и данная строка исключается из поиска. Ситуация а.1; возникнуть не может, так как если в i -м столбце однородной структуры хотя бы в одной ячейке , то на входе 21 всех ячеек столбца , Тогда после окончания переходных процессов на выходах 23, 25, 24 ячеек последнего столбца вектор В имеет следующие значения: у двоичного слова А, имеющего максимальное значение в массиве из т, у всех остальных слов массива. На выходах 27 ячеек самой нижней строки- находится значение максимального

элемента в массиве из т.

Поиск максимального в массиве из р и минимального в массиве из г элементов, .

Поиск максимального элемента осуществляется подачей на входы 17, 16, 15 ячеек первого столбца однородной структуры, принадлежащих массиву р элементов, граничных сигналов , . Поиск минимального элемента осуществляется подачей на входы 17, 16, 15 ячеек первого столбца однородной структуры, принадлежащих массиву г элементов, гранич1п 1х сигналов Z,, . Вьшолнение данной микрооперации аналогично предьадущим двум.

оторые вьтолняются в двух массивах иг.

Поиск ближайшего большего и блиайшего меньшего. Первой выполняется икрооперация поиска всех двоичных слов А больших, меньших и равных ходной переменной X. Затем среди больших находят минимальное двоичное слово А , а среди меньших максимальное двоичное слово А/ выпол- JQ нением микрооперации поиска минимального и максимального элементов массива. Таким образом, за две микрооперации находятся ближайшие большее (А,) и меньшее (1) к входной пере- j менной X двоичные слова А в массиве из m.

Классификация чисел (определение принадлежности входной переменной X интервалу). Если предположить,что 20 в нечетных строках однородной структуры хранятся нижние границы А, а в четных - верхние границы А интервалов, причем всегда , то, выполняя микрооперацию поиска всех 25 больших, меньших и равных элементов в строках однородной структуры относительно входной переменной X, можно осуш;ествлять операцию определения принадлежности входной пере- jg менной X интервалу. В этом случае анализируется результат операции - вектор В сразу в двух соседних строках, храняй1их один интервал А„, Ag3i , В,,, 001, для . При других комбинациях векторов , , входная переменная X не попадает в интервал А, Ац1, включая и его границы.

Пересечение интервалов. Если предположить так же, что в нечетных строках однородной структуры хранятся нижние границы А, а в четных - верхние границы А интервалов, то, выполняя микрооперацию разбиения массива строк однородной структуры на модмножества относительно границ интервала Х„, Xg3 (входных переменных), можно определить пересечение интервалов Хц, Хц1 и А,,, Agl. Вектор В на выходах строк однородной структуры анализируется сразу в двух соседних строках, хра- няш;их один интервал А, Agl

В«ч 101, В,,,000, ,, СА„, AglntX,, , А,1; Вне,000, В,, , А Хд, А„, ,,Х,1Ан, Xgl;

, В,,,001, А,/Х„, А, А,, Х,Х„, XJ, , В,, ,, А„, ,, Х,1А„,

неч

101, В 101, , А,Х, и

В,

В,, В,,,001, ,

А,, AjntX, Xj-ф.

Число ситуаций пересечений интервалов А, Ац , Х|,, Х легко расширить на случаи совпадения границ интервалов. Однородная структура, собранная на предлагаемЕ тх ячейках, обладает повьшшнным быстродействием, так как позволяет выделять за одну микрооперацию элементы массива, попадаюшле в заданный числовой интервал, равные границам интервала, большие верхней границы интервала, меньшие нижней границы интервала. Кроме того, данная однородная структура дает возможность проводить поиск максимального или минимального элемента массив, поиск максимального или минимального элементов в двух раздельных массивах одновременно, поиск всех больших, меньших и равных элементов массива по отношению к входной переменной X, одновременный поиск ближайшего большего и ближайшего меньшего к входной переменной X элементов массива за две микрооперации„ Если положить, что в каждой паре соседних строк (нечетной, четной) хранятся соответственно нижние А и верхние А границы интервалов А, Ац, то однородная структура позволяет вьшолнять операцию классификации чисел, т.е. определять принадлежность входной переменной интервалам f А„, Ag, , Agi, а также операцию нахождения пересечений интервалов А, Agl, хранящихся в строках однородной структуры и входного интер- вала Х„, Xel, А,, , Xj, причем устанавливается не только факт пересечения, но и все возможные виды пересечений.

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

Ячейка однородной среды, содер- жаш;ая первый, второй, третий и чет- вертый элементы И,, первьй, второй, третий элементы ИЛИ, первой элемент НЕ и триггер, причем первьй информационный вход ячейки соеди- нен с входом первого элемента НЕ, выход которого соединен с первым

7

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

609428

элемента НЕ, выход которого соединеЧ с третьим входом пятого элемента И, выход которого соединен с первым входом второго элемента ИЛИ, второй 5 вход которого соединен с третьим информационным входом ячейки, четвертый информационный вход которой соединен с первым входом третьего элемента ИЛИ, второй вход которого

10 соединен с выходом шестого элемента И, первый вход которого соединен с первым настроечным входом ячейки, второй вход шестого элемента И соединен с инверсным выходом триггера

t5 и n fiBbiM входом элемента И-ИЛИ,

второй вход которого соединен с вы-: ходом первого элемента НЕ, третий и четвертый .в ходы элемента И-ИЛИ соединены с первым настроечным вхо20 дом ячейки, первый инфо рма5ионный вход которой соединен с пятым входом элемента И-ИЯИ, шестой вход которого соединен с прямым выходом триггера, а выход элемента И-ИЛИ

25 является вторым наст зоечным выходом ячейки, третий настроечный выход которой соединен с выходом ко -шутатора, управляюш 1е входы которого соединень с инверсным выходом

30 триггера, вторым информационным и третьим настроечным входами ячейки соответственно, зтаформационные входы коммутатора соединены с вторым настроечным входом ячейки, первый и

35 второй информационные выходы которой соединены с выходами второго и третьего элементов ШИ.

Изобретение предназначено для использования в ассоциативных параллельных процессорах для обработки и преобразования структур данных. Цель изобретения - повышение быстродействия за счет выделения в одной микрооперации элементов массива, попадающих в заданный числовой интервал, равных Границам интервала, больших верхней границы интервала, меньших нижней границы интервала. Ячейка однофазной среды содержит триггер, шесть элементов И, два элемента НЕ, три элемента ИЛИ, элемент И-ИЛИ и коммутатор. Ячейка однородной среды выполняет следующие виды информационного поиска за одну микрооперацию: а) поиск элементов массива, попадающих в i заданный числовой интервал Х, Xg, равных границам интервала, больших верхней границы интервала Xg, меньших нижней границы интервала Х j б) поиск максимального и минимального элементов в двух массивах; в) поиск .всех больших, меньших, равных элементов массива по отношению ко входной переменной X. 2 ил. (р (Л го О5 о 4 ю

fM.1

Фиг. 2