Контрольная работа №2 (кр_в)

Контрольная работа №2.

1. Многоуровневый кэш (параметры, эффективность, учет при программировании).

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

По алгоритмам отображения оперативной памяти в кэш выделяют три типа кэш-памяти:

• полностью ассоциативный кэш (fully associative) – любой блок оперативной памяти может быть помещен в любую строку кэш-памяти;

• кэш прямого отображения (direct mapped) – блок ОЗУ будет всегда помещаться в строго определенную строку кэша;

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

В зависимости от того, хранятся ли данные и команды отдельно или вместе, можно выделить две архитектуры кэш-памяти:

• принстонская – смешанный кэш для команд и данных, например, в Intel-486;

• гарвардская – разделение кэш-памяти на кэш команд (I-cache), кэш данных
  (D-cache), буферы TLB. Это позволяет повысить эффективность работы кэша по следующим соображениям:

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

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

Именно поэтому все последние модели IA-32, начиная с Pentium, для организации кэш-памяти первого уровня используют гарвардскую архитектуру.

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

T_ср = (T_hit x R_hit) + (T_miss x (1 – R_hit)), где

T_hit - время доступа к кэш-памяти в случае попадания (включает время на идентификацию промаха или попадания);

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

R_hit - частота попаданий.

Чем ближе значение R_hit к 1, тем ближе значение T_ср к T_hit. Частота попаданий определяется в основном архитектурой кэш-памяти и ее объемом. На Рис.1 приведена зависимость частоты промахов от объема кэш-памяти первого уровня (L1) для архитектуры Alpha 21264. Данная зависимость была получена с помощью бенчмарка SPEC CPU2000.

2-way

прямой

полностью ассоциативный

4-way

8-way

Рисунок 1. Зависимость частоты промахов от объема кэша L1

Как видно, при возрастании объема кэша частота попаданий растет. Однако, при этом возрастает и латентность кэша, что негативно сказывается на производительности системы. Это привело к появлению многоуровневого кэша, для которого характерно разделение на несколько уровней, отличающихся размером и латентностью. Сначала проверяется кэш первого уровня (L1), имеющий минимальный размер и латентность. В случае непопадания проверяется кэш второго уровня (L2), и т.д. В современных высокопроизводительных системах используется 3 уровня кэша, например в процессоре Intel Itanium 2 кэш L3 имеет объем 6Мб, в IBM Power 4 – 256Мб (расположен не на чипе), в настольном процессоре AMD Phenom – 2Мб. В дальнейшем для простоты будем рассматривать случай двухуровневого кэша.

Можно выделить три основных типа многоуровневого кэша:

• исключающий (exclusive) кэш (например, в AMD Athlon) – если данные хранятся в кэше, то только в одном из уровней;

• строго включающий (strictly inclusive) кэш – все данные кэша L1 должны также храниться в кэше L2;

• нестрого включающий (mainly inclusive) кэш (например, в Intel Pentium II, III, IV) – все данные кэша L1 не обязательно продублированы в кэше L2, но для некоторых данных это может иметь место.

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

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

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

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

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

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

2. Влияние страничной организации ОЗУ на скорость вычислений.

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

Информация о каждой виртуальной странице хранится в таблице страниц, основную проблему для эффективной реализации которой создают большие размеры виртуальных адресных пространств. Например, 32-разрядные процессоры позволяют создавать виртуальные адресные пространства размером 4 Гбайт. В 32-битном адресном пространстве при размере страницы 4 Кбайт получаем 2³²/2¹²=2²⁰. Таким образом, таблица должна иметь примерно миллион строк, причем запись в строке состоит из нескольких байтов. Кроме того, каждый процесс нуждается в своей таблице страниц. Чтобы избежать размещения в памяти огромной таблицы, ее разбивают на ряд фрагментов. В оперативной памяти хранят лишь некоторые, необходимые для конкретного момента исполнения фрагменты таблицы страниц. В силу свойства локальности число таких фрагментов относительно невелико. Выполнить разбиение таблицы страниц на части можно по-разному. Наиболее распространенный способ разбиения – организация так называемой многоуровневой таблицы страниц:

Рисунок 2. Пример двухуровневой таблицы страниц.

Таблица, состоящая из 2²⁰ строк, разбивается на 2¹⁰ таблиц второго уровня по 2¹⁰ строк. Эти таблицы второго уровня объединены в общую структуру при помощи одной таблицы первого уровня, состоящей из 2¹⁰ строк. 32-разрядный адрес делится на 10-разрядное поле p₁, 10-разрядное поле p₂ и 12-разрядное смещение d. Поле p₁ указывает на нужную строку в таблице первого уровня, поле p₂ – второго, а поле d локализует нужный байт внутри указанного страничного кадра. Таким образом, для размещения процесса с большим объемом занимаемой памяти достаточно иметь в оперативной памяти одну таблицу первого уровня и несколько таблиц второго уровня.

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

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

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