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

В отличие от обычной машинной памяти, в которой пользователь задает адрес памяти и ОЗУ возвращает слово данных, хранящееся по этому адресу, АП разработана таким образом, чтобы пользователь задавал слово данных, и АП ищет его во всей памяти, чтобы выяснить, хранится ли оно где-нибудь в нем. Если слово данных найдено, АП возвращает список одного или более адресов хранения, где слово было найдено (и в некоторых архитектурах, также возвращает само слово данных, или другие связанные части данных). Таким образом, АП - аппаратная реализация того, что в терминах программирования назвали бы ассоциативным массивом.

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

1. 
   Гетероассоциативная память

1. 
   Охарактеризуйте две фазы в работе ассоциативной памяти

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

1. 
   Приведите определение процесса распознавания образов

1. 
   Охарактеризуйте два типа машин распознавания образов.

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

2ой тип машины.

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

1. 
   Опишите способ решения задачи идентификации систем.

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

1. 
   Опишите способ построения инверсной системы

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

1. 
   Приведите блок-схему системы управления с обратной связью

В этой системе используется единственная обратная связь, охватывающая весь объект управления. Таким образом, выход объекта управления вычитается из эталонного сигнала (), принимаемого из внешнего источника. Полученный таким образом сигнал ошибки (e) подаётся на нейроконтроллер для настройки свободных параметров. Основной задачей контроллера является поддержание такого входного вектора объекта, для которого выходной сигнал (у) соответствовал бы эталонному значению (d). Другими словами, в задачу контроллера входит инвертирование отображения вход-выход объекта управления.

1. 
   Опишите операции логической суммы и логического произведения над нечёткими множествами

Операция логической суммы:

Пусть
- наименьшее нечёткое подмножество, которое включает как так и с функцией принадлежности:

Операция логического произведения над нечёткими множествами:

Пусть
- наибольшее нечёткое подмножество, которое содержится одновременно в и в , тогда функция принадлежности имеет вид:

1. 
   Опишите операции отрицания множества и нормализации множества для нечётких множеств

Пусть - всё то множество, что не , тогда элемент, принадлежащий множеству , определяется согласно функции:

Нормализация нечётких множеств:

СУПРЕМУМ: Sup - точная верхняя грань (максимальное значение принадлежности, присутствующее в множестве).

НОРМАЛИЗАЦИЯ: нечеткое множество нормально если супремум множества равен единице. Для нормализации перечитывают принадлежности элементов:

M"a(x) = Ma(x)/(Sup Ma(x))

1. 
   Опишите операцию концентрации и растяжения для нечётких множеств

Операция размывания:

1. 
   Дайте определение лингвистической переменной

Математическое определение лингвистической переменной:
, где -имя переменной;
-множество имён лингвистических значений переменной , каждое из которых является нечёткой переменой на множестве
; - синтаксическое правило для образования имён значений ;
семантическое правило для ассоциирования каждой величины значения с её понятием.

1. 
   Опишите операцию алгебраического произведения для нечётких множеств

1. 
   Опишите меру Егера, характеризующую степень нечёткости множеств

,

количество элементов в ,
расстояние между множествами и в метрике (которое равно 1 или 2). Метрике Хэмминга соответствует значение

1. 
   Опишите метрику Евклида, характеризующую меру нечёткости множества

1. 
   Опишите энтропийную меру нечёткости множества Коско

1. 
   Опишите систему нечёткого вывода Мамдани-Заде

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

Для обеспечения взаимодействия этих двух видов вводится нечеткая система с так называемым фазификатором (преобразователем множеств входных данных в нечеткое множество) на входе и дефазификатором (преобразователем нечетких множеств в конкретное значение выходной переменной) на выходе.

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

В модели вывода Мамдани-Заде присутствуют следующие операторы:

Рис 1. Пример системы вывода Мамдани-Заде

На рис. 1 представлен способ агрегирования при двух входных переменных .

1. 
   Охарактеризуйте фаззификатор

1. 
   Охарактеризуйте понятие функции принадлежности

Коэффициент принадлежности - величина из диапазона , характеризующая степень принадлежности элемента нечеткому множеству.

Действительное число, принимающее значение в диапазоне (0,1), при этом 1 означает 100%-ю (безусловную) принадлежность a к множеству , а 0 - безусловное отсутствие в . Значения между 0 и 1 характеризуют нечётко включенные элементы.

Отображение множества элементов во множество значений образует функцию принадлежности .

Функция может быть определена явно в виде, например, алгебраического выражения или таблично (дискретно) в виде массива пар

1. 
   Опишите обобщённую гауссовскую функцию принадлежности

Также существует обобщённая гауссова функция:
параметр формы.

Рис 3. График обобщённой функции Гаусса для с=1,

Обобщённая функция Гаусса также может быть и в рациональной форме:
.

1. 
   Опишите понятие дефаззификации нечёткого множества

1. 
   Опишите дефаззификацию относительно среднего центра

1. 
   Опишите дефаззификацию относительно центра области

1. 
   Приведите блок-схему работы генетического алгоритма.

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

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

Целочисленное кодирование.

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

Вещественное кодирование.

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

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. Опишите функции машины (механизма) вывода

Главным в ЭС является механизм, осуществляющий поиск в БЗ по правилам рациональной логики, для получения решений. Этот механизм, называемый машиной вывода, приводится в действие при получении запроса пользователя и выполняет следующие задачи:

• 
  сравнивает информацию, содержащуюся в запросе пользователя, с информацией базы знаний;

• 
  ищет определенные цели или причинные связи;

• 
  оценивает относительную определенность фактов, основываясь на соответствующих коэффициентах доверия, связанных с каждым фактом.

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

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

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

Этап формализации определяет способы представления всех видов знаний, формализует основные понятия, определяет способы интерпретации знаний, моделирует работу системы. На этом этапе оценивается адекватность целям системы зафиксированных понятий, методов решения, средств представления и манипулирования знаниями.

На этапе выполнения осуществляется наполнение БЗ системы. На этапе тестирования эксперт (и инженер по знаниям) в интерактивном режиме, используя диалоговые и объяснительные средства, проверяет компетентность ЭС. Процесс тестирования продолжается до тех пор, пока эксперт не решит, что система достигла требуемого уровня компетентности.

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

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

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

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

Естественное решение проблемы ускорения - снабдить компьютер аппаратным устройством для отображения виртуальных страниц в физические без обращения к таблице страниц, то есть иметь небольшую, быструю кэш-память, хранящую необходимую на данный момент часть таблицы страниц. Это устройство называется ассоциативной памятью, иногда также употребляют термин буфер поиска трансляции (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 не.

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

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

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

Запоминающее устройство, как правило, содержит множе­ство одинаковых запоминающих элементов, образующих запоминающий массив (ЗМ). Массив разделен на отдельные ячейки; каждая из них предназначена для хранения двоичного кода, число разрядов в котором определяется шириной выбор­ки памяти (в частности, это может быть одно, половина или несколько машинных слов). Способ организации памяти зави­сит от методов размещения и поиска информации в запоми­нающем массиве. По этому признаку различают адресную, ас­социативную и стековую (магазинную) памяти.

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

При записи (или считывании) слова в ЗМ инициирующая эту операцию команда должна указывать адрес (номер ячейки), по которому производится запись (считывание).

Типичная структура адресной памяти, показанная на рис. 4.2, содержит запоминающий массив из N n-разрядных ячеек и его аппаратурное обрамление, включающее регистр адреса РгА, имеющий k {k > log 2 N) разрядов, информационный регистр РгИ, блок адресной выборки БАВ, блок усилителей считывания БУС, блок разрядных усилителей-формирователей сигналов за­писи БУЗ и блок управления памятью БУП.

Рис.4.2.Структура адресной памяти.

По коду адреса в РгА БАВ формирует в соответствующей ячейке памяти сигналы, позволяющие произвести в ячейке считывание или запись слова.

Цикл обращения к памяти инициируется поступлением в БУП извне сигнала Обращение. Общая часть цикла обраще­ния включает в себя прием в РгА с шины адреса ША адреса обращения и прием в БУП и расшифровку управляющего сиг­нала Операция, указывающего вид запрашиваемой операции (считывание или запись).

Далее при считывании БАВ дешифрирует адрес, посылает сигналы считывания в заданную адресом ячейку ЗМ, при этом код записанного в ячейке слова считывается усилителями считывания БУС и передается в РгИ. Затем в памяти с разру­шающим считыванием (при считывании все запоминающие элементы ячейки устанавливаются в нулевое состояние). про­изводится регенерация информации в ячейке путем записи в нее из РгИ считанного слова. Операция считывания завер­шается выдачей слова из РгИ на выходную информационную шину ШИВых.

При записи помимо выполнения указанной выше общей ча­сти цикла обращения производится прием записываемого сло­ва с входной информационной шины ШИВх в РгИ. Сама за­пись состоит из двух операций: очистки ячейки (сброса в 0) и собственно записи. Для этого БАВ сначала производит вы­борку и очистку ячейки, заданной адресом в РгА. Очистка вы­полняется сигналами считывания слова в ячейке, но при этом блокируются усилители считывания и из БУС в РгИ информа­ция не поступает. Затем в выбранную БАВ ячейку записывается слово из РгИ.

Блок управления БУП генерирует необходимые последова­тельности управляющих сигналов, инициирующих работу от­дельных узлов памяти. Цепи передачи управляющих сигналов показаны тонкими линиями на рис. 4.2.

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

Типичная структура ассоциативной памяти представлена на рис. 4.3. Запоминающий массив содержит N (п + 1) -разрядных ячеек. Для указания занятости ячейки используется служебный n-й разряд (0 - ячейка свободна, 1 - в ячейке записано слово).

По входной информационной шине ШИВх в регистр ассо­циативного признака РгАП в разряды 0-и-1 поступает п- разрядный ассоциативный запрос, а в регистр маски РгМ - код маски поиска, при этом п-й разряд РгМ устанавли­вается в 0. Ассоциативный поиск производится лишь для сово­купности разрядов РгАП, которым "соответствуют 1 в РгМ (незамаскированные разряды РгАП). Для слов, в которых цифры в разрядах совпали с незамаскированными разрядами РгАП, комбинационная схема КС устанавливает 1 в соответ­ствующие разряды регистра совпадения РгСв и 0 в остальные разряды. Таким образом, значение j-ro разряда в РгСв опреде­ляется выражением

РгСв (j) =

где РгАП [i], РгМ [i] и ЗМ - значения i-го разряда со­ответственно РгАП, РгМ и j-й ячейки ЗМ.

Комбинационная схема формирования результата ассоциа­тивного обращения ФС формирует из слова, образовавшегося в РгСв, сигналы  0 ,  1 ,  2 , соответствующие случаям отсутствия слов в ЗМ, удовлетворяющих ассоциативному признаку, нали­чию одного и более чем одного такого слова. Для этого ФС реализует следующие булевы функции:

 0 =

 1 = РгСв

 2 =  0  1

Формирование содержимого РгСв и сигналов  0 ,  1 ,  2 по содержимому РгАП, РгМ и ЗМ называется операцией контроля ассоциации. Эта операция является составной частью операций считывания и записи, хотя она имеет и самостоятельное значение.

При считывании сначала производится контроль ассоциа­ции по ассоциативному признаку в РгАП. Затем при  0 = 1 считывание отменяется из-за отсутствия искомой информации, при  1 = 1 считывается в РгИ найденное слово, при  2 = 1 в РгИ считывается слово из ячейки, имеющей наименьший номер среди ячеек, отмеченных 1 в РгСв. Из РгИ счи­танное слово выдается на ШИВых.

Рис. 4.3. Структура ассоциа­тивной памяти

При записи сначала оты­скивается свободная ячейка. Для этого выполняется опе­рация контроля ассоциации при РгАП= 111. ..10 и РгМ == 00... 01. При этом свободные ячейки отмечают­ся 1 в РгСв. Для записи вы­бирается свободная ячейка с наименьшим номером. В нее записывается слово, посту­пившее с ШИВх в РгИ.

Рис. 4.4. Стековая память

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

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

Стековая память, так же как и ассоциативная, является без­адресной. В стековой памяти (рис. 4.4) ячейки образуют одно­мерный массив, в котором соседние ячейки связаны друг с дру­гом разрядными цепями передачи слов. Запись нового слова производится в верхнюю ячейку (ячейку 0), при этом все ранее записанные слова (включая слово, находившееся в ячейке 0), сдвигаются вниз, в соседние ячейки с большими на 1 номера­ми. Считывание возможно только из верхней (нулевой) ячейки памяти, при этом, если производится считывание с удалением, все остальные слова в памяти сдвигаются вверх, в соседние ячейки с большими номерами. В этой памяти порядок считыва­ния слов соответствует правилу: последним поступил - первым обслуживается. В ряде устройств рассматриваемого типа пре­дусматривается также операция простого считывания слова из нулевой ячейки (без его удаления и сдвига слова в памяти). Иногда стековая память снабжается счетчиком стека СчСт, по­казывающим количество занесенных в память слов. Сигнал СчСт = 0 соответствует пустому, стеку, СчСт = N - 1 - заполненному стеку.

Часто стековую память организуют, используя адресную память. Широкое применение стековая память нахо­дит при обработке вложенных структур данных.

В последующих параграфах главы описываются различные типы ЗУ с адресной организацией. Ассоциативная память ис­пользуется в аппаратуре динамическо­го распределения ОП, а также для построения КЭШ-памяти.

Памятьс ассоциативным доступом или ассоциативная память отличается от остальных типов памяти тем, что обращение к ее ячейкам осуществляется не по определенному адресу, а по содержимому ячеек памяти. Фактически ассоциативная память работает как поисковая система, способная найти информацию по заданному образцу. Основу ассоциативной памяти составляют ассоциативные запоминающие устройства (АЗУ) , которые, как и большинство оперативных ЗУ, являются энергозависимыми и реализуются в виде полупроводниковых микросхем (наборов микросхем).

Принцип работы АЗУ поясняет схема, представленная на рис. 3.8.Запоминающий массив, как и в адресных ЗУ, разделен на m -разрядные ячейки, число которых n . Как правило, в состав АЗУ входят:

· запоминающий массив (ЗМ);

· регистр ассоциативных признаков (РгАП);

· регистр маски (РгМ);

· регистр индикаторов адреса со схемами сравнения на входе.

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

Рис. 3.8. Ассоциативное запоминающее устройство

Выборка информации из АЗУ происходит следующим образом. В регистр ассоциативных признаков из устройства управления передается образец для поиска - код признака искомой информации (иногда его называют компарандом ). Код может иметь произвольное число разрядов – от 1 до m . Если код признаков используется полностью, то он без изменения поступает на схему сравнения, если же необходимо использовать только часть кода, тогда ненужные разряды маскируются с помощью регистра маски. Перед началом поиска информации в АЗУ все разряды регистра индикаторов адреса устанавливаются в состояние 1 .После этого производится опрос первого разряда всех ячеек запоминающего массива, и содержимое сравнивается с первым разрядом регистра ассоциативных признаков. Если содержимое первого разряда i -й ячейки не совпадает с содержимым первого разряда РгАП, то соответствующий этой ячейке разряд регистра индикаторов адреса Т i сбрасывается в состояние 0 , если совпадает – разряд Т i остается 1 . Затем эта операция повторяется со вторым, третьим и последующими разрядами до тех пор, пока не будет произведено сравнение со всеми разрядами РгАП. После поразрядного опроса и сравнения в состоянии 1 останутся те разряды регистра индикаторов адреса, которые соответствуют ячейкам, содержащим информацию, совпадающую с записанной в регистре ассоциативных признаков. Эта информация может быть считана в той последовательности, которая определяется устройством управления.

Заметим, что время поиска информации в ЗМ по ассоциативному признаку зависит только от числа разрядов признака и от скорости опроса разрядов, но совершенно не зависит от числа ячеек ЗМ. Этим и определяется главное преимущество АЗУ перед адресными ЗУ: в адресных ЗУ при операции поиска необходим перебор всех ячеек запоминающего массива. Кроме того, существуют реализации АЗУ, выполняющих поиск одновременно над всеми разрядами всех слов, записанных в память, т.е. время поиска в подобных устройствах не превышает времени цикла памяти.

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

Нередко АЗУ строятся таким образом, что кроме ассоциативной допускается и прямая адресация данных, что представляет определенные удобства при работе.

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

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

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

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

Кэш-память

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

Новый вид памяти получил название кэш-память (от англ. cache – «тайник, убежище»), поскольку такая память скрыта, «невидима» для ЦП, который не может непосредственно обратиться к ней. В свою очередь, программист может вообще не знать о существовании кэш-памяти. В серийных ЭВМ кэш-память впервые была применена в системах модели 85 семейства IBMS/360. Сегодня кэш-память наличествует в любом классе ЭВМ, причем зачастую имеет многоуровневую структуру.

Все термины, которые были определены раньше, могут быть использованы и для кэш-памяти, хотя слово «строка » (line ) часто употребляется вместо слова «блок » (block ).

Как правило, кэш-память строится на основе сверхбыстродействующих и дорогостоящих ОЗУ статического типа, при этом ее быстродействие в 5-10 раз превышает быстродействие ОП, а объем – в 500-1000 раз меньше. Заметим, что увеличению объема кэш-памяти по отношению к емкости ОП препятствует не только и не столько высокая стоимость статических ОЗУ. Дело в том, что при увеличении емкости кэш-памяти возрастает сложность схем управления, что, в свою очередь, ведет к падению быстродействия. Многочисленные исследования показали, что указанное соотношение объемов кэш-памяти и ОП является оптимальным и будет сохраняться в процессе развития ЭВМ при увеличении быстродействия обоих видов памяти.

Как уже было сказано, ЦП не имеет непосредственного доступа к кэш-памяти. За организацию взаимодействия ЦП, ОП и кэш-памяти отвечает специальный контроллер. Вся ОП разбивается на блоки фиксированного объема, при этом старшая часть адреса ОП определяет адрес блока , а младшая часть – адрес слова внутри блока . Обмен информации между ОП и кэш-памятью осуществляется блоками. Кэш-память также имеет свою внутреннюю адресацию, и каждый считанный из ОП блок размещается в кэш-памяти по определенному адресу блока в кэш-памяти . Часто блоки кэш-памяти называются строками или кэш-строками .

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

Не менее важным является вопрос о том, в какой момент нужно помещать в кэш-память копию блока из ОП. Данный вопрос решается с помощью стратегии выборки .

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

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

Стратегии размещения

Существуетследующие способы размещения данных в кэш-памяти:

· прямое распределение;

· полностью ассоциативное распределение;

· частично (множественно) ассоциативное распределение.

Допустим, разрядность шины адреса n , тогда емкость ОП V ОП = 2 n слов. Без ограничения общности определим размер кэш-строки в 256 слов, таким образом, вся ОП будет поделена на 2 n-8 блоков. В адресе ОП старшие n-8 битов будут определять адрес блока, а младший байт – адрес слова в блоке. Пусть емкость кэш-памяти V кэш в 1024 раза меньше емкости ОП, т.е. V кэш = 2 n-10 слов или 2 n-18 блоков (кэш-строк).

Прямое распределение

Если каждый блок основной памяти имеет только одно фиксированное место, на котором он может появиться в кэш-памяти, то такая кэш-память называется кэшем с прямым распределением (direct mapped cache). Это наиболее простая организация кэш-памяти, при которой для отображения адресов блоков ОП на адреса кэш-памяти просто используются младшие разряды адреса блока. Таким образом, все блоки ОП, имеющие одинаковые младшие разряды в своем адресе, попадают в одну кэш-строку, т.е.

(адрес кэш-строки) = (адрес блока ОП) mod (число блоков в кэш-памяти)

В нашем примере адрес кэш-строки c будут составлять младшие n-18 бит адреса блока ОП (см. рис. 3.9). Преобразование адреса блока ОП в адрес кэш-строки осуществляется путем выборки этих младших n-18 бит. По этому адресу кэш-строки может быть помещен любой из 1024 блоков ОП, имеющих одинаковые n-18 младших бит. Между собой эти блоки будут различаться старшими 10-ю битами t , называемыми тегом . Для того, чтобы определить, какой именно блок ОП хранится в данное время в кэш-памяти, используется еще одна память – так называемая память тегов(теговая память) . Теговая память адресуется пословно, причем каждое слово имеет размер, равный размеру тега. Емкость памяти тегов – это произведение размера тега на общее число кэш-строк, для нашего примера составляет 10·2 n-18 бит. Адресом памяти тегов является адрес кэш-строки с . В отличие от памяти тегов, память, в которой хранятся блоки, помещенные в кэш, называется памятью данных . Память данных адресуется пословно, ее адрес образуется из адреса кэш-строки и адреса слова внутри блока (кэш-строки).

Рис. 3.9. Структура адреса памяти при прямом распределении

Рис. 3.10. Организация кэш-памяти с прямым распределением

При доступе к A -му адресу ОП (рис. 3.10) младшие n-18 бит адреса блока (поле c ), где содержится этот адрес, используются в качестве адреса кэш-строки. По адресу кэш-строки из теговой памяти считывается тег (поле t ). Параллельно этому осуществляется доступ к памяти данных с помощью n-10 младших бит адреса A (поля c и w ). Если считанный тег и старшие 10 бит адреса A совпадают, то это означает, что блок, содержащий адрес A , существует в памяти данных, и в слове, к которому осуществляется доступ, хранится копия A -го адреса ОП.

Если тег отличается от старших 10 бит адреса A , то из основной памяти считывается блок, содержащий адрес A , а из кэш-памяти удаляется кэш-строка, чей адрес определяется полем c (младшими n-18 битами) адреса считываемого блока. На место удаленной кэш-строки помещается считанный из ОП блок, при этом обновляется соответствующий тег в памяти тегов.

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

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

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

При записи (или считывании) слова в ЗМ инициирующая эту операцию команда должна указывать адрес (номер ячейки), по которому производится запись (считывание).

Типичная структура адресной памяти, содержит запоминающий массив из N-разрядных ячеек и его аппаратное обрамление, включающее в себя регистр адреса РгА , имеющий k (k » log N) разрядов, информационный регистр РгИ , блок адресной выборки БАВ , блок усилителей считывания БУС , блок разрядных усилителей-формирователей сигналов записи БУЗ и блок управления памятью БУП .

По коду адреса в РгА БАВ формирует в соответствующей ячейке памяти сигналы, позволяющие произвести в ячейке считывание или запись слова.

Цикл обращения к памяти инициируется поступлением в БУП извне сигнала Обращение . Общая часть цикла обращения включает в себя прием в РгА с шины адреса ША адреса обращения и прием в БУП и расшифровку управляющего сигнала Операция , указывающего вид запрашиваемой операции (считывание или запись).

Далее при считывании БАВ дешифрирует адрес, посылает сигналы считывания в заданную адресом ячейку ЗМ, при этом код записанного в ячейке слова считывается усилителями считывания БУС и передается в РгИ . Операция считывания завершается выдачей слова из РгИ на выходную информационную шину ШИВых .

При записи помимо выполнения указанной выше общей части цикла обращения производится прием записываемого слова с входной информационной шины ШИВх и РгИ . Затем в выбранную БАВ ячейку записывается слово из РгИ .

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

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

Типичная структура ассоциативной памяти представлена на рис. 4.3. Запоминающий массив содержит N (n+1)-разрядных ячеек. Для указания занятости ячейки используется служебный n-й разряд (0 - ячейка свободна, 1 - в ячейке записано слово).