Ассоциативная запоминающая среда

 

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

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

Известен ассоциативный накопитель ассоциативного запоминающего устройства (1).

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

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

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

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

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

На фиг. 1 показаны варианты организации взаимодействия ассоциативных ячеек в 2D-пространстве для пяти возможных правильных точечных систем (точечных решеток) в декартовой системе координат на плоскости с квадратной (а), с правильной треугольной (б), с косой параллелограмматической (в), с прямоугольной (г) и с ромбической (д) системами точек. На фиг. 2 приведена схема ассоциативной ячейки для 2D-решетки с правильной треугольной системой точек. На фиг. 3 показаны примеры фундаментальных областей 2D-решеток, а также типы окрестностей ассоциативной ячейки-ядра 2D-решеток среды. На фиг. 4 рассмотрен пример организации взаимодействия ассоциативных ячеек в гранецентрированной 3D-решетке среды.

Ассоциативные ячейки 1 (фиг.1), образующие точечную решетку, непосредственно взаимодействуют со смежными с ними ассоциативными ячейками.

На плоскости существует пять возможных точечных решеток, в 3D-пространстве - четырнадцать (решетки Брава) (3). Информация о наилучших по различным критериям решетчатых упаковках большей размерности приведена в (4).

Выходы 2 ассоциативных ячеек 1 соединены с входами соответствующих групп 3 смежных с ними ассоциативных ячеек. Входы ассоциативного опроса 4 и выходы результатов ассоциативного опроса 5 подключены соответственно к шинам ассоциативного опроса 6 и шинам результатов ассоциативного опроса 7 по заданным направлениям.

Из рассмотренных на фиг. 1 точечных решеток наибольший интерес для практической реализации представляют те, которые характеризуются степенью симметрии (фиг. 1, а; фиг. 1, б). Вариант на фиг. 1, а обеспечивает ортодиагональность представления и обработки информации; а на фиг. 1, б - максимально возможную для 2D-решетки степень симметрии, одинаковые расстояния ассоциативных ячеек от своих ближайших соседей, плотнейшую упаковку информации, наиболее экономное покрытие 2D-пространства ассоциативной среды (4).

На фиг. 2 представлена схема ассоциативной ячейки 1 для организации ячеек в 2D-решетку на фиг. 1, б. Ячейка 1 содержит узел анализа входной информации 8; узел хранения 9; узел 10 взаимодействия хранимой и поступающей в ячейку информации из смежных с ней ячеек; узлы ассоциативного сравнения 11₁-11₃; узел управления записью 12; узел управления хранением информации 13; узел управления правилами взаимодействия хранимой и поступающей в ячейку информации 14; узел управления опросом 15, входы записи 16, выходы 2; группы входов 3, входы опроса 4, группы выходов результатов опроса 5₁-5₃; управляющие входа 17. Выходы узла 10 соединены с входами одной их групп узла 8 ассоциативной ячейки.

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

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

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

- Зависимость записи от соотношения (сравнения) значимости хранимой в ячейке и записываемой информации. В этом случае в ассоциативной ячейке (конкретно, в узлах 8 и 12) должны быть предусмотрены средства для записи, хранения, сравнения значимости ранее записанной с вновь поступающей информацией и выработки решения. В том числе, зависимость записи от выполнения различных пороговых условий. Например, превышение порога по числу обращений к ячейке при записи в заданном интервале времени, превышение порога записи одного из альтернативных значений информации (лог. "0" или "1"). Для этого варианта примером реализации узла анализа входной информации 8 может послужить пороговый суммирующий нейрон [5], а узла управления записью 12 - схема задания порога срабатывания и весовых коэффициентов этого нейрона.

Вышесказанное о гибких правилах записи в ассоциативную ячейку справедливо для правил хранения, считывания, взаимодействия хранимой и поступающей в ячейку информации из смежных с ней ячеек ассоциативного опроса. Узлы 13 - 15 могут быть построены аналогично узлам 8 + 12.

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

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

На фиг. 3 показаны примеры фундаментальных областей 2D-решеток, а также типы окрестностей ассоциативной ячейки-ядра для 2D-решеток среды: (а) фундаментальная область в виде фундаментального параллелограмма (связность равна трем) [7], (б) фундаментальная область в виде фундаментального симплекса (связность равна двум) [8], (в) окрестность фон Неймана (связность ячейки-ядра равна четырем), (г) окрестность Мура (связность ячейки-ядра равна 8, (д) окрестность Голея (связность ячейки-ядра равна шести) [9].

В качестве примера реализации узла 11_i может служить схема ассоциативного сравнения по критерию "равно" и коммутационный элемент ассоциативного запоминающего элемента из [10], а узла 15 - пороговый суммирующий нейрон, разрешающий проведение ассоциативного сравнения при превышении заданного порога.

Критериями ассоциативного сравнения могут быть, например, полное или частичное совпадение сравниваемых объектов, их полная или частичная противоположность, одновременность или заданный интервал времени между их появлением и др. [11].

Правила задания ассоциативного сравнения, помимо вышерассмотренных, могут также обеспечивать коммутацию выходов групп 5₁ - 5_K узлов ассоциативного сравнения 11_i (i=1...K) к различным шинам результатов ассоциативного опроса 7.

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

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

В режиме хранения значение записанной в узле 9 информации может меняться в зависимости от устанавливаемых узлом 13 правил.

Считывание информации из ячейки производится с выходов 2.

Перед выполнением ассоциативного опроса необходимо осуществить настройку узлов 10 и узлов 11₁ - 11_K ассоциативных ячеек среды.

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

Настройка узлов ассоциативного сравнения 11₁ - 11_K заключается в предварительной записи в регистры коммутационных элементов "кодов подключения" выходов групп 5₁ -5_K результатов опроса к заданным шинам результатов опроса 7. Кроме того, должны быть заданы весовые коэффициенты и порог срабатывания узлом 15.

При выполнении ассоциативного опроса среды по любому из направлений признак ассоциативного опроса с шин 6 поступает на входы 4 опроса ассоциативных ячеек 1. Этот признак сравнивается с информацией, полученной на выходе узла 10, в соответствующем узле ассоциативного сравнения 11_i. И в соответствии с установленным критерием сравнения и заданных условий коммутации результат ассоциативного сравнения с выходов узла 11_i поступает на выбранные шины результатов ассоциативного опроса 7. В случае выполнения условий ассоциативного сравнения, маскирования сравнения или блокировки прохождения результатов ассоциативного сравнения соответствующая шина 7 не изменит своего состояния, или пределы этого изменения будут допустимыми. При невыполнении условий ассоциативного сравнения признак этого события поступит на выбранные шины 7, изменяя их состояние существенным образом, индицируя несовпадение.

Ассоциативный опрос может проводиться одновременно по нескольким, от одного до K, возможным направлениям ассоциативного доступа в ассоциативной запоминающей среде.

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6