Полное развертывание — единственный практичный способ, и вы правы, что он не подходит для большого количества итераций (и обычно не подходит для циклов, где количество итераций не является константой времени компиляции). Это отлично подходит для небольших циклов с известным количеством итераций.
Для вашего конкретного случая установки памяти на 1 на заданном расстоянии в x86 есть rep stosb, который реализует memset в микрокоде. Он не страдает от неправильного предсказания ветвления на текущих процессорах Intel, потому что ветки микрокода не могут быть предсказаны / спекулятивно выполнены и вместо этого останавливаются (или что-то в этом роде), что означает, что у него есть около 15 циклов накладных расходов при запуске, прежде чем делать какие-либо сохранения. См. Какую настройку выполняет REP? Для больших выровненных буферов rep stosb/d/q довольно близок к оптимизированному циклу AVX.
Таким образом, вы не получаете неверного прогноза, но получаете фиксированные накладные расходы при запуске. (Я думаю, что это останавливает выпуск/выполнение инструкций после rep stos, потому что секвенсор микрокода берет на себя переднюю часть, пока не закончит выдачу всех мопов. И он не может знать, когда это будет сделано, пока он не будет выполнен. некоторые, которые смотрят на rcx. Выдача происходит по порядку, поэтому более поздние независимые инструкции не могут даже попасть в неупорядоченную часть ядра до тех пор, пока rep stos не выяснит, какие мопы выдавать. Хранилища не должны выполняться , но ответвления микрокода есть.) Icelake должен иметь "быстрый короткий REP MOV", что может окончательно решить проблему с накладными расходами при запуске. Возможно, добавив выделенный аппаратный конечный автомат для rep movs и rep stos, например @KrazyGlew пожалел, что у него не было при разработке быстрых строк в Intel P6 uarch (ppro/PII/PIII), предке современных процессоров Intel, которые до сих пор используют очень похожие реализации микрокода. Насколько я знаю, AMD похожа, но я не видел цифр или подробностей об их rep stos накладных расходах при запуске.
В большинстве архитектур нет такой единственной инструкции memset, поэтому x86 определенно представляет собой особый случай в компьютерной архитектуре. Но некоторые старые компьютеры (например, Atari ST) могут иметь чип "blitter" для разгрузки копирующей памяти , особенно для графических целей. Они использовали бы DMA для копирования отдельно от процессора. Это было бы очень похоже на построение аппаратного конечного автомата на кристалле для запуска rep movs.
Неправильное предсказание ветвей нормального цикла
Рассмотрим обычный цикл asm, например
.looptop: do {
# loop body includes a pointer increment
# may be unrolled some to do multiple stores per conditional branch
cmp rdi, rdx
jb .looptop } while(dst < end_dst);
Ветвь оказывается строго предсказанной после того, как цикл пройдёт несколько раз.
При большом количестве итераций один неверный прогноз ветвления амортизируется по всем итерациям цикла и обычно незначителен. (Условная ветвь в нижней части цикла прогнозируется как выполненная, поэтому ветвь цикла неверно предсказывает один раз, когда она не была выполнена.)
Некоторые предикторы ветвления имеют специальную поддержку ветвлений цикла, с предсказателем шаблона, который может подсчитывать шаблоны, например, 30 раз выполнено / не выполнено. С некоторым большим пределом максимального количества итераций они могут правильно предсказать.
Или современный предсказатель TAGE (например, в семействе Intel Sandybridge) использует историю ветвей для индексации записи, поэтому он «естественно» дает вам некоторое предсказание шаблона. Например, Skylake правильно предсказывает ветвь выхода из цикла для внутренних циклов примерно до 22 итераций в моем тестировании. (Когда есть простой внешний цикл, который повторно запускает внутренний цикл с тем же числом итераций несколько раз.) Я тестировал на ассемблере, а не на C, поэтому я мог контролировать, сколько было выполнено развертывания.
Цикл средней длины, слишком длинный для правильного предсказания выхода, является худшим случаем для этого. Он достаточно короткий, чтобы часто возникало неверное предсказание выхода из цикла, если это внутренний цикл, который многократно выполняет ~ 30 итераций на процессоре, который, например, не может этого предсказать.
Стоимость одного неверного предсказания на последней итерации может быть довольно низкой. Если неупорядоченное выполнение может «увидеть» несколько итераций вперед для простого счетчика циклов, оно может выполнить саму ветвь, прежде чем тратить много времени на реальную работу за пределами этой неверно предсказанной ветви. С быстрым восстановлением пропущенных ветвей (без сброса всего неупорядоченного конвейера с помощью чего-то вроде буфера порядка ветвлений) вы все равно теряете возможность начать независимую работу после цикла в течение нескольких циклов. Это наиболее вероятно, если узким местом цикла является задержка цепочки зависимостей, но сам счетчик является отдельной цепочкой. Эта статья о реальной стоимости пропусков веток также интересно, и упоминает этот момент.
(Обратите внимание, что я предполагаю, что предсказание ветвления уже «загрунтовано», поэтому первая итерация правильно предсказывает ветвь цикла как выполненную.)
Непрактичные способы:
@Hadi связал забавную идею: вместо того, чтобы нормально запускать код, компилировать странным образом, когда управление и инструкции представляют собой все данные, например, x86, используя только инструкции mov с режимами адресации x86 + регистры. (и безусловная ветвь внизу большого блока). Можно ли принимать решения на ассемблере вообще без использования `jump` и `goto`? Это до смешного неэффективно, но на самом деле не имеет никаких условных ветвей: все зависит от данных.
Он использует разные формы MOV (между регистрами и непосредственно для регистрации, а также для загрузки/сохранения), поэтому это не компьютер с одним набором инструкций.
Менее безумная версия этого — интерпретатор: различные инструкции/операции в интерпретируемом коде превращаются в управляющие зависимости в интерпретаторе (создавая трудноразрешимую проблему эффективности для интерпретатора, см. Статья Дарека Михокки "Возвращение к общему циклу интерпретатора ЦП", но данные и поток управления в гостевом коде данные в интерпретаторе. Счетчик гостевой программы — это просто еще одна часть данных в интерпретаторе.
person
Peter Cordes
schedule
17.04.2018
