Адресная, ассоциативная и стековая организации памяти. Ассоциативная память

Общие сведения и классификация устройств памяти

Лекция 2. Организация памяти ЭВМ.

МинисуперЭВМ и суперминиЭВМ.

Малые и микроЭВМ.

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

В настоящее время малые и микроЭВМ встраивают в различные «умные» приборы (электросчетчики, микроволновки, стиральные машины, модемы, датчики и т.д.).

В классификации отсутствуют четкие границы между рассмотренными типами ЭВМ. В последнее время стали выделять два промежуточных типа.

К суперминиЭВМ относят высокопроизводительные ЭВМ содержащих один или несколько слабосвязанных процессоров, объединенных с общей магистралью (общей шиной). Для суперминиЭВМ характерно, что скорость выполнения его арифметических операций над числами с плавающей точкой существенно ниже скорости работы, определяемой по смеси команд, соответствующей информационно-логическим запросам. К этому типу можно отнести IBM-овский шахматный компьютер Deep Blue.

МинисуперЭВМ – это упрощенные (в частности за счет более короткого слова) многопроцессорные ЭВМ, чаще всего со средствами векторной и конвейерной обработки, с высокой скоростью выполнения операций над числами с плавающей точкой. К этому типу можно отнести ЭВМ с SMP(Symmetric multiprocessor) архитектурой.

Запоминающие устройства можно классифицировать по следующим критериям: · по типу запоминающих элементов · по функциональному назначению · по типу способу организации обращения · по характеру считывания · по способу хранения · по способу организации По типу запоминающих элементов Полупроводниковые Магнитные Конденсаторные Оптоэлектронные Голографические Криогенные По функциональному назначению ОЗУ СОЗУ ВЗУ ПЗУ ППЗУ По способу организации обращения С последовательным поиском С прямым доступом С непосредственным доступом или Адресные Ассоциативные Стековые Магазинные По характеру считывания С разрушением информации Без разрушения информации По способу хранения Статические Динамические По способу организации Однокоординатные Двухкоординатные Трехкоординатные Двух- трехкоординатные

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



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

Основными операциями в памяти являются занесение информации в память - запись и выборка информации из памяти - считывание . Обе эти операции называются обращением к памяти .

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

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

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

Удельная емкость есть отношение емкости ЗУ к его физическому объему.

Плотность записи есть отношение емкости ЗУ к площади носителя. Например, у HDD емкостью до 10 Гб плотность записи составляет 2 Гбит на кв. дюйм.

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

Продолжительность обращения к памяти (время цикла памяти) при считывании

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

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

Продолжительность обращения (время цикла) при записи

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

В качестве продолжительности цикла обращения к памяти принимается величина

В зависимости от реализуемых в памяти операций обращения различают: а) память с произвольным обращением (возможны считывание и запись данных в память); б) память только для считывания информации («постоянная» или «односторонняя»). Запись информации в постоянную память производится в процессе ее изготовления или настройки.

Эти типы памяти соответствуют терминам RAM (random access memory - память с произвольным обращением) и ROM (read only memory - память только для считывания).

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

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

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

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

Хорошим примером ленточного накопителя является применение адаптера АРВИД с VHS видеомагнитофоном. Емкость этого накопителя составляет 4ГБ/180мин.

Запоминающие устройства различаются также по выполняемым в ЭВМ функциям, зависящим в частности, от места расположения ЗУ в структуре ЭВМ.

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

Иерархическая структура памяти позволяет экономически эффективно сочетать хранение больших объемов информации с быстрым доступом к информации в процессе обработки.

Таблица 2.1.

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

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

Характеристики ОП непосредственно влияют на основные показатели ЭВМ и в первую очередь на скорость ее работы. На текущий момент оперативная память имеет емкость от нескольких МБ до нескольких ГБ и цикл обращения около 60 нс и менее. Запоминающие устройства ОП изготовляются на интегральных микросхемах с большой степенью интеграции (полупроводниковые ЗУ).

В последнее время ряд фирм заявили о начале серийного выпуска чипов динамической памяти емкостью 1Гб. Признанным лидером является Samsung. Самым массовым изделием на сегодняшний день можно считать 64 Мб чипы. В ближайший год предполагается широкое применение 128Мб и 256Мб чипов.

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

В качестве ОП и СОП используются быстродействующие ЗУ с произвольным обращением и непосредственным доступом.

Обычно емкость ОП оказывается недостаточной для хранения всех необходимых данных в ЭВМ. Поэтому ЭВМ содержит в своем составе несколько ЗУ с прямым доступом на дисках (емкость одного ЗУ на HDD дисках 1 - 30 Гбайт) и несколько ЗУ с последовательным доступом на магнитных лентах (емкость одного ЗУ 4 – 35 Гбайт).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

РгСв(j) =

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

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

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

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

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

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

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

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

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

Архитектурная организация процессора ЭВМ

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

Язык микропрограммирования предназначен для описания цифровых устройств, функционирующих на уровне регистров. Он имеет простые и наглядные средства описания машинных слов, регистров, шин и других базовых элементов ЭВМ. С учетом сказанного, ие­рархию языков описания вычислительного процесса на ЭВМ можно представить, в общем случае, на четырех уровнях: (1) булева операция (функционирование комбинационных ЛС) => (2) микрокоманда (функционирование узлов ЭВМ) => (3) команда (функционирование ЭВМ) => (4) оператор ЯВУ (описание алгоритма решаемой задачи). Для определения вре­менных соотношений между микрокомандами устанавливается единица времени (такт), в течение которой выполняется самая продолжительная микрокоманда. Поэтому выполнение одной команды ЭВМ синхроимпульсами, генерируемыми специальным устройством процес­сора - тактовым генератором, тактовая частота (измеряемая в МГц) в значительной степени определяет быстродействие ЭВМ. Естественно, для других классов ЭВМ дан­ный показатель иным образом связывается с производительностью, определяемой такими дополнительными факторами, как.

Ширина доступа в память,

Время выборки,

Разрядность,

Архитектура процессора и его сопроцессоров,

Укрупненная схема центрального процессора (ЦП) некоторой формальной ЭВМ представлена на рисунке, где изображены только основные его блоки управляющие регист­ры (УР), устройство управления (УУ), ПЗУ, арифметико-логическое устройство (АЛУ), ре­гистровая память (РП), кэш-память и интерфейсный блок (ИБ). Наряду с перечисленными ЦП содержит ряд других блоков (прерывания, защиты ОП, контроля и диагностики и др.), структура и назначение которых здесь не рассматриваются. Блок УУ вырабатывает последо­вательность управляющих сигналов, инициирующих выполнение соответствующей последо­вательности микрокоманд (находящихся в ПЗУ), реализующей текущую команду. Наряду с этим УУ координирует функционирование всех устройств ЭВМ посредством посылки управляющих сигналов обмен данными ЦП <-> ОП, хранение и обработка информации, ин­терфейс с пользователем, тестирование и диагностика и др. Поэтому УУ целесообразно рас­сматривать как отдельный блок ЦП; однако на практике большинство управляющих схем распределены по всей ЭВМ. Они связаны большим числом управляющих линий, передаю­щих сигналы для синхронизации операции во всех устройствах ЭВМ и принимающих сигна­лы об их состоянии. Блок УР предназначен для временного хранения управляющей информации и содержит регистры и счетчики, участвующие совместно с УУ в управлении вычислительным процессом регистр состояния ЦП, программы (ССП), счетчик команд (СК) представляет со­бой регистр, хранящий в ОП адрес выполняемой команды (в период выполнения текущей команды его содержимое обновляется на адрес следующей команды), регистр команд (РК) содержит выполняемую команду (его выходы связаны с управляющими схемами, генери­рующими распределенные во времени сигналы, необходимые для выполнения команд)

Блок РП содержит регистры сверхоперативной памяти (более высокого быстродейст­вия, чем ОП) небольшого объема, позволяющие повысить быстродействие и логические воз­можности ЦП. Эти регистры используются в командах путем сокращенной регистровой ад­ресации (указываются только номера регистров) и служат для хранения операндов, результа­тов операций, в качестве базовых и индексных регистров, указателей стэка и др. В некото­рых ЦП базовые и индексные регистры входят в состав блока УТ, как правило, РП выполня­ется в виде быстродействующих полупроводниковых интегральных запоминающих уст­ройств

Блок АЛУ служит для выполнения арифметических и логических операций над дан­ными, поступающими из ОП и хранящимися в РП, и работает под управлением УУ. АЛУ выполняет арифметические операции над бинарными числами с фиксированной и плаваю­щей точками, над десятичными числами, производит обработку символьной информации над словами фиксированной и переменной длины. Логические операции производятся над отдельными битами, группами битов, байтами и их последовательностями. Тип выпол­няемой АЛУ операции определяется текущей командой функционирующей в данный момент программы, точнее, АЛУ служит для выполнения любой операции, задаваемой ему УУ. В общем случае обрабатываемая ЭВМ информация состоит из слов, содержащих фиксирован­ное число n битов (например n =8. 16. 32, 64, 128 бит). В этом случае АЛУ должно иметь возможность производить операции над n-битными словами операнды поступают из ОП на регистры АЛУ, а УУ указывает операцию, которую необходимо над ними произвести, ре­зультат каждой арифметико-логической операции сохраняется в специальном регистре-сумматоре, являющимся основным регистром для арифметико-логических операций.

Сумматор соединен с вентильными схемами для выполнения необходимых операций над его содержимым и содержимым других регистров. Некоторые ЭВМ имеют несколько сумматоров, при количестве, большем 4, они выделяются в специальную группу регистров общего назначения (РОН). Конструктивно АЛУ выполняется на одном или нескольких БИС/СБИС, при этом ЦП может иметь одно АЛУ универсального назначения или несколько специализированных для отдельных видов операции. В по­следнем случае увеличивается структурная сложность ЦП, но повышается его быстродейст­вие за счет специализации и упрощения схем вычисления отдельных операций. Такой под­ход широко используется в современных ЭВМ общего назначения и супер-ЭВМ для повы­шения их производительности Несмотря на различные классы ЭВМ, их АЛУ используют общие принципы выполнения арифметико-логических операции. Различия касаются схемо­технических решений организации АЛУ и принципов реализации операции, обеспечиваю­щих ускорение их выполнения.

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

С учетом сказанного представим общую схему выполнения программ процессором. Выполнение программы, находящейся в ОП, начинается с того, что в СК засылается адрес первой ее команды, содержимое СК пересылается в РАП и в ОП посылается сигнал управле­ния считыванием. Через некоторое время (соответствующее времени доступа к ОП) адре­суемое слово (в данном случае первая команда программы) извлекается из ОП и загружается в РДП, затем содержимое РДП пересылается в СК. На этой стадии команда готова для деко­дирования ее УУ и выполнения. Если команда содержит операцию, которая должна быть выполнена АЛУ, то необходимо получить требуемые операнды. Если операнд находится в ОП (а он может быть также в УР), его необходимо выбрать из памяти. Для этого в РАП пере­сылается адрес операнда и начинается цикл чтения Операнд, выбранный из памяти в РДП, может быть передан в АЛУ. Выбрав таким образом один или несколько операндов, АЛУ может выполнить требуемую операцию, сохранив ее результат в одном из РОН. Если резуль­тат операции необходимо запомнить в ОП, он должен быть послан в РДП Адрес ячейки, в которую необходимо поместить результат, пересылается в РАП и начинается цикл записи. Между тем содержимое СК увеличивается, указывая следующую команду, которая должна выполняться. Таким образом, как только завершится выполнение текущей команды, может сразу же начаться выборка на выполнение следующей команды программы.

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


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

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


  1. Автоассоциативная память
Автоассоциативная память – память, которая может завершить или исправить образ, но не может ассоциировать полученный образ с другим образом. При решении задачи автоассоциативной памяти в нейронной сети запоминаются передаваемые ей образы (векторы). Затем в эту сеть последовательно подаются неполные описания или зашумленные представления хранимых в памяти исходных образов, и ставится задача распознавания конкpeтнoгo образа. Для настройки нейронных сетей, предназначенных для решения задач автоассоциативной памяти, используется обучение без учителя.

  1. Гетероассоциативная память
Гетероассоциативная память – память, в которой произвольному набору входных образов (стимулов) ставится в соответствие другой набор выходных производных сигналов (откликов). При этом размерность пространства выходных сигналов может, как отличаться от размерности пространства входных, так и совпадать. Для настройки нейронных сетей, предназначенных для решения задач гетероассоциативной памяти, используется модель обучения с учителем.

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

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


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

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

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

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

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


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

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


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

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


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

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


  1. Опишите операции логической суммы и логического произведения над нечёткими множествами
Нечёткое множество – обобщение обычных (чётких) множеств. Традиционный способ представления элемента множества A состоит в применении характеристической функции
, которая равна 1, если элемент принадлежит множеству A, или равна 0 в противном случае. В нечётких системах элемент может частично принадлежать любому множеству. Степень принадлежности множеству A, представляющая собой обобщение характеристической функции, называется функцией принадлежности , причём
, и
означает отсутствие принадлежности x множеству A, а
- полную принадлежность. Конкретное значение функции принадлежности называется степенью или коэффициентом принадлежности.

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

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

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

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


  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. Приведите блок-схему работы генетического алгоритма.
Генетический алгоритм (англ. genetic algorithm) - это эвристический метод, используемый для решения задач оптимизации и моделирования через последовательный подбор и комбинирование искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Блок-схема работы генетического алгоритма:


  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. Какие вы знаете модели представления знаний?

Наиболее распространенными моделями представления знаний в экспертных системах являются:


  • модель представления знаний средствами логики предикатов первого порядка;

  • продукционная модель;

  • фреймовая модель;

  • модель представления знаний в виде семантической сети;

  • модель представления знаний в виде доски объявлений;

  • модель представления знаний в виде сценария;

  • модель представления знаний на основе нечеткой логики;

  • нейросетевая модель представления знаний.
33. Что представляет собой логическая модель знаний?

Логическая модель представления знаний основана на логике предикатов. Предикатом, или логической функцией, называется функция от любого числа аргументов, принимающей истинное или ложное значение. Аргументы функции – значения из произвольного, конечного или бесконечного множества
, называемого предметной областью. Предикат от -аргументов называют -местным предикатом. Для модели представления знаний используется логика предикатов первого порядка, на которой основан Пролог.
34. Из чего состоит продукционная система?

Продукционная система – система обработки знаний, использующая представления знаний продукционными правилами. Продукционные правила – это выражения типа «Если (условие) то (действие)». “Условие” – предложение образец, по которому осуществляется поиск в базе знаний; “действие” – действие, выполняемое при успешном исходе поиска. Вывод на такой базе знаний может быть прямым (от данных к поиску цели) и обратным (от цели для её подтверждения – к данным). Данные – исходные факты, хранящиеся в базе фактов, на основании которых запускается машина вывода или интерпретатор правил, перебирающий правила из продукционной базы знаний.

В состав продукционной системы входят база правил, база данных и интерпретатор правил. База правил – это область памяти, которая содержит базу знаний – совокупность знаний, представленных в форме правил вида ЕСЛИ … ТО; база данных – это область памяти, содержащая фактические данные (факты). Интерпретатор – механизм вывода, это тот компонент системы, который формирует заключение, используя базу правил и базу данных.
35. Охарактеризуйте модель представления знаний в виде фреймов

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


36. Каким образом осуществляется представление знаний в семантической сети?

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

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

Информация, содержащаяся в базе знаний, обрабатывается с помощью машины вывода, которая использует эмпирические ассоциации или правила «ЕСЛИ … ТО» для формирования и проверки возможных решений. Интерфейс пользователя в доступной форме передает полученные результаты оператору.

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

38. Опишите функции машины (механизма) вывода

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


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

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

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

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

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

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

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

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

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

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


страница 1

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

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

Аппаратный ассоциативный массив

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

Промышленные стандарты адресуемой содержанием памяти

Определение основного интерфейса для АП и других Сетевых Элементов Поиска (Network Search Elements, NSE) было специфицировано в Соглашении о возможности взаимодействий (Interoperability Agreement), названном Интерфейс предысторий(Look-Aside Interface) (LA-1 и LA-1B ) который был разработан Форумом Сетевой Обработки, который позже был объединен с Оптическим Межсетевым Форумом (Optical Internetworking Forum, OIF). Многочисленные устройства были произведены компаниями Integrated Device Technology, Cypress Semiconductor, IBM, Netlogic Micro Systems и другими по этим соглашениям LA. 11 декабря 2007, OIF издал соглашение об интерфейсе последовательной предыстории (Serial Lookaside, SLA ).

Реализация на полупроводниках

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

Альтернативные реализации

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

Троичная Ассоциативная память

Двоичная АП - простейший тип ассоциативной памяти, который использует слова поиска данных, состоявшие полностью из единиц и нулей. В троичной АП добавляется третье значение для сравнения «X» или «не важно», для одного или более битов в сохраненном слове данных, добавляя таким образом большей гибкости поиску. Например, в троичной АП могло бы быть сохранено слово «10XX0», которое выдаст совдпадение на любое из четырех слов поиска «10000», «10010», «10100», или «10110». Добавление гибкости к поиску приходит за счет увеличения цены двоичной АП, поскольку внутренняя ячейка памяти должна теперь закодировать три возможных состояния вместо двух. Это дополнительное состояние обычно осуществляется добавлением бита маски «важности»(«важно»/«не важно») к каждой ячейке памяти.

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

Примеры приложений

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

Троичные АП часто используются в тех сетевых маршрутизаторах, в которых у каждого адреса есть две части: (1) адрес сети, который может измениться в размере в зависимости от конфигурации подсети, и (2) адрес хоста, который занимает оставшиеся биты. У каждой подсети есть маска сети, которая определяет, какие биты - адрес сети и какие биты - адрес хоста. Маршрутизация делается путем сверки с таблицей маршрутизации, которую поддерживает маршрутизатор (router). В ней содержатся все известные адреса сети назначения, связанная с ними маска сети и информация, необходимая пакетам, маршрутизируемым по этому назначению. Маршрутизатор, реализованный без АП, сравнивает адрес назначения пакета, который будет разбит, с каждым входом в таблице маршрутизации, выполняя при этом логическое И с маской сети и сравнивая результаты с адресом сети. Если они равны, соответствующая информация направления используется, чтобы отправить пакет. Использование троичной АП для таблицы маршрутизации делает процесс поиска очень эффективным. Адреса хранятся с использованием бита «не важно» в части адреса хоста, таким образом поиск адреса назначения в АП немедленно извлекает правильный вход в таблице маршрутизации; обе операции - применения маски и сравнения - выполняются аппаратно средствами АП.

Другие приложения АП включают

  • Диспетчеры кэша центрального процессора и ассоциативные буфера трансляции (TLB)

Библиография

  • Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 1982. - 384 с.

На английском языке

  • Anargyros Krikelis, Charles C. Weems (editors) (1997) Associative Processing and Processors , IEEE Computer Science Press. ISBN 0-8186-7661-2
  • Hannum et al. (2004) System and method for resetting and initializing a fully associative array to a known state at power on or through machine specific state . U.S. Patent 6,823,434.

Ссылки


Wikimedia Foundation . 2010 .

Смотреть что такое "Ассоциативная память" в других словарях:

    В информатике безадресная память, в которой поиск информации производится по ее содержанию (ассоциативному признаку). См. также: Память компьютера Прикладное программное обеспечение Финансовый словарь Финам … Финансовый словарь

    ассоциативная память - Память, в которой адресация определяется не местом расположения объекта, а его содержанием. Для нахождения адреса проводится анализ объекта и совпадение его названия (по определенным словам) с другими адресами. Использование ассоциативной памяти… … Справочник технического переводчика

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

    ассоциативная память - asociatyvioji atmintis statusas T sritis automatika atitikmenys: angl. associative memory vok. assoziativer Speicher, m; Durchsuchspeicher, m rus. ассоциативная память, f pranc. mémoire associative, f … Automatikos terminų žodynas

    АССОЦИАТИВНАЯ ПАМЯТЬ - См. память, ассоциативная … Толковый словарь по психологии

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

Обычно в запоминающих устройствах доступ к информации требует указания адреса ячейки. Однако значительно удобнее искать информацию не по адресу, а опираясь на какой-нибудь характерный признак, содержащийся в самой информации. Такой принцип лежит в основе ЗУ, известного как ассоциативное запоминающее устройство (АЗУ). В литературе встречаются и иные названия подобного ЗУ: память, адресуемая по содержанию (content addressable memory); память, адресуемая по данным (data addressable memory); память с параллельным поиском (parallel search memory); каталоговая память (catalog memory); информационное ЗУ (information storage); тегированная память (tag memory).

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

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

Ассоциативный признак– признак, по которому производится поиск информации.

Признак поиска– кодовая комбинация, выступающая в роли образца для поиска.

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

Структура ассоциативного ЗУ

АЗУ включает в себя:

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

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

  • а0 – не найдена;
  • а1 – содержится в одной ячейке;
  • а2 – содержится более чем в одной ячейке.

Формирование содержимого регистра совпадений и сигналов a0, a1, а2 носит название операции контроля ассоциации. Она является составной частью операций считывания и записи, хотя может иметь и самостоятельное значение.

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

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

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

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

  1. вида поиска информации;
  2. техники сравнения признаков;
  3. способа считывания информации при множественных совпадениях;
  4. способа записи информации.

В каждом конкретном применении АЗУ задача поиска информации может формулироваться по-разному.

Виды поиска информации :

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

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

Техника сравнения признаков:

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

Способ считывания информации при множественных совпадениях:

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

Способ записи информации:

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

Из-за относительно высокой стоимости АЗУ редко используется как самостоятельный вид памяти.

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

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

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

Похожие статьи