Погрешности. Техническая диагностика

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

Рис. 10 - Основные аспекты технической диагностики

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

Вопрос 3. Кэш-память. Принцип действия кэш-памяти. Проблема согласования данных

Введение

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

Рис. 11

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

На следующем уровне располагается более быстродействующая (время доступа равно примерно 10-20 наносекундам) и менее объемная (от десятков мегабайт до нескольких гигабайт) оперативная память, реализуемая на относительно медленной динамической памяти DRAM.

Для хранения данных, к которым необходимо обеспечить быстрый доступ, используются компактные быстродействующие запоминающие устройства на основе статической памяти SRAM, объем которых составляет от нескольких десятков до нескольких сотен килобайт, а время доступа к данным обычно не превышает 8 нс.

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

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

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

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

«Медленное» ЗУ далее будем называть основной памятью, противопоставляя ее вспомогательной кэш-памяти.

Цели и задачи кэш-памяти

В задачи кэша входит:

обеспечение быстрого доступа к интенсивно используемым данным;

согласование интерфейсов процессора и контроллера памяти;

упреждающая загрузка данных;

отложенная запись данных.

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

Рис. 12

Расположение кэша в иерархии оперативной памяти

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

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

Поиск наименее нужных данных называется стратегией замещения. Можно принимать решение, основываясь на количестве обращений к каждой порции данных (частотный анализ), можно - на времени последнего обращения, выбрав ту, к которой дольше всего не обращались (алгоритм LRU - Least Recently Used), можно - на времени загрузки из основной памяти, вытеснив ту, которая была загружена раньше всех (алгоритм FIFO - First Input First Output), а можно просто случайно (randomize-алгоритм) (кстати, именно такая стратегия замещения использовалась в процессорах AMD K5).

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

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

Упреждающая загрузка данных. Существует несколько стратегий загрузки данных из основной оперативной памяти в кэш-память. Простейший алгоритм загрузки, называемый загрузкой по требованию (on demand), предписывает обращаться к основной памяти только после того, как затребованных процессором данные не окажется в кэше (то есть, попросту говоря, после возникновения кэш-промаха). Использование такой стратегии приводитк тому, что в кэш попадают действительно нужные нам данные (и это плюс!), однако, при первом обращении к ячейке, процессору придется очень долго ждать - приблизительно 20 тактов системной шины, что есть несомненный минус! Стратегия спекулятивной (speculative) загрузки, напротив, предписывает помещать данные в кэш задолго то того, как к ним произойдет реальное обращение. Откуда же кэш-контроллеру знать, какие именно ячейки памяти потребуется процессору в ближайшем будущем? Наверняка знать этого он этого не может, но может попробовать угадать. Алгоритмы угадывания делятся на интеллектуальные и неинтеллектуальные. Типичный пример неинтеллектуального алгоритма - опережающая загрузка. Исходя из предположения, что данные из оперативной памяти обрабатываются последовательно в порядке возрастания адресов, кэш-контроллер, перехватив запрос на чтение первой ячейки, в порядке собственной инициативы загружает некоторое количество ячеек, последующих за ней. Если данные действительно обрабатываются последовательно, то остальные запросы процессора будут выполнены практически мгновенно, ведь запрошенные ячейки уже присутствуют в кэше. Следует заметить, что стратегия опережающей загрузки возникает уже в силу необходимости согласования разрядности оперативной памяти и процессора.

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

Интеллектуальный кэш-контроллер предсказывает адрес следующей запрашиваемой ячейки не по слепому шаблону, а на основе анализа предыдущих обращений. Исследуя последовательность кэш-промахов, контроллер пытается установить, какой именно зависимостью связны ее элементы и, если это ему удается, предвычисляет ее последующие члены. Если обращение к памяти происходит по регулярному шаблону, интеллектуальная стратегия спекулятивной загрузки при благоприятном стечении обстоятельств может полностью ликвидировать задержки, возникающие при ожидании загрузки данных из основной памяти. До недавнего прошлого интеллектуальные кэш-контроллеры использовались разве что в суперкомпьютерах, но теперь они реализованы в процессорах P-4 и AMD Athlon XP.

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

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

Принцип действия кэш-памяти

Рассмотрим одну из возможных схем кэширования. Содержимое кэш-памяти представляет собой совокупность записей обо всех загруженных в нее элементах данных из основной памяти. Каждая запись об элементе данных включает в себя:

значение элемента данных;

адрес, который этот элемент данных имеет в основной памяти;

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

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

если данные обнаруживаются в кэш-памяти, то есть произошло кэш-попадание (cache-hit), они считываются из нее и результат передается источнику запроса;

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

Рис. 13

Схема функционирования кэш-памяти

Понятно, что эффективность кэширования зависит от вероятности попадания в кэш. Покажем это путем нахождения зависимости среднего времени доступа к основной памяти от вероятности кэш-попаданий. Пусть имеется основное запоминающее устройство со средним временем доступа к данным t1 и кэш-память, имеющая время доступа t2, очевидно, что t2<t1. Пусть t -- среднее время доступа к данным в системе с кэш-памятью, ар -- вероятность кэш-попадания. По формуле полной вероятности имеем:

t - t1(d - р) + t2p - (t2 -t1)p + t1

Среднее время доступа к данным в системе с кэш-памятью линейно зависит от вероятности попадания в кэш и изменяется от среднего времени доступа в основное запоминающее устройство t1 при р=0 до среднего времени доступа непосредственно в кэш-память t2 при р=1. Отсюда видно, что использование кэш-памяти имеет смысл только при высокой вероятности кэш-попадания.

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

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

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

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

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

Проблема согласования данных

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

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

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

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

Способы отображения основной памяти на кэш

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

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

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

Рис. 14

Ассоциативный поиск в кэше со случайным отображением

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

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

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

Рис. 15

Прямое отображение

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

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

Рис. 16

Комбинирование прямого и случайного отображения

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

Размещено на Allbest.ru