Ассоциативная память представляет собой распределенную память, которая обучается на основе ассоциаций, подобно мозгу живых существ. В информационных технологиях память, доступ к которой производится не по адресу, а по содержанию. Модель, реализующая ассоциативную память, должна распознать требуемый образ и извлечь его.
В отличие от обычной машинной памяти, в которой пользователь задает адрес памяти и ОЗУ возвращает слово данных, хранящееся по этому адресу, АП разработана таким образом, чтобы пользователь задавал слово данных, и АП ищет его во всей памяти, чтобы выяснить, хранится ли оно где-нибудь в нем. Если слово данных найдено, АП возвращает список одного или более адресов хранения, где слово было найдено (и в некоторых архитектурах, также возвращает само слово данных, или другие связанные части данных). Таким образом, АП - аппаратная реализация того, что в терминах программирования назвали бы ассоциативным массивом.
Автоассоциативная память
Гетероассоциативная память
Охарактеризуйте две фазы в работе ассоциативной памяти
-ключевой образ, 
-запомненный вектор образов, 
-количество образов(ёмкость). Ключевой образ выступает не просто в роли стимула, определяющим местоположение запомненного образа , но и содержит ключ для его извлечения.Фаза восстановления. Соответствует процессу извлечения запомненного образа в ответ на представление в сеть зашумлённой или искажённой версии ключа.
Приведите определение процесса распознавания образов
Охарактеризуйте два типа машин распознавания образов.
Система состоит из двух частей: сети извлечения признаков (без учителя) и сети классификации (с учителем). Образ – набор из 
наблюдений, каждое наблюдение можно рассматривать точкой 
в -мерном пространстве наблюдений (данных). Извлечение признаков описывается с помощью преобразования, которое переводит в промежуточную точу 
в -мерном пространстве признаков 
. Это преобразование можно рассматривать как операцию снижения размерности (сжатие данных), что упрощает задачу классификации. Классификация – преобразование, которое отображает промежуточную точку в один из классов 
-мерного пространства решений ( - количество выделяемых классов).
2ой тип машины.
Система проектируется как единая многослойная сет прямого распространения, использующая один из алгоритмов обучения с учителем. При этом подходе задача извлечения признаков выполняется вычислительными узлами скрытого слоя сети.
Опишите способ решения задачи идентификации систем.
Описывает соотношение между входом и выходом в неизвестной системе с несколькими входами и выходами без памяти (инвариантность системы по времени). Тогда множество маркированных примеров можно использовать для обучения нейронной сети, представляющей модель этой системы. Пусть 
- выход нейронной сети, соответствующей входному вектору 
. Сигнал ошибки (
=
(желаемый отклик) - (выход сети)) используется для корректировки свободных параметров сети с целью минимизации среднеквадратичной ошибки 
Опишите способ построения инверсной системы
генерирует отклик в виде вектора . Инверсную систему можно описать следующим образом: 
вектор-функция 
-инверсная. На основе множества маркированных примеров (
) можно построить нейронную сеть, аппроксимирующую обратную функцию с помощью схемы:
()-желаемый отклик, () – входной сигнал (векторы , - поменялись местами). Вектор сигнал ошибки 
равен разности желаемого вектора и реального выхода нейронной сети , полученный в ответ на возмущение . Здесь вектор сигнала ошибки используется для минимизации суммы квадратов разностей между выходами неизвестной инверсной системы и нейронной сети в статическом смысле (т.е. вычисляемой на всём множестве примеров обучения).
Приведите блок-схему системы управления с обратной связью
В этой системе используется единственная обратная связь, охватывающая весь объект управления. Таким образом, выход объекта управления вычитается из эталонного сигнала (), принимаемого из внешнего источника. Полученный таким образом сигнал ошибки (e) подаётся на нейроконтроллер для настройки свободных параметров. Основной задачей контроллера является поддержание такого входного вектора объекта, для которого выходной сигнал (у) соответствовал бы эталонному значению (d). Другими словами, в задачу контроллера входит инвертирование отображения вход-выход объекта управления.
Опишите операции логической суммы и логического произведения над нечёткими множествами
, которая равна 1, если элемент принадлежит множеству A, или равна 0 в противном случае. В нечётких системах элемент может частично принадлежать любому множеству. Степень принадлежности множеству A, представляющая собой обобщение характеристической функции, называется функцией принадлежности , причём 
, и 
означает отсутствие принадлежности x множеству A, а 
- полную принадлежность. Конкретное значение функции принадлежности называется степенью или коэффициентом принадлежности.Операция логической суммы:
Пусть 
- наименьшее нечёткое подмножество, которое включает как 
так и 
с функцией принадлежности:
Операция логического произведения над нечёткими множествами:
Пусть 
- наибольшее нечёткое подмножество, которое содержится одновременно в и в , тогда функция принадлежности имеет вид:
Опишите операции отрицания множества и нормализации множества для нечётких множеств
Пусть 
- всё то множество, что не 
, тогда элемент, принадлежащий множеству , определяется согласно функции:
Нормализация нечётких множеств:
СУПРЕМУМ: Sup - точная верхняя грань (максимальное значение принадлежности, присутствующее в множестве).
НОРМАЛИЗАЦИЯ: нечеткое множество нормально если супремум множества равен единице. Для нормализации перечитывают принадлежности элементов:
M"a(x) = Ma(x)/(Sup Ma(x))
Опишите операцию концентрации и растяжения для нечётких множеств
Операция размывания: 
Дайте определение лингвистической переменной
Математическое определение лингвистической переменной: 
, где -имя переменной; 
-множество имён лингвистических значений переменной , каждое из которых является нечёткой переменой на множестве 
; 
- синтаксическое правило для образования имён значений ; 
семантическое правило для ассоциирования каждой величины значения с её понятием.
Опишите операцию алгебраического произведения для нечётких множеств
(агрегирование предпосылки).
Опишите меру Егера, характеризующую степень нечёткости множеств
,
количество элементов в , 
расстояние между множествами и в метрике 
(которое равно 1 или 2). Метрике Хэмминга соответствует значение 
Опишите метрику Евклида, характеризующую меру нечёткости множества
называется евклидовой метрикой: 
.
Опишите энтропийную меру нечёткости множества Коско
Кардинальное число множества 
сумма коэффициентов принадлежности всех элементов этого множества, т.е. 
.
Опишите систему нечёткого вывода Мамдани-Заде
множество используемых нечетких правил;
базу данных, содержащую описания функций принадлежности;
механизм вывода и агрегирования, который формируется применяемыми правилами импликации.
Для обеспечения взаимодействия этих двух видов вводится нечеткая система с так называемым фазификатором (преобразователем множеств входных данных в нечеткое множество) на входе и дефазификатором (преобразователем нечетких множеств в конкретное значение выходной переменной) на выходе.
Выходной сигнал модуля вывода может иметь вид нечетких множеств, определяющих диапазон изменения выходной переменной. Дефазификатор преобразует этот диапазон в одно конкретное значение, принимаемое в качестве выходного сигнала всей системы.
В модели вывода Мамдани-Заде присутствуют следующие операторы:
Рис 1. Пример системы вывода Мамдани-Заде
На рис. 1 представлен способ агрегирования при двух входных переменных .
Охарактеризуйте фаззификатор
Охарактеризуйте понятие функции принадлежности
Коэффициент принадлежности - величина из диапазона , характеризующая степень принадлежности элемента нечеткому множеству.
Действительное число, принимающее значение в диапазоне (0,1), при этом 1 означает 100%-ю (безусловную) принадлежность a к множеству , а 0 - безусловное отсутствие в . Значения между 0 и 1 характеризуют нечётко включенные элементы.
Отображение множества элементов во множество значений образует функцию принадлежности .
Функция может быть определена явно в виде, например, алгебраического выражения или таблично (дискретно) в виде массива пар
Опишите обобщённую гауссовскую функцию принадлежности
и параметром ширины 
имеет вид: 
Также существует обобщённая гауссова функция: 
параметр формы. 
Рис 3. График обобщённой функции Гаусса для с=1,
Обобщённая функция Гаусса также может быть и в рациональной форме: 
.
Опишите понятие дефаззификации нечёткого множества
Опишите дефаззификацию относительно среднего центра
где 
центр 
-ой одиночной функции принадлежности, участвующей в итоговой агрегированной функции.
Опишите дефаззификацию относительно центра области
или же в дискретной форме 
.
Приведите блок-схему работы генетического алгоритма.
Охарактеризуйте понятия целочисленного и вещественного кодирования.
Как правило, в хромосоме кодируются численные параметры решения. Для этого возможно использование целочисленного и вещественного кодирования.
Целочисленное кодирование.
В классическом генетическом алгоритме хромосома представляет собой битовую строку, в которой закодированы параметры решения поставленной задачи.
Вещественное кодирование.
Часто бывает удобнее кодировать в гене не целое число, а вещественное. Это позволяет избавиться от операций кодирования и декодирования, используемых в целочисленном кодировании и увеличить точность решения.
Опишите способы селекции.
Рулеточная селекция. В данном варианте селекции вероятность i-й особи принять участие в скрещивании pi пропорциональна значению ее приспособленности fi и равна .
Процесс отбора особей для скрещивания напоминает игру в «рулетку».
Рулеточный круг делится на сектора, причем площадь i-го сектора пропорциональна значению pi. После этого n раз «вращается» рулетка, где n – размер популяции, и по сектору, на котором останавливается рулетка, определяется особь, выбранная для скрещивания.
Селекция усечением.
При отборе усечением после вычисления значений приспособленности для скрещивания выбираются Ln лучших особей, где L – «порог отсечения», 0
Как правило, выбирают L в интервале от 0,3 до 0,7.
Турнирный отбор. В случае использования турнирного отбора для скрещивания, как и при рулеточной селекции, отбираются n особей.
Для этого из популяции случайно выбираются t особей, и самая приспособленная из них допускается к скрещиванию. Говорят, что формируется турнир из t особей, t – размер турнира. Эта операция повторяется n раз.
Чем больше значение t, тем больше давление селекции. Вариант турнирного отбора, когда t = 2, называют бинарным турниром. Типичные значения размера турнира t = 2, 3, 4, 5.
28. Охарактеризуйте принцип работы одноточечного, двухточечного и однородного операторов кроссовера для целочисленного кодирования.
Для целочисленного кодирования часто используются 1-точечный, 2-точечный и однородный операторы кроссинговера.
1-точечный кроссинговер работает аналогично операции перекреста для хромосом при скрещивании биологических организмов. Для этого выбирается произвольная точка разрыва и для создания потомков производится обмен частями родительских хромосом.
Для оператора 2-точечного кроссинговера выбираются 2 случайные точки разрыва, после чего для создания потомков родительские хромосомы обмениваются участками, лежащими между точками разрыва. Отметим, что для 2-точечного оператора кроссинговера, начало и конец хромосомы считаются «склеенными» в результате чего одна из точек разрыва может попасть в начало/конец хромосом и в таком случае результат работы 2-точечного кроссинговера будет совпадать с результатом работы 1-точечного кроссинговера.
При использовании однородного оператора кроссинговера разряды родительских хромосом наследуются независимо друг от друга. Для этого определяют вероятность p0, что i-й разряд хромосомы 1-го родителя попадет к первому потомку, а 2-го родителя – ко второму потомку. Вероятность противоположного события равна (1 – p0). Каждый разряд родительских хромосом «разыгрывается» в соответствии со значением p0 между хромосомами потомков. В большинстве случаев вероятность обоих событий одинакова, т.е. p0 = 0,5.
29. Опишите принцип работы двухточечного кроссовера для вещественного кодирования.
2-точечный кроссинговер для вещественного кодирования в целом аналогичен 2-точечному кроссинговеру для целочисленного кодирования. Различие заключается в том, что точка разрыва не может быть выбрана «внутри» гена, а должна попасть между генами
30. Охарактеризуйте понятие разрушающей способности кроссовера.
Операторы кроссинговера характеризуются способностью к разрушению родительских хромосом.
Кроссинговер для целочисленного кодирования считается более разрушительным, если в результате его применения расстояние по Хэммингу между получившимися хромосомами потомков и хромосомами родителей велико.
Другими словами, способность целочисленного кроссинговера к разрушению зависит от того, насколько сильно он «перемешивает» (рекомбинирует) содержимое родительских хромосом. Так, 1-точечный кроссинговер считается слаборазрушающим, а однородный кроссинговер в большинстве случаев является сильно разрушающим оператором. Соответственно, 2-точечный кроссинговер по разрушающей способности занимает промежуточную позицию по отношению к 1-точечному и однородному операторам кроссинговера.
В случае кроссинговера для вещественного кодирования способность к разрушению определяется тем, насколько велико расстояние в пространстве поиска между точками, соответствующими хромосомам родителей и потомков. Таким образом, разрушающий эффект 2 точечного кроссинговера зависит от содержимого родительских хромосом. Разрушающая способность арифметического кроссинговера зависит от значения параметра l, например, при l >> 1 и l >> 0, способность к разрушению будет низкой. Для BLX-a кроссинговера разрушающая способность зависит как от значения a, так и от разности значений соответствующих генов родительских особей.
Отметим, что одновременно со способностью к разрушению говорят также о способности к созданию (creation, construction) кроссинговером новых особей. Тем самым подчеркивается, что, разрушая хромосомы родительских особей, кроссинговер может создать совершенно новые хромосомы, не встречавшиеся ранее в процессе эволюционного поиска.
31. Охарактеризуйте канонический генетический алгоритм.
Канонический генетический алгоритм разработан Джоном Холландом и описан в его книге «Адаптация в естественных и искусственных системах», 1975 г. . Представляет одну из базовых моделей эволюционного поиска, подробно исследованную в 70-80-х годах 20 века.
Канонический ГА имеет следующие характеристики:
Целочисленное кодирование;
Все хромосомы в популяции имеют одинаковую длину;
Постоянный размер популяции;
Рулеточная селекция;
Одноточечный оператор кроссинговера;
Битовая мутация;
Новое поколение формируется только из особей-потомков (разрыв поколений Т = 1).
32. Какие вы знаете модели представления знаний?
Наиболее распространенными моделями представления знаний в экспертных системах являются:
модель представления знаний средствами логики предикатов первого порядка;
продукционная модель;
фреймовая модель;
модель представления знаний в виде семантической сети;
модель представления знаний в виде доски объявлений;
модель представления знаний в виде сценария;
модель представления знаний на основе нечеткой логики;
нейросетевая модель представления знаний.
Логическая модель представления знаний основана на логике предикатов. Предикатом, или логической функцией, называется функция от любого числа аргументов, принимающей истинное или ложное значение. Аргументы функции – значения из произвольного, конечного или бесконечного множества 
, называемого предметной областью. Предикат от 
-аргументов называют -местным предикатом. Для модели представления знаний используется логика предикатов первого порядка, на которой основан Пролог.
34. Из чего состоит продукционная система?
Продукционная система – система обработки знаний, использующая представления знаний продукционными правилами. Продукционные правила – это выражения типа «Если (условие) то (действие)». “Условие” – предложение образец, по которому осуществляется поиск в базе знаний; “действие” – действие, выполняемое при успешном исходе поиска. Вывод на такой базе знаний может быть прямым (от данных к поиску цели) и обратным (от цели для её подтверждения – к данным). Данные – исходные факты, хранящиеся в базе фактов, на основании которых запускается машина вывода или интерпретатор правил, перебирающий правила из продукционной базы знаний.
В состав продукционной системы входят база правил, база данных и интерпретатор правил. База правил – это область памяти, которая содержит базу знаний – совокупность знаний, представленных в форме правил вида ЕСЛИ … ТО; база данных – это область памяти, содержащая фактические данные (факты). Интерпретатор – механизм вывода, это тот компонент системы, который формирует заключение, используя базу правил и базу данных.
35. Охарактеризуйте модель представления знаний в виде фреймов
Во фреймовой системе единицей представления знаний является объект, называемый фреймом. Фрейм – форма представления некоторой ситуации, которую можно описывать некоторой совокупностью понятий и сущностей. В качестве идентификатора фрейму присваивается имя. Это имя должно быть единственным во всей фреймовой системе. Фрейм имеет определенную внутреннюю структуру, состоящую из множества элементов, называемых слотами, которым также присваиваются имена. Каждый слот, в свою очередь, представляется определенной структурой данных. Иногда слот включает компонент, называемый фасетом, который задает диапазон или перечень его возможных значений. Фасет указывает также граничные значения заполнителя слота (например, максимально допустимое число братьев
36. Каким образом осуществляется представление знаний в семантической сети?
Семантическая сеть представляет знания в виде графа, узлы которого соответствуют фактам или понятиям, а дуги – отношения между понятиями. Граф представляет собой множество вершин и множество дуг, соединяющих некоторые пары вершин. Размеченный граф для каждой вершины содержит дескрипторы (метки), благодаря которым вершины графа отличаются между собой. Для графа пространства состояний дескрипторы идентифицируют состояния в процессе решения задачи. Метки дуг в семантических сетях применяются для задания именованных отношений.
37. Опишите архитектуру экспертных систем
Группа экспертов или иной источник экспертизы обеспечивает загрузку в базу знаний фактов, наблюдений и способов анализа ситуаций. Пользователь запрашивает систему о конкретных проблемах через интерфейс, который допускает общение с использованием обычных выражений.
Информация, содержащаяся в базе знаний, обрабатывается с помощью машины вывода, которая использует эмпирические ассоциации или правила «ЕСЛИ … ТО» для формирования и проверки возможных решений. Интерфейс пользователя в доступной форме передает полученные результаты оператору.
В мощных интеллектуальных системах существует интерфейс на естественном языке, который позволяет задавать вопросы и получать ответы на обычном английском или русском языках. В случае обычных интеллектуальных систем пользователю предоставляется не столь изысканный, но тем не менее «дружественный» интерфейс.
38. Опишите функции машины (механизма) вывода
Главным в ЭС является механизм, осуществляющий поиск в БЗ по правилам рациональной логики, для получения решений. Этот механизм, называемый машиной вывода, приводится в действие при получении запроса пользователя и выполняет следующие задачи:
сравнивает информацию, содержащуюся в запросе пользователя, с информацией базы знаний;
ищет определенные цели или причинные связи;
оценивает относительную определенность фактов, основываясь на соответствующих коэффициентах доверия, связанных с каждым фактом.
39. Приведите структурную схему, описывающую этапы технологии создания экспертных систем
На этапе идентификации определяются задачи, которые подлежат решению, выявляются цели разработки, ресурсы, эксперты и категории пользователей.
На этапе получения знаний выделяют три стратегии: приобретение знаний, извлечение знаний и обнаружение знаний. Под приобретением знаний понимается способ автоматизированного наполнения базы знаний посредством диалога эксперта и специальной программы. Извлечением знаний называют процедуру взаимодействия инженера по знаниям с источником знаний (экспертом, специальной литературой и т.д.) без использования вычислительной техники. Термин обнаружение знаний связывают с созданием компьютерных систем, реализующих методы автоматического получения знаний. Сейчас это направление является наиболее перспективным. При этом предполагается, что система сама сможет раскрыть закономерности предметной области и сформулировать необходимые знания на основе имеющегося эмпирического материала.
На этапе концептуализации проводится анализ проблемной области, выявляются используемые понятия и их взаимосвязи, определяются методы решения задач.
Этап формализации определяет способы представления всех видов знаний, формализует основные понятия, определяет способы интерпретации знаний, моделирует работу системы. На этом этапе оценивается адекватность целям системы зафиксированных понятий, методов решения, средств представления и манипулирования знаниями.
На этапе выполнения осуществляется наполнение БЗ системы. На этапе тестирования эксперт (и инженер по знаниям) в интерактивном режиме, используя диалоговые и объяснительные средства, проверяет компетентность ЭС. Процесс тестирования продолжается до тех пор, пока эксперт не решит, что система достигла требуемого уровня компетентности.
На этапе опытной эксплуатации проверяется пригодность ЭС для конечных пользователей. По результатам этого этапа, так же как и этапа тестирования, может потребоваться существенная модификация ЭС.
Процесс создания ЭС не сводится к соблюдению строгой последовательности перечисленных выше этапов. В ходе разработки приходится неоднократно возвращаться на более ранние этапы и пересматривать принятые там решения.
страница 1 многоуровневой таблице страниц требует нескольких обращений к основной памяти, поэтому занимает много времени. В некоторых случаях такая задержка недопустима. Проблема ускорения поиска решается на уровне архитектуры компьютера.
В соответствии со свойством локальности большинство программ в течение некоторого промежутка времени обращаются к небольшому количеству страниц, поэтому активно используется только небольшая часть таблицы страниц .
Естественное решение проблемы ускорения – снабдить компьютер аппаратным устройством для отображения виртуальных страниц в физические без обращения к таблице страниц , то есть иметь небольшую, быструю кэш-память, хранящую необходимую на данный момент часть таблицы страниц . Это устройство называется ассоциативной памятью , иногда также употребляют термин буфер поиска трансляции (translation lookaside buffer – TLB).
Одна запись таблицы в ассоциативной памяти (один вход) содержит информацию об одной виртуальной странице: ее атрибуты и кадр, в котором она находится. Эти поля в точности соответствуют полям в таблице страниц .
Так как ассоциативная память содержит только некоторые из записей таблицы страниц , каждая запись в TLB должна включать поле с номером виртуальной страницы . Память называется ассоциативной , потому что в ней происходит одновременное сравнение номера отображаемой виртуальной страницы с соответствующим полем во всех строках этой небольшой таблицы . Поэтому данный вид памяти достаточно дорого стоит. В строке, поле виртуальной страницы которой совпало с искомым значением, находится номер страничного кадра. Обычное число записей в TLB от 8 до 4096. Рост количества записей в ассоциативной памяти должен осуществляться с учетом таких факторов, как размер кэша основной памяти и количества обращений к памяти при выполнении одной команды.
Рассмотрим функционирование менеджера памяти при наличии ассоциативной памяти .
В начале информация об отображении виртуальной страницы в физическую отыскивается в ассоциативной памяти . Если нужная запись найдена – все нормально, за исключением случаев нарушения привилегий, когда запрос на обращение к памяти отклоняется.
Если нужная запись в ассоциативной памяти отсутствует, отображение осуществляется через таблицу страниц . Происходит замена одной из записей в ассоциативной памяти найденной записью из таблицы страниц . Здесь мы сталкиваемся с традиционной для любого кэша проблемой замещения (а именно какую из записей в кэше необходимо изменить). Конструкция ассоциативной памяти должна организовывать записи таким образом, чтобы можно было принять решение о том, какая из старых записей должна быть удалена при внесении новых.
Число удачных поисков номера страницы в ассоциативной памяти по отношению к общему числу поисков называется hit (совпадение) ratio (пропорция, отношение). Иногда также используется термин "процент попаданий в кэш". Таким образом, hit ratio – часть ссылок, которая может быть сделана с использованием ассоциативной памяти . Обращение к одним и тем же страницам повышает hit ratio. Чем больше hit ratio, тем меньше среднее время доступа к данным, находящимся в оперативной памяти.
Предположим, например, что для определения адреса в случае кэш-промаха через таблицу страниц необходимо 100 нс, а для определения адреса в случае кэш-попадания через ассоциативную память – 20 нс . С 90% hit ratio среднее время определения адреса – 0,9x20+0,1x100 = 28 нс .
Вполне приемлемая производительность современных ОС доказывает эффективность использования ассоциативной памяти . Высокое значение вероятности нахождения данных в ассоциативной памяти связано с наличием у данных объективных свойств: пространственной и временной локальности.
Необходимо обратить внимание на следующий факт. При переключении контекста процессов нужно добиться того, чтобы новый процесс "не видел" в ассоциативной памяти информацию, относящуюся к предыдущему процессу, например очищать ее. Таким образом, использование ассоциативной памяти увеличивает время переключения контекста.
Рассмотренная двухуровневая (ассоциативная память + таблица страниц ) схема преобразования адреса является ярким примером иерархии памяти, основанной на использовании принципа локальности, о чем говорилось во введении к предыдущей лекции.
Инвертированная таблица страниц
Несмотря на многоуровневую организацию, хранение нескольких таблиц страниц большого размера по-прежнему представляют собой проблему. Ее значение особенно актуально для 64-разрядных архитектур, где число виртуальных страниц очень велико. Вариантом решения является применение инвертированной таблицы страниц (inverted page table). Этот подход применяется на машинах PowerPC, некоторых рабочих станциях Hewlett-Packard, IBM RT, IBM AS/400 и ряде других.
В этой таблице содержится по одной записи на каждый страничный кадр физической памяти. Существенно, что достаточно одной таблицы для всех процессов. Таким образом, для хранения функции отображения требуется фиксированная часть основной памяти, независимо от разрядности архитектуры, размера и количества процессов.
Несмотря на экономию оперативной памяти, применение инвертированной таблицы имеет существенный минус – записи в ней (как и в ассоциативной памяти ) не отсортированы по возрастанию номеров виртуальных страниц, что усложняет трансляцию адреса. Один из способов решения данной проблемы – использование хеш-таблицы виртуальных адресов . При этом часть виртуального адреса , представляющая собой номер страницы, отображается в хеш-таблицу с использованием функции хеширования. Каждой странице физической памяти здесь соответствует одна запись в хеш-таблице и инвертированной таблице страниц . Виртуальные адреса , имеющие одно значение хеш-функции, сцепляются друг с другом. Обычно длина цепочки не превышает двух записей.
Размер страницы
Разработчики ОС для существующих машин редко имеют возможность влиять на размер страницы. Однако для вновь создаваемых компьютеров решение относительно оптимального размера страницы является актуальным. Как и следовало ожидать, нет одного наилучшего размера. Скорее есть набор факторов, влияющих на размер. Обычно размер страницы – это степень двойки от 2 9 до 2 14 байт.
Однако зонтик, конечно же, остается на полке, потому что сознание человека, стоящего на пороге своей квартиры, заполнено совсем иными проблемами...
В попытках как-то объяснить этот обескураживающий феномен нейробиологи из Института биологических исследований Солка (Salk Institute for Biological Studies) в пригороде Сан-Диего (США, штат Калифорния) провели серию интересных экспериментов. Институт Солка - это независимая некоммерческая организация, занимающаяся фундаментальными исследованиями, лечением людей и обучением будущих специалистов, а назван этот институт по имени его основателя (1965) - иммунолога Джонаса Эдвардса Солка (Jonas Edward Salk (1914-1995), в свое время одержавшего победу над полиомиелитом). О полученных результатах сообщается в выпуске журнала Neuron ("Нейрон") от 20 октября. Грубо говоря, удалось впервые показать, что мозг помнит про грозовую угрозу, даже если мы ее игнорируем и оставляем зонтик дома.
"Впервые при взгляде на мозговую активность обезьяны резус мы научились отгадывать, что в действительности знает животное", - говорит Томас Д. Олбрайт (Thomas D. Albright), что руководит Vision Center Laboratory. А основной автор исследования, Адам Мессинджер (Adam Messinger), бывший аспирант Олбрайта, который ныне трудится в американском Национальном институте психического здоровья (National Institute of Mental Health - NIMH), сравнивает предмет своего изучения с подсознательным знанием. Это знание остается у нас даже в том случае, если оно недоступно непосредственно сознанию. Он приводит такой пример: "Вы знаете, что встретили жену вашего коллеги по работе, хотя и не способны вспомнить ее лицо".
Человеческая память полагается главным образом на ассоциации ; когда мы пытаемся восстановить какую-либо информацию, один предмет напоминает нам о каком-то другом, который в свою очередь напоминает нам о третьем, и так далее... Как раз на учете этого обстоятельства и основаны, например, феноменальные успехи рекордсменов по запоминанию цифровых рядов, увязывающих с каждой цифрой какие-то более привычные предметы из окружающего мира - это так называемые мнемонические приемы. Разумеется, нейробиологи уже давно и весьма активно пытаются разобрать устройство всей этой ассоциативной памяти "по винтикам". Некоторые специалисты вообще утверждают, что внутри нас запрятано по меньшей мере два типа памяти (а кто-то насчитывает их до десяти разновидностей, но это уже скорее из области курьезов). Первая - основная память - функционально связана с работой фронтальной коры головного мозга, а вторая, гораздо более емкая, - ютится в специфической области мозга, получившей название нижней височной коры (inferior temporal cortex - ITC). Именно там хранится информация едва ли не обо всех событиях нашей жизни. Правда, памятные следы в височной коре окружены неработающими участками мозга, они как бы замурованы. И активизировать, пробудить эту память можно, например, в состоянии гипнотического транса с помощью особых наводящих вопросов.
Еще один способ изучения ассоциативной памяти (реализованный исследователями из Института Солка) состоит в том, чтобы обучать подключенных к приборам макак-резусов (обезьян из рода макак) запоминанию пар каких-нибудь символов. При показе первого из запоминаемых парных символов (например, картинки с изображением хмурых облаков) обезьянам предлагаются на выбор два варианта, правильным из которых считается лишь один - тот, что связан с начальным стимулом (в данном случае это будет зонтик). Награда за правильный выбор - глоток обожаемого обезьянами фруктового сока.
"Мы старались, чтобы обезьяны не ошибались в ходе этих тестов, однако случались и серии ошибок, - поясняет Олбрайт. - И нам стало интересно, что же происходит в их мозгу, когда обезьяны делают явно неверный выбор, несмотря на то, что они наверняка должны были бы помнить правильную связь пары символов". И вот в то время как обезьяны пробовали вспомнить - то есть восстановить правильные ассоциативные связи - и делали-таки свой ошибочный выбор, ученые стали наблюдать сигналы от невроцитов (нервных клеток, нейронов) в этой самой нижней височной коре головного мозга. А теперь уже точно известно, что эта область критически важна для процессов визуального распознавания различных структур и к тому же отвечает за работу именно этого типа памяти.
После того, как Олбрайт и его группа проанализировали картины активности мозговых клеток в нижней височной коре, они сделать вывод о том, что более 50 процентов тамошних активных невроцитов можно смело отнести к особому новому классу нейронов, в которых, как считают исследователи, и закодирована память о правильных соединениях "стимула" и связанного с ним символа.
А самым удивительным во всей этой истории кажется то, что эти специализированные мозговые клетки продолжали посылать свои "правильные" импульсы даже тогда, когда обезьяны выбирали символы неверные. "В этом смысле мозговые клетки "знают" больше, чем обезьяны обнаруживают своим поведением", - говорит Олбрайт. Ведь в реальном мире обезьян (как и людей) все время что-нибудь отвлекает, то есть не дает как следует сосредоточиться и сбивает с правильных мыслей, не позволяет обратиться к истинной памяти...
Способы организации памяти
| Наименование параметра | Значение |
| Тема статьи: | Способы организации памяти |
| Рубрика (тематическая категория) | Компьютеры |
Функционально ЗУ любого типа всегда состоят из запоминающего массива, хранящего информацию, и вспомогательных, весьма сложных блоков, служащих для поиска в массиве, записи и считывания (и, в случае если требуется, для регенерации).
Запоминающий массив (ЗМ) состоит из множества одинаковых запоминающих элементов (ЗЭ). Все ЗЭ организованы в ячейки, каждая из которых предназначена для хранения единицы информации в виде двоичного кода, число разрядов которого определяется шириной выборки. Способ организации памяти зависит от методов размещения и поиска информации в ЗМ. По этому признаку различают адресную, ассоциативную и стековую память.
АДРЕСНАЯ ПАМЯТЬ
В памяти с адресной организацией размещение и поиск информации в ЗМ основаны на использовании адреса хранения единицы информации, которую в дальнейшем для краткости будем называть словом . Адресом служит номер ячейки ЗМ, в которой это слово размещается. При записи (считывании) слова в ЗМ инициирующая эту операцию команда должна указывать адрес (номер) ячейки, по которому нужно произвести запись (считывание).
На рис. 5.2 изображена обобщенная структура адресной памяти.
Цикл обращения к памяти инициализируется поступающим в БУП сигналом "Обращение". Общая часть цикла обращения включает в себя прием в РгА с шины адреса (ША) адреса обращения и прием в БУП управляющего сигнала "Операция", указывающего вид запрашиваемой операции (считывание или запись).
Считывание . БАВ дешифрирует адрес и посылает сигнал, выделяющий заданную адресом ячейку ЗМ. В общем случае БАВ может также посылать в выделенную ячейку памяти сигналы, настраивающие ЗЭ ячейки на запись или считывание. После этого записанное в ячейку слово считывается усилителями БУС и передается в РгИ. Далее в памяти с разрушающим считыванием происходит регенерация информации путем записи слова из РгИ через БУЗ в ту же ячейку ЗМ. Операция считывания завершается выдачей слова из РгИ на выходную информационную шину ШИ вых.
Запись. Помимо указанной выше общей части цикла обращения происходит прием записываемого слова с входной шины ШИ вх в РгИ. Сама запись в общем случае состоит из двух операций – очистки ячейки и собственно записи. Для этого БАВ сначала производит выборку и очистку ячейки, заданной адресом в РгА. Очистка ячейки ЗМ (приведение в исходное состояние) может осуществляться по-разному. В частности, в памяти с разрушающим считыванием очистку можно производить сигналом считывания слова в ячейке при блокировке БУС (чтобы в РгИ не поступила информация). Далее в выбранную ячейку записывается новое слово.
Необходимость в операции очистки ячейки перед записью, так же как и в операции регенерации информации при считывании, определяется типом используемых ЗЭ, способами управления, особенностями электронной структуры БИС памяти, в связи с этим в полупроводниковых памятях эти операции могут отсутствовать.
БУП генерирует необходимые последовательности управляющих сигналов, инициирующих работу отдельных узлов памяти. Следует иметь в виду, что БУП должна быть весьма сложным устройством (своеобразным управляющим контроллером, имеющим собственную кэш-память), придающим БИСу памяти в целом специальные потребительские свойства, такие как многопортовость, конвейерная выдача информации и т.п.
АССОЦИАТИВНАЯ ПАМЯТЬ
В памяти этого типа поиск информации происходит не по адресу, а по ее содержанию. Под содержанием информации в данном случае принято понимать не смысловая нагрузка лежащего на хранении в ячейке памяти слова, а содержание ЗЭ ячейки памяти, ᴛ.ᴇ. побитовый состав записанного двоичного слова. При этом ассоциативный запрос (признак) также представляет собой двоичный код с определенным побитовым составом. Поиск по ассоциативному признаку происходит параллельно во времени для всех ячеек ЗМ и представляет собой операцию сравнения содержимого разрядов регистра признака с содержимым соответствующих разрядов ячеек памяти. Для организации такого поиска все ЗЭ ЗМ снабжены однобитовыми процессорами, в связи с этим в ряде случаев память такого типа рассматривают как многопроцессорную систему.
Полностью ассоциативная память большого объёма является очень дорогостоящим устройством, в связи с этим для ее удешевления уменьшают число однобитовых процессоров до одного на ячейку памяти. В этом случае сравнение ассоциативного запроса с содержимым ячеек памяти идет последовательно для отдельных разрядов, параллельно во времени для всех ячеек ЗМ.
При очень больших объёмах памяти на определенных классах задач ассоциативный поиск существенно ускоряет обработку данных и уменьшает вероятность сбоя в ЭВМ. Вместе с тем, ассоциативные ЗУ с блоками соответствующих комбинационных схем позволяют выполнить в памяти достаточно сложные логические операции: поиск максимального или минимального числа в массиве, поиск слов, заключенных в определенные границы, сортировку массива и т.д.
Следует отметить, что ассоциативный поиск можно реализовать и в компьютере с обычной адресной памятью, последовательно вызывая записанные в ячейки памяти слова в процессор и сравнивая их с некоторым ассоциативным признаком (шаблоном). При этом при больших объёмах памяти на это будет затрачено много времени. При использовании ассоциативной памяти можно, не считывая слов из ОП в процессор, за одно обращение определить количество слов, отвечающих тому или иному ассоциативному запросу. Это позволяет в больших базах данных очень оперативно реализовать запрос типа: сколько жителей области не представило декларацию о доходах и т.п.
В некоторых специализированных ЭВМ ОП или его часть строится таким образом, что позволяет реализовать как ассоциативный, так и адресный поиск информации.
Упрощенная структурная схема ассоциативной памяти, в которой все ЗЭ ЗМ снабжены однобитовыми процессорами, приведена на рис. 5.3.
Первоначально рассмотрим операцию, называющуюся контроль ассоциации . Эта операция является общей для операции считывания и записи, а также имеет самостоятельное значение.
По входной информационной шине в РгАП поступает n-разрядный ассоциативный запрос, ᴛ.ᴇ. заполняются разряды от 0 до n-1. Одновременно в РгМ поступает код маски поиска, при этом n-й разряд РгМ устанавливается в 0. Ассоциативный поиск производится лишь для совокупности разрядов РгАП, которым соответствуют 1 в РгМ (незамаскированные разряды РгАП). Важно заметить, что для слов, в которых цифры в разрядах совпали с незамаскированными разрядами РгАП, КС устанавливает 1 в соответствующие разряды РгСв и 0 в остальные разряды.
Комбинационная схема формирования результата ассоциативного обращения ФС формирует из слова, образовавшегося в РгСв, как минимум три сигнала:
A 0 – отсутствие в ЗМ слов, удовлетворяющих ассоциативному признаку;
A 1 – наличие одного такого слова;
A 2 – наличие более чем одного слова.
Возможны и другие операции над содержимым РгСв, к примеру подсчет количества единиц, ᴛ.ᴇ. подсчет слов в памяти, удовлетворяющих ассоциативному запросу, и т.п.
Формирование содержимого РгСв и a 0 , a 1 , a 2 по содержимому РгАП, РгМ, ЗМ и принято называть операцией контроля ассоциации.
Считывание. Сначала производится контроль ассоциации по признаку в РгАП.
A 0 = 1 – считывание отменяется из-за отсутствия искомой информации;
A 1 = 1 – считывается в РгИ найденное слово, после чего выдается на ШИ вых;
A 2 = 1 – считывается слово, имеющее, к примеру, наименьший номер среди ячеек, отмеченных 1 в РгСв, после чего выдается на ШИ вых.
Запись. Сначала отыскивается свободная ячейка (полагаем, что в разряде занятости свободной ячейки записан 0). Для этого выполняется контроль ассоциации при РгАП=111...10 и РгМ=000...01, ᴛ.ᴇ. n-й разряд РгАП устанавливается в 0, а n-й разряд РгМ – в 1. При этом свободная ячейка отмечается 1 в РгСв. Для записи выбирают свободную ячейку, к примеру, с наименьшим номером. В нее записывается слово, поступившее с ШИ вх в РгИ.
Следует отметить, что на данной схеме не изображены блоки БУП, БУС, БУЗ, которые есть в реальных устройствах. Вместе с тем, для построения ассоциативной памяти требуются запоминающие элементы, допускающие считывание без разрушения.
СТЕКОВАЯ ПАМЯТЬ (МАГАЗИННАЯ)
Стековая память, так же как и ассоциативная, является безадресной. Стековая память должна быть организована как аппаратно, так и на обычном массиве адресной памяти.
В случае аппаратной реализации ячейки стековой памяти образуют одномерный массив, в котором соседние ячейки связаны друг с другом разрядными цепями передачи слов (рис. 5.4). При этом возможны два типа устройств (а, б), принципы функционирования которых различны. Рассмотрим первоначально структуру на рис. 5.4, а.
Запись нового слова, поступившего с ШИ вх, производится в верхнюю (нулевую) ячейку, при этом все ранее записанные слова (включая слово в ячейке 0) сдвигаются вниз, в соседние ячейки, номера которых на единицу больше. Считывание возможно только из верхней (нулевой) ячейки памяти. Основной режим - ϶ᴛᴏ считывание с удалением. При этом все остальные слова в памяти сдвигаются вверх, в соседние ячейки с меньшими номерами. В такой памяти реализуется правило: последний пришел – первый ушел . Стеки подобного типа принято называть стеками LIFO (Last In – First Out).
В ряде случаев устройства стековой памяти предусматривают также операцию простого считывания слова из ячейки 0 без его удаления и сдвига остальных слов. При использовании стека для запоминания параметров инициализации контроллеров каких-либо устройств ЭВМ обычно предусматривается возможность считывания содержимого любой ячейки стека без его удаления, ᴛ.ᴇ. считывание содержимого не только ячейки 0.
О первом слове, посылаемом в стек, говорят, что оно располагается на дне стека . О последнем посланном (по времени) в стек слове говорят, что оно находится в вершине стека . Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, ячейка N-1 – дно стека, а ячейка 0 – вершина.
Обычно аппаратный стек снабжается счетчиком стека СчСт, показывающим общее количество занесенных в память слов (СчСт = 0 – стек пустой). При заполнении стека полностью он запрещает дальнейшие операции записи.
Стековый принцип организации памяти можно реализовать не только в специально предназначенных для этого устройствах. Стековая организация данных возможна и на обычной адресной памяти с произвольным обращением (программный стек). Для организации стека LIFO в данном случае необходима еще одна ячейка памяти (регистр), в которой всегда хранится адрес вершины стека и которая принято называть указателем стека . Обычно в качестве указателя стека используют один из внутренних регистров процессора. Кроме этого, требуется соответствующее программное обеспечение. Принципы стековой организации данных на обычной адресной памяти иллюстрируются схемой на рис. 5.5.
В отличие от аппаратного стека данные, размещенные в программном стеке, при записи нового числа или считывании не перемещаются. Запись каждого нового слова осуществляется в ячейку памяти, следующую по порядку за той, адрес которой содержится в указателе стека. После записи нового слова содержимое указателя стека увеличивается на единицу (см. рис. 6.5). Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, в программном стеке перемещаются не данные, а вершина стека. При считывании слова из стека происходит обратный процесс. Слово считывается из ячейки, адрес которой находится в указателе стека, после чего содержимое указателя стека уменьшается на единицу.
В случае если вновь загружаемые в стек слова размещаются в ячейках памяти с последовательно увеличивающимися адресами, стек называют прямым. В случае если адреса последовательно убывают, то – перевернутым. В большинстве случаев используется перевернутый стек, что связано с особенностями аппаратной реализации счетчиков внутри процессора.
Чем удобна такая форма организации памяти? Забегая вперед, можно отметить, что любая команда, выполняемая в процессоре, в общем случае должна содержать код операции (КОП), адрес первого и второго операндов и адрес занесения результата. Для экономии памяти и сокращения времени выполнения машинной команды процессором желательно уменьшить длину команды. Пределом такого уменьшения является длина безадресной команды, ᴛ.ᴇ. просто КОП. Именно такие команды оказываются возможными при стековой организации памяти, так как при правильном расположении операндов в стеке достаточно последовательно их извлекать и выполнять над ними соответствующие операции.
Помимо рассмотренной выше стековой памяти типа LIFO в ЭВМ используются стековые памяти другого типа, реализующие правило: первый пришел – первый ушел . Стеки подобного типа принято называть стеками FIFO (First In – First Out). Такая стековая память широко используется для организации различного рода очередей (команд, данных, запросов и т.д.). Обобщенная структура аппаратного стека типа FIFO представлена на рис. 5.4, б.
Как и в предыдущем случае, ячейки стековой памяти образуют одномерный массив, в котором соседние ячейки связаны друг с другом разрядными цепями передачи слов. Запись нового слова, поступившего с ШИ вх, осуществляется в верхнюю (нулевую) ячейку, после чего оно сразу перемещается вниз и записывается в последнюю по счету незаполненную ячейку. В случае если стек перед записью был пустой, слово сразу попадает в ячейку с номером N-1, ᴛ.ᴇ. на дно стека. Считывание возможно только из нижней ячейки с номером N-1 (дно стека). Основной режим - ϶ᴛᴏ считывание с удалением. При этом все последующие (записанные) слова сдвигаются вниз, в соседние ячейки, номера которых на единицу больше. При заполнении стека счетчик (СчСт) запрещает дальнейшие операции записи в стек.
Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, в отличие от стека LIFO, в стеке FIFO перемещается не дно, а вершина. Записываемые в стек FIFO слова постепенно продвигаются от вершины ко дну, откуда и считываются по мере крайне важно сти, причем темп записи и считывания определяются внешними управляющими сигналами и не связаны друг с другом.
Программная реализация стека FIFO в настоящем разделе не рассматривается, поскольку на практике используется достаточно редко.
Способы организации памяти - понятие и виды. Классификация и особенности категории "Способы организации памяти" 2017, 2018.
В ассоциативной памяти элементы выбираются не по адресу, а по содержимому. Поясним последнее понятие более подробно. Для памяти с адресной организацией было введено понятие минимальной адресуемой единицы (МАЕ) как порции данных, имеющей индивидуальный адрес. Введем аналогичное понятие для ассоциативной памяти , и будем эту минимальную единицу хранения в ассоциативной памяти называть строкой ассоциативной памяти (СтрАП). Каждая СтрАП содержит два поля: поле тега (англ. tag - ярлык, этикетка, признак) и поле данных. Запрос на чтение к ассоциативной памяти словами можно выразить следующим образом: выбрать строку (строки), у которой (у которых) тег равен заданному значению.
Особо отметим, что при таком запросе возможен один из трех результатов:
- имеется в точности одна строка с заданным тегом;
- имеется несколько строк с заданным тегом;
- нет ни одной строки с заданным тегом.
Поиск записи по признаку - это действие, типичное для обращений к базам данных, и поиск в базе зачастую чвляется ассоциативным поиском. Для выполнения такого поиска следует просмотреть все записи и сравнить заданный тег с тегом каждой записи. Это можно сделать и при использовании для хранения записей обычной адресуемой памяти (и понятно, что это потребует достаточно много времени - пропорционально количеству хранимых записей!). Об ассоциативной памяти говорят тогда, когда ассоциативная выборка данных из памяти поддержана аппаратно. При записи в ассоциативную память элемент данных помещается в СтрАП вместе с присущим этому элементу тегом. Для этого можно использовать любую свободную СтрАП. Рассмотрим разновидности структурной организации КЭШ-памяти или способы отображения оперативной памяти на КЭШ .
Полностью ассоциативный КЭШ
Схема полностью ассоциативного КЭШа представлена на рисунке (см. рисунок ниже).
Опишем алгоритм работы системы с КЭШ-памятью. В начале работы КЭШ-память пуста. При выполнении первой же команды во время выборки ее код, а также еще несколько соседних байтов программного кода, - будут перенесены (медленно) в одну из строк КЭШа, и одновременно старшая часть адреса будет записана в соответствующий тег. Так происходит заполнение КЭШ-строки.
Если следующие выборки возможны из этого участка, они будут сделаны уже из КЭШа (быстро) - "КЭШ-попадание". Если же окажется, что нужного элемента в КЭШе нет, - "КЭШ-промахом". В этом случае обращение происходит к ОЗУ (медленно), и при этом одновременно заполняется очередная КЭШ-строка.
Схема полностью ассоциативной КЭШ-памяти
Обращение к КЭШу происходит следующим образом. После формирования исполнительного адреса его старшие биты, образующие тег, аппаратно (быстро) и одновременно сравниваются с тегами всех КЭШ-строк. При этом возможны только две ситуации из трех, перечисленных ранее: либо все сравнения дадут отрицательный результат (КЭШ-промах), либо положительный результат сравнения будет зафиксирован в точности для одной строки (КЭШ-попадание).
При считывании, если зафиксировано КЭШ-попадание, младшие разряды адреса определяют позицию в КЭШ-строке, начиная с которой следует выбирать байты, а тип операции определяет количество байтов. Очевидно, что если длина элемента данных превышает один байт, то возможны ситуации, когда этот элемент (частями) расположен в двух (или более) разных КЭШ-строках, тогда время на выборку такого элемента увеличится. Противодействовать этому можно, выравнивая операнды и команды по границам КЭШ-строк, что и учитывают при разработке оптимизирующих трансляторов или при ручной оптимизации кода.
Если произошел КЭШ-промах, а в КЭШе нет свободных строк, необходимо заменить одну строку КЭШа на другую строку.
Основная цель стратегии замещения - удерживать в КЭШ-памяти строки, к которым наиболее вероятны обращения в ближайшем будущем, и заменять строки, доступ к которым произойдет в более отдаленном времени или вообще не случится. Очевидно, что оптимальным будет алгоритм, который замещает ту строку, обращение к которой в будущем произойдет позже, чем к любой другой строке-КЭШ.
К сожалению, такое предсказание практически нереализуемо, и приходится привлекать алгоритмы, уступающие оптимальному. Вне зависимости от используемого алгоритма замещения, для достижения высокой скорости он должен быть реализован аппаратными средствами.
Среди множества возможных алгоритмов замещения наиболее распространенными являются четыре, рассматриваемые в порядке уменьшения их относительной эффективности. Любой из них может быть применен в полностью ассоциативном КЭШ.
Наиболее эффективным является алгоритм замещения на основе наиболее давнего использования (LRU - Least Recently Used ), при котором замещается та строка КЭШ-памяти, к которой дольше всего не было обращения. Проводившиеся исследования показали, что алгоритм LRU, который "смотрит" назад, работает достаточно хорошо в сравнении с оптимальным алгоритмом, "смотрящим" вперед.
Наиболее известны два способа аппаратурной реализации этого алгоритма. В первом из них с каждой строкой КЭШ-памяти ассоциируют счетчик. К содержимому всех счетчиков через определенные интервалы времени добавляется единица. При обращении к строке ее счетчик обнуляется. Таким образом, наибольшее число будет в счетчике той строки, к которой дольше всего не было обращений и эта строка - первый кандидат на замещение.
Второй способ реализуется с помощью очереди, куда в порядке заполнения строк КЭШ-памяти заносятся ссылки на эти строки. При каждом обращении к строке ссылка на нее перемещается в конец очереди. В итоге первой в очереди каждый раз оказывается ссылка на строку, к которой дольше всего не было обращений. Именно эта строка прежде всего и заменяется.
Другой возможный алгоритм замещения - алгоритм, работающий по принципу "первый вошел, первый вышел" (FIFO - First In First Out ). Здесь заменяется строка, дольше всего находившаяся в КЭШ-памяти. Алгоритм легко реализуется с помощью рассмотренной ранее очереди, с той лишь разницей, что после обращения к строке положение соответствующей ссылки в очереди не меняется.
Еще один алгоритм - замена наименее часто использовавшейся строки (LFU - Least Frequently Used). Заменяется та строка в КЭШ-памяти, к которой было меньше всего обращений. Принцип можно воплотить на практике, связав каждую строку со счетчиком обращений, к содержимому которого после каждого обращения добавляется единица. Главным претендентом на замещение является строка, счетчик которой содержит наименьшее число.
Простейший алгоритм - произвольный выбор строки для замены. Замещаемая строка выбирается случайным образом. Реализовано это может быть, например, с помощью счетчика, содержимое которого увеличивается на единицу с каждым тактовым импульсом, вне зависимости от того, имело место попадание или промах. Значение в счетчике определяет заменяемую строку.
Кроме тега и байтов данных в КЭШ-строке могут содержаться дополнительные служебные поля, среди которых в первую очередь следует отметить бит достоверности V (от valid - действительный имеющий силу) и бит модификации M (от modify - изменять, модифицировать). При заполнении очередной КЭШ-строки V устанавливается в состояние "достоверно", а M - в состояние "не модифицировано". В случае, если в ходе выполнения программы содержимое данной строки было изменено, переключается бит M, сигнализируя о том, что при замене данной строки ее содержимое следует переписать в ОЗУ. Если по каким-либо причинам произошло изменение копии элемента данной строки, хранимого в другом месте (например в ОЗУ), переключается бит V. При обращении к такой строке будет зафиксирован КЭШ-промах (несмотря на то, что тег совпадает), и обращение произойдет к основному ОЗУ. Кроме того, служебное поле может содержать биты, поддерживающие алгоритм LRU.
Оценка объема оборудования
Типовой объем КЭШ-памяти в современной системе - 8…1024 кбайт, а длина КЭШ-строки 4…32 байт. Дальнейшая оценка делается для значений объема КЭШа 256 кбайт и длины строки 32 байт, что характерно для систем с процессорами Pentium и PentiumPro. Длина тега при этом равна 27 бит, а количество строк в КЭШе составит 256К/ 32=8192. Именно столько цифровых компараторов 27 битных кодов потребуется для реализации вышеописанной структуры.
Приблизительная оценка затрат оборудования для построения цифрового компаратора дает значение 10 транз/бит, а общее количество транзисторов только в блоке компараторов будет равно:
10*27*8192 = 2 211 840,
что приблизительно в полтора раза меньше общего количества транзисторов на кристалле Pentium. Таким образом, ясно, что описанная структура полностью ассоциативной КЭШ-памяти () реализуема только при малом количестве строк в КЭШе, т.е. при малом объеме КЭШа (практически не более 32…64 строк). КЭШ большего объема строят по другой структуре.
