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

 

ЯЧЕЙКА ОДНОРОДНОЙ СРЕДЫ, содержащая триггер, пять элементов И и три элемента. ИЛИ , причём первый вход ячейки соединен с nepBfcB«iH вхо-дами первого и второго элементов И, второй вход первого элемента И подключен к второму входу ячейки и nep-i вому входу первого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, nepBfeA входом четвертого элемента И и первым входом второго элемента ИЛИ, второй вход которого подключен к выходу пятого элемента И, первый вход которого .соединен с третьим входом ячейки и первым входом третьего элемента И, второй вход пятого элемента И соединен с. четвертым входсм ячейки, вторым входом четвертого элемента И и вторым входом второго элемента И, выход которого подкдпочен к нулевому входу триггера, еди- . ничный вход которого соединен с выходом первого элемента И, а единичный выход - с вторь№4 ВХОДОМ третьег6 элемента И, выход четвертого элеьданта И подключен к. первому входу третьего элемента ИЛИ, второй вход которого соединен с пятым вхо. )гчейки, а выходы первого, второго и третьего элементов ИЛИ псдключёны соответственно к первому, второму и третьему выходам ячейки, О т л и ч а la щ а я с я тем, что, с целью расз(шрения области применения путем обеспечения возможности преобразования структур данных, в нее введены шестой, седьмой и восьмой элелюнты И, а также, первай и второй элементы НЕ, причём первые входы шестого, седьмого и восьмого элементов Л подключены к третьему входу ячейки/ вторые входы шестого, седьмого и восьмого элементов И соег динены с шестым входом ячейки и с входом первого элемента НЕ, которого подослючен к третьим входам тре тьего н пятого элементов И, третий вход седьмого элемента И соеди-; йен с BTOptei входсм ячейки }« с вхо-; .дом второго элемента НЕ, выход ко- DO торого подключен к третьему входу ; восьмого элемента И, четвертый.вход; со которого соединен с четверть вход( 4 ячейки, а выходы шестого, седьмого ;А9 и восьмого элементов И подключены собтветственно к третьим входам первого, второго и третьего элементов ИЛИ.

„„SU„„101 A

СОКИ СОВЕТСНИХ

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

РЕСПУБЛИК

3(59 G 06 F 7 00

k ь,"

ОПИСАНИЕ ИЗОБРЕТЕНИЯ - - ;:, :,. ;: (ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3378953/18-24 (22) 15. 01. 82 (46) 23.04.83, Бел, В 15 (72) Я.И. Фет (71) Институт математики Сибирского отделения АН, СССР (53) 681.3(088.8) (56) 1.,Авторское свидЕтельство СССР

Ф 664169, кл. G 06 F 7/00, 1979 °

2. Авторское свидетельство СССР

М 610105, кл. G 06 F 7/00, 1978 (прототип ).

К АВТОРСКОМУ СВИДЕ П=ЛЬСТВУ (54) (57) ЯЧЖЙКА ОДНОРОДНОЙ СРЕДЫ,, содержащая триггер, пять элементов

И и трн элемента ИЛИ, причем первый вход ячейки соединен с первыми вхо-. дами первого и второго элементов И, второй вход первого элемента И подключен к второму входу ячейки и первому входу первого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, первЬЫ входом четвертого элемента И и первым входом второго элемента ИЛИ, второй вход которого подключен к выходу пятого элемента И, первый вход которого .соединен с третьим входом ячейки и первым входом третьего элемента И, второй вход пятого элемента И соединен с.четвертым входом ячейки, вторым входом четвертого элемента И и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера, единичный вход которого соединен с выходом первого элемента И, а единичный выход - с вторым входом третьего элемента И, выход четвертого элемента И подключен: к. первому вхо ду третьего элемента ИЛИ, второй вход которого соединен с пятым вхо.дом ячейки, а выходы первого, второ- . го и третьего элементов ИЛИ подключены соответственно к первому, второму и третьему выходам ячейки, о т л и .ч а в щ а я с я тем, что,: с целью расширения области применения путем обеспечения возможности преобразования структур данных, в нее введены шестой, седьмой и восьмой элементы И, а также первай и второй элементы НЕ, причем первые вхо- Я ды шестого, седьмого и восьмого элементов И .подключены к третьему входу ячейки, вторые входы шестого, седьмого и восьмого элементов И соединены с шестым входом ячейки .и с входом первого элемента НЕ, выход Я которого подключен к третьим входам третьего к пятого элемейтов И, третий вход седьмого элемента И соединен с вторым входом ячейки и с вхо-" дом второго элемента НЕ, выход которого подключен к третьему входу восьмого элемента И, четвертый. вход-: которого соединен с четвертым входоМ ячейки, а выходы шестого, седьмого-- и восьмого элементов И подключены соответственно к третьим входам первого, второго и третьего элементов ИЛИ.

1013943

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

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

И, ИЛИ и HE. Однородная структура, построенная из таких ячеек, выполняет ряд массовых операций преобразования структур данных (сжатие, расширение, взвешивание, определение -положения к-й единицы и т.д.),. .обеспечивая при этом высокую скорость перестройки (1 ).

Недостатком этой структуры является то, что в ней не выполняются операции поиска информации.

Недостатком известной ячейки однородной среды является то, что в структуре не выполняются операции преобразования структур данных.

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

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

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

ИЛИ подключены соответственно к первому, второму и третьему выходам ячейки (2).

Однородная структура, построенная из таких ячеек, обеспечивает выполнение за одну команду следующих массовых информационно-логических операций: поиск максимального (минимального) элемента информации в массиве, разбиение массива на три подмножества, в первое из которых входят все элементы информации, совпадающие с заданным признаком,. во второе — все элементы, меньшие заданного признака, в третье — все элементы, большие заданного признака.

Поставленная цель достигается тем, что ячейка однородной среды, содержащая триггер, пять элементов

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

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

35 выходом первого элемента И, а единичный выход — со вторым входом третьего элемента И, выход четвертого элемента И подключен к первому вхо;ду третьего элемента ИЛИ, второй

40 вход которого соединен с .-.ятым входом ячейки, а выходы первого, второго и третьего элемента ИЛИ подключены соответственно к первому, второму и третьему выходам ячейки, дополнительно содержит шестой, седьмой и восьмой элементы И, первый и второй элементы НЕ, причем »ервые входы шестого, седьмого и .восьмого элементов И подключены к третьему входу ячейки, вторые входы шестого; седьмого и восьмого элементов И соединены с шестым входом ячейки и со входом первого элемен.та НЕ, выход которого подключен к третьим входам третьего и пятого

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

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

1013943

1. Поиск максимального элемента.

Для выполнения этой операции элементы обрабатываемого массива должны быть предварительно записаны по строкам (старшими разрядами слева)

-З0 в триггерах 12 однородной структуры.

Если теперь в каждом столбце соединить через элемент НЕ выходы 8,и 9 нижней ячейки и подать на входы 2 всех ячеек левого столбца и на вхоЗ5 ды 3 всех ячеек верхней строки гра1 ничные сигналы z = 1 и хо = О соответственно, то по окончании переходных процессов сигнал z = 1 на выходах 7 ячеек правого столбца уста40 новится в тех строках, которые содержат максимальные элементы информации.

На чертеже приведена лбгическая схема ячейки однородной среды.

Ячейка имеет входы 1-6 переменных k, z, х, у, v и и соответственно и выходы 7-11 переменных z, х, у, v и u соответственно и содержит триггер 12 с входными элементами И 13 и 14, элементы И. 15-20, элементы ИЛИ 21-23, а также элементы НЕ 24 и 25„.

В однородной структуре выходы 8 и 9 каждой ячейки соединены со входами 3 и 4 соседней по вертикали ячейки соответственно, а выходы

7, 10 и 11 — со входами 2, 5.и 6 соседней по горизонтали ячейки соответственно.

Внутри каждой ячейки первые входы элементов И 15-20 соединены со входом 2, а вторые входы элементов

И 18, 19 и 20 подключены ко входу 1.

Второй вход элемента И 15 соединен с единичным выходом триггера 12, а второй вход элемента И 16 — с первыми входами элементов И 14 и 17, третьим входом элемента И 20, а также со входом 4 и выходом 9 ячейки. Третьи входы элементов И 15 и 16 соединены через элемент НЕ 24 со входом 1 ячейки. Третий вход элемента И 19 соединен с первым входом элемента И 13, первым входом элемен та ИЛИ 21 и со входом 3 ячейки, который подКлючен также — через эле- . мент HE 25 — к четвертому входу элемента И 20. Выход элемента И 16 соединен с первым входом элемента

ИЛИ 22. Вторые входы элементов ИЛИ 2 и 22 и элемента И 17 подключены к выходу элемента И 15.-Первый вход элемента ИЛИ 23 соединен с выходом элемента И 17, а второй его .вход— со входом 5 ячейки. Выходы элементов И 18, 19 и 20 подключены соот ветственно к третьим входам элементов ИЛИ 21, 22 и 23, выходы которых соединены соответственно с выходами

8, 7 и 10 ячейки. Вторые входы элементов И 13 и 14 соединены со входом 6 и выходом 11 ячейки.

Ячейка однородной среды реализует функции: х = xvzak vzk) (1)

2 = а ч zyk v zxk; (2) ,ч = v ч кауКч zxóÌ; (3) . с „= их; (4)

ыу (5) где а — состояние триггера 12-;

qz, е — сигналы установки триггера 12 в "1" и "О";

k управляющий сигнал на входе 1.

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

Функции (4) и (5) позволяют осуществить парафазную запись информации в триггеры 12 однородной структуры. Для этого прямой код записываемого двоичного слова подается поразрядно на входы 3, а обратный код — на входы 4 соответствующих столбцов однородной структуры. Одновременно на входы 6 всех ячеек выбранной строки подается импульс разрешения записи.

Устройство может работать в раз10 личных режимах, в зависимости от .

I .значения управляющего сигнала k.

Е режиме информационного поиска .на входы 1 всех ячеек однородной структуры подается управляющий сиг15 нал k = О. Функции (1), (2) и (3) принимают вид:

x = xvza (1)

z — z (à ч ч) г (2)

20 Ч = vvzay ° (3)

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

2. Поиск минимального. элемента. Выполняется аналогично предыду45 щему, если все элементы массива за писаны в триггерах 12 обратным кодом.

3. Разбиение массива на три подмножества.

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

Если теперь подать на входы 2 и 5 всех ячеек левого столбца граничные сигналы z = 1, чз = О соответственно, -.o по окончании переходных

60 процессов на выходах 7 и 10 ячеек правого столбца во всех строках, где содержатся элементы, большие заданного признака, установятся сигналы v = 1, меньшие заданного

65 признака — сигналы v = О и z О, 1013943 совпадающие с признаком — сигналы

v =Оиг =1.

В режиме преобразования структур. данных на входы 1 всех ячеек однородной структуры подается управляющий сигнал К = 1. Функции (1 ), (2 ) и (3 ) принимают вид: х xv z; (1)

z = zx

v = vvzxy,. (3 )

Если при атом додать на входы 2 всех ячеек левого столбца произвольный двоичный вектор, а на входы 3 всех ячеек верхней строки — граничные сигналы х д О, то в первом (левом) столбце одйородной структуры выделится (условием zx = 1) первая сверху единица исходного двоичного вектора, во втором столбце - вторая его единица и т.д. Действительно, в первом (левом) . столбце согласно (1) переменная х сохраняет значение "О" до тех пор, пока z О. В некоторой i -й ячейке, где впервые встречается z = 1, х меняет значение на "1" и сохраняет

"1" до нижней rpaницы. Эначит, это единственная ячейка первого столб-. ца, s которой выполняется условие

zR 1. Горизонтальный канал г выделенной i -й ячейки в соответствии

Л

1 с(2 ) заперт сигналом х О, поэтому первая единица исходного двоич ного вектора далее по горизонтали не распространяется. Во всех ячейках первого столбца, расположенных ниже .i„-й ячейки, х 1 и, следовательно, z z. Значит, на входы 2 второго столбца поступает копия исходного двоичного вектора за исключением его первой (верхней) единицы. Аналогичные преобразования происходят so втором, третьем и . т.д. столбцах однородной структуры: в некоторой i -й ячейке второго столбца выделяется (условием zx = 1) .вторая единица исходного вектора, в i>-й ячейке третьего столбцатретья единица и т.д. При этом, очевидно, i„c i 2 (13 (...

Рассмотренное свойство последовательного выделения очередных единиц и наличие функции (3 ". ) обеспе1 чивают выполнение следующих операций преобразования структур данных.

1. Расширение.

Задача, которую решает устройство в этом случае, состоит в соединении m упорядоченных входных каналов с любой упорядоченной группой

m выходных каналов (из общего числа и). Номера выходных каналов

2 3 Ф (1 2 3 п )

1 t к которым должны бйть йодключены входные каналы 1, 2, ..., m„ задаются п»разрядным двоичным вектором, J

5 !

О

55 ницы подаются соответственно граничные сигналы гд = 1 и yo = 1. Если содержащим "1" н соответствующих разрядах (упранляющнй вектор). Этот вектор подается (поразрядно) на входы 2 ячеек левой границы однородной структуры. m входных кана лов подключаются поразрядно ко входам 4 ячеек верхней границы. На входы 5 ячеек левой границы подаются граничные сигналы vä = О. При этом н каждбй ячейке однородной структуры, где выполняется условие

zx = 1, в соответствии с (3") имеет место U = у, т.е. происходит поворот сигнала из вертикального канала у в горизонтальный канал U. Очевидно, при этом на выходы 10 ячеек правой границы будут, направлены: в i-й строке сигналы 1-го входного

4 канала, в i -й строке — сигналы 2-го входного кайала и т.д., что соответствует решаемой задаче.

2. Сжатие.

Эадача, которую решает устройство в этом случае, состоит н соединении любой упорядоченной группы входных каналов (из общего числа n) с m последовательными выходными каналами. Номера входных каналов (i (1<(... (1„,), которые должны быть подключены к выходным каналам 1,2,...,m, задаются и-разрядным двоичным вектором, содержащим "1" в соответствующих разрядах.

В данном случае этот управляющий вектор подается в обратном коде на входы 3 ячеек верхней границы однородной структуры. п входных каналов подключаются поразрядно ко входам

4 ячеек верхней границы. На входы

2 и 5 всех ячеек леной границы подаются соответственно граничные сигналы z = 1 и Uо = О. При этом в о тех столбцах, где управляющий век-. тор содержит "О", х = 1. Эначйт, в этих столбцах не может быть ныделенных ячеек. Остальные столбцы ведут себя следующим образом. Пусть н управляющем векторе единицы расположены на i -й,„ i -й и т.д. позициях. Так как z = F условие гх = 1 согласно (1" ) и (2") возникает в

i é слева ячейке 1-й строки, iy-й слева ячейке 2-й строки и т.д., следовательно, сигналы i „-rо, iy-ro и т.д. входных каналов будут направлены на выходы 10 ячеек праной границы в 1-й, 2-й и т. д. строках, что соответствует решаемой н данном случае задаче.

3 ° Взвешивание (подсчет количества единиц н двоичном векторе).

Вектор-аргумент подается н обратном коде .на входы 3 ячеек верхней границы. На нсе входы 2 ячеек леной границы и входы 4 ячеек верхней граВНИИПИ Заказ 3018/57 Тираж 704 Подписное

Филиал ППП "Патент", г.ужгород,ул.Проектная,4 в векторе-аргументе (который в данном случае служит управляющим вектором) содержится 0 единиц, то условие zx = 1 будет выполняться в точ- ности .в Р первых строках однородной структуры. Во всех остальных (расположенных ниже) строках условие

zx = 1 возникнуть не может. Значит, сигналы у = 1 будут -направлены в каналы v только в первых В строках.

Следовательно, выходы 10 ячеек пра вой границы образуют в данном случае шкалу, по которой отсчитывается вес (количество единиц) заданно-, го двоичного вектора.

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

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

10 данных ячеек, может иметь большую применяемость, что является одним из о .новных требований к современ-. ным БИС.

35 Дополнительным преимуществом является то, что расширение области применения достигается по-существу без увеличения:числа выводов - добавляется только вход 1

2О управляюще:о сигнала k, общий для всех ячеек данной БИС. В то же вре-

-мя значительно уменьшается отношение количества внешних выводов

БИС к общему объему находящейся в ней аппаРатуРы.