Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Замена деления на умножение.  (Прочитано 19894 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Aether
Специалист

ru
Offline Offline
Пол: Мужской

« : 24-01-2018 16:49 » 

Доброго вечера.

Хочу поинтересоваться: насколько развилась современная архитектура у x86/64 - всё ещё имеет смысл заменить одну операцию целочисленного деления на две операции целочисленного умножения? Или это уже не важно? И если важно, то каково хотя бы примерное соотношение скоростей этих операций, разумеется в варианте внутри регистров?

PS: регистров по 32 бита и по 64 бита в отдельных случаях.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 24-01-2018 21:28 » 

Алгоритм целочисленного деления требует N вычитаний и N сдвигов, где N — разрядность числа. Умножение — обратный процесс: N сдвигов и N сложений. Т.е. в базе количество операций равное. Деление оптимизируется по приходу вычитаемого к нулю. Умножение оптимизируется пропуском сложений, если очередной бит множителя равен нулю. Как это реализовано схемотехнически, на столько быстрее от базового алгоритма и будет работать. При особом расточительстве можно и за 1 такт вычислить.
На мой взгляд быстрый делитель сделать сложнее, чем умножитель. Т.ч. логично будет предположить, что в большинстве реализаций ALU умножение быстрее деления. Значит да, умножение на обратную величину будет быстрее деления.
А вот если у нас плавающие значения, не уверен. Предположу, что примерно также + сложение мантис.
« Последнее редактирование: 24-01-2018 21:31 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 24-01-2018 21:46 » 

Но сперва задайся вопросом, зачем. Параллельно могут выполняться другие, более тормозные процессы. Караван идет со скоростью самого медленного верблюда.
http://ithare.com/infographics-operation-costs-in-cpu-clock-cycles/
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Aether
Специалист

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 25-01-2018 09:28 » 

Хочется получить хорошую скорость в перспективе, поэтому есть идеи по реорганизации алгоритма. Сейчас нашёл данные только для PII, в нём умножение 32-х бит регистров выполняется за 3 такта, а деление 4 такта. Как бы при замене одного деления на два умножения идея терпит фиаско.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 25-01-2018 22:16 » new

https://habrahabr.ru/company/intel/blog/346822/
Для интереса почитай. Они тоже заняты вопросами ускорения. Но, к примеру, многопоточность не всегда дает ускорение, хотя казалось бы, в два потока пережевать быстрее. Работа с памятью и кешов оказалась важнее.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines