Tempora mutantur, et nos mutamur in illis




НазваниеTempora mutantur, et nos mutamur in illis
страница3/9
Дата публикации09.03.2013
Размер1.08 Mb.
ТипДокументы
uchebilka.ru > Информатика > Документы
1   2   3   4   5   6   7   8   9
^

Фундаментальные проблемы профилировки "в малом"


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


^

Конвейеризация или пропускная способность vs латентность


Начнем с того, что в конвейерных системах такого понятия как "время выполнения одной команды" просто нет. Уместно провести такую аналогию. Допустим, некоторый приборостроительный завод выпускает шестьсот микросхем памяти в час. Ответьте: сколько времени занимает производство одной микросхемы? Шесть секунд? Ну конечно же нет! Полный технологический цикл составляет не секунды, и даже не дни, а месяцы! Мы не замечаем этого лишь благодаря конвейеризации производства, т.е. разбиении его на отдельные стадии, через которые в каждый момент времени проходит по крайней мере одна микросхема.

Количество продукции, сходящей с конвейера в единицу времени, называют его пропускной способностью. Легко показать, что пропускная способность в общем случае обратно пропорциональна длительности одной стадии, – действительно, чем короче каждая стадия, тем чаще продукция сходит с конвейера. При этом количество самых стадий (попросту говоря длина конвейера) не играет абсолютно никакой роли. Кстати, обратите внимание, что практически на всех заводах каждая стадия представляет собой элементарную операцию, – вроде "накинуть ключ на гайку" или "стукнуть молотком". И не только потому, что человек лучше приспосабливается к однообразной монотонной работе (наоборот, он, в отличии от автоматов, ее терпеть не может!). Элементарные операции, занимая чрезвычайно короткое время, обеспечиваю конвейеру максимальную пропускную способность.

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

С одной стороны и хорошо, – конвейер крутится как угорелый, спуская до 6 микроинструкций за такт и какое нам собственно дело до его длины? А вот какое! Вернемся к нашей аналоги с приборостроительным заводом. Допустим, захотелось нам запустить в производство новую модель. Вопрос: через какое время она сойдет с конвейера? (Бюрократическими проволочками можно пренебречь). Ни через шесть секунд, ни через час новая модель готова не будет и придется ждать пока весь технологический цикл не завершится целиком.

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

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

Малоприятным следствием становится невозможность определения реального времени исполнения компактного участка кода (если, конечно, не прибегать к эмуляции процессора). До тех пор, пока время выполнения участка кода не превысит латентность конвейера (30 тактов на P6), мы вообще ничего не сможем сказать ни о коде, ни о времени, ни о конвейере!


^

Неточность измерений


Одно из фундаментальных отличий цифровой от аналоговой техники заключается в том, что верхняя граница точности цифровых измерений определяется точностью измерительного инструмента (точность аналоговых измерительных инструментов, напротив, растет с увеличением количества замеров).

А чем можно измерять время работы отдельных участков программы? В персональных компьютерах семейства IBM PC AT имеются как минимум два таких механизма: системный таймер (штатная скорость: 18,2 тика в секунду, т.е. 55 мсек., максимальная скорость – 1.193.180 тиков в секунду или 0,84 мсек.), часы реального времени (скорость 1024 тика в секунду т.е. 0,98 мсек.). В дополнении к этому в процессорах семейства Pentium появился так называемый регистр счетчик - времени (Time Stamp Counter), увеличивающийся на единицу каждый такт процессорного ядра.

Теперь – разберемся со всем этим хозяйством подробнее. Системный таймер (с учетом времени, расходующего на считывание показаний) обеспечивает точность порядка 5 мсек., что составляет более двух десятков тысяч тактов даже в 500 MHz системе! Это – целая вечность для процессора. За это время он успевает перемолотить море данных, скажем, отсортировать сотни полторы чисел. Поэтому, системный таймер для профилирования отдельных функций непригоден. В частности, нечего и надеяться с его помощью найти узкие места функции quick sort! Да что там узкие места – при небольшом количестве обрабатываемых чисел он и общее время сортировки определяет весьма неуверенно.

Причем, прямого доступа к системному таймеру под нормальной операционной системой никто не даст, а минимальный временной интервал, еще засекаемый штатной Си-функций clock(), составляет всего лишь 1/100 сек, – а это годиться разве что для измерения времени выполнения всей программы целиком.

Точность часов реального времени так же вообще не идет ни в какое сравнение с точность системного таймера (перепрограммированного, разумеется).

Остается надеяться лишь на Time Stamp Counter. Первое знакомство с ним вызывает просто бурю восторга и восхищения "ну наконец-то Intel подарила нам то, о чем мы так долго мечтали!". Судите сами: во-первых, операционные системы семейства Windows (в том числе и "драконическая" в этом плане NT) предоставляют беспрепятственный доступ к машинной команде RDTSC, читающий содержимое данного регистра. Во-вторых, поскольку он инкрементируется каждый такт, создается обманчивое впечатление, что с его помощью возможно точно определять время выполнения каждой команды процессора. Увы! На самом же деле это не далеко так!

Начнем с того, что в конвейерных системах (как мы уже помним) вообще нет такого понятия как время выполнения команды и следует говорить либо о пропускной способности, либо латентности. Сразу же возникает вопрос: а что же все-таки RDTSC меряет? Документация Intel не дает прямого ответа, но судя по всему, RDTSC считывает содержимое регистра счетчика-времени в момент прохождения данной инструкции через соответствующее исполнительное устройство. Причем, RDTSC – это неупорядоченная команда, т.е. она может завешаться даже раньше предшествующих ей команд. Именно так и произойдет если предшествующая команда простаивает в ожидании операндов.

Рассмотрим крайний случай, когда измеряется время выполнения минимальной порции кода (одна машинная команда уходит на то, чтобы сохранить считанное значение в первой итерации):
RDTSC ; читаем значение регистра времени

; и помещаем его в регистры EDX и EAX
MOV [clock], EAX ; сохраняем младшее двойное слово

; регистра времени в переменную clock
RDTSC ; читаем регистр времени еще раз
SUB EAX, [clock] ; вычисляем разницу замеров между

; первым и вторым замером

^ Листинг 5 Попытка замера времени выполнения одной машинной команды
При прогоне этого примера на P-III он выдаст 32 тактов, вызывая тем самым риторический вопрос: "а почему, собственно, так много?" Хорошо, оставим выяснение обстоятельств "похищения процессорных тактов до лучших времени", а сейчас попробуем измерять время выполнения какой-нибудь машинной команды, ну скажем, INC EAX, увеличивающий значение регистра EAX на единицу. Поместим ее между инструкциями RDTSC и перекомпилируем программу.

Вот это да! Прогон показывает все те же 32 такта. Странно! Добавим-ка мы еще одну INC EAX. Как это так – снова 32 такта?! Зато при добавлении сразу трех инструкций INC EAX контрольное время исполнения скачкообразно увеличивается на единицу, что составляет 33 такта. Четыре и пять инструкций INC EAX дадут аналогичный результат, а вот при добавлении шестой, результат изменений вновь подскакивает на один такт.

Но ведь процессор Pentium, имея в наличии всего лишь одно арифметическое устройство, никак не может выполнять более одного сложения за такт одновременно! Полученное нами значение в три команды за такт – это скорость их декодирования, но отнюдь не исполнения! Чтобы убедиться в этом запустим на выполнение следующий цикл:
MOV ECX,1000 ; поместить в регистр ECX значение 1000
@for: ; метка начала цикла

INC EAX ;\

INC EAX ; +- одна группа профилируемых инструкций

INC EAX ;/

INC EAX ;\

INC EAX ; +- вторая группа профилируемых инструкций

INC EAX ;/
DEC ECX ; уменьшить значение регистра ECX на 1

; (здесь он используется в качестве

; счетчика цикла)
JNZ @xxx ; до тех пор, пока ECX не обратится в ноль

; перепрыгивать на метку @for
^ Листинг 6 Измерение времени выполнения 6х1000 машинных команд INC
На P-III выполнение данного цикла займет отнюдь не ~2.000, а целых 6.781 тактов, что соответствует по меньшей мере одному такту, приходящемуся на каждую математическую инструкцию! Следовательно, в предыдущем случае, при измерении времени выполнения нескольких машинных команд, инструкция RDTSC "вперед батьки пролезла в пекло", сообщив нам совсем не тот результат, которого мы от нее ожидали!

Вот если бы существовал способ "притормозить" выполнение RDTSC до тех пор, пока полностью не будут завершены все предшествующие ей машинные инструкции… И такой способ есть! Достаточно поместить перед RDTSC одну из команд упорядоченного выполнения. Команды упорядоченного выполнения начинают обрабатываться только после схода с конвейера последней предшествующей ей неупорядоченной команды и, покуда команда упорядоченного выполнения не завершится, следующие за ней команды мирно дожидаются своей очереди, а не лезут как толпа дикарей вперед на конвейер.

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

Многие руководства (в частности и Ангер Фог в своем руководстве "^ How to optimize for the Pentium family of microprocessors" и технический документ "Using the RDTSC Instruction for Performance Monitoring" от корпорации Intel) предлагают использовать приблизительно такой код:
XOR EAX,EAX ; вызываем машинную команду CPUID,

CPUID ; после выполнения которой все

; предыдущие машинные инструкции

; гарантированно сошли к конвейера

; и потому никак не могут повлиять

; на результаты наших замеров
RDTSC ; вызываем инструкцию RDTSC, которая

; возвращает в регистре EAX младшее

; двойное слово текущего значения

; Time Stamp Counter 'a
MOV [clock],EAX ; сохраняем полученное только что

; значение в переменной clock
// … ;\

// профилируемый код ; +-здесь исполняется профилируемый код

// … ;/
XOR EAX,EAX ; еще раз выполняем команду CPUID,

CPUID ; чтобы все предыдущие инструкции

; гарантированно успели покинуть

; конвейер
RDTSC ; вызываем инструкцию RDTSC для чтения

; нового значение Time Stamp Count 'a
SUB EAX,[clock] ; вычисляем разность второго и первого

; замеров, тем самым определяя реальное

; время выполнения профилируемого

; фрагмента кода
^ Листинг 7 Официально рекомендованный способ вызова RDTSC для измерения времени выполнения
К сожалению, даже этот, официально рекомендованный, код все равно не годится для измерения времени выполнения отдельных инструкций, поскольку полученный с его помощью результат представляет собой полное время выполнения инструкции, т.е. ее латентность, а отнюдь не пропускную способность, которая нас интересует больше всего. (Кстати, и у Intel, и Фрога есть одна грубая ошибка – в их варианте программы перед инструкцией CPUID отсутствует явное задание аргумента, который CPUID ожидает увидеть в регистре EAX. А, поскольку, время ее выполнения зависит от аргумента, то и время выполнения профилируемого фрагмента не постоянно, а зависит от состояния регистров на входе и выходе. В предлагаемом много варианте, инициализация EAX осуществляется явно, что страхует профилировщик от всяких там наведенных эффектов).
Имеется и другая проблема, еще более серьезная, чем первая. Вы помните постулат квантовой физики, сводящийся к тому, что всякое измерение свойств объекта неизбежно вносит в этот объект изменения, искажающие результат измерений? Причем, эти искажения невозможно устранить простой калибровкой, поскольку изменения могут носить не только количественный, но и качественный характер.

Если профилируемый код задействует те же самые узлы процессора, что и команды RDTSC/CPUID, время его выполнения окажется совсем иным нежели в "живой" действительности! Никаким ухищрениями нам не удастся достигнуть точности измерений до одного–двух тактов!

Поэтому, минимальный промежуток времени, которому еще можно верить, составляет, как показывает практика и личный опыт автора, по меньше мере пятьдесят – сто тактов.

Отсюда следствие: штатными средствами процессора измерять время выполнения отдельных команд невозможно.


^
* В поисках нуля *

Для комфортной работы всякий прибор следует


Аппаратная оптимизация


На мгновение отвлечемся от компьютеров и зададимся вопросом: можно ли с помощью обычной ученической линейки измерить толщину листа принтерной бумаги? На первый взгляд, тут без штангенциркуля ну никак не обойтись… Но, если взять с полсотни листов бумаги и плотно сложить их друг с другом… вы уже поняли куда я клоню? Пусть погрешность измерения толщины образовавшегося "кирпича" составит 1 мм, тогда – точность определения толщины каждого отдельно взятого листа будет не хуже чем 0,02 мм, что вполне достаточно для большинства повседневных целей!

Почему бы не применить эту технику для измерения времени выполнения машинных команд? В самом деле, время выполнения одной команды так мало, что ничем его не измерять (см. "Неточность измерений"), но если мы возьмем сто или даже сто тысяч таких команд, то… Увы! Машинные команды – ведут себя совсем не так, как листы бумаги. Неоднородность конвейера приводит к тому, что зависимость между количеством и временем выполнения команд носит ярко выраженный нелинейный характер.

К тому же, современные процессоры слишком умы, чтобы воспринимать переданный им на выполнение код буквально. Нет! Они подходят к этому делу весьма творчески. Вот допустим встретится им последовательность команд MOV EAX, 1; MOV EAX, 1; MOV EAX, 1, каждая из которых помещает в регистр EAX значение "1". Думаете, процессор как полный идиот, исполнит все три команды? Да как бы не так! Поскольку, результат двух первых присвоений никак не используется, процессор отбросит эти команды как ненужные, затратив время лишь на их декодирование, и ощутимо сэкономит на выполнении!

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


^

Низкая "разрешающая способность"


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

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

Строго говоря, не эмулирующие профилировщики показывают не саму горячую точку, а некоторую протяжную область к которой эта "горячая" точка принадлежит.


1   2   3   4   5   6   7   8   9

Похожие:

Tempora mutantur, et nos mutamur in illis iconНовикова Михаила Петровича Gaudeamus tffttur Juvenes dum sunuts!...
Учебное пособие предназначено для студентов вузов и учащихся колледжей, гимназий, школ

Tempora mutantur, et nos mutamur in illis iconРеферат скачан с сайта allreferat wow ua
Возжелавшие ауспиций: «другие семьи» 7 Перспективы 8Раздел II. 10 “O tempora! O mores!” 10 Биология открытого брака 12 Моногамия...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<