Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ
УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ

УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ

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

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2028664
Класс(ы) патента: G06F15/16
Номер заявки: 4911994/24
Дата подачи заявки: 19.02.1991
Дата публикации: 09.02.1995
Заявитель(и): Кулик Борис Александрович; Кулик Лия Ефимовна; Федоров Виктор Федорович
Автор(ы): Кулик Борис Александрович; Кулик Лия Ефимовна; Федоров Виктор Федорович
Патентообладатель(и): Кулик Борис Александрович; Кулик Лия Ефимовна; Федоров Виктор Федорович
Описание изобретения: Изобретение относится к автоматике и вычислительной технике и может быть использовано, например, для параллельной обработки данных при решении задач информационного поиска, управления базами данных и базами знаний, задач на графах, задач, возникающих при разработке и ведении экспертных систем, и задач цифровой обработки данных произвольной размерности.
Известные способы и устройства параллельной обработки частично или полностью сохранили одну из основных особенностей обработки данных на машинах фоннеймановского типа - взаимодействие с оперативной памятью осуществляется с помощью ячеек ограниченной длины (как правило, до 32 бит). Поразрядная (или вертикальная) обработка применяется либо в ограниченном объеме, либо как, например, в ассоциативных ЗУ только для решения узкого класса задач.
К недостаткам этих способов относятся:
- сложность технической реализации;
- сложность структуры вычислительных устройств, затрудняющих анализ всевозможных вычислительных ситуаций и ситуаций управления процессом вычисления;
- необходимость в разработке отдельных устройств для решения узкого класса задач;
- сложность и большая трудоемкость программно-математического обеспечения.
В статье Кулика Б.А. Быстродействующие ИПС на основе операций с логическими векторами//УС и М, 1989, N 4, с.14-19 предложен способ обработки данных, при котором основные вычислительные операции осуществляются со строками в (0,1) - алфавите (логическими векторами) произвольной размерности, ограниченной размерами прямоугольного пространства ассоциативных признаков (битовой матричной памяти). При этом в качестве основных операций с этими векторами используются элементарные логические операции: И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, проверка логического вектора на наличие или отсутствие единиц. Используя алгоритмы, предложенные в этой статье, с помощью данного способа можно осуществить быстрый поиск информации в произвольных списковых, матричных и табличных структурах данных.
Данный способ обработки может быть реализован с помощью специально для этого разработанного устройства для адресации по содержанию блока памяти, что позволяет решать, используя параллельный способ обработки, многие поисковые задачи, задачи на графах, задачи обработки изображений и т.п. При этом коэффициент увеличения быстродействия по сравнению с быстродействием решения аналогичных задач на тадиционные ЭВМ составляет n/m, где m - размерность обрабатываемых слов, n - вертикальная размерность структуры данных (списка, матрицы, таблицы и т.д.). Архитектура устройства предполагает порязрядную обработку матричной памяти по двум координатам. В соответствии с этим данное устройство в совокупности с блоком управления предложено называть биассоциативной машиной (БМ).
Недостатком данного способа и устройства является то, что с его помощью трудно реализовать циклы по подпоследовательности (т.е. циклы, в которых обработке подлежат только маркированные строки), а также такие алгоритмы цифровой обработки данных, в которых требуется подсчет сумм элементов числовых векторов. Кроме того, при реализации некоторых видов задач искусственного интеллекта (экспертные системы, базы знаний и т.д.) в данном устройстве медленно реализуется подсчет весовых коэффициентов (или вероятностных характеристик), заданных или вычисляемых ассоциативных признаков системы.
Целью предлагаемого технического решения является расширение класса решаемых задач параллельной обработки, осуществляемой с помощью однократных параллельных логических операций над логическими векторами произвольной размерности.
Цель достигается тем, что в устройство, содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов, операционный блок, дополнительно введены подблок анализатора многократных совпадений и подблок вертикального сумматора. При этом информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым входами аргумента поиска устройства, а выходы - соответственно первым и вторым адресными входами блока памяти логических векторов, входы задания режимов первого и второго блоков хранения и сравнения ассоциативных признаков и блока памяти логических векторов являются соответственно первым, вторым и третьим входами задания режимов устройства, входы начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков соединены с первым входом начальной установки устройства, второй вход начальной установки которого соединен с одноименным входом операционного блока, первый и второй выходы блока памяти логических векторов соединены соответственно с первым и вторым информационными входами операционного блока, выход и вход кода операции которого являются соответственно информационным выходом и четвертым входом задания режима работы устройства, введены подблок анализатора многократных совпадений и подблок вертикального сумматора, причем один из входов задания режима работы анализатора является пятым входом задания режима работы устройства, а другой соединен с соответствующим выходом операционного блока, третий информационный вход которого соединен с первым информационным выходом анализатора, второй выход которого соединен с первым адресным входом блока памяти, а входы задания режимов работы, информационный вход и вход начальной установки вертикального сумматора соединены с соответствующими выходами операционного блока, при этом информационный выход вертикального сумматора является четвертым информационным входом операционного блока, а первый информационный выход анализатора многократных совпадений - вторым информационным выходом устройства.
Таким образом, удается осуществить быструю реализацию циклов по маркированным строкам блока матричной памяти логических векторов за счет использования анализатора многократных совпадений, а также быструю реализацию ряда алгоритмов цифровой обработки, расчета весовых коэффициентов или вероятностных характеристик ассоциативных признаков за счет введения вертикального сумматора.
Выявленные отличительные признаки в данной совокупности не встречались в ранее известных источниках, обеспечивают достижение поставленной цели и могут быть квалифицированы как "существенные отличия".
На фиг. 1 показана функциональная схема устройства параллельной обработки данных; на фиг.2 - функциональная схема операционного блока; на фиг. 3 - функциональная схема анализатора многократных совпадений; на фиг. 4 - функциональная схема блока вертикального сумматора; на фиг. 5 - временная диаграмма сигналов задания режима "Операция".
Устройство для параллельной обработки данных содержит блоки 11 и 12хранения и сравнения ассоциативных признаков, блок 2 памяти логических векторов, операционный блок 3, подблок 4 анализатора многократных совпадений, подблок 5 вертикального сумматора, выход 51, входы 64-66задания режима работы, вход 71 начальной установки. Блоки 11, 12, 2 полностью соответствуют прототипу как в схемном, так и в функциональном отношении.
В операционный блок 3 по сравнению с прототипом введены незначительные схемные (коммутационные) изменения в связи с подключением к нему подблоков 4 и 5, но в функциональном отношении соответствует прототипу.
Подблок 4 анализатора многократных совпадений функционально совпадает с одноименным устройством, приведенным в кн.Т.Кохонен, Ассоциативные запоминающие устройства (М.: Мир, 1982, с.167, рис. 3.8). Он логически связан с блоком 3 (фиг.2 и 3).
Подблок 5 вертикального сумматора функционально соответствует суммирующему групповому счетчику, описание и схема которого приведены в кн. Справочник по интегральным микросхемам/Под ред. Тарабрина Б.В. М.: Энергия, 1981, с.701, 704, рис. 5-190.
Наличие подблоков 4 и 5 определило две новые команды, которые подаются из блока управления в блок 3 (см.фиг. 2) на вход 66. Первая из них осуществляет быструю реализацию циклов по маркированным строкам памяти логических векторов. Обозначим эту команду БРЦ. Она инициализирует работу подблока 4.
Вторая команда осуществляет подсчет количества единиц в векторе столбца, обозначим ее Cl. Она инициализирует работу подблока 5. В связи с появлением двух новых команд расширяется по выходу и дешифратор команд 23, один из его выводов идет на вход подблока 5, а другой - на вход 4 подблока 4 (фиг.2).
Анализатор многократных совпадений, реализованный в подблоке 4 (фиг.1) и представленный схемой на фиг. 3, содержит:
- инвертор 31, на вход которого поступает сигнал БРЦ и тем самым направляет вектор информации, считанный из какого-либо столбца памяти 2 логических векторов, либо через двухвходовую сборку элементов И-ИЛИ 32 и выполняется операции БРЦ, либо через двухвходовую сборку элементов И-ИЛИ 33 и с ее выхода непосредственно в операционный блок 3:
- регистр-сдвигатель 35, в котором информация, сдвигаясь в сторону старших разрядов, сравнивается в схеме сравнения 38;
- схема сравнения 38 производит сравнение информации, поступающей из регистра-сдвигателя 35, с информацией, поступающей со входа 11;
- счетчик адреса 37, который при несовпадении информации в схеме сравнения 38 при каждом такте работы увеличивает содержимое адреса на единицу и, обращаясь к регистру адреса 36 и дешифратору адреса 34, выбирает следующий вектор-строку и т.д.
Следует отметить, что подблок 4 включен в разрядные цепи векторов-столбцов блока 2.
Вертикальный сумматор, реализованный в подблоке 5 (фиг.1), и представленный функционально схемой (фиг. 4), содержит:
- приемный регистр 40 для приема логического вектора;
- регистр-сдвигатель 41, который осуществляет сдвиг в сторону старших разрядов;
- счетный триггер 42;
- двоичный счетчик 43.
Режим "Запись" соответствует алгоритму, приведенному в прототипе.
В алгоритме режима "Операция" с учетом появления подблоков 4 и 5 и расширения функциональных возможностей устройства вносятся по сравнению с прототипом некоторые дополнения.
Предположим, необходимо считать произвольный вектор-столбец. По наличию единиц в его разрядах выбрать соответствующие вектор-строки. Произвести с элементами этих векторов строк операции, определяемые операционным блоком 3. Далее подсчитать сумму единиц произвольно выбранного вектор-столбца, используя подблок 5.
Тогда устройство выполняет эту операцию следующим образом: на вход 71 "Начальная установка" операционного блока 3 подается импульсный сигнал начальной установки. Помимо начальной установки всех схем устройства параллельной обработки данных происходит занесение единицы в схему совпадения 38 через вход 11 блока 4. После окончания действия сигнала начальной установки УУ считывает вектор-столбец по произвольному адресу и подает его на вход двухвходовой сборки элементов И19 блока 3. Одновременно на вход 66 блока 3 подается сигнал БРЦ, а на вход 64 - сигнал "Чтение столбца", который разрешает прохождение считанного вектор-столбца через сборки элементов И19 блока 3 на вход 6 подблока 4. Сигнал БРЦ, дешифруясь в дешифраторе команд 23 блока 3, поступает на вход 4 подблока 4 и далее на вход 1 сборки элементов ИЛИ 32, разрешая прохождение вектор-столбца на регистр-сдвигатель 35 подблока 4 и в инвертируемом виде - на вход 2 сборки элементов ИЛИ 33, запрещая прохождение вектор-столбца на выход 5 подблока 4. Далее вектор-столбец сдвигается в сторону старших разрядов регистра-сдвигателя 35 подблока 4. Таким образом, все разряды вектора-столбца проходят через старший разряд регистра-сдвигателя 35. При каждом сдвиге на один разряд заряжается на единицу счетчик адреса строк 37 подблока 4. Когда в старшем разряде регистра-сдвигателя 35 появляется единица, происходит срабатывание схемы совпадения 38 подблока 4, информационный вход которой соединен со старшим разрядом регистра-сдвигателя 35. При этом сигнал совпадения с выхода схемы совпадения 38, поступая на установочный вход счетчика адреса строк 37, разрешает занесение значения счетчика 37 на регистр адреса строк 36 подблока 4, дешифратор адреса строк 34 подблока 4 и через выход 3 подблока 4 на разрядные координаты векторов-строк блока 2, выбирая вектор-строку по определенному адресу. Одновременно УУ посылает сигнал "Чтение строки" на вход 65 блока 3 и один из кодов операций, например, "Логическое сложение" на вход 66 блока 3. Происходит подача вектора-строки на вход 2 блока 3, который проходит открытую сигналом "Чтение строки" сборку элементов 20, 21 и поступает в узел логических операций 26 блока 3. Далее выполняется логическая операция "Логическое сложение" в полном соответствии с прототипом. По окончании выполнения операции "Логическое сложение" возобновляется сдвиг вектора-столбца в регистре-сдвигателе 35 до появления в его старшем разряде следующей единицы, и весь процесс повторяется. Этот цикл повторяется до тех пор, пока младший разряд вектора-столбца, сдвигаясь, не окажется в старшем разряде регистра-сдвигателя 35 подблока 4. После этого вновь на вход 71"Начальная установка" операционного блока 3 подается импульсный сигнал начальной установки. На этом первая часть режима "Операция" заканчивается.
Производится подсчет числа единиц в произвольном векторе-столбце. Происходит это следующим образом.
После подачи на вход 71 "Начальная установка" сигнала начальной установки он по входу 10 проходит на триггер 42 и счетчик 43 подблока 5 и сбрасывает их в исходное состояние. По команде СI и команде "Чтение столбца" из дешифратора команд 23 через вход 7 подблока 5 на приемный регистр поступает сигнал, разрешающий подачу вектора-столбца из приемного регистра 40 в регистр-сдвигатель 41. Триггер 42 соединен со старшим разрядом регистра-сдвигателя 41. По мере сдвига вектора-столбца через регистр-сдвигатель 41 триггер реагирует только на наличие в этом разряде единицы. При наличии единицы в старшем разряде регистра-сдвигателя 41 триггер 42 срабатывает и заряжает счетчик 43 на единицу. При наличии в старшем разряде регистра сдвигателя нуля триггер остается в предыдущем состоянии, счетчик не заряжается. Таким образом, счетчик подсчитывает количество числа единиц в векторе-столбце и передает это в УУ.
Временная диаграмма сигналов задания режима приведена в прототипе на фиг. 5 и соответствует данной заявке на изобретение, а временная диаграмма сигналов задания режима "Операция", приведена на фиг. 5.
Чтобы объяснить вычислительные возможности устройства, необходимо привести основные положения программно-математического обеспечения биассоциативной машины.
Основными структурными единицами в существующих системах накопления, поиска и сортировки нечисловой и смешанной информации являются аналоги речевых структур, т. е. литеры, сочетания литер, слова, идентификаторы, представления чисел и т.д. При вводе и выводе информации эти структурные единицы бузусловно необходимы, но целесообразность их использования в качестве основных промежуточных элементов в процессе машинной реализации параллельных операций вызывает сомнение. Эффективное применение поразрядной обработки матричных структур и использование естественного параллелизма данных, очевидно, во многом зависит от выбора основных структурных единиц при обработке данных и от такой организации вычислений, при которой аналоги речевых структур по возможности не используются в качестве промежуточных результатов. С учетом этого целесообразно ввести в качестве основных структурных единиц элементы, соответствующие архитектуре БМ. К ним, в частности, относятся:
- последовательности М (строковых) и N (столбцовых) адресов;
- R - слова, слова и подслова;
- подпоследовательности.
Последовательности M и N являются множествами последовательных адресов соответствующих "битовых срезов" матричной памяти. По составу элементов (целых чисел) они могут пересекаться и даже совпадать.
R-слово - строка или столбец из нулей и единиц, размерность которых равна размерности соответствующей координаты матричной памяти. Слово или подслово - непрерывная часть R-слова.
В слове могут быть закодированы в (0,1) - алфавите числа, литеры, их последовательности или их части.
Подпоследовательности Р (Ri) определяются произвольным R-словом Riи представляют подмножество адресов или связанных с ними идентификаторов, соответствующих единицам R-слова Ri. Другими словами, при определении подпоследовательности считают, что произвольные R-слова являются характеристическими векторами каких-либо подмножеств М или N, или связанных с ними идентификаторов.
Вводят обозначения: R-слова будут обозначаться Ri, RNi (если они находятся в i-м регистре соответствующего процессорного модуля) и СМi, CNi (если они находятся в соответствующих адресам Mi и Ni строках или столбцах матричной памяти). Для обозначения слов вводятся дополнительно еще два индекса (j, k), которые обозначают начальные и конечные разряды слова в данном R-слове, т.е. Ri(j,k), CMi(j,k), CNi(j,k) являются словами в соответствующих R-словах.
Если данные в матричной памяти представлены в виде таблицы и для каждого элемента заголовка таблицы определены начальные и конечные разряды, т.е. слово в произвольном R-слове определяется идентификатором элемента заголовка, например Ri(B), CNi(GP) и т.д. В дальнейшем считают, что СКi- R-слово произвольной координаты.
Рассмотрим основные элементарные операции в БМ.
1) Ri ==CKi - пересылка строки или столбца матричной памяти с адресом Kj в регистр соответствующего процессорного модуля.
2) CKj= =Ri - запись R-слова, содержащегося в регистре, в столбец (или строку) матричной памяти с адресом Kj.
элементарные логические операции с R-словами, находящимися в регистрах определенного процессорного модуля: .NOT. - НЕ, OR. - ИЛИ, .AND. - И,. XOR. - ИСКЛ.ИЛИ.
4) Ri==Rj - пересылка R-cлова из регистра в регистр.
5) Ri==0 - "чистка" регистра, т.е. запись нуля во все разряды регистра.
6) Ri==0: - проверка нуля. Эта операция осуществляет проверку условия; во всех ли разрядах регистра нули или имеется хотя бы один разряд с единицей.
Помимо перечисленных операций в БМ целесообразно реализовать два вида циклов:
1) цикл по слову, в котором загрузка R-слова в процессорный модуль и реализация однотипных операций над ними производится последовательно по заданному подслову адресов M(j,k) или N(j,k), где j и k - соответственно начальный и конечный адреса подслов;
2) цикл по подпоследовательности, в котором загрузка R-слов и операции над ними производятся по подпоследовательности P(Ri).
Для быстрой реализации циклов по подпоследовательности в процессорный модуль вводится последовательный анализатор многократных совпадений, в котором последовательно по возрастанию адресов вводятся в действие активные разряды одного из регистров процессорного модуля, содержащего R-слово Ri.
Управляющее устройство (УУ) представляет собой обычную мини- или микроЭВМ, в которой предусмотрена возможность использования проблемно ориентированного языка (в данной работе используется часто встречающееся подмножество языка ПАСКАЛЬ с некоторым расширением для обозначения вышеописанных операций с R-словами).
В ст. Кулика Б.А. "Быстродействующие ИПС на основе операций с логическими векторами" приведен ряд алгоритмов, позволяющих организовать поиск в произвольной таблице. Список этих алгоритмов и оценка их вычислительной сложности приведены в таблице. При оценке сложности алгоритмов используются следующие обозначения:
0 - обозначение функции сложности;
m - число разрядов битового представления элемента массива;
k - число полей в таблице данных.
Для приведенных в таблице алгоритмов, вычислительная сложность не зависит от числа элементов массива или числа записей в таблиц данных при условии, что это число не превышает соответствующей размерности матричной памяти.
Рассмотрим некоторые неопубликованные алгоритмы и способы их реализации на предлагаемом устройстве, позволяющие использовать его для решения задач быстрой цифровой обработки данных векторного и матричного типов. Одним из основных алгоритмов цифровой обработки является алгоритм расчета векторной суммы. Рассмотрим вначале эту операцию для множества чисел без знака, представленных в формате с фиксированной точкой.
Алгоритм N(i,j)==N(p,q) + d
Данные: множество m-разрядных двоичных чисел без знака, расположенных в колонке N(p, q) и m-разрядное двоичное число d, значения разрядов которого равны соответственно
dm-1, dm-2,...,d0.
Результат: множество m+1-разрядных двоичных чисел без знака, расположенных в колонке N(i,j) и представляющих сумму каждого элемента исходного вектора с числом d.
{1} R1==0;
{2} R2==0;
{3} k:==0;
{4} while k<m+1 d0
{5} begin
{6} R3==CN(q-k);
{7} if dk=0 then R4==R1 else R4==.NOT.R1;
{8} R5==R2.XOR.R3.XOR.R4;
{9} R2==(R2. AND.R3). OR. (R2.AND.R4). .OR.(R3.AND.R4);
{10} CN(j-k)==R5;
{11} k:=k+1
{12} end;
{13} CN(i)==R2.
В представленном алгоритме в строке 8 вычисляется значение текущего разряда суммы, а в строке 9 реализуется вычисление функции переноса.
В ряде случаев возникает необходимость в процессе вычисления векторной суммы оставлять без изменения подпоследовательность каких-либо элементов множества чисел, например, добавлять заданное число только к отрицательным числам колонки. Для решения этой задачи можно, в частности, воспользоваться алгоритмом
N(i, j)= = N(p,q)+d.AND.P(ri), в котором изменяется величина только тех чисел, которые маркированы вектором P(n), находящемся в одном из разрядов матричной памяти. Для решения этой задачи можно воспользоваться предыдущим алгоритмом, добавив в него после строк 2 и 7 следующие строки:
{2а} R6==P(n);
{7a} R4==R4.AND.R6.
Для учета знаков чисел, расположенных в колонках матричной памяти, целесообразно ввести знаковый разряд, расположенный как и в традиционных АЛУ, левее старшего значащего разряда. Кроме того, числа могут представляться в дополнительном и обратном кодах. Покажем, как в устройстве выполняется операция преобразования прямого кода со знаком в старшем разряде в дополнительный код.
Алгоритм СС N(i,j)
Данные: множество чисел с фиксированной точкой, представленных в прямом коде в колонке N(i,j), и m-разрядное положительное число d, представляющее наименьшее положительное число в данном формате.
Результат: исходное множество чисел, представленное в дополнительном коде в той же колонке.
{1} Ri==CN(i);
{2} for k:=i+1 t0 j d0
{3} begin
{4} R2==CN(k);
{5} R2==R2.XOR.R1;
{6} CN(k)==R2;
{7} end;
{8} N(i,j)==N(i,j)+d.AND.R1.
В данном алгоритме в зависимости от значения знакового разряда остаются неизменными или инвертируются значения текущих разрядов чисел, после чего к отрица- тельным числам прибавляется число d.
Алгоритм перевода чисел из дополнительного кода в прямой реализуется аналогично с вышеописанным, но в обратном порядке: вначале к множеству отрицательных чисел прибавляется наименьшее отрицательное число, представленное в дополнительном коде, после чего инвертируются значащие разряды отрицательных чисел.
Для векторного сложения двух множеств чисел можно использовать следующий алгоритм.
Алгоритм N(i,j)==N(p,q)+N(s,t)
Данные: два числовых вектора, представленные в дополнительном коде в m-разрядных колонках N(p,q) и N(s,t).
Результат: множество m+1-разрядных чисел, представленных в дополнительном коде, каждое из которых равно сумме двух чисел, расположенных на соответствующей строке в колонках N(p,q) И N(s,t).
{1} R1==0;
{2} k:=0;
{3} while k<m+1 d0
{4} begin
{5} R2==CN(t-k);
{6} R3==CN(q-k);
{7} R4==R1. XOR.R2.XOR.R3;
{8} R1==(R1.AND.R2).OR.(R1.AND.R3). .OR.(R2.AND.R3);
{9} CN(j,k)==R4;
{10} k:=k+1;
{11} end;
{12} R4==R1.XOR.R2.XOR.R3;
{13} CN(i)==R4.
В данном алгоритме предусматривается добавление разряда в колонку результатов для того, чтобы избежать возможных случаев переполнения при подсчете суммы двух чисел.
Зная алгоритм вычисления векторной суммы, нетрудно составить алгоритм вычисления векторного произведения. В этом случае также, как и при выполненни операций с числами, представленными в формате с плавающей точкой, необходимо осуществлять сдвиг маркированных чисел колонки. В качестве примера рассмотрим алгоритм, с помощью которого реализуется сдвиг вправо на один разряд маркированных чисел колонки.
Алгоритм RS N(i,j).ABD.P(n)
Данные: m-разрядные слова или числа, записанные в колонне N(i,j), и вектор Р(n), маркирующий строки, подлежащие сдвигу.
Результат: сдвиг на один разряд маркированных слов колонки N(i,j).
{1} R1==P(n);
{2} R2==CN(i);
{3} R3== .NOT. R1. AND. R2;
{4} CN(i)==R3;
{5} R3==CN(i+1);
{6} for k:=1 t0 m-1 do
{7} begin
{8} R2==(R1. AND.R2).OR. (.NOT. R1.AND. R3);
{9} CN(i+k)==R2;
{10} R2==R3;
{11} R3==CN(i+k+1)
{12} end.
Нетрудно убедиться, что вычислительная сложность приведенных алгоритмов не зависит от размерности вектора, если она не превышает соответствующей размерности матричной памяти.
Вычисление суммы произвольного вектора в трацидионных ЭВМ осуществляется со сложностью O(N), где N - количество элементов вектора. Введение в устройство вертикального сумматора позволяет для векторов большой размерности значительно ускорить эту операцию. Обозначим SUM(Ri) операцию суммирования единиц в регистре Ri. Если m-разрядные элементы числового вектора представлены в прямом коде в колонке N(i,j), то суммирование всех элементов этого вектора можно осуществить с помощью следующей последовательности операций (S[1. . m-1] , T[1..m-1] - промежуточные массивы целых положительных чисел):
{1} R1==CN(i); {загрузка в регистр знакового разряда}
{2} R2== .NOT .R1;
{3} for k:=i+1 t0 j d0
{4} begin
{5} R3==CN(k);
{6} R4==R1. AND. R3;
{7} S[k-1]:=SUM(R4);
{8} R4==R2. AND .R3;
{9} T[k-1]:=SUM(R4)
{10} end.
Для вычисления суммы достаточно в УУ произвести следующие вычисления:
{1} SS: =S[i]×2m-i-1
{2} TS: =T[i]×2m-i-1
{3} RES:=TS-SS.
Очевидно, что при использовании вертикального сумматора вычислительная сложность операции суммирования вектора равна O(sm), где s-вычислительная сложность операции суммирования единиц в произвольном разряде, m-число разрядов элементов вектора.
Таким образом, предлагаемое техническое решение позволяет расширить класс задач параллельной обработки, осуществляемых с помощью параллельных логических операций над логическими векторами произвольной размерности.
Формула изобретения: УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ, содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов и операционный блок, причем информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым входами аргумента поиска устройства, а их выходы соединены соответственно с первым и вторым адресными входами блока памяти логических векторов, входы режима первого и второго блоков хранения и сравнения ассоциативных признаков и вход записи-считывания блока памяти логических векторов являются соответственно первым, вторым и третьим входами режима устройства, первый вход начальной установки устройства подключен к входам начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков, второй вход начальной установки - к входу начальной установки операционного блока, первый и второй выходы блока памяти логических векторов подключены соответственно к первому и второму информационным входам операционного блока, вход кода операции устройства подключен к входу кода операции операционного блока, отличающееся тем, что, с целью расширения функциональных возможностей за счет поиска логических векторов-строк по отличительным атрибутам через циклический перебор логических векторов-столбцов, а также подсчета числа единиц в произвольно заданном векторе-столбце, оно содержит блок анализа многократных совпадений, блок подсчета числа единиц, причем второй вход начальной установки устройства подключен к входам начальной установки блока подсчета числа единиц и блока анализа многократных совпадений, первый и второй выходы которого подключены соответственно к третьему адресному входу блока памяти логических векторов и к третьему информационному входу операционного блока, первый и второй информационные выходы, выход признака операции анализа многократных совпадений и выход признака операции определения числа единиц операционного блока подключены соответственно к информационным входам блока анализа многократных совпадений и блока подсчета числа единиц, к входам синхронизации блока анализа многократных совпадений и блока подсчета числа единиц, выход которого подключен к информационному выходу устройства и к четвертому информационному входу операционного блока.