Параллельный процессор для логической обработки информации Советский патент 1975 года по МПК G06F17/16 G06F15/00 

. fO, если a , (02-o)2(a,, a,.)- ii g.j, a.aj, где ,/ 0,7, . . ., n-1; . Для определения всех coi и «г требуется n (я-1) сравнений а,- с « , которые можно проводить одновременно на л (п-1) устройствах сравнения, формирующих функции coi Используя симметрию значений функции шь можно построить модифицированные функции (О 1 и 0)2 , реализация которых требует значительно меньшего количества оборудованияUi I 0) (а,-, ау) (а ,, а) со2(а-, a)(.oi (uj, а i), и и . Таким образом достаточно, ироведя п (п-1)/2 сравнений а,- с uj, определить все значения со i , затем, инвертирую значения со i , получить все значения со2 и но формуле (1) вычислить значения ы/ . Элементы исходного массива А переставляются в соответствии со значениями «; , так что элемент а занимает в результирующем массиве место с номером и, .Ж В предлагаемом устройстве параллельно определяются все значения оз i и со 2 и вычисляются все значеиия м,- , после чего параллельно проводится перестановка элементов исходного массива, что позволяет получить высокую скорость сортировки, процессор может эффективно выполнять также сортировку произвольного массива длины . Если исходный массив имеет длину kn, где k - целое и , то сортировку можно вести с использованием алгоритма попарной сортировки, предварительно зшорядочив подмассивы длины п, причем в пары последовательно объединяются подмассивы в таком порядке, как это делается для элементов при иснользованин метода Боуза-Нельсона. Процессор кроме параллельной сортировки при незначительных дополнениях позволяет также вести поиск информации. Здесь также возникают два случая. Первый случай - когда число элемег1тов исходного массива не превосходит п-1, и второй - для массива произвольной длины . А. При поиске в массиве , Cz, . . ., с „-1 все элементы массива одновременно сравниваются с ключевым признаком б и формируется логический вектор V (vi, V2, . ., , ), указывающий, какие элементы массива С равны б. (О, если Cf 8, . , „ / (l, если , . . ., п-1. Б. Поиск информации в массиве произольиой размерности можно провоить иоследовательным применением указанной операции, однако при большой длине массива более эффективно вести поиск в предварительно упорядоченном массиве следующим образом. Каждый упорядоченный массив разбивается на п-1 подмассивов. Составляется вектор b(bi, 62, . . ., bn-i ), в котором равно крайнему справа элементу /-го подмассива. Затем проводится сравнение всех компонент вектора b с признаком б, и формируются логические векторы аир, компоненты которых определяются следующим образом /0, если bj f, (О, если , , если . P/ (1, если Ь; 8,. Отметим, что tty -ПС01 («о, fly )(2) i (ао, aj)vVj(3) где ,2, . . ., п-1; б ао; bj-uj-. Формирование вектора у, показывающего, в каких подмассивах могут содержаться элементы, равные б, заключается в следующем: Yi ai(4) Y/ ayAp/-i ,(5) где / 2,3, . . ., п-1. Если Y/ 1 (, . . ., п-1), значит в подмассиве с номером / имеются элементы, равные б. Если заранее известно, что все элементы исходного массива различны, то только одно Y/ равно 1 и исходный элемент содержится в подмассиве с номером /. При этом, если длина /-ГО подмассива не более п-1, то поиск ведется но п. А. В противном случае /-Й подмассив разбивается на подмассивы меньшей размерности и повторяется п. Б до тех пор, пока размерность подмассива не будет меньше п, после чего выполняется п. А. Если в исходном массиве имеется несколько элементов, равных б, то наличие одной единицы в векторе у указывает на то, что искомые элементы находятся в нодмассиве, отмечениом единичной компонентой у т. е. если Yy 1, то искомые элементы содержатся в нодмассиве с номером /. Паличие нескольких единиц в Y свидетельствует о том, что искомые элементы имеются в нескольких соседних подмассивах, при этом следует найти элемепты, равные б, в подмассивах, отмеченных крайними слева и справа единицами в векторе Y, и если число единиц в Y больше двух, то остальные подмассивы, отмеченные подмассивами, целиком состоят из элементов, равных б. На фиг. 1 приведен параллельный процессор для логической обработки информации, состоящий из запоминающего устройства 1 хранения исходной информации, блока 2 сравнения, блока 3 сумматоров, коммутирующей матрицы 4, запоминающего устройства 5 хранения результирующей информации, регистраиндикатора 6, преобразователя 7 и регистрауказателя 8. Устройства 1 и 5 содержат по п запоминающих ячеек 9 для хранения чисел (признаков), блок 2 сравнения - п (п-1)/2 схем 10 сравнения двоичных чисел, блок 3 сумматоров - п д-входовых двоичных сумматоров И. Выходы ячеек 9 устройства I подключены к входам схем 10 сравнения, причем выход f-й ячейки - к первому входу, а выход /-и ячейки - к второму входу (1,/)-й схемы сравнения (i,/ 0,l, . . ., П--1, ). Каждая (1,)-я схема сравнения имеет два выхода (первый - выход признака coi (а ;, йу ) и второй - выход признака 032(0/ , и; ), которые соедипены с входами соответствующих сумматоров И, причем на вход i-ro сумматора поступают первые выходы (t,/)-x схем сравнения и вторые выходы (/,i)-x схем сравнения. Выход каждого i-ro сумматора 11 блока сумматоров связан с t-M управляющим входом, а выход каждой i-й ячейки 9 устройства 1 с i-й ячейки 9 устройства 1 с i-м информационным входом коммутирующей матрицы 4. Каждый i-й выход коммутирующей матрицы подключен к входу i-й ячейки 9 и устройства 5. Каждая (о,/)-я схема сравнения имеет дополнительный третий выход (выход признака V J-), который связан с /-м входом регистраиндикатора 6. Первый, второй и третий выходы каждой (о,/)-и схемы сравнения соединены с /-Й группой входов преобразователя 7, выходы преобразователя - с соответствующими входами регистра-указателя 8. В качестве коммутирующей матрицы можно использовать любой коммутатор, осуществляющий произвольную перестановку п чисел, дополненный сответствующим устройством управления, которое выполняет иастройку коммутатора в соответствии с сортирующим вектором. На фиг. 2 приведена логическая схема коммутирующей матрицы 4. Эта матрица содержит п дешифраторов 12, П.2 групп клапанов 13, причем количество клапанов в каждой группе равно разрядности ячейки 9, и п п-входовых групповых схем «ИЛИ 14, причем каждая групповая схема «ИЛИ 14 включает в себя п-входовых схем «ИЛИ, число которых в группе равно разрядности ячейки 9. Вход каждого дешифратора 12 соединен с выходом соответствующего сумматора 11 блока сумматоров 3. и. -и выход Ы; (0,1, . . ., п-1) каждого i-ro дешифратора 12 подключей к управляющему входу соответствующей группы клапанов 13, информационпып вход которой связан с выходом /-и ячейки 9 устройства 1. Выходы группы клапанов 13, управляющие входы которых подключены к и ; -м выходам дещифторов, соединены с входами U; -и групповой схемы «ИЛИ 14, выход которой подключен к входу м ,- -и ячейки устройства 5. Сортировку выполняют следуюндпм образом. Исходный массив записывается в ячейки 9 устройства 1. Каждая ((,./)-я схема 10 сравнения определяет значение функций со i (а , , а . и «2 (а,- , Gy ), которые вырабатываются соответственно на первом и втором выходах этой схемы. Все схемы сравнения работают параллельно. Каждый t-й сумматор И блока сумматоров 3 вычисляет сумму w; поступающих на его входы единиц. На выходе блока сумматоров формируется сорт1 рую1ций вектор и. Все сумматоры 11 работают параллельно. Коммутирующая матрица 4 параллельно выполняет перестановку всех чисел исходлого массива, поступающих на информацнопиые входь матрицы 4 с ячеек 9 устройства I, в созтветствии с вычисленным в блоке 3 сумматоров сортирующим вектором, проходящим па управляющие входы матрицы 4. Результирующий упорядоченный массив с выхода коммутирующей матрицы записывается в ячейки 9 устройства 5. Если число, поступающее на вход г-го дешифратора 12 с выхода i-ro сумматора 11, равно и I , то на ы , -м выходе этого дешифратора появляется единица и число из -й ячейки 9 устройства 1 через соответствуюпию группу клапанов 13 и соответствующую г|Пгь новую схему «ИЛИ 14 попадает па и; -ю ячейку 9 устройства 5. Иоиск элемеита в массиве длины п-1 про водят следующим образом. Ключевой призпак б записывается в О-ю ячейку 9 устройства 1, элементы массива -в I-(п.- 1) ячейки 9 устройства 1. Срлвнсане значений этих элементов массива с признаком б идет параллельно па (0,/)-ных схемах 10 сравнения, па третьих выходах которых формируется элемент ty 1, если Оу 5. В ре гистр-индпкатор 6 записывается вектор v по казывающий, какие компоненты массива рав ны б. Поиск подмассива, в котором содер/кат ся элементы, равные б, осуществляется следующим образом. Признак б записывается о О-ю ячейку, а вектор b - в 1-(п-1) ячейки 9 устройства 1. Сравнение всех компопептоп вектора b с Призпаком б выполняется параллельно па (0,/)-х схемах сравнения. Вектор у формируется в преобразователе 7 в соответствии с формулами (2-5) и записывается в регистр-указатель 8, содержимое которого, таким образом, показывает в каких подмассивах имеются элементы равные б.

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

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

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

фае. i

1 I I I I I I

L.

i.

i

/.

I