авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 | 3 | 4 |

Компонентный подход к построению оптимизирующих компиляторов

-- [ Страница 1 ] --

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

Дроздов Александр Юльевич

Компонентный подход к построению оптимизирующих компиляторов

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

Автореферат

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

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

Москва 2010

Работа выполнена в Институте Точной Механики и Вычислительной техники им. С.А. Лебедева

Официальные оппоненты: доктор физико-математических наук, чл.-корр. РАН Воеводин Владимир Валентинович доктор физико-математических наук Галатенко Владимир Антонович доктор физико-математических наук Крюков Виктор Алексеевич
Ведущая организация Учреждение Российской академии наук Вычислительный центр им. А. А. Дородницына  РАН

Защита состоится « 16 » декабря 2010 г. в 15 ч. 00 мин. на заседании диссертационного совета Д.002.087.01 при Институте системного программирования РАН по адресу:

109004, Москва, ул. Александра Солженицына, д.25,

Институт системного программирования РАН, конференц-зал (комн. 110).

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН.

Автореферат разослан «___» 2010 г.

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

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

кандидат физико-математических наук /Прохоров С.П./

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

Актуальность работы

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

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



Разработка каждого отдельного решения требует временных затрат в пределах десятков человеко-лет и значительных затрат по сопровождению этих решений. В качестве примеров можно привести оптимизирующие компиляторы компаний Intel, Sun Microsystems, Transmeta, Microsoft, IBM, HP, Elbrus, и др. Все эти компании создали свои собственные, не совместимые друг с другом коммерческие продукты с высоким уровнем внутренней сложности. Этот процесс продолжает нарастать, так как нужно соответствовать современной тенденции увеличения разнообразия аппаратных решений (Multi core, Many core, EPIC и т.д.).

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

Несколько последних десятилетий вычислительная техника развивалась бурными темпами, затрагивая всё более широкий круг проблем. И если в 60-е и 70-е годы прошлого века был только обозначен потенциал применения этой отрасли, проводились исследования фундаментальных принципов выполнения вычислений, то к началу XXI века ареал распространения вычислительной техники, её значение практически для всех областей деятельности человека достигли огромных масштабов. Уровень развития и применения вычислительных технологий в настоящее время является одним из важнейших стратегических факторов развития не только научного потенциала страны, но и всего общества в целом.

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

Динамическое распараллеливание вычислений наиболее распространено в современных микропроцессорах и продолжает обеспечивать некоторый рост производительности исполнения вычислительных задач. Но дальнейшее увеличение параллельности на уровне операций в архитектурах процессоров может быть ограничено квадратичным усложнением логики проверок в аппаратуре при планировании выполнения команд. Поэтому статический подход к реализации пооперационной параллельности в процессе компиляции сейчас активно развивается как альтернатива суперскалярным (с динамическим планированием вычислений) процессорам. Для обозначения такого рода архитектур во второй половине 90-х годов появился термин EPIC (Explicitly Parallel Instruction Computing) - архитектура с явно выраженной параллельностью на уровне команд.

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

Цель диссертационной работы

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

Исходя из вышеизложенного, для достижения поставленной цели в работе выполняются:

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

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

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

Предмет исследования

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

      • Алгоритмические основы функционирования блоков оптимизирующих компиляторов:
  • методы статического анализа программ;
  • методы планирования программ для архитектур с явной параллельностью на уровне команд, включая планирование выполнения циклических участков программы с использованием аппаратной поддержки;
  • методы многопоточного распараллеливания программ на основе технологии OpenMP;
  • методы группирования оптимизаций для ускорения работы компилятора и для получения более эффективного машинного кода;
  • оценка влияния использования предложенных методов анализа, планирования и оптимизаций программ на конечную производительность результирующего кода.
      • Методология разбиения оптимизирующего компилятора на блоки различного уровня абстракции;
      • Методология построения блоков оптимизирующей компиляции, обеспечивающая параллельный (одновременный) запуск одних и тех же оптимизаций для различных участков программы;
      • Методология портирования блоков оптимизирующей компиляции в контексте существующих инфраструктур оптимизирующей компиляции (GCC, phoenix, ACE, open64, pathscale, …);
      • Методология построения готовых продуктов в области оптимизирующих компиляторов (полнофункциональный компилятор, анализатор программ, автоматический распараллеливатель, векторизатор) на основе предложенных методологий и алгоритмов.

Методы исследования заимствованы из областей системного программирования, методологии компиляции, теории графов, теории абстрактной интерпретации, теории Диофантовых уравнений и неравенств, математической логики. Эффективность предложенных методов оценивалась путем вычисления значений ключевых параметров (время работы компилятора, производительность результирующего кода и т.п.), и сравнения значений этих параметров, со значениями, полученными с помощью традиционных подходов. Для проведения замеров использовался инструментальный комплекс в составе оптимизирующего компилятора и потактной модели архитектуры «Эльбрус-3М» и автоматический распараллеливатель, работающий в составе компиляторной технологии GCC (www.gnu.org). Замеры производились на пакетах задач Spec92, Spec95 и Spec2006.

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

Научной новизной в диссертации обладают:

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

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





Апробация

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

Практические результаты работы докладывались на международном форуме «Салон инноваций и инвестиций — 2008», который проходил в Москве, ВВЦ, в 2008 году. Проект «Разработчик оптимизирующих компиляторов» был удостоен золотой медали VIII Московского международного салона инноваций и инвестиций.

Результаты работы докладывались на IХ Санкт-Петербургской Международной конференции «Региональная информатика–2004 (РИ–2004)» в 2004 г., на Международной молодежной научной конференции «XXX Гагаринские чтения» (Москва, 2004 г.), XXI Научно-технической конференции войсковой части 03425 (Москва, в/ч 03425, 2003 г.), а также докладывались и обсуждались на семинарах и научно-технических совещаниях ЗАО “МЦСТ” (2003-2005 гг.), Института микропроцессорных вычислительных систем РАН (2004-2005 гг.), Института точной механики и вычислительной техники им. С.А. Лебедева РАН (2007-2008 гг.), Института системного программирования РАН (2008), ОАО «Научно-исследовательский центр электронной вычислительной техники» (НИЦЭВТ) (2008) и НИВЦ МГУ им. Ломоносова (2009, 2010).

Публикации

По теме диссертации опубликованы 36 печатных работ. Из них 14 в изданиях, рекомендованных ВАК.

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

Диссертация состоит из пяти глав и заключения. Диссертация содержит 307 страниц, 124 рисунка, 23 таблицы. Список литературы насчитывает 160 наименований.

Краткое содержание работы

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

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

Структурные аспекты

В качестве языка реализации был выбран язык C++, как проверенный инструмент отображения абстракций объектно-ориентированного проектирования.

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

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

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

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

- использование единого стиля программирования;

- использование методов и практик объектно-ориентированного проектирования и программирования;

- использование средств автоматического обнаружения ошибок путем инструментирования кода программ с последующим исполнением;

- использование средств внутренней верификации и отладки;

- использование средств визуализации внутренних структур данных;

- использование средств автоматической документации программ;

- глубокое тестирование программ.



Pages:   || 2 | 3 | 4 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

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