суббота, 9 мая 2015 г.

Лекции по оптимизирующим компиляторам

В последние несколько месяцев занимался довольно новым для себя делом - читал лекции по курсу "Оптимизирующие компиляторы". Раньше мне не приходилось читать лекции (ну или почти не приходилось), да и предмет не самый распространённый. В общем о том что получилось, что хочется дополнить и исправить расскажу ниже.
Сам по себе курс длится два семестра, я читаю только первый. В нём предполагается рассказать в целом про оптимизирующие компиляторы и сами оптимизации. Курс был составлен на основе моих конспектов этого курса, прочитанного в МФТИ в 2013 году.
Теперь про содержимое самого курса. Сейчас он состоит из 11 лекций:
  1. Введение в оптимизирующие компиляторы
  2. Введение в теорию языков и автоматов. Лексический анализ.
  3. Введение в теорию языков и автоматов. Синтаксический анализ.
  4. Алгоритмы на графах, используемые в компиляторах
  5. Структуры данных в оптимизирующих компиляторах
  6. Оптимизации управления
  7. Потоковые оптимизации
  8. Цикловые оптимизации
  9. Цикловые оптимизации (часть 2). Оптимизации памяти.
  10. Анализ указателей
  11. Планирование кода. Межпроцедурные оптимизации.
Я хочу дорабатывать данный курс. Пока мне видятся не лучшими решениями следующие вещи:
  • Наличие второй и третьей лекции. Теорию автоматов нужно изучать отдельно, а информацию по фронтенду можно слить в одну лекцию. Но не думаю что это подойдёт для кафедры, на которой читается курс - отдельно теории автоматов у них нет.
  • В девятой лекции идёт остаток восьмой про циклы и ещё треть лекции про оптимизации памяти. По идее про оптимизации памяти нужна отдельная лекция, но у меня по данной теме очень мало информации.
  • Одиннадцатая лекция тоже содержит две разные темы, их неплохо бы читать отдельно.
Есть ещё некоторые замечания по каждой лекции в отдельности, но об этом я расскажу когда (если) выложу слайды.
Ещё есть масса тем, про которые или не рассказано ничего, или сказано очень мало:

  • ничего нет про распараллелвание
  • почти ничего нет про режим -fwhole/-flto
  • мало про профилирование
  • ничего нет про векторизацию
  • почти ничего про межпроцедурные анализы
  • ничего про оптимизации C++
  • ничего про средства отладки/разработки/workflow
В общем сейчас у меня появились небольшие наработки по данному курсу, есть что и куда пилить. Но хотелось бы узнать у сообщества: что ещё следует читать в курсе оптимизирующих компиляторов, возможно кто-то знает удачные примеры таких курсов?

4 комментария:

  1. Анонимный28 мая 2015 г., 10:01

    Здравствуйте, а поясните пожалуйста про Эль-76 в советских эльбрусах - это был компилируемый язык в байткод как Java или как скриптовый язык как Lisp/JS?

    И как он так поддерживался машиной что на нем писали и программы и операционную систему, а ассемблеры вообще отсутствовали? Мне известно про всякие Java/lisp машины, но в моем представлении они являли собой - ну вот как GPU и OpenCL сейчас, но эльбрус то ведь вполне себе общезадачным был, на нем вроде даже и алгол работал.

    Современный эльбрус тоже ведь все это поддерживает (всякие указатели на типы) которые для поддержки высокоуровневых языков и внедрялись, да и потом Эльбрус-3 для тех же военных создавался, которые эксплуатировали Эльбрус 1 и 2, он просто не всего того же не поддерживать.

    Возможно ли на современном так же как работали Эльбрус-2 и Эль-76, организовать Эльбрус + ECMA Script 6 например?

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

    ОтветитьУдалить
    Ответы
    1. Давайте про Эль-76 и Эльбрус-2 я отвечу позже, т.к. про него особо ничего не знаю, и у меня уйдёт некоторое время на исследование, а про современный Эльбрус можно вот что сказать.

      > Современный эльбрус тоже ведь все это поддерживает (всякие указатели на типы) которые для поддержки высокоуровневых языков и внедрялись

      Я не очень понял что Вы имеете ввиду. Если Вы про защищённый режим, то там действительно есть теги, содержащие информацию о типах, но они служат не для поддержки высокоуровневых языков, а для контроля доступа к данным и используются для сборки обычных C/C++ программ.

      > Возможно ли на современном так же как работали Эльбрус-2 и Эль-76, организовать Эльбрус + ECMA Script 6 например?

      Если это и возможно технически (в чём я не уверен), то это совершенно ни к чему. Сейчас Вы просто скомпилируете движок языка, написанный на Си, и он будет работать. Если движок написан хорошо, возможно он даже тормозить не будет.

      Удалить
    2. Вот чего нашел:
      http://www.electriz.ru/postroenie-effekt-mnogoproc-sistem/perspektivnye-modeli-mnogoprocessornyh-evm-1.html
      http://www.electriz.ru/postroenie-effekt-mnogoproc-sistem/perspektivnye-modeli-mnogoprocessornyh-evm-2.html
      http://www.electriz.ru/postroenie-effekt-mnogoproc-sistem/perspektivnye-modeli-mnogoprocessornyh-evm-3.html (и так статей 6 где то, )

      > Рассматриваемая схема предполагает проведение разработки, ориентированной на языки высокого уровня, с использованием накопленного опыта создания системы «Эльбрус», проведение с самого начала значительных работ по оптимизирующему транслятору так, чтобы алгоритм, изложенный на одном из существующих языков высокого уровня, включая ЭЛЬ-76, после трансляции давал высокоэффективные программы фактически на уровне микропрограмм.
      > > Схема информационной системы будущих моделей «Эльбрус»
      > В этой схеме отсутствует уровень системы команд, он заменен уровнем микрокоманд.
      и:
      > Как и предыдущие модели, «Эльбрус-3» основан на теговой архитектуре, позволяющей последовательно проводить динамическую типизацию данных, а также обеспечивающей высокий уровень программирования и исключение ассемблера.

      Я вообще к чему это все -
      на дворе 2015 год а в интел с пафосом рассказывают как эффективно программировать используя регистры AVX. Диды в 70х уже с одними объектами работали а они все свой потешный SIMD наяривают.

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

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

      Удалить