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

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

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

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

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

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

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

    Принцип работы АЗУ поясняет схема, представленная на рис. 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 битами) адреса считываемого блока. На место удаленной кэш-строки помещается считанный из ОП блок, при этом обновляется соответствующий тег в памяти тегов.

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

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

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

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

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

    Но хватит теории, пора переходить непосредственно к простым и совершенно необременительным упражнениям!

    Итак, вы прочитали 50 слов, представляя соответствующие образы как можно ярче, в цвете и движении. А теперь постарайтесь связать все слова в один длинный рассказ или в несколько коротких: кошка, дом, машина, яблоко…

    Ключ

    Бело-рыжая КОШКА зашла в ДОМ из красного кирпича, прошла во встроенный гараж, села в малиновую МАШИНУ, выехала на автостраду и стала, управляя рулем левой лапой, грызть зеленое ЯБЛОКО, держа его правой лапой.

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

    Данный текст является ознакомительным фрагментом. Из книги Психология интеллекта и одаренности автора Ушаков Дмитрий Викторович

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

    автора Мюллер Станислав

    Часть I. Как в два раза улучшить память за сорок пять минут, или Введение в голографическую память С чего все начиналось… Несколько лет назад, после окончания последнего занятия по развитию памяти, один из студентов предъявляет претензии в отношении результатов

    Из книги Разблокируй свою память: запомни все! автора Мюллер Станислав

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

    Из книги Разблокируй свою память: запомни все! автора Мюллер Станислав

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

    Из книги Разблокируй свою память: запомни все! автора Мюллер Станислав

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

    Из книги Разблокируй свою память: запомни все! автора Мюллер Станислав

    Ассоциативная память Придумайте один рассказ, содержащий все пятьдесят слов, или несколько коротких. Трудные слова теперь не пропускаем. Составление рассказа не должно уже представлять для вас труда.Вспоминать слова или рассказы на данном этапе развития ассоциативной

    автора Мюллер Станислав

    Часть I Как в два раза улучшить память за 45 минут, или введение в голографическую память «В начале славных дел…» Несколько лет назад, после окончания последнего занятия по развитию памяти, один из студентов предъявил мне претензии:– Станислав, люди к вам приходят, чтобы

    Из книги Вспомни всё [Секреты суперпамяти. Книга-тренажер] автора Мюллер Станислав

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

    Из книги Начнем сначала, или Как разглядеть свое Завтра автора Козлов Николай Иванович

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

    Из книги Психология взрослости автора Ильин Евгений Павлович

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

    Из книги Психология развития [Методы исследования] автора Миллер Скотт

    «Повседневная» память и долговременная память Рассмотрим еще два вопроса, имеющих отношение к теме «Память». До сих пор основное внимание уделялось стандартным лабораторным методам, часто исполь-зуемым при изучении памяти в любой возрастной период. Два последних

    Из книги Общая психология автора Дмитриева Н Ю

    8. Ассоциативная психология В процессе формирования психологии стал преобладать ассоцианистский подход к восприятию. Ассоциативная психология – одно из основных направлений в психологии XVII–XIX вв. Главным объяснительным принципом психической жизни являлось понятие

    Из книги Все лучшее, что не купишь за деньги. Мир без политики, нищеты и войн автора Фреско Жак

    автора Ньюберг Эндрю

    Из книги Тайна Бога и наука о мозге [Нейробиология веры и религиозного опыта] автора Ньюберг Эндрю

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

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


    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
    Читать еще: