Borland Assembler (BASM) уроки для начинающих (урок 7 часть 1)

Урок 7

Добро пожаловать на урок номер 7. Темой сегодняшнего урока является плавающая запятая в BASM. Это уже было темой в более раннем уроке, но этот урок даст дополнительную информацию. Мы посмотрим, как кодировать скаляры на SSE2 и как инструкции обслуживаются в конвейерах FP. Сегодняшний пример это расчет полинома третьего порядка.

Вместо анализа и оптимизации этой функции мы посмотрим, как реально мы можем ее использовать. Полином третьего порядка может аппроксимировать функцию в ее интервале, [-1;1], с максимальной абсолютной ошибкой 0.086. Это не очень высокая точность, но то что мы разработаем в данном уроке можно будет расширить до более высоких порядков, в той же манере для получения большей точности.

Параметры A, B, C и D определяют форму кривой для функции и значения для аппроксимации в ArcSin с минимальной ошибкой. Для этой цели мы разработаем оптимизатор, который будет использоваться для измерения производительности. Поскольку ARCSIN(0) = 0 мы непосредственно видим, что D=0 и D можно вывести из оптимизации. Мы также знаем, что ArcSin это нечетная функция и поэтому выражение второго порядка B*X*X не используется в аппроксимации. Это поскольку выражение второго порядка  четное и симметрично относительно оси Y. Функции нечетных порядков имеют анти симметрию вокруг оси Y с F(X) = -F(-X). Все это означает, что наша функция может быть уменьшена до

Result := A*X*X*X + C*X;

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

В функции номер 1a имеется 6 умножений и три сложения. Напишем ее в виде формы Хорнера (Horner form). 

Result := ((A*X + B)*X + C)*X + D;

Уменьшив этим до трех умножений и сложений.

Другая форма такая

Result := (A*X + B)*(X*X)+(C*X + D);

Здесь четыре умножения и три сложения.

На современных процессорах очень важно распараллеливания можно извлечь из формулы и как много умножений и сложений она имеет. Современные процессоры, такие как AMD Athlon, Intel P4 и P3 имеют конвейеры. Конвейеры необходимы на процессорах, работающих на высокой частоте, поскольку основные операции сложения, вычитания, умножения или деления не могут быть выполнены за один такт частоты. На P4 есть конвейер называемый FP_ADD, который предназначен для операций сложения и вычитания. Этот конвейер имеет 5 состояний, это означает, что процесс сложения или вычитания может быть разбит на 5 подзадач. Следовательно, сложение и вычитание выполняются за 5 тактов. Преимущество конвейера состоит в том, что хотя операция требует 5 тактов, но зато каждая новая операция может начинаться в каждом такте. Это потому что первое сложение покидает первую подзадачу при втором такте и эта подзадача может начинать сложение для второго числа. Если мы имеем серию сложений, то первое сложение покидает конвейер на такте 5, второе на такте 6 и так далее. Производительность Throughput получается всего в один такт. Параллельность составляет до 5 сложений или вычитаний в конвейере одновременно. Проблема в том, что если второе или следующие сложения связаны с первым сложением, то придется ожидать, когда закончится первое сложение. Мы можем сказать, что здесь есть зависимость данных между двумя инструкциями, и мы видим, что полная латентность для сложения составляет 2 раза по 5 тактов.

Посмотрим на основе нашей функции работу конвейера.

Result := A*X*X*X + B*X*X + C*X + D;

Также видно, что четвертое выражение может выполняться параллельно, и затем сложено в конце действия. A*X это первая инструкция, готовая для обработки в конвейере F_MUL. Латентность для FMUL на P4 составляет 7 тактов и выражение A*X будет готово через 7 тактов. FMUL имеет максимальную пропускную способность (throughput) в 2 такта. Отсюда ясно, что FMUL не полностью конвейеризирован. Конвейер принимает новую инструкцию на такте три, а не на втором. B*X это вторая инструкция, готовая к выполнению и процессор начнет ее выполнение на такте 3. В такте 5 конвейер снова готов к принятию новой инструкции и это будет инструкция C*X. В такте 7 выполнение инструкции A*X будет закончено и выражение (A*X)*X можно будет начать вычислять в такте 8. В такте 10 вычисление выражения B*X будет закончено и процессор начнет выполнению выражения (B*X)*X. В такте 12 также будет закончено выполнение C*X и конвейер F_ADD прибавит значение D. В такте 15 будет закончено вычисление (A*X)*X и можно будет начинать выражение (A*X*X)*X. В такте 17 выражения (B*X)*X и (C*X) + D будут закончены и можно начать работу с конвейером F_ADD. Данное сложение будет закончено на такте 21, где выражение (A*X*X)*X также будет готово. Последнее сложение можно будет начать на такте 22. Осталась только одна операция в действии, и мы должны подождать до полной латентности FADD, которая составляет 5 тактов. На такте 27 последнее сложение будет закончено и работа будет выполнена.

Данные таблицы покажут это в деталях. Левая колонка символизирует конвейер F_MUL , с 7 состояниями 7, а правая конвейер F_ADD на 5 состояний.

Такт 1

Такт 2

Такт 3

Такт 4

Такт 5

Такт 6

Такт 7

Такт 8

Такт 9

Такт 10

Такт 11

Такт 12

Такт 13

Такт 14

Такт 15

Такт 16

Такт 17

Такт 18

Такт 19

Такт 20

Такт 21

Такт 22

Такт 23

Такт 24

Такт 25

Такт 26

Такт 27

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

После того, как мы посмотрели, как обслуживаются инструкции в конвейерах P4, мы приступим к измерению. Оптимизатор измерения ищет наилучшую возможность для нашего полинома ArcSin. Он базируется на наиболее простом алгоритме оптимизации, это исчерпывающий поиск. Мы просто пробуем множество комбинаций параметров и запоминаем каждый набор параметров, который дает наилучший результат. A и C начинаются в интервалах [AStart; AEnd] и [CStart; CEnd], а размер шага AStepSize и CStepsize. Это делается с помощью двух вложенных циклов.

Функция CalculateMaxAbsError рассчитывает количество точек X на интервале [-1;1], который определяет интервал функции ArcSin .

в каждой точке мы рассчитываем ошибку, вычитая значение Y из нашей функции аппроксимации из ссылки значения Y, полученное из  Delphi RTL функции ArcSin. Ошибка может быть положительной или отрицательной, нас же интересует абсолютное значение. Мы помним, что наибольшее абсолютное значение ошибки получается из двух значений MaxAbsError и AbsError, назначая из MaxAbsError. MaxAbsError инициализируется нулем, и в первом вычисление принимает значение первой ошибки (если она больше нуля). MaxAbsError возвращает результат из функции, после окончания полного цикла. В функции оптимизатора, два значения A и C, которые дают наименьшую максимальную ошибку, запоминаются вместе с действительным значением MinMaxAbsError.

Все, что делается в оптимизаторе это возможность расчета максимально количества комбинаций. По этой причине мы должны оптимизировать оптимизатор ;-), и функцию расчета. В этом уроке наши цели немного отличаются, поскольку все, что мы хотим, это получение правильных измерений для функций, которые мы хотим оптимизировать. Это все равно означает, что код оптимизатора должен занимать как можно меньше тактов, так как используемые в функциях большая часть общего количества использованных тактов. Первая оптимизация оптимизатора, которую мы сделаем, состоит в том, что не надо рассчитывать ссылки функции снова и снова. При возврате, нам не важно, какие значения имели A и C. Сделаем ссылку один раз и запишем значение Yref в массив.

Следующей оптимизации подвержены строки, которые рассчитывают MaxAbsError.

Длинная версия

Yref := ArcSinArray[I];
Error := Yref-Y;
AbsError := Abs(Error);

Короткая версия

AbsError := Abs(ArcSinArray[I]-Y);

Это поможет, поскольку Delphi создает множество лишнего кода, при компиляции FP кода.

Длинная версия компилируется в следующее

Здесь множество излишеств в данном коде и мы должны заключить, что Delphi сделала плохую работу по оптимизации кода с плавающей запятой. Попробую дать несколько разъяснений этого кода. В начале Паскаль назначает одну переменную типа double другой. Делается это с помощью пар инструкций MOV, одна для младших четырех байт переменной, а вторая для старшей части. Первая строка ассемблерного кода загружает адрес массива в регистр EAX, который используется как база для адресации в массиве. В EBX находится I, и он умножается на 8, поскольку элемент массива занимает 8 байт. Смещение на 4 байта, в последней из двух строк (в строке это скрыто!), это смещение до старшей части элемента.

Yref размещен во фрейме стека [EBP-$48] и загружается в первой строке FP кода. Y размещен во фрейме стека [EBP -$30] и он вычитается из Yref инструкцией FSUB. Результат Error и он записывается во фрейме стека [EBP-$50].

Последняя строка Паскаль кода компилируется в четыре строки ассемблерного кода, в котором сначала загружается Error. Сохранение и загрузка Error излишне и оптимизатор должен удалить это. FABS это функция ABS и вероятно одна из наиболее коротких реализации функций ;-). Компилятор Delphi не имеет inline оптимизации, но применяет это, как «компьютерную магию» к небольшому количеству функций, одна из которых ABS. Последняя строка записывает AbsError на стек.

Короткая версия компилируется в следующее

В данной версии нет лишнего кода, и компилятор должен был сделать такой же код и для длинной версии. Все строки кода присутствуют и в длинной версии, но весь лишний код удален. Первая строка загружает базовый адрес массива в EAX. Вторая строка загружает элемент I, который находится в регистре EBX, на верхушку стека FP. Третья строка вычитает Y из Yref. Четвертая строка это функция Abs. Пятая строка записывает результат в переменную AbsError.

Имеются странности с измерения, которые я не могу объяснить. Результаты измерений сильно изменяются при выполнении. Если клавиатура используется, то при нажатии клавиши, мы получаем различные очки, чем при нажатии мышкой! Единственный кто наверно сможет это объяснить, это Нобель Прайз (Nobel Prize) из Delphi ;-)

Другой иррациональной вещью, является то, что Delphi не выравнивает переменные с двойной точностью должным образом. Они должны быть выровнены по границе 8 байт, а Delphi их выравнивает на границу 4 байта. Пенальти, которое мы можем получить, придет из кэш памяти первого уровня, в отличие от кэш памяти второго уровня она не разделена. При загрузке переменной, она может оказаться разделенной между двумя строка кэш памяти, что потребует двойного времени на ее загрузку. Поскольку переменные двойной точности имеют размер в 8 байт, а строка кэш L1 на P4 размером в 64 байта, то одна из восьми переменных может оказаться разнесенной по разным строкам. На P3 ширина кэш L1 составляет 32 байта, и это может произойти для одного из четырех чисел.

Идеально когда переменные длиной в 4 байта выравнивались бы на границу в 4 байта и восьми байтные на границу в восемь байт соответственно. Что бы сделать это понятным представим себе первую строку в кэш памяти первого уровня, куда будут загружены наши переменные. Первая строка начинается по адресу 0, так, что память из адреса 0 будет загружена в нее. Наша первая переменная выровнена и занимает первые 8 байт в строке 1. переменная номер два занимает байты 9-16 ..., переменная номер восемь байты 57-64 и не пересекает границы строки. Если переменная выровнена на границу 4 байт, то первая переменная размещается в строке по байту 4, а восьмая по байту 61. Первые 4 байта ее находятся в строке 1, но следующие 4 байта уже в строке 2. Процессор загружает младшие 4 байта, затем загружает старшие 4 байта, вместо того, чтобы загрузить все это за один раз.

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

Данная функция получила 43243 пункта при измерении на моем P4 1600 MHz (разогнанным до 1920 MHz).

Дельфи от компилировало это так

Код из окна CPU view не откомпилируется, поскольку здесь есть инструкция FADDP ST(1), но мы удалим ST(1). По умолчанию инструкция FADDP оперирует с ST(0), ST(1) и поэтому нет необходимости писать это.

Во-первых, мы видим, что не надо устанавливать фрейм стека. Стек в действительности используется для записи временной переменной для результата и переписывается снов в строках

fstp  qword ptr [ebp-$08]
wait
fld   qword ptr [ebp-$08]

но для этого используется указатель базы, а не указатель стека. Строки, в которых используется EBP + смещение до параметров, которые расположены относительно указателя базы, и который равен фрейму стека вызывающей функции. Указатель стека не используется нигде в функции и изменение его не имеет значение. Инструкция MOV EBP, ESP, добавленная компилятором вместе со строкой ADD ESP, -$08 создает восьмибайтный фрейм. Поскольку эти строки изменяют регистр EBP, то его необходимо сохранить в стеке. В действительности мы можем удалить только строку ADD ESP, 8 и две строки POP ECX, назначение которых вычесть число 8 из ESP.

Данная реализация функции получила 42391 пункта (ранее 43243) и немного улучшила производительность.

Компилятор вставил строку MOV EBP, ESP и мы может уменьшить избыточность, используя Esp вместо EBP.