21.Общая шина: структура, принцип действия, виды шин
Шина – набор проводников. Как правило, в шину объединяют проводники, передающие сходные по назначению сигналы. Например, по шинам передаются в параллельном коде машинные слова: так в архитектуре вычислительных систем выделяют шину данных, шину команд, шину адреса, и т.п.
Общая шина – шина, сигналы на которую могут выдавать несколько устройств. Общая шина характеризуется тем, что к ней подключено несколько источников сигналов (драйверов) и для обеспечения правильного функционирования, а часто и физической целости системы, необходимо, чтобы в каждый момент времени на шину работал только один источник сигнала, а остальные источники находились в неактивном состоянии. Это достигается использованием специальных логических элементов с тремя состояниями (tri‑state outputs) и соответствующим управлением. К состояниям выхода «0» и «1» добавляется состояние «Z», в котором выход элемента отключен и от «0» и от «1», то есть в котором устройство не влияет на состояние сигналов общей шины. Буфер с тремя состояниями часто называют шинным формирователем.
Подключенные к общей шине устройства совместно или с помощью специального устройства – арбитра определяют очередность доступа к общей шине. Если два устройства будут выдавать на шину свои сигналы одновременно, может возникнуть конфликт. Так, если одно устройство выдает на шину «1», а другое – «0», то по шине потечет ток короткого замыкания, от «1» к «0», который может разрушить проводники шины или выходные усилители одного из устройств.
Поскольку устройства реагируют на сигналы, предоставляющие доступ к шине, не мгновенно, а с некоторой (в общем - случайной) задержкой, то в предоставлении устройствам доступа к шине всегда предусматривают паузы так, чтобы предыдущее устройство успело отключиться от шины, а следующее подключилось лишь после этого.
Другой распространенный вариант подключения нескольких источников сигналов к шине – использование мультиплексоров. В этом случае обеспечивается логическая коммутация сигналов. Мультиплексирование обеспечивает физическую целость устройства даже при неправильном управлении.
В логическом массиве СБИС ПЛ фирмы Altera отсутствуют внутренние шины с тремя состояниями (трехстабильные) и компилятор автоматически заменяет общую шину с трехстабильными элементами на шину с мультиплексированием сигналов. Трехстабильные буферы ввода/вывода СБИС ПЛ позволяют физически подключаться к внешним общим шинам. САПР Quartus при логическом синтезе не позволяет избежать конфликтов на выводах СБИС ПЛ, поскольку не имеет информации о внешних устройствах, подключенных к выводам. Однако при моделировании выявляются конфликты на выводах СБИС ПЛ, обусловленные подачей недопустимых внешних воздействий.
22.Принцип и алгоритмы кэширования данных при передаче
Кэш (англ. cache произносится [kæʃ])[1] — в компьютерных науках это подборка данных, дублирующих оригинальные значения, сохранённые где-то или вычисленные ранее, когда оригинальные данные труднодоступны из-за большого времени доступа или для вычисления. Другими словами, кэш — это промежуточный буфер с быстрым доступом, который хранит в себе ту информацию, которая с наибольшей вероятностью может быть запрошена. Один раз сохранённые в кэше данные в будущем могут использоваться доступом к кэшированной копии — это будет быстрее, чем повторная выборка или повторное вычисление оригинальных данных, так что среднее время доступа будет короче. Таким образом, кэш помогает ускорить доступ к данным.
Использование слова «кэш» в компьютерном контексте началось в 1967 году во время подготовки статьи для публикации в журнале IBM Systems. Статья касалась захватывающего усовершенствования памяти в модели 85, опоздавшего в линии продукта IBM System/360. Редактор журнала, Lyle R. Johnson, просивший придумать более описательный термин, чем «высокоскоростной буфер», за отсутствием идей, предложил слово «кэш». Статья была опубликована в начале 1968 года, авторы были премированы IBM, их работа была широко принята и впоследствии улучшена, и «кэш» вскоре стало использоваться в компьютерной литературе как стандартный термин. [2]
Своим происхождением слово Кэш обязано сленговому обозначению наличных денег. Собственно, аналогия сравнения англ. cash и англ. cache заключается в следующем: основная память, к которой происходит обращение (жёсткий диск, ОЗУ) сравнивается со счётом в банке, а кэш — с вашими наличными, которые клиент берёт в банке для быстрых расчётов.
[править] Функционирование
Диаграмма кэша памяти ЦПУ
Кэш —- это память с большей скоростью доступа, предназначенная для ускорения обращения к данным, содержащимся постоянно в памяти с меньшей скоростью доступа (далее «основная память»). Кэширование применяется ЦПУ, жёсткими дисками, браузерами и веб-серверами.
Кэш состоит из набора записей. Каждая запись ассоциирована с элементом данных или блоком данных (небольшой части данных), которая является копией элемента данных в основной памяти. Каждая запись имеет идентификатор, определяющий соответствие между элементами данных в кэше и их копиями в основной памяти.
Когда клиент кэша (ЦПУ, веб-браузер, операционная система) обращается к данным, прежде всего исследуется кэш. Если в кэше найдена запись с идентификатором, совпадающим с идентификатором затребованного элемента данных, то используются элементы данных в кэше. Такой случай называется попаданием кэша. Если в кэше не найдено записей, содержащих затребованный элемент данных, то он читается из основной памяти в кэш, и становятся доступным для последующих обращений. Такой случай называется промахом кэша. Процент обращений к кэшу, когда в нём найден результат, называется уровнем попаданий или коэффициентом попаданий в кэш.
Например, веб-браузер проверяет локальный кэш на диске на наличие локальной копии веб-страницы, соответствующей запрошенному URL. В этом примере URL —- это идентификатор, а содержимое веб-страницы —- это элементы данных.
Если кэш ограничен в объёме, то при промахе может быть принято решение отбросить некоторую запись для освобождения пространства. Для выбора отбрасываемой записи используется так называемый алгоритм вытеснения (см. алгоритмы вытеснения).
При модификации элементов данных в кэше выполняется их обновление в основной памяти. Задержка во времени между модификацией данных в кэше и обновлением основной памяти управляется так называемой политикой записи.
В кэше с немедленной записью каждое изменение вызывает синхронное обновление данных в основной памяти.
В кэше с отложенной записью (или обратной записью) обновление происходит в случае вытеснения элемента данных, периодически или по запросу клиента. Для отслеживания модифицированных элементов данных записи кэша хранят признак модификации (изменённый или «грязный»). Промах в кэше с отложенной записью может потребовать два обращения к основной памяти: первое для записи заменяемых данных из кэша, второе для чтения необходимого элемента данных.
В случае, если данные в основной памяти могут быть изменены независимо от кэша, то запись кэша может стать неактуальной. Протоколы взаимодействия между кэшами, которые сохраняют согласованность данных, называют протоколами когерентности кэша.
[править] Кэш центрального процессора
Ряд моделей центральных процессоров (ЦП) обладают собственным кэшем, для того чтобы минимизировать доступ к оперативной памяти (ОЗУ), которая медленее, чем регистры. Кэш-память может давать значительный выигрыш в производительности, в случае когда тактовая частота ОЗУ значительно меньше тактовой частоты ЦП. Тактовая частота для кэш-памяти обычно ненамного меньше частоты ЦП. См. так же TLB.
Уровни кэша
Кэш центрального процессора разделён на несколько уровней. Для универсальных процессоров – до 3. Кэш-память уровня N+1 как правило больше по размеру и медленнее по скорости обращения и передаче данных, чем кэш-память уровня N.
Самой быстрой памятью является кэш первого уровня – L1-cache. По сути, она является неотъемлемой частью процессора, поскольку расположена на одном с ним кристалле и входит в состав функциональных блоков. Состоит из кэша команд и кэша данных. Некоторые процессоры без L1 кэша не могут функционировать. На других его можно отключить, но тогда значительно падает производительность процессора. L1 кэш работает на частоте процессора, и, в общем случае, обращение к нему может производиться каждый такт (зачастую является возможным выполнять даже несколько чтений/записей одновременно). Латентность доступа обычно равна 2−4 тактам ядра. Объём обычно невелик — не более 64 КБ.
Вторым по быстродействию является L2-cache – кэш второго уровня. Обычно он расположен либо на кристалле, как и L1, либо в непосредственной близости от ядра, например, в процессорном картридже (только в слотовых процессорах). В старых процессорах – набор микросхем на системной плате. Объём L2 кэша от 128 КБ до 1−8 МБ. В современных многоядерных процессорах кэш второго уровня, находясь на том же кристалле, является памятью раздельного пользования – при общем объёме кэша в 8 МБ на каждое ядро приходится по 2 Мб. Обычно латентность L2 кэша, расположенного на кристалле ядра, составляет от 8 до 20 тактов ядра. В отличие от L1 кэша, его отключение может не повлиять на производительность системы. Однако, в задачах, связанных с многочисленными обращениями к ограниченной области памяти, например, СУБД, производительность может упасть в десятки раз.
Кэш третьего уровня наименее быстродействующий и обычно расположен отдельно от ядра ЦП, но он может быть очень внушительного размера – более 32 МБ. L3 кэш медленнее предыдущих кэшей, но всё равно значительно быстрее, чем оперативная память. В многопроцессорных системах находится в общем пользовании.
Отключение кэша второго и третьего уровней обычно используется в математических задачах, например, при обсчёте полигонов, когда объём данных меньше размера кэша. В этом случае, можно сразу записать все данные в кэш, а затем производить их обработку.
Ассоциативность кэша
Одна из фундаментальных характеристик кэш-памяти — уровень ассоциативности — отображает ее логическую сегментацию. Дело в том, что последовательный перебор всех строк кэша в поисках необходимых данных потребовал бы десятков тактов и свел бы на нет весь выигрыш от использования встроенной в ЦП памяти. Поэтому ячейки ОЗУ жестко привязываются к строкам кэш-памяти (в каждой строке могут быть данные из фиксированного набора адресов), что значительно сокращает время поиска. С каждой ячейкой ОЗУ может быть связано более одной строки кэш-памяти: например, n-канальная ассоциативность (англ. n-way set associative) обозначает, что информация по некоторому адресу оперативной памяти может храниться в n местах кэш-памяти.
При одинаковом объеме кэша схема с большей ассоциативностью будет наименее быстрой, но наиболее эффективной.
Кэширование внешних накопителей
Многие периферийные устройства хранения данных используют кэш для ускорения работы, в частности, жёсткие диски используют кэш-память от 1 до 32 Мб (модели с поддержкой NCQ/TCQ используют её для хранения и обработки запросов), устройства чтения CD/DVD/BD-дисков так же кэшируют прочитанную информацию для ускорения повторного обращения. Операционная система так же использует часть оперативной памяти в качестве кэша дисковых операций (в том числе для внешних устройств, не обладающих собственной кэш-памятью, в том числе жестких дисков, flash-памяти и гибких дисков).
Применение кэширования внешних накопителей обусловлено следующими факторами:
скорость доступа процессора к оперативной памяти во много раз больше, чем к памяти внешних накопителей;
некоторые блоки памяти внешних накопителей используются несколькими процессами одновременно и имеет смысл прочитать блок один раз, затем хранить одну копию блока в оперативной памяти для всех процессов;
доступ к некоторым блокам оперативной памяти происходит гораздо чаще, чем к другим, поэтому использование кэширования для таких блоков в целом увеличивает производительность системы;
для некоторых блоков памяти внешних накопителей не требуется непосредственной записи после модификации, и использование кэша для таких блоков оптимизирует использование ввода-вывода.
Кэширование выполняемое операционной системой
Кэш оперативной памяти состоит из следующих элементов:
набор страниц оперативной памяти, разделенных на буферы, равные по длине блоку данных соответствующего устройства внешней памяти;
набор заголовков буферов, описывающих состояние соответствующего буфера;
хэш-таблицы, содержащей соответствие номера блока заголовку;
списка свободных буферов.
Алгоритм работы кэша с отложенной записью
Изначально все заголовки буферов помещаются в список свободных буферов. Если процесс намеревается прочитать или модифицировать блок, то он выполняет следующий алгоритм:
пытается найти в хэш-таблице заголовок буфера с заданным номером;
в случае, если полученный буфер занят, ждет его освобождения;
в случае, если буфер не найден в хэш-таблице, берет первый буфер из хвоста списка свободных;
в случае, если список свободных буферов пуст, то выполняется алгоритм вытеснения (см. ниже);
в случае, если полученный буфер помечен как «грязный», выполняет асинхронную запись содержимого буфера во внешнюю память.
удаляет буфер из хэш-таблицы, если он был помещен в неё;
помещает буфер в хэш-таблицу с новым номером.
Процесс читает данные в полученный буфер и освобождает его. В случае модификации процесс перед освобождением помечает буфер как «грязный». При освобождении буфер помещается в голову списка свободных буферов.
Таким образом:
если процесс прочитал некоторый блок в буфер, то велика вероятность, что другой процесс при чтении этого блока найдет буфер в оперативной памяти;
запись данных во внешнюю память выполняется только тогда, когда не хватает «чистых» буферов, либо по запросу.
Алгоритм вытеснения
Если список свободных буферов пуст, то выполняется алгоритм вытеснения буфера. Алгоритмов вытеснения существенно влияет на производительность кэша. Существуют следующие алгоритмы:
LRU (Least Recently Used) — вытесняется буфер, неиспользованный дольше всех;
MRU (Most Recently Used) — вытесняется последний использованный буфер;
LFU (Least Frequently Used) — вытесняется буфер, использованный реже всех;
ARC (Advanced Replacement Cache) — алгоритм вытеснения, комбинирующий LRU и LFU, запатентованный IBM.
Применение того или иного алгоритма зависит от стратегии кэширования данных. LRU наиболее эффективен, если данные гарантированно будут повторно использованы в ближайшее время. MRU наиболее эффективен, если данные гарантированно не будут повторно использованы в ближайшее время. В случае, если приложение явно указывает стратегию кэширования для некоторого набора данных, то кэш будет функционировать наиболее эффективно.
При чтении данных кэш-память даёт однозначный выигрыш в производительности. При записи данных выигрыш можно получить только ценой снижения надёжности. Поэтому в различных приложениях может быть выбрана та или иная политика записи кэш-памяти..
Существуют две основные политики записи кэш-памяти — сквозная запись (write-through) и отложенная запись (write-back).
сквозная запись подразумевает, что при изменении содержимого ячейки памяти, запись происходит синхронно и в кэш и в основную память.
отложенная запись подразумевает, что можно отложить момент записи данных в основную память, а записать их только в кэш. При этом данные будут выгружены в оперативную память только в случае обращения к ним какого либо другого устройства (другой ЦП, контроллер DMA) либо нехватки места в кэше для размещения других данных. Производительность, по сравнению со сквозной записью, повышается, но это может поставить под угрозу целостность данных в основной памяти, поскольку программный или аппаратный сбой может привести к тому, что данные так и не будут переписаны из кэша в основную память. Кроме того, в случае кэширования оперативной памяти, когда используются два и более процессоров, нужно обеспечивать согласованность данных в разных кэшах.
Кэширование интернет-страниц
В процессе передачи информации по сети может использоваться кэширование интернет-страниц — процесс сохранения часто запрашиваемых документов на (промежуточных) прокси-серверах или машине пользователя, с целью предотвращения их постоянной загрузки с сервера-источника и уменьшения трафика. Таким образом, информация перемещается ближе к пользователю. Управление кэшированием осуществляется при помощи HTTP-заголовков. Как вариант, кэширование веб-страниц может осуществляться с помощью CMS конкретного сайта для снижения нагрузки на сервер при большой посещаемости. Кэширование может производится как в память, так и в файловый кэш (кэш на файлах).
Кэширование результатов работы
Многие программы записывают куда-либо промежуточные или вспомогательные результаты работы, чтобы не вычислять их каждый раз, когда они понадобятся. Это ускоряет работу, но требует дополнительной памяти (оперативной или дисковой). Примером такого кэширования является индексирование баз данных.