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

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

Основные принципы построения ассоциативной памяти (CAM – Content-Addressable Memory) не отличаются от уже рассмотренной памяти с произвольным доступом (RAM — Random Access Memory). Это же касается чтения из регистра по заданному адресу и записи в регистр, а также типовых схемотехнических решений для этих режимов. Поэтому сегодня разберем  только специфические особенности CAM.

Где применяется CAM

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

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

Запись в кеш или оперативную память выполняется блоками. Поэтому процессору нужно:

• помечать нужные блоки, чтобы различать их, и где-то хранить метки (теги) для последующего обращения,

• хранить адрес начала блока в кеше или в оперативной памяти, помеченный определенным тегом.

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

При промахе кеша (cache miss) данные приходится запрашивать из оперативной памяти, что занимает время. Поэтому нужно, чтобы данные подкачивались в кеш заранее. За это отвечает блок предварительной выборки (memory prefetcher). Он анализирует шаблоны доступа к памяти и прогнозирует, какие данные и когда понадобятся, чтобы заранее запросить их из оперативной памяти. 

Зачем нужны виртуальные адреса

Буфер трансляции адреса (translation look-aside buffer, TLB) — еще один отличный пример ассоциативной памяти. Но прежде чем говорить о TLB, разберемся, почему все программы компилируются для работы с виртуальными адресами. Дело в особенностях архитектуры вычислительной техники, которые обусловлены рядом причин.

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

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

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

Единое адресное пространство для каждой программы. Программа может быть скомпилирована с предположением, что код находится в определенном диапазоне адресов, данные — в другом аналогичном, стек — в третьем, а динамическая память (куча, heap) — в четвертом. И это расположение одинаково для каждого экземпляра программы, независимо от того, что делают другие программы в системе.

Поддержка динамических библиотек — например, .dll в Windows и .so в Linux. Они могут быть загружены в виртуальное адресное пространство любой программы по одним и тем же виртуальным адресам, даже если физически находятся в разных местах в RAM.

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

Отображение виртуального адреса на физический выполняет ОС по определенным правилам. Они хранятся в таблице страниц (page table) — это структура данных в оперативной памяти. Чтобы преобразовать виртуальный адрес в физический, нужно:

1. Взять виртуальный адрес.

2. Обратиться к оперативной памяти, чтобы прочитать запись из таблицы страниц.

3. Получить из нее физический адрес.

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

Получается, что каждое обращение к памяти требует двух обращений к оперативной памяти — для:

• трансляции адреса (обращение к таблице страниц),

• доступа к данным.

Это катастрофически медленный процесс, который сводит на нет производительность процессора. 

Будем рады видеть опытных специалистов по разработке микропроцессоров в команде YADRO:

→ RTL Designer (ASIC),
→ Старший инженер по разработке RTL,
→ RTL Verification Engineer,
→ RTL Designer (DFT).

Ускоритель работы с оперативной памятью

На помощь приходит TLB — небольшая и очень быстрая ассоциативная память внутри процессора. Она хранит кеш недавно использованных трансляций адресов.

Основные особенности TLB.

• Очень быстрая: работает на частоте процессора, доступ занимает 1-2 такта.

• Полностью или множественно-ассоциативная: важно избежать конфликтов (как и в кеше).

• Малый размер: обычно 64–1024 записей. Этого достаточно, так как программы в любой момент как правило работают с небольшим набором страниц памяти.

• Многоуровневая организация: как и кеш-память, TLB в современных процессорах имеет уровни L1 и L2 — для баланса скорости и размера.

• Разделение по типу обращений: часто существуют отдельные iTLB для инструкций и dTLB для данных.

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

Если процессору необходимо преобразовать адрес, то он подает его на входы поиска ассоциативной памяти и команду «найди мне это». Всего за один такт ассоциативная часть TLB успевает:

• сверить хранящиеся во всех своих регистрах биты с поданным на ее вход значением; 

• определить, есть ли попадание (hit) в каком-то из регистров или во всех случился промах (miss); 

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

Как все это реализуется? Нам нужна память со специфическим навыком поиска информации внутри себя, а не просто умеющая читать и писать, что ей скажут и куда скажут. Поэтому рассмотренная в предыдущей статье ячейка памяти не подходит. Для поддержки функции поиска ее нужно дооборудовать компаратором, входами SL и SLn (на них подаются прямой и инверсный бит данных для поиска) и выходом М, сигнализирующем о попадании или промахе:

У любого МОП-транзистора есть выводы: сток (С), затвор (З) и исток (И).

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

• Правило №1 — ток между истоком и стоком транзистора течет только в том случае, если на затворе n-канального оказывается логическая единица, а на затворе p-канального — логический ноль (об этом напоминает похожий на ноль кружок на затворе такого транзистора).

• Правило №2 — n-канальный транзистор без потерь напряжения способен передать с истока на сток логический ноль, а p-канальный – логическую единицу. Поэтому каждый из этих типов в КМОП-схемотехнике используется ближе к «своему» уровню напряжения: n-канальные к земле (GND), принимаемой за ноль, а p-канальные – к питанию (VDD), принимаемому за единицу.

Более подробно вопросы построения цифровых схем на МОП-транзисторах с многочисленными простыми экспериментами на макетной плате представлены в разработанном мной курсе по цифровой схемотехнике для начинающих.

Динамический подход

Зная эти простые правила, рассмотрим для начала работу динамического компаратора на транзисторном уровне. В нем всего четыре n-канальных МОП-транзистора.

Если на прямую (SL) и инверсную (SLn) шины поиска данных (search line) подан бит, совпадающий с хранящимся в ячейке (SL=B, SLn=Bn), то по правилу №1 ни в одной из двух последовательных цепочек транзисторов не откроются оба транзистора. Поэтому не будет тока между выходом M и землей GND — узел M не будет разряжаться до напряжения логического нуля.

Если на входы поиска подан бит, отличный от хранимого в ячейке (SL = Bn, SLn = B), то на одной из двух последовательных пар транзисторов оба прибора окажутся открытыми по правилу №1. Выход M через них подключится к земле, и по правилу №2 на M будет логический ноль.

Дальше уже неважно, что содержат остальные ячейки: сравнение идет по всему регистру (или слову), и одного несовпадения бита достаточно, чтобы оно считалось несовпавшим. 

Компаратор позволяет разрядить выход M в ноль. Но как зарядить его обратно до логической единицы? Достаточно одного p-канального транзистора — по правилу №2 именно он без потерь передает высокий уровень напряжения, соответствующий логической единице.

Все M-выходы ячеек в одном регистре объединяются в единый провод — шину совпадения ML (match line). На одном из краев этой шины размещается p-канальный транзистор предзаряда. На его затворе, чтобы транзистор был включен, пока не производится сравнение данных, сигнал PR по правилу №1 равен логическому нулю. По правилу №2 транзистор заряжает всю шину ML до напряжения питания, то есть до логической единицы:

Достоинством такого подхода является его простота: мы добавляем всего четыре транзистора в каждую 6-транзисторную ячейку и еще один общий на весь регистр для предзаряда. Но и недостатки тоже есть — не зря этот вариант назван динамическим по типу схемотехники. 

В отличие от статического подхода, о котором поговорим ниже, здесь заряд узла ML до напряжения питания и разряд его до нуля управляется разными сигналами, а не одним и тем же. А значит, между ними очень трудно соблюсти идеальное согласование во времени. Если предзаряд PR вовремя не переключить в логическую единицу, а поиск дал в какой-то ячейке промах (miss), то в открытом состоянии окажутся сразу три транзистора между землей и питанием: два в компараторе и один в предзаряде. Потечет сквозной ток, а потенциал ML будет «и ни ноль, и ни единица». 

Но и при нормальной работе в случае полного совпадения всех битов в регистре тоже не все гладко с электрической точки зрения. Ведь предзаряд в это время отключен, как и все компараторы всех ячеек регистра. То есть шина ML «болтается в воздухе», улавливая помехи из переключающихся проводов на кристалле вокруг себя как самая обычная антенна. 

Для защиты от помех можно «повесить» на нее простейший RS-триггер из двух закольцованных инверторов, как в ячейке памяти. Но делать триггерслишком большим нельзя — он будет мешать переключать шину ML за минимальное время при несовпадении. А слишком маленький RS-триггер не справится с функцией защиты. 

Кроме того, время разряда ML будет значительно отличаться для случаев несовпадения только в одном бите — шину должен разрядить один компаратор. Если не совпадают все биты, то над над этой задачей работают все ячейки. Это нужно учитывать при выборе момента для считывания сигнала с ML, чтобы он был достоверным.

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

Статическая схемотехника

Какие достоинства и недостатки есть у статического компаратора? Посмотрим на его схему: 

На четырех транзисторах собран логический элемент «Исключающее ИЛИ», состоящий из двух параллельно включенных пар транзисторов обоих типов проводимости. Стоки и истоки у них соединены друг с другом. 

Сигналы с ячейки подаются на них таким образом, что одна пара транзисторов будет находиться в открытом состоянии по правилу №1 всегда,  а не только при отключении предзаряда, который тут становится ненужным. Наличие в каждой паре р-канального и n-канального прибора позволяет ей передать через себя любой логический уровень, пришедший на истоки этой пары транзисторов с шин поиска. Поэтому при совпадении данных на выходе M такой ячейки будет единица (hit), а при несовпадении – ноль (miss) без использования предзаряда.

Объединять ячейки статического типа друг с другом просто проводом нельзя. Допустим, их всего две, и на одной из них есть совпадение, а на другой — промах. Тогда при замыкании их выходов друг на друга возникнет сквозной ток через компараторы двух этих ячеек, и потенциал такого выхода станет тоже неопределенным. Поэтому объединение возможно только через логические вентили. У большого регистра возникает древовидная схема объединения:

Это усложняет как схему, так и топологию такого регистра: нужно суметь «раскидать» дополнительную логику между ячейками и все это соединить проводами, не раздувая регистр по высоте. 

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

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

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

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

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

Ассоциативная память — это не только ячейки

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

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

В случае со статическими схемами добавить маску нетрудно — достаточно дополнить базовую 6-транзисторную ячейку, хранящую бит маски, усилительным вентилем. Он изолирует чувствительный к помехам узел хранения ячейки от остальных частей регистра:

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

С динамическими схемами ситуация другая: нужно гарантировать, что при любых входящих условиях для маскируемого бита динамическая шина ML не разряжалась. Поможет троичная ячейка, у которой помимо состояний «попадание» (hit) и «промах» (miss) есть состояние «всё равно» (don’t care). Вот ее схема:

Когда ничего маскировать не нужно, в обе половинки такого «монстра» записывают противоположные значения: либо ноль слева и единицу справа, либо наоборот. В режиме поиска эта схема работает как самая обычная двоичная ассоциативная ячейка. А при маскировании в обе половинки записываются нули. Тогда при любой комбинации в режиме поиска на входах SL, SLn разряд ML невозможен.

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

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

Наконец, если нужно, может быть выдан номер регистра, где произошло совпадение, и другая служебная информация, которую по ТЗ требуют от разработчика CAM-памяти. Если же совпадения нигде не было, то ассоциативная память сигнализирует о промахе.

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

Вот так устроена память, которую можно спросить: «А помнишь, я тебе рассказывал вот это?» — и она честно ответит, рассказывал или нет.

P. S. Благодарю за помощь в написании статьи моего коллегу Михаила, который недавно опубликовал материал о функциональной верификации цифрового дизайна.