Blog. Just Blog

Оптимизация умножения на константу на Ассемблере

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
В предыдущей статье по оптимизации мы рассматривали замену команд деления, как это описано в "AMD Athlon Processor x86 Code Optimization Guide". Но в этом же мануале описана оптимизация умножения на константу. Тут нет универсальных алгоритмов, по которым можно было бы однозначно определить нужную последовательность команд замены, как в случае с делением. Для каждой константы набор команд определяется на основании их "весовых коэффициентов" и количества тактов процессора, необходимых для их выполнения. В качестве примера приведена вот такая табличка оптимизации умножения с 2 до 32. Ее всегда можно посмотреть и в самом мануале, но лучше пусть будет под рукой.
  1. ; Умножение на 2
  2. add reg1, reg1          ; 1 такт процессора
  3.  
  4. ; Умножение на 3
  5. lea reg1, [reg1+reg1*2] ; 2 такта процессора
  6.  
  7. ; Умножение на 4
  8. shl reg1, 2             ; 1 такт процессора
  9.  
  10. ; Умножение на 5
  11. lea reg1, [reg1+reg1*4] ; 2 такта процессора
  12.  
  13. ; Умножение на 6
  14. lea reg1, [reg1+reg1*2] ; 3 такта процессора
  15. add reg1, reg1
  16.  
  17. ; Умножение на 7: 
  18. mov reg2, reg1          ; 2 такта процессора
  19. shl reg1, 3
  20. sub reg1, reg2
  21.  
  22. ; Умножение на 8: 
  23. shl reg1, 3             ; 1 такт процессора
  24.  
  25. ; Умножение на 9: 
  26. lea reg1, [reg1+reg1*8] ; 2 такта процессора
  27.  
  28. ; Умножение на 10: 
  29. lea reg1, [reg1+reg1*4] ; 3 такта процессора
  30. add reg1, reg1
  31.  
  32. ; Умножение на 11:
  33. lea reg2, [reg1+reg1*8] ; 3 такта процессора
  34. add reg1, reg1
  35. add reg1, reg2
  36.  
  37. ; Умножение на 12:
  38. lea reg1, [reg1+reg1*2] ; 3 такта процессора
  39. shl reg1, 2
  40.  
  41. ; Умножение на 13:
  42. lea reg2, [reg1+reg1*2] ; 3 такта процессора
  43. shl reg1, 4
  44. sub reg1, reg2
  45.  
  46. ; Умножение на 14:
  47. lea reg2, [reg1+reg1]   ; 3 такта процессора
  48. shl reg1, 4
  49. sub reg1, reg2
  50.  
  51. ; Умножение на 15:
  52. lea reg1, [reg1+reg1*2] ; 4 такта процессора
  53. lea reg1, [reg1+reg1*4]
  54.  
  55. ; Умножение на 16:
  56. shl reg1, 4             ; 1 такт процессора
  57.  
  58. ; Умножение на 17:
  59. mov reg2, reg1          ; 2 такта процессора
  60. shl reg1, 4
  61. add reg1, reg2
  62.  
  63. ; Умножение на 18:
  64. lea reg1, [reg1+reg1*8] ; 3 такта процессора
  65. add reg1, reg1
  66.  
  67. ; Умножение на 19:
  68. lea reg2, [reg1+reg1*2] ; 3 такта процессора
  69. shl reg1, 4
  70. add reg1, reg2
  71.  
  72. ; Умножение на 20:
  73. lea reg1, [reg1+reg1*4] ; 3 такта процессора
  74. shl reg1, 2
  75.  
  76. ; Умножение на 21:
  77. lea reg2, [reg1+reg1*4] ; 3 такта процессора
  78. shl reg1, 4
  79. add reg1, reg2
  80.  
  81. ; Умножение на 22:
  82. lea reg2, [reg1+reg1*4] ; 4 такта процессора
  83. add reg1, reg1
  84. lea reg1, [reg1+reg2*4]
  85.  
  86. ; Умножение на 23:
  87. lea reg2, [reg1+reg1*8] ; 3 такта процессора
  88. shl reg1, 5
  89. sub reg1, reg2
  90.  
  91. ; Умножение на 24:
  92. lea reg1, [reg1+reg1*2] ; 3 такта процессора
  93. shl reg1, 3
  94.  
  95. ; Умножение на 25:
  96. lea reg1, [reg1+reg1*4] ; 4 такта процессора
  97. lea reg1, [reg1+reg1*4]
  98.  
  99. ; Умножение на 26:
  100. lea reg2, [reg1+reg1*2] ; 4 такта процессора
  101. add reg1, reg1
  102. lea reg1, [reg1+reg2*8]
  103.  
  104. ; Умножение на 27:
  105. lea reg1, [reg1+reg1*2] ; 4 такта процессора
  106. lea reg1, [reg1+reg1*8]
  107.  
  108. ; Умножение на 28:
  109. lea reg2, [reg1*4]      ; 3 такта процессора
  110. shl reg1, 5
  111. sub reg1, reg2
  112.  
  113. ; Умножение на 29:
  114. lea reg2, [reg1+reg1*2] ; 3 такта процессора
  115. shl reg1, 5
  116. sub reg1, reg2
  117.  
  118. ; Умножение на 30:
  119. lea reg2, [reg1+reg1]   ; 3 такта процессора
  120. shl reg1, 5
  121. sub reg1, reg2
  122.  
  123. ; Умножение на 31:
  124. mov reg2, reg1          ; 2 такта процессора
  125. shl reg1, 5
  126. sub reg1, reg2
  127.  
  128. ; Умножение на 32:
  129. shl reg1, 5             ; 1 такт процессора
В разделе мануала, посвященном оптимизации целочисленного умножения, упоминается программа "FINDMUL", которая находится на "AMD Documentation CD-ROM". Как написано в мануале, эта программа должна рассчитывать оптимальный алгоритм умножения на константу. К сожалению, ни саму программу, ни этот диск в интернетах мне найти не удалось, поэтому больше ничего про нее сказать не могу. Неизвестны ни алгоритм ее работы, ни диапазон констант, которые она в состоянии оптимизировать. Если кто-то знает где его взять, то, пожалуйста, напишите. Буду очень благодарен.

Но в процессе поисков информации я наткнулся на интересную статью "Integer multiplying by constants" на сайте программиста Paul Hsieh. Там приведена расширенная таблица оптимизированного умножения на константу. Кроме самой таблицы выложены исходники программы "MULTOPP5", которая ищет оптимальный алгоритм умножения. Из-за особенностей работы, максимальное значение константы, которое сможет оптимизировать эта программа, немногим превышает 2000. Я не силен в C, но может быть как-нибудь можно ее модифицировать, чтобы расширить диапазон поиска. Авторский исходник, скомпилированный консольный вариант и листинг результатов ее работы находятся в приложении к статье.

MULTOPP5 by Paul HsiehMULTOPP5 by Paul Hsieh

MULTOPP5.by.Paul.Hsieh.zip (32,999 bytes)

Оптимизация умножения на константу до 16378Оптимизация умножения на константу до 16378

Multiply.By.Constants.up.to.16378.zip (33,400 bytes)


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

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

Комментарии

Отзывы посетителей сайта о статье
ManHunter (14.08.2013 в 11:58):
Добавил, спасибо!
anonym (14.08.2013 в 11:42):
http://www.wasm.ru/forum/viewt...p?pid=366853
есть за что зацепится

из хорошо гуглящегося только файлик
multiply_constants.txt
с который был с утилитой findmul
user (06.08.2013 в 22:47):
Grey,
думаю, если реализовать таким образом
умножение на 22'222'222, уже будет проигрыш.
Ну, а на 2,4,..32 - да, выигрыш будет по-любому.
Вот что я хотел сказать.
Grey (05.08.2013 в 10:15):
В больших матрицах, особенно если они многократно перемножаются, обращаются и т.п. выигрыш полюбому будет.
user (04.08.2013 в 20:36):
Ну - с этой точки зрения да.
Да и просто - красивое решение.
ManHunter (04.08.2013 в 20:33):
user, полностью согласен. Но всегда же может появиться необходимость обратной совместимости, или та же обфускация/метаморфирование с заменой команд. Знаний много не бывает :)
user (04.08.2013 в 20:26):
Позволю себе высказать предположение,
что подобная оптимизация умножения "на любое число"
вряд-ли целесообразна. На старых процессорах это ещё
имело бы смысл (8086 - MUL r16 - до 133 тактов).
Но уже на P5 она же - 11 тактов.
Видимо, главное - это обеспечить нахождение операндов
в регистрах, т.е. применять высокоуровневую оптимизацию,
пренебрежение которой способно многократно снизить выигрыш
от низкоуровневых изощрений...

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

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

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