Тема 2.9. Оптимизация программ. Оптимизирующие компиляторы

Тема 2.8. Эффективность программ

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

Понятие оптимизации программ

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

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

Основная цель профилировки – это исследование характера поведения приложения во всех его точках. В зависимости от степени детализации в качестве «точки» рассматривается как отдельная машинная команда, так и целая конструкция высокого языка - функция, цикл, процедура. Сложная программа состоит из большого числа функций. Нет смысла оптимизировать их все – трудоемкость такого подхода будет выше выгод, полученных от оптимизации программы целиком. Для начала необходимо локализовать участки кода с максимальной вычислительной трудоемкостью. Участки программы, которые в наибольшей степени влияют на ее производительность, в силу наиболее частого выполнения или своей ресурсоемкости называются критическим кодом. В поиске критического кода программы используют профайлеры (профилировщики) – специальные программы, которые измеряют временные затраты на выполнение участков кода программы. Профилировщики представляют возможности для оптимизации программ. К таким программам относятся Intel VTune, AMD Code Analyst, profile.exe и множество других. Наиболее мощным из них на сегодняшний день является пакет от Intel. Эта программа позволяет измерить время обработки каждой команды и вывести полную статистику о состоянии процессора при выполнении каждой команды.

Большинство современных профилировщиков поддерживают следующий набор базовых операций:

• определение общего времени исполнения каждой точки программы;

• определение удельного времени исполнения каждой точки программы;

• определение причины и/или источника конфликтов;

• определение количества вызовов той или иной точки программы;

• определение степени покрытия программы.

Основные правила оптимизации:

1. Прежде чем приступать к оптимизации, необходимо иметь надежно работающий неоптимизированный вариант.

2. Основной прирост оптимизации дает не учет особенностей системы, а алгоритмическая оптимизация.

3. Обнаружив профилировщиком узкие места необходимо произвести оптимизацию в рамках языка высокого уровня.

Возможны ситуации, где в неудовлетворительной производительности кода виноваты процессор или подсистема памяти, а не компилятор. Лишь после анализа листинга следует приступать к ассемблерной оптимизации.

Оптимизация начинается с выделения профилировщиком критического кода и анализа его неоптимальности. Причем каждое внесенное изменение необходимо проверять профилировщиком. После завершения оптимизации локального фрагмента программы, необходимо выполнить контрольную профилировку всей программы целиком на предмет обнаружения новых появившихся «горячих точек».

Проводя оптимизацию, не следует забывать о ее цели. Фактически идеал недостижим, поэтому оптимизацию следует завершать когда:

1. Производительность программы признана удовлетворяющей;

2. В программе отсутствуют «горячие точки», то есть количество инструкций равномерно распределено по все программе, и дальнейшая оптимизация потребует переписывания большого количества кода;

3. Сложность алгоритма настолько высока, что не представляется возможным дальнейшая оптимизация без значительных временных затрат;

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

Ко всем методам оптимизации алгоритма предъявляются следующие требования:

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

2. оптимизация не должна увеличивать трудоемкость разработки (в том числе тестирования) приложения более чем на 10-15%.

3. оптимизирующий алгоритм должен давать выигрыш не менее чем на 20-25% в скорости выполнения.

4. оптимизация не должна допускать безболезненное внесение изменений.

Алгоритмические приемы оптимизации

Приемы оптимизации программы можно разделить на алгоритмические и машинно-зависимые способы. В случае использования алгоритмических приемов оптимизации используются различные математические и логические методы для улучшения параметров алгоритма. Такой способ оптимизации невозможно автоматизировать, успешность его применения зависит от программиста. Способность программиста к алгоритмической оптимизации программы зависит от его понимания предметной области: владения им базовых концепций применяемых алгоритмов и особенностей предметной области программы.

В первую очередь это замена алгоритмов на более быстродействующие. Часто бывает, что более простой алгоритм показывает низкую производительность по сравнению с более сложными. Тогда, возможна замена эквивалентных алгоритмов, например, замена пузырьковой сортировки массива на быструю сортировку.

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

На практике используется весьма широкий набор машинно-независимых оптимизирующих преобразований, что связано с большим разнообразием неоптимальностей. К ним относятся:

• разгрузка участков повторяемости - это такой способ оптимизации, который состоит в вынесении вычислений из многократно исполняемых участков программы на участки программы, редко исполняемые. К этому виду преобразования относятся различные чистки зон, тел циклов и тел рекурсивных процедур, когда инвариантные по результату выполнения выражения, исполняемые при каждом прохождении участка повторяемости, выносятся из него. Если размещение осуществляется перед входом в участок повторяемости, то эту ситуацию называют чисткой вверх, если же за выходом из участка повторяемости, то чисткой вниз

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

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

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

• реализация действий - это способ повышения быстродействия программы за счет выполнения определенных ее вычислений на этапе трансляции.

• сокращение программы и другие методы.

Машинно-зависимые приемы оптимизации

Машинно-зависимые используют особенности устройства и работы конкретной системы. Ярким примером машинно-зависимой оптимизации является векторизация операций, т.е. использование потоковых расширений процессора, таких как MMX (MultiMedia eXtensions), SSE (Streaming SIMD Extensions) и т.п. Машино-зависимую оптимизацию можно выполнять двумя различными способами. Первый способ основан на понимании работы кодогенератора компилятора, его алгоритма и рекомендуется для приложений, в которых компилятор выбирается в начале проекта и в дальнейшем не меняется. При использовании такого способа преобразуется исходный код программы, написанный на языке высокого уровня. Для тех проектов, в которых заранее не известен компилятор (OpenSource проекты, кроссплатформенные приложения) применятся другой способ, основанный на замещении ресурсоемких участков кода ассемблерными вставками. При такой оптимизации ухудшается переносимость кода на другие платформы. Машинно-зависимые способы оптимизации довольно хорошо автоматизируются и большую часть их выполняют оптимизирующие компиляторы. Однако всегда остаются моменты в программе, которые можно оптимизировать вручную.

Раздел 3. Отладка и сопровождение программных продуктов.

Тема 3.1. Ошибки ПО: причины, источники и классификация.

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

Систематические характеры ошибок могут служить ориентиром для разработчиков при распределении усилий при создании комплекса программ. Кроме того характеристики ошибок в процессе проектирования программного комплекса помогают:

­ Оценивать реальное состояние проекта и планировать трудоемкость и срок до его завершения;

­ Рассчитывать необходимую эффективность средств защиты от невыявленных ошибок;

­ Оценивать требующиеся ресурсы ПК по памяти и производительности с учетом затрат на устранение ошибок;

­ Проводить исследования и осуществлять адекватный выбор показательной сложности компонент и комплекса в целом, а также некоторые другие показатели качества.

Анализ первичных ошибок в программе производиться на двух уровнях детализации:

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

2. обобщенно – по суммарным характеристикам их обнаружения в зависимости от продолжительности разработки, эксплуатации и сопровождения ПС.

Классификация ошибок:

1. технологические ошибки. В документации и фиксировании программ в памяти ПК составляют 5-10% от общего числа ошибок обнаруживаемых при отладке. Большинство технологических ошибок выявляется автоматически формализованными методами. Например, при ручной подготовке машинных носителей (перфокарты, магнитные ленты) исходные данные имеют вероятность искажения около 10^-3 на символ или 10^-4 на двоичный разряд, т.е. все зависит от селектирующих свойств человека.
2. программные ошибки по количеству и типам в первую очередь определяются степенью автоматизации программирования и глубиной формализованного контроля текстов программ. Количество программных ошибок зависит от квалификации разработчика и от общего объема программного комплекса, от глубины логического и информационного взаимодействия модулей и от ряда других факторов.
3. алгоритмические ошибки значительно труднее поддаются обнаружению методами формализованного автоматического контроля. К алгоритмическим следует отнести прежде всего ошибки обусловленные некорректной постановкой функциональных задач. Когда в спецификациях не полностью оговорены все условия, необходимые для получения правильного результата.
4. системные ошибки – сложных комплексов программ определяются прежде всего неполной информацией о реальных процессах происходящих в источниках и потребителях информации. На начальных стадиях проектирования не всегда удается точно сформулировать целевую задачу всей системы, а также целевые задачи основных групп программ и эти задачи уточняются в процессе проектирования. В соответствии с этим уточняются и конкретизируются техническое задание, описание программ, и выявляются отклонения от уточненного задания, которые могут квалифицироваться как системные ошибки.

Дата добавления: 2014-01-07