Сравнение эффективности автоматической оптимизации на основе полиэдральной модели



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

Comparison of the efficiency of the automatic optimization based on the polyhedral model

Sushko Sergey, doctoral student, Pukhov Institute for Modelling in Energy Engineering, Kiev, Ukraine

Chemeris Alexander, PhD. of CS, Pukhov Institute for Modelling in Energy Engineering, Kiev, Ukraine

Small parts of the source code that consume more resources are computational loops. Polyhedral model is one of the mostefficient mathematical models that allows to represent arbitrary loop as some abstract description. Polyhedral model is obtained from source code and thencan be altered by using different approaches and finally reverted to the newoptimized source code. This paper contains optimization results of the softwarethat uses polyhedral model.

Keywords: automatic software optimization, polyhedral model, pluto software

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

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

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

Чтобы представить циклы в качестве модели, пригодной для дальнейшего анализа и обработки используют полиэдральную модель или метод многогранника (polyhedral model и polytope method). Полиэдральная модель является математической основой для представления циклов произвольной вложенности иможет быть использована для оптимизации программ. Полиэдральная модель трактует каждую итерацию цикла внутри вложенных циклов как точки решетки внутри геометрических объектов, называемых многогранники, и использует аффинные преобразования, а затем преобразовывает вновь полученные многогранники обратнов эквивалентный оптимизированный исходный код, проходя по всем узлам многогранника.

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

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

Наданный момент существуют несколько пакетов программного обеспечения, предоставляющего функционал, обеспечивающий автоматическую оптимизацию циклов. Рассматривая существующие пакеты с точки зрения охвата возможных подходов,полноты описания и научной базы, которая лежит в их основе, объектом исследования был выбран свободно распространяемый пакет программного обеспечения Pluto версии 0.11.4. Помимо опций, непосредственно влияющих на метод оптимизации, пакет имеет опцию включения распараллеливания через библиотеку OpenMP. Это также может оказывать значительный эффект на общую производительность оптимизированного алгоритма.

Для проверки эффективности опций оптимизаций данного пакета был выбран набор тестовых программ PolyBench/C 4.1. Он содержит в себе 29 коротких программ на С, каждая изкоторых содержит некий прикладной алгоритм. Кроме того, каждая программа включает в себе модуль замера времени своего выполнения, которое выводится по окончанию расчета. Все указанные особенности удовлетворяют задаче проверки эффективности оптимизации различных исходных кодов и измерения времени их выполнения. В качестве аппаратной тестовой платформы применялся настольный ПК на базе четырехядерного процессора Intel Core i5-4670K.

Тестирование представляет собой ряд последовательных действий. На первом этапе были скомпилированы и запущены на выполнение изначальные исходные коды тестового пакета с целью получения исходного времени выполнения каждого теста. Затем для каждого тестового примера выполнялся запуск пакета оптимизации Plutoс разными опциями. Полученный оптимизированный исходный код так же компилировался и затем замерялось время его выполнения. Полученные данные представлены натаблице ниже.

Таблица 1. Таблица времени выполнения тестовых программ при различных опциях оптимизации

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

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

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

Bibliography:

  1. Uday Bondhugula. EffectiveAutomatic Parallelization and Locality Optimization Using The Polyhedral model: дис. канд. / Uday Bondhugula. - The Ohio State University, 2010. - 193 c.

  2. C´edric Bastoul. Code generation in the polyhedral model is easier than you think. In IEEE International Conference on Parallel Architectures and Compilation Techniques, pages 7–16, September 2004.

  3. Uday Bondhugula, M. Baskaran, S. Krishnamoorthy, J.Ramanujam, A. Rountev, and P. Sadayappan. Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in thePolyhedral Model. International Conference on Compiler Construction (ETAPS CC), April 2008, Budapest, Hungary.

  4. PouchetL. PolyBench/C the Polyhedral Benchmark suite [Електронний ресурс] / Louis-Noël Pouchet – Режим доступу до ресурсу: http://web.cse.ohio\-state.edu/~pouchet/software/polybench/#description.
May 27, 2016