Математическое моделирование многоуровневой памяти вычислительных систем тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Биматов, Дмитрий Владимирович

• Биматов, Дмитрий Владимирович
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Биматов, Дмитрий Владимирович

ВВЕДЕНИЕ.

1. ПРОБЛЕМЫ ПОСТРОЕНИЯ ЭФФЕКТИВНОЙ ПАМЯТИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

1.1. Архитектура многоуровневой памяти.

1.2. Типы кэш-памяти.

1.3. Анализ моделей многоуровневой памяти.

1.4. Выводы о направлениях работ.

2. АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ ДВУХУРОВНЕВОЙ ПАМЯТИ.

2.1. Модель двухуровневой памяти.

2.1.1. Описание модели.

2.1.2. Операционные характеристики подсистемы памяти.

2.1.3. Идеальная модель вытеснения блоков.

2.1.4. Геометрическое распределение востребованности блоков памяти.

2.2. Влияние размера блока на вероятность попадания в кэш.

2.2.1. Полностью ассоциативный кэш.

2.2.2. Множественный ассоциативный кэш.

2.3. Влияние размера блока на среднее время доступа.

2.4. Выводы.

3. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МНОГОУРОВНЕВОЙ ПАМЯТИ.

3.1. Описание модели многоуровневой памяти.

3.2. Операционные характеристики многоуровневой памяти.

3.2.1. Вероятность попадания в кэш заданного уровня.

3.2.2 Среднее время доступа.

3.3. Анализ влияния коэффициента ассоциативности на производительность подсистемы памяти.

3.4. Выбор оптимального количества уровней памяти.

3.5. Выводы.

4. ПОДСИСТЕМА ПАМЯТИ МНОГОПРОЦЕССОРНОГО ВЫЧИСЛИТЕЛЯ.

4.1. Описание модели.

4.2. Вычисление вероятностей состояний.

4.2.1. Однопроцессорная вычислительная система.

4.2.2. Двухпроцессорная вычислительная система.

4.2.3. Трехпроцессорная вычислительная система.

4.2.4. Четырехпроцессорная вычислительная система.

4.2.5. Численный расчет вероятностей состояний подсистемы памяти многопроцессорного вычислителя.

4.3. Операционные характеристики.

4.4. Влияние параметров подсистемы памяти на ее производительность.

4.5. Методика определения распределения востребованности блоков памяти вычислителем.

4.5.1. Сбор статистики обращения процессора к памяти.

4.5.2. Описание эксперимента.

4.5.3. Вычисление процента промаха в кэш

4.6. Выводы.

Введение диссертации (часть автореферата) на тему «Математическое моделирование многоуровневой памяти вычислительных систем»

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

С широким распространением многопроцессорных систем с общей памятью, а также с появлением многоядерных процессоров, позволяющих выполнять несколько независимых потоков команд, нагрузка на подсистему памяти существенно возрастает [51, 52, 55, 57, 58, 110]. При построении высокопроизводительных вычислителей задача построения эффективной подсистемы памяти принимает особое значение, так как реальная производительность многих систем значительно ниже пиковой, в частности, из-за неоптимальной организации работы с памятью [71, 72, 109, 111, 112].

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

Фундаментальные исследования по организации высокопроизводительных вычислительных систем провели российские и зарубежные ученые, среди них: Б.А. Бабаян, Е.П. Балашов, B.C. Бурцев, В.В. Воеводин, В.М. Глушков, Э.В. Евреинов, А.В. Забродин,

A.В. Каляев, С.А. Лебедев, И.В. Прангишвили, Д.В. Пузанков,

B.Г. Хорошевский, Н.Н. Яненко, A. Agarwal, S. Cray, М. Flynn, J.L. Hennessy, D.A. Patterson, и другие [1,2, 20, 22, 30, 31, 70, 104, 119, 121, 129]. Основные классические результаты по исследованию и моделированию многоуровневой памяти получили Т. Кохонен, Э. Та-ненбаум, К. Хамахер, 3. Вранешич, С. Заки, А. Пом, Ю. Лускинд. Новейшие исследования по организации современных вычислительных систем изложены в работах М. Кузьминского, Л. Черняка, В.З. Шнитмана. Однако известные модели многоуровневой памяти не учитывают в явном виде влияние архитектурных параметров памяти на ее операционные характеристики.

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

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

1) построить и исследовать модели многоуровневой памяти;

2) разработать способы расчета операционных характеристик памяти;

3) получить методику оптимизации архитектуры многоуровневой памяти.

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

Научная новизна определяется следующими положениями:

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

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

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

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

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

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

Внедрение результатов работы. Материалы настоящего исследования используются в учебном процессе при чтении спецкурсов лекций «Архитектура вычислительных систем и компьютерных сетей», «Принципы организации многопроцессорных комплексов» на факультете информатики Томского государственного университета.

Результаты диссертационной работы используются в ООО «Триаксес Вижн» для оптимизации аппаратно-программных комплексов обработки графических изображений и видео-потоков.

Положения, выносимые на защиту

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

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

3. Методика расчета операционных характеристик и оптимизации количества уровней подсистемы памяти при заданном классе выполняемых на вычислительной системе прикладных задач.

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

• V Всероссийской конференции «Наука и образование» (Томск, 2001);

• П-ой Международной конференции молодых ученых и аспирантов «Актуальные проблемы современной науки» (Самара, 2001);

• XLI Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2003);

• Всероссийской конференции «Наука и практика: диалоги нового века» (Анжеро-Судженск, 2003);

• III Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» (Анжеро-Судженск, 2004);

• XI Всероссийской научно-практической конференции «Научное творчество молодежи» (Анжеро-Судженск, 2007);

• IV-ой Сибирской школе-семинаре по параллельным и высокопроизводительным вычислениям (Томск, 2007).

Личный вклад. Основные научные результаты получены автором самостоятельно. Постановка задачи была выполнена автором совместно с научным руководителем. Разработка программ для расчета операционных характеристик многоуровневой памяти была произведена автором единолично.

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Биматов, Дмитрий Владимирович

4.6. Выводы

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

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

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

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

ЗАКЛЮЧЕНИЕ

В диссертационной работе рассмотрены вопросы моделирования процесса доступа к адресуемым объектам вычислителя и разработки способов расчета операционных характеристик многоуровневой памяти.

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Биматов, Дмитрий Владимирович, 2009 год

1. Бабаян Б.А., Бочаров А.В., Волин А.С. Многопроцессорные ЭВМ и методы их проектирования. — М.: Высшая школа, 1990. — 143 с.

2. Балашов Е.П., Пузанков Д.В., Смолов В.Б. Микропроцессоры и микропроцессорные системы. — М.: Радио и связь, 1981. — 326 с.

3. БашаринГ.П., Богуславский Л.Б., Штейнберг В.И. Анализ конфликтов в общей памяти мультипроцессорных систем // Автоматика и вычислительная техника, 1980, №6. — С. 27-32.

4. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. — М.: Наука. Гл. ред. физ.-мат. лит., 1989.

5. Беркович С .Я., Кочин Ю.Я. Ассоциативная память. — М.: Знание, 1976.

6. Биматов Д.В. Моделирование трехуровневой подсистемы памяти // Материалы XI Всероссийской научно-практической конференции «Научное творчество молодежи», 4.1. — Томск: Изд-во Том. ун-та, 2007.—С. 61-64.

7. Биматов Д.В. О целесообразности изменения количества уровней в многоуровневой памяти // Материалы IV Сибирской школы-семинара по параллельным и высокопроизводительным вычислениям. — Томск, 2008.

8. Биматов Д.В., Севостьянов Д.В., Сущенко М.С., Сущенко С.П. Вероятностные модели кэша: анализ эффективности // Сборник трудов V Всероссийской конференции «Наука и образование». — Томск: Изд-во ТГПУ, 2001.

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

10. Биматов Д.В., Сущенко С.П. Анализ производительности многоуровневой подсистемы памяти // Вестник Томского гос. ун-та. Серия «Управление, вычислительная техника и информатика», 2007, № С. 92-100.

11. Биматов Д.В., Сущенко С.П. Моделирование современных высокопроизводительных вычислителей. // Материалы Всероссийской конференции «Наука и практика: диалоги нового века», Ч.З. — Томск: Изд-во Том. ун-та, 2003.

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

13. Богуславский JI.Б., Ляхов А.И. Методы оценки производительности многопроцессорных систем. — М.: Наука, 1992.

14. Богуславский JI.Б., Ляхов А.И., ШевчикК.С. Сравнительный анализ стратегий доступа с обратной связью в многопроцессорных системах // Автоматика и телемеханика, 1996, №5. — С. 160-176.

15. Брехов О.М., Слуцкин А.И. Имитационное моделирование иерархической памяти MB С // Автоматика и вычислительная техника, 1986, №1. —С. 48.

16. Брехов О.М., Слуцкин А.И. Исследование способов обеспечения идентичности информации в буферной памяти многопроцессорных вычислительных систем // Автоматика и телемеханика, 1988, №8.— С. 156-169.

17. Бурцев B.C. Параллелизм вычислительных процессов и развитие архитектур суперЭВМ. — М.: ИВВС РАН, 1997. — 352 с.

18. Вейцман К. Распределенные системы мини- и микро-ЭВМ. М.: Финансы и статистика, 1983. — 382 с.

19. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург. 2002. — 608 с.

20. Волков Д., ФроловА. Оценка быстродействия нерегулярного доступа к памяти // Открытые системы, 2008, №1.

21. Головкин Б.А. Анализ факторов, влияющих на скорость вычисления в параллельных и конвейерных системах // Автоматика и телемеханика, 1988, №5. — С. 152-164.

22. Головкин Б.А. Вычислительные системы с большим количеством процессоров. -М.: Радио и связь, 1995. — 320 с.

23. Головкин Б.А. Параллельные вычислительные системы. — М.: Наука. Гл. ред. физ.-мат. лит-ры, 1980. — 519 с.

24. Головкин Б.А. Соотношения между показателями производительности супер-ЭВМ и метод ее оценивания // Автоматика и телемеханика, 1989, №12.— С. 141-152.

25. Гурвиц М. Многопроцессорные серверы в новом масштабе // LAN, 1988, №4. —С. 30-38.

26. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. — М.: Радио и связь, 1988.

27. Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. — М.: Янус-К, 2003. — 380 с.

28. Каляев И.А. Реконфигурируемые мультиконвейерные вычислительные структуры. — Ростов-на-Дону: ЮНЦ РАН, 2008. — 320 с.

29. КатцанГ. Вычислительные машины системы 370. — М.: Мир, 1974.

30. КлейнрокЛ. Теория массового обслуживания. — М.: Машиностроение, 1979.

31. Коваленко Е. Система Sequent NUMA-Q // Открытые системы, 1997, №2.—С. 6-13.

32. Коган Я.А., Ляхов А.И., Нерсесян С.Г. Асимптотический анализ эффективности использования кэш-памяти в многопроцессорных системах // Автоматика и телемеханика, 1986, №11. — С. 142-151.

33. Корячко В.П., Сускин В.В. Анализ эффективности распределения данных в памяти специализированных микропроцессорных вычислительных систем // Автоматика и вычислительная техника, 1984, №2. —С. 66-68.

34. Корячко В.П., Су скин В.В. Анализ функционирования микропроцессорной вычислительной системы с буферной памятью // Автоматика и вычислительная техника, 1985, №3. — С. 75-77.

35. Кохонен Т. Ассоциативная память. М.: Мир, 1980. — 239 с.

36. Кохонен Т. Ассоциативные запоминающие устройства: Пер. с англ. М.: Мир, 1982. — 384 с.

37. Кошман Е.А., Соловьев С.П. Оценка номинальной производительности универсальных ЭВМ // Вопросы радиоэлектроники, сер. ЭВТ, 1977, вып. 5. — С. 60-70.

38. Кузьминский М. 64-разрядные микропроцессоры AMD // Открытые системы, 2002, №4. — С. 10-15.

39. Кузьминский М. Архитектура на базе Power4 // Открытые системы, 2004, №1. —С. 10-14.

40. Кузьминский М. Архитектура серверов HP Superdome // Открытые системы, 1997, №3. — С. 9-13.

41. Кузьминский М. Архитектура S2MP свежий взгляд на сс-NUMA // Открытые системы, 1997, №2. — С. 14-21.

42. Кузьминский М. Архитектурные особенности микропроцессоров РА-8000/8200/8500 // Открытые системы, 1997, №3. — С. 6-10.

43. Кузьминский М. Будущее архитектуры Power 4 // Открытые системы, 2000, №4. — С. 16-20.

44. Кузьминский М. Дорога к высоким частотам // Открытые системы, 2001, №2, —С. 8-14.

45. Кузьминский М. Краткий обзор IA-64 // Открытые системы, 1999, №9-10.— С. 8-14.

46. Кузьминский М. Микроархитектура DEC Alpha21264 // Открытые системы, 1998, № 1, — С. 7-11.50