Л.Е. Карпов - Системы программирования (1114903), страница 12
Текст из файла (страница 12)
Более сложные варианты алгоритмов свертки принимают вовнимание известные им значения переменных (например, сразу после присваивания) идаже функций.Арифметические преобразования. Компилятор может изменять характер ипорядок следования операций на основании известных алгебраических и логическихтождеств, например, заменять выражение A=B*C+B*D выражением A=B*(C+D).Некоторые операции могут заменяться более “простыми”, что делает их выполнениеболее эффективным:x := y ** 2x := y * 2=>=>x := y * y;x := y + y;Устранение общих подвыражений (избыточных вычислений). Операциялинейного участка может оказаться избыточной, если ранее на этом же линейномучастке уже выполнялась идентичная операция, и никакой операнд данной операции небыл изменен в промежутке между двумя идентичными операциями.Удаление ненужных присваиваний и других операций.
Если на некоторомлинейном участке между двумя операциями присваивания какой-либо переменнойзначений (одинаковых или разных, не имеет значения), не было ни одного оператора, вкотором использовалось бы первое значение переменной, это присваивание являетсябесполезным и может быть удалено из программы без изменения ее смысла.Иногда по наличию операторов присваивания одним переменным значенийдругих переменных удается исключить использование некоторых переменных, заменивих использованием их копий (метод носит название “распространение копий”). В такихслучаях происходит как экономия времени исполнения программ, так и экономия44памяти, отведенной под хранение данных программы.
Например, после присваиванияf:=g можно вместо переменной f использовать переменную g, а присваивание простоисключить из программы. В наилучшем случае переменная f совсем станет ненужной,значит, и память для нее тоже распределять не придется. Подобные преобразованиястановятся особенно актуальными при компиляции автоматически сгенерированныхпрограмм, работающих с многочисленными переменными и “цепными”присваиваниямиПерестановка независимых смежных участков программ.
Иногдакомпиляторам удается таким образом переставить следующие друг за другом операции,что без изменения смысла программы удается применить какие-либо другиепреобразования. Например, имея выражение A=2*B*3*C можно преобразовать егоперестановкой в A=(B*C)*(2*3), а затем можно вычислить значение подвыраженияиз констант. Даже если выражение из констант получить не удается, перестановкаопераций может привести к экономии временных переменных, которые порождаютсякомпилятором для хранения промежуточных результатов вычислений. Например,непосредственное вычисление выражения A=(B+C)+(D+E) может потребовать, покрайней мере, одной временной переменной для хранения промежуточного результатасложения B и C.
Если же провести перестановку операций, эта переменная будет ненужна, а результат останется прежним: A=((B+C)+D)+E.В некоторых случаях перестановка операций может приводить к потереточности вычислений. Некоторые типы операндов могут сделать переупорядочениевыражений невозможным. Например, перестановка целочисленных операций ввыражении I/J*K может привести к неверному вычислению выражения 10*3/8.Удаление недостижимых фрагментов программы часто требует глобальногоанализа программы для определения “достижимости”.
В основе такого анализа лежатидеи теории графов, связанные с анализом потока управления и потока данных.Простейший вариант – удаление недостижимых фрагментов, выделяемых с помощьюпрепроцессорных операторов.Оптимизациявычислениялогическихвыражений.Особенностьюоптимизации логических выражений является то, что для получения их значений невсегда требуется проводить вычисление всего выражения до конца. Иногда порезультату первых же операций можно заранее определить окончательный результат.Например, операцию логического сложения можно не проводить, если известно, чтоодин из ее операндов имеет значение “истина”.
Если это разрешается правилами языка,компиляторы так строят внутренние представления логических выражений, чтобы ихвычисления прекращались сразу же, как только значение всего выражения становитсяпредопределенным. Аналогичные рассуждения относятся и к арифметическимвыражениям, но умножения на 0 встречаются гораздо реже, чем логическое “И” созначением “ложь”.Оптимизация передачи параметров и вызовов функций проводится на основедвух подходов: прямой подстановки тел функций в основной текст программы ипередачи параметров не с помощью общего стекового механизма, а через глобальныепеременные, которые впоследствии связываются с регистрами центральныхпроцессоров.Прямая подстановка функций в основной цикл программы может привести ксущественному увеличению скорости работы программы, но одновременно и кувеличению размеров программы (если функция вызывается из нескольких разных45мест). Этот метод приводит к сокращению времени на передачу параметров ивозвращаемого результата, на команды передачи управления, захвата памяти в стеке идругие вспомогательные операции.
Некоторые языки (Си++) разрешаютпрограммистам явно указывать функции, которые желательно реализоватьподстановкой (inline).Передача параметров через регистры процессора относится к машиннозависимой оптимизации. Отказ от универсального стекового механизма вопределенных случаях может приводить к значительному снижению времени работыпрограммы, но передача параметров через регистры зависит от количества доступныхрегистров в вычислительной системе и от используемого в компиляторе алгоритма ихраспределения.Важность данного метода постоянно возрастает с ростом возможностейвычислительной аппаратуры, но метод имеет ряд выраженных недостатков.
Во-первых,он сильно зависит от особенностей конкретной архитектуры вычислительной машины.Во-вторых, процедуры, оптимизированные таким образом, не могут включаться вобщие библиотеки, поскольку используют нестандартный метод полученияпараметров. В-третьих, использовать метод не удается, если в теле функциииспользуются операции вычисления адресов параметров.В некоторых языках программирования программисты имеют возможность явноуказывать, какие переменные следует размещать на регистрах (в Си++ – с помощьюключевого слова register). Подобные указания имеют для компилятороврекомендательный характер, но часто помогают получить хорошо оптимизированныепрограммы.Оптимизацияциклов.Цикломвпрограмменазываетсялюбаяпоследовательность участков программы, которая может выполняться повторно.Циклы необязательно должны оформляться с помощью операторов цикла, и чтобы ихобнаружить, используется граф управления программы.
Обычно циклы содержат в себеодин или более линейных участков, где производятся вычисления, поэтому для нихмогут применяться все методы оптимизации линейных участков. Для оптимизациициклов разработаны и специальные методы:•••вынесение инвариантных вычислений из тела цикла,замена операций с переменными цикла,слияние, расщепление и развертывание циклов.Вынесение инвариантных вычислений из тела цикла сводится к вынесению запределы цикла тех операций, операнды которых не изменяются в процессе выполненияцикла. Например, циклfor (i = 0; i < limit – 2: i ++) A [i] = B * C * A [i];может быть заменен последовательностью операцийD = B * C; k = limit – 2;for (i = 0; i < k: i ++) A [i] = D * A [i];при условии, что значения B , C и limit не изменяются в теле цикла. При этомумножение B*C будет выполнено только один раз, а не 10, как в исходном варианте.Для вычислительных машин с векторной архитектурой оптимизация цикловстановится машинно-зависимой.
Например, для некоторых векторных архитектур46снижение времени выполнения программы иногда можно получить, не проводявынесение вычислений из циклов, а внося их туда: в таких архитектурах оказываетсяэффективнее провести повторные вычисления с помощью векторных регистров, чемнарушать работу векторного конвейера выполнением операции со скалярнойпеременной.Замена операций с переменными цикла производится на основе пониманиятого, что с каждым шагом цикла значение переменной цикла меняется на один “шагцикла”. Многие алгоритмы устроены так, что в ходе вычислений некоторые величиныоказываются пропорциональными номеру итерации. При этом в программахпроизводится умножение этих величин на значение переменной цикла.
Такиепеременные называются индуктивными. Все такие переменные заменяютсякомпилятором на одну, значения других вычисляются с помощью коэффициентов.Например, последовательность операторовS = 10; for (i = 0; i < N; i ++) A [i] = i * S;может быть заменена последовательностью операцийS = 10; T = 0; for (i = 0; i < 10; i ++) T = T + S, A [i] = T;Вычисление значения A[i] тоже может потребовать индуктивной переменной,так как изменение значения переменной цикла на 1 может приводить к изменениюадреса элемента массива на величину sizeof (A[0]), значит, &A[i] ≡A+sizeof(A[0])*i.В тех вычислительных системах, в которых время выполнения операцииумножения превышает время выполнения сложения, удается добиться немалогоэффекта.
Иногда оказывается возможным отказаться от переменной цикла, как вследующем примере:S = 10; for (i = 0; i < N; i ++) R = R + F (S), S = S + 10;В этом примере две индуктивные переменные, но переменную цикла можнопросто исключить:S = 10; M = S + N * 10; while (S <= M) R = R + F (S), S = S + 10;Таким преобразованием за счет введения дополнительной переменной M удалосьисключить N операций сложения для переменной i.Слияние и развертывание циклов – это два различных вариантапреобразований: слияния двух смежных или вложенных циклов в один и замена циклана последовательность операций (часто линейную). Слияние смежных циклов снезависимыми внутренними операторами S1 и S2 позволяет снизить накладные расходына организацию циклической работы:for (i = 0; i < n; i ++) { S1 }for (i = 0; i < n; i ++) { S1; S2 }for (i = 0; i < n; i ++) { S2 }Замену циклов последовательностями операций можно выполнять для циклов,кратность которых известна уже на стадии компиляции.47Расщепление цикла может оказаться полезным в случае наличия в теле циклаусловных операторов:for (i = 0; i < n; i ++){ if (x < y){ S1 ; }else{ S2 ; }}if (x < y)for (i = 0; i < n; i ++) { S1; }else for (i = 0; i < n; i ++) { S2; }Развертывание цикла позволяет в определенных случаях уменьшить числопроверок условий завершения цикла, а также создать предпосылки для последующегораспараллеливания выполнения операций:for (i = 0; i < n; i ++){ A [i] = B [i] * C [i]; }for (i = 0; i < n; i += 2){ A [i] = B [i] * C [i];A [i+1] = B [i+1] * C [i+1]; }Кажущиеся правильными преобразования не всегда ведут к построениюэквивалентной программы.
Например, циклfor (i = 1; i < 100; i ++) { … A = i * B; … }может быть преобразован к виду:for (i = 1; i < 100; i ++) { … A = A + B; … }однако это преобразование будет правильным только для целочисленных переменныхA и B. Если в теле цикла использованы вещественные переменные, то при ихпоследовательном суммировании может накапливаться погрешность, которая призначительном числе итераций может стать недопустимо большой.3.3.4.2. Машинно-зависимая оптимизацияМашинно-зависимые методы оптимизации ориентированы на конкретнуюархитектуру вычислительной системы, то есть на совокупность аппаратных ипрограммных составляющих, а также взаимосвязи между ними. Некоторые аспектыметодов машинно-зависимой оптимизации имеют общий характер и применяютсямногими разработчиками.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
