Когда говорят о запоминающих устройствах, большинство людей вспоминают о накопителях на магнитных дисках (HDD) и о памяти с произвольным доступом (ОЗУ). Уверен, большинство читающих этот пост, знает о множестве фундаментальных различий между устройствами этих классов. Но на самом деле у этих устройств есть и кое-что общее: и в оперативной памяти, и на жёстких дисках поиск информации выполняется по её адресу. Программистам такой подход кажется если не единственно возможным, то уж точно самым логичным, но к счастью реальный мир не ограничивается исключительно программными абстракциями. В этой статье мы рассмотрим запоминающие устройства с доступом по содержанию.
Прежде чем перейти к описанию ассоциативных запоминающих устройств (АЗУ), мы рассмотрим небольшой пример из жизни. Пусть вы хотите найти эту девушку:
У вас есть два пути:
1. Узнать, где она живёт и прийти по адресу ул. М****х, д. №N, кв. №M;
2. Обойти всех девушек на нашей планете и проверять удовлетворяют ли они следующим признакам: глаза – серые, волосы – рыжие, рост – 165 см., вес – 55 кг., и некоторым другим.
Надеюсь, вы поняли, что первый путь – это адресный способ доступа, а второй путь – ассоциативный (т.е. доступ по содержанию). Конечно, вы заметили, что первый способ гораздо проще и привычнее, но что если у вас есть возможность найти и проанализировать всех девушек мира одномоментно? Тогда второй путь не выглядит таким уж нелепым. На деле встречается множество технических устройств, где такой одномоментный анализ возможен, при использовании АЗУ. Думаю, будет правильно, если я расскажу, что это за устройства в конце статьи, а пока мы рассмотрим устройство АЗУ.
Мне кажется, что при описании АЗУ более правильно начинать рассмотрение не сверху вниз, а снизу вверх, поэтому первым делом мы рассмотрим одну ассоциативную ячейку. Схема её представлена на следующем рисунке:
Ассоциативная ячейка содержит следующие контакты:
1. Адресный вход (А). Адресный вход служит для активации ячейки. При низком уровне сигнала на этом входе в ячейку невозможно производить запись данных.
2. Входы данных (Д1, Д0). С помощью сигналов на входах данным производится запись произвольных данных в ячейку. При А=1, Д1=1, Д0=0 в ячейку будет записана 1, при А1=1, Д1=0, Д0=1 в ячейку будет записан 0. Д1=Д0=0 означает маскирование записи (т.е. данные в ячейке не изменяются). Комбинация Д1=Д0=1 является запрещённой и переводит ячейку в нестабильное состояние.
3. Входы ассоциативного сравнения (АС1, АС0). Входы ассоциативного сравнения во многом похожи на входы данных, но служат не для записи, а для считывания данных. АС1=1, АС0=0 означает сравнение с 0. АС1=0, АС0=1 означает сравнение данных, хранящихся в ячейке с 0.
4. Выходной сигнал (В). На этом выводе при активном адресном входе всегда выдаётся инверсия хранящегося в ячейке значения.
5. Разрядный выход (Р). На разрядный выход выдаётся результат ассоциативного сравнения (см. сигналы АС1, АС0).
Надеюсь, этих небольших пояснений достаточно для того, чтобы в общих чертах представить алгоритм функционирования одной ячейки.
А теперь давайте представим, что мы соберём из этих ячеек матрицу (NxM), так чтобы шины А, Р были общими в пределах одной строки, а шины данных, ассоциативного сравнения и выходная шина были общими в пределах одного столбца. Полученная структура называется ассоциативным накопителем. Создание накопителя – самый важный, но далеко не последний шаг на пути создания АЗУ. На рисунке представлена схема самого простого ассоциативного запоминающего устройства:
Рассмотрим основные блоки устройства:
1. Накопитель. С устройством накопителя мы познакомились выше. Накопитель состоит из ассоциативных ячеек, но мы можем рассматривать каждую строку матрицу, как одно слово, тогда наш накопитель может хранить N слов по M разрядов в каждом.
2. Регистр аргумента поиска действительно реализуется в виде простого регистра. В этот регистр мы записываем любое слово, которое хотим найти в накопителе или записать в него.
3. Регистр маски. Единичные значения в этом регистре показывают, какие разряды аргумента поиска будут маскироваться при ассоциативном сравнении. Именно благодаря этому регистру мы можем выполнять поиск слов следующего вида: 1?1?00?1, где на месте? может стоять как 0, так и 1.
4. Выходной регистр. В этот регистр записывает слово, которое удовлетворяет результату ассоциативного сравнения. Как этот регистр ведёт себя при многократном совпадении зависит от конкретной реализации.
5. Селектор адреса – это регистр, который сохраняет значения шины А для каждого слова в накопителе. Именно это регистр определяет, будет ли словно активно в момент записи данных.
6. Память фиксации реакции. В этом регистре сохраняются сигналы Р после выполнения ассоциативного сравнения.
7. Анализатор многократных совпадений (АМС). Зачастую, результатом поиска является не одно слово накопителя, а сразу несколько. Т.е. в памяти фиксации реакции есть несколько единичных бит. Именно анализатор многократных совпадений «решает», что делать в таких случаях. Конкретная реализация зависит от целей АЗУ. В простейшем случае АМС просто копирует данные из памяти фиксации реакции в селектор адреса.
Думаю, вы уже заметили, что для этого устройства характерна массовая параллельность (все слова обрабатываются одновременно). Но, к сожалению, эту параллельность не так легко использовать. Большинство людей сходу может придумать только одно применение для АЗУ – быстрый поиск в памяти. На самом деле, это применение является наиболее распространённым. Сейчас кеш-память многих процессоров работает именно с АЗУ, когда необходимо определить есть ли в кеш слово с данным адресом.
Но это далеко не единственное применение. Сейчас я расскажу вам алгоритм, который позволит найти максимум в накопителе за O(M), напомню, что в реальных задачах N>>M, а поиск в памяти работает за O(N). Некоторые скажут, что в отсортированном массиве поиск можно выполнить быстрее, но не забывайте, что сортировка тоже требует времени (и не малого) а АЗУ не нуждается в сортировке в принципе.
А теперь сам алгоритм. Для начала выполним некоторые подготовительные операции: в регистр аргумента поиска запишем максимально возможное число (все единицы), в селекторе адреса делаем активными все разряды, i:=1. Сам алгоритм состоит из следующих простых действий.
1. Маскируются все разряды кроме i-ого.
2. Выполняется ассоциативное сравнение.
3. Если в памяти с фиксацией реакции нет единиц, то селектор адреса не меняется, если одна единица, поиск завершён и соответствующее слово является максимумом, если же единиц несколько, то в селекторе адреса сбрасываются все разряды кроме тех, которые дали 1 в памяти фиксации реакции.
4. i:=i+1.
Алгоритм завершается, когда в памяти фиксации реакции остаётся одна единица, или же когда i>=M.
По-моему. Очень красивый и простой алгоритм. На его основе можно создать и алгоритм сортировки со сложностью O(NM). Но и это далеко не всё, если усложнить структуру ячейки, можно выполнять потоковую обработку фотографий и решать различные задачи машинного зрения. Если вам будет интересно, я как-нибудь и об этом расскажу.
На этом всё, спасибо за внимание, живите долго и процветайте.
Автор: GORKOFF
