И.А. Волкова, И.Г. Головин, Л.Е. Карпов - Системы программирования (1114897), страница 13
Текст из файла (страница 13)
Например, циклfor (i = 1; i < 100; i ++) { … A = i * B; … }может быть преобразован к виду:for (i = 1; i < 100; i ++) { … A = A + B; … }однако это преобразование будет правильным только для целочисленных переменныхA и B. Если в теле цикла использованы вещественные переменные, то при ихпоследовательном суммировании может накапливаться погрешность, которая призначительном числе итераций может стать недопустимо большой.3.3.4.2. Машинно-зависимая оптимизацияМашинно-зависимые методы оптимизации ориентированы на конкретнуюархитектуру вычислительной системы, то есть на совокупность аппаратных ипрограммных составляющих, а также взаимосвязи между ними. Некоторые аспектыметодов машинно-зависимой оптимизации имеют общий характер и применяютсямногими разработчиками.
К таким аспектам относятся:•••••••учет регистровой структуры вычислительной аппаратуры,удаление излишних команд,оптимизация потока управления и удаление недостижимых участковпрограмм,снижение “стоимости” программы,использование машинных идиом,слияние, дробление и развертывание циклов, иногда требующееся из-затехнических особенностей аппаратуры,учет векторных и конвейерных свойств архитектуры.Одним из важнейших аспектов является учет распространенной особенностимногих вычислительных архитектур, строящихся на программно доступных регистрах.Среди этих регистров одни могут быть специально выделены для выполнения48определенных задач (управление стеком), а другие представляют собой регистрыобщего назначения. Выполнение операций над регистрами производится существеннобыстрее, чем над элементами памяти, к тому же часто над элементами памяти, кромеопераций пересылки, вообще нельзя выполнять никаких операций, а требуетсяпредварительная загрузка их содержимого на регистры.
Все это ставит передразработчиками почти всех компиляторов задачи распределения регистров иоптимизации их использования. Эта задача в общем случае является NP-полной, но вкаждом конкретном случае удается найти приемлемое решение.Простейшим методом распределения регистров является их “жесткое”распределение, например, только для хранения фактических параметров процедури/или важнейших переменных.
Такой выбор, с одной стороны, упрощает разработкукомпилятора, с другой стороны, ограничивает эффективность использованиярегистров.Более сложным является распределение на основе анализа графа потокауправления. Граф потока управления строится из узлов, которыми являются базовыеблоки программы (последовательности команд, имеющие один вход и один выход), идуг, соответствующих переходам от одного базового блока к другому при наличиинекоторых входных для базового блока данных.
Результаты вычисления некоторыхвыражений, вычисляемых в базовых блоках, оказываются при этом внутренними(промежуточными), некоторые другие результаты переходят в смежные блоки. Такиерезультаты и пытаются хранить на регистрах.Распределение на основе раскраски графа взаимодействия регистровпроводится так:•••число регистров полагается равным числу переменных в программе.два узла (регистра) соединяются дугой, если два регистра должны хранитьнекоторые значения одновременно.граф раскрашивается так, чтобы никакие соседние узлы не получилиодинаковый цвет, при этом число цветов соответствует числу реальноимеющихся регистров. Если цветов не хватает, узлы итеративно удаляются,причем максимально долго остаются на регистрах переменные,используемые во внутренних циклах программы.Поскольку при выполнении вычислений регистров может не хватать,содержимое некоторых из них приходится выгружать в память (независимо отвыбранной стратегии их распределения).
Выгруженное значение может понадобиться впоследующих вычислениях, и его придется снова читать из памяти. Это значит, что привычислениях встает проблема выбора того регистра, содержимое которого можновыгрузить с минимальными потерями в производительности.Компилятор должен анализировать полученную им программу и выяснять, какоеиз значений ему понадобится для дальнейших вычислений и когда оно понадобится.Обычно алгоритм выбора регистра для выгрузки работает так, что им выбираетсярегистр, содержимое которого понадобится позднее других (это не всегда оптимально,но несложно определяется).Аналогичным образом производится оптимизация специальных регистров –сумматоров, индексных регистров, регистров базирования и других.
Проблемараспределения регистров усложняется тем, что некоторые вычислительные и/илиоперационные системы накладывают дополнительные ограничения на использование49регистров. Например, для некоторых операций иногда требуется сразу пара регистров,причем имеется требование к четности номера первого регистра из этой пары.При генерации команд на основе внутреннего представления отдельныхоператоров программы довольно часто возникают ситуации, когда в общем потокевозникают лишние команды. Например, после записи содержимого некоторогорегистра в память может сразу следовать команда загрузки этого регистра из того жеэлемента памяти (проблема “считывания после записи”). Вторая команда оказываетсяизлишней, а компилятор старается удалить из созданной последовательности командывсе излишние команды.При проведении оптимизации каждой команде присваивается некотораяхарактеристика, называемая ее “стоимостью” (с точки зрения времени выполнениякоманды, использования аппаратных ресурсов и т.
п.). Компилятор стремится снизитьсовокупную стоимость программы, то есть заменить “дорогие” команды более“дешевыми”, но дающими тот же результат. Подобные преобразования могут,например, приводить к замене операции возвышения в степень операциями умножения,а в определенных случаях – даже операциями сдвига влево. Качество оптимизацииоказывается особенно высоким, если удается заменять не отдельные “дорогие”команды, а связки команд.В каждой вычислительной машине могут оказаться аппаратно реализованныекоманды, удобные для выполнения специфических операций (машинные идиомы).Можно встретить системы команд с аппаратными возможностями по вычислениютригонометрических функций, с одновременным вычислением частного и остатка вцелочисленном делении, с выполнением некоторых команд в режиме автоувеличенияили автоуменьшения, при которых к операнду прибавляется (или вычитается из него)единица до или после использования его значения в операции.
Например, режимыавтоувеличения и автоуменьшения очень удобны для организации работы со стеком, атакже при выполнении операций вида i:=i+1.Все большее развитие получают архитектуры, ориентированные напараллельные или векторные вычисления. Очень часто в таких архитектурах удаетсясовместить одновременное выполнение нескольких операций. Перед компиляторамиэто ставит задачу перераспределения последовательности вычислений так, чтобы рядомоказывались операции, не зависящие друг от друга (в противном случае, их нельзябудет выполнять параллельно).
Для всей программы в целом решить такую задачуневозможно, но некоторые участки программы могут быть хорошо оптимизированы.Например, в архитектуре с одним потоком вычислений операцию A+B+C+D+E+F надовыполнять в порядке ((((A+B)+C)+D)+E)+F. Если же вычислительная машинаимеет два потока вычислений, лучше организоватьвычислениятак:((A+B)+C)+((D+E)+F). Тогда операции A+B и D+E, а также сложение сиспользованием их результатов могут выполняться параллельно.При рассмотрении полезности оптимизирующих преобразований нужноучитывать, что наибольший выигрыш возникает при участии самого программиста,причем возникает он еще на этапе выбора алгоритма, который реализуется впрограмме. Верный выбор алгоритма всегда способствует получению эффективнойпрограммы. Например, замена алгоритма сортировки вставками алгоритмом быстройсортировки может привести к изменению времени сортировки N элементов с 2.02N2на 12log2N.
Для реальной программы сортировки 100 чисел это изменение уменьшает50совокупное время работы в 2.5 раза, для 100000 чисел снижение времени работыреальной программы – в 1000 раз!3.3.5. Основные методы динамического распределения памятиВо время распределения памяти компилятор ставит в соответствие языковымединицам исходной программы адрес, определяет их размер и приписывает иматрибуты области памяти, необходимой для этой языковой единицы. О языковыхединицах речь идет потому, что выбор области памяти и распределение памяти в нейпроводятся не только для объектов данных, но и для выполняемых фрагментовпрограмм – операторов, блоков, функций и процедур. Область памяти – этосовокупность объединенных между собой элементов памяти, причем логикаобъединения задается семантикой входного языка.Семантика всех программ подразумевает, что при выполнении программобласти памяти будут необходимы для хранения:••••кодов пользовательских программ;данных, необходимых для работы этих программ;кодов системных программ, обеспечивающих поддержку пользовательскихпрограмм в период их выполнения;записей о текущем состоянии процесса выполнения программ (например,записей об активации процедур).ЛокальнаяГлобальнаяОбласть памятиСтатическаяДинамическаяСтековаядисциплинаДисциплина произвольногораспределенияРаспределяемаяпрограммистомРаспределяемаякомпиляторомОбласти памяти, в которых проводится распределение, обладают двумяхарактеристиками – характеристикой использования этой памяти в программе ихарактеристикой способа ее распределения.
По способу использования области памятиделятся на глобальные и локальные, а по способу распределения – на статические идинамические.51Наиболее проста стратегия статического распределения памяти, всоответствии с которой память автоматически распределяется в статических областяхкомпилятором. Размеры объектов, размещаемых в этих областях, никогда не меняются,как и та часть адресов этих объектов, которая указывает их положение внутри области.Единственное, что может измениться – это начальный адрес самой области, но и этоизменение происходит до выполнения программы, перед загрузкой ее в память.Стратегия динамического распределения выбирается в тех случаях, когда настадии компиляции не удается определить положение объекта в некоторой областипамяти и/или его размер.
При динамическом распределении возможно применениеразличных дисциплин, наиболее известны из которых стековая дисциплинараспределения и дисциплина произвольного распределения (распределение в “куче”).В случае выбора стековой дисциплины необходимо выделить некоторыйфрагмент свободной памяти, на котором при запросах ресурсов памяти будетмоделироваться работа со стеком областей памяти в стиле “первым освобождаетсяпоследний из ранее размещенных фрагментов памяти”. Дисциплина произвольногораспределения памяти, по-существу, означает отсутствие какой-либо дисциплины вэтом распределении. Захват фрагментов памяти может осуществляться попроизвольным запросам, так же производится и освобождение памяти. Выделениепамяти в соответствии с дисциплиной произвольного распределения памяти можетпроисходить явно самим разработчиком программы, а может осуществлятьсякомпилятором автоматически, то есть неявно.Выбор той или иной стратегии и дисциплины основывается на следующихкритериях:•••эффективность начального распределения памяти;эффективность восстановления статуса “свободной памяти”;эффективность уплотнения свободных участков областей памяти(эффективность объединения свободных фрагментов во фрагментысуммарного размера).Исходными данными для распределения памяти являются информационныетаблицы компилятора, полученные на фазах анализа исходной программы.
Этаинформация собирается на основе обработки операторов описания объектов данныхпрограммы и пополняется при компиляции исполняемых операторов программы наоснове семантических правил входного языка. Именно поэтому семантический анализтакже должен предшествовать фазе распределения памяти.С учетом выделенных объектов для хранения в памяти наиболее целесообразновыбирать••для кодов пользовательских программ, кодов системных программ, буферовввода/вывода: статические области памяти и стратегию статического распределения.для данных разной природы, необходимых для работы различных программ: статические области памяти и стратегию статического распределения– для глобальных, статических (не глобальных, а собственных)переменных, констант, внутренних структур данных, возникающихпри трансляции некоторых языковых конструкций, например, таблицвиртуальных функций для полиморфных классов;52•динамическую стратегию со стековой дисциплиной – дляраспределения памяти под локальные переменные; динамическуюстратегиюсдисциплинойпроизвольногораспределения – для переменных, создаваемых по явному запросу спомощью специальных операторов или библиотечных функций(операторы new в Паскале и Си++, функция malloc() в Си), а такжедля переменных, размеры которых меняются в процессе выполненияпрограммы (объекты типа vector из библиотеки STL).для записей о текущем состоянии процесса выполнения программ, а такжедля записей о входах в блоки операторов, которые можно рассматривать вкачестве процедур без параметров.Например, для записей об активации процедур, которые содержат всюнеобходимую информацию для обеспечения выполнения процедур ивозврата в точки вызова, в частности, фактические параметры, локальные, втом числе временные переменные, адреса возврата, значения регистров вмомент входа в процедуру, ссылки на подобные записи объемлющих ивызвавших процедур.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
