Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов




Скачать 49.12 Kb.
НазваниеРазработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов
Дата публикации02.09.2013
Размер49.12 Kb.
ТипДокументы
skachate.ru > Информатика > Документы

Проект научного исследования студента кафедры «Компьютерные технологии» СПбГУ ИТМО Е.В.Смирнова по теме


Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов

  1. Цель и задачи работы


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

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

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

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

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

  1. ^

    Научный задел


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

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

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

Полученный в результате работы фрагмент работает в среднем на 13% быстрее в режиме интерпретации байткода и на 1-2% быстрее при включенной JIT-компиляции (скорее всего именно найденная нетривиальная замена сложения на ИЛИ позволяет «обогнать» встроенный в виртуальную машину оптимизирующий JIT-компилятор).
Таблица 1. Сравнение исходной и оптимизированной последовательностей




Исходная последовательность, сгенерированная компилятором javac

Последовательность, полученная в результате работы алгоритма










Инструкции

ILOAD 0

ILOAD 0

IMUL

ILOAD 0

IMUL

ILOAD 0

ILOAD 0

IMUL

IADD

ILOAD 0

IADD

ILOAD 0

ICONST_1

IADD

ILOAD 0

IMUL

ICONST_1

IOR

ILOAD 0

IMUL

Формула

x3+x2+x

((x + 1)x ИЛИ 1)x

Число инструкций

6хILOAD

3xIMUL

2xIADD

Всего: 11

3xILOAD

2xIMUL

1xIADD

1xIOR

2xICONST_1

Всего: 9


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

По итогам данного этапа исследований автором был сделан доклад на на VII Межвузовской конференции молодых ученых (20-23 апреля 2010 года, СПбГУ ИТМО).

  1. ^

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


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

  1. ^

    Основные планируемые результаты


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

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


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

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

Похожие:

Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов iconЖирков В. Ф. Методические указания к курсовой работе
Изучение коллекции методов оптимизации, освоение алгоритмов, получение практических навыков при выполнении типовых задач, разработка...
Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов iconУдк-004. 4'416 Применение генетических алгоритмов для локальной оптимизации программного кода
Целью данной работы является проверка эффективности применения генетических алгоритмов как замены полного перебора при поиске лучшего...
Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов iconПрименение генетических алгоритмов для локальной оптимизации программного кода
Целью данной работы является проверка эффективности применения генетических алгоритмов как замены полного перебора при поиске лучшего...
Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов iconОтчетность
Целью настоящего пособия является изучение методов моделирования радиотехнических систем и устройств и их конструкций, методов оптимизации...
Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов iconПрименение генетического программирования для локальной оптимизации кода
Целью данной работы является проверка возможности применения генетических алгоритмов как замены полного перебора при поиске более...
Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов iconТребования к проектированию генетических алгоритмов
Как следствие расширения области применения, наиболее остро встает вопрос разработки методов повышения эффективности генетических...
Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов iconПрименение генетического программирования для локальной оптимизации кода
Эта оптимизация представляет собой поиск определенных небольших фрагментов последовательного (не содержащего ветвлений) кода и замена...
Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов iconИсследование и разработка алгоритмов обобщения на основе теории приближенных множеств
Специальность 05. 13. 11 – Математическое и программное обеспечение вычислительных машин, комплексов
Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов iconИсследование и разработка алгоритмов обобщения на основе теории приближенных множеств
Специальность 05. 13. 11 – Математическое и программное обеспечение вычислительных машин, комплексов
Разработка методов оптимизации низкоуровневого программного кода на основе эволюционных алгоритмов iconО поиске сходства интернет-документов с помощью частых замкнутых множеств признаков
В работе исследуется применение алгоритмов Data Mining для поиска кластеров дубликатов с использованием синтаксических и лексических...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница