Scientific journal

Fundamental research

ISSN 1812-7339

"Перечень" ВАК

ИФ РИНЦ = 1,674

Составление расписаний учебных занятий является одной из сложных задач автоматизации. В продаже и свободном распространении имеется большое количество программных продуктов для ее решения, таких как «Ректор-ВУЗ» [4], «FET» и др. Как правило, такие программы при оптимизации расписания опираются на критерий качества, выраженный в виде целевой функции. Имитационное моделирование расписания занятий [2] включает модель целевой функции при оптимизации.

Известны различные методы оптимизации расписания учебных занятий. Одним из известных методов является метод последовательного перебора. Однако уже при малом числе групп данный метод требует больших вычислительных затрат, так как это NP-полная задача. В этом случае актуальной является задача сокращения времени вычислений. Одним из подходов решения данной задачи служит применение методов оптимизации исходного кода программы [1].

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

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

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

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

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

В имитационном моделировании расписания учебных занятий задача состоит в оптимальном расположении объектов по дискретным интервалам времени, причем имеется n объектов и m интервалов [2]. Вектор расположений объектов имитирует расписание. У каждого объекта по два целочисленных параметра, исходя из значений которых на основании расписания однозначно вычисляется значение целевой функции.

Первый эксперимент состоит в запуске полного перебора вариантов расположения объектов для n = 10, m = 20 с оцениванием каждого варианта. Для этого используется прием программирования, называемый рекурсией, которая определяется как вызов подпрограммой самой себя. Рекурсия реализует следующую схему поиска в «глубину», начинающую работу со второго уровня вложенности рекурсии при взаимно однозначном соответствии между объектами и уровнями: объект текущего уровня в цикле от 1 до m смещается вправо на один временной интервал, и для каждого такого смещения вызывается рекурсивная функция, выполняющая аналогичные смещения с вызовами самой себя и наращиванием уровня, пока уровень не достигнет числа n. При каждом смещении объекта n-го уровня вместо вызова рекурсии производится вычисление целевой функции, причем для повышения быстродействия вычисляется только ее изменение и складывается со старым значением. Поиск завершается при последнем в цикле возврате из рекурсии на втором уровне. Всего оценивается m(n–1) = 209 = 5,12?1011 вариантов, так как перемещения первого объекта программой не рассматриваются в силу особенностей задачи.

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

В данной серии экспериментов рассматриваются четыре комбинации методов оптимизации исходного кода:

1. Обычные вызовы рекурсии, которые рассмотрены выше. При вычислении целевой функции здесь и далее применяется такая эвристика, как предварительное вычисление массива произведений параметров объектов размером n×n.

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

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

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

Вторая серия экспериментов связана с методом встраивания обычных (нерекурсивных) функций. Для этого по 100 000 раз запускается функция, вычисляющая значение целевой функции для псевдослучайных моделей расписаний при n = 40, m = 100.

Рассматриваются четыре комбинации других методов оптимизации исходного кода: A – обычный вызов функций; B – встраивание функций, т.е. вместо вызова функции в вызывающем модуле используется текст, эквивалентный тексту функции; C – встраивание функции, при котором ее внутренний вычислительный цикл становится внешним, т.е. рассматривается метод перестроения системы вложенных циклов. В данном случае вложены три цикла, из которых два внешних сначала выполнялись от 1 до n – 1, а внутренний от 1 до m, а теперь цикл от 1 до m стал внешним, а два цикла от 1 до n – 1 стали внутренними; D – встраивание функции, при котором ее внутренний цикл (от 1 до m) помещен между двумя циклами от 1 до n – 1.

Для получения обобщенных результатов предлагается рассмотреть работу тестовой программы на процессорах различных годов выпуска (которые связаны с тактовой частотой), моделей и типов. Исследование проведено с применением персональных компьютеров с процессорами П1, П2, П4, П5 (табл. 1) и ноутбука с процессором П3.

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

Результаты встраивания рекурсий и предварительных действий

Эффективность применяемых методов можно выразить индексом производительности для разных процессоров l1 = 1/(fT) – числом вычислений (в данном случае переборов вариантов) в секунду, которое привносит 1 МГц процессора (табл. 2). Здесь f – тактовая частота процессора, МГц; T – среднее время вычислений при переборе вариантов, с. Время вычислений определено с помощью диспетчера задач как суммарное время работы центрального процессора и в табл. 2 не внесено.

Таблица 1

Таблица 2

l1·106 для разных процессоров и методов оптимизации при n = 10, m = 20

Примечание. * Без оптимизации кода в настройках компилятора (очевидно, ее использование влияет на эффект от применения приемов оптимизации исходного кода на основе «искусства» программирования).

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

В исходном варианте индекс производительности у всех процессоров почти одинаков. Заполнение массивов уменьшает l1 на (22 ± 8) %. Это заметнее на новых процессорах и особенно на процессорах AMD. Встраивание рекурсивных вызовов в дополнение к заполнению массивов обычно немного уменьшает l1. В итоге сравнение встраивания рекурсий и вызова рекурсий показывает, что l1 уменьшается на (24 ± 7) %.

Таким образом, необходимости встраивания рекурсивных вызовов нет. Тем более что при встраивании значительно усложняется исходный код. Это отрицательно сказывается на всех фазах жизненного цикла исходного кода [5], увеличивая трудоемкость его разработки и дальнейшего сопровождения. Данное обстоятельство становится особенно весомым при значительных перерывах в работе с исходным кодом и при передаче его на сопровождение третьим лицам [6].

Если оптимизацию выключить, производительность снижается меньше: 11–18 % и 13–19 % соответственно. В среднем, как видно в табл. 2, l1 уменьшается на 23 %. Для новых процессоров Intel в среднем нет снижения производительности, для старых в среднем это 22 %, а для новых процессоров AMD – 30 %. Однако при обычном вызове рекурсий и выключенной оптимизации наблюдается снижение производительности для всех процессоров.

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

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

Второй индекс производительности для разных процессоров (табл. 3) l2 = 1/(fT) – число однократных вычислений значений целевой функции в секунду, которое привносит 1 МГц процессора, где T – время 105 вычислений значений целевой функции, с.

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

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

Рассмотрим, как влияет на производительность изменение структуры вложенных циклов. Первый вариант модификации структуры цикла сильно снижает l2: в пределах 1,5–3,4 раза при оптимизации средствами компилятора и в 1,9–2,5 раза без нее. Второй вариант модификации у процессоров Intel тоже снижает l2, но не так сильно: от 12 до 30 % при оптимизации средствами компилятора и от 15 до 23 % без нее. У AMD, напротив, увеличивает соответственно от 13 до 44 % и от 32 до 47 %. Следовательно, первоначальный вариант модификации структуры циклов в основном можно считать наиболее удачным.

Таблица 3

l2 для разных процессоров при n = 40, m = 100

Примечание. * Без оптимизации кода в настройках компилятора.

Снижение производительности из-за отказа от оптимизации средствами компилятора в среднем составляет 37 % (от 28 до 41 %). При этом оно наименьшее в первом варианте модификации циклов и меньше у процессоров Intel.

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

Заключение

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

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