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



Скачать 253.25 Kb.
Дата05.09.2014
Размер253.25 Kb.
ТипДокументы
Оглавление


Введение

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

Одним из видов повышения скорости работы кода, который в той или иной мере включают в себя все современные оптимизирующие средства, является локальная оптимизация (peephole optimization). Этому виду оптимизации (подробно описанному в разделе 1.1) и посвящена данная работа.

Глава 1. Основные понятия

В данной главе будут описаны все основные понятия, используемые в процессе работы.



    1. Состояние вычислительной машины

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

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

S1:


Регистр 1 = 5

Регистр 2 = <пусто>

S2:

Регистр 1 = -10



Регистр 2 = <пусто>

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

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



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

S2:


Регистр 1 = 5

Регистр 2 = <пусто>

S1:

Регистр 1 = <пусто>



Регистр 2 = <пусто>

Разность состояний для состояний S1 и S2 – множество действий, которые необходимо предпринять, чтобы получить S2 из S1. Например, для двух состояний

разность будет состоять из одного действия – записи в первый регистр целого числа. В дальнейшем разность будет обозначаться как delta (S1, S2).

Свойства разность могут зависеть от целевой платформы. Например, в случае JVM она не является коммутативной – в приведенном примере delta(S1, S2) = {запись в регистр 1 целого числа}, а delta(S2, S1) = {}. Это обусловлено тем фактом, что единожды записанный регистр в общем случае невозможно снова сделать пустым. Из этого правила есть исключение, связанное с записью значений, занимающих несколько регистров, но мы не будем его здесь рассматривать.

Инструкция – описание операции, которую должна выполнить ЭВМ. Содержит код выполняемой операции, указания по определению операндов и по размещению получаемого результата (1). Результатом выполнения инструкции служит преобразование вычислительного состояния.


    1. Локальная оптимизация

Локальная оптимизация (peephole optimization) – оптимизация, производимая над небольшими фрагментами последовательного кода (2). В процессе оптимизации рассматривается только фиксированный фрагмент когда, так называемое «окно» (optimization window) и не принимается во внимание контекст, в это окно не попадающий. Таким образом, все изменения локализуются в пределах окна и не зависят друг от друга (в отличие от, например, межпроцедурной оптимизации, в которой изменение кода в рамках одной функции может привести к переработке всех мест, откуда эта функция вызывается). Из данного свойства вытекает основное преимущество локальной оптимизации – простота реализации и низкие затраты ресурсов на работу, так как не требуется поддержания каких-либо глобальных структур данных, графов потоков выполнения/данных и т.п. Существуют компиляторы (например, Realia для языка Cobol), имеющие в своем составе только локальный оптимизатор и благодаря этому способные работать на системах с жесткими ограничениями по памяти.

Локальная оптимизация может включать в себя следующие этапы:



  • сворачивание констант (constant folding);

  • удаление неиспользуемого кода;

  • замена отдельных инструкций более быстрыми аналогами;

  • упрощение арифметических выражений (например, замена умножения на два на сдвиг).

Некоторая часть из используемых оптимизаций может быть описана общим алгоритмом (например, поиск и удаление кода, результат работы которого нигде не используется), тогда как другая часть никаким алгоритмом не описывается и выглядит как таблица правил вида «встретив набор команд X заменить его на набор Y». Простейшим примером такого правила является повсеместно используемая в архитектуре x86 замена записи в регистр нуля на xor регистра с самим собой, то есть вместо

move ax, 0

все современные компиляторы сгенерируют

xor eax, eax

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


    1. Краткое описание генетических алгоритмов

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

    1. Краткое описание устройства JVM

Большая часть примеров в данной работе будет приведена в виде инструкций виртуальной машины Java. Для читателей, не знакомых с внутренним устройством данной виртуальной машины, в этом разделе будут описаны некоторые принципы ее работы. Подробная спецификация может быть взята по адресу (5)

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

Помимо стека существует еще набор регистров, так называемых локальных переменных. Они представляют собой набор нумерованных ячеек, содержащих данные. Параметры метода передаются через локальные переменные и занимают первые n из них. Регистры служат только для хранения данных примитивных типов и указателей, для вычислений значения должны быть сперва загружены на стек одной из инструкций семейства xLOAD (ILOAD для целых чисел, ALOAD для указателей и т.п.). Конкретный набор локальных переменных для каждого метода определяется на этапе компиляции, использовать другие регистры нельзя (код не пройдет проверку при загрузке).

Набор локальных переменных и стек операндов содержатся в так называемом кадре стека (stack frame). Общая схема показана на Рис. . Структура стека JVM



jvm_stack.png

Рис. . Структура стека JVM

Большинство команд JVM являются типизированными: например, инструкция ILOAD x ожидает наличия в локальной переменной с индексом x целого числа. Если же в данной локальной переменной ничего нет, либо содержится значение неверного типа – данный код не запустится или выкинет исключение во время выполнения.

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



Глава 2. Существующие решения

2.1. Применение полного перебора

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

Программные средства, которые могут доказать оптимальность своих результатов обычно называют супероптимизаторами. Данный термин впервые был применен в работе (6). С тех пор было создано несколько реализаций супероптимизаторов, например описанный в статье (7). Однако во всех случаях такая оптимизация рассматривалась как процесс, занимающий многие часы процессорного времени. В данной работе будет приведено сравнение скорости поиска решений генетическим алгоритмом и перебором, и сравнение будет совсем не в пользу последнего.

2.2. Генетическое программирование

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

Главная проблема в реализации генетического программирования – получение представления программы, над которым удобно выполнять операции скрещивания, мутации и пр. На данный момент наиболее широко используется древовидное представление программ. Подробно работа с таким представлением описана в работах J.R.Koza (8).

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

Как описано в работе (9), эволюция программ может строиться двумя способами:



  1. все возможные наборы инструкций могут быть получены в результате генетического процесса;

  2. строятся только «правильные» наборы инструкций.

«Правильные» - это таки последовательности, которые могут быть выполнены без ошибок. Например, такая последовательность является правильной:

ILOAD 0


ILOAD 0

IMUL


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

ILOAD 0


ILOAD 0

FMUL


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

В данной работе рассмотрен именно такой вариант. В разделе 3.3 будет подробно описана реализация генетических операторов, сохраняющий свойство корректности особей.



2.3. Генетические алгоритмы в оптимизаторах кода

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

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


  • полный перебор;

  • перебор с итеративным исключением;

  • генетические алгоритмы;

  • алгоритмы статистического выбора и т.д.

Использование полученных в результате перечисленных методов наборов опций позволяет достичь небольшого, но заметного (в пределах 5-10%) прироста производительности. Данный подход используют разнообразные инструментальные средства, например ACOVEA (11)

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

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

Глава 3. Применение генетического программирования к задаче оптимизации

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



3.1. Постановка задачи

Пусть имеется исходная последовательность инструкций Isource, преобразующая состояние ЭВМ из Ssource в Sdest за время T. Успешным решением задачи локальной оптимизации будем считать получение такой последовательности Ioptimized, что:



  • для работы ей достаточно Ssource (то есть Ioptimized не использует ресурсы, которые не использовались в Isource);

  • результатом работы является в точности Sdest (delta(Ssource, Sdest) = delta(Sdest, Ssource) = 0);

  • время работы Toptimized < T.

3.2. Ограничения

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

Поясним на примере. Пусть дан следующий фрагмент кода для виртуальной машины Java:

ILOAD 0


ILOAD 0

IMUL


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

  1. Нельзя сделать никаких предположений о наличии на стеке значений и их типах.

  2. На момент начала выполнения локальная переменная с индексом 0 доступна для чтения и содержит целое число.

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

Как уже было отмечено в разд. 1.4, в данной работе используется подход, при котором все генерируемые особи могут быть запущены (являются корректным кодом). Таким образом, ни в одной из особей не может появиться инструкции ILOAD 1 (загрузка целого числа из регистра с номером один) или ISTORE 0 (сохранение целого числа с верхушки стека в регистр с номером ноль), так как регистр #1 недоступен, а регистр #0 доступен только на чтение.

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



3.3. Построение генетического процесса

Как указано в книге (4), при решении практических задач с помощью эволюционных алгоритмов, необходимо выполнить четыре следующих подготовительных этапа:



  1. выбрать способ представления решения;

  2. создать начальную популяцию;

  3. разработать операторы случайных изменений;

  4. определить законы выживания решения.

В данном подразделе будут последовательно описан ход выполнения всех четырех этапов.

3.3.1. Представление особи

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

Каждая инструкция состоит из уникального индекса (так называемого опкода, англ. opcode) и необязательного набора аргументов. При этом инструкции рассматриваются как некие абстрактные структуры, без их конкретного приложения к реальному процессору. Не имеет значения их двоичная закодированная форма, которая используется например в так называемых CGPACompiled Genetic Programming Algorithms, впервые предложенных в работе (13). Манипуляция напрямую с бинарным представлением инструкций позволяет ускорить процесс вычисления фитнесс-функции (который зачастую является наиболее трудоемкой операцией), но значительно усложняет весь процесс и привязывает его к определенной целевой архитектуре.


5
Особь представляет собой список инструкций и изображена на рис. 2.

Opcode:

0x04 (ICONST_1)



Параметры:

Opcode:

0x4F (ISTORE)



Параметры:

Opcode:

0x84 (IINC)



Параметры:

-1

5



5

Рис.2. Структура особи.



3.3.1. Генерация начального поколения

Описание

При построении особей для начального поколения помимо перечисленных в разд. 2.2 ограничений будем принимать в расчет также и длину получаемых наборов инструкций. Действительно, для любой пары вычислительных состояний существует бесконечное множество наборов инструкций, переводящих одно состояние в другое. Такие решения могут отличаться друг от друга количеством повторенных бессмысленных (не влияющих на вычислительное состояние) фрагментов – вида «положить на стек – снять со стека» или любого другого. Разумным является ограничить возможную длину, например в диапазоне 0.5L – 1.5L, где L –длина исходного фрагмента.

В работе используется следующий алгоритм построения особей для начальной популяции:


  1. На основании исходной особи вычисляются начальное и конечное вычислительные состояния Ssource и Starget, а так же их разность Dtarget.

  2. Создается пустая последовательность инструкций.

  3. Строится разность состояний после выполнения текущего сгенерированного фрагмента Scur и Starget

  4. Если |delta(Scur, Starget)| = 0, то с вероятностью равной Lcur/L – 0.5 генерация прекращается, особь построена.

  5. Если длина сгенерированного фрагмента превысила длину исходного более чем в 1.5 раза, генерация текущего кандидата прекращается и начинается заново с пункта 2) Это позволяет избежать построения избыточно длинных последовательностей, которые возможно когда-нибудь и сойдутся к Starget, но которые будут сильно замедлять генетический процесс. Подробнее о борьбе с ростом длины особей будет рассказано в разд. 3.3.4.

  6. Выбирается режим генерации следующей инструкции:

    1. С вероятностью P = |delta(Scur, Starget)| / (1.5L - Lcur), где L – длина исходной особи, а Lcur – длина текущего фрагмента, будет выбрана инструкция, гарантированно уменьшающая разность состояний по крайней мере на одну операцию.

    2. С вероятностью 1 – P будет выбрана случайная инструкция.

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

  8. Переход к пункту 3)

Несмотря на то, что теоретически данный процесс может быть бесконечным (если постоянно будут строиться слишком длинные «неудачные» наборы), на практике в худшем случае приходится делать около 20 попыток для получения корректной особи приемлемой длины, в большинстве же случаев хватает одной-двух попыток.

Доказательство корректности

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



3.3.2. Скрещивание

Описание

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




Особь 2

(1)POP


(2)ICONST_M1

(3)DUP


(4)IMUL


Особь 1

(1)ILOAD 0

(2)ICONST_M1

(3)IXOR


(4)IAND

Производится поиск подходящих позиций для проведения скрещивания. Позиции i и j являются подходящими в особях C1 и C2, если последовательности инструкций C1[1..i] и C2[1..j] переводят исходное вычислительное состояние в одинаковые конечные состояния. То есть с точки зрения оставшихся частей этих особей безразлично, какой из двух фрагментов стоит в начале. Приведем пример. Пусть даны две особи:

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



  1. Из найденных позиций выбирается случайным образом пара, по которой будет проведено скрещивание. Вероятность пары быть выбранной тем выше, чем ближе оба индекса в ней к средней длине особей. Без данного условия если слишком часто будут выбираться пары с индексами в начале, популяция будет быстро разделяться на две группы. В первой группе будут очень короткие особи (две-три инструкции независимо от длины исходной особи), дающие совершенно неправильные результаты (их длины просто недостаточно чтобы выполнить все необходимые вычисления), а во второй – очень длинные особи (в десятки раз длиннее исходной). Такие особи возможно и будут получать правильные результаты при вычислениях, но за счет своих размеров и большого количества лишних действий никогда не смогут превысить скорость работы исходного варианта.

  2. Выполняется скрещивание. Родительские хромосомы разрезаются и обмениваются своими хвостами, начиная с i+1 и j+1 позиций. Полученные особи добавляются к популяции вместе с родителями.

Доказательство корректности

Пусть даны две корректные особи C1 и С2, преобразующие состояние Ssource в Sdest. Пусть выбраны пара позиций (i, j) таких, что C1[1..i]:Ssource->Sintermed и C2[1..j]:Ssource->Sintermed. После кроссовера получатся особи C1[1..i]C2[j + 1..size(C2)] и C2[1..j]C1[i..size(C1)]. При этом первая часть каждой особи по-прежнему переводит Ssource в Sintermed, а вторая – Sintermed в Sdest, то есть сохранено приведение вычислительного состояния к желаемому.



      1. Мутация

Описание

В ходе выполнения работы было рассмотрено две реализации операции мутации:



  • мутация отдельных инструкций;

  • мутация целых фрагментов.

Мутация отдельных инструкций

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

Так же, пользуясь сложной структурой отдельного гена в хромосоме, такая мутация может заменить один из операндов инструкции на какой-либо другой.

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



Мутация фрагментов

Алгоритм выполнения мутации фрагментов во многом аналогичен алгоритму получения начального поколения:



  1. Из особи вырезается фрагмент случайной длины

  2. Анализируется изменение вычислительного состояния, производимое вырезанным фрагментом

  3. Строится новая последовательность инструкций, реализующая то же изменение состояния. Используется алгоритм, описанный в разд. 3.3.1.

  4. Полученная последовательность вставляется в исходную на место вырезанного фрагмента.

Доказательство корректности

Пусть исходная особь является корректной и переводит состояние Ssource в Sdest. Разобьем ее на три фрагмента: первый Ssource->S1, второй S1->S2, третий – S2->Sdest и проведем замену второго фрагмента. По построению алгоритма генерации фрагмента новый второй фрагмент будет также переводить состояние из S1 в S2, следовательно особь в целом будет выполнять преобразование Ssource->Sdest, то есть будет являться корректной.



      1. Фитнесс-функция

Фитнесс-функция определяет ценность каждого отдельного кандидата.

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



  • скорость работы. Цель всего процесса – получение более быстрого варианта;

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

Скорость работы контролируется многократным запуском исходного и полученного кода и сравнения времени их выполнения. Стоит отметить, что в случае целевой платформы, использующей виртуальную машину (такой как Java), из-за наличия дополнительной прослойки между сгенерированным из особи кодом и реальными машинными инструкциями вычисление времени работы может быть непростой задачей. Описание наиболее часто возникающих сложностей можно прочесть в статье (14), и все они в той или иной степени проявили себя на данном этапе.

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

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

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

Несмотря на требование корректности получаемых особей, иногда вычислительно состояние, получаемое особью-кандидатом, может отличаться от необходимого результата. Самый распространенный случай – появление исключения деления на ноль. Пусть есть две особи, исходная (которая добавляет к содержимому регистра #0 единицу):

ICONST_1


ILOAD 0

IADD


и кандидат, в котором сложение замещено на целочисленное деление:

ICONST_1


ILOAD 0

IDIV


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

Вариант 2

NOP

Вариант 1



ICONST_1

ILOAD 1


IDIV

POP


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

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

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

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



Глава 4. Реализация

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

Было создано две реализации для двух разных платформ: байткода виртуальной машины Java и ассемблера x86. Целью было проверить применимость подхода для двух разных типов архитектур (JVM является стековой, а x86 – смешанной, большей частью регистровой). Две эти архитектуры оказались полными противоположностями с точки зрения сложности реализации:


  • JVM имеет очень простой и понятный, хоть местами и избыточный набор команд. Команды x86 наоборот запутаны, неочевидны, обладают разнообразными побочными эффектами.

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

  • Байткод отделен от реального процессора виртуальной машиной и оптимизирующим JIT-компилятором, что приводит к значительным сложностям в оценке производительности наборов инструкций. Ассемблер x86 такого недостатка лишен.

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

  • ядро;

  • платформенно-зависимые компоненты;

  • серверная часть;

  • клиентская часть.

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

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

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

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

Код ядра, сервера и клиента написан на языке Java. Платформенно-зависимая часть сделана частично на Java, а частично на C++ и подключена с использованием JNI (Java Native Interface).

4.1 Реализация для JVM

Реализация для виртуальной машины Java поддерживает набор из 55 инструкций. В него входят все инструкции арифметики с целыми (int и long) и вещественными (double и float) числами, а так же некоторые инструкции работы со стеком и локальными переменными (загрузка/сохранение данных, копирование, обмен и некоторые другие).



4.2. Реализация для x86

4.3. Примеры полученных оптимизаций

4.4. Сравнение с полным перебором

Заключение

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

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


Список литературы


1. Иллингуорт В., Глейзер Э. Толковый словарь по вычислительным системам. Москва : Машиностроение, 1990.

2. Peephole Optimization. W.M., McKeeman. 7, 1965 r., Communications of the ACM, Т. 8.

3. Фогель Л., Оуэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. Москва : Издательство "Мир", 1969.

4. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. Москва : ФИЗМАТЛИТ, 2003.

5. The Java Virtual Machine Specification. Sun development network. [В Интернете] http://java.sun.com/docs/books/jvms/.

6. Superoptimizer: a look at the smallest program. H., Massalin. 1987. ACM SIGPLAN Notices. Т. 22.

7. Automatic Generation of Peephole Superoptimizers. Bansal S., Aiken A.

8. J.R., Koza. Genetic Programming: On the programming of computers by means of natural selection. б.м. : MIT Press, 1998.

9. Genetic Programming in the Wild: Evolving Unrestricted Bytecode. Orlov M., Sipper M. 2009. Т. Proceedings of the 11th Annual conference on Genetic and evolutionary computation, стр. pp. 1043-1050.

10. Автоматическая оптимизация при компиляции. Л., Брусенцов.

11. Инструментальное средство для генетической оптимизации параметров компилятора ACOVEA. [В Интернете] http://www.coyotegulch.com/products/acovea/index.html.

12. Cavazos J., O'Boyle M. Automated Tuning of Inlining Heuristics for Java JIT Compilation.

13. P., Nordin. A Compiling Genetic Programming System that Directly Manipulates Machine Code. Advances in Genetic Programming. б.м. : MIT Press, 1994.

14. Б., Гетц. Теория и практика Java: Анатомия некорректных микротестов оценки производительности. [В Интернете] http://www.ibm.com/developerworks/ru/library/j-jtp02225/index.html.




Похожие:

Основные понятия в данной главе будут описаны все основные понятия, используемые в процессе работы. Состояние вычислительной машины iconС 01. 07. 2012 вступают в силу изменения статьи 2 «Основные понятия, используемые в настоящем Федеральном законе»
«Основные понятия, используемые в настоящем Федеральном законе» Федерального закона от 22. 11. 1995 №171-фз «О государственном регулировании...
Основные понятия в данной главе будут описаны все основные понятия, используемые в процессе работы. Состояние вычислительной машины iconОсновные термины и понятия цифровой вычислительной техники
Приведем термины и понятия вычислительной техники, с которыми часто приходится встречаться [1]
Основные понятия в данной главе будут описаны все основные понятия, используемые в процессе работы. Состояние вычислительной машины iconЗакон санкт-петербурга об основах промышленной политики Санкт-Петербурга Принят Законодательным Собранием Санкт-Петербурга 13 мая 2009 года Статья Основные понятия, используемые в настоящем Законе Санкт-Петербурга
Для целей настоящего Закона Санкт-Петербурга используются следующие основные понятия
Основные понятия в данной главе будут описаны все основные понятия, используемые в процессе работы. Состояние вычислительной машины icon1 Основные понятия, используемые при изучении фазовых равновесий
Цель курса: Обучить постановке и проведению исследований воздействия высокого всестороннего давления на фазовое состояние, структуру...
Основные понятия в данной главе будут описаны все основные понятия, используемые в процессе работы. Состояние вычислительной машины iconЦена, эффективность, качество новая версия
Цель работы: показать, что основные понятия, используемые в экономике, нуждаются в радикальном обновлении
Основные понятия в данной главе будут описаны все основные понятия, используемые в процессе работы. Состояние вычислительной машины iconСтатья Основные понятия, используемые в настоящем Федеральном законе

Основные понятия в данной главе будут описаны все основные понятия, используемые в процессе работы. Состояние вычислительной машины icon7. Краткая история развития вычислительной техники
...
Основные понятия в данной главе будут описаны все основные понятия, используемые в процессе работы. Состояние вычислительной машины iconОсновные понятия и определения
Цели урока: дать основные понятия о принципах и методах сборки. Научиться составлять технологическую схему сборки
Основные понятия в данной главе будут описаны все основные понятия, используемые в процессе работы. Состояние вычислительной машины iconВопросы к зачету по I полугодию по спецматематике, 8 класс, 2007 Основные понятия и определения
Основные понятия и определения (уметь формулировать, применять, приводить примеры)
Основные понятия в данной главе будут описаны все основные понятия, используемые в процессе работы. Состояние вычислительной машины iconОсновные понятия и определения 4 Линейные пространства 4
Данная работа рассматривает основные понятия, свойства, определения и теоремы, связанные с одним из классов линейных операторов –...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org