Замена деления умножением на Ассемблере

При написании на Ассемблере алгоритмов, использующих деление на константу, операции деления можно заменять на операции умножения. Зачем это надо? Дело в том, что процессор выполняет операцию умножения в несколько раз быстрее, чем операцию деления. К примеру, на умножение тратится 5-9 тактов процессора (знаковое умножение) или 4-8 (беззнаковое умножение), тогда как для деления необходимо 22-47 тактов (знаковое деление) или 17-41 тактов (беззнаковое деление). В высокооптимизированных алгоритмах, таких как шифрование, математические расчеты, архивация больших объемов данных, подсчет контрольных сумм и других подобных задачах, экономия каждого такта процессора может дать значительный прирост общей скорости работы программы.

В руководстве по оптимизации "AMD Athlon Processor x86 Code Optimization Guide" вопрос замены деления умножением расписан очень подробно. Рассмотрены частные случаи деления, такие как деление на степень двойки, описан выбор алгоритма для знакового и беззнакового деления и приведен код для вычисления вспомогательных корректирующих значений. Кроме этого, в руководстве описаны методы оптимизации и других математических операций. Даже если вы никогда не будете использовать на практике замену деления умножением, почитать о других способах оптимизации будет очень полезно.

Сперва рассмотрим оптимизацию беззнакового целочисленного деления. Здесь есть несколько вариантов в зависимости от значений делителя. Первый вариант - если делитель находится в диапазоне от 1 до (2³¹ - 1):Тип алгоритма, множитель и коэффициент смещения вычисляются на основании значения делителя. В мануале для этого приведены исходники программы на C. Он наглядный и удобный для понимания.

Второй вариант беззнакового деления - когда делитель находится в интервале от 2³¹ до (2³² - 1). В этом случае частное может принимать только два значения - 0 или 1. Соответственно, оптимизированный алгоритм будет иметь следующий вид:В случае, если значение делимого неважно для дальнейших расчетов, этот вариант можно еще немного оптимизировать, отказавшись от использования дополнительного регистра:В мануале, кстати, в этом месте допущена опечатка. В тексте рассказывается об избавлении от второго регистра, и тут же приводится неработающий код с этим же регистром (страница 117, если интересно). Копипаст не всегда бывает полезным. Там же в мануале рекомендуется использовать вариант с дополнительным регистром, хотя лично я какой-то принципиальной разницы в этом не вижу. Те же яйца, только сбоку.

На всякий случай напомню частные случаи беззнакового целочисленного деления. На ноль натуральные числа делить нельзя, это без вариантов, так что и про оптимизацию тут речи быть не может. При делении на единицу частное всегда равно делимому, это вы тоже должны помнить еще со школьной скамьи. Деление на степень двойки в Ассемблере оптимизируется с использованием команды битового сдвига вправо SHR reg, степень_двойки:Под это же правило, в принципе, можно притянуть и деление на единицу, так как 2⁰ = 1.Целочисленное знаковое деление немного сложнее, так как при получении результата приходится учитывать знак делимого и делителя. Приведенные ниже алгоритмы работают только с положительными значениями делителя. Если делитель отрицательный, то сперва вычисляется его модуль, который и используется в дальнейших расчетах, а к полученному результату деления применяется ассемблерная команда NEG. Это следует из математической аксиомы n/-d = -(n/d). Целочисленный делитель должен находиться в диапазоне от 2 до (2³¹ - 1).Как и в беззнаковом делении, тип алгоритма, множитель и коэффициент смещения вычисляются на основании значения делителя, а точнее его модуля. Исходник на C есть в мануале.

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


В исходниках и мануале упоминается статья Torbjorn Granlund "Division by Invariant Integers using Multiplication", на всякий случай вот ее полный текст (на английском).


В приложении скомпилированные программы из мануала для знакового и беззнакового деления, а также утилиты Magic Divider от The Svin и Muldiv 1.0 от bart^xt.

Комментарии

Добавить комментарий

Для вставки цитаты выделите текст и нажмите сюда

Имя*:

Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.

Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.