Прискорення оптимізації програм під час зв'язування

  1. анотація
  2. Ключові слова

К.Ю. Долгорукова (ІСП РАН, Москва, Росія)
C.В. Арішин (ІСП РАН, Москва, Росія)

анотація

У даній статті мова йде про два методи прискорення процесу складання програми: розпаралелювання межпроцедурной оптимізації і про легковесном методі проведення оптимізацій. Прискорення в першому випадку досягається за рахунок горизонтального масштабування системи оптимізації часу зв'язування. У другому випадку метод являє собою роботу виключно на анотаціях, що дозволяє працювати з мінімально необхідною інформацією замість коду всієї програми цілком. Проблема горизонтальної масштабованості системи завжди пов'язана з необхідністю поділу великого завдання на кілька підзадач, які можуть бути виконані незалежно і паралельно. Масштабування оптимізацій часу зв'язування - непросте завдання, тому що оптимізують перетворення працюють послідовно на всіх проміжному поданні програми, і результат їх роботи залежить від попередніх перетворень. Для оптимізації на етапі зв'язування необхідно розділити проміжне представлення модульна програми на ділянки, мінімізуючи залежності між ними, і оптимізувати ці ділянки окремо. Для аналізу програми використовується граф викликів. Таким чином, завдання зводиться до того, щоб розділити граф викликів на кілька слабко пов'язаних один між одним компонент. Дане завдання відноситься до однієї з складних комбінаторних проблем, і знаходження оптимального рішення - NP-повна задача. Проте, якість роботи алгоритму залежить від властивостей графа, тому доцільно досліджувати властивості графа викликів в контексті оптимізацій часу зв'язування і підібрати до нього прийнятний алгоритм, перевіривши роботу на реальних програмах. Основне завдання даного дослідження - знайти легкий і ефективний метод розбиття структури програми таким чином, щоб якомога менше погіршити продуктивність зібраних програм за незалежної оптимізації ділянок коду. У статті представлений новий метод розбиття графа викликів програм, проведено його порівняння з деякими іншими існуючими методами для графів викликів тестових програм. Також описана реалізація запропонованого методу в системі LLVM, представлені результати порівняння продуктивності програм, зібраних в один потік і в кілька потоків. Запуск на 4-х потоках показав прискорення процесу складання в середньому на 31%, тоді як продуктивність в порівнянні з зібраними в один потік програмами впала в середньому на 3%. Для легкого методу оптимізацій описана реалізація перетворення видалення мертвого коду. Також наведені результати тестування в сукупності з ледачою завантаженням коду.

Ключові слова

видання

Праці Інституту системного програмування РАН, том 28, вип. 5, 2016, стор. 175-198.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514 / ISPRAS-2016-28 (5) -11

Повний текст статті у форматі pdf К Повернутися до змісту томи