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

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИ ЕТЕЛЬСТВУ(22) Заявлено 051179 (21) 2837248/18-24с присоединением заявки йо(51)М. Кл. 6 Об Г 7/38 С 11 С 11/14 Государственный комитет СССР по деедам изобретений н открытий(088. 8) Дата опубликования описания 2 Ы 0.81 г(71) Заявитель нститут электронных управляющих машин АССОЦИАТИВНЫЙ ПАРАЛЛЕЛЬНЫЙ ПРОЦЕССО параллельржащий реи, блоки вылогических енты 13. является его те 20 Изобретение относится к вычислительной технике и может быть использо" вано при построении устройств обработки дискретной информации.Известен ассоциативныйный процессор (АПП), содегистры хранения информациполнения арифметических иопераций, логические элемНедостатком этого АППсложность.Наиболее близким по технической сущности к предлагаемому является АПП, который содержит магнитоодноосную пленку, на которой размещены регистры 15 хранения информации, соединенные через элементы выборки с блоком выполнения логических и арифметическихопераций 21Однако параллельность выполнения операций и известном процессе достигается только за счет параллельного соединения пленок из магнитоодноос-. ного материала. В самой же пленке информация обрабатывается последова тельно по словам и битам. Это значительно увеличивает время обработки информации. Топологическая структура каждой магнитоодноосной пленки состоит из большого количествараз ного рода логических, переключательных и запоминающихэлементов, соединенных комбинационным методом. Каждый кристалл содержит большое количество выводов токовых шин. Все это усложняет изготовление и эксплуатацию такого АПП.Цель.изобре ния - упрощение известного АПП.Поставленная цель достигается тем, что он содержит многофункциональные логические элементы и замкнутый регистр связи, регистры хранения информации расположены на магнитоодноосной пленке в виде матрицы, вдоль столбцов которой расположены замкнутый регистр связи, первые и третьи входы и выходы многофункциональных логических элементов, расположенных между столбцами матрицы соединены с парами регистров хранения, расположенных в одноименных строках двух соседних столбцов матрицы, а вторые входы и выходы - с замкнутым регистром связи, а первые и третьи входы и выходы многофункциональных логических элементов, расположенных между строками матрицы, соединены с парами регистров хранения одноименных столб. цов двух соседних строк матрицы.На фиг.1 изображена блок-схемапредложенного АПП; на фиг.2-4 - принцип его работы.Предложенный АПП содержит магнитоодноосную пленку 1, на которой размещены регистры 2 хранения информации, соединенные между собой припомощи многофункциональных логических элементов 3, замкнутый регистр 4связи, генератор 5 и датчик б считывания цилиндрических магнитных доменов (ЦМД), блок 7 управления записьюинформации (БУЗ), соединенный с генератором ЦМД 5, блок 8 управления считыванием (БУС), соединенный с датчиком 6 считывания ЦМД, блок 9 управления,режимом работы АПП (БУР), соединенный с токопроводящими шинами 10и 11.АПП работает следующим образом.В регистры хранения длиной 2 К разрядов помещается информация предназначенная для обработки. Регистр 4связи доставляет информацию во всерегистры хранения, а также содержитинформацию, предназначенную для управления работой многофункциональныхлогических элементов АПП,Блок 7 управления записью заполняет регистр 4 связи таким образом,что каждое слово информационной последовательности (фиг.2), принадлежащее столбцам АПП, т.е. слова (1+М)информационных блоков (1+й) каждогостолбца, подводятся к соответствующему.логическому элементу 3.После того как БУЗ заполняет регистры хранения, выдается сигнал вблок 9 управления режимом работы(БУР). БУР формирует импульсы токав шину,5 (Фиг.З) многофункциональных логических элементов 3, располо 1 фженных между столбцами матрицы регистров хранения, При подаче импульса тока в шину 5 ЦМД, находящиеся вэтот момент времени в замкнутомрегистре 4 связи, перейдут в регистры 2 хранения.Следует отметить, что все многофункциональные логические элементы 3,используемые в АПП, имеют одну топологию и содержат две токопроводящиешины. В зависимости от полярности иамплитуды импульса, подаваемого в одну шину или в обе шины вместе многофункциональный логический элементможет работать в шести режимах. Нафиг.3 показаны логические и переключательные функции, выполняемые элементсф. В первых двух столбцах отображены переключательные .функции, востальных логические. Строки этойтаблицы отображают функции, выполняемые в каждом канале в разных режимах.Во втором цикле операции "запись"БУЗ заполняет регистр связи управляющей последовательностью. Управляющая последовательность представляет собой цепочку слов, состоящих из 0 15 20 25 30 35 40 45 50 55 60 65"1. Количество "1" соответствуетколичеству сравниваемых разрядов,т.е. является маской.Операция ассоциативного поискапроизводится над любой парой чиселв двух соседних столбцах. Даннаяоперация включает в себя следующиережимы: поиск слова равного или,неравного заданному (=; ф;) и поиск слова, равного большему или равного меньшему из сравниваемых. Даннаяоперация производится под управлением БУР, В обоих режимах БУР Формирует одинаковые последовательностиимпульсов тока для двух петель логических элементов. В этих режимахлогический элемент выполняет функцию"равнозначность" с маскированиемпо каналу У. По окончании операцииассоциативного поиска в каждой паререгистров хранения, там где находились сравниваемые слова, останутся слова, равные большему из сравниваемых. Для определения меньшего илиравного числа, необходимо произвестианализ управляющей последовательности. Анализ производится в блоке управления считыванием (БУС) послеоперации "считывания",Операция "считывание" может бытьсовмещена с операцией "запись". Вовремя выполнения этой операции БУР 9включает логические элементы 3 навыполнение режима переключения. ЦМДиз регистров 2 хранения в регистр 4связи, а БУЗ в это время заполняетрегистр связи новой информацией,Через К-тактов БУР прекращает подачуимпульсов считывания и выдает сигнал в БУС. БУС принимает информациюот АПП, формирует информационныеблоки и производится анализ управляющей информации. Анализ управляющейинформации заключается в следующем.Считываемая с АПП информация поступает в БУС последовательно бит .забитом иэ регистров связи. Первым всегда поступает блок управляющей.информации Б 1 (Фиг.4), преобразованнойпосле выполнения операции ассоциативного поиска. Каждое слово блокаБ 1 содержит информацию о результатесравнения слов (М)-го столбца, находящихся вблоке Б 2 (Фиг.4) н слов,находящихся в соседнем М-ом столбцематрицы регистров хранения,При выполнении режима простого ассоциативного поиска (=; ф;) необходимо определить, имеется ли в каждом слове блока Б 1 хотя бы один битравный "Оф. Если в слове М, например,есть бит, равный "О", это означаетчто слово 1 блока Б 2 (фиг.4) не равно слову, оставшемуся в столбце й,находящемся в матрице регистров хранения рядом со столбцом М, из ко- фторого был выбран блок информации Б 2.Для выполнения режима сложногоассоциативного поиска необходимо проанализировать тот разряд одного из сравниваемых чисел, в котором соответствующий разряд слова управляющей последовательности равен нулю. Сравнение слов происходит старшими разрядами вперед, поэтому по первому. несовпадающему разряду. можно определить какое из сравниваемых слов меньше. После проведения операции ассоциативного поиска в регистрах 2 хранения остаются числа, равные боль шему из сравниваемых.Операция "инверсия" предназначается для получения инверсии чисел, находящихся в регистрах хранения. Для выполнения этой операции БУР 9 должен включить логические элементы 15 на ассоциативный поиск, но сравнение нужно производить со словами, все разряды которых равны "Оф. Результат операции, т.е. инверсные числа, поступают в регистр 4 связи. 20 В дальнейшем, они могут быть считаны с кристалла или переписаны в другие регистры хранения на том же .кристалле.25Операция "сложение по модулю два" предназначается для поразрядного сложения по модулю два чисел, находящих ся в соседних столбцах матрицы регистров хранения. Для выполнения этой опера- Зции БУР 9 формирует импульсы тока полярности, противоположной той, которая подается в логические элементы 3 при ассоциативном поиске.Операция "перемещения" информации осуществляется. как по столбцам, так и по строкам матрицы регистров хранения. При этом БУР 9 вырабатывает две последовательности импульсов тока для режимов поэтапного переключения ЦМД из регистра 2 хранения в 40 регистр 4 связи и из регистра связи в регистр хранения другого столбца строки) . При этом на переключение тратится один период поля управ.- ления, т.е. один такт работы АПП. , 45Алгоритм сложения требует совмещения двух операций: сложения по модулю два и операции перемещения информации по столбцам матрицы регистров хранения. Полная сумма каждой пары складываемых положительных чисел появится на выходе К+1-го многофункционального логического элемента 3, начиная от элемента, расположенного между регистрами, в которых находились слагаемые (К-число разрядов складываемых слов) . Поразрядная полусумма продвигается по замкнутому регистру 4 связи, а частичные переносы по регистрам 2 хранения, щ 0 расположенным по столбцам и соединенным между собой многофункциональными логическими элементами,работающими в режиме переключения. Задержка распространения переноса осуществля- д ется за счет переключения ЦМД из одного регистра хранения в другой.Алгоритм умножения состоит в последовательном суммировании частичных произведений со сдвигом одного из сомножителей. Возможно применение ускоренных алгоритмов умножения.Алгоритм вычитания требует, совме. - щения операций финверсиями, "сложение по модулю два" и "перемещение". Он отличается от алгоритма сложения только необходимостью инвертировать знак вычитаемого.Таким образом, предложенный АПП позволяет производить необходимый набор логических, арифметических и ассоциативных операций над каждой парой хранимых в АПП слов одновременно. Полный ассоциативный поиск ); (; =; ф ;) осуществляется за один проход двух сравниваемых слов через многофункциональный логический элемент. Простота и однородность структуры АПП достигается за счет применения одного типа многофункционального логического элемента, топологическая структура которого позволяет внедрять его непосредственно в доменопродвигающую структуру регистров хранения, а многофункциональность позволяет выполнять полный набор логических, переключательных и ассоциативных операций. Все это позволяет уменьшить время обработки информации, упростить топологию каждой магнитоодноосной пленки и увеличить надежность АПП в целом.формула изобретенияАссоциативный параллельный процессор, содержащий магнитоодноосную пленку, на.которой размещены регистры хранения информации, соединенный через элементы выборки с блоком выполнения логических и арифметических операций, о т л и ч а ю щ и й.с я тем, что, с целью упрощения ассоциативного параллельного процессора и увеличения его быстродействия, он содержит многофункциональные логические элементы и замкнутый регистр.связи, регистры хранения информации расположены на магнитоодноосной пленке в виде матрицы, вдоль столбцов которой расположены замкнутый регистр связи, первые и третьи выходы и входы многофункциональных логических элементов, расположенных между столбцами матрицы, соединены с парами регистров хранения, расположенных в одноименных строках двух соседних столбцов матрицы, а вторые входы и выходы - с замкнутым регистром связи, а первые и третьи входы и выходы многофункциональных логических элементов, расположенных между строками матрицы, соединены с парами регистров .хранения одноименных столбцовдвух соседних строк матрицы. Источники информации,принятые во внимание при экспертизе1. Т. КеппесЬ ес а 1., "Сопр.5 пгч."ч,7, Р 4, 1975,2, Авторское свидетельство СССРР 495664, кл, С 06 Г 7/38, 1974875377 00 - -0 Составитель Ю. РозентальТехред С.Мигунова Корректор М, Демчи Волкова едакто 8 исн Заказ 9335 Патент", г.ужгород, ул.Проектная, 4 лиал Тираж НИИПИ Государст по делам иэобр 13035, Москва, нного ком ений и от 35, Раушс Подтета СССРрытийая наб., д.4