Побочные эффекты в экспериментальных исследованиях программ

Прямые измерения времени выполнения программ

Средства измерений. В качестве альтернативы статико-динамическому анализу может рассматриваться методика прямых измерений времени выполнения выделенных фрагментов программ. Основная прагматическая посылка для применения этого подхода заключается в предположении, что отдельные процессоры или процессорные узлы, используемые при создании масштабируемых вычислительных платформ, заранее известны и доступны. Далее, современные процессоры обладают развитым набором специальных средств для оценки временных характеристик программ. Так, начиная с семейства Pentium, в процессорах фирмы Intel имеется счетчик Time Stamp-Counter (TSC), содержимое которого инкрементируется в каждом цикле работы процессора. Вводя для каждого из фрагментов программы переменную-счетчик и обращаясь к регистру TSC в определенных для фрагмента контрольных точках входа и выхода, можно получить время его выполнения (сложность). Кроме счетчика TSC, особенности работы с которым мы рассмотрим чуть позже, в процессорах Pentium предусмотрен еще целый ряд контрольных счетчиков для оценки таких динамических характеристик программ, как число декодируемых команд, прерываний и обращений к кэш-памяти.

Чтобы пояснить общие принципы работы с такого рода средствами измерений, нам необходимо привести некоторые сведения по архитектуре команд IA-32. Это тем более важно, что функции измерений временных характеристик воспроизведены и в архитектуре IA-64, реализованной в процессорах Itanium. В соответствии с терминологией, принятой в руководстве по архитектуре команд IA-64, мы будем использовать понятия среды IA-32 и среды Itanium. Первая из них поддерживает и 16-разрядные процессоры (8086, 8088, 80286, 80386, 80486), и 32-разрядные машины (семейство Pentium, Celeron, Xeon и т.д.). Вторая среда обеспечивает выполнение команд архитектур IA-32 и IA-64.

Основными режимами функционирования процессоров Pentium являются:

– защищенный режим;

– режим реальной (16-разрядной) адресации;

– виртуальный режим процессора 8086.

В защищенном режиме выполняются функции, присущие только процессору Pentium и отсутствующие, в частности, в процессорах 8086, 8088. В этом режиме предусмотрено четыре уровня привилегий (CPL – current privilege level): уровень 0 используется операционной системой, уровень 3 присваивается пользовательским программам. В режиме реальной адресации Pentium работает как процессор 8086 или 8088. Виртуальный режим делает возможным исполнение программ для 8088 в специальной среде с защитой, создаваемой операционной системой. При этом, в отличие от режима реальной адресации, в случае возникновения сбоя программы ее не нужно снова перезапускать, а информация о сбое передается операционной системе.

Обычно к регистрам общего назначения в процессоре Pentium относят регистры EAX, ЕBX, ЕCX, ЕDX. Более специализированные регистры – ESI, EDI, EBP и ESP. В работе со счетчиками для измерений различных временных характеристик, как правило, используются следующие три регистра: EAX – основной арифметический регистр; ECX – регистр для организации циклов и хранения адресов модельных (виртуальных) регистров и счетчиков; EDX – регистр для умножения и деления.

Этой краткой сводки данных по среде IA-32 будет вполне достаточно, чтобы пояснить, как можно использовать средства измерений и соответствующие команды. В качестве примера рассмотрим команду RDPMC (Read Performance-Monitoring Counters). В шестнадцатеричной системе счисления она имеет код OF 33. Эта команда позволяет загрузить содержимое N-разрядного контрольного счетчика, адрес которого определяется содержимым [ECX] регистра ECX, в регистры EDX:EAX. В регистр EDX помещаются старшие (N–32) разряда, а в регистр EAX – младшие 32 разряда контрольного счетчика. Он может быть запрограммирован для подсчета различных событий (прерываний, декодирования команд соответствующего типа, числа обращений к кэш-памяти и т.д.). Команда RDPMC позволяет осуществлять контроль за временными характеристиками без вызовов операционной системы, что, естественно, исключает дополнительные затраты времени и вычислительных ресурсов. Кроме этого, она не линеаризует исследуемый код. Иными словами, это означает, что события, наступление которых обусловлено командами, предшествующими RDPMC, не обязательно должны произойти до начала выполнения команды RDPMC. По аналогии, события, обусловленные командами, следующими за RDPMC, не обязательно должны наступить после завершения выполнения этой команды. В среде IA-32 команда RDPMC доступна программам, исполняемым на уровнях привилегий 1, 2 и 3, если в контрольном регистре CR4 установлен флаг PCE. Если в защищенном режиме флаг PCE не установлен, а уровень привилегий (CPL) не равен 0, то происходит исключение (exception), называемое общей защитой (General Protection). Мнемонически оно обозначается как: #GP(0), в скобках указывается код ошибки. В виртуальном режиме и режиме реальной адресации исключение #GP наступает в случае, если не установлен флаг PCE в регистре CR4. В среде Itanium при работе с командой RDPMC используются регистры PMC (performance monitor configuration registers) и PMD (performance monitor data registers). Адрес регистра PMD определяется содержимым регистра ECX со смещением 4. Исключение #GP(0) происходит всякий раз, когда уровень привилегий отличен от 0, а бит PM регистра PMD равен 1 либо установлен флаг PSR.sp. Кроме этого, и в среде IA-32, и в среде Itanium всегда наступает исключение, если содержимое регистра ECX не соответствует задействованным счетчикам (Implemented Counters), т.е. делается попытка чтения из нереализованных счетчиков.

Для описания действия команд в архитектуре IA-32 принят псевдокод, подобный языку Pascal (в архитектуре IA-64 нотации действия команд основаны на языке С). Описание выполнения команды RDPMC может быть представлено следующим образом:

IF (ECX!=Implemented Counters) THEN #GP(0) /* исключение */

IF (Itanium System Environment) /* среда Itanium */

THEN

SECURED=PSR.sp || CR4.pce==0;

IF ((PSR.cpl==0)||(PSR.cpl!=0&&~PMC[ECX].pm&&~SECURED)))

THEN

EDX:EAXPMC[ECX+4]; /* чтение содержимого счетчика */

ELSE

#GP(0) /* исключение */

FI;

ELSE /*среда IA-32*/

IF ((CR4.PCE=1 OR ((CR4.PCE=0) AND (CPL=0)))

THEN

EDX:EAXPMD[ECX+4]; /* чтение содержимого счетчика */

ELSE (*CR4.PCE is 0 and CPL is 1, 2, or 3*)

#GP(0) /* исключение */

FI;

Средства, подобные контрольным счетчикам и счетчику TSC в семействе Pentium, есть и в процессорах Alpha. Они позволяют подсчитывать число промахов при обращении к кэш-памяти, число ошибочных предсказаний условных переходов и т.д.

Приведем пример. В архитектуре команд процессоров Alpha имеется инструкция rpcc (read processor cycle count), осуществляющая доступ к 64-разрядному регистру, 32 младших разряда которого образуют счетчик процессорных циклов. К слову, доступность для измерений лишь 32 разрядов – весьма серьезное ограничение, поскольку, например, на частоте 500 МГц счетчик переполняется примерно каждые 8,6 с. При наличии компилятора gcc в операционной системе LINUX обращение к счетчику циклов в семействе процессоров Aplha может быть реализовано следующим образом:

static inline u_int realcc (void) {

u_long cc; /* чтение содержимого 64 разрядов счетчика

в переменную сс */

asm volatile ("rpcc%0":"= r"(cc)::"memory");

return cc; /* возвращение 32 младших разрядов */

}

Чтобы обеспечить корректность результатов измерений при возможном переполнении счетчика, необходимо вызывать функцию gettime и определять, сколько раз имело место переполнение. Заметим, что 32 старших разряда счетчика, возвращаемых командой rpcc, системно зависимы. Это позволяет учесть "чистое" время выполнения того или иного фрагмента программы, когда подсчет процессорных циклов осуществляется лишь после инициализации процесса, который вызывает функцию virtcc (в отличие от функции realcc):

static inline unsigned int virtcc (void) {

u_long cc;

asm volatile ("rpcc %0":"= r"(cc)::"memory");

return (cc+(cc<<32))>>32; /* увеличить содержимое счетчика

после возобновления процесса */

}

Заметим, что некоторые операционные системы поддерживают работу с процессорными средствами измерений с помощью специальных программ. Так, в Digital UNIX доступ к различным измерительным счетчикам в процессорах Alpha может быть осуществлен на основе обращений к профилирующим программам uprofile и kprofile.

Итак, общая идея прямых измерений заключается в том, чтобы выделить в программе интересующие пользователя фрагменты; определить для них точки входа и выхода; обращаясь к соответствующим счетчикам в этих точках, получить требуемые динамические характеристики программы. Однако практическая реализация этой идеи требует преодоления следующих трудностей. Во-первых, фрагментация и соответствующая модификация кода программы не должны нарушать ее логической структуры. Во-вторых, основные источники погрешности прямых измерений – побочные эффекты, обусловленные следующими факторами. Это – особенности конкретной операционной системы, в частности, многозадачность, характерная для UNIX и LINUX, а также влияние архитектурных решений процессоров. Смысл, вкладываемый в термин "многозадачность", будет пояснен чуть позже, в п. 4.3 данного раздела. Например, разброс оценок времени выполнения одной и той же программы в различных прогонах на одинаковых исходных данных может быть вызван такими механизмами, как динамическое предсказание переходов или загрузка кэш-памяти команд. Необходимо заметить, что имеющиеся в операционных системах средства измерения, подобные утилите gettimeofday( ) в UNIX, обладают довольно низкой разрешающей способностью, неприемлемой в ряде приложений. Например, упомянутая утилита для процессора Alpha 21164A с частотой 500 МГц обеспечивает разрешение всего 1 мс, что соответствует 500 000 процессорных циклов. Кроме того, обращение к gettimeofday( ) предполагает медленный системный вызов, который может приводить к проблемам с памятью, в частности, могут иметь место многочисленные промахи при обращении к кэш-памяти, когда пользовательская программа возобновляет работу.

Основные этапы методики прямых измерений сложности для программ на языке высокого уровня включают в себя:

– фрагментацию кода по специальным правилам;

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

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

Далее в этом подразделе мы рассмотрим первый и второй этапы методики. Третьему этапу посвящен следующий подраздел данного раздела.

Фрагментация исходного кода программы. Рассмотрим основные правила фрагментации текста на языке С++. Коды, соответствующие началу и окончанию фрагмента, будем обозначать как <старт> и <стоп>. Простейший случай фрагментации – разбиение всей программы на линейные участки. Модификация текста, заключающаяся в расстановке контрольных точек <старт>, <стоп>, при этом не нарушает логики работы программы. В действительности же часто заголовки циклов и операторов выбора относятся к одним фрагментам, а последующие блоки – к другим. Тривиальная расстановка точек начала и окончания приведет в этом случае к нарушению логической структуры программы, например:

<стартf1> /* начало фрагмента f1 */

i++;

fscanf(f,"%c",&ar[i]);in++;

while(ar[i]!=' ')

{

<стопf1> /* окончание фрагмента f1 */

<стартf2> /* начало фрагмента f2 */

ina[ink][2]=in-1;

ink++;

i++;

fscanf)f,"%c",&ar[i];

<стопf2> /* окончание фрагмента f2 */

}

ar[i]='\0';

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

Правило 1. Фрагмент должен начинаться и заканчиваться на одном и том же структурном уровне:

if ((strcmp(ar,"unsigned short")==0)||(strcmp(ar,"signed short")==0))

{

<старт>

ar[i]=' ';

i++;

fscanf(f,"%c",&ar[i]);

flag=1;

<стоп1> /* допустимая точка окончания фрагмента */

}

ch=ar[i];

ar[i]='\0'

<стоп2> /* неверно! Если условие перехода ложно,

то начало фрагмента не выполнится,

а окончание выполнится */

Правило 2. Фрагменты не должны перекрываться. Исключения составляют особые случаи, например, оценка заголовков циклов (см. далее Случай 2).

Правило 3. Каждый новый структурный уровень должен быть заключен в конфигураторные скобки {}, даже если он содержит лишь один оператор:

if(name[j]=='=')

{

<старт>

fscanf(f,"%c",&ar[i]);

<стоп>

}

Ясно, что без конфигураторных скобок функция fscanf выпадает из области действия оператора выбора.

Правило 4. Каждый новый структурный уровень блоков необходимо начинать с новой строки.

Рассмотрим четыре особых случая фрагментации и оценки сложности.

Случай 1. Если фрагмент оканчивается заголовком оператора выбора if, то следующая строка кода не является однозначно определяемым выходом фрагмента.

Тогда необходимо поставить две точки выхода: первую – непосредственно после if в случае истинности условия выбора, вторую – на альтернативной ветви:

<старт1>

if(Num == (OPR - 2))

{

<стоп1> /* первая точка выхода */

TAB[Num][3][i] = min(cf1, cf2);

TAB[Num][3][i] = OptValue ((OPR-1), TAB[Num][1][i]);

TAB[Num][4][i] = TAB[Num][3][i] + TAB[Num][2][i];

}

<стоп2> /* вторая точка выхода */

или

<старт1>

if(Num == (OPR - 2))

{

<стоп1> /* первая точка выхода */

TAB[Num][3][i] = min(cf1, cf2);

TAB[Num][3][i] = OptValue ((OPR-1), TAB[Num][1][i]);

TAB[Num][4][i] = TAB[Num][3][i] + TAB[Num][2][i];

}

else

{

<стоп2> /* вторая точка выхода */

TAB[Num][3][i] = table (TAB, TAB[Num][1][i], (Num+1), a);

TAB[Num][4][i] = TAB[Num][3][i] + TAB[Num][2][i];

}

Случай 2. Если фрагмент содержит заголовок цикла for, while, то нельзя ставить точку окончания фрагмента сразу после объявления цикла, поскольку количество выходов из фрагмента превысит количество входов.

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

<старт f1> /* начало фрагмента f1 */

i++;

fscanf(f,"%c",&ar[i]);in++;

while(ar[i]!=' ') /* заголовок цикла */

{

<старт f2> /* начало тела цикла */

ina[ink][2]=in-1;

ink++;

i++;

<стоп f2> /* окончание фрагмента f2 */

<старт f3> /* начало фрагмента f3 */

fscanf(f,"%c",&ar[i]);

<стоп f3> /* окончание тела цикла */

}

<стоп f1> /* окончание фрагмента f1 */

ar[i]='\0';

Истинная сложность фрагмента f1 при этом составляет

где S(f1) – суммарная сложность фрагмента f1 и цикла; , – значения сложности фрагментов f2 и f3, составляющих тело цикла в -й итерации; – число итераций.

Случай 3. Если во фрагменте есть операторы break, continue, goto, return, то резко изменяется трасса выполнения программы.

Пусть фрагмент содержит оператор return. Тогда фрагментация выполняется следующим образом. Если начало фрагмента лежит вне тела функции, то выполнение return не приведет к выходу за пределы фрагмента. В противном случае, если фрагмент начинается внутри тела функции, он не может закончиться вне ее (на более высоком структурном уровне). Поэтому перед return ставится точка окончания текущего фрагмента. Рассмотрим примеры.

Начало фрагмента вне тела функции: <старт> . . . table (MT[1],MT[0][1][i]. a); . . . <стоп> . . . float table (MYTABLE far &TAB, float z, float M3 { TAB[0][1]=z-M3; TAB[1][1]=M3; if (MT[0][1][i]<(z+M3)) { return (TAB[1][1]); } else { return (TAB[0][1]); } }

Начало фрагмента внутри тела функции: float table (MYTABLE far &TAB, float z, float M3 { <старт> TAB[0][1]=z-M3; TAB[1][1]=M3; if (MT[0][1][i]<(z+M3)) { <стоп1> return (TAB[1][1]); } else { <стоп2> return (TAB[0][1]); } }

Оператор break прекращает выполнение цикла for, while. Возможны следующие варианты фрагментации. Один вариант – выполнение цикла осуществляется в рамках текущего фрагмента:

<старт>

fprintf (res,"First Граф \n");

for (int j=0;j<NV;j++) /* заголовок цикла */

{

fprintf (res,"%d",tree_new[i][j]);

if (tree_new[i][j] ==0)

{

break;

}

fprintf (res,"\n");

}

<стоп>

Второй вариант – происходит переход к другому фрагменту. В этом случае заголовок и тело цикла принадлежат разным фрагментам и выход из текущего фрагмента ведет к началу нового фрагмента:

<старт f1>

fprintf (res,"First Граф \n");

for (int j=0;j<NV;j++) /* заголовок цикла */

{

<старт f2> /* начало тела цикла */

fprintf (res,"%d",tree_new[i][j]);

if (tree_new[i][j] ==0)

{

<стоп f2>

break;

}

fprintf (res,"\n");

<стоп f2>

}

<стоп f1>

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

Случай без выхода из фрагмента: <старт> fprintf (res,"First Граф \n"); for (int j=0;j<NV;j++) { fprintf (res,"%d",tree_new[i][j]); if (tree_new[i][j] ==0) { continue; } fprintf (res,"\n"); } <стоп>

Случай с выходом из фрагмента: <старт f1> fprintf (res,"First Граф \n"); for (int j=0;j<NV;j++) { <старт f2> fprintf (res,"%d",tree_new[i][j]); if (tree_new[i][j] ==0) { <стоп f2> continue; } fprintf (res,"\n"); <стоп f2> } <стоп f1>

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

Нет выхода за пределы текущего фрагмента: <старт> for (i=0;i<k;i++) { Dsk = scal (D, n[i]); Wsk = scal (w[i], n[i]); t = -Wsk/Dsk; tv = min(t,tv); if (t>1) { goto l4; } } . . . l4: R1.Init(-10000,-10000); <стоп>

Выход за пределы текущего фрагмента: <старт f1> for (i=0;i<k;i++) { <старт f2> Dsk = scal (D, n[i]); Wsk = scal (w[i], n[i]); t = -Wsk/Dsk; tv = min(t,tv); if (t>1) { <стоп f2> goto l4; } <стоп f2> } <стоп f1> <старт f3> /* начало фрагмента, содержащего метку l4 */ . . . l4: <старт f3> R1.Init(-10000,-10000);

Случай 4. Если фрагмент включает часть конструкции switch-case, то необходимо особо оговорить допустимую расстановку границ фрагментов. Кроме того, как и в случае с циклами, заголовок switch может быть включен в один фрагмент, а альтернативы case – в другие.

Рассмотрим примеры.

Вся конструкция включена в один фрагмент: <старт f1> switch (TYP){ case 0: { bi_one (tree_old,n); break; } case 1: { bi_two (tree_old,n); break; } case 2: { bi_three (tree_old,n); break; } default: { printf("Wrong TYP!"); break; } } <стоп f1>

Заголовок и альтернативы принадлежат разным фрагментам: <старт f1> switch (TYP){ <стоп f1> /* недопустимая точка окончания */ case 0: { <старт f2> bi_one (tree_old,n); break; <стоп f2> } case 1: { <старт f3> bi_two (tree_old,n); break; <стоп f3> } case 2: { <старт f4> bi_three (tree_old,n); break; <стоп f4> } default: { <старт f5> printf("Wrong TYP!"); break; <стоп f5> } }

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

Здесь допускается перекрытие фрагментов:

<старт f1>

switch (TYP) {

case 0:

{

<старт f2>

bi_one (tree_old,n); break;

<стоп f2>

}

case 1:

{

<старт f3>

bi_two (tree_old,n); break;

<стоп f3>

}

case 2:

{

<старт f4>

bi_three (tree_old,n); break;

<стоп f4>

}

default:

{

<старт f5>

printf("Wrong TYP!"); break;

<стоп f5>

}

<стоп f1> /* допустимая точка окончания */

Каждой альтернативе должен соответствовать свой фрагмент. Нельзя объединить несколько альтернатив в одном фрагменте, поскольку в соответствии с синтаксисом языка С++ точки начала и окончания фрагмента просто не будут выполнены:

switch (TYP) {

<старт f2>

case 0:

{

bi_one (tree_old,n); break;

}

case 1:

{

bi_two (tree_old,n); break;

}

<стоп f2>

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

Эксперименты с фрагментированной программой. После фрагментации реализуется эксперимент – серия прогонов программы на одних и тех же исходных данных. Под прогоном понимается однократное выполнение программы. Для каждого фрагмента вводится переменная-счетчик, в которой накапливается суммарная сложность в процессорных циклах. Сложность однократного исполнения определяется как разность моментов окончания и начала выполнения фрагмента. Для этого в экспериментах на Pentium-совместимых процессорах осуществляется обращение к 64-разрядному счетчику TSC в контрольных точках каждого из выделенных фрагментов. Как уже говорилось, в процессорах семейства Alpha имеется аналог счетчика TSC и соответствующая команда доступа к нему rpcc. Для чтения содержимого счетчика TSC в средах IA-32 и Itanium используется специальная команда RDTSC – Read Time-Stamp Counter, имеющая код OF 31. Аналогичный счетчик имеется и в процессорах SPARC. Кроме этого, в операционную систему Solaris, начиная с версии 2.4, введена функция высокоточного измерения времени gethrtime ( ), ориентированная на архитектуру SPARC. Эта функция, подобная команде RDTSC для процессора Pentium, возвращает абсолютное значение времени и использует "быстрый" системный вызов. Содержимое счетчика TSC накапливается в 64-разрядном модельном специализированном регистре MSR (model specific register). Старшие 32 разряда регистра MSR загружаются в регистр EDX, а младшие 32 разряда – в регистр EAX. Процессор инкрементирует содержимое регистра MSR в каждом цикле и обнуляет его при перезагрузке. Использование 64 разрядов позволяет измерять сложность довольно больших фрагментов программ: так, переполнение счетчика в процессоре Itanium на частоте 800 МГц может наступить лишь через 6 405 119 часов. Важно, что команда RDTSC доступна программам с пользовательским приоритетом. В среде IA-32 действие этой команды ограничивается флагом TSD (time stamp disable), устанавливаемым в регистре CR4. Если флаг TSD не установлен, то инструкция RDTSC может выполняться на любом уровне привилегий. В случае его установки, для обращения к TSC необходим привилегированный уровень (CPL=0). В среде Itanium ограничения на использование команды RDTSC определяются флагами PSR.si и CR4.TSD в регистрах PSR и CR4 соответственно. Когда эти флаги сброшены, то доступ к счетчику может быть осуществлен на любом уровне привилегий. Когда же один из них либо оба установлены, то необходим уровень операционной системы. Подобно инструкции RDPMC, команда обращения к счетчику TSC не линеаризует анализируемый код. Нет необходимости ожидать, пока будут выполнены все инструкции, предшествующие чтению содержимого счетчика. Также не нужно требовать, чтобы все инструкции, следующие за командой RDTSC, выполнялись после завершения обращения к счетчику. Команда, о которой идет речь, впервые была введена в процессоры Pentium. В защищенном режиме исключение #GP(0) вызывается лишь тогда, когда установлен флаг TSD и уровень привилегий CPL больше 0. В режиме реальной адресации и виртуальном режиме наступает исключение #GP и #GP(0), соответственно, всегда, когда в регистре CR4 установлен флаг TSD. В среде Itanium происходит исключение #GP(0) в случае, когда установлены флаги PSR.si или CR4.TSD, а уровень привилегий больше 0.

На псевдокоде выполнение команды RDTSC может быть записано так:

IF (IA-32 System Environment) /* среда IA-32 */

IF (CR4.TSD=0) OR ((CR4.TSD=1) AND (CPL=0))

THEN

EDX:EAXTimeStampCounter; /* загрузка содержимого

TSC */

ELSE (*CR4 is 1 and CPL is 1, 2, or 3*)

#GP(0) /* исключение */

FI;

ELSE (Itanium System Environment) /* среда Itanium */

SECURED=PSR.si || CR4.TSD;

IF (!SECURED) OR (SECURED AND (CPL=0))

THEN

EDX:EAXTimeStampCounter; /* загрузка содержимого

TSC */

ELSE (*CR4 is 1 and CPL is 1, 2, or 3*)

#GP(0) /* исключение */

FI;

Заметим, что содержимое счетчика TSC может считываться и с помощью команды RDMSR (Read from Model Specific Register). Она имеет код OF 32 и загружает содержимое регистра MSR, адрес которого хранится в регистре ECX, в регистры общего назначения EDX:EAX. Если не все 64 разряда в регистре MSR задействованы под счетчик, то содержимое соответствующих разрядов в EDX:EAX никак не определяется. Инструкция RDMSR должна выполняться только операционной системой (CPL=0) либо в режиме реальной адресации (в виртуальном режиме эта команда не распознается). В противном случае всегда генерируется исключение #GP(0) в защищенном режиме либо #GP – в режиме реальной адресации. Указание на зарезервированный либо незадействованный регистр MSR всегда вызывает исключение общей защиты. Команда RDMSR была введена в семейство процессоров Pentium. Попытка ее использования в более ранних моделях процессоров вызывает исключение #UD (Undefined Opcode) – неправильный, недостоверный код. Рассматриваемая команда выполняется и в среде Itanium:

IF Itanium System Environment THEN IA-32_Intercept (INST,RDMSR);

EDX:EAXMSR[ECX];

Теперь рассмотрим, как использовать команду чтения счетчика RDTSC для динамического исследования программы на языке высокого уровня.

Обращение к счетчику TSC в операционной системе LINUX осуществляется следующим образом:

_asm _volatile (".byte OxOf, Ox31":="A"(<имя переменной>));

Необходимо также внести изменения в исходный код программы. Точка начала фрагмента обозначается кодом вида:

unsigned long longf9;

__asm__volatile (".byte 0x0f, 0x31" : "=A" (f9));

Здесь f9 – имя фрагмента.

В точке окончания фрагмента вставляется код

unsigned long longf9end;

__asm__volatile (".byte 0x0f, 0x31" : "=A"(f9end));

printf("\n00000000 f9: %d\n",f9end-f9);

Здесь 00000000 – последовательность символов, отделяющая результаты прямых измерений от другой информации.

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

Побочные эффекты в экспериментальных исследованиях программ

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

Далее мы сосредоточим внимание на программах, выполняемых в операционной системе LINUX на Pentium-совместимых процессорах. Однако, для того чтобы проиллюстрировать общность проблемы побочных эффектов, еще раз обратимся к примеру, где исследуется динамика программ для процессоров Alpha, исполняемых в среде LINUX. С помощью функций realcc( ) и virtcc( ) можно подсчитать число циклов процессора, затрачиваемых на прогон исследуемых участков программы. Так, программа на языке С, которая позволяет подсчитать число циклов при 10 вызовах функции вычисления квадратного корня sqrt (2.0), выглядит следующим образом:

void measure_sqrt (void){

u_int start, stop, time[10]; int i; double x =2.0;

for (i=0; i<10; ++i) {

start=realcc();sqrt (x); stop=realcc();

time[i]=stop - start;

}

for (i=0; i<10; ++i) printf("%u", time[i]); printf("\n");

}

Заметим, что вывод результатов (printf) осуществляется в отдельном цикле, поскольку требует системных вызовов. Если бы функция printf была включена в основной цикл, то результаты эксперимента были бы менее достоверными из-за влияния ОС.

При выполнении этой программы на процессоре Alpha 21164 число циклов, затрачиваемое на каждый из 10 вызовов функции sqrt(2.0), соответственно равно:

1 2 3 4 5 6 7 8 9 10 (вызовы);

120 101 101 101 101 101 101 101 101 101 (число циклов).

Из этих данных видно, что первый вызов выполняется медленнее, чем остальные девять. Очевидно, это обусловлено тем, что перед первым вызовом кэш-память команд первого уровня еще не загружена (эффект "холодного" кэша). Функция же sqrt( ) достаточно компактна, чтобы разместиться в кэше первого уровня процессора Alpha 21164. Поэтому все последующие вызовы этой функции требуют одинакового количества циклов. Есть еще одна особенность в этом характерном примере – использование функции realcc(), а не virtcc( ) (напомним, последняя возвращает "чистое" время прогона). Функция realcc( ) позволяет выявить такой побочный эффект, как влияние переключения контекстов. Здесь важно различать системные вызовы, обусловленные самой исследуемой программой (как было бы в случае, если бы функция вызова printf находилась в основном цикле) и обращения к операционной системе, никак не связанные с выполнением приложения.

Примером такого побочного влияния на результаты измерений и является переключение контекстов, значительно замедляющее исполнение прикладной программы. Попытаемся разобраться, в чем тут дело. В современных RISC-процессорах, таких как Itanium, семейства Alpha и SPARC, особым образом организовано виртуальное адресное пространство. В контроллере памяти имеется буфер быстрого преобразования адреса TLB (translation lookaside buffer). По сути своей это – таблица, отображающая адреса виртуальных страниц в адреса физических страниц. Число виртуальных страниц огромно. Поэтому TLB содержит адреса последних используемых виртуальных страниц. Когда процесс вызывает контекст, то виртуальный адрес в этом контексте, обозначенном некоторым кодом, передается в контроллер памяти. Там происходит сравнение адреса виртуальной страницы со всеми элементами буфера TLB для данного контекста. При совпадении формируется адрес физической страницы. В противном случае имеет место промах в TLB, который вызывает срабатывание ловушки (trap) в операционной системе. При этом вызывается специальная процедура – обработчик системных прерываний. Выполнение приложения, разумеется, приостанавливается до окончания обработки ловушки. Таким образом, переключение контекста может быть вызвано срабатыванием ловушек в операционной системе. Другое происхождение этого явления, не связанное с конкретными архитектурными особенностями RISC-процессоров, это – прерывания. В отличие от срабатывания ловушек, прерывания вызываются косвенно, асинхронно по отношению к выполняемой программе. Обычно прерывания связаны с процессами ввода/вывода.

Примеры исследования сложности программ. Итак, в основном нас будут интересовать побочные эффекты измерения сложности фрагментов программ, обусловленные особенностями архитектуры процессоров и операционной системы. Для анализа влияния на погрешность оценки сложности операционной системы LINUX мы проведем сравнительный анализ экспериментальных результатов, полученных и в MS DOS. Нужно заметить, что в общем случае необходима серия экспериментов с различными исходными данными, если время выполнения программы зависит от их вида.

Рассмотрим результаты измерения сложности четырех фрагментов теста Linpack при числе линейных уравнений, равном 100. Чтобы исключить влияние исходных данных, коэффициенты системы линейных уравнений во всех прогонах эксперимента берутся одинаковыми. Первый фрагмент (f1) представляет собой вычисление коэффициентов, второй (f2) – вычисление множителей для метода последовательных исключений Гаусса, которым решается система уравнений, третий (f3) и четвертый (f4) фрагменты соответствуют процедуре решения системы уравнений. В табл. 4.1 показаны результаты эксперимента из пяти прогонов в ОС LINUX на участке трассы программы из 25 шагов на платформе Pentium MMX с частотой 200 МГЦ, оперативная память (DIMM) 128 Мбайт, частота системной шины 83 МГц. Здесь MMX означает расширение системы команд для мультимедиа-задач (multimedia extensions), а DIMM – модуль памяти с двухсторонними выводами (dual inline memory module). Под шагом понимается однократное исполнение фрагмента.

Табл. 4.1

Сложность фрагментов теста Linpack на участке трассы в разных прогонах

Шаг	Фрагмент	Прогон
		1	2	3	4	5
i	f1	260 181	259 801	260 434	12 758 362	259 826
i+1	f2	1 876 015	1 882 509	1 876 037	1 882 268	1 876 038
i+2	f1	260 536	259 714	259 908	260 241	260 025
i+3	f2	1 881 737	1 881 833	1 875 827	1 875 925	1 881 306
i+4	f1	259 779	259 829	259 725	259 725	259 794
i+5	f2	1 875 908	1 876 112	26 923 693	1 882 379	1 876 070
i+6	f1	259 706	273 009	261 092	259 872	259 713
i+7	f2	1 881 765	1 876 049	1 893 307	1 881 607	1 881 835
i+8	f1	259 764	259 710	259 959	259 781	259 755
i+9	f2	1 883 881	1 905 222	1 884 391	1 875 923	1 875 860
i+10	f1	260 107	260 403	259 810	259 710	266 053
i+11	f2	1 875 903	1 875 895	1 875 792	26 923 693	1 876 064
i+12	f1	259 707	268 264	259 706	261 287	259 697
i+13	f2	1 882 161	1 876 529	1 881 698	1 893 474	1 881 350
i+14	f1	259 877	259 704	259 724	259 885	259 784
i+15	f2	1 875 752	1 881 517	1 881 342	1 907 391	1 875 762
i+16	f1	272 672	259 764	259 764	260 396	259 704
i+17	f2	1 876 829	1 888 189	1 875 771	1 875 942	1 881 587
i+18	f1	12 758 362	259 716	259 746	270 871	259 810
i+19	f2	1 881 983	1 885 407	1 876 831	1 884 537	1 888 576
i+20	f3	6 775	6 788	7 249	6 870	6 539
i+21	f4	5 951	5 889	7 791	6 000	5 849
i+22	f3	6 233	6 286	6 233	6 301	6 233
i+23	f4	5 603	5 603	5 603	5 603	5 603
i+24	f3	6 248	6 248	6 248	6 248	6 248

Как видно из результатов одного и того же прогона, имеют место разбросы сложности двух типов. Разбросы первого типа – это увеличение сложности на 0,3-39% относительно минимального значения. Другой тип – это приращения порядка 10⁷ процессорных циклов, причем эти "выбросы" наблюдаются на различных шагах прогона фрагмента при одних и тех же исходных данных: в табл. 4.1 – это шаги i+18, i+5 и i, i+11 в прогонах 1, 3 и 4 соответственно. Причина заключается в переключении контекстов операционной системы на другие, в данном случае, внутренние задачи, никак не связанные с исследуемой программой. В частности, это может быть обработка аппаратного прерывания таймера. Разбросы первого типа также носят случайный характер и, очевидно, обусловлены влиянием архитектуры процессора: использованием кэш-регистров, конвейеризацией и сцепкой команд, а в целом – высоким уровнем внутреннего параллелизма процессора.

Итак, "выбросы" сложности объясняются многозадачной природой ОС LINUX. Здесь необходимо сделать несколько пояснений. Термин "многозадачность" нами используется для обозначения целого комплекса понятий, характерных для таких сложно организованных операционных систем, как UNIX, LINUX, Windows NT. Прежде всего, это – виртуальная память, виртуальные команды ввода/вывода и средства параллельной обработки. На одном процессоре путем разделения времени может моделироваться несколько процессов, системы поддерживают несколько потоков управления (threads) в пределах одного процесса. Подобная сложная организация ОС не может не проявляться в виде некоторых побочных эффектов, подобных рассматриваемым в этом подразделе, даже если процессор занят выполнением одной единственной программы! Чтобы убедиться в этом, сравним результаты эксперимента для одного и того же фрагмента f2 текста Linpack на вышеупомянутом процессоре Pentium, а также на платформе Celeron с частотой 333 МГЦ, оперативная память 128 Мбайт (DIMM), частота системной шины 66 МГц, в разных операционных системах (рис. 4.7) – LINUX (рис. 4.7, а, в) и MS DOS (рис. 4.7, б, г). Из-за ограничений на размер памяти в MS DOS число линейных уравнений в тесте Linpack было сокращено со 100 до 40. MS DOS не позволяет непосредственно обращаться к регистрам общего назначения ЕАХ и EDX. Поэтому нужно изменить коды начала и окончания фрагментов, следующим образом.

Код начала фрагмента:

asm { db 0x0f; db 0x31; } /* загрузка содержимого TSC в

регистры EAX:EDX */

asm mov f1,DX; /* чтение младших 16 разрядов EDX */

asm { db 0x66; db 0xc1; db 0xea; db 0x10; } /* сдвиг

содержимого регистра ЕDX вправо на 16 разрядов */

asm mov f2,DX; /* чтение старших 16 разрядов EDX */

asm mov f3,АX; /* чтение младших 16 разрядов EАX */

asm { db 0x66; db 0xc1; db 0xe8; db 0x10; } /* сдвиг

содержимого регистра ЕАX вправо на 16 разрядов */

asm mov f4,АX; /* чтение старших 16 разрядов EАX */

Соответствующие изменения по аналогии вносятся и в код окончания фрагмента:

asm { db 0x0f; db 0x31; }

asm mov f11,DX;

asm { db 0x66; db 0xc1; db 0xea; db 0x10; }

asm mov f2,DX;

asm mov f3,АX;

asm { db 0x66; db 0xc1; db 0xe8; db 0x10; }

asm mov f4,АX;

f5=f3+f4*pow(2,16)+f1*pow(2,32)+f2*pow(2,48);

f5end=f13+f14*pow(2,16)+f11*pow(2,32)+f12*pow(2,48);

printf("\n 00000000 f5 : %10.0f\n",f5end-f5);

а) б)

в) г)

Рис. 4.7. Результаты экспериментов в различных ОС

на процессоре Pentium (а, б) и Celeron (в, г)

Разброс среднего по прогонам значения суммарной сложности в MS DOS практически отсутствует, что подтверждает гипотезу происхождения "выбросов", вызванных многозадачностью LINUX.

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

Относительная погрешность измерения сложности фрагмента в одном прогоне не превышает величины

В свою очередь,

Относительная погрешность эксперимента по измерению сложности любого фрагмента не превышает максимального из значений по всем прогонам. Так, для эксперимента, результаты которого приведены в табл. 4.1, ее значения не больше 0,5% для фрагмента f1 и 0,2% – для f2.

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

На рис. 4.8 показаны результаты экспериментов в ОС LINUX на процессоре Pentium для четырех выделенных фрагментов теста Linpack. Приведены значения непосредственно измеряемой сложности и результаты ее обработки с учетом "выбросов".

Как правило, практически приемлемая оценка сложности получается уже после трех прогонов, поскольку вероятность "выброса" сложности фрагмента на одном и том же шаге в разных прогонах ничтожно мала (см. табл. 4.1 и рис. 4.8).

Так, при однократном выполнении фрагмента, если , , , то . Как уже отмечалось, если сложность зависит от исходных данных, то необходима серия экспериментов с различными их значениями.

Выводы. Таким образом, методика прямых измерений времени выполнения программ не требует детального моделирования аппаратуры и ориентирована на доступность процессорных узлов, из которых строится целевая вычислительная платформа. Выше рассмотрены правила фрагментации исходного текста на языке высокого уровня, не нарушающие структуры программы. Реализация методики измерений рассчитана на архитектурные решения современных RISC-процессоров, а также процессоров, имеющих черты VLIW-компьютеров, например, Itanium. Побочные эффекты измерений заключаются во влиянии операционной системы и аппаратуры. Выше рассмотрен подход для динамического анализа программ и обработки его результатов с учетом побочных эффектов.

Усредненная суммарная сложность f1 Усредненная суммарная сложность f2

Число прогонов Число прогонов

а) б)

Усредненная суммарная сложность f3 Усредненная суммарная сложность f4

Число прогонов Число прогонов

в) г)

Рис. 4.8. Результаты экспериментов на четырех фрагментах

теста Linpack в OC LINUX

Дата добавления: 2021-06-02; просмотров: 65; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!