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

• Галазин, Александр Борисович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Галазин, Александр Борисович

Введение.

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%.

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

Список литературы диссертационного исследования кандидат технических наук Галазин, Александр Борисович, 2008 год

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