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

УДК 004 4416 На правах рукописи

□□3448615

Галазин Александр Борисович

МЕТОДЫ ОПТИМИЗАЦИИ ДОСТУПА К ПОДСИСТЕМЕ ПАМЯТИ НА ЭТАПЕ КОМПИЛЯЦИИ

ДЛЯ МИКРОПРОЦЕССОРНЫХ СИСТЕМ С АРХИТЕКТУРОЙ ШИРОКОГО КОМАНДНОГО СЛОВА

05 13 11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 6 О КГ 2003

Москва - 2008

003448615

Работа выполнена в ЗАО «МЦСТ» и ОАО «ИНЭУМ им И С Брукам

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

Нейман-заде Мурад Искендер-оглы

Официальные оппоненты

доктор технических наук, профессор Сухомлин Владимир Александрович кандидат технических наук Добров Андрей Дмитриевич

Ведущая организация

Институт проблем информатики РАН

Защита состоится »_НЛ^и^_ 2008 г в часов на заседании диссертационного совета Д 409 009 01 при ОАО «Институт электронных управляющих машин им. И. С. Брука», расположенном по адресу 119334, г Москва, ул Вавилова д 24

С диссертацией можно ознакомиться в библиотеке ОАО «ИНЭУМ им. И. С. Брука»

Автореферат разослан »_2008 г

Ученый секретарь

диссертационного совета,

кандидат технических наук, профессор

Красовский В Е

Общая характеристика работы

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

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

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

структур организовано в программе хранение и обращение к данным (в дальнейшем они характеризуются как «шаблоны хранения и обращения»)

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

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

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

и разработки эффективных методов доступа к подсистеме памяти, реализуемых на этапе компиляции

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

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

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

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

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

• реализовать указанные методы в составе оптимизирующего компилятора для микропроцессора «Эльбрус»

Научная новизна

Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую составляют

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

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

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

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

Практическая ценность результатов работы состоит в том, что на основе предложенных методов были разработаны реализованные на этапе компиляции методы эффективного взаимодействия с подсистемой памяти с учетом особенностей целевой архитектуры Предложенные методы оптимизации взаимодействия процессоров и подсистемы памяти могут эффективно использоваться для микропроцессоров с архитектурой широкого командного слова Все представленные в диссертационной работе алгоритмы и методы реализованы в составе оптимизирующего компилятора с языков высокого уровня Си, Си++, Фортран для микропроцессора «Эльбрус», и их эффективность подтверждена на пакетах задач SPEC CPU2000, SPEC CPU95

Результаты, выносимые на защиту

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

1 Комплексный метод программной поддержки комбинированного метода предварительной подкачки 0-линейно регулярных данных,

который позволил в среднем повысить производительность на 24% на задачах пакета SPEC CPU2000

2 Методы программной предварительной подкачки п-(не)линейно (псевдо)регулярных и n-кольцевых рекуррентных данных, учитывающие особенности архитектуры, что дополнительно в среднем улучшило на 18,5% и 9,1% показатели производительности задач с соответствующим контекстом

3 Метод программной предварительной подкачки кода для архитектур с широким командным словом, который позволил в среднем на 3,2% ускорить задачи пакета SPEC CINT2000

4 Метод определения оптимального взаимного расположения глобальных массивов, что дополнительно в среднем улучшило показатели производительности задач пакета SPEC CFP95 на 10% и пакета SPEC CFP2000 на 5,9%

Апробация

Результаты, полученные в работе, изложены в ряде печатных публикаций, докладывались на научных конференциях и семинарах, в частности на XXXIV Международной молодежной научной конференции «Га-гаринские чтения»(Москва, МАТИ, 2008 г), XXIII научно-технической конференции «Направления развития и применения перспективных вычислительных средств и новых информационных технологий в В ВТ РКО»(Москва, в/ч 03425, 2007 г), XIV Международной конференции студентов, аспирантов и молодых ученых «Ломоносов»(Москва, МГУ им М В Ломоносова, 2007 г), XXXIII Международной молодежной научной конференции «Гагаринские чтения»(Москва, МАТИ, 2007 г), семинарах секции программного обеспечения ЗАО «МЦСТ»

Публикации

По теме диссертации опубликовано 10 печатных работ

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и приложения Список литературы составляет 77 наименований Объем диссертации составляет 149 страниц текста Диссертация содержит 55 рисунков

Содержание работы

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

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

В современных микропроцессорах кэш данных формируется из нескольких блоков (банков) памяти с независимым доступом, что позволяет одновременно исполнить несколько инструкций чтения/записи В качестве примера можно привести системы Sun OpenSPARC Tl, Intel Itanium 2 Многобанковая кэш-память является важным элементом, обеспечивающим максимальную загрузку исполнительных устройств архитектуры с широким командным словом Она реализована в качестве кэш-памяти второго уровня (L2$) в микропроцессоре «Эльбрус»

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

Рис. 1. Внутренние блокировки кэш-памяти данных на задачах пакета SPEC CFP95

ся и формируются очереди запросов по чтению и записи к банкам. Размер каждой очереди ограничен.

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

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

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

2) блокировки, причиной которых является занятость устройства доступа в память.

Блокировки первого класса в дальнейшем будем называть внутренними блокировками кэша flaHHbix(L2$-staIl), а блокировки второго класса — блокировками устройства доступа в память (MAU-stall).

Изучение причин возникновения блокировок проводилось на вы-

Рис. '2. Внутренние блокировки кэш-памяти данных на задачах пакета SPEC CFP2000

числительном комплексе «Эльбрус-ЗМ1» с помощью инструментальных средств подсчета событий микропроцессора. В качестве единицы измерения было взято количество тактов блокировки на 1000 исполненных широких команд (в дальнейшем ц).

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

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

:Для наглядности данные по пакету SPEC CFP2000 представлены в логарифмической шкале

S00 500 400 300 200 100 5. 101 1 _ ■ i. ^ - - _ 1 1 зО 250 lililí

% Ъ % ^ Ч % % % % % % %■ %% \ч \\ * V* ^ \VV< V

Рис. 3. Количество блокировок по отсутствию кода

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

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

На рис. 3 представлены результаты замеров количества блокировок по отсутствию кода на задачах пакета SPEC CPU2000.

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

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

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

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

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

В предлагаемой классификации выделяются следующие шаблоны хранения и обращения к данным в циклах

1 а) 0 -линейно регулярный — чтение объекта, адрес которого вычисляется с помощью линейной функции от безусловной индуктивной переменной цикла2 (например, а[1+1]),

б) 0-нелинейно регулярный — чтение объекта, адрес которого вычисляется с помощью нелинейной функции от базовой индуктивной переменной цикла (например, а[1&К]),

2Персмо1шая, изменяющаяся на инвариантную величину на каждой итерации цикла

в) п-линейно регулярный — чтение объекта, адрес которого линейно зависит от результата (п — 1)-линейно регулярного чтения (например, доступ по вторичным индексам является 1-линейно регулярным Ъ [а [1+1] +2]),

г) п-нелинейно регулярный — чтение объекта, адрес которого зависит от результата (п — 1)-нелинейно регулярного чтения, либо нелинейно зависит от результата (п — 1)-линейно регулярного чтения (например, Ь[а[л.&К]+1]),

2 а) 0-линейно псевдорегулярный — чтение объекта, адрес кото-

рого вычисляется с помощью линейной функции от условной индуктивной переменной3,

б) 0-нелинейно псевдорегулярный — чтение объекта, адрес которого вычисляется с помощью нелинейной функции от условной индуктивной переменной,

в) п-линейно псевдорегулярный — чтение объекта, адрес которого линейно зависит от результата (п — 1)-линейно псевдорегулярного чтения,

г) п-нелинейно псевдорегулярный — чтение объекта, адрес которого зависит от результата (п — 1)-нелинеино псевдорегулярного чтения,

3 0-кольцевой рекуррентный — чтение объекта, адрес которого определяется рекуррентной цепочкой, состоящей только из арифметических инструкций, при этом каждая составляющая адреса полностью определяется своим значением с предыдущей итерации цикла (например, а+=Ь, Ъ+=а, с[Ь],),

3Перемснная, изменяющаяся на инвариантную величину при выполнении некоторого условия

4 п-кольцееой рекуррентный — чтение объекта, адрес которого определяется рекуррентной цепочкой, состоящей из арифметических инструкций и п > 0 инструкций чтения, при этом каждая составляющая адреса полностью определяется своим значением с предыдущей итерации цикла (например, а = с[а+1] ,),

Тип 1а является наиболее распространенным способом обращения к данным Большинство существующих методов подкачки ориентировано именно на обработку такого типа данных

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

В типе 2 достаточно существенны п-линейно псевдорегулярные данные при п > О Случаи нелинейного доступа ничем не отличается от линейных в плане анализа возможности проведения предварительной подкачки

Тип 3 также может быть объектом предварительной подкачки, поскольку при задании расстояния подкачки адрес упреждающего запроса вычислим на этапе компиляции Гораздо сложнее случай п-кольцевого рекуррентного доступа при п > О (тип 4), так как в таком случае в цепочке инструкций, вычисляющих адрес присутствуют инструкции чтения Это делает адрес упреждающего запроса невычислимым, а значит нельзя однозначно утверждать, что произойдет подкачка необходимых данных Тем не менее, предварительная подкачка для данных 4-го типа возможна, однако требует специфических методов подкачки, которые были разработаны в рамках данной работы

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

ным шаблоном, и реализует программную поддержку комбинированного метода подкачки в рамках оптимизирующего компилятора для микропроцессора «Эльбрус» Его использование привело к повышению производительности в среднем на 21% по пакету SPEC CPU2000

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

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

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

2) оценивается время, требуемое для чтения данных без использования предварительной подкачки, оно вычисляется как произведение

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

3) дополнительно принимается во внимание тот факт, что использование предварительной подкачки позволяет уменьшить длину ап-паратно конвейеризуемого цикла, так как освобождает арифметические устройства от инструкций чтения

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

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

Использование комплексного метода генерации программы предварительной подкачки позволило в результате в среднем повысить производительность на 24% на задачах пакета SPEC CPU2000

Построение программы предварительной подкачки возможно для чтений, классифицируемых 0-линейно регулярным шаблоном При использовании остальных шаблонов типов 1 и 2 это затруднительно, поскольку требует расширенной аппаратной поддержки, однако, в данном случае возможно применение явных инструкций предварительной подкачки С этой целью был разработан программный метод предварительной подкачки, который основывается на прогнозировании адресов данных, необходимых для последующих вычислений Он ориентирован на п-(не)линейно псевдорегулярные обращения при п > 0 и п-(не)линейно регулярные обращения при п > 0 Это потребовало создания и реализа-

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

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

Разработанные в данной работе методы программной предварительной подкачки п-(не)линейно (псевдо)регулярных и п-кольцевых рекуррентных данных, дополнительно в среднем повысили на 18,5% и 9,1% показатели производительности задач с соответствующим контекстом

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

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

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

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

Решение этой проблемы потребовало разработки специального метода минимизации блокировок, основанного на понятии ^-непрерывно исполняемого участка кода, где в — минимальная вероятность исполнения инструкции, заканчивающей непрерывный участок Суть метода состоит в предварительной подкачке кода, исполняемого по прямой ветви Важно отметить, что подкачке подлежат только ациклические участки кода с достаточно высокой вероятностью исполнения Кроме того, следует задать эффективное значение расстояния до подкачиваемого кода с тем, чтобы обеспечить его своевременную загрузку При этом надо учитывать невозможность вычисления этого значения на этапе компиляции При реализации метода применительно к архитектуре «Эльбрус» была исследована зависимость количества блокировок от параметра 0 и других параметров и выбраны их оптимальные значения, соответствующие

основным классам задач Использование предложенного метода привело к в среднем к повышению производительности на 3,2% на задачах пакета SPEC CINT2000

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

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

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

менения адреса из множества S шагов и а - набор смещений начальных адресов, определяющий взаимное расположение массивов в памяти Следует найти минимум по а максимального среднего количества запросов в память использующих j-ый банк кэша на одной итерации цикла -ф^1 (а) Тогда, обозначив значение счетчика цикла через ш (I), количество банков с одинаковым максимальным количеством запросов - ф(а), получаем задачу минимизации функционала

seS

Точное решение задачи предполагает исследование всех возможных смещений для всех возможных вариантов упорядоченного расположения массивов и аналитически невыразимо Поэтому для задач пакетов SPEC CFP95 и SPEC CFP2000 были проведены оценки применимости двух методов определения минимума функционала, которые позволяют избежать полного перебора — метода Монте-Карло и метода покоординатного спуска Они показали, что второй алгоритм при значительно меньшем времени исполнения позволяет в такой же мере сократить количество блокировок

Использование предложенного программного метода позволило дополнительно в среднем улучшить показатели производительности задач пакета SPEC CFP95 на 10% и пакета SPEC CFP2000 на 5,9%

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

Заключение

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

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

Для снижения количества блокировок по отсутствию данных были разработаны и реализованы в составе компилятора новые эффективные методы предварительной подкачки данных, основанные на предложенной в работе расширенной классификации шаблонов хранения и обращения к данным Их использование позволило в среднем повысить производительность на задачах пакета SPEC CPU2000 на 24% для 0-линейно регулярных данных и на 18,5% и 9,1% для п-(не)линейно (псев-до)регулярных и n-кольцевых рекуррентных данных соответственно

В ходе исследования было установлено, что основная часть блокировок по отсутствию кода возникает при исполнении непрерывных участков, доля которых в среднем на пакете задач SPEC CINT2000 составляет 15,5% Для решения этой проблемы был разработан новый метод минимизации блокировок, основанный на понятии ^-непрерывно исполняемого участка кода, что позволило в среднем на 3,2% повысить производительность

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

данных, базирующийся на изменении начальных адресов Его использование метода дополнительно улучшило показатели производительности задач пакета SPEC CFP95 в среднем на 10% и пакета SPEC CFP2000 в среднем на 5,9%

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

Список работ, опубликованных по теме диссертации

1 Галазин А Б , Грабежной А В , Нейман-заде М И Оптимизация размещения данных для эффективного исполнения программ на архитектуре с многобанковой кэш-памятью данных // Информационные технологии, № 3, 2008, С 35-39

2 Галазин А Б , Ступаченко Е В , Шлыков С JI Программный метод предварительной подкачки кода в архитектурах со статическим планированием // Программирование JV? 1, 2008, С 67-74

3 Галазин А Б Методы оптимизации размещения данных для архитектур с многобанковой кэш-памятью данных // Научные труды XXXIV Международной молодежной научной конференции «Гага-ринские чтения», т 6 М МАТИ, 2008, С 167-168

4 Галазин А Б , Степаненков А М , Ступаченко Е В Программная предварительная подкачка кода для микропроцессора Эльбрус-ЗМ // Информационные технологии, № И, 2007, С 35-42

5 Галазин А Б , Грабежной А В Эффективное взаимодействие микропроцессора и подсистемы памяти с использованием асинхронной

предварительной подкачки данных // Информационные технологии, № 5, 2007, С 26-31

6 Галазин А Б Методы предварительной подкачки в микропроцессоре Эльбрус-ЗМ // Научные труды XXXIII Международной молодежной научной конференции «Гагаринские чтения», т 6 М MATH, 2007, С 213-214

7 Галазин А Б Предварительная подкачка кода для микропроцессора Эльбрус-ЗМ // Материалы докладов XIV Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов» / Отв ред И А Алешковский, II Н Костылев [Электронный ресурс] - М Издательский центр Факультета журналистики МГУ им М В Ломоносова, 2007 - 1 электрон опт диск (CD-ROM)

8 Галазин А Б Оптимизация участков кода с малым количеством исполнений // Высокопроизводительные вычислительные системы и микропроцессоры сборник трудов ИМВС РАН, Выпуск № 9, 2006, С 58-63

9 Дроздов А Ю , Новиков С В , Боханко А С , Галазин А Б Def-Use граф и методы его использования в современных оптимизирующих компиляторах//Компьютеры в учебном процессе, Л"2 12 2005 С 314

10 Дроздов А Ю , Новиков С В , Боханко А С , Галазин А Б Глобальный граф потока данных и его роль в проведении оптимизирующих преобразований программ // Высокопроизводительные вычислительные системы и микропроцессоры сборник трудов ИМВС РАН, Выпуск № 8, 2005, С 78-87

Подписано в печать 14 июля 2008 г Объем 1,0 п л Тираж 100экз Заказ № 1016 Отпечатано в Центре оперативной полиграфии ООО «Ол Би Принт» Москва, Ленинский пр-т, д 37

Введение.

1. Аспекты производительности современных вычислительных систем

1.1. Недостатки кэш-памяти.

1.2. Аппаратные особенности микропроцессора «Эльбрус»

1.2.1. Кэш данных второго уровня

1.2.2. Буфер инструкций.

1.2.3. Механизмы предварительной подкачки данных

1.3. Причины потери производительности.

1.3.1. Отсутствие запрашиваемых данных в кэше

1.3.2. Неравномерная загрузка банков кэша.

1.3.3. Отсутствие необходимого кода в буфере инструкций

1.4. Постановка задачи.

1.5. Выводы.

2. Методы предварительной подкачки данных.

2.1. Классификация данных и способов доступа

2.2. Существующие методы предварительной подкачки данных

2.2.1. Программная предварительная подкачка данных

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

2.3. Недостатки существующих методов предварительной подкачки данных

2.4. Комбинированный метод предварительной подкачки данных

2.4.1. Теоретические преимущества комбинированного метода

2.4.2. Ограничения, налагаемые на подкачиваемые данные

2.4.3. Базовый алгоритм.

2.4.4. Результаты применения базового алгоритма

2.4.5. Оптимизация программы предварительной подкачки

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

2.4.7. Итоговые результаты предварительной подкачки

2.5. Программная предварительная подкачка данных

2.5.1. Предварительная подкачка (псевдо)регулярных чтений

2.5.2. Предварительная подкачка n-кольцевых рекуррентных чтений

2.6. Выводы.

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

3.1. Известные методы подкачки кода

3.1.1. Аппаратные методы.

3.1.2. Программные и комбинированные методы подкачки кода

3.2. Недостатки существующих методов подкачки кода

3.3. Особенности исполняемого кода VLIW-микропроцессоров . 88 3.3.1. Оптимизирующие преобразования, увеличивающие длины

3.4. Минимизация блокировок по ожиданию кода

3.4.1. Эффективные значения параметров.

3.4.2. Повышение эффективности алгоритма предварительной подкачки кода

3.4.3. Результаты.

3.5. Выводы.

4. Повышение плотности запросов в оперативную память

4.1. Методы повышения времени'ой локальности данных.

4.2. Внутренние конфликты кэш-памяти

4.3. Недостатки существующих методов сокращения блокировок кэшпамяти

4.4. Сокращение внутренних блокировок многобанковой кэш-памяти данных

4.4.1. Математическая постановка задачи.

4.4.2. Метод покоординатного спуска.

4.5. Эффективность алгоритма сокращения внутренних блокировок кэша данных.

4.5.1. Структуры хранения данных в языке Фортран.

4.5.2. Разделение COMMON-блоков

4.5.3. Расширенное разделение COMMON-блоков

4.6. Результаты.

4.7. Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

• реализовать указанные методы в составе оптимизирующего компилятора для микропроцессора «Эльбрус».

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

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

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

• конечная эффективность и производительность результирующего кода.

Методы исследования заимствованы из областей системного программирования, проектирования, технологии компиляции, математической статистики, теории алгоритмов. Эффективность предложенных решений оценивалась путем замера времени исполнения программ на вычислительном комплексе с микропроцессором «Эльбрус». Замеры производились на пакетах задач SPEC CPU95 и SPEC CPU2000 [3].

Научная новизна Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую составляют:

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

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

• программный метод предварительной подкачки кода, ориентированный на архитектуру с -широким командным словом;

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

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

1 Определения будут даны п глапе 2 подсистемы памяти могут эффективно использоваться для микропроцессоров с архитектурой широкого командного слова. Все представленные в диссертационной работе алгоритмы и методы реализованы в составе оптимизирующего компилятора с языков высокого уровня Си, Си++, Фортран для микропроцессора «Эльбрус», и их эффективность подтверждена на пакетах задач SPEC CPU2000, SPEC CPU95.

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

1. Комплексный метод программной поддержки комбинированного метода предварительной подкачки 0-линейно регулярных данных, который позволил в среднем повысить производительность на 24% на задачах пакета SPEC CPU2000.

2. Методы программной предварительной подкачки п-(не)линейно (псев-до)регулярных и ^-кольцевых рекуррентных данных, учитывающие особенности архитектуры, что дополнительно в среднем улучшило на 18,5% и 9,1% показатели производительности задач с соответствующим контекстом.

3. Метод программной предварительной подкачки кода для архитектур с широким комащщым словом, который позволил в среднем на 3,2% ускорить задачи пакета SPEC CINT2000.

4. Метод определения оптимального взаимного расположения глобальных массивов, что в среднем улучшило показатели производительности задач пакета SPEC CFP95 на 10% и пакета SPEC CFP2000 на 5,9%.

Апробация

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

• на XXXIV Международной молодежной научной конференции «Гагарин-ские чтения», Москва, МАТИ, 2008 г.

• на XXIII научно-технической конференции «Направления развития и применения перспективных вычислительных средств и новых информационных технологий в ВВТ РКО», Москва, в/ч 03425, 2007 г.

• на XIV Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», Москва, МГУ им. М. В. Ломоносова, 2007 г.

• на XXXIII Международной молодежной научной конференции «Гагарин-ские чтения», Москва, МАТИ, 2007 г.

• на семинарах секции программного обеспечения ЗАО «МЦСТ» в 20062008 гг.

Публикации

По теме диссертации опубликовано 10 печатных работ:

1. Галазин А. В., Грабежной А. В., Нейман-заде М. И. Оптимизация размещения данных для эффективного исполнения программ на архитектуре с многобанковой кэш-памятью данных // Информационные технологии, № 3, 2008, С. 35-39.

2. Галазин А. В., Ступаченко Е. В., Шлыков С. Л. Программный метод предварительной подкачки кода в архитектурах со статическим планированием // Программирование № 1, 2008, С. 67-74.

3. Галазин А. Б. Методы оптимизации размещения данных для архитектур с многобанковой кэш-памятью данных // Научные труды XXXIV Международной молодежной научной конференции «Гагаринские чтения», т. 6. М.: МАТИ, 2008, С. 167-168.

4. Галазин А. В., Степаненков А. М., Ступаченко Е. В. Программная предварительная подкачка кода для микропроцессора Эльбрус-ЗМ // Информационные технологии, № 11, 2007, С. 35-42.

5. Галазин А. Б., Грабежной А. В. Эффективное взаимодействие микропроцессора и подсистемы памяти с использованием асинхронной предварительной подкачки данных // Информационные технологии, № 5, 2007, С. 26-31.

6. Галазин А. Б. Методы предварительной подкачки в микропроцессоре Эльбрус-ЗМ // Научные труды XXXIII Международной молодежной научной конференции «Гагаринские чтения», т. 6. М.: МАТИ, 2007, С. 213214.

7. Галазин А. Б. Предварительная подкачка кода для микропроцессора Эльбрус-ЗМ // Материалы докладов XIV Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов». / Отв. ред. И. А. Алешковский, П. Н. Костылев. [Электронный ресурс] - М.: Издательский центр Факультета журналистики МГУ им. М.В. Ломоносова, 2007. - 1 электрон, опт. диск (CD-ROM).

8. Галазин А. Б. Оптимизация участков кода с малым количеством исполнений // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск № 9, 2006, С. 58-63.

9. Дроздов А. 10., Новиков С. В., Боханко А. С., Галазин А. Б. Def-Use граф и методы его использования в современных оптимизирующих компиляторах // Компьютеры в учебном процессе, № 12. 2005. С. 3-14.

10. Дроздов А. Ю., Новиков С. В., Боханко А. С., Галазин А. Б. Глобальный граф потока данных и его роль в проведении оптимизирующих преобразований программ // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск № 8, 2005, С. 7887.

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

Диссертация состоит из введения, четырех глав, заключения и приложения. Список литературы составляет 77 наименований. Объем диссертации составляет 149 страниц текста. Диссертация содержит 55 рисунков.

4.7. Выводы

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

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

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

4. Совместная реализация алгоритма повышения равномерности загрузки банков кэша и преобразований промежуточного представления позволила снизить количество внутренних блокировок кэш-памяти для задач пакета SPEC CFP95 на 61,9%, а для задач пакета SPEC CFP2000 на 22%, и привела к повышению производительности вычислительного комплекса на задачах пакета SPEC CFP95 на 10,1%, а на пакете SPEC CFP2000 на 5,9%.

Заключение

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

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

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

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

2. Предложена новая классификация шаблонов хранения и обращения к данным в циклах.

3. Разработан комплексный алгоритм программной поддержки комбинированного метода предварительной подкачки 0-линейно регулярных данных и метод оценки целесообразности применения комбинированного метода предварительной подкачки 0-линейно регулярных данных, что в совокупности позволило в среднем повысить производительность на 24% на задачах пакета SPEC CFP2000.

4. Разработаны алгоритмы программной предварительной подкачки п-(не)линейно (псевдо)регулярных и п-кольцевых рекуррентных данных, учитывающие особенности архитектуры, что дополнительно в среднем улучшило на 18,5% и 9,1% показатели производительности задач с соответствующим контекстом.

5. Предложен метод предварительной подкачки кода, взаимодействующий с другими оптимизирующими компонентами компилятора, реализация которого позволила дополнительно в среднем на 3,2% ускорить задачи пакета SPEC CINT2000.

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

7. Разработан алгоритм и предварительные преобразования, позволившие решить задачу определения оптимального взаимного расположения глобальных массивов, что дополнительно в среднем улучшило показатели производительности задач пакета SPEC CFP95 на 10% и пакета SPEC CFP2000 на 5,9%.

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

1. Colwell, R.P., Nix, R.P., O'Donnell, J.J., Papworth, D.B., Rodman, P.K. A VL1. architecure for a trace scheduling compiler. IEEE Transactions on Computers, volume 37, № 8:pp 967-979. — 1988

2. Ellis, J.R. Bulldog: A Compiler for VLIW Architectures. MIT Press, 1986

3. Standard Performance Evaluation Corporation. The SPEC Benchmark Suites. CPU-intensive benchmark suite. Electronic resource., — 1995-2000. http://www.spec.org/cpu

4. Uhlig, R., Nagle, D., Mudge, T.N., Sechrest, S., Emer, J.S. Instruction fetching: Coping with code bloat. Proceedings of the 22nd Annual International Symposium on Computer Architecture, pp 345-356. Santa Margherita Ligure, Italy, 1995

5. Denning, P.J. The locality principle. Commun. ACM, volume 48, № 7:pp 19-24. 2005

6. Sun Microsystems, Inc. OpenSPARC Tl Micro Architecture Specification. — 2006. http://opensparc-tl.sunsource.net

7. Intel Corporation. Introduction to Microarchitectural Optimization for Itaium 2 Processors. — 2002. http://developer.intel.com

8. Santhanam, V., Gornish, E.H., Hsu, W.C. Data prefetching on the hp pa-8000. Proceedings of the 24th Annual International Symposium on Computer Architecture, pp 264-273. ACM Press, Denver, Colorado, United States, 1997

9. Silicon Graphics, I. MlPSpro Compiler and Preformance Tuning Guide. Mountain View, CA, USA. 1997

10. Smith, A.J. Cache memories. ACM Computing Surveys, volume 14, 3:pp 473-530. 1982

11. Porterfield, A. Software Methods for Improvement of Cache Performance on Supercomputer Applications, phdthesis, Rice University. — 1989

12. Klaiber, A.C., Levy, H.M. An architecture for software-controlled data prefetching. ISCA '91: Proceedings of the 18th annual international symposium on Computer architecture, pp 43-53. ACM, New York, NY, USA, 1991

13. Przybylski, S. The performance impact of block sizes and fetch strategies. ISCA '90: Proceedings of the 17th annual international symposium on Computer Architecture, pp 160-169. ACM Press, New York, NY, USA, 1990

14. Vanderwiel, S.P., Lilja, D.J. When caches aren't enough: Data prefetching techniques. IEEE Computer, volume 30, № 7:pp 23-30. — 1997

15. Dahlgren, F., Dubois, M., Stenstrom, P. Fixed and adaptive sequential prefetching in shared memory multiprocessors. Proceedings of the 1993 International Conference on Parallel Processing, volume 1: Architecture, pp 5663. 1993

16. Fu, J.W.C., Patel, J.H. Data prefetching in multiprocessor vector cache memories. ISCA '91: Proceedings of the 18th annual international symposium on Computer architecture, pp 54-63. ACM Press, New York, NY, USA, 1991

17. Robert G. Babb, I., editor. Programming parallel processors, chapter Alliant FX/8, pp 155-183. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1987

18. Lee, R.L., Yew, P.C., Lawrie, D.H. Data prefetching in shared memory multiprocessors. ICPP '87: International Conference on Parallel Processing, pp 28-31. 1987

19. Baer, J.L., Chen, T.F. An effective on-chip preloading scheme to reduce data access penalty. Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on Supercomputing, pp 176-186. ACM Press, New York, NY, USA, 1991

20. Fu, J.W.C., Patel, J.H., Janssens, B.L. Stride directed prefetching in scalar processors. MICRO 25: Proceedings of the 25th annual international symposium on Microarchitecture, pp 102-110. IEEE Computer Society Press, Los Alamitos, CA, USA, 1992

21. Chen, T.F., Baer, J.L. Effective hardware based data prefetching for high-performance processors. IEEE Transaction on Computers, volume 44, № 5:pp 609-623. 1995

22. Harrison, L., Mehrotra, S. A data prefetch mechanism for accelerating general computation, techreport 1351, Universityof Illinois at Urban a-Champaign, Dept. of Computer Science, Urbana, IL, USA. — 1994

23. Галазин, А.Б. Оптимизация участков кода с малым количеством исполнений / А.Б. Галазин // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН. — 2006. — Вып. 9. — С. 58-63.

24. Дроздов, А.Ю., Корнев, P.M., Боханко, А.С. Индексный анализ зависимостей по данным / А.Ю. Дроздов, P.M. Корнев, А.С. Боханко // Информационные технлогии и вычислительные системы. — 2004. — Вып. 3. — С. 27-37.

25. Дроздов, А.Ю., Степаненков, A.M. Технология оптимизации циклов для архитектур с аппаратной поддержкой конвейеризации / А.Ю. Дроздов, A.M. Степаненков // Информационные технлогии и вычислительные системы. — 2004. Вып. 3. - С. 52-62.

26. Bacon, D.F., Graham, S.L., Sharp, O.J. Compiler transformations for high-performance computing. ACM Computing Surveys, volume 26, JVS 4:pp 345-420. 1994

27. Новиков, С.В. Развитие методов глобального планирования для архитектур с явно выраженной параллельностью. Дис. канд. тех. наук: 05.13.11, ЗАО «МЦСТ», М. 2005

28. Smith, J.Е., Hsu, W.C. Prefetching in supercomputer instruction caches. Supercomputing '92: Proceedings of the 1992 ACM/IEEE conference on Supercomputing, pp 588-597. IEEE Computer Society Press, Los Alamitos, CA, USA, 1992

29. Zhang, Y., Haga, S., Barua, R. Execution history guided instruction prefetching. Proceedings of the 2002 International Conference on Supercomputing, pp 199208. ACM, New York City, NY, USA, 2002

30. Pierce, J., Mudge, T. Wrong-path instruction prefetching. MICRO 29: Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, pp 165-175. IEEE Computer Society, Washington, DC, USA, 1996

31. Young, H.C., Shekita, E.J. An intelligent i-cache prefetch mechanism. ICCD '93: Proceedings of the 1993 International Conference on Computer Design: VLSI in Computers and Processors, pp 44-49. IEEE Computer Society, Cambridge, MA, USA, 1993

32. Oehler, R.R., Blasgen, M.W. IBM RISC System/6000: Architecture and performance. IEEE Micro, volume 11, № 3:pp 14-17, 56-62. — 1991

33. Le, H.Q., Starke, W.J., Fields, J.S., O'Connell, F.P., Nguyen, D.Q., Ronchetti, B.J., Sauer, W.M., Schwarz, E.M., Vade, M.T. Ibm power6 microarchitecture. IBM Journal of Research and Development, volume 51, № 6:pp 639-662. — 2007

34. Xia, C., Torrellas, J. Instruction prefetching of systems codes with layout optimized for reduced cache misses. Proceedings of the 23rd Annual International Symposium on Computer Architecture, pp 271-282. Philadelphia, PA, US, 1996

35. Luk, C.K., Mowry, T.C. Architectural and compiler support for effective instruction prefetching: a cooperative approach. ACM Transactions on Computer Systems, volume 19, № l:pp 71-109. — 2001

36. Driesen, K., Holzle, U. Accurate indirect branch prediction. ISCA '98: Proceedings of the 25th annual international symposium on Computer architecture, pp 167-178. IEEE Computer Society, Washington, DC, USA, 1998

37. Chang, P.Y., Ilao, E., Patt, Y.N. Target prediction for indirect jumps. ISCA '97: Proceedings of the 24th annual international symposium on Computer architecture, pp 274-283. ACM, New York, NY, USA, 1997

38. Grunwald, D., Klauser, A., Manne, S., Pleszkun, A. Confidence estimation for speculation control. ISCA '98: Proceedings of the 25th annual internationalsymposium on Computer architecture, pp 122-131. IEEE Computer Society, Washington, DC, USA, 1998

39. Yeager, K.C. The MIPS R10000 superscalar microprocessor. IEEE Micro, volume 16, № 2:pp 28-40. — 1996

40. Annavaram, M., Patel, J.M., Davidson, E.S. Call graph prefetching for database applications. ACM Trans. Comput. Syst., volume 21, № 4:pp 412-444. — 2003

41. Standard Performance Evaluation Corporation. The SPEC Benchmark Suites. Java Application Server. Electronic resource. — 1995-2008. http://www.spec.org/jAppServer2004/

42. Harizopoulos, S., Ailamaki, A. Improving instruction cache performance in OLTP. ACM Trans. Database Syst., volume 31, № 3:pp 887-920. 2006

43. Transaction Processing Performance Council. The TPC Benchmark C. On-line transaction processing (OLTP) benchmark.Electronic resource. — 1992-2008. http://tpc.org/tpcc/

44. Галазин, А.В., Степаненков, A.M., Ступаченко, E.B. Программная предварительная подкачка кода для микропроцессора Эльбрус-ЗМ / А.Б. Галазин, A.M. Степаненков, Е.В. Ступаченко // Информационные технологии. 2007. - Вып. 11. - С. 35-42.

45. Lam, M.S., Wolf, М.Е. A data locality optimizing algorithm. PLDI '91: Proceedings of the ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation, pp 30-44. ACM, New York, NY, USA, 1991

46. Wolf, M.E., Lam, M.S. A loop transformation theory and an algorithm to maximize parallelism. IEEE Trans. Parallel Distrib. Syst., volume 2, № 4:pp 452-471. 1991

47. Cierniak, M., Li, W. Unifying data and control transformations for distributed shared-memory machines. PLDI '95: Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, pp 205—217. ACM, New York, NY, USA, 1995

48. Kandemir, M., Ramanujam, J., Choudhary, A. A compiler algorithm for optimizing locality in loop nests. ICS '97: Proceedings of the 11th international conference on Supercomputing, pp 269-276. ACM, New York, NY, USA, 1997

49. Manjikian, N., Abdelrahman, T.S. Fusion of loops for parallelism and locality. IEEE Trans. Parallel Distrib. Syst., volume 8, № 2:pp 193-209. 1997

50. Singhai, S., McKinley, K.S. A parametrized loop fusion algorithm for improving parallelism and cache locality. Computer Journal, volume 40, № 6:pp 340-355.- 1997

51. McKinley, K.S., Carr, S., Tseng, C.W. Improving data locality with loop transformations. ACM Trans. Program. Lang. Syst., volume 18, № 4:pp 424-453.- 1996

52. Gao, G.R., Olsen, R., Sarkar, V., Thekkath, R. Collective loop fusion for array contraction. Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, pp 281-295. Springer-Verlag, London, UK, 1993

53. Carr, S., Kennedy, K. Compiler blockability of numerical algorithms. Supercomputing '92: Proceedings of the 1992 ACM/IEEE conference on Supercomputing, pp 114-124. IEEE Computer Society Press, Los Alamitos, CA, USA, 1992

54. Irigoin, F., Triolet, R. Supernode partitioning. POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pp 319-329. ACM, New York, NY, USA, 1988

55. Wolfe, M. More iteration space tiling. Supercomputing '89: Proceedings of the 1989 ACM/IEEE conference on Supercomputing, pp 655-664. ACM, New York, NY, USA, 1989

56. Chame, J., Moon, S. A tile selection algorithm for data locality and cache interference. ICS '99: Proceedings of the 13th international conference on Supercomputing, pp 492-499. ACM, New York, NY, USA, 1999

57. Coleman, S., McKinley, K.S. Tile size selection using cache organization and data layout. PLDI '95: Proceedings of the ACM SIGPLAN 1995 conferenceon Programming language design and implementation, pp 279-290. ACM, New York, NY, USA, 1995

58. Hsu, W. Array padding for higher memory throughput in the presence of dirty misses. U.S. Patent 6,041,393. — 2000

59. Bailey, D.H. On the behaviour of cache memories with strided data access, techreport RNR-92-015, NASA Ames Research Center, Monffett, CA, USA. — 1992

60. Rivera, G., Tseng, C.W. Eliminating conflict misses for high performance architectures. Proceedings of the 1998 International Conference on Supercomputing, pp 353-360. ACM Press, Melbourne, Australia, 1998

61. Rivera, G., Tseng, C.W. Data transformations for eliminating conflict misses. PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, pp 38-49. ACM Press, New York, NY, USA, 1998