Производительность BSF / BSR не зависит от данных каких-либо современных процессоров. См. https://agner.org/optimize/, https://uops.info/ (только для Intel) или http://instlatx64.atw.hu/ для экспериментальной синхронизациирезультаты, а также https://gmplib.org/~tege/x86-timing.pdf, которые вы нашли.
На современном Intel они декодируют до 1 мегапикселя с задержкой 3 цикла и пропускной способностью 1 / такт, работая только на порту 1. Ryzen также запускает ихс задержкой 3c для BSF, задержкой 4c для BSR, но с несколькими мопами.Ранее AMD иногда даже медленнее.
Ваша стоимость "8 циклов" (задержка и пропускная способность), по-видимому, для 32-битного BSF на AMD K8, из таблицы Гранлунда, которую вы связали.Таблица Агнера Фога согласна (и показывает, что она декодируется до 21 моп вместо того, чтобы иметь выделенный модуль выполнения битового сканирования. Но микрокодированная реализация, по-видимому, все еще не имеет ответвлений и не зависит от данных).Понятия не имею, почему вы выбрали этот номер;K8 не имеет SMT / Hyperthreading, поэтому возможность для бокового канала синхронизации ALU значительно уменьшена.
Обратите внимание, что у них есть выходная зависимость от регистра назначения, который они оставляютнемодифицированный, если ввод был нулевым. AMD документирует это поведение, Intel реализует его аппаратно, но документирует его как «неопределенный» результат , поэтому, к сожалению, компиляторы не воспользуются этим, и, возможно, программисты-людидолжен быть осторожным.IDK, если какой-то древний 32-битный только ЦП имел другое поведение, или если Intel планирует когда-либо изменить (сомнительно!), Но я бы хотел, чтобы Intel документировал поведение по крайней мере для 64-битного режима (исключая любые старые процессоры).
lzcnt / tzcnt и popcnt на процессорах Intel (но не AMD) имеют одинаковую зависимость выхода до Skylake и до Cannon Lake (соответственно), хотя архитектурно результат хорошо определен для всехвходы.Все они используют один и тот же исполнительный блок.( Как POPCNT реализован на аппаратном уровне? ).AMD Bulldozer / Ryzen строит свой модуль выполнения битового сканирования без запоминания выходной зависимости, поэтому BSF / BSR работают медленнее, чем LZCNT / TZCNT (несколько мопов для обработки случая input = 0, и, вероятно, также устанавливают ZF в соответствии с вводом, а нерезультат).
Псевдокод в руководстве не является реализацией.
Он дает точно такой же результат во всех случаях, так что вы можете использовать его, чтобы точно понять, что произойдетдля любых угловых случаев текст заставляет задуматься.То есть all .
Смысл в том, чтобы быть простым и легким для понимания, и это означает моделирование вещей в терминах простых операций с двумя входами, которые происходят последовательно. C / Fortran / типичный псевдокод не имеет операторов для множественных входов И, ИЛИ или XOR, но вы можете встроить его в аппаратные средства до определенного момента ( ограничен вентилятором , противоположным вентилятору-out).
Целочисленное добавление может быть смоделированным как перенос последовательных битов, но это не так, как это реализовано!Вместо этого мы получаем задержку одного цикла для 64-битного сложения с гораздо меньшими задержками в 64 шлюза, используя такие хитрости, как перенос сумматоров с упреждением .
Используемые методы фактической реализациив модуле исполнения bit-scan / popcnt Intel описаны в патенте США US 8214414 B2 .
аннотация
A объединеныописан путь к данным для PopCount и BitScan.Аппаратная схема включает в себя дерево компрессоров, используемое для функции PopCount, которое повторно используется функцией BitScan (например, прямое сканирование битов (BSF) или обратное сканирование битов (BSR)).
Логика селектора включает дерево компрессоровработать с входным словом для операции PopCount или BitScan на основе инструкции микропроцессора.Входное слово кодируется, если выбрана операция BitScan.
Дерево компрессоров получает входное слово, работает с битами так, как будто все биты имеют одинаковый уровень значимости (например, для N-битного входного слова,входное слово обрабатываетсякак N однобитных входов). Результатом схемы дерева компрессора является двоичное значение , представляющее число, относящееся к выполненной операции (количество установленных битов для PopCount, или позиция бита первого установленного бита, обнаруженного при сканированиивходное слово ).
Можно с уверенностью предположить, что реальный кремний Intel работает аналогично этому.Другие патенты Intel на такие вещи, как нестандартное оборудование (ROB, RS), действительно совпадают с экспериментами по производительности, которые мы можем выполнить.
AMD может сделать что-то другое, но независимо от того, что мы знаем из экспериментов по производительности, этоне зависит от данных.
Хорошо известно, что фиксированная задержка очень полезна для внепланового планирования, поэтому очень удивительно, когда инструкции не имеют фиксированную задержку. Sandybridge даже пошел настолько далеко, что стандартизировал задержки, чтобы упростить планировщик и уменьшить вероятность конфликтов обратной записи (например, 3-тактная задержка с последующим 2-тактовой задержкой).Переход на один и тот же порт даст 2 результата в одном и том же цикле).Это означало, что комплексный LEA (со всеми 3 компонентами: [disp + base + idx*scale]) занимает 3 цикла вместо 2 для 2 добавлений, как на предыдущих процессорах.На семействе Сэндибридж нет 2-тактных задержек.(Существуют некоторые 2-тактовые команды задержки, потому что они декодируют до 2 мопов с задержкой 1 с каждая, но планировщик планирует мопы, а не инструкции).
Одно из немногих исключений из правила фиксированной задержки для ALUuops - это Division / sqrt, который использует не полностью конвейеризованный модуль выполнения.Деление по своей сути итеративное, в отличие от умножения, когда вы можете создавать широкое оборудование, которое выполняет частичные продукты и частичные добавления параллельно.
На процессорах Intel переменная задержка для доступа к кэш-памяти L1d может привести к воспроизведению зависимых мопов, если данныене был готов, когда планировщик оптимистично надеялся, что это будет.