WWW.DISSERS.RU

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

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

Pages:     |
|

На правах рукописи

Биматов Дмитрий Владимирович МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ МНОГОУРОВНЕВОЙ ПАМЯТИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Специальность 05.13.11 — «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

Автореферат диссертации на соискание ученой степени кандидата технических наук

Томск — 2009 2

Работа выполнена в Томском государственном университете.

Научный руководитель доктор технических наук, профессор Сущенко Сергей Петрович Официальные доктор технических наук, профессор оппоненты: Назаров Анатолий Андреевич (Томский государственный университет) кандидат технических наук, доцент Замятин Александр Владимирович (Томский политехнический университет) Ведущая организация Сибирский государственный университет телекоммуникаций и информатики (г. Новосибирск)

Защита состоится 28 мая 2009 г в 10:30 на заседании диссертационного совета Д 212.267.08 при Томском государственном университете (634050, г. Томск, пр. Ленина, 36) в аудитории 102 второго корпуса ТГУ.

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета Автореферат разослан 17 апреля 2009 г.

Ученый секретарь диссертационного совета Д 212.267.08 доктор технических наук, профессор А.В. Скворцов 3

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Фундаментальные исследования по организации высокопроизводительных вычислительных систем провели российские и зарубежные ученые, среди них: Б.А. Бабаян, Е.П. Балашов, В.С. Бурцев, В.В. Воеводин, В.М. Глушков, Э.В. Евреинов, А.В. Забродин, А.В. Каляев, С.А. Лебедев, И.В. Прангишвили, Д.В. Пузанков, В.Г. Хорошевский, Н.Н. Яненко, A. Agarwal, S. Cray, M. Flynn, J.L. Hennessy, D.A. Patterson, и другие. Основные классические результаты по исследованию и моделированию многоуровневой памяти получили Т. Кохонен, Э. Таненбаум, К. Хамахер, З. Вранешич, С. Заки, А. Пом, Ю. Лускинд. Новейшие исследования по организации современных вычислительных систем изложены в работах М. Кузьминского, Л. Черняка, В.З. Шнитмана. Однако известные модели многоуровневой памяти не учитывают в явном виде влияние архитектурных параметров памяти на ее операционные характеристики.

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

Работа проводилась в рамках гранта А04-3.16-426 для поддержки научно-исследовательской работы аспирантов государственных образовательных учреждений высшего профессионального образования, находящихся в ведении Федерального агентства по образованию (конкурс 2004 года, головная организация – Санкт-Петербургский государственный университет).

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

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

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

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

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

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

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

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

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

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

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

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

Достоверность аналитических зависимостей, полученных в данной работе, подтверждается (а) строгими математическими выкладками, проведенными в соответствии с теорией вероятностей, теорией массового обслуживания; (б) результатами численных расчетов;

(в) а также результатами внедрения.

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

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

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

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

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

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

Апробация работы и публикации. По результатам выполненных исследований опубликовано 10 печатных работ, в том числе публикации в журналах из списка ВАК. Основные результаты диссер тационной работы докладывались и обсуждались на следующих научно-технических форумах: V Всероссийской конференции «Наука и образование» (Томск, 2001); II-ой Международной конференции молодых ученых и аспирантов «Актуальные проблемы современной науки» (Самара, 2001); XLI Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2003); Всероссийской конференции «Наука и практика: диалоги нового века» (Анжеро-Судженск, 2003); III Всероссийской научнопрактической конференции «Информационные технологии и математическое моделирование» (Анжеро-Судженск, 2004); XI Всероссийской научно-практической конференции «Научное творчество молодежи» (Анжеро-Судженск, 2007); IV-ой Сибирской школе-семинаре по параллельным и высокопроизводительным вычислениям (Томск, 2007).

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

Структура и содержание диссертационной работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы. Общий объем диссертации – 144 страницы, включая 61 рисунок, 3 таблицы и список литературы из 152 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

Во второй главе исследованы свойства двухуровневой памяти.

Предложена модель двухуровневой подсистемы памяти, состоящей из кэша и основной памяти. Кэш и основная память разбиты на блоки (строки) фиксированной длины l. Количество блоков в кэше — V, а в основной памяти — VОЗУ. В кэше блоки объединяются в группы объемом A 1 блоков. Число А называется коэффициентом ассоциативности. При A 1 имеем кэш прямого отображения (КПО). При A V (размер группы совпадает с общим количеством блоков в кэше) получаем полностью ассоциативный кэш (ПАК). Промежуточные значения параметра A приводят к множественному ассоциативному кэшу (МАК). На каждую g-тую группу блоков кэша g 0, G 1 отобража ется последовательность блоков памяти с номерами V g Gm, m 0, M 1, где G — количество групп в кэше, а A M VОЗУ — количество блоков памяти, отображаемых на группу G кэша.

В качестве меры эффективности памяти используются операционные характеристики «вероятность попадания в кэш» и «среднее время доступа к блоку памяти» T. Предполагаются, что заданы вероятности p g Gm обращения вычислителя к блоку памяти с номе ром g Gm, которые отражают класс задач, выполняемых на вы числительной системе. Естественно, что распределение p g Gm должно удовлетворять условию нормировки.

В общем случае вероятность попадания в кэш может быть вычислена по формуле:

G1 M (g Gum) p(g Gm), (1) g 0 mгде g Gm – вероятность того, что g Gm -й блок основной памяти находится в кэше. Среднее время доступа к блоку двухуровневой памяти может быть вычислено по следующей формуле T 1 K 1 RK, (2) где - время поиска и выбора блока из кэша, K — время выбора блока из оперативной памяти (K — натуральное число), R 1 — вероятность промаха в кэш. Отметим, что часто множитель опускают, вычисляя среднее время доступа в тактах работы кэша.

Для исследования эффективности работы кэша в настоящей работе используется модель кэша с идеальной стратегией вытеснения блоков. В этом случае предполагается, что исследователю заранее известно распределение вероятностей востребованности блоков памяти вычислителем. В работах С.П. Сущенко доказано, что при идеальном вытеснении вероятность нахождения блока памяти с номером g+Gm в кэше равна:

1, m 0, A p(g Gm) (g Gm), m A 1, M 1, (3) M p(g Gi) i A Соответственно при идеальном вытеснении (3) вероятность попадания в кэш (1) вычисляется так:

M p(g Gm) G1 A mA p(g Gm). (4) M g 0 m p(g Gm) m AДля получения аналитических зависимостей операционных характеристик кэш-памяти необходимо задать распределение вероятности востребованности блоков p(g+Gm). С одной стороны это распределение должно быть достаточно простым, с другой стороны – представлять собой широкий спектр распределений, встречающихся на практике. Поэтому в настоящей работе мы используем усеченное геометрическое распределение, одинаковое для каждой группы кэша:

1 q qm p(g Gm), m 0, A 1 (5) G 1 qA 0, m A, M 1 M Здесь – доля оперативной памяти, занятая востребованныA A ми вычислителем приложениями, выраженная в количестве объемов кэша первого уровня, a 0 q 1 – параметр усеченного геометрического распределения.

При усеченном геометрическом распределении (5) на основе выражения (4) получена зависимость для вычисления вероятности попадания в кэш:

1 q 2qA qA 1 q. (6) 1 qA 1 q Очевидно, что при q 0 (вероятностная масса сосредоточена в одном элементе группы) кэш работает без промахов и выражение (6) упрощается: 1; при q 1 (равномерное распределение) вероятность попадания в кэш минимальна и составляет:.

Далее рассмотрено влияние увеличения размера блока на производительность двухуровневой памяти. Отдельно рассматриваются два типа архитектуры кэша: 1 — полностью ассоциативный кэш; 2 — множественный ассоциативный кэш, включая кэш прямого отображения. В каждом случае рассматривается по два крайних способа объединения блоков: (а) объединение максимально далеких по вероятности востребованности блоков; (б) объединение соседних по вероятно сти востребованности блоков. Очевидно, случай (а) соответствует лучшему результату с точки зрения вероятности попадания в кэш, случай (б) соответствует худшему результату. В реальности характер объединения блоков предсказать заранее невозможно, следует ожидать результатов в диапазоне от случая (а) к случаю (б). В итоге получены аналитические зависимости для вычисления вероятности попадания адресуемого объекта в кэш от кратного увеличения размера интерфейсного блока для различных (четырех) вариантов изменения отображения блоков памяти в кэш при объединении исходных блоков в новый супер-блок (рис. 1, 2).

Pages:     |
|



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

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