устройство для параллельной обработки данных

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

УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ, содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов и операционный блок, причем информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым входами аргумента поиска устройства, а их выходы соединены соответственно с первым и вторым адресными входами блока памяти логических векторов, входы режима первого и второго блоков хранения и сравнения ассоциативных признаков и вход записи-считывания блока памяти логических векторов являются соответственно первым, вторым и третьим входами режима устройства, первый вход начальной установки устройства подключен к входам начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков, второй вход начальной установки - к входу начальной установки операционного блока, первый и второй выходы блока памяти логических векторов подключены соответственно к первому и второму информационным входам операционного блока, вход кода операции устройства подключен к входу кода операции операционного блока, отличающееся тем, что, с целью расширения функциональных возможностей за счет поиска логических векторов-строк по отличительным атрибутам через циклический перебор логических векторов-столбцов, а также подсчета числа единиц в произвольно заданном векторе-столбце, оно содержит блок анализа многократных совпадений, блок подсчета числа единиц, причем второй вход начальной установки устройства подключен к входам начальной установки блока подсчета числа единиц и блока анализа многократных совпадений, первый и второй выходы которого подключены соответственно к третьему адресному входу блока памяти логических векторов и к третьему информационному входу операционного блока, первый и второй информационные выходы, выход признака операции анализа многократных совпадений и выход признака операции определения числа единиц операционного блока подключены соответственно к информационным входам блока анализа многократных совпадений и блока подсчета числа единиц, к входам синхронизации блока анализа многократных совпадений и блока подсчета числа единиц, выход которого подключен к информационному выходу устройства и к четвертому информационному входу операционного блока.

Описание изобретения к патенту

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

Известные способы и устройства параллельной обработки частично или полностью сохранили одну из основных особенностей обработки данных на машинах фоннеймановского типа - взаимодействие с оперативной памятью осуществляется с помощью ячеек ограниченной длины (как правило, до 32 бит). Поразрядная (или вертикальная) обработка применяется либо в ограниченном объеме, либо как, например, в ассоциативных ЗУ только для решения узкого класса задач.

К недостаткам этих способов относятся:

- сложность технической реализации;

- сложность структуры вычислительных устройств, затрудняющих анализ всевозможных вычислительных ситуаций и ситуаций управления процессом вычисления;

- необходимость в разработке отдельных устройств для решения узкого класса задач;

- сложность и большая трудоемкость программно-математического обеспечения.

В статье Кулика Б.А. Быстродействующие ИПС на основе операций с логическими векторами//УС и М, 1989, N 4, с.14-19 предложен способ обработки данных, при котором основные вычислительные операции осуществляются со строками в (0,1) - алфавите (логическими векторами) произвольной размерности, ограниченной размерами прямоугольного пространства ассоциативных признаков (битовой матричной памяти). При этом в качестве основных операций с этими векторами используются элементарные логические операции: И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, проверка логического вектора на наличие или отсутствие единиц. Используя алгоритмы, предложенные в этой статье, с помощью данного способа можно осуществить быстрый поиск информации в произвольных списковых, матричных и табличных структурах данных.

Данный способ обработки может быть реализован с помощью специально для этого разработанного устройства для адресации по содержанию блока памяти, что позволяет решать, используя параллельный способ обработки, многие поисковые задачи, задачи на графах, задачи обработки изображений и т.п. При этом коэффициент увеличения быстродействия по сравнению с быстродействием решения аналогичных задач на тадиционные ЭВМ составляет n/m, где m - размерность обрабатываемых слов, n - вертикальная размерность структуры данных (списка, матрицы, таблицы и т.д.). Архитектура устройства предполагает порязрядную обработку матричной памяти по двум координатам. В соответствии с этим данное устройство в совокупности с блоком управления предложено называть биассоциативной машиной (БМ).

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

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

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

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

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

На фиг. 1 показана функциональная схема устройства параллельной обработки данных; на фиг.2 - функциональная схема операционного блока; на фиг. 3 - функциональная схема анализатора многократных совпадений; на фиг. 4 - функциональная схема блока вертикального сумматора; на фиг. 5 - временная диаграмма сигналов задания режима "Операция".

Устройство для параллельной обработки данных содержит блоки 1₁ и 1₂хранения и сравнения ассоциативных признаков, блок 2 памяти логических векторов, операционный блок 3, подблок 4 анализатора многократных совпадений, подблок 5 вертикального сумматора, выход 5₁, входы 6₄-6₆задания режима работы, вход 7₁ начальной установки. Блоки 1₁, 1₂, 2 полностью соответствуют прототипу как в схемном, так и в функциональном отношении.

В операционный блок 3 по сравнению с прототипом введены незначительные схемные (коммутационные) изменения в связи с подключением к нему подблоков 4 и 5, но в функциональном отношении соответствует прототипу.

Подблок 4 анализатора многократных совпадений функционально совпадает с одноименным устройством, приведенным в кн.Т.Кохонен, Ассоциативные запоминающие устройства (М.: Мир, 1982, с.167, рис. 3.8). Он логически связан с блоком 3 (фиг.2 и 3).

Подблок 5 вертикального сумматора функционально соответствует суммирующему групповому счетчику, описание и схема которого приведены в кн. Справочник по интегральным микросхемам/Под ред. Тарабрина Б.В. М.: Энергия, 1981, с.701, 704, рис. 5-190.

Наличие подблоков 4 и 5 определило две новые команды, которые подаются из блока управления в блок 3 (см.фиг. 2) на вход 6₆. Первая из них осуществляет быструю реализацию циклов по маркированным строкам памяти логических векторов. Обозначим эту команду БРЦ. Она инициализирует работу подблока 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.

Тогда устройство выполняет эту операцию следующим образом: на вход 7₁ "Начальная установка" операционного блока 3 подается импульсный сигнал начальной установки. Помимо начальной установки всех схем устройства параллельной обработки данных происходит занесение единицы в схему совпадения 38 через вход 11 блока 4. После окончания действия сигнала начальной установки УУ считывает вектор-столбец по произвольному адресу и подает его на вход двухвходовой сборки элементов И19 блока 3. Одновременно на вход 6₆ блока 3 подается сигнал БРЦ, а на вход 6₄ - сигнал "Чтение столбца", который разрешает прохождение считанного вектор-столбца через сборки элементов И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, выбирая вектор-строку по определенному адресу. Одновременно УУ посылает сигнал "Чтение строки" на вход 6₅ блока 3 и один из кодов операций, например, "Логическое сложение" на вход 6₆ блока 3. Происходит подача вектора-строки на вход 2 блока 3, который проходит открытую сигналом "Чтение строки" сборку элементов 20, 21 и поступает в узел логических операций 26 блока 3. Далее выполняется логическая операция "Логическое сложение" в полном соответствии с прототипом. По окончании выполнения операции "Логическое сложение" возобновляется сдвиг вектора-столбца в регистре-сдвигателе 35 до появления в его старшем разряде следующей единицы, и весь процесс повторяется. Этот цикл повторяется до тех пор, пока младший разряд вектора-столбца, сдвигаясь, не окажется в старшем разряде регистра-сдвигателя 35 подблока 4. После этого вновь на вход 7₁"Начальная установка" операционного блока 3 подается импульсный сигнал начальной установки. На этом первая часть режима "Операция" заканчивается.

Производится подсчет числа единиц в произвольном векторе-столбце. Происходит это следующим образом.

После подачи на вход 7₁ "Начальная установка" сигнала начальной установки он по входу 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) - алфавите числа, литеры, их последовательности или их части.

Подпоследовательности Р (R_i) определяются произвольным R-словом R_iи представляют подмножество адресов или связанных с ними идентификаторов, соответствующих единицам R-слова R_i. Другими словами, при определении подпоследовательности считают, что произвольные R-слова являются характеристическими векторами каких-либо подмножеств М или N, или связанных с ними идентификаторов.

Вводят обозначения: R-слова будут обозначаться R_i, RNi (если они находятся в i-м регистре соответствующего процессорного модуля) и СМ_i, CN_i (если они находятся в соответствующих адресам M_i и N_i строках или столбцах матричной памяти). Для обозначения слов вводятся дополнительно еще два индекса (j, k), которые обозначают начальные и конечные разряды слова в данном R-слове, т.е. R_i(j,k), CM_i(j,k), CN_i(j,k) являются словами в соответствующих R-словах.

Если данные в матричной памяти представлены в виде таблицы и для каждого элемента заголовка таблицы определены начальные и конечные разряды, т.е. слово в произвольном R-слове определяется идентификатором элемента заголовка, например R_i(B), CN_i(GP) и т.д. В дальнейшем считают, что СК_i- R-слово произвольной координаты.

Рассмотрим основные элементарные операции в БМ.

1) R_i ==CK_i - пересылка строки или столбца матричной памяти с адресом K_j в регистр соответствующего процессорного модуля.

2) CK_j= =Ri - запись R-слова, содержащегося в регистре, в столбец (или строку) матричной памяти с адресом K_j.

элементарные логические операции с R-словами, находящимися в регистрах определенного процессорного модуля: .NOT. - НЕ, OR. - ИЛИ, .AND. - И,. XOR. - ИСКЛ.ИЛИ.

4) R_i==R_j - пересылка R-cлова из регистра в регистр.

5) R_i==0 - "чистка" регистра, т.е. запись нуля во все разряды регистра.

6) R_i==0: - проверка нуля. Эта операция осуществляет проверку условия; во всех ли разрядах регистра нули или имеется хотя бы один разряд с единицей.

Помимо перечисленных операций в БМ целесообразно реализовать два вида циклов:

1) цикл по слову, в котором загрузка R-слова в процессорный модуль и реализация однотипных операций над ними производится последовательно по заданному подслову адресов M(j,k) или N(j,k), где j и k - соответственно начальный и конечный адреса подслов;

2) цикл по подпоследовательности, в котором загрузка R-слов и операции над ними производятся по подпоследовательности P(R_i).

Для быстрой реализации циклов по подпоследовательности в процессорный модуль вводится последовательный анализатор многократных совпадений, в котором последовательно по возрастанию адресов вводятся в действие активные разряды одного из регистров процессорного модуля, содержащего R-слово R_i.

Управляющее устройство (УУ) представляет собой обычную мини- или микроЭВМ, в которой предусмотрена возможность использования проблемно ориентированного языка (в данной работе используется часто встречающееся подмножество языка ПАСКАЛЬ с некоторым расширением для обозначения вышеописанных операций с R-словами).

В ст. Кулика Б.А. "Быстродействующие ИПС на основе операций с логическими векторами" приведен ряд алгоритмов, позволяющих организовать поиск в произвольной таблице. Список этих алгоритмов и оценка их вычислительной сложности приведены в таблице. При оценке сложности алгоритмов используются следующие обозначения:

0 - обозначение функции сложности;

m - число разрядов битового представления элемента массива;

k - число полей в таблице данных.

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

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

Алгоритм N(i,j)==N(p,q) + d

Данные: множество m-разрядных двоичных чисел без знака, расположенных в колонке N(p, q) и m-разрядное двоичное число d, значения разрядов которого равны соответственно

d_m-1, d_m-2,...,d₀.

Результат: множество m+1-разрядных двоичных чисел без знака, расположенных в колонке N(i,j) и представляющих сумму каждого элемента исходного вектора с числом d.

{1} R₁==0;

{2} R₂==0;

{3} k:==0;

{4} while k<m+1 d₀

{5} begin

{6} R₃==CN(q-k);

{7} if d_k=0 then R₄==R₁ else R₄==.NOT.R₁;

{8} R₅==R₂.XOR.R₃.XOR.R₄;

{9} R₂==(R₂. AND.R₃). OR. (R₂.AND.R₄). .OR.(R₃.AND.R₄);

{10} CN(j-k)==R₅;

{11} k:=k+1

{12} end;

{13} CN(i)==R₂.

В представленном алгоритме в строке 8 вычисляется значение текущего разряда суммы, а в строке 9 реализуется вычисление функции переноса.

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

N(i, j)= = N(p,q)+d.AND.P(r_i), в котором изменяется величина только тех чисел, которые маркированы вектором P(n), находящемся в одном из разрядов матричной памяти. Для решения этой задачи можно воспользоваться предыдущим алгоритмом, добавив в него после строк 2 и 7 следующие строки:

{2а} R₆==P(n);

{7a} R₄==R4.AND.R₆.

Для учета знаков чисел, расположенных в колонках матричной памяти, целесообразно ввести знаковый разряд, расположенный как и в традиционных АЛУ, левее старшего значащего разряда. Кроме того, числа могут представляться в дополнительном и обратном кодах. Покажем, как в устройстве выполняется операция преобразования прямого кода со знаком в старшем разряде в дополнительный код.

Алгоритм СС N(i,j)

Данные: множество чисел с фиксированной точкой, представленных в прямом коде в колонке N(i,j), и m-разрядное положительное число d, представляющее наименьшее положительное число в данном формате.

Результат: исходное множество чисел, представленное в дополнительном коде в той же колонке.

{1} R_i==CN(i);

{2} for k:=i+1 t₀ j d₀

{3} begin

{4} R₂==CN(k);

{5} R₂==R₂.XOR.R₁;

{6} CN(k)==R₂;

{7} end;

{8} N(i,j)==N(i,j)+d.AND.R₁.

В данном алгоритме в зависимости от значения знакового разряда остаются неизменными или инвертируются значения текущих разрядов чисел, после чего к отрица- тельным числам прибавляется число 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} R₁==0;

{2} k:=0;

{3} while k<m+1 d₀

{4} begin

{5} R₂==CN(t-k);

{6} R₃==CN(q-k);

{7} R₄==R₁. XOR.R₂.XOR.R₃;

{8} R₁==(R₁.AND.R₂).OR.(R₁.AND.R₃). .OR.(R₂.AND.R₃);

{9} CN(j,k)==R₄;

{10} k:=k+1;

{11} end;

{12} R₄==R₁.XOR.R₂.XOR.R₃;

{13} CN(i)==R₄.

В данном алгоритме предусматривается добавление разряда в колонку результатов для того, чтобы избежать возможных случаев переполнения при подсчете суммы двух чисел.

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

Алгоритм RS N(i,j).ABD.P(n)

Данные: m-разрядные слова или числа, записанные в колонне N(i,j), и вектор Р(n), маркирующий строки, подлежащие сдвигу.

Результат: сдвиг на один разряд маркированных слов колонки N(i,j).

{1} R₁==P(n);

{2} R₂==CN(i);

{3} R₃== .NOT. R₁. AND. R₂;

{4} CN(i)==R₃;

{5} R₃==CN(i+1);

{6} for k:=1 t₀ m-1 d_o

{7} begin

{8} R₂==(R₁. AND.R₂).OR. (.NOT. R₁.AND. R₃);

{9} CN(i+k)==R₂;

{10} R₂==R₃;

{11} R₃==CN(i+k+1)

{12} end.

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

Вычисление суммы произвольного вектора в трацидионных ЭВМ осуществляется со сложностью O(N), где N - количество элементов вектора. Введение в устройство вертикального сумматора позволяет для векторов большой размерности значительно ускорить эту операцию. Обозначим SUM(R_i) операцию суммирования единиц в регистре R_i. Если m-разрядные элементы числового вектора представлены в прямом коде в колонке N(i,j), то суммирование всех элементов этого вектора можно осуществить с помощью следующей последовательности операций (S[1. . m-1] , T[1..m-1] - промежуточные массивы целых положительных чисел):

{1} R₁==CN(i); {загрузка в регистр знакового разряда}

{2} R₂== .NOT .R₁;

{3} for k:=i+1 t₀ j d₀

{4} begin

{5} R₃==CN(k);

{6} R₄==R₁. AND. R₃;

{7} S[k-1]:=SUM(R₄);

{8} R₄==R₂. AND .R₃;

{9} T[k-1]:=SUM(R₄)

{10} end.

Для вычисления суммы достаточно в УУ произвести следующие вычисления:

{1} SS: =S[i]2^m-i-1

{2} TS: =T[i]2^m-i-1

{3} RES:=TS-SS.

Очевидно, что при использовании вертикального сумматора вычислительная сложность операции суммирования вектора равна O(sm), где s-вычислительная сложность операции суммирования единиц в произвольном разряде, m-число разрядов элементов вектора.

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