Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
Замена деления умножением на Ассемблере
Замена деления умножением на Ассемблере

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

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

Сперва рассмотрим оптимизацию беззнакового целочисленного деления. Здесь есть несколько вариантов в зависимости от значений делителя. Первый вариант - если делитель находится в диапазоне от 1 до (231 - 1):
  1. ; В описании используются следующие вспомогательные значения:
  2. ; m = множитель (multiplier)
  3. ; s = коэффициент смещения (shift factor)
  4.  
  5. ;-----------------------------------------------------
  6. ; Алгоритм №0
  7. ;-----------------------------------------------------
  8.         mov     eax, m
  9.         mul     делитель
  10.         shr     edx, s
  11.         ; EDX = частное
  12.  
  13. ;-----------------------------------------------------
  14. ; Алгоритм №1
  15. ;-----------------------------------------------------
  16.         mov     eax, m
  17.         mul     делитель
  18.         add     eax, m
  19.         adc     edx, 0
  20.         shr     edx, s
  21.         ; EDX = частное
Тип алгоритма, множитель и коэффициент смещения вычисляются на основании значения делителя. В мануале для этого приведены исходники программы на C. Он наглядный и удобный для понимания.

Второй вариант беззнакового деления - когда делитель находится в интервале от 231 до (232 - 1). В этом случае частное может принимать только два значения - 0 или 1. Соответственно, оптимизированный алгоритм будет иметь следующий вид:
  1.         ; EAX = делимое
  2.         xor     edx, edx
  3.         cmp     eax, делитель ; CF = (делимое < делитель) ? 1 : 0
  4.         sbb     edx, -1 ; частное = 0+1-CF = (делимое < делитель) ? 0 : 1
  5.         ; EDX = частное
В случае, если значение делимого неважно для дальнейших расчетов, этот вариант можно еще немного оптимизировать, отказавшись от использования дополнительного регистра:
  1.         ; EAX = делимое
  2.         cmp     eax, делитель ; CF = (делимое < делитель) ? 1 : 0
  3.         mov     eax, 0
  4.         sbb     eax, -1 ; частное = 0+1-CF = (делимое < делитель) ? 0 : 1
  5.         ; EAX = частное
В мануале, кстати, в этом месте допущена опечатка. В тексте рассказывается об избавлении от второго регистра, и тут же приводится неработающий код с этим же регистром (страница 117, если интересно). Копипаст не всегда бывает полезным. Там же в мануале рекомендуется использовать вариант с дополнительным регистром, хотя лично я какой-то принципиальной разницы в этом не вижу. Те же яйца, только сбоку.

На всякий случай напомню частные случаи беззнакового целочисленного деления. На ноль натуральные числа делить нельзя, это без вариантов, так что и про оптимизацию тут речи быть не может. При делении на единицу частное всегда равно делимому, это вы тоже должны помнить еще со школьной скамьи. Деление на степень двойки в Ассемблере оптимизируется с использованием команды битового сдвига вправо SHR reg, степень_двойки:
  1.         ; EAX = делимое
  2.         shr     eax,1    ; EAX / 2
  3.         shr     eax,2    ; EAX / 4
  4.         shr     eax,3    ; EAX / 8
  5.         shr     eax,4    ; EAX / 16
  6.         ; и так далее
Под это же правило, в принципе, можно притянуть и деление на единицу, так как 20 = 1.
  1.         ; EAX = делимое
  2.         shr     eax,0    ; EAX / 1
  3.         ; EAX остался неизменным
Целочисленное знаковое деление немного сложнее, так как при получении результата приходится учитывать знак делимого и делителя. Приведенные ниже алгоритмы работают только с положительными значениями делителя. Если делитель отрицательный, то сперва вычисляется его модуль, который и используется в дальнейших расчетах, а к полученному результату деления применяется ассемблерная команда NEG. Это следует из математической аксиомы n/-d = -(n/d). Целочисленный делитель должен находиться в диапазоне от 2 до (231 - 1).
  1. ; В описании используются следующие вспомогательные значения:
  2. ; m = множитель (multiplier)
  3. ; s = коэффициент смещения (shift factor)
  4.  
  5. ;-----------------------------------------------------
  6. ; Алгоритм №0
  7. ;-----------------------------------------------------
  8.         mov     eax, m
  9.         imul    делитель
  10.         mov     eax, делитель
  11.         shr     eax, 31
  12.         sar     edx, s
  13.         add     edx, eax
  14.         ; EDX = частное
  15.  
  16. ;-----------------------------------------------------
  17. ; Алгоритм №1
  18. ;-----------------------------------------------------
  19.         mov     eax, m
  20.         imul    делитель
  21.         mov     eax, делитель
  22.         add     edx, eax
  23.         shr     eax, 31
  24.         shr     eax, s
  25.         add     edx, eax
  26.         ; EDX = частное
Как и в беззнаковом делении, тип алгоритма, множитель и коэффициент смещения вычисляются на основании значения делителя, а точнее его модуля. Исходник на C есть в мануале.

Частные случаи целочисленного знакового деления также отличаются от беззнакового. Вот, например, деление на двойку и степени двойки с разными знаками.
  1. ;-----------------------------------------------------
  2. ; Знаковое деление на 2
  3. ;-----------------------------------------------------
  4.         ; EAX = делимое
  5.         cmp     eax, 800000000h
  6.         sbb     eax, –1
  7.         sar     eax, 1
  8.         ; EAX = частное
  9.  
  10. ;-----------------------------------------------------
  11. ; Знаковое деление на 2^n
  12. ;-----------------------------------------------------
  13.         ; EAX = делимое
  14.         cdq
  15.         and     edx, (2^n–1)
  16.         add     eax, edx
  17.         sar     eax, n
  18.         ; EAX = частное
  19.  
  20. ;-----------------------------------------------------
  21. ; Знаковое деление на -2
  22. ;-----------------------------------------------------
  23.         ; EAX = делимое
  24.         cmp     eax, 800000000h
  25.         sbb     eax, –1
  26.         sar     eax, 1
  27.         neg     eax
  28.         ; EAX = частное
  29.  
  30. ;-----------------------------------------------------
  31. ; Знаковое деление на -(2^n)
  32. ;-----------------------------------------------------
  33.         ; EAX = делимое
  34.         cdq
  35.         and     edx, (2^n–1)
  36.         add     eax, edx
  37.         sar     eax, n
  38.         neg     eax
  39.         ; EAX = частное
Как вы уже поняли, все оптимизации операций деления на заранее известную константу выполняются на стадии написания программы, а не вычисляются динамически в процессе ее работы. Иначе о какой оптимизации может идти речь? Из этого же следует, что использовать такие алгоритмы для часто меняющихся делителей не надо.

AMD Athlon Processor x86 Code Optimization GuideAMD Athlon Processor x86 Code Optimization Guide

AMD.Athlon.Processor.x86.Code.Optimization.Guide.zip (1,047,105 bytes)

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

Torbjorn Granlund - Division by Invariant Integers using MultiplicationTorbjorn Granlund - Division by Invariant Integers using Multiplication

Torbjorn.Granlund.Division.by.Invariant.Integers.using.Multiplication.zip (152,759 bytes)

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

Утилиты для расчета замены деления умножениемУтилиты для расчета замены деления умножением

Division.by.Multiplication.Utilities.zip (20,895 bytes)


Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 10137 | Комментариев: 4

Внимание! Статья опубликована больше года назад, информация могла устареть!

Комментарии

Отзывы посетителей сайта о статье
ManHunter (23.07.2013 в 15:01):
Да, так правильнее. Спасибо.
kw33 (23.07.2013 в 13:18):
На мой взгляд название zip-архива должно быть не "multiplication by division", а "division by multiplication".
sim31 (18.07.2013 в 13:42):
Если девушка на картинке поняла хоть половину написанного на доске она гений, кроме того что... :) Да и автор блога тоже светлая голова, IQ наверное более 150, или таких 1:5000 что тоже самое. Какую статью не взять достаточно интересно )
Zhelezyaka (09.07.2013 в 08:07):
Спасибо, как говорится - мотаем на ус,
и картинка клёвая, да - таких нужно умножать, а не делить )))

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

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2017
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.06 сек. / MySQL: 2 (0.0033 сек.) / Память: 4.5 Mb
Наверх