Каким образом латентность работы арифметической или элементарной функции зависит от количества бит?

Question

Обратите внимание, что соотношение между 64-битными и 32-битными операциями с плавающей запятой различно на разных аппаратных средствах. Например, недавно NVidia улучшила 64-битную производительность, в то время как 32-битная осталась неизменной. Это сделало меня любопытным: учитывая достаточно широкий путь передачи данных, каковы факторы, определяющие, сколько должно быть определенных операций с плавающей запятой, когда вы удваиваете число битов?

Для целей этого вопроса предположим, что вы можете значительно увеличить ширину вашего пути к данным, удвоив число битов. Не неограничен (иначе теоретически возможна таблица поиска для любой арифметической функции), но достаточно широк, чтобы параллельно выполнять арифметические операции над независимыми битами. Учитывая это, каким фактором удвоение размера слова замедлит арифметические операции +,*,/? А как насчет встроенных элементарных функций, таких как log,exp,sin,atan?

РЕДАКТИРОВАТЬ:

Позвольте мне объяснить более ясно, что я спрашиваю здесь.

Прежде всего, известно, что если теоретически каждый имеет неограниченную схему / область, то можно вычислить любую математическую операцию на N-битных входных данных в O(log N). Все, что нужно сделать, это создать огромную хеш-таблицу размером 2^N (для функций с 1 операндом, например, sin(x)) или 2^(2*N) (для функций с 2 ​​операндами) и найти нужное значение используя ввод в качестве хеш-ключа. Излишне говорить, что это абсолютно непрактично, и мне не интересен такой ответ. Однако это показывает, что теоретически невозможно доказать, что любая операция обязательно потребует больше времени O (log N), учитывая произвольную ширину канала данных.

Во-вторых, также известно, что Omega(log N) является нижней границей даже для относительно простой операции, такой как сумматор. Это связано с глубиной зависимостей между выходными битами и, следовательно, глубиной схемы.

Вопрос на самом деле заключается в следующем: при разумной оценке размера схемы (скажем, не более, чем полиномиальных (N) вентилей), каково будет асимптотическое поведение задержки оптимальной схемы, реализующей операции арифметики и элементарных функций?

Известно, что ответом является O (log N) для сумматора, реализованного с помощью суммирующего сумматора. Я не знаю ответа для умножения, но подозреваю, что можно также реализовать его как схему O (log N), потому что умножение сводится к логическим значениям const времени, за которыми следует добавление нескольких операндов и расширение предыстории переноса для сумматора с несколькими операндами. не кажется слишком сложным.

Я понятия не имею, что будет асимптотикой для деления и квадратного корня.

Мне также любопытно узнать об общих элементарных функциях, таких как log, exp, sin и т. Д.

Answer 1

Есть два измерения, в которых увеличение логической сложности будет влиять на задержку цепи. Одним из них является влияние на этапы конвейера, где одна или несколько комбинационных задержек будут "критическими путями", ограничивающими минимальный тактовый период. Почти произвольно (хотя и с разными объемами работы) вы можете взять сложную схему и выполнить ее в любом количестве этапов. Большее количество этапов приведет к увеличению логики, увеличивая задержку в циклах, но также уменьшая минимальный тактовый период, что увеличивает пропускную способность. Обратите внимание, что при увеличении этапов вы сталкиваетесь с уменьшением доходности, поскольку регистры конвейера имеют постоянные издержки. Кроме того, большее количество этапов конвейера означает, что зависимые инструкции должны ждать дольше, чтобы получить свои входные данные, хотя это не сильно влияет на графические процессоры из-за высокой параллельности потоков.

Я просто упомяну, что увеличение площади схемы всегда будет косвенно влиять на производительность. Большие контуры означают более сложное размещение и маршрутизацию, и это будет означать, что комбинационные задержки не будут линейно масштабироваться с количеством логических элементов. Мы пока проигнорируем это.

Удвоение ширины канала данных для некоторых вещей не повлияет на комбинационную задержку. Например, если у вас есть побитовая операция И, каждый бит вычисляется независимо. Таким образом, в абстрактном случае удвоение ширины вашего канала данных не повлияет на время вашего цикла.

Теперь вы спрашиваете о плавающей точке, но конвейер с плавающей точкой будет состоять из целочисленных блоков, которые выполняют такие вещи, как сложение (и вычитание), умножение и сдвиг. Я собираюсь основываться на памяти здесь, так что, возможно, кто-то должен исправить меня, но здесь идет.

Заблаговременное добавление или субблок прогнозирования обычно увеличивается логарифмически с количеством битов, поэтому удвоение ширины канала данных (опять же, игнорируя влияние размещения и маршрутизации) лишь немного увеличит задержку.

IIRC, баррель имеет такую ​​же скорость роста, как add/sub.

Множитель будет линейно увеличиваться с шириной, потому что это более или менее двумерный массив полных сумматоров, но некоторые оптимизации могут быть сделаны. Поэтому, если вы удвоите ширину канала данных, я думаю, вы удвоите задержку схемы. Так что в этом случае вы можете разделить ваш множитель на два этапа.