Организация ассоциативного поиска

Моделирование поисковых операций ассоциативной памяти

ПО ДИСЦИПЛИНЕ

РАЗРАБОТКА ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ

(наименование дисциплины)

Разработчик: Титенко Евгений Анатольевич

(подпись) (ФИО)

Цель лабораторной работы:

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

Задание

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

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

3. На основе полученных логических функций и схемы разработайте программу и получите файл листинга программы.

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

Содержание отчета

- титульный лист;

- задание;

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

- граф-схема решения задачи и схема взаимодействия потоков;

- текст программы;

- результаты работы программы

Основные понятия

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

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

- совмещение функции хранения и обработки данных;

- инвариантность времени поиска к хранимому объему данных и зависимость времени поиска от уровня важности данных.

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

Организация ассоциативного поиска

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

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

При ассоциативном поиске количество ячеек накопителя не является определяющей величиной, так как поиск будет выполняться не «горизонтально» по ячейкам, а «вертикально» по разрядным срезам. Разрядный срез – совокупность j-ых элементов памяти, взятых из всех ячеек (рис.1). Временной выигрыш при ассоциативном поиске достигается за счет параллельной обработки элементов разрядного среза. Таким образом, время ассоциативного поиска T является функцией разрядности ячейки m, а не количества ячеек N, причем справедливое для современной памяти отношение N > > m определяет предпочтительным ассоциативный поиск.

Рис. 1 Формирование ячейки и разрядного среза памяти.