Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail 05.08.2013 | Категория: Образ мышления: Assembler | Автор: ManHunter
В предыдущей статье по оптимизации мы рассматривали замену команд деления, как это описано в "AMD Athlon Processor x86 Code Optimization Guide". Но в этом же мануале описана оптимизация умножения на константу. Тут нет универсальных алгоритмов, по которым можно было бы однозначно определить нужную последовательность команд замены, как в случае с делением. Для каждой константы набор команд определяется на основании их "весовых коэффициентов" и количества тактов процессора, необходимых для их выполнения. В качестве примера приведена вот такая табличка оптимизации умножения с 2 до 32. Ее всегда можно посмотреть и в самом мануале, но лучше пусть будет под рукой.
Code (Assembler) : Убрать нумерацию
  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)


Поделиться ссылкой ВКонтакте
Просмотров: 8293 | Комментариев: 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 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Это я :-)
Если программист в девять утра уже на работе, значит он там же и ночевал
Главная страница Web-мастеру и не только Образ мышления: Assembler Мои программы Software Темная сторона Силы Обзоры техники А еще я туда ем! Жизнь в оффлайне Всякая всячина
Карта сайта Ссылки Обратная связь Правила сайта Настройки сайта RSS-канал
Ограничение по возрасту 16+ Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Метки статей
.NET (30), AJAX (5), Assembler (362), COM (41), CSS (42), Exif (15), FASM (8), Firefox (7), HDD (17), Hello Teddy (9), HTML (52), iconBIT (4), JavaScript (73), MySQL (13), Nikon (19), PDF (10), PHP (122), Samsung (6), SEO (12), Sublime Text (9), TintonLife (4), UGREEN (4), Windows 7 (66), аккумуляторы (23), аксессуары (12), анализаторы файлов (8), архиваторы (6), аттракционы (7), безопасность (55), браузеры (16), бытовая техника (19), варенье (19), ВВЦ (9), ВДНХ (14), видео (20), Воробьевы горы (9), вторые блюда (125), выпечка (29), выставки (119), генератор ПСЧ (10), графика (120), десерты (31), Египет (8), заготовки на зиму (47), закуска (22), закуска к пиву (25), зарядные устройства (24), защита (15), зоопарки (10), игры (36), иконки (22), интерфейс (26), исследование защиты (317), каша (4), клавиатура (7), Коломенское (37), консоль (7), концерты (52), Кузьминки (4), куклы (27), ледяные скульптуры (6), мои программы (69), мониторы (6), музеи (78), мультимедиа (77), мясо (62), напитки (14), ноутбуки (8), обфускация (7), окна (69), оформление сайта (50), парки Москвы (7), песчаные скульптуры (13), плееры (10), подводная съемка (4), поздравления (130), полезные функции (42), прохождения (4), процессы (25), птица (21), путешествия (25), распаковка (22), реверсинг (52), рыба (35), салаты (19), сброс триала (4), сеть (36), система (178), Сокольники (8), соусы (14), супы (14), телефоны (10), Тунис (6), умный дом (13), файлы справки (6), фаст-фуд (18), фестиваль цветов (5), флешки (5), фото (23), хеши (16), числа (8), юмор (12), яйца (19), Яндекс (11)
Вам помог этот сайт?
Сказать спасибо! Поблагодарили 35,328 раз
<< 2024 - ОКТЯБРЬ >>
Пн Вт Ср Чт Пт Сб Вс
  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
28 29 30 31      
День кадрового работника
Всемирный день борьбы с артритом
Нашли на сайте орфографическую ошибку? Выделите ее мышкой и нажмите
Ctrl
+
Enter
Буду очень благодарен, если размеcтите мою кнопочку:
Личный блог ManHunter'а
Valid CSS Valid XHTML 1.0 Transitional Valid mobileOK Basic Valid RSS
Яндекс тИЦ: {YANDEX_TIC} Яндекс ИКС: 360
Сейчас я слушаю
---
Имя:

Сообщение:

Осталось символов: 200

   
-
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2024
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.08 сек. / MySQL: 2 (0.0062 сек.) / Память: 4.5 Mb
Наверх