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

 

 

 

Курсовая работа

на тему:

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Москва, 2006 г.

 

Содержание

 

Введение 3

1. Ассоциативная память 4

1.1. Сущность ассоциативной памяти 4

1.2. Применение ассоциативной памяти 7

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

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

Заключение 21

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

 

 

Введение

 

Ассоциативная память - это массив ограниченного размера из строк памяти. Строка памяти содержит адрес A, данные D и надежность R. (Можно ли обойтись без надежности и без забывчивости?) Рассмотрим только битовую (логическую) память. Она устроена несколько сложнее, чем аналоговая. Адрес и данные характеризуются количеством бит или байт, а надежность - это число от 0 до 1. При записи новая строка ADR заносится на место одной из наименее надежных строк. Ассоциативная память характеризуется тем, что чтение из нее возможно, даже если в ней нет строки с нужным адресом A. Результат чтения из памяти есть вероятностная сумма всех данных, рассчитанная по их надежности R и близости адреса A к заданному адресу. Можно определять близость адреса сортировкой. Можно по количеству отличающихся бит или байт.

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

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

 

1. Ассоциативная память

1.1. Сущность ассоциативной памяти

 

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

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

Естественное решение -  снабдить компьютер  аппаратным устройством для отображения виртуальных  страниц в физические без обращения к таблице страниц,  то есть иметь небольшую, быструю  кэш-память,  хранящую необходимую на данный момент часть таблицы страниц.  Это устройство называется ассоциативная память,  иногда также употребляют термин ассоциативные регистры (иногда translation lookaside buffer (TLB)).

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

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

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

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

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

Процент раз, когда номер страницы находится в ассоциативной памяти, называется hit (совпадение) ratio (пропорция, отношение). Таким образом, hit ratio - часть ссылок, которая  может быть сделана с использованием  ассоциативной памяти. Обращение к одним и тем же страницам повышает hit ratio.

Например,  предположим, что для доступа к таблице страниц необходимо 100 нс, а для доступа к ассоциативной  памяти 20 нс. С 90% hit ratio среднее  время доступа - 0.9*20+0.1*100 = 28 нс.

Вполне приемлемая производительность современных ОС доказывает эффективность использования ассоциативной памяти.  Высокое значение вероятности нахождения данных в ассоциативной памяти связано с наличием у данных объективных свойств: пространственной и временной локальности.

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

 

1.2. Применение ассоциативной памяти

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

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

Системные поля - это ключи. В них входят первичный ключ (счетчик) для связи с подчиненными таблицами и вторичные ключи для связи с главными таблицами (если данная таблица является подчиненной).

Поля наименования - это те поля, по которым пользователь может идентифицировать описанный в таблице объект в ряду себе подобных. Для предотвращения дублирования записей (т.е. появления "двойников") необходимо обеспечивать уникальность записей. Типы полей - строковые, реже - числовые или дата/время.

Поля данных - в них хранятся данные об объекте. Это поля типа числовые, денежные, дата/время, и т.д.

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

При подходе сверху главный определяющий фактор - удобство пользователя. Существует много способов доступа к данным в таблицах, но наибольшее распространение получил язык SQL. Фактически SQL фактически стал индустриальным стандартом для реляционных баз данных. Американский Институт Национальных Стандартов (ANSI) в 1986 году объявил язык SQL стандартом для реляционных баз данных. То же самое сделала и Международная Организация по стандартам (ISO). Все основные реляционные системы управления баз данных поддерживают в том или ином виде язык SQL, и большинство разработчиков реляционных систем управления базами данных стремятся следовать стандарту ANSI. Конструкторы SQL встроены в настольные СУБД (ACCESS, Delphi), серверные приложения работают в основном с SQL (ORACLE, SQL server).

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

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

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

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

Индексирование. Индексы - это специальные конструкции, которые позволяют быстро найти адрес нужной записи и в настоящее время они широко применяются на практике. На одну таблицу можно создавать несколько индексов. В качестве примера можно рассмотреть рекомендации по применению индексов в ORACLE. Они сводятся к следующему: рекомендуется использовать индексы для обеспечения уникальности записей; для ускорения выборки данных; задавать индексы для тех полей, выборку по которым производится чаще всего, и при этом рекомендуется задавать на таблицу не более 3 индексов, что очень мало. На практике применяют индексы следующим образом: в системных полях таблиц используют 1-2 индекса, и еще один индекс - на поля наименования. Область данных почти никогда не индексируют, хотя отбор чаще всего происходит именно по этим полям. Кроме того, на обновление индексов также требует времени, а сами индексы занимают место на диске (а иногда размер индексов превышает размер основной таблицы).

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

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

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

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

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

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

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