Параллельный процессор для логической обработки информации

 

О11И САН ИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

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

Республик

К А870РСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 14.01.72 (21) 1739781/18-24 с присоединением заявки №вЂ” (23) Приоритет—

Опубликовано 30.08.75. Бюллетень № 32

Дата опубликования описания 21.07.76 (51) М. Кл. G 06f 15/20

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

Совета Мнннстроа СССР во делам изобретений н открытнй (53) УДК 681.14(088.8) (72) Автор изобретения (71) Заявитель

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

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

Цель изобретения — увеличение скорости обработки информации.

Это достигается тем, что выход i-й ячейки запоминающего устройства хранения исходной информации подключен к первому входу, а выход /-й ячейки — к второму входу (t., /)-й схемы сравнения (/,/=0,1, ..., и — 1, i

А=<аю, аь..., а„ i ).

Для упорядочения массива в порядке неубывания слева направо строится и-компонентный сортирующий вектор U= (ию, иь..., и„|) такой, что каждая его компонента и, соответствует элементу а,. из исходного массива А и указывает его номер в упорядоченном массиве. Тогда для сортировки достаточно переставить элементы исходного массива А в соответствии со значениями и, . Сортирующий вектор представляется в виде

25 и,. = Х о; (а;, а,) + Х о (а;, а,) (О, если а (;а,, 1 1, если а, ) а;, Эо где jj=01,, и — 1; i +j„

1 Г. Иванов

Институт математики Сибирского отделения АН СССР

482749

v I2=l ), указывающий, какие элементы массива С равны о.

О, если с+6,.

Б. Поиск информации в массиве произвольной размерности N) n — 1 можно проводить последовательным применением указанной операции, однако при большой длине массива более эффективно вести поиск в предварительно упорядоченном массиве следующим образом. Каждый упорядоченный массив разбивается на n — 1 подмассивов. Составляется вектор Г= (b!, bg,..., b, ), в котором b равно крайнему справа элементу j-го подмассива. Затем проводится сравнение всех компонент вектора b с признаком 6, и формируются логические векторы а и р, компоненты которых определяются следующим образом

I0, если bj<6, /О, если bj- Л, - ) I1 если Ь;) б. (1, если Ь, а

Отметим, что

О, если а,. а;, 1, если а,.) где !,i =0,1,..., n — 1; i

20 (! = !»(а,, а )= г !å 1,j — -0,1,..., п — 1, !)!, n — (—

u; = — (» (a;> aj) (»2 (a !, aj)> (1) ! =, (=О 25 причем (» (а;, а,) =)(» (а(, а,), и=и .

Таким образом достаточно, проведя и (и — 1)/2 сравнений а(с а,, определить все

Г з! ачения (» затем, иивертирую значения (» получить все значения (» и по формуле (1)

I вычислить значения и;

Элементы исходного массива А переставляются в соответствии со значениями и(, так что элемент а; занимает в результирующем

I массиве место с номером и; .

B предлагаемом устройстве параллельно

I определяются все значения ж и (0 г и выI

40 числяются все значения и;, после чего параллельно проводится перестановка элементов исходного массива, что позволяет получить высокую скорость сортировки. Процессор может эффективно выполнять также сор- 4,-. тировку произвольного массива длины N)n.

Если исходный массив имеет длину kn, где

h — целое и й)2, то сортировку можно вести с использованием алгоритма попарной сортиI;,0â!(è, предварительно упорядочив подмасси- 50 вы длины и, причем в пары последовательно объединяются подмассивы в таком порядке, как это делается для элементов при использовании метода Боуза — Нельсона.

Процессор кроме параллельной сортировки

55 при незна !ительиых дополнениях позволяет также вести поиск информации. Здесь также возникают два случая. Первый случай — когда число элементов исходного массива не превосходит n — 1, и второй — для массива

60 произвольной длины V)n — 1.

Л. При поиске в массиве С=<с!, с,..., с „.! ) все элементы массива одновременно сравнив=:þòñÿ с ключевым признаком б и формируется логический вектор Р= (!, оь..., 65 (4) (5) у(=а! у«=а(Р P l — где « =2,3,..., n — 1.

Если у; =1 (j=12, и — 1), значит в подмассиве с номером «имеются элементы, равные о.

Если заранее известно, что все элементы исходного массива различны, то только одно у; равно 1 и исходный элемент содержится в подмассиве с номером j. При этом, если длина

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

Если в исходном массиве имеется несколько элементов, равных о, то наличие одной еди«!ицы в векторе у указывает на то, что искомые элементы находятся в подмассиве, отмеченном единичной компонентой у, т. е. если у,. =1, то искомые элементы содержатся в подмассиве с номером j. Наличие нескольких единиц в у свидетельствует о том, что искомые элементы имеются в нескольких соседних подмассивах, при этом следует найти элементы, равные о, в подмассивах, отмеченных крайними слева и справа единицами в векторе у, и если число единиц в у больше двух, то остальные подмассивы, отмеченные подмасси3 (, !О, если а, а1, I 1, если а =а где i j=0,7,..., n — 1; j

Для определения всех (»! и (» требуется и (п — 1) сравнений а,. с а которые можно проводить одновременно на п (n — 1) устройствах сравнения, формирующих функции (»! (»2.

Используя симметрию значений функции 10 !

»!, можно построить модифицированные функI цни (» н (», реализация которых требует значительно меньшего количества оборудоват!!!я с(,=- 1(» (ао, а, ) (2) ;=(» (ао, а,) vVj (3) где j=1,2, 6 — a!!, Формирование вектора у, показывающего, в каких подмассивах могут содержаться элементы, равные 6, заключается в следующем:

482749

1О

65 вами, целиком состоят из элементов, равных 6.

На фиг. 1 приведен параллельный процессор для логической обработки информации, состоящий из запоминающего устройства 1 хранения исходной информации, блока 2 сравнения, блока 3 сумматоров, коммутирующей матрицы 4, запоминающего устройства 5 хранения результирующей информации, регистраиндикатора 6, преобразователя 7 и регистрауказателя 8.

Устройства 1 и 5 содержат по и запоминающих ячеек 9 для хранения чисел (признаков), блок 2 сравнения — и (n — 1)l2 схем 10 сравнения двоичных чисел, блок 3 сумматоров — и и-входовых двоичных сумматоров 11, Выходы ячеек 9 устройства 1 подключены к входам схем 10 сравнения, причем выход i-й ячейки — к первому входу, а выход j-й ячейки — к второму входу (ц)-й схемы сравнения (Ц=0,1,..., и — 1, i(j). Каждая (ц)-я схема сравнения имеет два выхода (первый—

I выход признака ю? (а,, а. ) и второй — выI ход признака??2(a;, а,. ), которые соединены с входами соответствующих сумматоров

11, причем на вход i-го сумматора поступают первые выходы (ц) -х схем сравнения и вторые выходы (у) -х схем сравнения. Выход каждого i-ro сумматора 11 блока сумматоров связан с i-м управляющим входом, а выход каждой i-й ячейки 9 устройства 1 с i-й ячейки

9 устройства 1 с i-м информационным входом коммутирующей матрицы 4. Каждый i-й выход коммутирующей матрицы подключен к входу 1-й ячейки 9 и устройства 5.

Каждая (оj)-я схема сравнения имеет дополнительный третий выход (выход признака

V ), который связан с j-м входом регистраиндикатора 6. Первый, второй и третий выходы каждой (о,1)-й схемы сравнения соединены с j-й группой входов преобразователя 7, выходы преобразователя — с соответствующими входами регистра-указателя 8.

В качестве коммутирующей матрицы можно использовать любой коммутатор, осуществ И ляющий произвольную перестановку п чисел, дополненный сответствующим устройством управления, которое выполняет настройку коммутатора в соответствии с сортирующим вектором.

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

Эта матрица содержит п дешифраторов 12, и групп клапанов 13, причем количество клапанов в каждой группе равно разрядности ячейки 9, и n n-входовых групповых схем

«ИЛИ» 14, причем каждая групповая схема

«ИЛИ» 14 включает в себя и-входовых схем

«ИЛИ», число которых в группе равно разрядности ячейки 9.

Вход каждого дешифратора 12 соединен с выходом соответствующего сумматора 11 блока сумматоров 3. и,. -й выход и, = (0,1,..., п — 1) каждого i-го дешифратора 12 подклюl5

55 чен к управляющему входу соответствующей группы клапанов !3, и»форма»поп??ы» вход которой связан с выходом ? -й ячейкп 9 устройства 1. Выходы группы кляпа»ов 13, у»равляющие входы которых»одключепы к и,. -м выходам дешифторов, соединены с входами и,- -й групповой с.;емы «ИЛИ» 14, выход которой подключен к входу и,- -й ячейки устройства 5.

Сортировку выполняют следуlotIIIIM образом.

Исход»ый массив записывается в ячейки 9 устройства 1. Каждая (i,j)-я схема 10 сравнения определяет значение функций t»! (а,, а

1 и о2 (at, а ), которые вырабатываются соответственно на первом и втором выходах этой схемы. Все схемы сравнения работают параллельно. Каждый t-й сумматор 11 блока сумматоров 3 вычисляет сумму и„поступающих на его входы единиц. Н?? ьп?хо tc блока сумматоров формируется сортпрующпй вектор и. Все сумматоры 11 работа?от ??;?!?;?л.?ел?и о.

Коммутирующая матрица 4 параллел?и о выполняет перестановку всех чисел исход»ого массива, поступающих на информацпо»»ые входы матрицы 4 с ячеек 9 устройства 1, в сответствии с вычисленным в блоке 3 суммлт0ров сортирующим вектором, проходящим»л управляющие входы MBTpHLtt I 4. Результпруloщий упорядоченный массив с выхода коммутирующей матрицы записывается в ячейки 9 устройства 5.

Если число, поступаюгцее на вход i-го дешифратора 12 с выхода i-го сумматора 11. равно и,, то на и,- -м выходе этого дсш?.фрлтора появляется единица и число из ?-й ячейки 9 устройства 1 через соответствую»?ую группу клапанов 13 и соответствующую групповую схему «ИЛИ» 14 попадает»л и; -к> ячейку 9 устройства 5.

Поиск элемента в массиве длины и — про водят следующим образом.

Ключевой признак б записывается в 0-к ячейку 9 устройства 1, элеме?;ты ii.ë .cc! I!i» в 1 — (и — 1) ячейки 9 устройства !. Срлв? с??11?. значений этих элементов массива с признаком

6 идет параллельно на (О,j) - ых схе»? ях 10 сравнения, на третьих выходах которых формируется элемент ??,- =1, если а,. =о. В ре гистр-индикатор 6 записывается вектор г»о казыва?ощий, какие компоненты массива р????ны 6. Поиск подмассива, в котором содер>к;и ся элементы, равные б, осуществляется след.ющим образом. Признак 6 записывается в 0-к? ячейку, а вектор b — в 1 — (и — 1) ячейки 9 устройства 1. Сравнение всех компо»е»топ вектора b с признаком б выполняется паря; ?лель»о на (0j)-õ схемах сравнения. Вектор у формируется в преобразователе 7 в соответствии с формулами (2 — 5) и записывается в регистр-указатель 8, содержимое которого, таким образом, показывает в каких подмасспвах имеются элементы равные 6.

482749

Предмет изобретения

Параллельный процессор для логической обработки информации, содержащий состоящее из и ячеек запоминающее устройство хранения исходной информации, п (и — 1)!2 схем сравнения двоичных чисел, и двоичных сумматоров, коммутирующую матрицу, запоминающее устройство хранения результирующей информации, состоящее из а ячеек, (и — 1)— разрядный регистр-индикатор, логический преобразователь и (и — 1) — разрядный регистр-указатель, отличающийся тем, что, с целью повышения быстродействия процессора, выход i-й ячейки запоминающего устройства хранения исходной информации подключен к первому входу, а выход j-й ячейки — к второму входу (ц)-й схемы сравнения (i,i=

О,l,..., и — 1, i

5 двоичного сумматора подключен к соответствующему управляющему входу коммутирующей матрицы, информационные входы которой соединены с выходами ячеек запоминающего устройства хранения исходной информации, а

lo информационные выходы — с входами ячеек запоминающего устройства хранения результирующей информации, третий выход каждой (oi)-й схемы сравнения соединен с i-м входом регистра-указателя, а выходы каждой

1й (0,1)-й схемы сравнения соединены с /-й группой входов логического преобразователя, выходы которого подключены к соответствующим входам регистра-указателя.

482749

Составитель И. Фирсова

Техред 3. Тараненко

Корректор Е. Хмелева

Редактор И. Грузова

МОТ, Загорский филиал

Заказ 1613 Изд. л1з 1743 Тираж 679 Подписное

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

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