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

у

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

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

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

Ячейка имеет входы 1-6 (k,z,x, y,v,u соответственно), выходы 7- II (z ,х ,у ,v ,и соответственно), триггер 12, элементы И 13-20, элементы ИЛИ 21-23, элементы НЕ 24 и 25, элементы И 26 и 27, элементы ИЛИ 28, И 29, ИЛИ 30, НЕ 31 и 32.

В однородной структуре выходы 8 и 9 ячейки соединены с входами 3 и 4 соседней по вертикали ячейки соответственно, а выходы 7,10 и 11 - с входами 2,5 и 6 соседней ячейки по горизонтали соответственно.

Ячейка однородной структуры реализует функции

X X V Z ak V zk; (1) z z ak vzyk v zxku V kua; (2)

vv zayk V zxyk; uxk Ч ukz; uyk V ukz ,

(3) (4) (5)

где а - состояние триггера 12;

q,,qQ - сигналы установки триггер

12 в I и k,z,x,y,

v,u - управляющие сигналы на

входах 1-6 ячейки; z ,х ,у ,

v ,и - сигналы на выходах 7-1 I

ячейки.

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

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

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

Устройство может работать в различных режимах, в зависимости от значения управляющего сигнала k и управляющего сигнала и.

В режиме информационного поиска

на входы 1 всей ячеек однородной структуры подается управляющий сигнал k О, а на входы 6 - управляющий сигнал U 0. Функции (1) - (3) пpинIiмaют вид:

(1)

х X V za; z z(a V у); v V V zay.

(2) (3)

При этом ячейки однородной ч:труктуры обеспечивают вьтолнение в однородной структуре следующих информационно-логических операций.

Поиск максимального элемента. Для вьтолнения этой операции элементы ов- рабатьшаемого массива должны быть предварительно записаны по строкам, старшими разрядами слева, в триггеpax 12 однородной структуры. Если теперь в каждом столбце соединить через элемент НЕ выходы 8 и 9 нижней ячейки и подать на входы 2 всех ячеек левого столбца и на входы 3

всех ячеек верхней строки граничные сигналы z I и X О соответственно, то по окончанию переходных процессов сигнал z 1 на выходах 7 ячеек правого столбца установится

в тех строках, которые содержат максимальные элементы информации.

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

в триггерах 12 обратным кодом.

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

Признак сравнения подается поразрядно на входы 4 верхних ячеек соответственно в столбцы в обратном коде. Если теперь подать на входы 2 и 5 всех ячеек левого столбца граничные

сигналы , соответственно, то по окончании переходных, где содержатся элементы, большие заданного признака, установятся сигналы v 1, если меньшие заданного признака сигналы v О и z О, совпадающие с признаком - сигналы v О и z 1.

в режиме преобразования структур данньгх на входы 1 всех ячеек однородной структуры подаются управляющие сигналы k 1 и U 0.

Функции (1) - (5) принимают вид:

X X V z; z zx;

V i zxy;

q, qi

a, a

t-i

Если при этом подать на входы 2 всех ячеек левого столбца произвольный двоичный вектор, а на входы 3 всех ячеек верхней строки - граничные сигналы X О, то в первом (левом) столбце однородной структуры выделится (условием zx 1) первая сверху единица исходного двоичного вектора, во втором столбце - вторая его единица, и т.д. Действительно, в первом (левом) столбце согласно () переменная х сохраняет значение О до тех пор, пока . В некоторой i-й ячейке, где впервые встречается z 1, х меняет значение на 1 и сохраняет 1 до нижней границы. Значит, это едчнственная ячейка первого столбца, в которой выполняется условие , Горизонтальный канал z выделенной i-й ячейки в соответствии с (2 ) заперт сигналом , поэтому первая I исходного двоичного вектора далее по горизонтали не распространяется. Во всех ячейках первого столбца, расположенных ниже i,-и ячейки, и, следовательно, z z. Значит, на входы 2 второго столбца поступает копия исходного двоичного вектора за исключением его первой (верхней) единицы. Аналогичные преобразования происходят во втором, третьем и т.д. столбцах однородной структуры: в некоторой i-й ячейке второго столбца вьще- ляется (условием ) вторая 1 исходного вектора, в ячейке третьего столбца - третья 1 и т.д. При этом очевидно i , i i ... ,

Рассмотренное свойство последовательного выделения очередных единиц и напичие функции (З) обеспечи

:

10

15

20

25

30

35

40

45,

1

50

55

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

Расширение. Задача, которую решает устройство в этом случае, состоит в соединении m упорядоченных входных каналов с любой упорядоченной группой m выходных каналов (из общего числа п). Номер входных каналов 1, ,i2 ,1. . . ,i(i,- i - i, . . .) , к которым должны быть подключены входные каналы 1,2,..., задаются п-разрядным двоичным вектором, содержащим 1 в соответствующих разрядах (управляющий вектор). Этот вектор подается поразрядно на входы 2 яеек левой границы однородной структуры, m входных каналов подключаются поразрядно к входам 4 ячеек верхней границы. На входы 5 ячеек левой границы подаются граничные сигналы Уд 0. При этом в каждой ячейке однородной структуры, где выполняется условие , в соответствии с (3 ) имеет место v у,т.е. происходит поворот сигнала из вертикального канала у в горизонтальный канал V. Очевидно, при этом на выходы 10 ячеек правой границы будут направлены в i,-й строке сигналы 1-го входного канала, в i2-й строке - сигналы 2-го канала и т.д., что соответствует решаемой задаче.

Сжатие. Задача, которую решает устройство в этом случае, состоит в соединении любой упорядоченной группы входных каналов (из общего числа п) с m последовательными выходными каналами. Номера входных каналов

i , , ij ,. . . , (i, i z i 3. i) . которые должны быть подключены к выходным каналам 1,2,...,га, задаются п-разрядным двоичным вектором, содержащим 1 в соответствующих раз- разрядах. В данном случае этот управляющий вектор подается в обратном коде на входы 3 ячеек верхней границы однородной структуры, п входных каналов подключаются поразрядно к входам 4 ячеек верхней границы. На входы 2 и 5 всех ячеек левой границы подаются соответственно граничные сигналы и V 0. При этом в тех столбцах, где управляющий вектор содержит О, . Значит, в столбцах не может быть выделенных ячеек. Остальные столбцы ведут себя следующим образом. Пусть в упргшляющем векторе, единицы расположены на ,

И Т.Д. ПОЗИЦИЯХ. Так как ,

iNx -. (7 )

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

Взвешивание (подсчет количества единиц в двоичном векторе). Вектор- аргумент подается в обратном коде на входы 3 ячеек верхней границы. На все входы 2 ячеек левой границы и входы 4 ячеек верхней границы подаются соответственно граничные сигналы и у 1. Если в векторе-аргументе содержится 1 единиц, то условие будет вьтолняться в точности в 1 первых строках однородной структуры. Во всех остальных, расположенных ниже, строках условие возникнуть не может. Значит, сигналы будут направлены в каналы v только в первых 1 строках. Следовательно выходы IО яеек правой границы образуют в данном случае шкалу, по которой считьгаается вес (количество единиц) заданного двоичного вектора.

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

XV z;

a;

V V zxy;

d) (2 (3)

(4) (5)

Таким образом, настройка ячеек однородной структуры на выполнение функций (l) - (5) обеспечивает возможность записи в триггеры этих ячеек информации, поступающей в них по входу 2, и одновременно с этим формирование на выходе 7 значения состояния триггера соответствующей ячейки Б предыдущий такт работы однородной структуры. Это свойство обеспечивает выполнение следующих операций в однородной структуре.

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

ячеек крайнего левого столбца однородной структуры. Для решения этой задачи на входы 2 ячеек крайнего левого столбца однородной структуры подается п-разрядный двоичный вектор, на входы 6 которых подается также сигнал , на входы 4 всех ячеек однородной структуры - сигнал , на входы 1 ячеек i-ro столбца однородной структуры, в которых выполняется запись исходно двоичного вектора, подается импульсный сигнал . В результате такой настройки в ячейках i-ro столбца реализуются функции (l) - (5),а в остальных

ячейках однородной структуры - функции (1-5) в виде:

х X V za;(Г )

z z;(2)

V V V za; q, X

%

(3) (4) (5)

Таким образом, в соответствии с (l )-(5) двоичный вектор, подаваемый на входы 2 ячеек крайнего левого столбца однородной структуры, без изменения поступает на входы 2 ячеек i-ro столбца и в соответствии с (l )-(5) заносится в триггеры 12 этих ячеек при поступлении импульса записи по входу, что и требуется для решения поставленной задачи.

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

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

() значения состояния (i-l,j)-й ячейки, чем достигается сдвиг данных, хранящихся в ячейках однородной

од n)i

13

разряд Бпра структуры на во.

Цпя реализации этой задачи на входы I всех ячеек однородной структуры подается сигнал ,na входы 6 ячеек крайнего левого столбца подается импульс ,при этом на выходах 7 каждой ячейки однородной структуры формируется значение состояния триггера этой ячейки, которое по входу 2 поступает в соседнюю ячейку и заносится в ее триггер. Длительность импульса при работе однородной структуры в данном режиме соответственно должна быть равна 26, +2 с + , где С,, Г;, э соответственно времена задержки сигналов в схемах ИЛИ,И,НЕ, на которых реализованы ячейки однородной структуры. Таким образом, в результате настройки ячеек однородной структуры сигналами и однородная структура в данном случае преобразуется в матричный сдвиговый регистр, в котором реализуется операция сдвига вправо на одну позицию хранимых данных, что и требуется для решения поставленной задачи.

Следует отметить, что при соединении выходов 7 ячеек крайнего правого столбца однородной структуры с входами крайнего левого столбца однородная структура преобразуется в матри ный сдвиговый кольцевой регистр. Кроме того, в случае формирования на входах 6 ячеек крайнего левого столбца однородной структуры серии импульсов в однородной структуре будет реализован сдвиг на п позиций, где п - число импульсов в задаваемой серии.

8

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

Изобретение относится к цифровой вычислительной технике и предназначено для массовой параллельной обработки информации. Целью изобретения является расширение функциональных возможностей за счет выполнения операций перемещения данных. Ячейка однородной среды содержит триггер 12, элементы НЕ 24,25,31,32 элементы И 13-20,26,27,29, элементы ИЛИ 21- 23, 28,30, входы 1-6, выходы 7-11. Устройство работает в различньк режимах в зависимости от значений управляющих сигналов К и И. Устройство выполняет: 1) информационный поиск, включающий поиск максимального элемента, поиск минимального элемента, разбиение массива на три подмножества; 2)преобразование структур,включающее расширение,сжатие,взвешивание; 3) перемещение данных, включающее запись информации в столбец, сдвиг данных. I ил. S сл

Формула

50

зобретени Ядс Р входом ячейки соответственно, а

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

50

55

9137232210

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