Performance analysis of multilevel memory .pdf Современное состояние вычислительной техники характеризуется растущим разрывом между скоростью обработки данных в микропроцессорах и быстродействием оперативной памяти. Многоуровневая организация памяти позволяет сгладить этот разрыв с помощью механизма кэширования - накопления часто используемых данных в верхних, более быстрых, но менее емких уровнях памяти для быстрого доступа к ним.В наиболее общем случае организации многоуровневой памяти кэш и оперативное запоминающее устройство (ОЗУ) разбиты на блоки фиксированной длины. В кэше блоки объединяются в группы объемом A блоков. Число А называется коэффициентом ассоциативности.Процесс выбора данных из многоуровневой памяти блокирующего типа производится следующим образом: сначала процессор обращается в кэш уровня 1. Если требуемый блок находится в кэше («попадание»), то элемент извлекается из кэша, иначе («промах») происходит обращение к следующему уровню памяти [1].1. Модель многоуровневой памятиРассмотрим многоуровневую подсистему памяти с количеством уровней в иерархии равным U > 1. На каждом уровне u = 1...U -1, кроме последнего, находится кэш; последний уровень u = U занимает ОЗУ (рис. 1). Количество блоков в ОЗУ равно Уи = УОЗУ = V . Время выбора блока из ОЗУ равно Ки = КОЗУ = К , авремя поиска и выбора блока из кэша уровня u равно Ku. Кэш каждого уровня характеризуется следующими параметрами: объемом кэша в блоках - Vu; количеством групп - Gu, коэффициентом ассоциативности - Au = Vu / Gu; количеством блоков ОЗУ, отображаемых на группу кэша u-го уровня Mu = V03y / Gu. По логике построения многоуровневой памяти с ростом номера уровня времена обращения и объемы памяти возрастают:K < Kj, Vi < Vj, i < j.Для исследования эффективности работы кэша используется модель с идеальной стратегией вытеснения блоков [2]. В этом случае предполагается, что заранее известно распределение вероятностей востребованности блоков памяти вычислителем:p(i), i = 0, V -1, X1 p(i) = 1. (1)Важнейшей операционной характеристикой кэша заданного уровня u является вероятность попадания в кэш, которая определяется соотношением [2]Gu-1Mu-1П = ЁЁ П (g + Gm) Р(g + Gu m) ,(2)g=0 m=0где YIu (g + Gu m) - вероятность того, что m-й блок ОЗУ, отображаемый на g-югруппу кэша, находится в кэше. Тогда среднее время доступа к адресуемым объектам многоуровневой памяти блокирующего типа [3]U и-1Tu (Ki , K2, Ku ) = X KuПR ,(3)u=1 i=1где Rt = l - Ylt - вероятность промаха в кэш уровня i. Операционная характеристика «среднее время доступа» позволяет оценивать эффективность работы подсистемы памяти в целом. Чем меньше среднее время, тем лучше работает многоуровневая память.2. Вероятность попадания в кэшОдна из основных проблем получения вероятностей попадания в кэши различных уровней состоит в построении по одному известному распределению востребованности блоков ОЗУ вычислителем (1) отображений элементов ОЗУ в группу кэша каждого уровня [4]. Поскольку механизм идеального вытеснения обладает свойством концентрации в А-1 блоках каждой группы кэша самых востребованных вычислителем блоков памяти, то без ограничения общности можно считать, что вероятности востребованности блоков памяти, отображаемых на каждую группу кэша первого уровня, упорядочены по убыванию:р(g + G1i) > р(g + GJ), i < j; i, j = 0, Mi -1, Vg = 0, Gi -1.Для выполнения сравнительного анализа вероятностей попадания в кэши различных уровней иерархической памяти необходимо по заданному отображению распределения востребованности блоков ОЗУ центральным процессором на один из кэшей (кэш первого уровня) получить отображения на кэши других уровней.В случае, когда количество групп в кэше u-го уровня кратно количеству групп в кэше первого уровня, то естьGu = eu ■ G{, eu - натуральное число ,(4)последовательность блоков ОЗУ, отображаемых на g-ю группу кэша первого уровняg + G1m1, g = 0, Gi -1, mi = 0, Mi -1,отображается на eu групп кэша уровня u:g + Gin + Gumu, g = 0, Gi -1,Видно, что при (4) последовательность блоков памяти, отображаемых на группу кэша уровня u, также упорядочена по убыванию. Так как процесс накопления блоков в кэше рассматривается независимо от кэшей других уровней, то вероятность попадания блока из основной памяти в идеальный кэш уровня u [2]\ 1,m = 0, Д, - 2,P(g + Gu m)-, m = Au-1, Mu-1.Tlu (g + Gu m) = |E Pg + Gu i)Соответственно, исходя из общей зависимости (2), вероятность попадания в кэш первого уровня составитП = ЕЕ П1 (g + Gl«) />(g + Gim) =Г= ЕAj-2Е p g+Gim)+Mj-1Е pg+G1m)(5)а вероятность попадания в кэш уровня u имеет вид'M„-1Е П2(g + Gin + euGim) ■ p(g + Gin + euGim)m=0Е [ (g + Gin + eu Gim)fAu-2Е p( g+Gin+euGim)+Mu-iЕ p (g+Gin+euGim)m=Au-i1(6)Для упрощения вычислений можно ввести верхнюю П и нижнюю П оценки вероятности попадания в кэш уровня u:Верхняя и нижняя оценки вероятности попадания в кэш первого уровня определяются на основе (5) следующими зависимостями:Gi -14-1G,-1й. = ЕЕ рg+Gim) ,m=0 _A,-2Е Р(g + Gm) + р(g + G(И. -1). m=0(7) (8)Верхняя и нижняя оценки вероятности попадания в кэш уровня u определяются из (6) соотношениямиGi-i eu-1fi „ = ЕЕg=0 и=0о,-1 e„-1a-1 ] Z P(S + Gin + euGim)n u = ZZg=0 n=0Е Pg + G1n + eu G1m) + P(g + G1n + eu G1 \- -1m=0V eu(9) (10)3. Анализ вероятности попадания в кэш при усеченном геометрическом распределении востребованости блоков памяти вычислителемДля простоты предположим, что вероятность востребованности m-го блока основной памяти, отображаемой на группу кэша первого уровня, не зависит от номера группы:p(g + Gxm) = p (h + Gxm), Vg, h = 0, Gx -1, m = 0, Mx -1. Полагаем, что вероятности востребованности блоков основной памяти определены на интервале m = 0, aAx -1 и убывают с ростом m по усеченному геометрическому закону (заданному на конечной области определения):p(g + Gxm) = р(g) ■ qm, g = 0, Gx -1.Здесь - G1 -1,p( g )■m=0 G1G\ ■ (1 - qMl )Тогда вероятность попадания в кэш первого уровня будет вычисляться из (5) по формуле(1 + q)-(-q 1 ) а вероятность попадания в кэш уровня u1 + qe" - 2qe"A + q^1 (l - qe" )Пи =, «Wl a^1,0 < q < 1 .(12)В случае равномерного распределения (q = 1) вероятности попадания в кэш первого и u-го уровней выражаются из (5), (6) следующими соотношениями:П- 1 П- e"A V"aA1 aV1где V,, i = 1,2 - емкость кэша i-го уровня. Верхняя и нижняя оценки вероятности попадания в кэш первого уровня, вычисленные из (7) и (8) с использованием формулы суммы геометрической последовательности, равны соответственноП = 1 - qA П = 1 - qA - + (1 - q) qaA- .1 - q1 - qВерхняя и нижняя оценки вероятности попадания в кэш уровня и, найденные по формуле (9), (10), определятся следующими зависимостями:1 _ qe„A,1 - qe»(A-1) + (1 - qe» ) qaAl~e»1 _ q 11 - q 1В случае, когда коэффициенты ассоциативности в кэше первого и второго уровней совпадают (Ax = A2 = A), соотношения (11) и (12) для нахождения вероятности попадания упрощаются:1 + q - 2qA + qaA (1 - q) _= 1 + qe - 2qeA + qaA (l - qe ) 1 = (1 + q ) (1 - qaA ) ; 2 = (1 + qe )■ (l - q°A )При равном количестве групп в кэшах первого и второго уровней (е=1) функциональные зависимости (11) и (12) принимают видп= 1 + q - 2qÄA + qaÄA (1 - q) R= 1 + q - 2qA- + qaÄA (1 - q)1(1 + q)-(l-q^) 2(1 + q)-(l-q^) 'В случае, когда кэш первого уровня является кэшем прямого отображения (Ax = 1) из (11) и (12), получаемп= (1-q)■(! + qa) п= 1 + ge -2qeA2 + ga(1 -qe)1 (1 + q) (1 -qa у 2(1 + q). (l-qa) 'Если при этом кэш второго уровня также является кэшем прямого отображения (A2 = 1), то выражение для вероятности попадания в кэш второго уровня преобразуется к следующему виду:(1 - qe ) (1 + qa )П 2(1 + qe - qa )'Вид зависимости вероятностей попадания в кэши первого и второго уровней, а также их оценки от параметра усеченного геометрического распределения q представлены на рис. 2. Здесь У\ = 16, V2 = 32, ¥0зу = 64. A\ = 2, A2 = 4, a = 4, e = 1. Видно, что оценки П и П наиболее точно представляют вероятность попадания П при q близком к единице (равномерное распределение) и при q, близком к нулю (вся вероятностная масса сосредоточена в одном блоке каждой группы). Рис. 3 и 4 иллюстрируют эффект от добавления кэша второго уровня к двухуровневой подсистеме памяти с параметрами Vi = 16, Ai = 16 (полностью ассоциативный кэш), Vo3y = 128, a = 8. Объем добавляемого кэша V2 = 64, коэффициент e вычисляется0из соотношения (4). На рис. 3 изображено п влияние параметра ассоциативности А2 на вероятность промаха в кэш второго уровня R2 при различных параметрах усеченного геометрического распределения q. Видно, что при увеличении параметра ассоциативности вероятность промаха снижается, однако при равномерном распределении (q = 1) вероятность промаха не зависит от коэффициента ассоциативности. Характерная зависимость вероятности промаха в кэш от параметра усеченного геометрического распределения q при различных коэффициентах ассоциативности кэша второго уровня A2 приведена на рис. 4. Видно, что полностью ассоциативный кэш (A2 = V2) обладает наиболее низкой, а кэш прямого отображения (A2 = 1) - наиболее высокой вероятностью промаха на всем диапазоне изменения параметра q.R20,8 0,6 0,4 0,2 0-О- Ш2),q --°- RiiA2),q -^ R(A2),q =-О- Ä2(A),q -0,93 0,95 0,97 0,99 1R0,75 0,50 0,250Ä2(9), A= 10,90 0,92 0,94 0,96 0,984. Сравнительный анализ подсистем памяти с двумя и тремя уровнямиПолагаем, что среднее время доступа к адресуемым объектам многоуровневой памяти определяется выражением (3). Предположим, что в подсистему иерархической памяти добавляется еще один уровень памяти перед уровнем с номером а. Пусть время доступа к добавляемому уровню памяти - K*, а вероятность промаха - R*. Естественно, что параметры добавляемого уровня памяти должны соответствовать логике построения многоуровневой памяти: кэш более высокого уровня характеризуется большим временем доступа и меньшей вероятностью промаха:Ra-l ^ R ^ Ra .Целесообразность добавления уровня памяти в существующую систему перед уровнем с номером a выражается неравенствомAT(a) = Tu (К,,Ku ) - TU+ (Kj,Ka_x, К*, KaKv ) > 0 .Здесь TU"] (KjKa-j,К*,KaКи) - среднее время доступа к подсистеме памяти с дополнительно введенным на а-м уровне кэшем. Подставляя в это неравенство соотношение (3), после приведения подобных получимfy * Z Ku П R.1u=a i=aОтсюда следует, что добавление еще одного уровня памяти в иерархию перед уровнем с номером a целесообразно, если отношение скорости обращения к добавляемому уровню памяти к вероятности попадания в добавляемый уровень памяти меньше среднего времени доступа к уровням памяти более высокого уровня. Для удобства последнее выражение можно переписать в видеf U u-1 ЛI U u-1к* 0 ..Kl*Отсюда получаем < Kj + Я1КОЗУ ,1 - R*K* < (1 -R*) (Kj + RjKo3y) или (1 -R*)> К* .Kl + R1K03yЦелесообразность добавления кэша второго уровня к исходной подсистеме памяти задается условиемAT(2) = T2 (Kj, Козу ) - T(2) (Kj, K*, K03Y) > 0, которое приводит к неравенствам:1 - R* ОЗУ K* < (1 - R*) КОЗУ или (1 - R*) > K* / КОЗУ . Рис. 5 иллюстрирует в пространстве быстродействия и вероятности промаха в кэш добавляемого уровня области целесообразности добавления кэша к двухуровневой подсистеме памяти с параметрами: Ri = 0,5, K\ = 8, КОЗу = 64. Область 0 < R* < R1 соответствует добавлению уровня между центральным процессором и существующим кэшем (добавление кэша первого уровня), а область Rj < R* < 1 -добавлению кэша между существующим кэшем и ОЗУ (добавление кэша второго уровня). Рис. 6 - 8 показывают эффект от добавления кэша второго уровня к двухуровневой системе памяти с параметрами: V1 = 128, V03y = 512 (а = 4), К1 = 8, К0ЗУ = 64 при равномерном распределении востребованности блоков ОЗУ вычислителем. На рис. 6 изображена зависимость среднего времени доступа от времени обращения к добавляемому кэшу К*. Горизонтальная линия соответствует среднему времени доступа к исходной двухуровневой памяти. Видно, что чем больше объем добавляемого кэша, тем шире диапазон значений К*, при которых трехуровневая память имеет меньшее среднее время доступа. Рис. 7 иллюстрирует влияние объема добавляемого кэша на среднее время доступа к модифицированной подсистеме памяти. Горизонтальная линия соответствует среднему времени доступа к исходной подсистеме памяти. Видно, что чем меньше время обращения к добавляемому кэшу, тем шире диапазон объемов добавляемого кэша V*, при которых имеет смысл использовать трехуровневую память вместо двухуровневой. Наконец, рис. 8 представляет область целесообразности добавления кэша с объемом V* и временем доступа К*.Рис. 9 и 10 показывают эффект от добавления кэша второго уровня к двухуровневой подсистеме памяти при усеченном геометрическом распределении востребованности блоков ОЗУ вычислителем. Исходная подсистема памяти характеризуется параметрами: V1 = 16, V03y = 64 (а = 4); A1 = 2, К1 = 8, К0ЗУ = 64. Добавляемый кэш имеет объем V2 = 32 и ассоциативность А2 = 2. На рис. 9 приведен график среднего времени доступа исходной (T2) и модифицированной (T3(2)) подсистем памяти от параметра усеченного геометрического распределения q при различных временах доступа к добавляемому кэшу К2. Рис. 10 показывает выигрыш от добавления кэша при заданном параметре q и различных временах обращения к добавляемому кэшу К2.AT (2)(q), K=K=8 ЛAT (2)(q), K=32AT (2)(q), K=48- AT (2)(q), K=K03y=640,00,00,20,40,60,8Рис. 10. Выигрыш от добавления кэша второго уровня с различными временами обращения K2ЗаключениеВ результате проведенного исследования предложена модель многоуровневой памяти. Найдены аналитические зависимости для вычисления вероятности попадания в кэш каждого уровня в случае, когда количество групп каждого кэша кратно количеству групп кэша первого уровня. Найдены аналитические зависимости для вычисления вероятности попадания в кэш заданного уровня для усеченного геометрического распределения востребованности блоков ОЗУ вычислителем. Проведен сравнительный анализ функционирования двухуровневой и трехуровневой памяти. Выявлено влияние архитектурных параметров кэша и типа решаемой на вычислительной системе смеси задач на эффективность работы подсистемы памяти в целом.

Скачать электронную версию публикации