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

МОСКОВСКИЙ ордена ЛЕНИНА и ордена ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

На правах рукописи

БОРИСОВ ВАДИМ ВЛАДИМИРОВИЧ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МНОГОКООРДИНАТНЫХ АССОЦИАТИВНЫХ ЗАПОМИНАЮЩИХ УСТРОЙСТВ ДЛЯ СИСТЕМ ОБРАБОТКИ ИНФОРМАЦИИ

.Специальность 05.13.05 - Элементы и устройства вычислительной

техники и систем управления

)

;

)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

МОСКВА 1991'

Работа выполнена на кафедре Вычислительной техники Московского ордена Ленина и ордена Октябрьской революции энергетического института'

Научный руководитель

Официальные оппоненты

Ведущая организация

- доктор технических наук профессор ОГНЕВ И. Е

- доктор технических наук профессор ВАГИН Е Е кандидат технических наук САРЫЧЕВ К. Ф.

- НИИВК

Защта диссертации состоится "_"_1991 г.

в аудитории _в _час. _мин. на заседании специализированного Совета К 053.16.09 Московского ордена Ленина и ордена Октябрьской Революции энергетического института

Отзывы (в двух экземплярах, заверенные печатью) просим направлять по адресу: 105835, ГСП, Москва, Е-250, Красноказарменная ул. , д. 14, Ученый Совет МЭИ.

С диссертацией можно ознакомиться в библиотеке ЮИ.

Автореферат разослан "_"_ 1991 г.

Ученый секретарь специализированного Совета К 053.16. 09 ЮИ, к. т. н.

т?0

СЫЧЕВ КХЕ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

АКТУАЛЬНОСТЬ ТЕМЫ. Прогресс в области вычислительной техники в настоящее время связывается с результатами исследований в сфере искусственного интеллекта (ИИ), где за последнее десятилетие сформировалась новая отрасль индустрии - производство интеллектуальных систем.

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

Результаты исследований позволяют сделать вывод о том, что одним из наиболее узких мест в создании новых, а также в развитии уже известных систем ИИ, является отсутствие элементной базы БИС АЗУ для систем обработки изображений. При этом наиболее актуальными являются задачи разработки и создания БИС специализированных АЗУ, обеспечивающих внутрисхемное выполнение специальных Функций обработки иконически представленной информации ( то есть, для которой свкаь объекта с его изображением устанавливается на основе 'фактического сходства ).

Работа выполнялась в МЭИ по планам НИР НИЧ МЭИ в соответствии с Приказом Гособразования СССР N701 от 30. Об. 1989г. в рамках Всесоюзной межвузовской научно-технической программы "Интеллектуальные системы" по договору N01900066957, а также в соответствии с договором между НИО ВТ МЭИ и 1МЗМИ ( N020408900 ).

ЦЕЛЬ РАБОТЫ состоит в разработке и исследовании многокоординатных АЗУ для систем обработки информации на основе анализа ассоциативных информационных взаимодействий на базе принципов реализации иерархической М-мерной ассоциативной памяти, основанной на принципах пост-

роения и функционирования иерархической по мерности модели представления информации.

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

- разработать классификацию систем ассоциативной памяти;

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

- разработать и исследовать схемы ассоциативных ячеек и схемы многокоординатных АЗУ;

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

- исследовать и осуществить типизацию структурно-функциональных решений многокоординатных АЗУ для их реализации в виде БИС.

МЕТОДЫ ИССЛЕДОВАНИЯ Основным методом исследования являлось теоретическое исследование с позиций анализа принципов построения и функционирования иерархической по мерности модели представления информации и механизма ассоциативных информационных взаимодействий в иерархической М-мерной ассоциативной памяти.

Экспериментальные исследования проводились с использованием моделирования на ЭВМ, а также систем функционально-логического проектирования БИС и аналогового проектирования.

НАУЧНАЯ НОВИЗНА РАБОТЫ заключается в следующем:

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

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

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

- разработаны и исследованы схемы ассоциативных ячеек и схемы АЗУ нового класса - ортокоординатных АЗУ - , а также ряда специализированных АЗУ на базе предложенной концепции иерархической по мерности многокоординатной ассоциативной памяти, использование которых позволяет повысить эффективность выполнения различных задач обработки информации в системах, построенных на базе таких устройств;

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ состоит в следующем:

- разработаны схемы специализированных ассоциативных ячеек, на основе которых могут быть созданы БИС АЗУ;

- разработаны оригинальные структурно-функциональные решения АЗУ 'нового класса - ортокоординатных АЗУ г , а также ряда специализированных АЗУ на базе предложенной концепции иерархической по мерности многокоординатной ассоциативной памати с проработкой базовой структуры АЗУ такого типа для реализации в виде БИС с целью использования в проблемно-ориентированных системах обработки информации;

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Результаты исследований использованы в разработках НИЭМИ в виде конструкторской документации на изготовление ассоциативных ячеек и БИС ортокоординатного АЗУ на основе базового матричного кристалла БМК 4. 601ВЖЗ, а также в рамках Всесоюзной межвузовской научно-технической программы "Интеллектуальные сис-

темы".

АПРОБАЦИЯ РАБОТЫ. Основные положения диссертационной докладывались и обсуждались на:

- международной конференции "First International Conference on Information Technologies for Image Analysis and Pattern Recognition ( Львов. СССР. 1090 );

- 45 Всесоюзной сессии ВНТО РЭС ( Москва, 1990 );

- 7 Всесоюзном Координационном совещании по проблеме "Развитие методов проектирования и изготовления интегральных запоминающих устройств" ( Москва, 1991 );

Кроме того, результаты исследований обсуждались на:

- Всесоюзной научно-технической школе "Устройства хранения информации в информационных и вычислительных системах" ( Таллинн, lOftf );

- Всесоюзной школе-семинаре "Состояние и направления развития запоминающих устройств для перспективных ЭЕМ" ( Симферополь, 1989 ).

ПУБЛИКАЦИИ. Результаты исследований опубликованы в пяти печатных {аботах. Ка пять заявок на изобретения получены положительные решения Госкомиэобретений.

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертационная работа изложена на 215 страницах, из них 128 страниц основного текста, 47 рисунков и состоит из введения, 5 глав, заключения, списка литературы из 104 наименований и 4 приложений.

'ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во ВВЕДЕНИИ обоснована актуальность темы диссертации, сформули-роьана цель работы и основные положения, выносимые на защиту, приво-длтсн дополнительные сведения по работе. . -

ПЕРВАЯ ГЛАВА посвящена разработке классификации и анализу современного состояния элементной базы АЗУ. . '

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

Разработана классификация систем ассоциативной памяти на основе характерных признаков в соответствии с выделенными подходами.

1. По подходу к проблемам ассоциативного взаимодействия:

- по способу реализации памяти, адресуемой по содержанию;

- по способу формирования ассоциативных отношений;

- по формам представления информации;

- по формам ассоциативной связи.

2. По подходу к построению ассоциативных структур:

- по структурному решению;

- по виду физического носителя.

3. По подходу к организации функционирования ассоциативной памяти:

- по способу записи;

- по виду ассоциативного поиска;

- по способу опроса;

- по способу выборки многозначного ответа

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

Проанализированы проблемы создания, тенденции и перспективы развития ассоциативных приборов памяти. Проведен анализ современного состояния элементной базы БИС АЗУ.

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

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

В этой главе также сформулированы цель и задачи работы.

ВО ВТОРОЙ ГЛАВЕ рассмотрены вопросы, связанные с разработкой иерархической по мерности модели представления информации и с анализом ассоциативных взаимодействий в иерархической Л-мерной ассоциативной памяти.

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

Основные понятия, используемые при описании модели:

- информационная структура ( 3 ) - структура, служащая для аккумулирования, хранения, оперирования и обмена информацией;

- информационное поле ( 0 ) - информация, доступная множеству всех информационных структур;

- уровень информационного поля ( - информация, доступная информационным структурам определенного уровня иерархии;

- слой уровня информационного поля ( с£) - информация, доступная отдельному Г-подмножеству информационных структур Е^ I уровня иерар-

хии

где N - число информационных структур из подмножества еД^

Основные принципы построения и функционирования модели.

1) Иерархическая взаимосвязь уровней информационного поля.

2) Мерность информации - как признак иерархии уровней информационного поля.

3) Соответствие слоя уровня информационного поля определенной мерности одному из подмножеств информационных структур определенного уровня иерархии.

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

С^ —^ С1 ^(Ог ¿(г)*

- "горизонтальные" информационные взаимодействия.

5) Информационные структуры более низких уровней иерархии имеют доступ к слоям уровней информационного поля, которые соответствуют

информационным структурам более низкого уровня иерархии, и наоборот, посредством "вертикальных" ( межурсвневых ) взаимодействий, г 1

А

/уи- "вертикальные" ( снизу вверх ) информационные взаимодействия; ^^ "вертикальные" ( сверху вниз ) информационные взаимодействия.

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

гI*< />у (• к

- ¿г

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

8) Непротиворечивость представления информации в информационных структурах модели реализуется на основе:

а) мгновенности осуществления информационных взаимодействий;

б) соблюдения принципа причинности при осуществлении информационных взаимодействий.

9) Эффективность оперирования в информационных структурах модели информацией различной мерности определяется соотношением:

¿ГГ5ГЛ /у ш.

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

(} информация из уровня (^''информационного поля, хранимая в ин-

формационной структуре З^'* ;

¿¡Т^явцУ информадая из уровня (}" информациокного поля, соответствующего множеству информационных структур Ь уровня иерархии, связанных с .

У(^*М)У(£1 )- соответственно, информационная емкость структуры $ ' и связанных с ней структур Ь уровня иерархии.

10) Полнота отображения информации на различных уровнях иерархии модели:

а) необходимое условие

ох

б) достаточное условие

- У(^).

Далее во второй главе проанализированы разработанные принципы реализации модели на иерархической Ы-мерной ассоциативной памяти ( ИАП ).

1) Понятие информационной .1-ой структуры 1-го уровня иерархии модели соответствует массиву ассоциативных элементов Р^^ ИАП

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

3) Понятие уровня информационного поля соответствует информации, которая может быть отображена во всех массивах ассоциативных элементов множества (Р^)/^!'^} с 1-числом доступов, С^ - число массивов ассоциативных элементов с 1-числом доступов

4) Понятие слоя уровня информационного поля 0/ соответствует информации, отображенной в массиве Р/ут-;

1Г(Р1а))

5) Взаимосвязь между массивами ассоциативных элементов ИАП разной мерности реализуется посредством "вертикальных" информационных взаимодействий ^ ^

Ртт /к*^1} ,

- множество массивов ассоциативных элементов с (1-1) числом доступов, непосредственно связанных с 1-ым массивом ассоциативных элементов с I числом доступов.

Основными операциями при осуществлении "вертикальных". ( снизу вверх ) информационных взаимодействий являются:

- и -

а) ассоциативный иерархический поиск;

0) ассоциативный иерархический опрос.

Основными операциями при осуществлении "вертикальных" ( сверху вниз ) информационных взаимодействий являются:

а) ассоциативное иерархическое проецирование;

б) ассоциативное иерархическое контекстное проецирование.

6) Взаимосвязь массивов ассоциативных элементов ИАП одной и той же мерности реализуется посредством "вертикальных" информационных взаимодействий. При этом в роли "посредников" выступают массивы ассоциативных элементов большей мерности.

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

8) Возможность качественного изменения представления информации в массивах ассоциативных элементов ИАП реализуется за счет изменения мерности массивов Р/<т7 от уровня к уровню, а также за счет выполнения преобразований в процессе осуществления и .

9) Непротиворечивость взаимосвязей между массивами Р/уд) ИАП реализуется за счет:

а) ассоциативного характера операций информационных взаимодействий;

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

10) Эффективность оперирования в массивах Р^гу/; ИАП информацией различной мерности определяется соотношением:

У(Ртт)

Н4

УЩШ^Ш)

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

11) Информация из массива Р^) может быть определена и представлена конечным набором проекций этой информации в массивах из мно-хества •

Условие полноты представления информации

(/(Ргт) - Ш{Р/а!^т}) .

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

1) Ассоциативное иерархическое проецирование ( АШР ).

Особенностью АШР является то, что для ассоциативного сравнения

в массив¡K'tпоисковый аргумент формируется в массиве ?jc) с мерностью на единицу больше.

Для реализации АИПР ассоциативные ячейки массива Рja) должны обеспечивать возможность их использования в качестве источников битов поисковых аргументов по всем реализованным направлениям.

2) Ассоциативный иерархический поиск ( АИП ).

При выполнении АИП в массиве ^j(i) поисковый аргумент формируется в любом из массивов /fci+Т] с мерностью на единицу меньше. Поиск проводится по любому из реализованных в массиве Vr/n направ-

т/г)

лений. В случае совпадения поискового аргумента из P^y/./j с поисковым аргументом из Р^/^активизируюгся ассоциативные элементы этого искомого аргумента, который теперь может выступать в качестве поискового аргумента при выполнении АИП в массиве P/^jv/p мерностью на единицу больше.

3) Ассоциативный иерархический опрос ( АИО ).

При выполнении АИО на основе поисковых аргументов из всех массивов мн о же с т в a {Pj^tjfc Формируется поисковый объект мерности I, соответствующей мерности массива fj(r) , в котором осуществляется этот опрос.

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

4)Ассоциативнное иерархическое контекстное проецирование( АИКПР).

• При выполнении АИКПР результат ассоциативного поиска в. массиве Pj-(Z) мерности I является исходной информацией для осуществления ассоциативного поиска в массивах мерности (1-1).

ТРЕТЬЯ ГЛАВА посвяшена разработке и исследованию схем АЗУ нового класса - ортокоординатных АЗУ (ОКАЗУ) - на базе предложенной концепции иерархической по мерности ыногокоординатно'й ассоциативной памяти.

- 13 -

основными особенностями которой ЯВЛЯЮТСЯ:

а) иерархическая взаимосвязь между массивами элементов разной мерности; мерность выступает признаком иерархии;

б) возможность выполнения ассоциативных иерархических взаимодействий по всем реализованным направлениям з каядом массиве ассоциативных элементов;

в) возможность обработки информации в логико-запоминающей среде самого устройства;

г) многопортовый доступ к информации;

д) максимальная программируемость логико-запоминающей среды.

-ги ПА1

ПА2 С2

-т С1

Р1

г1-

Р2

-гп

Рис. 1

ПА1 - строчный поисковый аргумент; ПА2 - столбцовый поисковый аргумент; Р1 - результат строчного ассоциативного поиска; Р2 - результат столбцового ассоциативного поиска.

С1 - маска ПА1; С2 - маска ЛА2;

1

т

На рис. 1 приведена упрощенная блок-схема базового ОКАЗУ. Далее в третьей главе рассмотрены разработанные разновидности ОКАЗУ.

- Базовое ОКАЗУ, обеспечивающее возможность выполнения ассоциативного поиска одновременно по строкам и столбцам ассоциативного накопителя по критерию "равно". То есть,

, ¿-А/??.

- ОКАЗУ с обеспечением возможности проведения ассоциативного поиска по двум координатам ассоциативного накопителя с зависимым маски-рованием■ р^ т >

Щ - ШШ21 УС2£]) УЦ -

- ОКАЗУ с выполнением логических преобразований над результатами ассоциативного поиска.

Р-Ю.....Рп)>

, ¿•/+Л (т.Л),

7/ / I, лри с¿* СП ,

{п-(ч'+#/) . при (¿+к{) >п ,

-7П Г ¿ + кг . лри (¿+К2)4П,

/л -(¿+*2) . лр" ( п ,

Л>с - логическая операция из набора: А/.....Я/ ;

к1, к2 - задаваемые смешения результатов, соответственно, строчного и столбцового ассоциативного поиска.

- ОКАЗУ с блочной организацией ассоциативного накопителя обеспечивает возможность выполнения ассоциативного поиска одновременно по строкам и столбцам накопителя. ,

- ОКАЗУ с матричным расположением поисковых аргументов обеспечивает возможность ассоциативного сравнения искомой информации с поисковым объектом, мерность которых ограничена мерностью ассоциативного накопителя такого ОКАЗУ.

- Трехмерное иерархическое ОКАЗУ - ориентировано на обработку иконически представленных трехмерных информационных объектов и обеспечивает реализацию разработанных ассоциативных иерархических взаимодействий.

Рассмотренные в этой главе разработаю«« разновилясатх •:"'.'>:" позволяют расширить область применения АЗУ в аровлемно-огк-.-нг/гог.лн-ных системах обработки информации.

В ЧЕТВЕРТОЙ ГЛАВЕ рассмотрен ряд спенкшк'кровшшкх ДС-У. Г'-' ботанных на основе анализа ассоциативных иерархических ин;>:р!.''.цк:: к;./ взаимодействий.

- АЗУ с возможностью выполнения ассошпткг.чсгэ г.сн.г-"'-. о;:: того же поискового аргумента. представленного кик з пгям' й, и ь зеркально отображенной форме без его перезаписи, сдас?;-:м-::и50 г.? строкам и столбцам ассоциативного накопителя.

Р// =Л/(Щ УС.у , ¿.£*т, *А,Ш1 )Шс], у-/-/?,

Р2ГАС(ЛА!(т.п</•

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

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

или

АН--

<т

- матрица выделенных строк ассоциативного накопителя.

- АЗУ с возможностью выполнения внутреннего, конъюьктиенэго и. дизъюнктивного ассоциативного поиска.

а) Результат внутреннего ассоциативного поиска

где А$/ = (АЯ/>/.....~ стР01^ ассоциативного накопителя АЗУ,

являющаяся внутренним поисковым аргументом для ассоциативного поиска.

б) Результат конъюнктивного и дизъюнктивного ассоциативного поиска . п

к

й-

'Щ,

- матрица строк ассоциативного накопителя, участвующих в формировании поискового аргумента к

При конъюнктивном ассоциативном поиске: А .

при дизъюнктивном ассоциативном поиске: о?

- АЗУ с переключением строчного и столбцового каналов ассоциативного поиска, обеспечивающее возможность проведения смешанного ассоциативного поиска по строкам и столбцам ассоциативного накопителя.

е) Результат строчного смешанного ассоциативного поиска:

_ . л

Р/< Яд ,

ЛРЩ),1 (ЛА2< УС2<7 V

где РУА (РЩ,..., /ЭД. РУ2* .содержимое, соответс-

венно, строчного и столбцового регистров переключения каналов, б) Результат столбцового смешанного ассоциативного поиска:

Р2п* £СЩЛРУ2< )А (ПА.(/

У[(ЩТШс)Л С/1А2.1 3АЯу)\ZC2i].

- АЗУ с реконфигурацией ассоциативного накопителя по строкам и столбцам при проведении строчного и столбцового . ассоциативного поис-

■где

, при ,

[/77- , лри ,

*т

кс1- ( кс1|..... кс1л) - коды смешений, определяющие подключение

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

р^ = [(т 1 ^п .

где ¿Г ксцу , при (Ш^ф^п,.

( П-(КС2С^) , при >п ,

кс2- ( кс2у.....кс2т) - коды смещений, определявшие подключение

ассоциативных ячеек соответствующих строк накопителя к соответсвующим выходам строчного опроса

Разработанные специализированные АЗУ обеспечивают реализацию дополнительных возможностей при их использовании в системах обработки информации при решении арифметико-логических задач, задач поиска и сортировки данных.

Разработаны и исследованы новые разновидности ассоциативного поиска - внутренний, конъюнктивный, дизъюнктивный, смешанный - , реализация которых позволяет расширить область применения АЗУ.

В ПЯТОГН'ЛАВЕ рассмотрены вопросы, связанные с разработкой и типизацией ОКАЗУ в виде БИС и с анализом эффективности использования ортокоординатной ассоциативной памяти для решения задач обработки изображений.

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

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

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

Рассмотрены вопросы, связанные с разработкой устройств на основе Г/." ОКАс.У и с анализом их эффективности при решении задач обработки Прсьедек анализ и показана эффективность выполнения раз-I устройствами специальных функций обработки иконически

прел 'тав.ч-гякоЯ кнФормщии ( сравнение изображения с эталоном, поиск ■"¿ъектсь по установленным критериям, утокьшение и утолщение линий, сжатие ( кодирование ) изображений, подавление на изображении шумов и г.с.мех на основе различных видов фильтрации, выделение границ связ-ссластей и т.д. ).

Из. оскоьг результатов, полученных при осуществлении программого мод^-лпосьаннл, произведена оценка увеличения скорости выполнения рас-о.'отге-нкых операций 1ЕУ/РС при использовании устройств на базе БИС СКАЗУ я а различных размерах растра изображений.

Показаны преимущества систем, реализующих концепцию ортокоордк-натней ассоциативной г.амяти, по сравнению с архитектурами на основе традиционных АСУ.

Б ЗАКЛЮЧЕНИИ изложены основные научные и практические результаты, полученные в диссертационной работе, определены направления дальнейших исследований.

Б ПРИЛО:?£151ЯХ приводятся результаты моделирования функционирования разработанной схемы специализированной ассоциативной ячейки и БИС СКАЗУ, а также материалы по использованию результатов диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

ассоциативного взаимодействия, построения и организации функционирования ассоциативных структур.

2. Разработаны принципы реализации иерархической Л-мерной ассоциативной памяти на базе предложенных принципов построения и функционирования иерархической по мерности модели представления информации. На основе анализа этих принципов разработаны и исследованы процедуры ассоциативных иерархических информационных взаимодействий.

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

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

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

6. Осуществлена разработка и типизация ортокоординатного АЗУ в виде БИС на основе результатов моделирования работы ячейки ассоциативной памяти, а также схемы ОКАЗУ на базовом матричном кристалле. Проанализирована эффективность выполнения операций обработки иконически представленной информации предложенными устройствами на основе разработанных БИС ОКАЗУ на базе ПЭВМ. Дана сравнительная оценка и показаны преимущества ориентированных на параллельное выполнение алгоритмов обработки изображений систем, реализующих концепгига орто-координатной ассоциативной памяти, по сравнению с архитектурами на базе традиционных АЗУ.

Основные положения диссертации опубликованы в следующих работах:

1) Огнев И. а , Борисов ЕЕ, Исаев 0. В. БИС ортокоординатного ассоциативного запоминающего устройства. - 3 кн: Тез. докл. 45 Всесоюзной научной сессии ВНТО РХ "Вычислительная техника и автсматизиро-

- 20 -

ванные системы управления". - М. , 1990, с.73-74.

2) Огнев И. В. , Борисов ЕЕ , Исаев 0. Е Устройства на основе БИС ортокоординатного ассоциативного запоминающего устройства в задачах обработки изображений. - М. , Деп. в ВИНИТИ N4067-B90, 1990. - 25с.

3) Исаев 0. Е , Огнев И. К , Борисов В. Е , Кудряпов 0. К1 Устройства обработки изображений на основе БИС ортокоординатных ассоциативных ЗУ - Recognizers Using Ortokoordinate Associative Memory LSI in an Image Processing Tasks. - ITIAPR'90 Intern. Conf. on Information Technologies for Image Analysis and Pattern Recognition. Oct. 22-28, 1990, Lviv, USSR. Vol.2, p. 106-109.

4) Огнев И. E , Борисов EE .Вельмакин С. П. Способы классификации и анализ современного состояния ассоциативных запоминающих устройств. - М. , Деп. в ВИНИТИ N1091-B91, 1991. - 25с.

5) Огнев И. Е , Борисов Е Е Ортокоординатные ассоциативные запоминающие устройства - новый тип "разумных" ЗУ для функционально-ориентированных систем обработки данных. - В кн.: Тез. докл. 7 Всесоюзного координационного совещания. Развитие методов проектирования и изготовления интегральных запоминающих устройств. - Ы.: МИЭТ,1991,с. 7.

П'ММН* ЯНи К Г1ГЧ.1ТИ Л - J^t/' . „ Псч .1. /¿J' Тн|..1А /Ос> _ Зяк.11 /¿>ЬУ

Титл рлфн« МЭИ, Кр.н н^ка.1.1 рчстия, IJ