Ассоциативная память и ассоциативные процессоры

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

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

Данная плата расширения может быть использована для повышения производительности серверов (за счет обработки информации на этапе считывания из памяти, а также уменьшения нагрузки на шины) баз данных типа ORACLE и SQL SERVER, расположенных на машинах Pentium, при этом применение платы расширения должно быть оправдано по критерию "стоимость - эффективность".

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

Использование специальных аппаратных средств для повышения производительности компьютера при выполнении узкоспециализированных задач - достаточно традиционный подход к решению проблемы. Если вспомнить историю, то в начале 80-х годов для ускорения расчетов был создан математический сопроцессор, а в середине 90-х для ускорения вывода графики - 3D ускоритель (видеопроцессор).

1.3. Ассоциативные вычислительные системы

 

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

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

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

Итак, высокая степень параллельности обработки может быть достигнута тогда, когда одноименные операции выполняются одновременно над всем множеством содержащихся в выделенном поле ассоциативной памяти слов. Для этого в состав ассоциативной вычислительной системы вводятся обрабатывающие элементы, реализующие арифметическую и логическую обработку информации. Упрощенная структура связки ассоциативная память - обрабатывающие элементы (ОЭ) представлена на рис. 1.

Рисунок 1. Упрощенная структура связки ассоциативная память - обрабатывающие элементы

 

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

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

Три 256-разрядных регистра M, X, Y составляют модуль обрабатывающих элементов. В состав каждого элементарного процессора входит по одному разряду из названных регистров. Регистр маски (М) позволяет маскировать элементы 256-разрядных кодов. Регистры X, Y и связанная с ними логика предназначены для выполнения логических операций над двумя переменными.

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

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

Рисунок 2. Ассоциативный матричный модуль

 

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

1. совместную независимую реализацию одинаковых логических функций:

2. селективную реализацию указанных функций:

при при

3. селективную и независимую их реализацию:

при при

В последнем случае для маскирования операций на регистре Х используется состояние регистра Y, в котором он находится перед модификацией посредством F.

Наиболее характерным представителем группы ассоциативных вычислительных систем является система STARAN, разработанная в США. От матричных систем, описанных ниже, она отличается не только наличием ассоциативной памяти, но и другими особенностями: ассоциативная память является памятью с многомерным доступом, т. е. в нее можно обратиться как поразрядно, так и пословно; операционные процессорные элементы предусмотрены для каждого слова памяти; имеется уникальная схема перестановок для перегруппировки данных в памяти. Основным элементом системы является многомерная ассоциативная матрица - ассоциативный модуль (АМ), который представляет собой квадрат из 256 разрядов из 256 слов, т.е, содержит в общей сложности 65536 бит данных. Для обработки информации имеется 256 процессорных элементов, которые последовательно, разряд за разрядом, обрабатывают слова. Все ПЭ работают одновременно, по одной команде, выдаваемой устройством управления. Таким образом, сразу по одной команде обрабатываются все выбранные по определенным признакам из памяти слова.

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

Базовая конфигурация системы содержит один АМ. Однако число этих модулей может варьироваться в системе от 1 до 32. Таким образом, при максимальной комплектации в системе может подвергаться ассоциативной обработке 256 кбайт информации. Скорость поиска и обработки информации 256 процессорными элементами высока, и остальные элементы системы спроектированы так, чтобы поддерживать эту скорость.

 

2. Применение ассоциативных процессоров (на примере интерференционного управления системами)

 

С помощью ЭВМ можно построить программные модели ряда рассмотренных голографических корреляторов - голографа Габора, голофона Лонге-Хиггинса, голографона (в том числе программно-управляемого), а также ряда других корреляционных приборов.

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

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

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

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

Рис. 3. Результаты машинного моделирования операций записи и считывания временных цепочек в ассоциативном процессоре: а) запись двух циклически-замкнутых последовательностей (цифр и букв); б) результаты считывания при возбуждении процессора различными входными изображениями и отрезками цепей.

 

Любой из рассмотренных корреляторов с пространственным наложением коррелограмм (голограмм) характеризуется тем, что отношение сигнал/шум зависит от степени заполнения памяти и уменьшается с заполнением памяти. В традиционных системах памяти это отношение постоянно. В работе предложен коррелятор на основе "развивавшейся" среды. Число ячеек (объем корреляционной матрицы) в этом корреляторе не постоянно, а зависит от входного потока информации: как только в некоторой ячейке матрицы отношение сигнал/шум уменьшится ниже определенного порога, запускается механизм удвоения ячейки (механизм увеличения памяти). В результате удвоения память увеличивается, степень заполнения уменьшается, и поэтому отношение сигнал/шум возрастает. В этом устройстве объем матрицы контролируется входами сигналами, т.е. запись осуществляется в "растущей" среде. Такой коррелятор можно рассматривать как модель клеточной среды, растущей под влиянием сигналов "новизны".

 

 

Заключение

 

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

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

 

 

Список литературы

 

Быховский В.К. Принципы построения ассоциативного оптического процессора. М., 1973.

Быховский В.К. Принципы построения ассоциативного оптического процессора. М., 1973.

Головко В.А., под ред. проф. А.И.Галушкина   Нейронные сети: обучение, организация и применение. - Москва: ИПРЖР, 2001.

Короткий С. Нейронные сети - http://lii.newmail.ru

Кохонен Т. Ассоциативные запоминающие устройства. Москва, "Мир", 1982.

Сороко Л.М. Интерференционная обработка информации. М., 1966.

Солимар Л. Туннельный эффект в сверхпроводниках и его применение.