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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

СОЮЗ СОВЕтСкик

Социалистических

Республик (ll) 6 l0105

;. 0 )1(j. (бт) Дополнительное к авт. свид-ву (22) Заявлено 18,07.75(23) 2158429/24 с присоединенлем заявки,% (23) Приоритет (43) Опубликовано 050678. Битллетень РЙ 21 (51) M. Кл.

G 06 Р 7/00

Государственный намнтет

Совета й(нннатрав СИР аа делам нзааретеннй н аткрытнй (53) УДК

681.325(088.8) (45) Дата оп бликования описания 1505.78 (72) Автор изобретения

Я.И. Фет

Pl) Заявитель

Институт математики Сибирского отделения AH СССР (54) ЯчеЙкА ОДнОРОДПОЙ сРеДН

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

Известна ячейка однородной среды (1), содержащая триггер и логические

1 элементы И и ИЛИ.

В устройствах, построенных из известных ячеек, упорядочение информации производится путем выполнения оп- (( ределенной последовательности опросов ассоциативной матрицы в соответствии с так называемым алгоритмом СибераЛнндквиста. При этом для упорядочения массива из И элементов информации требуется в среднем 2,9 Р(,команд.

Для решения задачи выделения упорядоченного списка элементов в заданных границах Р, с А < Р в известных устройствах предварительно в специальный столбец ассоциативной матрицы для всех элементов исходного массива заносятся единицы. Затем проводится упорядоченный поиск (в порядке убывания) всех элементов, начиная с Рн, и в выделенных строках стираются единицы столбца меток. Аналогично проводится упорядоченный поиск (в порядке возрастания) всех элементов, начиная с Рз, а также стираются метки. В результате метки остаются только у тех элементов, которые расположены в заданных границах. После этого проводится упорядоченная выборка всех отмеченных (искомых) элементов,. Поскольку в общем просматривается весь массив, число команд постоянно (2,9 И ) и не зависит от полезного объема массива р(о, т.е. от того, сколько элементов удовлетворяют заданным условиям.

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

Наиболее близкой по технической сущности к изобретению является ячейка устройства для сортировки информации (21, содержащая триггер, четыре элемента И и два элемента ИЛИ. Первый вход ячейки соединен с первыми входами первого и второго элементов И.

Второй вход первого элемента И подключен ко второму входу ячейки и первому входу первого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И и первым входом второго элемента ИЛИ, второй вход которого подключен к выходу четвертого элемента И, первый вход которого соединен с третьим входом ячейки и первым входом третьего элемента И, а второй

610105 вход — с четвертым входом ячейки и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера, единичный вход которого соединен с выходом первого элемента И

8 а единичный выход — co вторым входом третьего элемента И.

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

Эта цель достигается тем, что в ячейку однородной среды введены пятый элемент И и третий элемент ИЛИ. Первый вход пятого элемента И соединен с выходом третьего элемента И, второй вход — со вторым входом четвертого элемента И, а выход — с первым входом третьего элемента ИЛИ, второй вход которого подключен к пятому входу ячейки.

Таблица1

Ч = Gl Ч P CM Y = С1 P

О О

О 1

1 О

1 1

Выражение (2) показывает, что сигнал на выходе Z ячейки равен 1, если имеется сигнал. 1 на входе 2 и, кроме того, 0 > P . Выражение (3) показывает, что сигнал на выходе ч1 ячейки равен 1, если имеется сигнал 1 на входе ч либо сигнал 1 на входе, и кроме того, а Ð

Для выполнения операции сравнения на все входы Z левой границы однородной среды подается сигнал 1, а на все входы ч левой границы — сигнал О.

При сравнении произвольных чисел =111С(2 и P - p p возможны три случая:

1. Во всех разрядах а p . Это значит, что 4 и . Согласно выражениям (2) и (3) при этом на правой границе вырабатывается сигнал 2 „ = 1 и ч « * О.

1 1

2. Во всех старших разрядах (до некоторого 3 -го} с p« p, iр1 (т.е, а =1, Ц = О) . Это значит, что А Р независимо от соотношения дальнейших разрядов. Так как 2, = 1, то, согласно выражениям (2) и (3), в 1 -й ячейке

Z 1 и ч = 1. Если во всех дальнейших (младших) разрядах 1- p, To z, =, 1 1

> 1 если же хотя бы в одном разряде a < р, то 21р = О.

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

Ячейка 1 имеет входы 2, 3, 4, 5 и

6 переменных Z, Х, I, ч U соответствен.но и выходы 7, 8, 9, 10 и 11 переменных z, х, у, v и () соответственно и содержит триггер 12 с входными элементами И 13 и 14, элементы И 15, 16 и 17 и элементы ИЛИ 18, 19 и 20.

В однородной среде выходы 8 и 9 каждой ячейки 1 соединены со входами 3 и

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

Внутри каждой ячейки 1 первые входы элементов И 1 5 и 16 соединены со входом 2, выход элемента И 15 — с первыми входами элементов ИЛИ 18 и И 19, 40 второй вход элемента ИЛИ 18 — со входом 3 ячейки, а второй вход элемента

HJlH 19 — с выходом элемента И 16. Выход элемента ИЛИ 18 (19) подключен к выходу 8 (7) ячейки, Второй вход эле- 45 мента И 15 соединен с единичным выходом триггера 12, а второй вход элемента И 16 — со входом 4 и выходом 9 ячейки. Первый вход элемента И 17 соединен с выходом элемента И 15, второй 50 вход — со входом 4 ячейки, а выход— с первым входом элемента ИЛИ 20, второй вход которого соединен со входом

5 ячейки, а выход — C выходом 10 ячейки. г,5

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

Х =ХЧО2. (1)

>

Z = Z(ci÷ъ), (2) ч "- v> 2<1, (3)

9,=ох, (4)

Фо ) ч, (5 ) где о — состояние триггера 12.

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

Функции (1) и (2) совместно обеспечивают выделение максимальных элементов информации.

Для выяснения роли функции (3), которая действует совместно с функцией (2) построим табл.1. Из этой таблицы видно, что a

a > р, с р = 1 в том случае, когда а Р

3. Во всех старших разрядах (до неKOTOPOrO - O) а = Р, Z

Oj = 0I Р1 =1) . Это значит, что A > p независимо от соотношения дальнейших разрядов., Согласно выражениям (2) и (3), <, О и Ч, = О. Следовательно Z"„ =О и v = О.

610105

Таблица 2

А

A= Р

0 0

0 1 о

l5

А Р

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

Результаты приведенного анализа по азаны в табл.2.

Таким образом, однородная среда, построенная из предложенных ячеек, обеспечивает рЕшение за одиу команду следующих видов информационно-логических задач:

1. Поиск максимального элемента информации в массиве.

2. Выделение всех элементов информации, совпадающих с заданным признаком.

3. Разбиение массива на три подмножества, в первое из которых входят все элементы информации, совпадающие с заданным признаком, во второе — ace элементы, меньшие заданного признака, в третье — все элементы, большие заданного признака.

Рассмотрим примеры решения некоторых распространенных информационнологических задач в однородной среде, построенной из предложенных ячеек.

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

3()

l

Для упорядочения массива из элементов требуется М команд.

2. Выделение упорядоченного списка элементов, расположенных в заданных границах Р, < A < Р .

Для решения этой задачи вначале проводится сравнение с признаком Р.< после чего все элементы, удовлетворяющие условию А < Р4, исключаются из дальнейшей обработкй. Затем проводится сравнение с признаком z, и исключаются все элементы д > Р . В оставшемся подмножестве проводится упорядочение (см. выше), Таким образом, для решения этой задачи требуется И о+2 команды, где

)4о — число элементов исходного массива, удовлетворяющих заданным условиям, 3. Поиск элемента, ближайшего меньшего заданного признака Р.

Вначале проводится сравнение с признаком Р и исключаются все элементы

A i p, Затем в оставшемся массиве выделяется максимальный элемент, который и является искомым.

Для решения задачи требуются 2 команды.

4. Ассоциативная обработка информации.

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

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

И и первым входом второго элемента ИЛИ, второй вход которого подключен к выходу четвертого элемента И, первый вход которого соединен с третьим входом ячейки и первым входом третьего элемента И, а второй вход — с четвертым входом ячейки и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера, егиничный вход которого соединен с выходом первого элемента И, а единичный выход — co вторым входом третьего элемента И, отличающаяся тем, что, с целью расширения функцион»льных возможностей, в нее введены пятын элемент И и третий элемент ИЛИ; причем первый вход пятого элемента И «оединен с выходом третьего элемент» и, второй вход — со вторым входом четвертого элемента И, а выход — с первым входом третьего элемента ИЛИ, второй вход которого подключен к пятому вхг— ду ячейки.

Источники информации, принятые во внимание при экспертизе:

1. Патент США М 3320594,кл.340-172,5

1972, 2. Авторское свидетельство СССР

9 424141, кл. G 06 Р 7/00, 1971.

610105

Составитель В.Тарасов

Редакто Л.Утехина Тех е Н.Ваб ка Ко екто А. Власенко

Заказ 3011/37 Тираж 826 Подписное

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

113035 Москва Ж-35 Ра шс б 4 5

Филиал ППП Патент, r. Ужгород, ул. Проектная, 4