Шпаргалка по предмету "Основы информатики"

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

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

Архитектура современных 32-разрядных процессоров включает ряд средств кэширования памяти: два уровня кэша инструкций и данных (L1 Cache и L2 Cache), буферы ассоциативной трансляции (TLB) блока страничной переадресации и буферы записи. Эти средства в разных вариациях (на кристалле, картридже процессора или на системной плате) представлены в системах с процессорами 486, Pentium и Р6. В процессоре 80386 (Intel) имелся только TLB, а кэш-память, устанавливаемая на системной плате, не имела поддержки со стороны процессора. 

Все механизмы кэширования в основном прозрачны для прикладных программ и после разрешения кэширования пропускают через себя потоки инструкций и данных без требования явного программного управления. Однако знание особенностей механизмов кэширования помогает в оптимизации кода. Так например, можно определить оптимальные размеры одновременно обрабатываемых структур данных, при которых кэш не «буксует» (cache thrashing). Процессоры разных моделей имеют различные характеристики отдельных элементов кэша. Определить характеристики элементов кэша процессоров Р6 позволяет вызов инструкции CPUID(2). Заметим, что не все модели процессоров способны кэшировать весь объем физически адресуемой памяти.

Кэш-память процессоров строится с учетом возможности обращений к памяти со стороны внешних абонентов – других процессоров или иных контроллеров шины. Процессоры имеют механизмы внешнего слежения за состоянием собственного кэша с соответствующими аппаратными интерфейсами. Для поддержания согласованности данных кэша и основной памяти процессор отрабатывает циклы слежения (Snoop Cycle или Inquire Cycle), инициированные внешней (для него) системой. В этих циклах, происходящих при обращении к памяти со стороны внешнего абонента, процессор определяет присутствие затребованной области в своем собственном кэше. Если область отображается в кэше, то действия процессора зависят от состояния соответствующей строки кэша и типа внешнего обращения. Обращение по записи вызовет аннулирование данной строки. Обращение по чтению к области, соответствующей модифицированной («грязной») строке, вызовет выгрузку ее содержимого в основную память, прежде чем внешний абонент выполнит реальное считывание. В процессорах Р6 обращение к «грязной» строке со стороны другого процессора может вызывать выгрузку ее содержимого непосредственно в обращающийся процессор, что экономит время. Выгрузка этой строки в основную память будет произведена позже, согласно алгоритму обратной записи

 

 

 

 

 

 

 

 

 

 

 

21. Кэш прямого отображения. Наборно-ассоциативный и ассоциативный  кэш.

Кэш прямого отображения

В кэш-памяти прямого отображения адрес памяти, по которому происходит обращение, однозначно определяет строку кэша, в которой может находиться требуемый блок. Принцип работы такого кэша поясним на примере несекторированного кэша объемом 256 Кбайт с размером строки 32 байта и объемом кэшируемой основной памяти 64 Мбайт – типичный кэш системной платы для Pentium

Кэшируемая основная память условно разбивается на страницы (в данном случае по 256 Кбайт), размер которых совпадает с размером кэш-памяти (256 Кбайт). Кэш-память (и, условно, страницы основной памяти) делятся на строки (256 Кбайт/32= 8 Кбайт строк). Архитектура прямого отображения подразумевает, что каждая строка кэша может отображать из любой страницы кэшируемой памяти только соответствующую ей строку. Поскольку объем основной памяти много больше объема кэша, на каждую строку кэша может претендовать множество блоков памяти с одинаковой младшей частью адреса (смещением внутри страницы). Одна строка в определенный момент может, естественно, содержать копию только одного из этих блоков. Номер (адрес) строки в кэш-памяти называется индексом (index). Тег несет информацию о том, какой именно блок занимает данную строку (то есть старшая часть адреса или номер страницы). Память тегов должна иметь количество ячеек, равное количеству строк кэша, а ее разрядность должна быть достаточной, чтобы вместить старшие биты адреса кэшируемой памяти, не попавшие на шину адреса кэш-памяти. Кроме адресной части тега, с каждой строкой кэша связаны биты признаков действительности и модифицированности данных. В начале каждого обращения к кэшируемой памяти контроллер вначале считывает ячейку каталога с заданным индексом, сравнивает биты адреса тега со старшими битами адреса памяти и анализирует признак действительности. Этот анализ выполняется в специальном цикле слежения (snoop cycle), иногда его называют циклом запроса(inquire). Если в результате анализа выясняется, что требуемого блока нет в кэше, генерируется (или продолжается) цикл обращения к основной памяти (случай кэш-промаха). В случае попадания запрос обслуживается кэш-памятью. В случае промаха после считывания основной памяти приемником информации новые данные помещаются в строку кэша (если она чистая), а в ее тег помещаются старшие биты адреса и устанавливается признак действительности данных. Независимо от объема затребованных данных в кэш из основной памяти строка переписывается вся целиком (поскольку признак действительности относится ко всем ее байтам). Если контроллер кэша реализует упреждающее считывание (read ahead), то в последующие свободные циклы шины также обновится и следующая строка (если она была чистой). Чтение “про запас” позволяет при необходимости осуществлять пакетный цикл чтения из кэша через границу строки.

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

Объем кэшируемой памяти (Мcached) при архитектуре прямого отображения определяется объемом кэш-памяти (Vcache) и разрядностью памяти тегов (N):

Мcached = Vcache • 2N, в нашем случае Мcached = 256 Кбайт • 28 = 64 Мбайт.

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

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

В простейшем случае каждый блок памяти может помещаться в одну из двух строк (Two Way Set-Associative Cache – двухканальный наборно-ассоциативный кэш). Такой кэш должен содержать два банка памяти тегов.

Номер набора (индекс), в котором может отображаться затребованный блок данных, однозначно определяется средней частью адреса (как номер строки в кэше прямого отображения). Строка набора, отображающая требуемый 
5-2  блок, определяется сравнением тегов (как и в ассоциативном кэше), параллельно выполняемым для всех каналов кэша. Кроме того, с каждым набором должен быть связан признак, определяющий строку набора, подлежащую замещению новым блоком данных в случае кэш-промаха. Кандидатом на замещение обычно выбирается строка, к которой дольше всего не обращались (алгоритм LRU– Least Recently Used). При относительно большом количестве каналов (строк в наборе) прибегают к некоторому упрощению – алгоритм Pseudo-LRU для четырех строк (Four Way Set Associative Cache) позволяет принимать решения, используя всего 3 бита. Возможно также применение алгоритма замещения FIFO (первым вошел – первым вышел) или даже случайного (random) замещения, что проще, но менее эффективно. Наборно-ассоциативная архитектура широко применяется для первичного кэша современных процессоров. Объем кэшируемой памяти определяется так же, как и в предыдущем варианте, но здесь фигурируют объем одного банка (а не всего кэша) и разрядность относящихся к нему ячеек тега.

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

 

 

 

22. Математическая модель  нейрона, как объекта, обрабатывающего  информацию.

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

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

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

Составные части нейрона :

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

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

Искусственная нейронная сеть

Искусственная нейронная сеть это совокупность нейронных элементов и связей между ними [1].

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

Рисунок 2: математическая модель нейрона

• Нейрон обладает группой синапсов - однонаправленных входных связей, соединенных с выходами других нейронов. Каждый синапс характеризуется величиной синаптической связи или ее весом wi.
• Каждый нейрон имеет текущее состояние, которое обычно определяется, как взвешенная сумма его входов: 

 

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

y = f(s)

 

Функция f называется функцией активации.

Рисунок 3: различные виды функции активации

Функция активации может иметь разный вид : пороговый ( рис. 3.a), кусочно-линейный ( рис. 3.б), сигмоид( рис. 3.в, 3.г ).

Множество всех нейронов искусственной нейронной сети можно разделить на подмножества - т.н. слои. Взаимодействие нейронов происходит послойно.

Слой искусственной нейронной сети это множество нейронов на которые в каждый такт времени параллельно поступают сигналы от других нейронов данной сети [1].

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

Искусственные нейронные сети могут быть программного и аппаратного исполнения. Реализация аппаратная обычно представляет собой параллельный вычислитель, состоящий из множества простых процессоров [3].