Лекции (5) (Презентации лекций (PDF))

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

Например, вслучае исключения из программы вызова функции с "побочным эффектом".У современных компиляторов существует возможность выбора критерияоптимизации и отдельных методов оптимизации.Машинно-независимые оптимизирующие преобразованияМашинно-независимые преобразования исходнойпрограммы производятся в основном над ее внутреннимпредставлением и основаны на известных математических илогических преобразованиях.1.Удаление недостижимого кода.(задача компилятора найти и убрать его).Пример:if (1)S1;elseS2;S1;Машинно-независимые оптимизирующие преобразования2.

Оптимизация линейных участков программы.В современных системах программирования профилировщик на основерезультатов запуска программы выдаёт информацию о том, на какие еёлинейные участки приходится основное время выполнения.а) Удаление бесполезных присваиваний.a = b * c; d = b + c; a = d * c;  d = b + c; a = d * c;Однако, в следующем примере эта операция уже не бесполезна:p = & a; a = b * c; d = * p + c; a = d * c;б) Исключение избыточных вычислений.d = d + b * c; a = d + b * c; c = d + b * c;t = b * c; d = d + t; a = d + t; c = a;в) Свертка объектного кода (выполнение во время компиляции техопераций исходной программы, для которых значения операндов ужеизвестны).i = 2 + 1; j = 6 * i + i;i = 3; j = 21;Машинно-независимые оптимизирующие преобразованияг) Перестановка операций (для дальнейшей свертки илиоптимизации вычислений).a = 2 * b * 3 * c;  a = (2 * 3) * (b * c);a = (b + с) + (d + e);  a = (b + (c + (d + e) ) );д) Арифметические преобразования (на основеалгебраических и логических тождеств).a = b * c + b * d;  a = b * (c + d);a * 1  a,a * 0  0,a+0 a.e) Оптимизация вычисления логических выражений.Но!a || b || c || d;  a, если а есть true.a || f(b) || g(c)не всегда а (при а = true),может быть побочный эффект.Машинно-независимые оптимизирующие преобразования3.

Подстановка кода функции вместо ее вызова вобъектный код.Этот метод, как правило, применим к простым функциям ипроцедурам, вызываемым непосредственно по адресу, безприменения косвенной адресации через таблицы RТTI (RunTime Type Information).Некоторые компиляторы допускают применять методтолько к функциям, содержащим последовательныевычисления без циклов.Язык С++ позволяет явно указать (inline), для каких функцийжелательно использовать inline-подстановку.Машинно-независимые оптимизирующие преобразования4.

Оптимизация циклов.а) Вынесение инвариантных вычислений из циклов.for (i = 1; i <= 10; i++)a [i] = b * c * a [i];d = b * c; for (i = 1; i <= 10; i++)a [i] = d * a [i];б) Замена операций с индуктивными (образующими арифметическуюпрогрессию) переменными (как правило, умножения на сложение).for (i = 1; i <= N; i++)a [i] = i * 10;t = 10; i = 1; while (i <= N) {a [i] = t; t = t + 10; i++;}s = 10; for (i = 1; i <= N; i++) {r = r + f (s); s = s + 10; }s = 10; m = N * 10; while (s <= m) {r = r + f (s); s = s + 10; }(избавились от одной индуктивной переменной).Машинно-независимые оптимизирующие преобразованияв) Слияние циклов.for (i =1; i <= N; i++)for (j = 1; j <= M; j++)a [i] [j] = 0;k = N * M;for (i = 1; i <= k; i++)a [i] = 0; (только в объектном коде!)г) Развертывание циклов (можно выполнить для циклов, кратностьвыполнения которых известна на этапе компиляции).for (i = 1; i <= 3; i++)a [i] = i;a [1] = 1;a [2] = 2;a [3] = 3;Машинно-зависимые оптимизирующие преобразованияМашинно-зависимые преобразования результирующей объектнойпрограммы зависят от архитектуры вычислительной системы, на которойбудет выполняться результирующая программа.

При этом можетучитываться объем кэш-памяти, методы организации работы процессора….Эти преобразования, как правило, являются "ноу-хау", и именно онипозволяют существенно повысить эффективность результирующего кода..1. Распределение регистров процессора.Использование регистров общего назначения и специальных регистров(аккумулятор, счетчик цикла, базовый указатель) для хранения значенияоперандов и результатов вычислений позволяет увеличитьбыстродействие программы.Доступных регистров всегда ограниченное количество, поэтому передкомпилятором встает вопрос их оптимального распределения ииспользования при выполнении вычислений.Машинно-зависимые оптимизирующие преобразования2.

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

методы передачи параметровчерез регистры не стандартизованы и зависят от реализации компилятора.- этот метод не может быть использован, если где-либо в функции требуетсявыполнить операции с адресами параметров.Языки Си и С++ позволяют явно указать (register), какие параметры илокальные переменные желательно разместить в регистрах.Машинно-зависимые оптимизирующие преобразования3. Оптимизация кода для процессоров, допускающихраспараллеливание вычислений.При возможности параллельного выполнения нескольких операцийкомпилятор должен порождать объектный код таким образом, чтобы в нембыло максимально возможное количество соседних операций, всеоперанды которых не зависят друг от друга.Для этого надо найти оптимальный порядок выполнения операций длякаждого оператора (переставить их).a + b + c + d + e + f; для одного потока обработки данных: ((((a + b) + c) + d) + e) + f;для двух потоков обработки данных:((a + b) + c) + ((d + e) + f);для трех потоков обработки данных:(a + b) + (c + d) + ( e + f);.