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

 

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

COtO3 СОВЕТ СНИХ

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

РЕСГ!УБЛИН

2322 А1 (191 (11) (51)4 G 06 F 7/00

ВСГ1 AN ty. g

13 „ 13

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4132878/24-24 (22) 11..06.86 (46) 07.02.88.Бюл. М 5 (71) Северо-Западный заочный политехнический институт (72) В.С.Князьков, С.Е.Раевский, В.Н.Егоров и Т.В.Волченская (53) 681.3 (088.8) (56) Авторское свидетельство СССР

У 851398, кл.С 06 F 7/00, 1978.

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

У 1013943, кл.G 06 F 7/00, 1982. (54) ЯЧЕЙКА ОДНОРОДНОЙ СТРУКТУРЫ (57) Изобретение относится к цифровой вычислительной технике и предназначено для массовой параллельной обработки информации. Целью изобретения является расширение функциональных возможностей за счет выполнения операций перемещения данных ° Ячейка однородной среды содержит триггер 12, элементы HF. 24,25,31,32 элементы

И 13-20,26,27,29, элементы ИЛИ 21—

23, 28,30, входы 1 -6, выходы 7-11.

Устройство работает в различных режимах в зависимости от значений управляющих сигналов К и И. Устройство выполняет: 1) информационный поиск, включающий поиск максимального элемента, поиск минимального элемента, разбиение массива на три подмножества; 2)преобразование структур, включающее расширение, сжатие, взвешивание;

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

1372322 ры.

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

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

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

z = z ak vzyk ч zxku ч kua; (2) (3) ч = vv zayk ч zxyk; (4) q, = uxk v ukz; (5) q = Ugk ч Ukz» состояние триггера 12; сигналы установки триггера

I2 в "1" "О" где а

Ч1»Чо

° z,x»y

V U управляющие сигналы на входах 1-6 ячейки;

I ( г,х,у

v,u — сигналы на выходах 7-11 ячейки.

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

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

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

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

На чертеже приведена функциональная схема ячейки однородной структувсех ячеек выбранной строки подается импульс разрешения записи, а на входы 1 — нулевой сигнал, 5

Устройство может работать в различных режимах, в зависимости от значения управляющего сигнала k u управляющего сигнала и, В режиме информационного поиска на входы 1 всей ячеек однородной структуры подается управляющий сигнал k = О, а на входы 6 - управляющий сигнал u = О. Функции (1) — (3) принимают вид:

15 (1) (2) (3) х =хч za;

z = z(av у);

v = vv гау. но, то по окончанию переходных процессов сигнал z = I на выходах 7 ячеек правого столбца установится

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

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

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

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

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

Если теперь подать на входы 2 и 5 всех ячеек левого столбца граничные сигналы z-=l, v=0 соответственно, то по окончании переходных, где содержатся элементы, большие заданного признака, установятся сигналы ч = 1, если меньшие заданного признака

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

Поиск максимального элемента. Для выполнения этой операции элементы обрабатываемого массива должны быть предварительно записаны по строкам, старшими разрядами слева, в тригге30 рах 12 однородной структуры. Если теперь в каждом столбце соединить через элемент НЕ выходы 8 и 9 нижней ячейки и подать на входы 2 всех ячеек левого столбца и на входы 3 всех ячеек верхней строки граничные сигналы z = 1 и х = О соответствен1372322 сигналы v = О и z = О, совпадающие с признаком — сигналы v = =О и

I г = 1.

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

Функции (1) — (5) принимают вид: х =xYz;

z = zx, I (2 ) (3 ) ч = v Y zxy; (4 ) о — а = a (5 )

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

В некоторой i-й ячейке, где впервые встречается z = 1, х меняет значение на "1" и сохраняет "l" до нижней границы. Значит, это единственная ячейка первого столбца, в которой выполняется условие zx=l. Горизонтальный канал г выделенной i-й ячейки в соответствии с (2 ) заперт сигналом х=О, поэтому первая "!" исходного двоичного вектора далее по горизонтали не распространяется. Во всех ячейках первого столбца, расположенных ниже i -й ячейки, х=l и, следовательно, z = z. Значит, на входы

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

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

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

Расширение. Задача, которую решает устройство в этом случае, сос— тоит в соединении m упорядоченных входных каналов с любой упорядоченной группой m выходных каналов (из общего числа и). Номер входных кана10 лов 11 1 1 ° .. 1 (1 1 1 С...) к которым должны быть подключены входные каналы 1,2,..., задаются и-разрядным двоичным вектором, содержащим "1" в соответствующих разрядах (управляющий вектор). Этот вектор подается поразрядно на входы

2 яеек левой границы однородной структуры. m входных каналов подключаются поразрядно к входам 4

2р ячеек верхней границы. На входы 5 ячеек левой границы подаются граничные сигналы v, = О. При этом в каждой ячейке однородной структуры, где выполняется условие zx=l в соответВ I

25 ствии с (3 ) имеет место v = у,т.е. происходит поворот сигнала иэ вертикального канала у в горизонтальный канал v. Очевидно, при этом на выходы 10 ячеек правой границы будут направлены в i é строке сигналы

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

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

n) с m последовательными выходными каналами. Номера входных каналов

40 1 1 ° ° ° (1 - 1z 1з .. 1 ), коЩ торые должны быть подключены к выходным каналам l, 2,...,ш, задаются и-разрядным двоичным вектором, содержащим "l в соответствующих раз45 разрядах. В данйом случае этот управ1 ляющий вектор подается в обратном коде на входы 3 ячеек верхней границы однородной структуры, и входных каналов подключаются поразрядно к входам 4 ячеек верхней границы. На входы 2 и 5 всех ячеек левой границы подаются соответственно граничные сигналы z=l и ч = О. При этом в тех столбцах, где управляющий вектор

55 содержит "О", x= 1 Значит, в столбцах не может быть выделенных ячеек.

Остальнь:е столбцы ведут себя следующим образом. Пусть в управляющем векторе единицы расположены на i -й, 1372322

25 (х (1 ) (2 ) (3 ) 45 (4 ) (5" ) хч z а, v ч zxy; ч

z аС=г

Таким образом, настройка ячеек однородной структуры на выполнение функ- 50 ций (1 ) — (5 ) обеспечивает возможность записи в триггеры этих ячеек информации, поступающей н них по входу 2, и одновременно с этим формирование на выходе 7 значения сос- 55 тояния триггера соответствующей ячейки н предыдущий такт работы однородной структуры. Это свойство обеспеi -й и т.д. позициях. Так как z=l, II I( условие zx= I согласно (! ) и (2 ) возникает в i, -й слева ячейке 1-й строки, i -й слева ячейке 2-й строки и т.д., следовательно, сигналы

-го и т.д. входных каналов будут направлены на выходы

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

Взвешивание (подсчет количества единиц в двоичном векторе). Вектораргумент подается в обратном коде на входы 3 ячеек верхней границы. На !5 все входы 2 ячеек левой границы и входы 4 ячеек нерхней границы подаются соответственно граничные сигналы

z l и у =I. Если в векторе-аргументе содержится 1 единиц, то условие

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

y=l будут направлены в каналы v только н первых 1 строках. Следовательно, выходы IO яеек правой границы образуют в данном случае шкалу, по которой считывается вес (количество единиц) 30 заданного двоичного вектора.

В режиме перемещения данных на входы 6 всех яеек однородной структуры подается сигнал u=l, а на входы

1 ячеек, настраиваемых на работу в 35 указанном режиме — кратковременный сигнал k-=I. При этом ячейки, на которые подаются сигналы настройки u=

=k=1, реализуют функции (1) †(5) в виде: 40

I х = х ч га;

z = zI (1" ) (2" ) ч = v Ч za; (3 ) (4 ) (5 ) q,= х

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

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

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

Запись информации в столбец. Задача, которую решает устройство в данном случае, состоит н записи в некоторый 1-й столбец однородной структуры п-разрядности дноичного вектора, поступающего на вторые входы . ячеек крайнего левого столбца однородной структуры. Для решения этой задачи на входы 2 ячеек крайнего левого столбца однородной структуры подается п-разрядный двоичный вектор, на входы 6 которых подается также сигнал u=l, на входы 4 всех ячеек однородной структуры — сигнал y=l, на входы 1 ячеек i-ro столбца однородной структуры, в которых выполняется запись исходно двоичного вектора, подается импульсньцЪ сигнал

k=1. В результате такой настройки в ячейках i-го столбца реализуются функции (1 ) — (5 ),а в остальных ячейках однородной структуры — функции (1-5) в ниде:

1372322

15

25

35

40 структуры на один разряд лира во.

Для реализации этои задачи на входы 1 всех ячеек однородной структуры подается сигнал k=1,nà входы

6 ячеек крайнего левого столбца подается импульс u-=l,при этом на выходах 7 каждой ячейки однородной структуры формируется значение состояния триггера этой ячейки, которое по входу 2 поступает в соседнюю ячейку и заносится в ее триггер.

Длительность импульса u=-1 при работе однородной структуры в данном режиме соответственно должна быть равна 2, +2 с + ь,, где ... с-., соответственно времена задержки сигналов в схемах ИЛИ,И,НЕ, на которых реализованы ячейки однородной структуры. Таким образом, в результате настройки ячеек однородной структуры сигналами k=1 и u=! однородная структура в данном случае преобразуется в матричный сдвиговый регистр, в котором реализуется операция сдвига вправо на одну позицию хранимых данных, что и требуется для решения поставленной задачи.

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

u=I в задаваемой серии. формула изобретения45

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

50 ячейки соединен с входом первого элемента HF, и первыми входами первого, второго и третьего элементов И, вторые входы которых соединены с вторым входом ячейки и первыми входами чет55 вертого и пятого элементов И, вто рые входы которых соединены с выходом первого элемента НЕ, выход первого элемента И соединен с первым входом первого элемента ИЛИ, второй вход которого соединен с третьим входом второго элсмснта И, первым входом шестого элемента 11, третьжч входом ячейки и входом второго элемента HF., выход которого соединен с третьим входом третьего элемента И, четвертый вход которого соединен с третьим входом пятого элемента И, первыми входами седьмого и восьмого элементов И, четвертым входом и первым выходом ячейки, пятый вход которого соединен с первым входом второго элемента ИЛИ, второй и третий входы которого соединены с выходами третьего элемента И и седьмого элемента

И, второй вход которого соединен с третьим входом первого элемента ИЛИ, ныходом четвертого элемента И и первым входом третьего элемента ИЛИ, второй и третий входы которого соединены с выходами второго и пятого элементов И, вьгоды первого, второго и третьего элементов ИЛИ соединены с вторым, третьим и четвертым выходами ячейки, шестой вход которой соединен с вторыми входами шестого и восьмого элементов И и пятым выходом ячейки, третий вход четвертого элемента И соединен с выходом триггера, отличающаяся тем, что, с целью расширения функциональных возможностей за счет выполнения oneрации перемещения данных, она дополнительно содержит третий и четвертый элементы НЕ, девятый, десятый и одиннадцатый элементы И, четвертый и пятый элементы HJIH, причем первый вход ячейки соединен с первыми входами девятого, десятого и одиннадцатого элементов И, вторые входы которых соединены с выходом триггера, выходом третьего элемента НЕ и вторым входом ячейки соответственно, а третьи входы девятого, десятого и одиннадцатого элементов И соединены с шестым входом ячейки и входом четвертого элемента НЕ, выход которого соединен с четвертым входом второго элемента И, выход первого элемента HE соединен с третьими входами шестого и восьмого элементов И, выходы которых соединены с первыми входами четвертого и пятого элементов ИЛИ, вторые входы которых соединены с выходами одиннадцатого и десятого элементов И, а выходы четвертого и пятого элементов ИЛИ соеди1372322

Составитель О. Береэикова

Редактор В.Данко Техред Н. Ходанич Корректор А.Тяско

Заказ 484/41 Тираж 704 Подписное

ВПИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие, r.Óæãoðîä, ул. Проектная, 4 нены с единичным и нулевым входами триггера, вход третьего элемента HE соединен с вторым входом ячейки,четвертый вход третьего элемента И сое— динен с выходом девятого элемента И.