Инструмент для поиска потенциальных возможностей проведения кэш-оптимизаций

Создать новую статью

Дата последнего изменения :   19.10.2009 07:40
Рейтинг
 


Аннотация

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

Введение

Г. Маркес был прав, говоря, что самое лучшее в нашей жизни происходит неожиданно. И случайно замеченное мной на просторах Интернета приглашение в Летнюю Школу Intel - яркий тому пример. Сегодня, находясь в Иркутске и выбрав тему диплома непосредственно связанную с тематикой моего проекта в Летней Школе, я понимаю, что один месяц, проведенный на стажировке в Новосибирском Академгородке, оказал достаточно сильное влияние на мою дальнейшую деятельность. В этой статье мне бы хотелось познакомить вас с идеей проекта, рассказать о уже проделанной работе, а также о перспективах развития данной темы.

Об идее проекта

«Создание инструмента для поиска потенциальных возможностей проведения кэш-оптимизаций» - таково название проекта, над которым кроме меня работал Антон Астафьев, а курировал проект ментор от Intel Дмитрий Буданов.

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

Суть проекта

Рис. 1. Суть проекта

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

  • Loop invariant code motion (вынесение инвариантов цикла) - оптимизация, которая находит и выносит за пределы цикла выражения независящие от индексных переменных цикла;
  • Loop fusion (объединение циклов) - объединение циклов, увеличивающее инструкционный параллелизм и позволяющее интенсивнее загружать вычислительные устройства процессора;
  • Loop distribution (разбиение циклов) - разбиение циклов способное улучшить производительность за счет улучшения работы с памятью;
  • Loop unrolling (развертка цикла) - техника призванная уменьшить количество условных переходов в цикле. Несколько итераций цикла объединяются в одну;
  • Loop unswitching (размыкание цикла) - оптимизация, состоящая в вынесении условия за пределы цикла и дублирования тела цикла с помещением соответствующих вариантов в соответствующие ветви условия;
  • Loop interchange (Перестановка циклов) - оптимизация, при которой меняется порядок циклов;
  • Loop tiling (разбиение цикла на блоки) - метод оптимизации состоящий в разбиении пространства итерирования исходного цикла на небольшие блоки меньшего размера, что позволяет хранить используемые в этих небольших блоках данные в кэше полностью для их неоднократного использования в процессе выполнения блока.

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

Средства, способы и алгоритмы реализации

Для реализации первой компоненты нам понадобилась утилита Pin. Pin - Dynamic Binary Instrumentation Tool, утилита, которая внедряется в анализируемый процесс непосредственно перед стартом и позволяет отслеживать выполнение практически любых инструкций, предоставляет API доступа к содержимому регистров, контексту выполнения программы, символьной и отладочной информации. В нашем случае, мы использовали API, позволяющие инструментировать инструкции доступа к памяти.

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

Что касается БД, то мы использовали SQLite - свободно распространяемую реляционную базу данных, не использующую парадигму «клиент-сервер», а основанную на встраиваемом движке. SQLite хранит всю базу данных (включая определения, таблицы, индексы и данные) в единственном стандартном файле на том компьютере, на котором исполняется программа.

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

Реализация №1: Определение границ кластеров по каждому измерению с помощью фильтра LoG, фильтрация по плотности наполнения областей.

Фильтр LoG (Laplacian of Gaussian) - сглаживание ряда данных по методу Гаусса, взятие второй производной и определение границ кластера по смене её знака. Чтобы применить фильтр формируются временные таблицы следующей структуры: адрес инструкции, число её повторений (для выявления диапазонов адресов инструкций) и адрес ячейки памяти, число обращений к этой ячейки (для выявления диапазонов адресов ячеек памяти).

Реализация №2: Сортировка собранной статистики пространственным деревом поиска (окто-деревом), фильтрация по плотности и восходящее объединение кластеров.

Кластеризацию на окто-дереве можно описать следующими характеристиками:

  • 3D пространство данных;
  • Равномерное распределение по каждому измерению - O(n);
  • Заполнение дерева - O( n x Log8n ) ~ 7n;
  • Автоматическая балансировка загрузки памяти;
  • Связная структура для быстрого объединения;
  • Гибкое распараллеливание;
  • Использование гипотезы λ-компактности: критерии одинаковой плотности и близости объемов.

Результат обеих реализаций сведен к единому формату - списку кластеров. Кластер представляет собой пересечене диапазонов времени, адресов инструкций и адресов данных.

Надо сказать, что вопрос наиболее эффективного метода обработки данной статистики еще не закрыт и является основным направлением нашего дальнейшего исследования в этом проекте. В рамках Летней Школы мы представили результаты, полученные методами, описанными выше. Графический интерфейс был разработан на языке Java с помощью библиотек Swing и JfreeChart, в среде NetBeans 6.5.

О проблемах

Думаю, было бы странно, если при работе над проектом не возникло бы ни одного затруднения. В этом проекте мне пришлось впервые столкнуться с достаточно большими объемами данных. Индексация и обработка баз данных занимала довольно много времени на ПК средней производительности. Благодаря тому, что у нас был доступ к использованию кластера, нам удалось в разы сократить время работы инструмента. Кроме того, из-за большого объема данных (миллионы записей) терялась точность выявления проблемных областей. Объем данных в свою очередь был связан с выбором шага инструментации. В итоге было принято решение, менять шаг инструментации в соответствии с размером исследуемого кода.

Результаты

Исследовав предметную область, выбрав средства реализации и устранив возникшие проблемы, мы перешли к реализации задуманного. Благодаря организованной работе команды (Антон занимался реализацией первого компонента и метода, основанного на окто-деревьях, а я реализацией третьего компонента и метода, использующего фильтр LoG) и грамотному управлению проектом со стороны нашего куратора, был создан инструмент, архитектура которого представлена на рис.2.

Архитектура инструмента

Рис. 2. Архитектура инструмента

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

Ниже вы видите график пересечений диапазонов и общий вид графического интерфейса.

plot.jpg

Рис. 3. График пересечений диапазонов

На графике по оси Х указаны адреса ячеек памяти, а по оси Y адреса инструкций. Синим цветом показано, что два диапазона адресов инструкций обращаются к одному и тому же диапазону адресов памяти. Данное пересечение указывает на потенциальную «проблемную» область.

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

gui.jpg

Рис. 4. Общий вид графического интерфейса

Перспективы

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

  • Аналитическая обработка данных. Дальнейшее исследование предметной области и методов анализа данных необходимо для создания более эффективного статистического анализатора.
  • Визуализация в 3D. Для представления общей картины нужно будет сформировать куб, измерениями которого будут: адрес инструкции, адрес ячейки памяти, момент времени. Таким образом, интересующие нас фрагменты кода будут представлены в виде наиболее плотных областей в этом кубе. Тип доступа предполагается выделять цветом.
  • Объединение компонентов. Следует объединить инструментатор бинарного кода со статистическим анализатором и графическим интерфейсом пользователя, что возможно повлечет за собой незначительные изменения в структуре базы данных.
  • Экспертная система для помощи в выявлении потенциальных возможностей кэш-оптимизаций. На данном этапе инструмент предлагает в табличном и графическом виде только факты нахождения проблемных областей, и пользователь сам должен сделать выводы о том, какие корректировки можно провести в структуре кода. Было бы неплохо создать модуль, действующий на основе базы знаний о возможных оптимизациях.
  • Тестирование на реальных приложениях. Необходимо уделить больше времени тестированию инструмента, провести сравнительные анализы выполнения на разных аппаратных и программных платформах.

Заключение

Как видите, впереди много интересной работы. Возможно, пройдет время, и на сайте сообщества появится статья о второй версии инструмента, а пока я прощаюсь с вами. Благодарю за внимание.

Об авторе и летней школе Intel

Жданова Наталия Юрьевна, студентка Байкальского Государственного Университета Экономики и Права ( факультет Экономической Кибернетики), проходила стажировку в рамках Летней Школы Intel в Новосибирске. Для меня стажировка в Летней Школе стала самым ярким событием этого лета. Интенсивная работа, интереснейшие лекции и тренинги, общение с единомышленниками, экскурсии - четыре сумасшедших недели за которые я расширила свой кругозор, нашла новых друзей, получила опыт работы в команде, изменила взгляд на науку и многое другое. Если бы стажировка длилась всё лето, я бы не задумываясь провела его с Intel, потому что как оказалось, лето и Intel очень даже совместимы!

Используемая литература и ссылки на ресурсы

  1. Презентация «Проект №5: Создание инструмента для поиска потенциальных возможностей проведения кэш-оптимизаций» Астафьев А., Жданова Н.
  2. Презентация «Современные оптимизирующие компиляторы» Ануфриенко А.
  3. http://www.ixbt.com/soft/intel-parallel-inspector.shtml - «Intel Parallel Inspector - поиск ошибок доступа к памяти» В. Цымбал.
  4. http://en.wikipedia.org/wiki/Loop_optimization - Loop optimization.
  5. http://www.pintool.org/ - сайт, посвященный утилите Pin(Dynamic Binary Instrumentation Tool.
  6. http://www.sqlite.org/ - официальный сайт БД SQLite.
  7. http://www.jfree.org/jfreechart/ - официальный сайт графической библиотеки Jfreechart.