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

(51) М, Кл. б 061 15/20 Государственный комитет Сонате Министров СССР во делом изобретений и открытий(72) Автор изобретения Г. Г. ИвановИнститут математики Сибирского отделения АН СССР(71) Заявитель 1Предлагаемый процессор относится к области вычислительной техники, а именно к специализированным устройствам для логической обработки больших информационных массивов, Процессор может быть использован для поиска и упорядочения информации в составе автоматизированных систем управления, информационно-поисковых систем.Известные параллельные устройства для логической обработки информации имеют сравнительно малую производительность вследствие того, что время полного упорядочения массива 2 элементов пропорционально глубине сети, равной р(р+ 1)/2.Цель изобретения - увеличение скорости обработки информации.Это достигается тем, что выход с-й ячейки запоминающего устройства хранения исходной информации подключен к первому входу, а выход /-й ячейки - к второму входу (с, /)-й схемы сравнения (с,/=0,1 и - 1, с(/), входы каждого с-го двоичного сумматора подсоединены к первым выходам (с,/) -х схем сравнения и вторым выходам (/,с)-х схем сравнения, выход каждого двоичного сумматора - к соответствующему управляющему входу коммутирующей матрицы, информационные входы которой соединены с выходами ячеек запоминающего устройства хранения исходной информации, а информационные выходы - с входами ячеек запоминающего устройства хранения результирующей информации, Третий выход каждой (О,/)-й схемы сравнения связан с /-м входом регистра-указателя,а выходы каждой (О,/)-й схемы сравнения -с /-й группой входов логического преобразователя, выходы которого подключены к соответствующим входам регистра-указателя. Всесравнения элементов исходного массива, не 10 обходимые для установления порядка, выполняются в процессоре одновременно на матричном устройстве, на входы которого подаютсясоответствующие элементы исходного массиваА=ао, а 1 а -).Для упорядочения массива в порядке неубывания слева направо строится и-компонентный сортирующий вектор с/= (ио, иь,и) такой, что каждая его компонента и,соответствует элементу а,. из исходного массива А и указывает его номер в упорядоченном массиве. Тогда для сортировки достаточно переставить элементы исходного массива Ав соответствии со значениями ис . Сортирующий вектор представляется в виде25и = Х о с (а;, а ) + Х со 2(а а ), а,), (1) 25 30 3ГО, если аач=сча, аУ 11, если а;=агде ,1=0,7 г - 1; (,Для определения всех в и о требуется п (и - 1) сравнений а, с а, которые можно проводить одновременно на и (и - 1) устройствах сравнения, формирующих функции о и и 2.Используя симметрию значений функции и, можно построить модифицированные функпни кн в, реализация которых требует значительно меньшего количества оборудоватия О, если ан, - (а а )=1, если агде ,=0,1 и - 1; с(,О, если а=-ч(и(и - 1)/2 сравнений а,. с а определить всез ачения в , затем, ицвертирую значения со,получить все зцачения н и по формуле (1)вычислить значения иЭлементы исходного массива А переставляются в соответствии со значениями и , такчто элемент а,. занимает в результирующеммассиве место с номером и;,В предлагаемом устройстве параллельноопределяются все значения жи а г и вычисляются все значения и;, после чего параллельно проводится перестановка элементов исходного массива, что позволяет получить высокую скорость сортировки, Процессор может эффективно выполнять также сортировку произвольного массива длины У)п.Если исходный массив имеет длину йи, гдеЛ - целое и й)2, то сортировку можно вестис использованием алгоритма попарной сортировки, предварительно упорядочив подмассивы длины п, причем в пары последовательнообъединяются подмассивы в таком порядке,как это делается для элементов при использовании метода Боуза - Нельсона.Процессор кроме параллельной сортировкипри незначительных дополнениях позволяеттакже вести поиск информации, Здесь такжевозникают два случая. Первый случай - когда число элементов исходного массива непревосходит и - 1, и второй - для массивапроизвольной длины Л)а - 1.Л. При поиске в массиве С=(с, съ,с . ) все элементы массива одновременносравниваются с ключевым признаком б и формируется логический вектор Р= (оь оь ,4о), указывающий, какие элементы массива С равны б.1 О, если с,б,.1, если с=б 15Б. Поиск информации в массиве произвольной размерности И)п - 1 можно проводить последовательным применением указанной операции, однако при большой длине массива более эффективно вести поиск в предварительно упорядоченном массиве следующим образом. Каждый упорядоченный массив разбивается на а - 1 подмассивов. Составляется вектор Ь=(Ь, Ьь, Ь,), в котором Ь 15 равно крайнему справа элементу 1-го подмассива, Затем проводится сравнение всех компонент вектора Ь с признаком 6, и формируются логические векторы а и р, компоненты 20которых определяются следующим образом0, если Ь (6, /О, если Ь Л,а, 1, если Ь;)б, . 11, если Ь,( аОтметим, что а,=- 1 в(ао, а, ) (2),=(ао, а,)оР, (3)где =1,2,б=ао, Ь, =а.Формирование вектора у, показывающего,в каких подмассивах могут содержаться элементы, равные б, заключается в следующем: у=а (4) 35у;=ауЛг -(5)где =2,3 а - 1.Если у; =1 (=1,2 п - 1), значит в 40подмассиве с номеромимеются элементы, равные о.Если заранее известно, что все элементыисходного массива различны, то только одно у; равно 1 и исходный элемент содержится в подмассиве с номером , При этом, если длина 45-го подмассива не более а - 1, то поиск ведется по п, А, В противном случае 1-й подмассив разбивается на подмассивы меньшей размерности и повторяется п. Б до тех пор, пока размерность подмассива не будет меньше п, после чего выполняется п. А.Если в исходном массиве имеется несколько элементов, равных о, то наличие одной едиицы в векторе у указывает на то, что искомые элементы находятся в подмассиве, отмеиченном едицичнои компонентои у, т. е. если у, =1, то искомые элементы содержатся в подмассиве с номером . Наличие нескольких единиц в у свидетельствует о том, что искомые элементы имеются в нескольких соседних подмассивах, при этом следует найти элементы, равные о, в подмассивах, отмеченных крайними слева и справа единицами в векторе у, и если число единиц в у больше двух, то 55 остальные подмассивы, отмеченные подмасси 482749О 60 65 вами, целиком состоят из элементов, равных 6.На фиг. 1 приведен параллельный процессор для логической обработки информации, состоящий из запоминающего устройства 1 хранения исходной информации, блока 2 сравнения, блока 3 сумматоров, коммутирующей матрицы 4, запоминающего устройства 5 хранения результирующей информации, регистра- индикатора 6, преобразователя 7 и регистра- указателя 8.Устройства 1 и 5 содержат по и запоминающих ячеек 9 для хранения чисел (признаков), блок 2 сравнения - и (и - 1)/2 схем 10 сравнения двоичных чисел, блок 3 сумматоров - и и-входовых двоичных сумматоров 11,Выходы ячеек 9 устройства 1 подключенык входам схем 10 сравнения, причем выход -йячейки - к первому входу, а выход 1-й ячейки - к второму входу (ц)-й схемы сравнения(г,1 =0,1 и - 1, г(1), Каждая (ц)-я схема сравнения имеет два выхода (первый -Рвыход признака ю 1 (а а ) и второй - выход признака о,(а;, а,. ), которые соединены с входами соответствующих сумматоров11, причем на вход 1-го сумматора поступаютпервые выходы (ц) -х схем сравнения и вторые выходы О,г) -х схем сравнения. Выходкаждого г-го сумматора 11 блока сумматоровсвязан с г-м управляющим входом, а выходкаждой г-й ячейки 9 устройства 1 с г-й ячейки9 устройства 1 с г-м информационным входомкоммутирующей матрицы 4. Каждый г-й выход коммутирующей матрицы подключен квходу г-й ячейки 9 и устройства 5,Каждая (о,1)-я схема сравнения имеет дополнительный третий выход (выход признакаР ), который связан с г-м входом регистраиндикатора 6, Первый, второй и третий выходы каждой (о,1)-й схемы сравнения соединены с 1-й группой входов преобразователя 7,выходы преобразователя - с соответствующими входами регистра-указателя 8.В качестве коммутирующей матрицы можно использовать любой коммутатор, осуществйляющий произвольную перестановку и чисел,дополненный сответствующим устройством управления, которое выполняет настройку коммутатора в соответствии с сортирующим вектором.На фиг. 2 приведена логическая схемакоммутирующей матрицы 4.Эта матрица содержит и дешифраторов 12,и групп клапанов 13, причем количество клапанов в каждой группе равно разрядностиячейки 9, и и и-входовых групповых схемИЛИ 14, причем каждая групповая схемаИЛИ 14 включает в себя и-входовых схемИЛИ, число которых в группе равно разрядности ячейки 9.Вход каждого дешифратора 12 соединен свыходом соответствующего сумматора 11 блока сумматоров 3. и -й выход и, = (0,1и - 1) каждого г-го дешифратора 12 подклю 5 20 25 30 35 40 45 50 55 чен к управляющему входу соответствующей группы клапанов 13, информационный вход которой связан с выходом -и ячейкп 9 устройства 1, Выходы групшя клапанов 13, управляющие входы которых подключены к и, -м выходам дешифторов, соединены с входами иг -й групповой с.;емы ИЛИ 14, выход которой подключен к входу и,. -й ячейки устройства 5.Сортировку выполняют следующим образом. Исходный массив записывается в ячейки 9 устройства 1. Каждая (,1)-я схема 1 О сравнения определяет значение функций со 1 (а а и о, (аг, а ), которые вырабатываются соответственно на первом и втором выходах этой схемы. Все схемы сравнения работают параллельно, Каждый -Й сумматор 11 блока сумматоров 3 вычисляет сумму ипоступающих на его входы единиц. Ня ыходе блока сумматоров формируется сортпрующпй вектор й. Все сумматорь 11 1)аботаютКоммутирующая матрица 4 параллельно выполняет перестановку всех чисел исходного массива, поступающих на информационные входы матрицы 4 с ячеек 9 устройства 1, в соответствии с вычисленным в блоке 3 сумматоров сортирующим вектором, проходящим пя управляющие входы матрицы 4, Результирующий упорядоченный массив с выхода коммутирующей матрицы записывается в ячейки 9 устройства 5.Если число, поступаюгцее на вход -го дешифратора 12 с выхода г-го сумматора 11. равно и то на и, -м выходе этого дсшнфрятора появляется единица и число из -й ячейки 9 устройства 1 через соответствуннцую группу клапанов 13 и соответствующую групповую схему ИЛИ 14 попадает ня и; -и ячейку 9 устройства 5.Поиск элемента в массиве длины и - 1 про водят следующим образом.Ключевой признак б записывается в 0-к 1 ячейку 9 устройства 1, элементы мясснн; в 1 - (и - 1) ячейки 9 устройства 1. Сряв ение значений этих элементов массива с П 1 м 1 зняком б идет параллельно на (0,)-ных схемах 10 сравнения, на третьих выходах которых формируется элемент г,. =1, если а; =о. В ре гистр-индикатор 6 записывается вектор г по казывающий, какие компоненты массцвя ряв ны 6. Поиск подмассива, в котором содеркят ся элементы, равные б, осуществляется следующим образом. Признак 6 записывается в 0-ю ячейку, а вектор 6 - в 1 в (и - 1) ячейки 9 устройства 1. Сравнение всех компонентов вектора г с признаком б выполняется паря;1 лельно на (О,у)-х схемах сравнения. Вектор у формируется в преобразователе 7 в соответствии с формулами (2 - 5) и записывается в регистр-указатель 8, содержимое которого, таким образом, показывает в каких подмасспвах имеются элементы равные 6.Параллельный процессор для логической обработки информации, содержащий состоящее из а ячеек запоминающее устройство хранения исходной информации, п (и - 1)2 схем сравнения двоичных чисел, и двоичных сумматоров, коммутирующую матрицу, запоминающее устройство хранения результирующей информации, состоящее из а ячеек, (и - 1) - разрядный регистр-индикатор, логический преобразователь и (и - 1) - разрядный регистр-указатель, отличающийся тем, что, с целью повышения быстродействия процессора, выход 1-й ячейки запоминающего устройства хранения исходной информации подключен к первому входу, а выход-й ячейки - к второму входу (ц)-й схемы сравнения (ц= 80,1 и - 1, (1), входы каждого ко двоичного сумматора подключены к первым выходам (1,1)-х схем сравнения и к вторым выходам (р) -х схем сравнения, выход каждого 5 двоичного сумматора подключен к соответствующему управляющему входу коммутирующей матрицы, информационные входы которой соединены с выходами ячеек запоминающего устройства хранения исходной информации, а 10 информационные выходы - с входами ячеекзапоминающего устройства хранения результирующей информации, третий выход каждой (0,1)-й схемы сравнения соединен с 1-м входом регистра-указателя, а выходы каждой 15 (0,1)-й схемы сравнения соединены с 1-й группой входов логического преобразователя, выходы которого подключены к соответствующим входам регистра-указателя.482749 Фиг,орректор Е. Хмелева Заказ 1613 И ЦНИИПИ Го 1 зе 1743 Тираж 679арственного комитета Совета Министров СССРо делам изобретений и открытийМосква, Ж, Раушская наб., д. 4/5 дписное МОТ, Загорский филиа Составитель И. фирсовактор И. Грузова Техред 3, Тараненко