Содержание к диссертации
Введение
1. Проблемы построения эффективной памяти вычислительных систем 10
1.1. Архитектура многоуровневой памяти 10
1.2. Типы кэш-памяти 15
1.3. Анализ моделей многоуровневой памяти 19
1.4. Выводы о направлениях работ 27
2. Анализ производительности двухуровневой памяти 30
2.1. Модель двухуровневой памяти 30
2.1.1. Описание модели 30
2.1.2. Операционные характеристики подсистемы памяти 32
2.1.3. Идеальная модель вытеснения блоков 34
2.1.4. Геометрическое распределение востребованности блоков памяти 36
2.2. Влияние размера блока на вероятность попадания в кэш 40
2.2.1. Полностью ассоциативный кэш 41
2.2.2. Множественный ассоциативный кэш 47
2.3. Влияние размера блока на среднее время доступа 53
2.4. Выводы 59
3. Исследование эффективности многоуровневои памяти 60
3.1. Описание модели многоуровневой памяти 60
3.2. Операционные характеристики многоуровневой памяти 61
3.2.1. Вероятность попадания в кэш заданного уровня 61
3.2.2 Среднее время доступа 66
3.3. Анализ влияния коэффициента ассоциативности на производительность подсистемы памяти 68
3.4. Выбор оптимального количества уровней памяти 74
3.5. Выводы 80
4. Подсистема памяти многопроцессорного вычислителя 82
4.1. Описание модели 82
4.2. Вычисление вероятностей состояний 86
4.2.1. Однопроцессорная вычислительная система 87
4.2.2. Двухпроцессорная вычислительная система 88
4.2.3. Трехпроцессорная вычислительная система 94
4.2.4. Четырехпроцессорная вычислительная система 97
4.2.5. Численный расчет вероятностей состояний подсистемы памяти многопроцессорного вычислителя 98
4.3. Операционные характеристики 99
4.4. Влияние параметров подсистемы памяти на ее производительность 103
4.5. Методика определения распределения востребованности блоков памяти вычислителем 115
4.5.1. Сбор статистики обращения процессора к памяти 116
4.5.2. Описание эксперимента 118
4.5.3. Вычисление процента промаха в кэш 121
4.6. Выводы 124
Заключение 127
Литература 129
- Анализ моделей многоуровневой памяти
- Влияние размера блока на вероятность попадания в кэш
- Операционные характеристики многоуровневой памяти
- Численный расчет вероятностей состояний подсистемы памяти многопроцессорного вычислителя
Введение к работе
В настоящее время практически во всех вычислительных системах используется многоуровневая память. Дело в том, что на протяжении последних десятилетий скорость работы памяти растет значительно более низкими темпами по сравнению со скоростью обработки данных в центральном процессоре. Известно, что основные требования к памяти (достаточно большая емкость, высокая скорость и экономическая эффективность) невозможно удовлетворить в одном устройстве, поэтому обычно комбинируют несколько запоминающих устройств с различными параметрами, добиваясь создания комплексного решения с требуемыми характеристиками.
С широким распространением многопроцессорных систем с общей памятью, а также с появлением многоядерных процессоров, позволяющих выполнять несколько независимых потоков команд, нагрузка на подсистему памяти существенно возрастает [51, 52, 55, 57, 58, ПО]. При построении высокопроизводительных вычислителей задача построения эффективной подсистемы памяти принимает особое значение, так как реальная производительность многих систем значительно ниже пиковой, в частности, из-за неоптимальной организации работы с памятью [71, 72, 109, 111, 112].
Эффективность доступа к многоуровневой памяти определяется не только быстродействием и емкостью отдельных уровней подсистемы памяти, но и набором архитектурных параметров, таких как: размер интерфейсного блока, коэффициент ассоциативности (определяет способ накопления блоков основной памяти в кэше) и коэффициент неблокируемости кэш-памяти (определяет степень параллелизма при выполнении операций доступа к различным уровням памяти).
Фундаментальные исследования по организации высокопроизводительных вычислительных систем провели российские и зарубежные ученые, среди них: Б.А. Бабаян, Е.П. Балашов, B.C. Бурцев, В.В. Воеводин, В.М. Глушков, Э.В. Евреинов, А.В. Забродин, А.В. Каляев, С.А. Лебедев, И.В. Прангишвили, Д.В. Пузанков, В.Г. Хорошевский, Н.Н. Яненко, A. Agarwal, S. Cray, М. Flynn, J.L. Hennessy, D.A. Patterson, и другие [1,2, 20, 22, 30, 31, 70, 104, 119, 121, 129]. Основные классические результаты по исследованию и моделированию многоуровневой памяти получили Т. Кохонен, Э. Та-ненбаум, К. Хамахер, 3. Вранешич, С. Заки, А. Пом, Ю. Лускинд. Новейшие исследования по организации современных вычислительных систем изложены в работах М. Кузьминского, Л. Черняка, В.З. Шнитмана. Однако известные модели многоуровневой памяти не учитывают в явном виде влияние архитектурных параметров памяти на ее операционные характеристики.
В связи со значительным влиянием производительности подсистемы памяти на общую производительность вычислителя, работы по совершенствованию архитектуры памяти приобретают особую актуальность.
Целью настоящей работы является разработка методики выбора архитектурных параметров подсистемы памяти, обеспечивающих повышение ее производительности для заданного класса решаемых задач. Для достижения данной цели необходимо решить следующие задачи:
построить и исследовать модели многоуровневой памяти;
разработать способы расчета операционных характеристик памяти;
получить методику оптимизации архитектуры многоуровневой памяти.
Методы исследования. При выполнении диссертационной работы использовались методы теории вероятностей, теории массового обслуживания, теории марковских цепей, а также теории вычислительных систем.
Научная новизна определяется следующими положениями:
Разработана модель функционирования двухуровневой памяти, отличающаяся учетом архитектурных параметров (коэффициент ассоциативности, размер межуровневого интерфейсного блока) и выполняемых вычислителем задач, позволяющая повысить точность вычисления операционных характеристик памяти.
Разработана конвейерная модель двухуровневой памяти симметричной многопроцессорной системы, отличающаяся учетом коэффициента неблокируемости кэша и количества процессоров, позволяющая вычислять операционные характеристики памяти.
Предложена методика аналитического расчета вероятностей попадания в кэши многоуровневой памяти, отличающаяся необходимостью задания отображения распределения востребованности блоков памяти только в кэш первого уровня и позволяющая оптимизировать число уровней памяти.
Теоретическая значимость. На основе предложенных моделей многоуровневой памяти получены явные аналитические зависимости для вычисления операционных характеристик памяти по заданным архитектурным параметрам и заданному распределению востребованности блоков основной памяти.
Предложенные модели могут быть использованы для построения математических моделей подсистемы памяти вычислителей с распределённой памятью.
Практическая ценность. Предложенная методика может быть использована для проектирования эффективных подсистем памяти, а также для оценки производительности и сравнительного анализа существующих систем. Разработанное в рамках диссертационной работы программное обеспечение позволяет численно оценивать и оптимизировать производительность подсистемы памяти симметричных многопроцессорных систем, а также получать частоты обращений к блокам памяти при выполнении прикладных программ.
Внедрение результатов работы. Материалы настоящего исследования используются в учебном процессе при чтении спецкурсов лекций «Архитектура вычислительных систем и компьютерных сетей», «Принципы организации многопроцессорных комплексов» на факультете информатики Томского государственного университета.
Результаты диссертационной работы используются в ООО «Триаксес Вижн» для оптимизации аппаратно-программных комплексов обработки графических изображений и видео-потоков.
Положения, выносимые на защиту
Модель двухуровневой памяти однопроцессорной вычислительной системы, явно учитывающая коэффициент ассоциативности кэша и размер интерфейсного блока.
Конвейерная модель двухуровневой памяти симметричной многопроцессорной системы, явно учитывающая коэффициент неблокируе-мости кэша.
Методика расчета операционных характеристик и оптимизации количества уровней подсистемы памяти при заданном классе выполняемых на вычислительной системе прикладных задач.
Апробация работы и публикации. По результатам выполненных исследований опубликовано 10 печатных работ, в том числе 2
публикации в журналах из списка ВАК. Основные результаты диссертационной работы докладывались и обсуждались на следующих научно-технических форумах:
V Всероссийской конференции «Наука и образование» (Томск, 2001);
П-ой Международной конференции молодых ученых и аспирантов «Актуальные проблемы современной науки» (Самара, 2001);
XLI Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2003);
Всероссийской конференции «Наука и практика: диалоги нового века» (Анжеро-Судженск, 2003);
III Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» (Анжеро-Судженск, 2004);
XI Всероссийской научно-практической конференции «Научное творчество молодежи» (Анжеро-Судженск, 2007);
IV-ой Сибирской школе-семинаре по параллельным и высокопроизводительным вычислениям (Томск, 2007).
Личный вклад. Основные научные результаты получены автором самостоятельно. Постановка задачи была выполнена автором совместно с научным руководителем. Разработка программ для расчета операционных характеристик многоуровневой памяти была произведена автором единолично.
Структура диссертации. Работа состоит из введения, четырех глав, заключения, списка литературы. Проведенный в первой главе аналитический обзор проблем построения многоуровневой памяти и результатов, достигнутых в моделировании различных архитектур,
позволил установить основные направления исследований. Выявленные направления развиваются в следующих трех главах.
Во второй главе исследовано влияние размера блока памяти и коэффициента ассоциативности кэша на вероятность промаха в кэш и среднее время доступа. Результаты этой главы опубликованы в работах автора [8, 9, 13].
В третьей главе предложен способ построения распределения востребованности блоков памяти для каждого уровня памяти по одному заданному распределению востребованности блоков памяти для кэша первого уровня. Это позволяет проводить исследование эффективности подсистемы памяти с количеством уровней более двух. В параграфе 3.4 изучается вопрос определения оптимального количества уровней памяти. Результаты этой главы опубликованы в работах автора [6,7, 11, 14].
В четвертой главе построены конвейерные модели двухуровневой памяти, позволяющие исследовать влияние коэффициента небло-кируемости кэша и количества процессоров на операционные характеристики подсистемы памяти симметричного многопроцессорного вычислителя. В параграфе 4.5 предлагается методика, позволяющая получить частоты обращений к блокам памяти при выполнении заданной прикладной программы. Материалы данной главы изложены в работах автора [10, 12, 15].
Автор выражает глубокую благодарность научному руководителю профессору Сергею Петровичу Сущенко за постоянное внимание и помощь в работе над диссертацией.
Анализ моделей многоуровневой памяти
Кэш-память используется еще со времен «больших» вычислительных машин серии IBM 360/85 и первых мини-ЭВМ DEC PDP-11 для согласования скоростей работы процессора и основной памяти [32, 40, 39, 68]. Исследования в области кэш-систем начались в конце 60-х - начале 70-х годов.
В работе Мида [63], пожалуй, впервые были подробно рассмотрены вопросы построения кэш-систем. В работе [61] проведен подробный обзор основополагающих концепций кэш-памяти, которые не утратили свою актуальность и по сей день. Используются следующие операционные характеристики кэш-памяти: вероятность удачного обращения (или вероятность попадания — hit rate), вероятность неудачного обращения (или вероятность промаха miss rate), среднее время доступа к памяти. Отмечены качественные закономерности влияния архитектурных (тип кэша - ПАК, МАК, КПО, размера блока) и временных параметров кэш-памяти на операционные характеристики. Дополнительно, обращается внимание на сложность построения оптимальной кэш-памяти и приводится высказывание эксперта Тома Гудмена «... мнений о том, как следует строить кэш-память, имеется ровно столько, сколько существует разработчиков вычислительных систем».
Исследователи выделяют следующие факторы, влияющие на вероятность попадания в кэш: 1) объем кэш-памяти, 2) размер блока кэша, 3) алгоритм выборки информации, 4) стратегия вытеснения блоков из группы кэша, 5) тип задач, для которых предназначена вычислительная система [16, 21, 22, 61, 62, 66, 68, 92, 93, 94, 100, 139, 151].
Цель и способы исследования. Основной целью исследования подсистемы памяти является обнаружение функциональных и численных зависимостей между параметрами памяти различных уровней и операционными характеристиками вычислительной системы. При этом необходимо выделить самые существенные факторы, определяющие данные зависимости, так как преувеличенно точное детальное описание процессов функционирования вычислителя часто мало способствует достижению цели (получению общих закономерностей), а чрезмерно необоснованное упрощение слишком идеализирует реальные процессы.
Для понимания узких мест и механизма влияния основных факторов на быстродействие вычислительной системы наиболее эффективным инструментов является аналитическое моделирование вычислительных процессов, позволяющее наглядно увидеть достоинства и недостатки различных архитектур [16]. Аналитические модели обычно представляют собой набор уравнений, связывающих показатели производительности с параметрами системы. Однако формализация вычислительных процессов (особенно допускающая аналитическое решение) часто предусматривает их идеализацию, после чего возникает вопрос адекватности аналитической модели реальной системе и проблема интерпретации полученных результатов. Поэтому наряду с аналитическими методами [4, 16, 29, 97, 98] широко применяется имитационное моделирование [16, 18, 128, 130, 133, 134, 140] и методы тестирования вычислительных систем [23, 101, 103, 132, 147, 148], позволяющие исследовать трудно формализуемые при аналитическом моделировании элементы вычислительного процесса.
Пожалуй, наиболее распространенным в настоящее время является экспериментальный метод (или метод тестирования) при исследовании эффективности многоуровневой памяти. Предлагается некоторый набор тестовых программ [23, 103], и из факта повышения производительности кэша при выполнении выбранного ограниченного набора приложений делается вывод о позитивном или негативном влиянии того или иного архитектурно-временного параметра на эффективность подсистемы памяти. Методы тестирования также часто используются для выявления уровня локализации тех или иных приложений в вычислительных системах с заданной архитектурой подсистемы памяти. Заметим, что экспериментальный метод исследования позволяет исследовать лишь существующие на рынке технические решения и не годится при проектировании новых вычислительных систем.
Модели двухуровневой памяти. Известные исследования быстродействия подсистемы памяти основаны на модели двухуровневой памяти «кэш — оперативная память» [16, 17, 19, 35, 40, 61, 68, 73, 74, 76, 80, 82, 86, 87, 89, 100, 139]. В рамках такой модели при заданном типе распределения прикладных задач в оперативной памяти вычис лительной системы обычно анализируется вероятность попадания в кэш и среднее время доступа к многоуровневой памяти, а также скорость обновления содержимого кэша при переключениях вычислителя на выполнение нового приложения (скорость движения к стационарному состоянию) [73, 74, 138, 144].
Анализ факторов, определяющих долю обращений за блоками информации, удовлетворяемых на уровне кэша, выполнен в [16, 40, 138, 142, 143, 149, 150, 151].
В работах [16, 17, 19, 61, 68, 73, 100] получены асимптотические соотношения и численные зависимости операционных показателей эффективности подсистемы памяти от объема кэш-памяти, коэффициента ассоциативности, размера блока данных. Из проведенного анализа следует, что рост ассоциативности позволяет снизить отрицательный эффект от явления конфликта адресов одинаково востребованных вычислителем блоков памяти, отображаемых на одну группу кэша. Характерная зависимость вероятности попадания в кэш от коэффициента ассоциативности определяется монотонно возрастающей функцией, а от объема кэш-памяти имеет вид кривой с насыщением. Однако общий аналитический вид операционных характеристик не получен.
Влияние стратегий вытеснения кэш-строк при конфликте адресов обсуждается в [3, 16, 19, 60, 61, 68, 73, 74, 94, 100, 126, 139, 140]. Отмечается, что наилучшей среди реализуемых стратегий является стратегия вытеснения LRU (Least Recently Used) или ее модификация -стратегия накопления MFU (Most Frequently Used) [140].
Влияние размера блока на вероятность попадания в кэш
Вероятность попадания в кэш при максимальном увеличении размера блока (п=А) составит: Разность между вероятностью попадания при наименьшем и наибольшем размере блока составляет: Производное распределение приближает исходное распределение к равномерному закону. На рис 2.7 изображена схема объединения исходных блоков в новый супер-блок. Сверху — блоки исходной длины / (в прямоугольниках указаны диапазоны блоков), снизу - укрупненные блоки длины 2к1. Тогда вероятность востребованности нового укрупненного блока размера пі (п=2к— четное число) может быть вычислена через вероятности востребованности блоков исходного кэша следующим образом: Подставляя в данное соотношение вместо р, выражение (2.11) и используя формулы суммы геометрического ряда получаем:
При усеченном геометрическом распределении зависимость для вычисления вероятности попадания в кэш принимает вид: На рис. 2.8 представлены зависимости вероятности попадания в полностью ассоциативный кэш от параметра геометрического распределения q при различных размерах блока (от / до А1, А=8) и различных способах объединения исходных блоков группы кэша в новый укрупненный блок (случаи 1а, 16).
Видно, что в случае 1а (объединение соседних по вероятности востребованности блоков) приводит к лучшим показателям вероятности попадания. Случай 16 (объединение максимально далеких по вероятности востребованности блоков) приводит к более низким значениям вероятности попадания на всем диапазоне изменения параметра q. Следует ожидать, что реальное значение вероятности промаха при увеличении размера блока до 2к1, п=2к и геометрическом распределении востребованности блоков с параметром q будет варьироваться между величинами П ., и П)". Рис. 2.9 иллюстрирует падение вероятности попадания в кэш при максимальном увеличении размера блока (в А раз) при различных способах объединения блоков (случаи 1а, 16). Видно, что при крайних значениях параметра q (q = Q и q = \) вероятность попадания не зависит от размера блока. Случай 1а характеризуется меньшим падением вероятности попадания, по сравнению со случаем 16. Функция разности между максимальной П,1,0 и минимальной 1 вероятностью попадания от параметра геометрического распределения q при различных размерах блока приведена на рис. 2.10.
Операционные характеристики многоуровневой памяти
Одна из основных проблем получения вероятностей попадания в кэши различных уровней состоит в построении по одному известному распределению востребованности блоков основной памяти вычислителем (2.1) отображений элементов основной памяти в группу кэша каждого уровня [6, 11].
Для выполнения сравнительного анализа вероятностей попадания в кэши различных уровней памяти необходимо по заданному отображению распределения востребованности блоков основной памяти центральным процессором на один из кэшей (например, на кэш первого уровня) получить отображения на кэши других уровней. В случае, когда количество групп в кэше и-го уровня кратно количеству групп в кэше первого уровня, то есть последовательность блоков основной памяти, отображаемых на g-ю группу кэша первого уровня g + Gxmx, g = 0, G,-l, тх=0, Mx-l отображается на eu групп кэша уровня и: что при (3.3) последовательность блоков памяти, отображаемых на группу кэша уровня и, также упорядочена по убыванию. Так как процесс накопления блоков в кэше рассматривается независимо от кэшей других уровней, то вероятность попадания блока из основной памяти в кэш уровня и равна [74]:
Соответственно, исходя из общей зависимости (3.2), вероятность попадания в кэш первого уровня составит:
Для упрощения вычислений можно аналогично (2.7), (2.8) ввести верхнюю Пи и нижнюю П„ оценки вероятности попадания в кэш уровня u:tlu П„ ПЦ Верхняя и нижняя оценки вероятности попадания в кэш первого уровня определяются на основе (3.4) следующими зависимостями:
Рассмотрим усеченное геометрическое распределение востребованности блоков памяти вычислителем (2.11). Тогда вероятность попадания в кэш первого уровня будет вычисляться из (3.4) по формуле: а вероятность попадания в кэш уровня и 1 вычисляется из (3.5):
В случае равномерного распределения (q = і) вероятности попадания в кэш первого и и-го уровня выражаются из (3.4), (3.5) следующими соотношениями: где , /=1,2 - емкость кэша /-го уровня.
Верхняя и нижняя оценки вероятности попадания в кэш первого уровня, вычисленные из (3.6), (3.7) с использованием формулы суммы геометрической прогрессии, равны соответственно:
Верхняя и нижняя оценки вероятности попадания в кэш уровня и, найденные по формуле (3.8), (3.9), определятся следующими зависимостями:
В случае, когда коэффициенты ассоциативности в кэше первого и второго уровня трехуровневой подсистемы памяти совпадают (АХ=А2= А), соотношения (3.10), (3.11) для нахождения вероятности попадания упрощаются:
При равном количестве групп в кэшах первого и второго уровней (е = 1) функциональные зависимости (ЗЛО), (3.11) принимают вид:
В случае, когда кэш первого уровня является кэшем прямого отображения ( Ах = 1), из (3.10), (3.11) получаем:
Если при этом кэш второго уровня также является кэшем прямого отображения (Аг = 1), то выражение для вероятности попадания в кэш второго уровня преобразуется к следующему виду:
Отсюда видно, что при е = а П2 = 1, то есть приложение полностью локализуется в кэше второго уровня.
Численный расчет вероятностей состояний подсистемы памяти многопроцессорного вычислителя
Для вычисления вероятностей состояний систем с более высоким количеством процессоров М или коэффициентом неблокируемости N, или временем обращения к оперативной памяти К нахождение аналитического решения представляется достаточно трудоёмким. К тому же интерпретация громоздкого аналитического решения затруднена. Существуют два способа численного вычисления вероятностей состояний любых Марковских цепей: 1. Численное решение заключается в решении системы уравнений равновесия с учетом условия нормировки одним из известных численных методов решения систем линейных уравнений, например, методом Гаусса [105]. 2. Итерационное решение заключается в последовательном умножении вектора вероятностей состояний на матрицу переходов. Таким образом, после п таких умножений мы найдем вектор вероятностей состояний на n-том такте системы: где % - начальный вектор вероятностей состоянии, % - вектор вероятностей состояний системы после і-того такта, Р — матрица переходов цепи Маркова. Существует теорема, которая говорит о том, что для однородной, неприводимой и апериодической цепи Маркова всегда существует вектор 7с предельных вероятностей состояний, не зависящий от на чального вектора п вероятностей состоянии: Это означает, что итеративный процесс (4.11) обязательно сойдется независимо от выбора начального вектора состояний [33]. Именно этот подход используется в разработанном автором приложении SMPMemMark для численного вычисления вероятностей состояний системы.
Важнейшими операционными характеристиками многоуровневой подсистемы памяти являются: вероятность блокировки; среднее время выполнения запроса (транзакции доступа к памяти); пропускная способность. Вероятность блокировки. Операционная характеристика «Вероятность блокировки» показывает, как часто кэш т-тото процессора оказывается заблокированным. Вероятность блокировки кэш-памяти ш-того процессора определяется как сумма вероятностей состояний системы, в которых кэш /л-того процессора является заблокированным. Напомним, что блокировка КНТ происходит, когда количество обрабатываемых транзакций на втором этапе конвейера достигает значения коэффициента неблокируемости N, а выбор адресуемого элемента из оперативной памяти занимает К этапов. Тогда вероятность блокировки кэш-памяти m-того процессора может быть вычислена из вероятностей состояний системы следующим образом: Вероятность блокировки кэш-памяти всех процессоров может быть вычислена следующим образом:
Среднее время выполнения запроса. Операционная характеристика «Среднее время выполнения запроса» (или «Средняя задержка») показывает, сколько времени в среднем выполняется транзакция доступа к подсистеме памяти. При прочих равных условиях, чем меньшее время требуется для обработки отдельной транзакции, тем эффективнее функционирует подсистема памяти. При достаточно большой средней задержке возникают ощутимые простои процессора. Напомним, что транзакция от m-того процессора может быть успешно завершена уже на первом этапе конвейера при попадании к кэш (вероятность l-Rm). В таком случае, время выполнения транзакции будет равно времени обращения в кэш t. В случае промаха в кэш (вероятность Rm), время выполнения транзакции от т-того процессора складывается из времени разблокировки кэша ТЫоскт и времени обращения к оперативной памяти Taccessm : где т - среднее количество этапов обработки транзакций обращения т-того процессора к подсистеме памяти в фазе доступа к оперативной памяти, Ьт - среднее число этапов обслуживания, блокирующих доступ к кэш-памяти m-того процессора, а т - интенсивность потока, принятого к обслуживанию от m-того процессора. В общем случае величины т и Ат соответственно определяются следующими соотношениями
