автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Исследование и разработка методов и средств моделирования многоуровневой оперативной памяти для проектирования высокопроизводительной ЭВМ на системном этапе

ГТб Од

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

Кузьмин Юрий Михайлович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ МОДЕЛИРОВАНИЯ МНОГОУРОВНЕВОЙ ОПЕРАТИВНОЙ ПАМЯТИ ДЛЯ ПРОЕКТИРОВАНИЯ ВЫСОКОПРОИЗВОДИТЕЛЬНОЙ ЭВМ НА СИСТЕМНОМ ЭТАПЕ

Спетшаттыюсть 05.13.13- Вычислительные машины, комплексы, системы и сети

Автореферат

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

Рязань 1998

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

Научные руководители - заслуженный деятель науки и техники Российской Федерации доктор технических наук, профессор Злобин В.К.,

кандидат технических наук, доцент Пржсгорлинскиб В.Н.

Официальные оппоненты - доктор технических наук, профессор Голубкин В.Н.,

кандидат технических наук Везенов В.И.

Ведущая организация - Институт точной механики и вычислительной техники им. С.А. Лебедева АН РФ.

Защита состоится 1 июля 1998 года в 12 часов на заседании диссертационного Совет ДК 063.92.031 по защите кандидатских диссертаций при Рязанской государственной ради технической академии (391000, г. Рязань, ул. Гагарина, 59/1, ауд. 235) .

С диссертацией можно ознакомиться в библиотеке академии.

Автореферат разослан мая 1998 года.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

И.А. Телко

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

Актуальность проблемы. Рост сложности задач, решаемых на современных ЭВМ, предъявляет повышенные требования к быстродействию тракта процессор-память и одновременно к емкости оперативной памяти. Необходимость удовлетворения этих двух требований привела к тому, что оперативная память (011П) высокопроизводительных ЭВМ выполняется многоуровневой, где уровень, наиболее близкий к центральному процессору (кэш), работает с тактом процессора.

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

В наибольшей степени данное направление исследований развивалось в работах таких зарубежных авторов, как Agarwail Л., Goodman J.R., Pohm A.V., Smith Л.J., Stone H.S., Thiebaui D. и др. Однако обилие работ на эту тему еще не вывело ее из рамок эмпирических исследований, несмотря на то, что уже давно сложилась острая потребность в переходе от констатации полученных при моделировании ОПП результатов к достаточно точным моделям взаимодействия обращений программ с многоуровневой оперативной памятью, предсказывающим влияние параметров ее структуры и рабочей нагрузки на общую эффективность ОПП. В нашей стране в работах Бре-хова О.М., Когана Я.А, Козинского Л.Б., Слуцкина А.И. и др. отражены результаты проводившихся работ в данной области, однако, в основном по причине отсутствия у отечественных ученых средств получения трасс программ, объем проводившихся исследований был незначительным.

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

Иель работы. Целями данной диссертационной работы являются: 1) создание методики определения рациональной структуры (варианта организации) многоуровневой ОПП; 2) создание аналитической модели функционирования многоуровневой ОГТП для возможности формальной постановки и решения задач оптимального проектирования.

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

• анализ процессов, протекающих в кэш; анализ работы кэш во времени;

• анализ работы и эффективности кэш в условиях мультипрограммирования;

• оценка влияния работы подсистемы ввода-вывода на эффективность кэш;

• оценка влияния параметров программ на эффективность кэш;

• комплексная оценка эффективности двухуровневой и многоуровневой ОПП;

• исследование эффективности различных вариантов разделения (команды и данные, задача и управляющая программа и т.д.) и расслоения кэш;

• исследование влияния на эффективность ОПП алгоритмов замещения, выборки и записи.

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

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

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

2. Получены статистические характеристики процессов, протекающих в двухуровневой ОПП, и характеристики взаимосвязи этих процессов.

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

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

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

Практическая ценность работы заключается в следующем:

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

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

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

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

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

6. Получены количественные оценки степени взаимосвязи параметров рабочей нагрузки с параметрами структуры и эффективности Oi 111.

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

!. Подход к анализу многоуровневой ОПП, основанный на анализе параметров выбранного набора процессов, протекающих в ней.

2. Модели для оценки параметров рабочей нагрузки.

3. Статистические характеристики процессов, протекающих в двухуровневой ОПП, и характеристики взаимосвязи этих процессов.

4. Модели для комплексной оценки эффективности многоуровневой ОПП.

5. Методика выбора трасс программ, пригодных для использспатшя при моделировании двухуровневой 01111.

Объем и структура диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений, занимающих 222 страницы текста, в том числе 38 рисунков и 32 таблицы на 27 страницах, список использованной литературы из 136 наименований на 15 страницах, приложение на 6 страницах.

Реализация и внедрение. Теоретические и практические результаты, полученные автором, использованы в четырех научно-исследовательских хоздоговорных работах, выполненных на кафедре "Электронные вычислительные машины" Рязанской государственной радиотехнической академии по заказам НИЦЭВТ и ОКБ "Спектр", и нашли применение в разработках этих предприятий: в НИЦЭВТе - при разработке ОПП для ЭВМ ЕС 1087, ЕС1181 и ЕС1191, а в ОКБ "Спектр" - при разработке многоуровневой памяти для распределенной системы управления испытаниями. Документы, подтверждающие внедрение результатов работы в указанных организациях, приведены в приложении. Кроме того, результаты диссертационной работы используются в учебном процессе Рязанской государственной радиотехнической академии на кафедре ЭВМ.

Публикации. По результатам диссертации автором опубликовано 10 работ.

Апробация работы. Основные положения диссертации обсуждены на всесоюзной школе-семинаре "Разработка и применение в народном хозяйстве ЕС ЭВМ" (г. Кишинев, 1985), на всесоюзной школе-семинаре "Разработка и внедрение в народное хозяйство САПР ЭВМ" (г. Ереван, 1986 г.), на всесоюзной конференции "Моделирование систем информатики" (г. Новосибирск, 1988 г.), на всесоюзном совещании "Перспективы развития и опыт эксплуатации высокопроизводительных комплексов" (г. Днепропетровск, 1988 г.), на всесоюзной школе-семинаре "Разработка и внедрение в народное хозяйство ЕС ЭВМ" (г. Киев, 1989 г.), на заседании Советского национального комитета по математическому и машинному моделированию (г. Рязань, 1989 г.).

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

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

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

Выполнен анализ существующих способов организации многоуровневой ОПП современных высокопроизводительных ЭВМ по следующим направлениям:

1) способы организации многоуровневой ОПП;

2) схемы отображения адресов обращения процессора в адреса кэш;

3) организация ОПП с числом уровней, больше двух;

4) организация ОПП с разделением кэш на части;

5) организация ОПП с различными алгоритмами замещения, записи и выборки;

6) влияние операций ввода/вывода и виртуальной адресации.

На основании анализа существующих способов организации многоуровневой ОПП современных ЭВМ определена обобщенная структура объекта исследований -многоуровневой ОПП высокопроизводительных ЭВМ - и предложен обобщенный алгоритм его функционирования.

Определены цели, задачи и этапы исследований. Показано, что для достижения поставленных целей требуется:

а) создание модели многоуровневой ОПП;

б) сбор с помощью модели и анализ экспериментальных данных по каждой из задач;

в) отбор набора факторов, определяющих эффективность ОПП;

г) статистическая обработка экспериментальных данных с целью возможного построения эмпирических аналитических моделей взаимодействия программ с кэш;

д) построение точных аналитических моделей ОПП.

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

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

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

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

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

1) при построении моделирующего алгоритма отказаться от воспроизведения реальных временных диаграмм функционирования ОПП и учитывать логику обработки запросов лишь на уровне структуры;

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

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

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

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

1) параметры внутренней организации ОПП;

2) параметры организации функционирования ОПП;

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

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

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

К параметрам третьей группы относятся глубина мультипрограммирования, длительность интервала активности программ, параметры, задающие распределение общего адресного пространства между разными программами в ОП.

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

1) процесс заполнения кэш блоками программы;

2) процесс использования кэш блоками программы;

3) процесс реального использования информации, записанной в кэш;

4) процесс замещения блоков программы;

5) процесс "жизни" (пребывания) в кэш блоков программы;

6) процесс конкуренции за место в кэш между блоками, загружаемыми различными источниками запросов: командами и данными, процессором и системой ввода-вывода, проблемной программой и операционной системой;

7) процесс изменения информации в блоках кэш.

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

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

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

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

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

В соответствии с выбором трасс обращения программ к ОПП в качестве исходных данных для моделирования во второй главе диссертации также выполнен анализ особенностей представления информации в различных формах трасс программ. Приведена классификация трасс программ и выбрана форма представления исходных данных в трассах для целей моделирования 01Ш.

Третья глава посвящена решению вопросов подготовки и анализа исходных данных для моделирования ОПП.

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

1) правильность выбора трассы программы;

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

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

Выбор трасс включает в себя решение следующих трех задач:

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

2) выбор формы трасс;

3) выбор длины трассы;

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

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

При выборе формы трассы требуется сделать выбор среди следующих возможных вариантов:

а) чистая или полная трасса программы;

б) трасса однозадачного или многозадачного режима работы;

в) исходная, первичная или вторичная форма трассы;

г) естественные или искусственные трассы (для многозадачного режима).

Исходными являются те трассы, в которых для каждой команды и ее операндов

обязательно хранятся: адрес размещения команды; адрес размещения ее операндов; код операции и т.п.

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

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

На основании проведенного анализа предложено использовать на входе модели ОПТТ одну из разновидностей исходной формы трасс, а преобразование адресов размещения в адреса обращения выполнять в процессе моделирования в соответствии с заданной разрядностью обращения к оперативной памяти. Проигрыш в скорости моделирования при этом получается неболыной(5 - 10 %), зато выигрыш в универсальности - значительным.

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

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

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

В работе показано, что целесообразно придерживаться следующей последовательности использования форм трасс при моделировании ОПП:

1

эднопрограммные

трассы 1

Естественные многопрограммные трассы

1-й этап

Исследование работы кэш при функционировании ЭВМ в одно-программном режиме

2-й этап

Исследование влияния мультипрограммного режима работы ЭВМ на эффективность кэш

3-й этап

Оценка эффективности кэш на реальной рабочей нагрузке

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

При небольшой длине трассы общее количество промахов в кэш большого объема за время моделирования может оказаться сконцентрированным в коротком интервале начального заполнения кэш. Верхнюю 1раницу этого интервала можно использовать для оценки того минимума, ниже которого длину трассы выбирать нельзя. Анализ реальных трасс программ показал, что время полного заполнения кэш размером 64 Кбайт находится в пределах от 90000 до 300000 обращений к ОПП в зависимости от размера блока, числа строк и колонок кэш, размера рабочего набора страниц программ.

При использовании полных трасс программ более половины из общего количества обращений на начальном участке трассы составляют обращения управляющей программы операционной системы. Для того чтобы в процессе моделирования учитывать влияние не только управляющей программы, необходимо использовать трассы длиной, большей величины интервала, за которым число обращений управляющей программы в общей доле обращений снижается со 100 до 50 %. В работе показано, что по данному критерию длина трассы не должна быть менее 500 тыс. обращений к ОПП.

Несмотря на то, что трассы длиной порядка 1 миллиона обращений соответствуют лишь долям секунды работы высокопроизводительных ЭВМ, результаты, полученные с их использованием, обычно мало отличаются от результатов моделирования с использованием трасс, имеющих длину, на порядок большую. Так, если в кэш есть место для блоков только двух процессов, то количество процессов в мультизадачной смеси и длительность моделирования мало влияют на результаты по следующим двум причинам: 1) блоки, загруженные по запросам управляющей программы, будут в кэш постоянно, т.к. управляющая программа инициирует каждый пользовательский про-

цесс; 2) каждый получивший управление пользовательский процесс будет полностью выводить из кэш блоки предшествующего процесса.

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

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

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

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

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

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

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

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

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

Четвертая глава посвящена экспериментальным исследованиям многоуровневой ОПП с использованием разработанной имитационной модели.

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

Для выбранных базовых структур с помощью имитационной моделирующей подсистемы были исследованы следующие процессы в двухуровневой ОПП:

1) процесс заполнения кэш блоками одной программы;

2) процесс использования информации в кэш в однопрограммном режиме;

3) процесс замещения информации в кэш в однопрограммном режиме.

Для процесса заполнения кэш анализ экспериментальных данных привел к следующим выводам: 1) поток обращений за данными обеспечивает вдвое более быстрое полное заполнение кэш, чем поток обращений за командами; 2) время полного заполнения кэш со стороны управляющей программы является постоянной величиной, тогда как по остальным источникам обращений оно переменно для разных трасс; 3) наличие или отсутствие выборки по записи практически не влияет на время полного заполнения кэш; 4) пространственная локальность программ влияет на время полногс заполнения кэш: при одинаковой структуре кэш время полного ее заполнения обращениями от программы с худшей пространственной локальностью существеннс больше.

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

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

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

1. Параметры потока обращений к ОПП: коэффициент вариации для обращений за командами постоянно выше, чем для обращений за данными по всем трассам и

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

2. Число колонок ОПП: Ееличнна коэффициента вариации для любого из источников обращений увеличивается в два и более раз при увеличении количества колонок ОПП.

Эффективность использования кэш вычислялась по вел!гчине коэффициента использования кэш, равного отношению суммарного количества реально использованных байт к количеству байт, переданных из ОП в ЦП при промахах. Эффективность к'пт как буфера между ОН п ЦП тем выше, чем больше информации передается в направлении от кэш к ЦП по сравнению с количеством информации, передаваемой от ОП к кэш. В работе показано, что по графику зависимости коэффициента использования от размера блока удобно оценивать оптимальность выбора размера блока, причем этот выбор будет зависеть от характеристик локальности используемых программ. Так, в большинстве случаев для эффективного использования кэш обращениям от управляющей программы требуются меньшие по размеру блоки, чем обращениям от проблемкой программы.

Для процесса замещения информации в кэш в работе были получены значения коэффициента промахов. Показана целесообразность разложения обшей величины коэффициента промахов б кэш (КП) на части- КГ1 при чтении, КП при записи, К11 для команд. КП для данных, КП при чтении данных, КП при записи данных. Это. во-первых, позволяет более детально анализировать эффективность кэш, а во-вторых, позволяет оценивать эффективность разделенной кэш. В работе были получены и проанализированы значения КП для всех выбранных, для исследования структур ОПП, всех использованных трасс программ и всех потоков обращений.

Проведенный в работе анализ степени связи параметров программ с величиной КГ1 различных видов позволил выделить параметры программ, в наибольшей степени влияющие на величину того или иного КП. Такими параметрами для КП при чтении, КП при чтении данных и КП при чтении команд являются следующие:

1) среднее расстояние между соседними во времени рабочими наборами программы (БВКТ);

2) размер ядра страниц программы, на которое приходится 50 % обращений программы (М).

Каждый из названных параметров программ самостоятельно определяет величину коэффициента промахов на 85 - 90 %. Исходя из этого в работе были получены и

и

исследованы простые регрессионные модели взаимодействия программ и Olill следующего вида:

КПЯ = А, *SDIST + A2*M + B,

где KHr - коэффициент промахов при чтении;

А], А2 и В - коэффициенты, зависящие от параметров ОПП.

В четвертой главе также проведен анализ влияния взаимодействий между различными потоками обращений к ОПП на величину КП. Этот анализ проводился с целью определения соотношения между долей КП, объясняемой собственно свойствами конкретного потока обращений к ОПП, и долей КП, объясняемой взаимодействием данного потока обращений с другими.

Анализ полученных данных показал следующее: 1) доля КП, объясняемая взаимодействием различных потоков обращений, может достигать 50 и более процентов; 2) взаимодействие потоков обращений может не только увеличивать КП, но и уменьшать его; в каждом конкретном случае все определяется степенью пересечения в адресном пространстве обращений взаимодействующих потоков.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

4. Сформировано множество параметров, характеризующих рабочую нагрузку.

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

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

7. Для выбранных базовых структур ОПП выполнен анализ информационных процессов, протекающих в кэш: процесса заполнения, процесса использования и про-

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

8. Получены количественные оценки степени взаимосвязи параметров рабочей нагрузки, параметров структуры ОПП и параметров эффективности ОПП.

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

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

ПЕРЕЧЕНЬ ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Кузьмин Ю.М. Программные средства анализа двухуровневой оперативной памяти на системном этапе проектирования // Проектирование вычислительных машин и систем: Межвуз. сб. Рязань: РРТИ, 1987. С. 126-130.

2. Машины вычислительные электронные ЕС1191, ЕС1181. Технический проект. Пояснительная записка. Книга 10. "Структурная организация и основные технические характеристики мультипроцессора обработки данных со встроенной оперативной памятью. ЭВМ ЕС 11 81". 1988. С.181-205.

3. Кузьмин Ю.М.. Пржегорлинский В.Н. Вопросы исследования двухуровневой оперативной памяти ЭВМ с использованием трасс программ // Проектирование вычислительных машин н систем: Межвуз. сб. Рязань: РРТИ, 1988. С. 16-19.

4. Кузьмин Ю.М., Пржегорлинский В.Н. Моделирование двухуровневой оперативной памяти ЭВМ общего назначения // Моделирование систем информатики: Тез. докл. Всесоюзной конференции, Новосибирск, 13-15 сент. 1988. Новосибирск. 1988. С.273-274.

5. Кузьмин Ю.М., Пржегорлинский В.Н. Моделирование двухуровневой оперативной памяти ЭВМ общего назначения // Перспективы развития и опыт эксплуатации высокопроизводительных вычислительных комплексов: Материалы Всесоюзного совещания, Днепропетровск, 30 августа-1 сентября 1988. Днепропетровск: ДГУ. 1989.

С.66-72.

6. Вельский H.H., Кузьмин Ю.М., Пржегорлинский В.Н., Злобин В.К. Исследование двухуровневой оперативной памяти ЭВМ // Разработка и внедрение в народное хозяйство ЕС ЭВМ (ЕС ЭВМ-89): Тез. докл. Всесоюзной школы-семинара, Киев, сент. 1989. М„ 1989. С. 247-248.

7. Игонин A.A., Кузьмин Ю.М., Пржегорлинский В.Н. Исследование двухуровневой оперативной памяти многопроцессорных вычислительных систем // Информацион-

ное и программное обеспечение автоматизированных систем: Межвуз. сб. Рязань: РРТИ, 1990. С.96-101.

8. Игонин А.А., Кузьмин Ю.М., Пржегорлинский В.Н. Исследование процессов обмена информацией между элементами двухуровневой оперативной памяти в многопроцессорных вычислительных системах // Проектирование ЭВМ: Межвуз. сб. Рязань: РРТИ, 1992. С.21-26.

9. Кузьмин Ю.М., Пржегорлинский В.Н. Формирование набора параметров программ, влияющих на эффективность функционирования двухуровневой оперативной памяти // Вестник РГРТА: Научно-технический сборник. Рязань: РГРТА, 1997. №3. С.48-50.

Ю.Кузьмин Ю.М., Пржегорлинский В.Н. Выбор трасс программ для имитационного моделирования двухуровневой оперативной памяти// ЭВМ и информационные технологии: Межвуз. сб. Рязань: РГРТА, 1998. С. 74-78.