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

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

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

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

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

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

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

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

Поставленная цель достигается тем, что ячейка однородной среды, содержащая триггер, пять элементов И и три элемента ИЛИ, причем первый вход ячейки соединен с первыми входами первого и второго элементов И, второй вход первого элемента И подключен ко второму входу ячейки и первому входу первого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, первым входом четвертого элемента И и первым входом вт орого элемента ИЛИ, второй вход которого подключен к выходу пятого элемента И, первый вход которого.соединен с третьим входом ячейки и первым входом третьего элемента И; второй вход пятого элемента И соединен с четвертым входом ячейки, вторым входом четвертого элемента И и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера единичный вход которого соединен с выходом первого элемента И, а единичный выход - со вторым входом третьего элемента И, выход четвертого элемента И подключен к первому входу третьего элемента ИЛИ, второй вход которого соединен с пятым входом ячейки, а выходы первого, второго и третьего элемента ИЛИ подключены соответственно к nepBOMY, второму и третьему выходам ячейки, дополнительно содержит шестой, седьмой и восьмой элементы И, первый и второй элементы НЕ, причем первые входы шестого,седьмого и -восьмого элементов И подключены к третьему входу ячейки, вторые входы шестого-, седьмого и восьмого элементов и соединены с шестым входом ячейки и со входом первого элемен.та НЕ, выход которого подключен к третьим входам третьего и пятого элементов И, третий вход седьмогоэлемента И соединен со вторым входом ячейки и со входом второго элемента НЕ, выход которого подключен к третьему входу восьмо.го элемента И, .четвертый вход которого соединен с четвертым входом ячейки, а выходы шесто1о, седьмого и восьмого элементов И подключены соответственно к третьим входам первого, второго и третьего элементов ИЛИ. На чертеже приведена логическая схема ячейкл однородной среды. Ячейка имеет входы 1-6 переменных k, Z, X, у, V и U соответствен но и выходы 7-11 переменных z, х , у , v и и соответственно и содержит триггер 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 и 1 соединены через элемент НЕ 24 со входом 1 ячейки. Третий .вход элемен та И 19 соединен с первым входом элемента И 13, первым входом элеме те ИЛИ 21 и со входом 3 ячейки, который подключен также - через элемент НЕ 25 к четвертому входу эле мента И 20. Выход элемента И 16 сое динен с первым входом элемента ИЛИ 22. Вторые входы элементовИЛИ и 22 и элемента И 17 подключены к выходу элемента И 15.-Первый вход элемента ИЛИ 23 соединен с выходом элемента И 17, а второй его .вход со входом 5 ячейки. Выходы элементов И 18, 19 и 20 подключены соответственно к третьим входам элемен тов ИЛИ 21, 22 и 23, BHXojDtbJ которых соединены соответственно с выходами 8, 7 и 10 ячейки. Вторые входы элементов И 13 и 14 соединены со входом 6 и выходом 11 ячейки. Ячейка однородной среды реализу ет функции: X V zak V zk ; Z zak V zyk v zxk; v vvzaykvzxyk; (4) q ux; (5) Чо У - состояние триггера 12 4-1 Яп сигналы установки три ° гера 12 в 1 и k - управляющий сигнал иа входе 1. . Ячейка однородной среды работае следующим образом. Функции (4) и (5) позволяют осу ществить парафазную запись информа ии в триггеры 12 однородной струкуры. Для этого прямой код записыаемого двоичного слова подается поазрядно на входы 3, а обратный од - на входы 4 соответствующих толбцов однородной структуры. Од- овременно на входы 6 всех ячеек ыбранной строки подается импульс азрешения записи. Устройство может работать в различных режимах, в зависимости от значения управляющего сигнала k. С режиме информационного поиска на входы 1 всех ячеек однородной структуры подается управляющий сигнал k 0. Функции (1), (2) и (3) принимают вид: х xvza J z (а V v) ; v vvzav . При этом, как известно из (2}, однородная структура обеспечивает выполнение следующих информационнологических операций. 1.Поиск максимального элемента. Для выполнения этой операции элементы обрабатываемого массива должны быть предварительно записаны по строкам (старшими разрядами слева) в триггерах 12 однородной структуры. Если теперь в каждом столбце соединить через элемент НЕ выходы 8, и 9 нижней ячейки и подать на входы 2 всех ячеек левого столбца и на входы 3 всех ячеек верхней строки граничные сигналы Zg 1 ихд О соответственно, то по окончании переходных процессов сигнал z 1 на выхода.х 7 ячеек правого столбца установится в тех строках, которые содержат максимальные элементы информации . 2.Поиск минимального элемента ; Выполняется аналогично предыду1цему, если все элементы массива за;писаны в триггерах 12 обратным ко-дом. 3.Разбиение массива на три подмножества. Для выполнения этой операции массив записывается так же, как при поиске максимального элемента. Признак сравнения подается поразрядно на входы 4 верхних ячеек соответствующих столбцов в обратном коде. Если теперь подать на входы 2 и 5 всех ячеек левого столбца граиичиые сигналы ZQ 1 , VQ О соответственно, то по окончании переходных процессов на выходах 7 и 10-ячеек правого столбца во всех строках, где содержатся элементы, большие заданного признака, установятся сигналы v 1, меньшие заданного Сиг О, признака - сигналы v совпадающие с признаком - сигналы V О и z 1. В режиме преобразования структу данных на входы 1 всех ячеек однородной структуры подается управляю щий сигнал К 1. Функции (1) (2) и (З) принимают вид: X X V Z ;(1J z zx(С2) V vvzxy..(3) Если при этом подать на входы 2 всех ячеек левого столбца произвол ный двоичный вектор, а на входы 3 всех ячеек верхней строки - гранич ные сигналы Хо О, то в первом (левом) столбце однородной структуры выделится (условием zx 1) первая сверху единица исходного двоичного вектора, во втором столб це вторая его единица и т.д. Дей ствительно, в первом (левом) стол це согласно (1) переменная х сох раняет значение О до тех пор, по ка z 0. В некотброй i -и ячейке, где впервые встречается z 1, х 4eняeт значение на 1 и сохраняет 1 до нижней границы. Значит, это единственная ячейка первого столбца, в которой выполняется условие zX 1. Горизонтальный канал z выделенной ii,-ft ячейки в соответствии с( заперт сигналом х О, поэто му первая единица исходного двоичнего вектора далее по горизонтали не распространяется. Во всех ячейках первого столбца, расположенных ниже ячейки, X 1 и, следовательно, 2 « г. Значит, на входы 2 второго столбца поступает копия исходного двоичного вектора за исключением его первой (верхней) единицы. Аналогичные преобразования происходят во втором, третьем и т.д. столбцах однородной структуры; в некоторой in-и ячейке второго столбца вьаделяется (условием zx 1 вторая единица исходного вектора, в ij-й ячейке третьего столбца третья единица и т.д. При этом, очевидно, L i2 .i Рассмотренное свойство последовательного выделения очередных единиц и наличие функции (3 ) обеспечивают выполнение следукмцих операций преобразования структур данных. 1. Расширение. Задача, которую решает устройство в этом случае, состоит, в соединении m упорядоченных входных каналов с любой упорядоченной группой m выходных каналов (из общего числа п). Номера выходных каналов .- . ... . 2 .к которым должны быть подключены входные каналы 1, 2, ..., т, задают ся п-раэрядным двричным вектор.ом, содержащим 1 в соответствующих , разрядах (управляющий вектор).Этот вектор подается (поразрядно) на входы 2 ячеек левой границы однородной структуры, m входных каналов подключаются поразрядно ко входам 4 ячеек верхней границы. На входы 5 ячеек левой границы подаются граничные сигналы v 0. При этом в каждой ячейке однородной структуры, где выполняется условие zx 1, в соответствии с (3 имеет . меЬто V у, т.е. происходит поворот сигнала из вертикального канала у в горизонтальный канал V. Очевидно, при этом на выходы 10 ячеек, правой границы будут, направлены: в 1гй строке сигналы 1-го входного канала, в строке - сигналы 2-го входного канала и т.д., что соот- . ветствует решаемой задаче. 2. Сжатие. . Задача, которую решает устройство в этом , состоит в соединении любой упорядоченной группы входных каналов (из общего числа п) с m последовательными выходными каналами. Номера входных каналов i , i, .... i ( i i 2 . .), которые должны быть подключены к выходным каналам 1,2,...,т, задаются п-разрядным двоичным вектором, содержащимв соответствувдцих разрядах. В данном случае этот управляющий вектор подается в обратном коде на входы 3 ячеек верхней границы однородной структуры, п входных каналов подключаются поразрядно ко входам 4 ячеек верхней границы. На входы 2 и 5 всех ячеек левой границы подаются соответственно граничные сигналы Zp 1 и УО 0. При этом в тех столбцах, где управляющий век-. тор содержит О, 1. Значит, в этих столбцах не может быть выделенных ячеек. Остальные столбцы ведут себя следующим образом. Пусть в управляющем векторе единигда расположены на 1-,-й, 1„-й и т.д. позициях. Так как Zg условие гх 1 согласно (1) и {2)1 возникает в слева ячейке 1-й строки, слева ячейке 2-й строки и т.д., следовательно, сигналы , ig-ro И т.д. входных каналов будут направлены на выходы 10 ячеек правой границы в 1-й, 2-й и т.д. строках, что соответствует решаемой в данном случае задаче. 3. Взвешивание (подсчет количества единиц в двоичном векторе). Вектор-аргумент подается в обратном коде .на входы 3 ячеек верхней границы. На все входы 2 ячеек левой границы и входы 4 ячеек верхней границы подаются, соответственно граничные сигналы . Если

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