Труды института системного программирования РАН
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Труды ИСП РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Труды института системного программирования РАН, 2016, том 28, выпуск 5, страницы 175–198
DOI: https://doi.org/10.15514/ISPRAS-2016-28(5)-11
(Mi tisp75)
 

Ускорение оптимизации программ во время связывания

К. Ю. Долгорукова, С. В. Аришин

Институт системного программирования РАН
Список литературы:
Аннотация: В данной статье речь идет о двух методах ускорения процесса сборки программы: распараллеливании межпроцедурной оптимизации и о легковесном методе проведения оптимизаций. Ускорение в первом случае достигается за счет горизонтального масштабирования системы оптимизации времени связывания. Во втором случае метод представляет собой работу исключительно на аннотациях, что позволяет работать с минимально необходимой информацией вместо кода всей программы целиком. Проблема горизонтальной масштабируемости системы всегда связана с необходимостью разделения большой задачи на несколько подзадач, которые могут быть выполнены независимо и параллельно. Масштабирование оптимизаций времени связывания - непростая задача, так как оптимизирующие преобразования работают последовательно на всем промежуточном представлении программы, и результат их работы зависит от предыдущих преобразований. Для оптимизации на этапе связывания необходимо разделить промежуточное представление компилируемой программы на участки, минимизируя зависимости между ними, и оптимизировать эти участки отдельно. Для анализа программы используется граф вызовов. Таким образом, задача сводится к тому, чтобы разделить граф вызовов на несколько слабо связанных друг между другом компонент. Данная задача относится к одной из сложных комбинаторных проблем, и нахождение оптимального решения - NP-полная задача. Тем не менее, качество работы алгоритма зависит от свойств графа, поэтому целесообразно исследовать свойства графа вызовов в контексте оптимизаций времени связывания и подобрать к нему приемлемый алгоритм, проверив работу на реальных программах. Основная задача данного исследования - найти легковесный и эффективный метод разбиения структуры программы таким образом, чтобы как можно меньше ухудшить производительность собираемых программ при независимой оптимизации участков кода. В статье представлен новый метод разбиения графа вызовов программ, проведено его сравнение с некоторыми другими существующими методами для графов вызовов тестовых программ. Также описана реализация предложенного метода в системе LLVM, представлены результаты сравнения производительности программ, собранных в один поток и в несколько потоков. Запуск на 4-х потоках показал ускорение процесса сборки в среднем на 31%, тогда как производительность по сравнению с собранными в один поток программами упала в среднем на 3%. Для легковесного метода оптимизаций описана реализация преобразования удаления мертвого кода. Также приведены результаты тестирования в совокупности с ленивой загрузкой кода.
Ключевые слова: компиляторы, оптимизация времени связывания, масштабирование, разбиение графов.
Реферативные базы данных:
Тип публикации: Статья
Образец цитирования: К. Ю. Долгорукова, С. В. Аришин, “Ускорение оптимизации программ во время связывания”, Труды ИСП РАН, 28:5 (2016), 175–198
Цитирование в формате AMSBIB
\RBibitem{DolAri16}
\by К.~Ю.~Долгорукова, С.~В.~Аришин
\paper Ускорение оптимизации программ во время связывания
\jour Труды ИСП РАН
\yr 2016
\vol 28
\issue 5
\pages 175--198
\mathnet{http://mi.mathnet.ru/tisp75}
\crossref{https://doi.org/10.15514/ISPRAS-2016-28(5)-11}
\elib{https://elibrary.ru/item.asp?id=27679159}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/tisp75
  • https://www.mathnet.ru/rus/tisp/v28/i5/p175
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Труды института системного программирования РАН
    Статистика просмотров:
    Страница аннотации:150
    PDF полного текста:131
    Список литературы:31
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024