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

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

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (511 4 G 06 F,7/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСКОМУ(СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР пО делАм изОБРетений и oTHpblTHA (21) 3889428/24-24, (22) 24. 04. 85 (46) 30.09.86. Бюл. Ф 36 (72) А,П.Мальппев и С 11.Окулов (53) 681.3(088.8) (56) Авторское свидетельство СССР

Ф 610105, кл. G 06 F 7/00, 1975, Авторское свидетельство СССР

9 851398, кл. G 06 F 7/00, 1979, Авторское свидетельство СССР

У 1013943, кл. G 06 F 7/00, 1982.

Фет Я.И. Параллельные процессоры для управляющих систем. M„:

Эневгоиздат, 1981; с. 41. (54) ЯЧЕЙКА ОДНОРОДНОЙ СРЕДЫ (57) Изобретение предназначено для использования в ассоциативных параллельных процессорах для обработки и преобразования структур данных, Цель изобретения — повьппение быстродействия за счет выделения в одной мик„„Я0„„1260942 А (рооперации элементов массива, попадающих в заданный числовой интервал, равных границам интервала, больших верхней границы интервала, меньших нижней границы интервала. Ячейка однофазной среды содержит триггер, шесть элементов И, два элемента НЕ, три элемента ИЛИ, элемент И-ИЛИ и коммутатор, Ячейка однородной среды выполняет следующие виды информационного поиска за одну микрооперацию: а) поиск элементов массива, попадающих в,заданный числовой интервал

Х, Х, равных границам интервала, HВ пЭ больших верхней границы интервала

Х, меньших нижней границы интервала Х 1 б) поиск максимального и мин нимального элементов в двух массивах; в) поиск всех больших, меньших, равных элементов массива по отношению ко входной переменной Х. 2 ил.

1260942

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

40 использовано в ассоциативных парал-. лельных процессах для обработки данных. S

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

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

Ячейка включает: элементы НЕ 1 и

2, элементы И 3-8; триггер 9, элементы ИЛИ 10-12, коммутатор 13, элемент И-ИЛИ 14, настроечные входы 15l7, вход записи 18, информационные ходы 19--22, настроечные выходы 2325„ информационные выходы 26-27.

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

num, где и - количество столбцов, а

m - количество строк.„ настроечные выходы 23-25 каждой ячейки соединяются с настроечными входами 17, 16, 15 соответственно соседней справа ячейки, а информационные выходы 26 и 27 — с информационными входами

29 и 19 соответственно соседней сни- 3S с зу ячейки. Информационные входы 21 и 22 являются общими для всех ячеек, образующих столбец, а вход записи

18 является общим для всех ячеек, образующих строку.

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

7. -Z Х vZ, анУ;И; (!) (2)

u ---!1 2, зХ„ К,аХ (3)

У, =-V, v Z, Ыа; (1!) (s) где а — состояние триггера 9 (разряд двоичного слова А= 50

9а 9 9а1 9

1 щего строку длиной и однородной структуры, старшими разрядами слева);

Х, Х вЂ” соответственно значения

Н разрядов нижней Х„={:;„, =-(Х,Х,...,Х „,) границ интервала подаваемые на информационные входы 21 и

22 ячеек однородной структуры, всегда Х >Х,;

Z,,Z,Ч вЂ” значения переменных на соответствующих настроечных входах 17, 15, 16 ячейки1

Е,,Е,Ч вЂ” значения переменных на соответствующих настроечных выходах 23, 25„ 24 ячейки;

Y,,Y — значения переменных на информационных входах 19 и 20 соответственно„

Y,,Y — значение переменньгх на информационных выходах 27 и

26 соответственно.

Входы У, и Y ячеек первой строки однородной структуры являются установочными и;на них постоянно подан сигнал "О".

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

Запись информации. Прямой код записываемого двоичного слова А подается поразрядно на входы 21, а инверсный код . — на входы 22 соответствующих столбцов однородной структуры. Одновременно на входы записи 18 всех ячеек выбранной строки подается сигнал записи, Считывание информации. Для выполнения считывания необходимо в каждом столбце однородной структуры соединить выход 26 (Y ) самой ниж2 ней ячейки через схему НЕ с входами

?? всек ячеек этого столбца, а выход

27 (У ) — с входами 21 всех ячеек этого столбца. Ячейка позволяет производить считывание информации одновременно из двух строк однород1 ной структуры на выходах У, и Y последней строки, причем на вьгходах

\ информация в инверсном коде. На

Я входы 17, 15, 16 крайнего левого столбца однородной структуры подаются граничные сигналы Z, =1, Z,=M=0 (выход у ) и Z M О, Z 1 (выход М ) для считываемых строк и граничные сигналы 7.,=7. =M=O или W=1 для остальных строк однородной структуры„

Разбиение массива из 1, двоичных слов А на подмножества, в которые входят А Х А Х„, Х„

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

1260942

В=001, B=101

В=000, В=100, В=010, А>Х >

Хн °

Х„ А Х,;

А=Х„;

А=Х

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

А, если положить Х„=Х =Х. На входы

17, 15, 16 всех ячеек первого столбца однородной структуры соответственно подаются граничные сигналы

30

Z,=Z =l, W=O,а, а на входы 21 и 22 ячеек каждого столбца поразрядно — значение Х.

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

В=001, В=101, В=110, А)Х;

А<Х;

А=Х.40

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

22 через схему НЕ всех ячеек того же столбца и с входами 21 всех ячеек gp того же столбца.

Существуют модификации этой микрооперации, Поиск минимального элемента в массиве из н двоичных слов А. На входы

17, 16, 15 всех ячеек первого столбца однородной структуры соответственно подаются граничные сигналы

Zi =W=O, Z, =1. Если а; =1, Х;=Î, l=левого) столбца однородной структуры соответственно подаются граничные сигна 21=2 2=1, W=O;Ô на входы

21 и 22 ячеек каждого столбца соответственно границы интервала X„, 5

Х, поразрядно, старшими разрядами слева. Каждая ячейка однородной среI 1 ды может изменять значения Z, Z

21

W на своих выходах (фиг. 2) в соответствии с выражениями (1) - (3) °

Таким образом, после окончания переходных процессов на выходах 23, 25, 24 ячеек последнего столбца однородной структуры появятся векI I тора признаков В=j2„,2,W j, которые указывают на принадлежность двоичных слов А одному из подмножеств

=1,n, то в цели 2 появляется сигнал

"О" и данная строка исключается из поиска. Ситуапия а, =О Х =! возник81 нуть не может, так как если Ь, -м столбце однородной структуры хотя бы в одной ячейке а.=О, то на входе

Э

22 всех ячеек столбца Х = У =О. ТогЬ 2 да после окончания переходных процессов на выходах 23, 25, 24 ячеек последнего столбца вектор В имеет следующие значения: B=01X Y двоичного слова А, имеющего минимальное значение в массиве из ni B=OOX Y всех остальных слов массива, где

Х вЂ” неанализируемое значение разряда.

На выходах 26 ячеек самой нижней строки находится инверсное значение минимального элемента в массиве из m, Поиск максимального элемента в массиве из ш двоичных слов А. На входы 17, !б 15 всех ячеек первого столбца однородной структуры соответственно подаются граничные сигналы Z„=l У=2 =О. Если а. =О; Х„; =1, ! то в цепи W йоявляется сигнал "1", который так же сохраняется в цепи

Z, и данная строка исключается из поиска. Ситуация а. =1; Х„, =О воэник1 нуть не может, так как если в i --м столбце однородной структуры хотя бы в одной ячейке а=l, то на входе

21 всех ячеек столбца Х„, = Y, =1 . Тогда после окончания переходных процессов на выходах 23, 25, 24 ячеек последнего столбца вектор В имеет следующие значения: B=100 у двоичного слова А, имеющего максимальное значение в массиве из m, B=101 у всех остальных слов массива. На выходах 27 ячеек самой нижней строки.. находится значение максимального элемента в массиве из m, Поиск максимального в массиве из р и минимального в массиве из r элементов, p+r=m.

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

Ч=2 =О. Поиск минимального элемента осуществляется подачей на входы 17, 16, 15 ячеек первого столбца однородной структуры, принадлежащих массиву r элементов, граничных сигналов

2,=И=O, 2д=1. Выполнение данной микрооперации аналогично предыдущим двум, 30

В .„=101, В„„=ООО, A (X, Хн А (Х, 55

5 12609 которые выполняются в двух массивах риг.

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

Х интервалу). Если предположить,что в нечетных строках однородной структуры хранятся нижние границы А„, а в четных — верхние границы А интервалов, причем всегда А >А, то, выполняя микрооперацию поиска всех 25 больших, меньших и равных элементов в строках однородной структуры относительно входной переменной Х, можно осуществлять операцию определения принадлежности входной переменной Х интервалу, В этом случае анализируется результат операции— вектор В сразу в двух соседних строках, хранящих один интервал (А„, А ); В =101; В „„=001, для А (Х<А

IIpH других 1 омбинациях Векторов В еч

В„„, входная переменная Х не попадает в интервал (А„, А 1, включая и его границы.

Пересечение интервалов. Если пред-40 положить так же, что в нечетных строках однородной структуры хранят. ся нижние границы А„, а в четных— верхние границы А интервалов, то, выполняя микрооперацию разбиения массива строк однородной структуры на модмножества относительно границ интервала (Х„, Х ) (входных переменных), можно определить пересечение интервалов f X Х l и (А ч 50

А 1, Вектор В на выходах строк однородной структуры анализируется сразу в двух соседних строках, хранящих один интервал (A„ AH) 42 6 (А„, А )П(Х„, Х )=(А„, А ); (А, А,)П (Х, Х81-ф.

Число ситуаций пересечений интервалов (А„, А ), (Х„, Х ) легко расширить на случаи совпадения границ интервалов. Однородная структура, собранная на предлагаемых ячейках, обладает повьш енным быстродействием, так как позволяет выделять за одну микрооперацию элементы массива, попадающие в заданный числовой интервал, равные границам интервала, большие верхней границы интервала, меньшие нижней границы интервала. Кроме того, данная однородная структура дает возможность проводить поиск максимального или минимального элемента массируй, поиск максималь. ного или минимального элементов в двух раздельных массивах одновременно, поиск всех больших, меньших и равных элементов массива по отношению к входной переменной Х, одновременный поиск ближайшего большего и ближайшего меньшего к входной переменной Х элементов массива за две микрооперации. Если положить, что в каждой паре соседних строк (нечетной, четной) хранятся соответственно нижние А„ и верхние Аб границы интервалов (А, А ), то однородная структура позволяет выполнять операцию классификации чисел, т.е. определять принадлежность входной переменной Х=Х„=ХВ интервалам fA»

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

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

7 входом первого элемента И, второй вход которого соединен с первым настроечным входом ячейки, а третий вход первого элемента И соединен с прямым выходом триггера, инверсный .выход которого соединен с первым входом второго элемента И, второй вход которого соединен с вторым информационным входом ячейки, второй настроечный вход которой соединен с третьим входом второго элемента И выход которого соединен с первым входом первого элемента ИЛИ; второй вход которого соединен с выходом первого элемента И, а третий вход первого элемента ИЛИ соединен с третьим настроечным входом ячейки, первый настроечный выход которой со динен с выходом первого элемента

ИЛИ, отличающаяся тем, что, с целью увеличения быстродейст вия ячейки, в нее введены второй элемент НЕ, пятый и шестой элементы

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

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

10 соединен с выходом шестого элемента

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

25 является вторым настроечным вы— ходом ячейки, третий настроечный выход которой соединен с выходом коммутатора, управляющие входы ко" торого соединены с инверсным выходом

ЗО триггера, вторым информационным и третьич настроечным входами ячейки соответственно, информационные входы коммутатора соединены с вторым нас-,роечным входом ячейки, первый ы второй информационные выходы которой соединены с выходами второго и третьего элементов

ИЛИ.

1260942

Фиг. 2

Составитель О.Березикова

Техред A.Êðàâ÷óê

Корректор M. Максимишинец, Редактор T.Ïàðôåíîâà

Заказ 5232/49

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

11 3035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4