SU1372322A1 - Ячейка однородной среды - Google Patents

Abstract

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

Description

у

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

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

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

Ячейка имеет входы 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

Формула

50

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

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

50

55

9137232210

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

Claims (1)

1. Формула и зобретения

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

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

   сое-