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

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

Абу Асси Халед Мохаммад Хасан

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПОСТТРАНСЛЯТОРНОЙ ОБРАБОТКИ ПРОГРАММ

Специальность

05.13.11.- Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

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

Москва-2003

Работа выполнена в Московской

Государственной Академии Приборостроения и Информатики Министерства образования Российской

Федерации.

Научный руководитель- кандидат технических наук,

доцент Г.В. Зеленко

Официальные оппоненты: доктор технических наук,

профессор Н.А. Левин

кандидат технических наук, П.Н. Телегин

Ведущая организация; ОАО НИИ вычислительных комплексов им. М. А. Карцева

Защита диссертации состоится «16» декабря 2003 г. В 13,30 часов На заседании Диссертационного Совета Д212.119.02

Московской Государственной Академии Приборостроения и Информатики

по адресу: 107076, Москва, СтромынкаДО.

С диссертацией можно ознакомиться в библиотеке Московской Государственной Академии Приборостроения и Информатики (МГАПИ).

Автореферат разослан « 14» ноября 2003 г.

Учёный секретарь Диссертационного Совета к.т.н., доцент

М.В. Ульянов

О.С>у[С> ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы.

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

Для уменьшения времени обращения к памяти используется

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

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

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

Методы исследования

Исследования проводились на основе теории марковских процессов и методов математической статистики, а также элементов теории графов.

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

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

• построена марковская модель, описывающая случайный процесс " промахов в кэш данных;

• разработана система показателей качества предварительной выборки данных;

Г "рус. НАЦИОНАЛЬНАЯ | I БИБЛИОТЕКА | 1 С. Петербург - , г '

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

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

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

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

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

Реализация и внедрение результатов работы

Основные результаты диссертационной работы внедрены в Институте точной механики и вычислительной технике РАН и в МГАПИ на кафедре "Персональные ЭВМ, системы и сети"

Апробация работы

Основные результаты работы были доложены на заседаниях кафедры МГАПИ "Персональные ЭВМ, системы и сети" и на VI Международной научно-практической конференции "Фундаментальные и .прикладные проблемы приборостроения, информатики, экономики и права" (Сочи 2003г)

Публикации

Основные результаты диссертации опубликованы в 5 печатных работах.

Структура и объем работы

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

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

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

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

В начале главы приведены современные методы организации кэш, дается описание структуры кэш, его параметров и характеристик. Далее анализируются методы замещения строк кэш, приводятся понятия "холодного" и "горячего" стартов кэш.

В этой главе анализируются современные методы повышения эффективности кэш и выявляются основные направления работ, смежных с данной областью исследования. Эти направления отражены в частности в диссертациях Кручинина С.З., Кузьмина Ю.М., Кириенко Н.А, Поленова М.Ю., Ляпунцова С.А. и других.

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

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

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

далее), однако все они позволяют повысить эффективность кэш при

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

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

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

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

2. Создание системы показателей качества предлагаемого метода предварительной выборки данных.

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

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

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

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

неструктурированными приложениями.

В основу Марковского предвыборщика положено предположение, что поток адресов промахов может быть аппроксимирован Марковской моделью. Графически такая модель может быть представлена ориентированным графом, вершины которого соответствуют адресам ссылок в память, вызвавшим промахи, а дуги - переходам от одной такой ссылки к другой. На рис.1 приведен пример такого графа. В представленном на рис.1 графе буквами в вершинах графа А,В,СД),Е и Р обозначены адреса ссылок в память, а дуги

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

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

Раа ▼ / РаЬ В Pbc^^^

А

Рва

Рис. 1

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

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

• большой объем дополнительной аппаратуры ;

• снижение не miss ratio, а потерей от промаха в кэш;

® возможность реализовать только предвыборку по промахам, а не тэгированную предвыборку;

• нет слияния нескольких адресов предвыборок, относящихся к одной строке кэш, в одну предвыборку.

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

В основу программной реализации Марковского предвыборщика положены следующие принципы:

1. Автоматическое переключение на пошаговую предвыборку;

2. Два режима предвыборки: предвыборка по промахам и тэгированная предвыборка;

3. Слияние предвыборок, относящихся к одной строке кэш;

4. Ограничение числа предсказаний промахов с учетом их приоритета.

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

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

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

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

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

• относительное количество тактов на одну инструкцию, требуемое для обращения к памяти" ( Cycles Per Instruction contributed by Memory accsses ~ MCPI).

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

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

• графически частичная модель представляется связным подграфом;

• частичная модель позволяет точно оценить все статистические характеристики общей модели;

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

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

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

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

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

{ 2 71] Рл, I = 1,2... г. ]=1

К этой системе алгебраических уравнений добавляется условие нормировки: г

Ця! = 1 1=1

Таким образом мы определяем стационарное распределение вероятностей. Обозначим через ш; среднее время пребывания процесса в состоянии 1. Тогда среднее время пребывания процесса в выбранном подмножестве состояний определится следующим образом.

Л

Э! 6 в'

Т5'= - ,

О-ХйР])

Б; е б' Б] е б' где б' - выбранное подмножество состояний,

Т5- - среднее время пребывания процесса в выбранном подмножестве состояний.

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

В этой главе предлагается аналитическая модель стартовых: промахов сначала для структурированных приложений, а затем - для

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

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

Стартовое число промахов ( Мб) определяется числом различных строк кэш, к которым обращается процедура при запуске. Максимальное значение Мб = На. В общем случае Ыа >= Мб >= [ Ыа / Ь ], где [ Ыа / Ь ] - округленное до ближайшего целого значение.

На значение Мэ влияет начальный и конечный адреса последовательности. Начальная позиция - [ - последовательности в строке кэш меняется от 0 до Ь —1, то есть 0 < = 1 < = Ъ — 1. Для размещения последовательности длиной п необходимо [ (п + 1 ) / Ь ] строк.

Вероятность попадания начала последовательности в позицию 1 - р; — 1/ Ь. Тогда среднее значение числа строк кэш для размещения последовательности длиной п равно

Ь-1

Мз = 2(1/Ь* [(п + 0/Ъ]) = (п+ Ь -1)/Ъ 1=0

Обозначим через Ыз число последовательностей адресных ссылок, через От - разрыв между двумя последовательностями, выраженный в количестве адресных ссылок, и через рп - вероятность наличия последовательности длиной п среди всех последовательностей в N8. Тогда Мб для всего приложения можно определить следующим образом: Ыа

Мв^Кб* I рп*(п+ Ъ - 1 )/Ь п=1

После преобразований получим Мв= (Ыа+ №* (Ь-1))/ Ъ

Суммарное количество строк, занятых зазорами при средней длине зазора g, такой что % > — Ь-1

80т = Е(т* (Ь-1))/Ь, где т - общее число зазоров, равное N8-1 Тогда окончательная формула для оценки числа стартовых промахов: МБ=Ыа/Ь+ БОш + (Ь-1)) / Ь

Таким образом, на среднее число промахов при холодном старте влияет длина строки кэш, количество различных адресных ссылок и количество

зазоров между последовательностями ( со средней длиной g, такой что

g>= b- 1).

Глава 3 посвящена вопросам реализации программного Марковского предвыборщика и организации эксперимента на модели микропроцессора Alpha с целью исследования эффективности предлагаемого метода предварительной выборки данных. В этой главе приведены также результаты проведения эксперимента.

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

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

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

автоматическое переключение на пошаговую предвыборку задается перед выполнением эксперимента.

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

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

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

Для проведения эксперимента использовался ряд неструктурированных приложений, содержащих порядка 10 миллионов адресных ссылок в память

данных. К таким приложениям, например относятся многопользовательская среда разработки программного обеспечения из набора тестовых программ SPEC SDM, тестовая программа TCP/IP для проверки производительности коммуникационных систем и так далее. Для сравнения эксперименты проводились и со структурированными приложениями из набора SPEC95, например, с программой моделирования физических процессов ( расчеты с плавающей точкой), с программой управления базами данных (целочисленные расчеты)

В той главе приведены результаты проведения экспериментов по оценке эффективности Марковского предвыборщика на модели микропроцессора Alpha в среде DVT (Design Verification Test), разработанной фирмой Compaq и предназначенной для верификации проектов.

CjBxozP) 1

Трансляция приложения

I

Запуск приложения без I

предвыборки ]

РИС. 2

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

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

На рис. 3 приведены графики зависимости относительного числа промахов (miss ratio) от количества предсказаний для различных неструктурированных приложений в режиме предвыборок по промахам. Первая колонка в каждом из графиков соответствует работе приложения без предвыборщика, 2-я, 3-я и 4-я колонки - работе приложения с предвыборщиком с одним, двумя и четырьмя предсказаниями соответственно. Пятая колонка отражает значение miss ratio при совместной работе пошагового и Марковского предвыборщика с четырьмя предсказаниями. Под каждым кз графиков приведено название приложения.

На рис. 4 приведены графики зависимости относительного количества тактов на одну инструкцию, требуемого для обращения к памяти (MCPI). Структура графиков аналогична описанной выше. Значение MCPI при работе приложения без предвыборщика принято за 1.

Рис. 3

Рис. 4

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

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

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

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

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

3. Для оценки эффективности предлагаемого метода повышения

производительности кэш разработана система показателей качества предвыборки данных,

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

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

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

7. Разработана методика проведения экспериментов на модели микропроцессора Alpha для анализа эффективности предлагаемого метода.

8. Были проведены эксперименты с Марковским предвыборщиком по разработанной методике при различных режимах предвыборки, разном числе предсказаний промахов на всех выбранных приложениях.

Публикации по теме диссертации

1. Абу Асси X. Аналитическая модель для вычисления промахов в кэш // Межвузовский сборник научных трудов "Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ". - М.: МГАПИ, 2002, выпуск 5.

2. Абу Асси X., Шмейлин Б.З. Повышение производительности кэш путем предварительной выборки данных. // Межвузовский сборник научных трудов "Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ". - М.: МГАПИ, 2002, выпуск 5./ 3/2

3. Абу Асси X. Выбор метода повышения производительности кэш // Межвузовский сборник научных трудов "Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ'. - М.: МГАПИ, 2003, выпуск 5.

4. Абу Асси X. Организация эксперимента по анализу эффективности предварительной выборки в кэш // Межвузовский сборник научных трудов "Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ". - М.: МГАПИ, 2003, выпуск 5.

5. Абу Асси X., Шмейлин Б.З. Способ построения модели промахов в кэш // Межвузовский сборник научных трудов "Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ". - М.: МГАПИ, 2003, выпуск 5 /3/2.

Отпечатано в ООО «Компания Спутник+» ПД № 1-00007 от 25.09.2000 г. Подписано в печать 10.11.03 Тираж 100 экз. Усл. п.л. 0,94 Печать авторефератов (095) 730-47-74

QaO

(О

I

1 i

ВВЕДЕНИЕ.

Глава 1 . Методы ускорения доступа к памяти. Использование кэш- памяти.

1.1 Организация современной кэш- амяти.

1.2 Методы оптимизации использования кэш.

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

1.3 Предварительная выборка. Общие положения.

Глава 2. Разработка и исследование методов предварительной выборки данных.

2.1 Методы предварительной выборки.

2.2 Принципы построения Марковского предвыборщика.

2.3 Анализ марковской модели промахов.

2.4Аналитическая модель для вычисления стартовых промахов.

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

2.4.2 Вычисление стартовых промахов для неструктурированных

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

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

Повышение производительности МП за счет увеличения тактовой частоты в конечном счете наталкивается на технологические ограничения. Эти ограничения обусловлены размерами транзисторов на кристалле - в пределе это 0.05 мкм.

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

Так завод фирмы Intel в 1986 году стоил 200 млн долларов. Примерно через 10 лет при современной технологии завод стоит 2.4 млрд долларов. А при объявленной технологии 0.25 мкм такой завод будет стоить 10 млрд.- [1].

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

К таким архитектурным решениям можно отнести:

1 .Предсказание передач управления. Такое предсказание позволяет избежать или существенно сократить простои конвейера инструкций, так как при передачах управления нарушается последовательность инструкций, что ведет к простою конвейера инструкций (" осушению" конвейера).

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

Если запись выполнялась по другому адресу, то результат загрузки становится окончательным, в противном случае загрузку придется повторить.

3. Механизм предикатов. Механизм предикатов используется.в МП Pentium 6 ( предварительное название MERCED) для устранение передач управления. Все инструкции выполняются под предикатами. Последние вырабатываются в инструкциях сравнения. Если условие сравнения выполняется, соответствующий предикат принимает значение ИСТИНА, а в противном случае - ЛОЖЬ. Инструкция, выполняемая под предикатом со значеним ИСТИНА, работает обычным образом, а при значении предиката ЛОЖЬ вместо данной инструкции выполняется пустая команда (NOP).Таким образом конвейер инструкций никогда не "осушается" .

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

5. Уменьшение времени доступа к памяти. В современных МП цикл обращения к памяти в десятки раз превышает время выполнения инструкции В работе [2] приводятся следующие данные: За 10 лет производительность процессора выросла более чем в 12 раз, тогда как скорость обращения к памяти лишь удвоилась. Нет сомнения, что в будущем разрыв между производительностью процессора и главной памяти будет увеличиваться.

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

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

Именно таким вопросам посвящена диссертационная работа, что делает ее несомненно актуальной.

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

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

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

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

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

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

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

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

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

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

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

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

Выводы. 1. Разработанная Инструментальная среда позволяет автоматизировать трудоемкие процессы оценки эффективности различных методов повышения производительности кэш.

2. Несмотря на то, что такая Инструментальная среда предназначена для определенного метода предвыборки, а именно марковской предвыборки, и конкретной модели МП (Alpha 21364), эта среда может быть адаптирована для анализа эффективности самых различных методов повышения производительности кэш на моделях различных МП.

ЗАКЛЮЧЕНИЕ

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

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

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

4. Для оценки эффективности предлагаемого метода повышения производительности кэш разработана система показателей качества предвыборки.

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

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

-1147. Разработана методика проведения экспериментов на модели микропроцессора Alpha для анализа эффективности предлагаемого метода.

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

9. Были проведены эксперименты с Марковским предвыборщиком по разработанной методике при различных режимах предвыборки, разном числе предсказаний промахов на всех выбранных приложениях.

10. Проведенные эксперименты показали, что: a) количество предвыборок на один промах, при котором достигается разумный компромисс между показателями качества предвыборки - степенью покрытия, точностью и интенсивностью потока предвыборок, равно четырем; b) для большинства неструктурированных приложений такие показатели качества предвыборки, как относительное число промахов и степень покрытия, примерно совпадают в обоих режимах предвыборки — тэгированном и по промахам, но точность и интенсивность потока предвыборок лучше при предвыборке по промахам; c) Обобщенный показатель качества предвыборки - относительное количество тактов на одну инструкцию, требуемое для обращения к памяти ( MCPI) позволяет сделать вывод, что предвыборка всегда эффективна при одном или двух предсказаниях и всегда неэффективна при восьми предсказаниях; d) При четырех предсказаниях предвыборка эффективна при выборе режима предвыборки по промахам для приложений, у которых инструкции обращения к памяти неравномерно распределены среди остальных инструкций и поэтому критичным является нагрузка на шины памяти. Если же у приложения этот параметр не является критичным, то тэгировнная предвыборка будет более эффективна, е) при работе со структурированными приложениями наиболее эффективно совместное применение пошагового и Марковского предвыборщиков.

11. С целью автоматизации выполнения отдельных этапов проведения экспериментов разработана Инструментальная среда для анализа производительности кэш (ИСАПК ).

12. Данная Инструментальная среда может быть адаптирована для анализа эффективности самых различных методов повышения производительности кэш на моделях различных МП.

1. В.Корнеев, А.Киселев Современные микропроцессоры М. -"Нолидж" 2000

2. H.Kwak, B.lee,A.Hurson, S-H.Yoon,W-J.Hahn "Effects of Multithreding on Cache Performance "IEEE Transactions on Computers vol 48 No 2 Feb 1999

3. A.Smith "Cache Memories " Computing Surveys V.14N3 1982

4. G.Tyson, M.Farrens, J.Matthews, A.Pleszkin A Modified Approach to Data Cache Management Proc.28th Ann. Int't Symp. Microarchitecture Nov 1995

5. E. Tam "Improving Cache Performance Via Active Management " The Dissertation of Phd in the University of Michigan 1999

6. R. Kessler . The Alpha 21264 Microprocessor IEEE Micro v. 19 (2) Mar 1999

7. J-K. Peir, W.Hsu , A.Smith " Functional Implementation Techniques for CPU Cache Memories" IEEE Transactions on Computers vol 48, N 2 Feb 1999

8. M. Charney, V. Srinivasan "SpliCS Optimized Cache Line Placement Based on Reuse and Access Latency" IBM Research Development vol. 43, N5 1999

9. J.Collins, D. Tullsen " Hardware Identification of Cache Conflict Misses "Proc. of the 32nd Annual MICRO-32 ACM/IEEE International Symposium on Micoarchitecture Nov 1999

10. V.Pai, S.Adve " Improving Software Prefetching wiTh Memory Parallelism Transformations" Technical Report ECE-9910 Rice University Nov 1999

11. T.Kolarz " Performance Evaluation: An Analytical Model for Calculation Start Misses in Caches " Proc. Conference Euromicro92 v35 N1-5 Sept 1992

12. J.Sinoh, H.Stone "A model of workloads and its use in miss-ratio prediction for fully associative caches" IEEE Trans, on Computers v.41, N7, 1992

13. E.Rotenberg,S.Bennett J.Smith. "A Trace Cache Microarchitecture and Evaluation" IEEE Transactions on Computers vol 48 No 2 Feb 1999

14. S.Patel, D. Friendly, Y.Patt "Evalution of Design Options for the Trace Cache Fetch Mechanism " IEEE Transactions on Computers vol 48 No 2 Feb 1999

15. Temam " An Algoritm for Optimally Exploiting Spatial and Temporal Locality in Upper Memory Level " IEEE Transactions on Computers vol 48 No 2 Feb 1999

16. E. Tam, J.Rivers, G, Tyson "Evaluation the Performance of Active Cache Management Schemes" Report of the University of Michigan 1999

17. N.Topham , A . Gonzalez " Randomized Cache Placement for Eliminating Conflict" IEEE Transactions on Computers vol 48, N 2 Feb 1999

18. T.Chenj.Bayer "Effective Hardware based Data Prefetching for High Performance Processors" IEEE Trans.on Computers vol.44,no 5 (May 1995)

19. S. Abraham, R. Sugumar "Predictability of Load/Store Instruction Latencies " Proc. of the 26th Ann. International Symposium on Microarchitecture , Austin, Texas Dec 1993

20. S.Laha, J.Patel " Accurate Low Cost Methods for Performance Evalutions of Cache Memory systems. IEEE Trans, on Computers v.37 , N1 l,Nov 1988

21. T.Mowry, C. Luk " Understanding Why Correlation Profiling Improves predictability of data cache misses on nonnumeric applications 11 IEEE Transactions on Computers vol 49, N 4 Apr 2000

22. C.Luk, T.Mowry, " Automatic Compiler-Inserted Prefetching for Pointed-Based Applications1' IEEE Transactions on Computers vol 48 No 2 Feb 1999

23. D.Joseph, D.Grunwald "Prefetching Using Markov Predictors" IEEE Transactions on Computers vol 48 No 2 Feb 1999

24. T.Mowry, M.Lam, A.Gupta "Design and Evaluation of Compiler Algorithm for Prefetching" Proc ASPLOS-Y ,Oct 1992

25. N.Jouppi " Improving Direct-Mapped Cache Performance by Addition of Small Fully Associative Cache and Prefetch Buffers " Proc 17th Int't Symp. Computer Architecture May 1990

26. J.Tse, A.Smith "CPU Cache Prefetching: Timing Evaluation of Hardware Implementation" IEEE Trans, on Computers v.47, N 5 1998

27. M.Charney, A.Reeves " Generalized Correlation Based Hardware Prefetching " Technical Report EE-CEG-95-1 Cornell Univ. Feb. 1995

28. W-C. Hsu, J.Smith, "A Performance Study of Instruction Cache Prefetching Methods" IEEE Trans, on Computers v.47, N 5 1998

29. S.Patacharia, R.Kessler "Evaluating Stream Buffers as a Secondary Cache Replacement" Proc. 21st Ann. Int'l Symp. Computer Architecture 1994

30. T.Chen, J. Laer "Reducing Memory Latency Via Non-Blocking and Prefetching Caches " Proc ASPLOS-Y ,Oct 1992

31. K.Farkas , N. Jouppi " Complexity/ Performance Tradeoffs with non-Blocking Loads " Proc. 21st Ann, Int'l Symp. Computer Architecture, Apr. 1994

32. Ю.П.Журавлев, JI.A. Котелюк, Н.И. Циклинский " Надежность и контроль ЭВМ", М.: Сов. радио, 1978

33. Alpha Architecture Reference Manual

34. A.Maynard, C.Donnelly, B. Olszeewski " Constraining Characteristics and Cacha Performance of Technical and Multi-User Commercial Workloads " Proc. ASPLOS-YI Apr 1994

35. M. J. Charnev and T. R. Puzak Prefetching and memory system behavior of the SPEC95 benchmark suite . IBM Research Development vol. 41, N 3 1997

36. H. Гуревич, О. Гуревич Visual Basic 6.0 M. Бином, 1998

37. A. Smith " Cache Evaluation and the Impact of Workload Choice" Proc.th

38. Ann.International Symposium on Computer Architecture. Jun 1985

39. P. Emma J.Knight "Cache Miss Facility with Stored Sequences for Data Fetching" U.S. Patent 5.233.702 (Issued: August 3,1993)

40. A.Agarwal "Analysis of Cache Performance for Operating Systems And Microprogramming " Technical Report N CSL TR 87332 Stanford University May 1987.

41. M.Hill, A.Smith Evaluating Associativity in CPU Cache IEEE Trans on Comp vol 38 n. 12 Dec 1989

42. Z.Cvetanovich, d.Bhandakar " Characterisation of Alpha axp using tp and spce Workloads Proc. 21-st Ann. Int't Symp Computer Architecture Apr 1994 pp60-70

43. Agrawal, Horowith "An Analitical Cache Model " ACM Trans on Computer Systems v.7 ppl84 ,1989

44. Jacob, Chen and oth. " An Analitical Model for Designing Memory Hierarchies" IEEE Trans, on Computers v.45, pi 180 1996

45. D.Xing " Memory hierarchy considerations for cost-effective claster computing " IEEE Trans, on Computers v.49 N 9 pp 915 Sep 2000

46. А.Анго. Математика для электро и радиоинженеров М. Наука -1965г

47. R. Kessler , Е. McLellan, D. Webb "The Alpha 21264 Microprocessor Architecture " Proc. IEEE Int'l Conf. Computer Design Oct 1998

48. J.Cantin, M.Hill "Cache Performance for SPEC CPU2000 Benchmarks" Technical Report of University of Wisconsin-Madison Jan 2002

49. A.Smith "Sequentially and Prefetching in Data Base Systems" ACM Trans. Data Base Systems, vol. 3,N3,1979.

50. W-Y. Chen "The Effect of Code Expanding Optimizations on Instraction Cache Design" IEEE Trans, on Computers v.42, N 9 1993

51. Mowry, M.Lam, A.Gupta "Design and Evaluation of Compiler Algorithm for Prefetching" Proc. Int't Conf. Architectural Support for Programming Language and Operating Systems 1992

52. A.Smith " Sequential Program Prefetching in Memory Hierarchies" Computer, Dec 1978.

53. J.Smith " A Study of Branch Prediction Strategies" Proc. 8 Ann. Symp. Computer Architecture 1981

54. W.Hwu, P.Chang " Achieving High Instruction Cache Performance with Optimizing Compiler" Proc. 11 Ann. Symp. Computer Architecture 1984

55. Callahan, Kennedy, Porterfield " Software Prefetching" Proc.4 Int't Conf. Architectural Support for Programming Language and Operating Systems Apr. 1991

56. E.Dahlgren, P.Stenstrom "Sequential Hardware Prefetching in Shared Memory Multiprocessors " IEEE Trans. Parallel and Distributed Systems , vol.6 N7, 1995

57. J.Fu, J.Patel " Data Prefetching Strategies for vector Cache Memories" Proc. 5 Int't Parallel Processing Symp. May 1991

58. J.Gee, M.Hill, D. Penvmatikatos, A.Smith " Cache Performance of the SPEC Benchmark Suite" IEEE Micro vol.13 N 4, Aug.!993

59. S.Kim " Threaded Prefetching: An Adaptive Instruction Prefetch Mechanizm" Microprocessing and Microprogramming vol.39 N 1 Nov. 1993.

60. A.Smith " Characterizing the Storage Process and its Effects on Main Memory Update" ACM vol.26, N 1, Jan. 1979

61. A.Smith "Cache Evaluation And the Impact of Workload Choice" Proc. 12 Int'1 Symp. Computer Architecture 1985

62. A.Smith "Line (Block) Size Selection in CPU Cache Memories" IEEE Trans, on Computers vol.36, N 9 Sept. 1987

63. A.Smith "Trace-Driven Simulation in Research on Computer Architecture and Operating Systems" Proc. New Directions in Simulation for Manufacturing and Comm. (SIM94), Aug. 1994

64. J.Tse, A.Smith " Performance Evaluation of Cache Implementation" Technical Report UCB / CSD-95-877, Univ. of California, June 1995

65. V.Varma, G.Sinha " A Class of Prefetch Schemes for On-Chip Data Caches" Technical Report, Univ. of California 1992

66. R.Min, Y.Hu " Improving Performance Of Large Physically Indexed Caches by Decoupling Memory Addresses from Cache Addresses " IEEE Trans, on Computers v.50, N 5 2001

67. Кемени Д., Снелл Д. Конечные цепи Маркова М.: Наука, 1970

68. Казаков В.А. Введение в теорию марковских процессов и некоторые радиотехнические задачи М.: Сов,радио, 1973

69. P.Singh, H.Stone, D.Thiebaut "A model of workloads and its use in miss-rate prediction for fully associative caches " IEEE Trans, on Computers v.41, N 7, 1992

70. G.Rao " Performance analysis of cache memories" Journal of the ACM, v.25 N3, 1978

71. R. Ladner, J.Fix, A.LaMarca " Cache Performance Analysis of Traversal and Random Accesses "10 Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

72. J.Cantin, M.Hill "Cache Performance for SPEC CPU2000 Benchmarks" Report University of Wisconsin-Madison Jan. 2002

73. С.Кручинин "Исследование структурной организации иерархических подсистем оперативной памяти многопроцессорных векторно-конвейерных суперэвм" Автореферат диссертации на соискание ученой степени канд.техн.наук М.: 1991.

74. Ю.Сокол " Разработка моделей, методов и структурных средств взаимодействия процессоров и параллельной общей памяти в мультимикропроцессорных вычислительных системах" Автореферат диссертации на соискание ученой степени д-ра техн. наук" М, 1994

75. Ю.Кузьмин "Исследование и разработка методов и средств моделирования многоуровневой оперативной памяти для проектирования высокопроизводительной ЭВМ на системном этапе" Автореферат диссертации на соискание ученой степени канд.техн.наук Рязань 1998.

76. С.Ляпунцов "Информационные методы оценки производительности вычислительных систем" Автореферат диссертации на соискание ученой степени канд.техн.наук М.-1991.

77. Н.Кириенко "Оптимизация программ в процессе трансляции" Автореферат диссертации на соискание ученой степени канд.техн.наук-Минск, 1992.

78. М.Поленов "Разработка инструментальных средств проектирования, исследования и оптимизации проблемно-ориентированных вычислительных систем" Автореферат диссертации на соискание ученой степени канд.техн.наук Таганрог 1995.

79. Р.Халабия "Анализ эффективности исходных текстов программ в процессе обучения " Автореферат диссертации на соискание ученой степени канд.техн.наук- М. 1999

80. В. Мураховский, Г. Евсеев " Железо ПК 7-е издание " М. —"I-Press" 2003

81. А.Жаров " Железо IBM 10-е издание " М. -" Микро Арт " 2003

82. К.Касперски "Техника оптимизации программ. Эффективное использование памяти " С.П. «БХВ-Петербург» 2003

83. Абу Асси X. Аналитическая модель для вычисления промахов в кэш // Межвузовский сборник научных трудов "Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ". М.: МГАПИ, 2002, выпуск 5.

84. Абу Асси X. Выбор метода повышения производительности кэш // Межвузовский сборник научных трудов "Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ". М.: МГАПИ, 2003, выпуск 5.