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

СОКИ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 3(59 С 06 Е 2 00 НОМИТЕТ СССРТЕНИй И ОтНРЫтий ГОСУДАРСТВЕ ПО ДЕЛАМ И ННЫИЗОЬРЕОПИСАНИЕ ИЗОБРЕТ ИЯ АВТОРСЙ СВИДЕ ГЕЛЬСТВУ ены(71) Институт математики Сибирского отделения АН, СССР(56) 1.,Авторское свидЕтельство СССР 9 664169, кл. 6 06 Р 7/00, 19792. Авторское свидетельство СССР М 610105, кл. С 06 Р 7/00, 1978 (прототип ).(54)(57) ЯЧЕЙКА ОДНОРОДНОЙ СРЕДЫ, , содержащая триггер, пять элементов И и три элемента ИЛИ, причем первый вход ячейки соединен с первыми вхо-. дами первого й второго элементов И, второй входпервого элемента И под- . ключен к второму входу ячейки и первому входу первого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, первЬЫ входом четвертого элемента И и первым входом второго элемента ИЛИ, второй вход которого подключен к выходу пятого элемента И, первый вход. которого .соединен с третьим входом ячейки и первым входом третьего элемента И, второй вход пятого элемента И соединен с.четвертым входом ячейки, вторым входом четвертого элемента И и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера, единичный вход которого соединен с вы,.80,101 А ходом первого элемента И, а единичный выход - с вторым входом третьего элемента К, выход четвертого элемента И подключен: к. первому входу третьего элемента ИЛИ, второй вход которого соединен с пятым вхо; дом ячейки, а выходы первого, второ- . го и третьего элементов ИЛИ подключены соответственно к первому, второму и третьему выходам ячейки, о т л и ч а в щ а я с я . тем, что,: с целью расширения области применения путем обеспечения воэможности преобразования структур данных, в нее введены шестой, седьмой и восьмой элементы И, а также первей и второй элементы НЕ, причем первые вхо- Я ды шестого, седьмого и восьмого элементов И .подключены к третьему входу ячейки, вторые входы шестого, седьмого и восьмого элементов И соединены с шестым входом ячейки .и с входом первого элемента НЕ, выход Я которого подключен к третьим входам третьего к пятого элемейтов И, третий вход седьмого элемента И соединен с вторым входом ячейки и с вхо-" дом второго элемента НЕ, выход которого подклвчен к третьему входу восьмого элемента И, четвертый. вход: которого соединен с четвертым входоМ ячейки, а выходы шестого, садь и восьмого элементов И подклвч соответственно к третьим входам первого, второго и третьего элементов ИЛИ.1013943 10 Поставленная цель достигаетсятем, что ячейка однородной среды,содержащая триггер, пять элементовИ и три элемента ИЛИ, причем первыйвход ячейки соединен с первыми входами первого и второго элементов И,второй вход первого элемента И подключен ко второму входу ячейки ипервому входу первого элемента ИЛИ,20 второй вход которого соединен с выходом третьего элемента И, первымвходом четвертого элемента И и первым входом второго элемента ИЛИ,второй вход которого подключен к25 выходу пятого элемента И, первыйвход которого. соединен с третьимвходом ячейки и первым входом третьего элемента И; второй вход пятого элемента И соединен с четвертым30 входом ячейки, вторым входом четвертого элемента И и вторым входом второго элемента И, выход которогоподключен к нулевому входу триггера,единичный вход которого соединен с35 выходом первого элемента И, а единичный выход - со вторым входом третьего элемента И, выход четвертогоэлемента И подключен к первому вхо;ду третьего элемента ИЛИ, второй40 вход которого соединен с пятым входом ячейки, а выходы первого, второго и третьего элемента ИЛИ подключены соответственно к первому,второму и третьему выходам ячейки,дополнительно содержит шестой, седьмой и восьмой элементы И, первыйи второй элементы НЕ, причем первые входы шестого,седьмого и восьмого элементов И подключены к третьему входу ячейки, вторые входышестого; седьмого и восьмого элементов И соединены с шестым входомячейки и со входом первого элемен.та НЕ, выход которого подключен ктретьим входам третьего и пятого55 элементов И, третий вход седьмогоэлемента И соединен со вторым входом ячейки и со входом второго элемента НЕ, выход которого подключенк третьему входу восьмого элемента60 И, четвертый вход которого соединенс четвертым входом ячейки, а выходышестого, седьмого и восьмого элементов И подключены соответственнок третьим входам первого, второго65 и третьего элементов ИЛВ,Наиболее близкой к предлагаемой по технической сущности является ячейка однородной среды, содержащая триггер, пять элементов И и три элемента ИЛИ. Первый вход ячейки соединен с йервыми входами первого и второго элементов И. Второй вход первого элемента И подключен ко второму входу ячейки и первому входу первого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, первым входом четвертого элемента И и с первым входом второго элемента ИЛИ, второй вход которого подключен к выходу пятого элемента И, первый вход ко-. торого соединен с третьим входом ячейки и первым входом третьего элемента И, а второй вход - с четвертым входом ячейки, вторым входом четвертого элемента И и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера, единичный вход которого соединен с выходом первого элемента И, а единичный выход - со вторым входом третьего элемента И, выход четвертого элемента И пбдключен к первому входу третьего элемента ИЛИ, второй вход которого соединен с пятым входом ячейки. Выходы первого, второго и третьего элементов ИЛИ подключены соответственно к первому, второму и третьему выходам ячейки 2. Изобретение относится к цифровой вычислительной технике и предназначено для массовой параллельной обработки информации.Известна ячейка однороднойсреды, содержащая логические элементы И, ИЛИ и НЕ, Однородная структура, построенная из таких ячеек, выполняет ряд массовых операций преобразования структур данных (сжатие, расширение, взвешивание, определение .положения к-й единицы и т,д,).обеспечивая при этом высокую скорость перестройки 11.Недостатком этой структуры является то, что в ней не выполняются операции поиска информации. Однородная структура, построенная из таких ячеек, обеспечивает выполнение за одну команду следующих массовых информационно-логических операций: поиск максимального (минимального) элемента информации в массиве, разбиение массива на три подмножества, в первое из которых входят все элементы информации, совпадающие с заданным признаком,. во второе - все элементы, меньшие заданного признака, в третье - все элементы, большие заданного признака. Недостатком известной ячейкиоднородной среды является то, чтов структуре не выполняются операциипреобразования структур данных. Целью изобретения является расширение области применения путем обеспечения возможности преоб- разования структур данных при массовой параллельной обработке информации.1. Поиск максимального элемента.25Для выполнения этой операции элементы обрабатываемого массива должны быть предварительно записаны построкам (старшими разрядами слева)-З 0 в триггерах 12 однородной структуры,Если теперь в каждом столбце соединить через элемент НЕ выходы 8,и 9нижней ячейки и подать на входы 2всех ячеек левого столбца и на вхо 35 ды 3 всех ячеек верхней строки гра 1 ничные сигналы го = 1 и хо = 0 соответственно, то по окончании переходных процессов сигнал г = 1 на выходах 7 ячеек правого столбца уста 40 новится в тех строках, которые содержат максимальные элементы информации,На чертеже приведена лбгическая схема ячейки однородной среды.Ячейка имеет входы 1-6 переменных к, г, х, у, ч и ц соответственно и выходы 7-11 переменных г, х, у, ч и цсоответственно и содержит триггер 12 с входными элементами И 13 и 14, элементыИ. 15-20, элементы ИЛИ 21-23, а также элементы НЕ 24 и 25.В однородной структуре выходы 8 и 9 каждой ячейки соединены со входами 3 и 4 соседней по вертикали ячейки соответственно, а выходы 7, 10 и 11 - со входами 2, 5,и б соседней по горизонтали ячейки соответственно.Внутри каждой ячейки первые входы элементов И 15-20 соединены со входом 2, а вторые входы элементов И 18, 19 и 20 подключены ко входу 1. Второй вход элемента И 15 соединен с единичным выходом триггера 12, а второй вход элемента И 16 - с первыми входами элементов И 14 и 17, третьим входом элемента И 20, а также со входом 4 и выходом 9 ячейки. Третьи входы элементов И 15 и 16 соединены через элемент НЕ 24 со входом 1 ячейки. Третий .вход элемента И 19 соединен с первым входом элемента И 13, первым входом элемен та ИЛИ 21 и со входом 3 ячейки, который подКлючен также - через элемент НЕ 25 - к четвертому входу элемента И 20. Выход элемента И 16 соединен с первым входом элемента ИЛИ 22. Вторые входы элементов ИЛИ 2 и 22 и элемента И 17 подключены к выходу элемента И 15. Первый вход элемента ИЛИ 23 соединен с выходом элемента И 17, а второй его,вход - со входом 5 ячейки. Выходы элементов И 18, 19 и 20 подключены соответственно к третьим входам элементов ИЛИ 21, 22 и 23, выходы которых соединены соответственно с выходами 8, 7 и 10 ячейки. Вторые входы элементов И 13 и 14 соединены со входом б и выходом 11 ячейки.Ячейка однородной среды реализует функции:х = х ч гаГ ч гас ) (1) г = га 1 ч гурыч гх 1; (2) ,ч = ч ч гауКч гхуМ; (3) е= цх; (4)(5) где а - состояние триггера 12-;ц, ч - сигналы установки триггера 12 в "1" и "0"; управляющий сигнал навходе 1.Ячейка однородной среды работает следующим образом.функции (4) и (5) позволяют осуществить парафазную запись информа" ции в триггеры 12 однородной структуры. Для этого прямой код записываемого двоичного слова подается поразрядно на входы Э, а обратныйкод - на входы 4 соответствующих 5 столбцов однородной структуры. Одновременно на входы 6 всех ячееквыбранной строки подается импульсразрешения записи.Устройство может работать в раз .личных режимах, в зависимости от.значения управляющего сигнала М,Е режиме информационного поискана входы 1 всех ячеек однороднойструктуры подается управляющий сиг нал 3 с = О. Функции (1), (2).и (3)принимают вид:х = хчга;. (1)г = г(ачч) (2) 20 ч = ччгач. (Э)При этом, как известно из (2,.однородная структура обеспечиваетвыполнение следующих информационнологических операций. 2. Поиск минимального. элемента.Выполняется аналогично предыдущему, если все элементы массива записаны в триггерах 12 обратным кодом.3. Разбиение массива на три подмножества.50 для в ,олнения этой операции массив записывается так же, .как припоиске максимального элемента. Признак сравнения подается поразряднона входы 4 верхних ячеек соответст вующих столбцов в обратном коде.Если теперь подать на входы 2 и 5всех ячеек левого столбца граничныесигналы го = 1, чз = 0 соответственно, то по окончании переходных 60 процессов на выходах 7 и 10 ячеекправого столбца во всех строках,где содержатся элементы, большиезаданного признака, установятсясигналы ч = 1, меньшие заданного 65 признака - сигналы ч= О и гО, 1013943совпадающие с признаком - сигналыч=Он г =1.В режиме преобразования структур. данных на входы 1 всех ячеек однородной структуры подается управляющий сигнал К = 1. Функции (1), (2 ф) и (3) принимают видх хч г; (1)г = гх)ч = ччгку, (3 )Если при атом додать на входы 2 всех ячеек левого столбца произвольный двоичный вектор, а на входы 3всех ячеек верхней строки - граничные сигналы х оО, то в первом(левом) столбце одйородной структуры выделится (условием гх = 1)первая сверху единица исходногодвоичного вектора, во втором столбце - вторая его единица и т,д. Действительно, в первом (левом) . столбце согласно (1) переменная х сохраняет значение "Оф до тех пор, пока гО. В некоторой 1 -й ячейке,где впервые встречается г = 1, хменяет значение на "1 ф и сохраняет1" до нижней границы. Эначит, этоединственная ячейка первого столб-. ца, в которой выполняется условиеН 1. Горизонтальный канал г выделенной 1 -й ячейки в соответствииЛ1с(2 ) заперт сигналом хО, поэтому первая единица исходного двоичного вектора далее по горизонтали не распространяется. Во всех ячейках первого столбца, расположенных виже .1-й ячейки, х 1 и, следовательно, гг. Значит, на входы 2 второго столбца поступает копия исходного двоичного вектора за исключением его первой (верхней) единицы. Аналогичные преобразованияпроисходят во втором, третьем и . т,д. столбцах однородной структуры: в некоторой 1-й ячейке второго столбца выделяется (условием гх = 1) .вторая единица исходного вектора, в 1-й ячейке третьего столбца- третья единица и т.д, При этом, очевидно, 1 с 12 (13 (Рассмотренное свойство последовательного выделения очередных единиц и наличие функции (3". ) обеспечивают выполнение следующих операций преобразования структур данных.1. Расширение.Задача, которую решает устройство в этом случае, состоит в соединении а упорядоченных входных каналов с любой упорядоченной группой в выходных каналов (из общего числа и). Номера выходных каналов2 Зв (2 з п) к которым должны быть подключены входные каналы 1, 2, , щ, задаются и-разрядным двричным вектором,5О15 25 30 35 40 45 50 55 содержащим "1" в соответствующих разрядах (управляющий вектор). Этот вектор подается (поразрядно) на входы 2 ячеек левой границы однородной структуры. щ входных каналов подключаются поразрядно ко входам 4 ячеек верхней границы. На входы 5 ячеек левой границы подаются граничные сигналы чд = О, При этом в каждбй ячейке однородной структуры, где выполняется условие гх = 1, в соответствии с (3") имеет место Ч = у, т.е. происходит поворот сигнала из вертикального канала у в горизонтальный канал Ч. Очевидно, при этом на выходы 10 ячеек правой границы будут, направлены: в 1-й строке сигналы 1-го входного канала, в 1-й строке - сигналы 2-го входного кайала и т.д., что соответствует решаемой задаче.2. Сжатие. Эадача, которую решает устройство в этом случае, состоит в соединении любой упорядоченной группы входных каналов(из общего числа и) с щпоследовательными выходными каналами. Номера входных каналов 11(1. ( 1 (( 1,), которые должны быть подключены к выходным каналам 1,2я, задаются и-разрядным двоичным вектором, содержащим "1 ф в соответствующих разрядах. В данном случае этот управляющий вектор подается в обратном коде на входы 3 ячеек верхней границы однородной структуры. п входных каналов подключаются поразрядно ко входам 4 ячеек верхней границы. На входы 2 и 5 всех ячеек левой границы подаются соответственно граничные сигналы г = 1 и Чо = О, При этом вотех столбцах, где управляющий век-. тор содержит "0", х = 1. Эначйт, в этих столбцах не может быть ныделенных ячеек. Остальные столбцы ведут себя следующим образом. Пусть в управляющем векторе единицы расположены на 1-й, 1 -й и т.д. позициях. Так как ге = 1 условие гх = 1 согласно (1") и (2") возникает в 1-й слева ячейке 1-й строки, 12-й слева ячейке 2-й строки и т.д., следовательно, сигналы 1 -го, 1-го и т,д, входных каналов будут направлены на выходы 10 ячеек праной границы в 1-й, 2-й и т,д. строках, чтосоответствует решаемой н данном случае задаче. 3. Взвешивание (подсчет количества единиц н двоичном векторе). Вектор-аргумент подается в обратном коде .на входы 3 ячеек верхнейграницы. На все входы 2 ячеек лендйграницы и входы 4 ячеек верхней границы подаются соответственно граничные сигналы го = 1 и уо = 1. Если"Патент", г.ужгород,ул.Проектная ли в векторе-аргументе (который в данном случае служит управляющим вектором) содержится 0 единиц, то условие гх = 1 будет выполняться в точ- ности .в Р первых строках однородной структуры, Во всех остальных (расположенных ниже) строках условие гх = 1 возникнуть не может. Значит, сигналы у = 1 будут направлены в каналы ч только в первых В строках. Следовательно, выходы 10 ячеек правой границы образуют в данном случае шкалу, по которой отсчитывается вес (количество единиц) заданно-, го двоичного вектора.Таким образом, данная однородная структура имеет более широкую область применения по сравнению с известным устройством. Кроме того, поскольку в данной структуре выполняются операции ассоциативного поиска и параллельной записи, она может быть использована в качестве матрицы-накопителя параллельного ассоциативного процессора, т.е.обеспечивает эффективную реализацию всех известных алгоритмов ассоциа-.тивной обработки информации, в томчисле - массовых вычисленийПредлагаемая ячейка однороднойсреды позволяет строить на единойлогической и технологической основе решающие поля различных специализированных .и универсальных процессоров. Следовательно, интегральная схема, реализующая матрицу иэ 10 данных ячеек, может иметь большуюприменяемость, что является однимиз о .новных требований к современ-.ным БИС. 35 Дополнительным преимуществомявляется то, что расширение области применения достигается по-существу без увеличения:числа выводов - добавляется только вход 1 2 О управляюще:о сигнала И, общий длявсех ячеек данной БИС. В то же вре-мя значительно уменьшается отношение количества внешних выводовБИС к общему объему находящейся в 25 ней аппаратуры.