WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     ||
|

Установлено, что увеличение размера блока не увеличивает вероятность попадания в кэш с произвольным коэффициентом ассоциативности на всем диапазоне изменения параметра q. При равномерном распределении вероятность попадания в кэш инвариантна к размеру блока.

1,0,n=n=2k=0,n=n=2k=n=0,n=2k=n=n=2k=0,n=0,случай 1б 0,случай 1а 0,0,0,0 0,2 0,4 0,6 0,8 1,q Рис. 1. Зависимость вероятности попадания в полностью ассоциативный кэш от параметра геометрического распределения q при увеличении размера блока в n раз Также выполнены численные исследования влияния размера блока на индексы быстродействия подсистемы памяти. Показано (рис. 3), что размер интерфейсного блока подсистемы памяти имеет оптимальное значение, минимизирующее показатель среднего удельного времени доступа (среднее время доступа к одному байту – вычисляется на основе выражения (2)).

1,0, - 2a 0,1a 1б 2б 0,0,0 0,2 0,4 0,6 0,8 1,q Рис. 2. Зависимость вероятности попадания в кэш от параметра геометрического распределения q при исходном (жирная линия) и вдвое увеличенном размере блока при различных способах объединения блоков 1b: q=0.85 q=0.9 q=0.1a: q=0.85 q=0.9 q=0.2 4 6 8 10 12 14 k Рис. 3. Зависимость удельного среднего времени доступа T от размера блока 2kl n при различных способах объединения блоков (случаи 1а и 1б) и различных параметрах геометрического распределения q (кэш полного отображения) В третьей главе вводится модель многоуровневой памяти с количеством уровней равным U 1. На каждом уровне u 1, U 1 кроме последнего, находится кэш; последний уровень u U занимает оперативная память. Количество блоков в оперативной памяти равно VU VОЗУ. Время выбора блока из оперативной памяти равно KU KОЗУ, а время поиска и выбора блока из кэша уровня u равно Ku.

T Кэш каждого уровня характеризуется объемом кэша в блоках Vu, коu личеством групп Gu, коэффициентом ассоциативности A V, коu Gu личеством блоков оперативной памяти, отображаемых на группу кэша u-го уровня M VОЗУ.

u Gu В общем случае соотношение для вычисления вероятности попадания в кэш уровня u с точностью до индексов аналогично соотношению для двухуровневой подсистемы памяти (1):

Gu 1 Mu (g Gum) p(g Gum), (7) u u g 0 mгде g Gum — вероятность того, что m-й блок оперативной па u мяти, отображаемый на g-ю группу кэша уровня u, находится в нем.

Среднее время доступа к блоку многоуровневой памяти T вычисляется по следующей формуле:

U u1 U u TU K1, K2,..., KU, (8) Ku 1 i Ku Ri u1 i1 u1 iгде Ri 1 i - вероятность промаха в кэш уровня i (7). В рамках рассматриваемой модели очевидно, что RU 0, U 1.

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

M p(g G1m) G11 Am A 1 p(g G1m) (9) Mmgp(g G1m) mA и в кэш уровня u:

Mu p g G1n euG1m G11 eu 1 Au m Au p(g G1n euG1m). (10) u Mu g0 n0 mp g G1n euG1m mAu В случае усеченного геометрического распределения востребованности блоков памяти вычислителем (5) на основе (9), (10) получены зависимости для вычисления вероятностей попадания в кэши различных уровней:

1 1 q 2qA qA 1 q 1, 0 q 1; (11) 1 q 1 qA u u 1 u 1 qe 2qe Au qA 1 qe, 0 q 1. (12) u u 1 qe 1 qA При равномерном распределении зависимости (11), (12) упрощаются:

1 e A V u u u 1 ;, где Vi, i=1,2 – емкость кэша i-го уровня.

u A1 VАнализ влияния коэффициента ассоциативности на производительность многоуровневой памяти показал, что его увеличение снижает среднее время доступа к многоуровневой памяти на всем диапазоне изменения параметра геометрического распределения q. (рис. 4).

A2=V2=A2=A2=A1=A1=A1=V1=0,0 0,2 0,4 0,6 0,8 1,q Рис. 4. Зависимость среднего времени доступа T трехуровневой памяти от параметра усеченного геометрического распределения q при различных значениях ассоциативности кэша первого и второго уровней: A1, A2.

Далее предложена методика выбора количества уровней иерархической памяти и получены условия целесообразности архитектурной реструктуризации подсистемы памяти. Предположим, что в исходную многоуровневую подсистему иерархической памяти (количество уровней — U) добавляется еще один уровень памяти перед уровнем с номером а. Пусть время доступа к добавляемому уровню памяT ти — K*, а вероятность промаха — R*. Тогда целесообразность добавления уровня памяти в существующую систему перед уровнем с номером a выражается неравенством:

(a) (a) T TU K1,..., KU TU 1 K1,..., K, K*, K,..., KU 0. (13) a1 a Здесь TU K1,..., KU - среднее время доступа к исходной подсис (a) теме памяти (8), а TU 1 K1,..., K, K*, K,..., KU – среднее время дос a1 a тупа к подсистеме памяти с дополнительно введенным на а-ом уровне кэшем. При подстановке и приведении подобных в выражение (13) получаем критерий целесообразности добавления уровня к подсистеме памяти:

K* U u. (14) K 1 R* ua uRi ia То есть добавление еще одного уровня памяти перед уровнем с номером a целесообразно, если отношение длительности обращения к добавляемому уровню памяти к вероятности попадания в добавляемый уровень памяти меньше среднего времени доступа к уровням памяти более высокого уровня (рис. 5).

K* область целесообразности добавления кэшаT(2)=Rобласть целесообразности добавления кэшаT(1)=KR* 0,0 0,2 0,4 0,6 0,8 1,Рис. 5. Области целесообразности добавления кэша первого и второго уровней к двухуровневой подсистеме памяти с параметрами R1=0,5; K1=8; KОЗУ=64.

Целесообразность добавления кэша к двухуровневой подсистеме памяти выражается на основе (14) следующими неравенствами:

K* K1 R1KОЗУ — при добавлении кэша первого уровня;

1 R* K* KОЗУ — при добавлении кэша второго уровня.

1 R* Рис. 6 показывает выигрыш (выраженный в разнице среднего времени доступа к исходной и измененной подсистеме памяти) от добавления кэша второго уровня к двухуровневой памяти при заданном параметре геометрического распределения q и различных временах обращения к добавляемому кэшу K2. Видно, что чем больше время обращения к добавляемому кэшу K2, тем уже диапазон изменения параметра q, при котором целесообразно добавлять дополнительный кэш (кривая выше оси ординат).

T(2) --T(2)(q), K2=K1=-15 T(2)(q), K2=T(2)(q), K2=-T(2)(q), K2=KОЗУ=q -0,0 0,2 0,4 0,6 0,8 1,Рис. 6. Выигрыш от добавления кэша второго уровня объемом V2=32 и ассоциативностью А2=2 с различными временами обращения K2 к двухуровневой подсистеме памяти с параметрами V1=16, VОЗУ=64 (=4); A1=2, K1 =8, KОЗУ=В четвертой главе исследовано влияние параметра глубины неблокируемости кэша на операционные характеристики подсистемы памяти многопроцессорной вычислительной системы.

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

Фаза доступа к основной памяти вычислителя описывается системой массового обслуживания с дискретным временем, многоэтап ным обслуживанием и конечным накопителем. Функционирование данной системы массового обслуживания в стационарном режиме задается цепью Маркова в M-мерном пространстве, где M – количество процессоров. Время между поступлениями заявок от m-того процессора (транзакций обращения к основной памяти) кратно t и имеет геометрическое распределение с параметром, равным вероятности промаха в кэш данного процессора R. Для завершения одной транзакции m оперативной памяти требуется выполнить K этапов.

Выделяются следующие параметры моделируемой подсистемы памяти: число процессоров в вычислительной системе (M); глубина неблокируемости кэша каждого процессора (N); время выбора элемента из оперативной памяти K (в тактах обращения к кэшу t); вектор вероятностей промаха R R1, R2,...RM, где R - вероятность промаха m в кэш m-го процессора.

Затем вычисляются вероятности состояний цепи Маркова, описывающей функционирование подсистемы памяти многопроцессорного вычислителя конвейерной моделью. Аналитически получены вероятности состояний марковских цепей, соответствующих некоторым подсистемам памяти вычислительных систем с количеством процессоров до четырех (коэффициент неблокируемости N=1, 2). Численно возможно вычислить вероятности состояний марковской цепи, соответствующей подсистеме памяти с произвольными значениями параметров M, N, K, R.

На рис. 7 приведена марковская цепь, соответствующая подсистеме памяти двухпроцессорного вычислителя (M=2) с параметрами:

N=2, K=2. Номер состояния состоит из двух чисел, каждое число – это количество этапов для обработки на второй фазе конвейера от соответствующего процессора. При увеличении значений параметров K, неблокируемости N, количества процессоров M количество состояний и сложность соответствующей марковской цепи стремительно растут.

В качестве операционных характеристик подсистемы памяти используются «среднее время доступа» и «пропускная способность»;

сформулированы способы их расчета на основе вероятностей состояний марковской цепи.

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

04 14 24 03 23 02 12 22 32 01 21 00 10 20 30 Рис. 7. Марковская цепь для подсистемы памяти двухпроцессорного вычислителя (M=2)с коэффициентом неблокируемости N=2 (K=2) Для вычисления операционных характеристик по предлагаемым моделям необходимо задать распределение вероятностей обращения вычислителя к блокам основной памяти. Далее предложен способ определения частот обращений к блокам памяти вычислителем (рис. 10), а также способ определения вероятности промаха при выполнении тес тового приложения в реальной вычислительной и программной среде с помощью разработанной автором утилиты MemMap.

4,3,3,2,N=N=T1 2,N=N=1,1,0,0,0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,1-RРис. 8. Влияние вероятности промаха в кэш R1 на среднюю задержку T1 при различных значениях коэффициента неблокируемости N (M=1, K=2) 1,0,N=N=C1 0,N=N=0,0,0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,1-RРис. 9. Влияние вероятности промаха в кэш R1 на пропускную способность Cпри различных значениях коэффициента неблокируемости N (M=1, K=2) Сравнительный анализ теоретически вычисленных и практически полученных вероятностей промаха в кэши различных уровней вычисли теля на основе процессора Intel Pentium M показал достаточную адекватность разработанных моделей и позволил обнаружить неучтенный в модели эффект предвыборки данных в кэш.

1,0E+1,0E+1,0E+1,0E+1,0E+1,0E+1,0E+1,0E+1 2049 4097 блок Рис. 10. Частоты обращений к блокам основной памяти при кодировании аудиофайла из формата WAV в формат MP3 (приложение Lame) ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ В диссертационной работе рассмотрены вопросы моделирования процесса доступа к адресуемым объектам вычислителя и разработки способов расчета операционных характеристик многоуровневой памяти.

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в периодических изданиях из списка ВАК для публикации результатов диссертаций:

1. Биматов Д.В., Сущенко М.С., Сущенко С.П. Моделирование разделяемой памяти двухпроцессорной вычислительной системы // Вестник Томского гос. ун-та, 2003, №280. — С. 319–323.

2. Биматов Д.В., Сущенко С.П. Об эффективности многоуровневой памяти вычислительной системы // Обозрение прикладной и промышленной математики, 2008, Т. 15, вып. 1. — С. 117–118.

Pages:     ||
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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