Ассоциативный параллельный процессор

Ассоциативный параллельный процессор

Иллюстрации

Показать все

Реферат

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКРМУ СВИ ЕТЕЛЬСТВУ

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

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

Республик .

<>875377 (63) Дополнительное к авт. саид-ву (22) Заявлено 05.1179 (21) 2837248/18-24 с присоединением заявки ¹ (23) Приоритет (51)М. Кл.

G 06 F 7/38

G 11 С 11/14

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

СССР по дедам изобретений н открытий

Опубликовано 23.10.81. Бюллете< ¹ 39 (53) УДК 681 327.66 (088. 8) Дата опубликования описания 23,10.81

Институт электронных управляющих машин (71) Заявитель (5 4 ) АССОЦИАТИВНЫЙ ПАРАЛЛЕЛЬНЫЙ ПРОЦЕССОР

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

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

Недостатком этого АПП является его сложность

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

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

Цель. изобретения — упрощение известного АПП.

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

875377

На фиг.1 изображена блок-схема предложенного AIIII; на фиг.2-4 — принцип его работы.

Предложенный АПП содержит магнитоодноосную пленку 1, на которой размещены регистры 2 хранения информа ции, соединенные между собой при помощи многофункциональных логических элементов 3, замкнутый регистр 4 связи, генератор 5 и датчик б считывания цилиндрических магнитных доменов (ЦМД), блок 7 управления записью информации (БУЗ), соединенный с генератором ЦМД 5, блок 8 управления считыванием (БУС), соединенный с датчиком 6 считывания ЦМД, блок 9 управления.режимом работы АПП (БУР), соединенный с токопроводящими шинами 10 и 11.

AIIII работает следующим образом.

В регистры хранения длиной 2К разрядов помещается информация предназначенная для обработки. Регистр 4 связи доставляет информацию во все регистры хранения, а также содержит информацию, предназначенную для управления работой многофункциональных логических элементов АПП, Блок 7 управления записью заполняет регистр 4 связи таким образом,,что каждое слово информационной последовательности (фиг.2), принадлежащее столбцам AIIII, т.е. слова (1+М) информационных блоков (1+Й) каждого столбца, подводятся к соответствующему логическому элементу 3.

После того как БУЗ заполняет регистры хранения, выдается сигнал в блок 9 управления режимом работы (БУР). БУР формирует импульсы тока в шину .5 (фиг.3) многофункциональных логических элементов 3, располо(у женных между столбцами матрицы регистров хранения. При подаче импульса тока в шину 5 ЦМД, находящиеся в этот момент времени в замкнутом регистре 4 связи, перейдут в регистры 2 хранения.

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

Во втором цикле операции "запись"

БУЗ заполняет регистр связи управляющей последовательностью. Управляющая последовательность представляет собой цепочку слов, состоящих из (О

"1 . Количество "1" соответствует количеству сравниваемых разрядов, т.е. является маской.

Операция ассоциативного поиска производится над любой парой чисел в двух соседних столбцах. Данная операция включает в себя следующие режимы: поиск слова равного или,не равного заданному (=; ф;) и поиск слова, равного большему или равного меньшему из сравниваемых. Данная операция производится под управлением БУР. В обоих режимах БУР формирует одинаковые последовательности импульсов тока для двух петель логических элементов. В этих режимах логический элемент выполняет функцию

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

Операция "считывание" может быть совмещена с операцией "запись". Во время выполнения этой операции БУР 9 включает логические элементы 3 на выполнение режима переключения ЦМД из регистров 2 хранения в регистр 4 связи, а БУЗ в это время заполняет регистр связи новой информацией.

Через К-тактов БУР прекращает подачу импульсов считывания и выдает сигнал в БУС. БУС принимает информацию от АПП, формирует информационные блоки и производится анализ управляющей информации. Анализ управляющей информации заключается в следующем.

Считываемая c AIIII информация поступает в БУС последовательно бит .за битом иэ регистров связи. Первым всегда поступает блок управляющей.информации Б1 (фиг.4), преобразованной после выполнения операции ассоциативного поиска. Каждое слово блока

Б1 содержит информацию о результате сравнения слов (N-1)-го столбца, находящихся в блоке Б2 (фиг.4) н слов, находящихся в соседнем М-ом столбце матрицы регистров хранения.

При выполнении режима простого ассоциативного поиска (=; ф;) необходимо определить, имеется ли в каждом слове блока Б1 хотя бы один бит равный "0". Если в слове М, например, есть бит, равный "0", это означает что слово 1 блока Б2 (фиг.4) не рав-. но слову, оставшемуся в столбце й, находящемся в матрице регистров хранения рядом со столбцом N-1, из которого был выбран блок информации Б2.

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

Операция "инверсия" предназначается для получения инверсии чисел, находящихся в регистрах хранения.

Для выполнения этой операции БУР 9 должен включить логические элементы на ассоциативный поиск, .но сравнение нужно производить со словами, все разряды которых равны "О". Pe" зультат операции, т.е. инверсные числа, поступают в регистр 4 связи. 20

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

Операция "сложение по модулю два" предназначается для поразрядного сложения по модулю два чисел, находящих ся в соседних столбцах матрицы регистров хранения. Для выполнения этой опера- З 1 ции БУР 9 формирует импульсы тока полярности, противоположной той, которая подается в логические элементы 3 при ассоциативном поиске.

Операция "перемещения" информации осуществляется как по столбцам, так и по строкам матрицы регистров хранения. При этом БУР 9 вырабатывает две последовательности импульсов тока для режимов поэтапного переключения ЦМД из регистра 2 хранения в 40 регистр 4 связи и из регистра связи в регистр хранения другого столбца (строки) . При этом на переключение тратится один период поля управ.ления, т.е. один такт работы АПП., 45

Алгоритм сложения требует совмещения двух операций: сложения по модулю два и операции перемещения информации по столбцам матрицы регистров хранения. Полная сумма каждой пары складываемых положительных чисел появится на выходе К+1-ro многофункционального логического элемента 3, начиная от элемента, расположенного между регистрами, в которых находились слагаемые (К-число разрядов складываемых слов) . Поразрядная полусумма продвигается по замкнутому регистру 4 связи, а частичные переносы по регистрам 2 хранения, д» расположенным по столбцам и соединенным между собой многофункциональными логическими элементами,работающими в режиме переключения. Задержка распространения переноса осуществля- д ется за счет переключения ЦМД из одного регистра хранения в другой.

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

Алгоритм вычитания требует, совме.— щения операций "инверсия", "сложение по модулю два" и "перемещение".

Он отличается от алгоритма сложения только необходимостью инвертировать знак вычитаемого.

Таким образом, предложенный AIIII позволяет производить необходимый набор логических, арифметических и ассоциативных операций над каждой парой хранимых в AIIII слов одновременно. Полный ассоциативный поиск (); (; =; ф ;) осуществляется за один проход двух сравниваемых слов через многофункциональный логический элемент. Простота и однородность структуры АПП достигается за счет применения одного типа многофункционального логического элемента, топологическая структура которого позволяет внедрять его непосредственно в доменопродвигающую структуру регистров хранения, а многофункциональность позволяет выполнять полный набор логических, переключательных и ассоциативных операций. Все это позволяет уменьшить время обработки информации, упростить топологию каждой магнитоодноосной пленки и увеличить надежность Allll в целом.

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

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

Фиг. 1 ров .хранения одноименных столбцов двух соседних строк матрицы.

Источники информации, принятые во внимание при экспертизе

1. Т. Kenneth ес a1., "Comp Snrv

v,7, 9 4, 1975.

2. Авторское свидетельство СССР

Р 495664, кл. G 06 F 7/38, 1974 (прототип).

875377

Фиг. Я

Составитель Ю. Розенталь

Редактор Г. Волкова Техред С.Мигунова Корректор М. Демчик

Заказ 9335/74 Тираж 748 Подписное

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

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

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4