Я работаю над устройством GPU с очень высокой задержкой целочисленного деления, несколькими сотнями циклов. Я ищу оптимизацию разделов.
Все деления на знаменатель, который находится в наборе {1,3,6,10}, однако числитель - это положительное значение времени выполнения, примерно 32000 или меньше. из-за ограничений памяти, таблица поиска может не быть хорошим вариантом.
Можете ли вы подумать об альтернативах? Я думал о вычислении обратных точек с плавающей запятой и используя их для умножения числителя.
Спасибо
PS. спасибо людям. бит-сдвиг взлома - это действительно здорово. для восстановления после округления, я использую следующий сегмент C:
// q = m/n
q += (n*(j +1)-1) < m;
a/b=a*(1/b)
x=(1<<16)/b
a/b=(a*x)>>16
Вы можете создать таблицу поиска для знаменателей? так как вы сказали, что 15-битные числители, вы можете использовать 17 для сдвигов, если все без знака 32 бит:
a/b=a*((1<<17)/b)>>17
Чем больше сдвиг, тем меньше ошибка округления. Вы можете выполнить проверку грубой силы, чтобы увидеть, сколько раз, если таковые имеются, это действительно неправильно.
Стандартными взломами встроенных систем для этого является преобразование целочисленного деления на N в умножение на фиксированную точку на 1/N.
Предполагая, что 16 бит, 0.33333 можно представить как 21845 (десятичный). Умножьте, предоставив 32-битное целочисленное произведение и сдвиньте 16 бит.
Вы почти наверняка столкнетесь с некоторой ошибкой округления (усечения). Это может быть или не быть чем-то, с чем вы можете жить.
Возможно, стоит посмотреть на свой GPU и посмотреть, можете ли вы скомпоновать более быструю процедуру разделения по целому ряду, используя ваши знания ограниченного диапазона числителя.
В книге "Хакерский восторг" Генри Уоррена имеется целая глава, посвященная целочисленному делению по константам, включая методы, которые преобразуют целое число деление на операцию умножения/сдвига/добавления.
Эта страница вычисляет магические числа для операций умножения/сдвига/добавления: