Л.Е. Карпов - Системы программирования (1114903), страница 13
Текст из файла (страница 13)
К таким аспектам относятся:•••••••учет регистровой структуры вычислительной аппаратуры,удаление излишних команд,оптимизация потока управления и удаление недостижимых участковпрограмм,снижение “стоимости” программы,использование машинных идиом,слияние, дробление и развертывание циклов, иногда требующееся из-затехнических особенностей аппаратуры,учет векторных и конвейерных свойств архитектуры.Одним из важнейших аспектов является учет распространенной особенностимногих вычислительных архитектур, строящихся на программно доступных регистрах.Среди этих регистров одни могут быть специально выделены для выполненияопределенных задач (управление стеком), а другие представляют собой регистрыобщего назначения. Выполнение операций над регистрами производится существеннобыстрее, чем над элементами памяти, к тому же часто над элементами памяти, кроме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 чисел это изменение уменьшаетсовокупное время работы в 2.5 раза, для 100000 чисел снижение времени работыреальной программы – в 1000 раз!503.3.5. Основные методы динамического распределения памятиВо время распределения памяти компилятор ставит в соответствиелексическим единицам исходной программы адрес, определяет их размер иприписывает им атрибуты области памяти, необходимой для этой лексическойединицы. О лексических единицах речь идет потому, что выбор области памяти ираспределение памяти в ней проводятся не только для объектов данных, но и длявыполняемых фрагментов программ – операторов, блоков, функций и процедур.Область памяти – это совокупность объединенных между собой элементов памяти,причем логика объединения задается семантикой входного языка.Семантика всех программ подразумевает, что при выполнении программобласти памяти будут необходимы для хранения:••••кодов пользовательских программ;данных, необходимых для работы этих программ;кодов системных программ, обеспечивающих поддержку пользовательскихпрограмм в период их выполнения;записей о текущем состоянии процесса выполнения программ (например,записей об активации процедур).ЛокальнаяГлобальнаяОбласть памятиСтатическаяДинамическаяСтековаядисциплинаДисциплина произвольногораспределенияРаспределяемаяпрограммистомРаспределяемаякомпиляторомОбласти памяти, в которых проводится распределение, обладают двумяхарактеристиками – характеристикой использования этой памяти в программе ихарактеристикой способа ее распределения.
По способу использования области памятиделятся на глобальные и локальные, а по способу распределения – на статические идинамические.Наиболее проста стратегия статического распределения памяти, всоответствии с которой память автоматически распределяется в статических областяхкомпилятором. Размеры объектов, размещаемых в этих областях, никогда не меняются,51как и та часть адресов этих объектов, которая указывает их положение внутри области.Единственное, что может измениться – это начальный адрес самой области, но и этоизменение происходит до выполнения программы, перед загрузкой ее в память.Стратегия динамического распределения выбирается в тех случаях, когда настадии компиляции не удается определить положение объекта в некоторой областипамяти и/или его размер. При динамическом распределении возможно применениеразличных дисциплин, наиболее известны из которых стековая дисциплинараспределения и дисциплина произвольного распределения (распределение в “куче”).В случае выбора стековой дисциплины необходимо выделить некоторыйфрагмент свободной памяти, на котором при запросах ресурсов памяти будетмоделироваться работа со стеком областей памяти в стиле “первым освобождаетсяпоследний из ранее размещенных фрагментов памяти”.
Дисциплина произвольногораспределения памяти, по-существу, означает отсутствие какой-либо дисциплины вэтом распределении. Захват фрагментов памяти может осуществляться попроизвольным запросам, так же производится и освобождение памяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
