Оценка снижения времени выполнения тестовых программ при применении автоматической оптимизации на основе полиэдральной модели на Raspberry Pi 3



Для оптимизации вычислительных циклов используют различные методы на основе представления итерационного пространства цикла в виде многогранника – так называемая полиэдральная модель. Такая модель позволяет представить произвольный вычислительный цикл в виде абстрактного математического описания. Полиэдральная модель может быть получена из исходного кода, изменена и преобразована обратно в исходный код. Статья содержит результаты автоматической оптимизации тестовых приложений на Raspberry Pi 3.

Ключевые слова: автоматическая оптимизация программного обеспечения, полиэдральная модель, Pluto, Raspberry Pi 3

Estimation of execution time reducing in the test applications with automatic optimization based on the polyhedral model on Raspberry Pi 3

There are a several methods of the computational loops' optimizations. They use aniterative presentation space of loops in the form of a polyhedron. Polyhedral model is a mathematical model that allows to represent a computational loop asan abstract mathematical description. Polyhedral model can be obtained from anysource code, modified then and converted back to source code. This article contains the results of the automatic optimization of test applications on Raspberry Pi 3 computer.

Keywords: automatic software optimization, polyhedral model, Pluto software, Raspberry Pi 3

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

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

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

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

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

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

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

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

Для проверки работы оптимизатора вычислительных циклов был выбран пакет Pluto версии 11.4. Этот пакет позволяет использовать стандартную опцию разбиения цикла на блоки с целью повышения локальности данных (tile), а также более усовершенствованные подходы, а именно:повторное разбиение на блоки (tile a second time) (l2tile), полноразмерный одновременный старт разбиения на блоки (enables full-dimensional concurrentstart) (diamond-tile), использование всех уровней параллелизма (extract alldegrees of parallelism) (multipar), использование исключительно внутреннего параллелизма (choose pure inner parallelism over pipelined/wavefront parallelism) (innerpar). В том числе доступна опция автоматического распараллеливания по ядрам (parallel). Возможность распараллеливания использует стандартную библиотеку OpenMP. Распараллеливание может быть использовано совместно с разбиением цикла на блоки.

Аппаратная платформа представляет собой компьютер Raspberry Pi 3 version B. Четырехядерный центральный процессорBroadcom BCM2837 64bit основан на ядре ARMv8 и работает с максимальной частотой 1.2 ГГц. Измерения проводились в операционной системе Ubuntu Mate 16.04 32bit.

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

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

Для наглядности ускорения времени работы на таблице ниже приведены данные относительного ускорения по сравнению с оригинальной версией каждого алгоритма.

Таблица 1 — относительное ускорение времени выполнения оптимизированных алгоритмов, разы

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

Рассматривая полученные результаты времени выполнения оптимизированных алгоритмов, можно сделать такие выводы для однопоточных оптимизаций:

$-$ однопоточное классическое разбиение на блоки (tile) ускоряет время выполнения алгоритмов в 15 случаях,без существенных изменений в 8 случаях и в 5 случаях замедляет время выполнения;

$-$ однопоточное использование исключительно внутреннего параллелизма (innerpar) ускоряет время выполнения алгоритмов в 12 случаях, без существенных изменений в 13 случаях и в 3 случаях замедляет время выполнения;

$-$ однопоточное использование исключительно внутреннего полноразмерного одновременного старта разбиения на блоки (diamond-tile) ускоряет время выполнения алгоритмов в 10 случаях, без существенных изменений в 10 случаях и в 4 случаях замедляет время выполнения.

Рис. 1 — график ускорения времени работы алгоритмов в зависимости от использованной оптимизации

Рис. 2 — график ускорения времени работы алгоритмов в зависимости от использованной оптимизации (продолжение)

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

Выводы. Анализируя результаты времени выполнения для многопоточных версий, использующих различные методы разбиения в своём составе, следует отметить отсутствие однозначного ответа на вопрос об ускорении относительно однопоточной версии. Снижение производительности происходит приблизительно в 4% случаев и не составляет более 8% снижения результата. В то же время в большинстве случаев (приблизительно 84%) включение многопоточности приводит к существенному ускорению времени работы. Максимальный прирост от совместного использования метода разбиения на блоки и многопоточности составляет 7.78 раза.

Отдельно следует отметить использование опции l2tile, которая дважды производит разбиение на блоки совместно с распараллеливанием. Как показали результаты измерений, именно в этом наборе опций наиболее часто происходит замедление времени выполнения тестовых алгоритмов. Из этого можно сделать вывод, что повторное разбиение на блоки в вычислительных системах на основе ядра процессора ARMv8 нецелесообразно в связи с его архитектурными особенностями.

Перелік посилань:

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

$2.$ XUE J. Loop Tilingfor Parallelism / JINGLING XUE. – Sydney, NSW2052, Australia: Springer Science+Business Media New York,2000. – (Kluwer international series in engineering and computer science ; SECS575).

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

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

$5.$ Summer InfoCom 2016: Матеріали II Міжнародної науково-практичної конференції, м. Київ,1-3 червня 2016 р.- К.: Вид-во«Інжиніринг», 2016. - 116 с. ISBN 978-966-2344-50-9 ст. 74-76.)

Mar 22, 2017