Медленная jmp-инструкция

Question

Медленная jmp-инструкция

В продолжение моего вопроса . Преимущества использования 32-битных регистров / инструкций в x86-64, я начал измерять стоимость инструкций. Я знаю, что это было сделано несколько раз (например, Агнер Фог), но я делаю это для развлечения и самообразования.

Мой тестовый код довольно прост (для простоты здесь, как псевдокод, в действительности на ассемблере):

for(outer_loop=0; outer_loop<NO;outer_loop++){
    operation  #first
    operation  #second
    ...
    operation #NI-th
}

Но все же некоторые вещи должны быть рассмотрены.

Если внутренняя часть петли большая (большая NI>10^7), весь контент цикла не помещается в кэш инструкций и, следовательно, должен загружаться снова и снова, поэтому скорость ОЗУ определяет время, необходимое для выполнения. Например, для больших внутренних частей, xorl %eax, %eax (2 байта) на 33% быстрее, чем xorq %rax, %rax (3 байта).
Если NI маленький, и весь цикл легко помещается в кеш инструкций, чем xorl %eax, %eax а также xorq %rax, %rax одинаково быстры и могут выполняться 4 раза за такт.

Однако эта простая модель не выдерживает jmp-instruction. Для jmp-инструкция моего тестового кода выглядит следующим образом:

for(outer_loop=0; outer_loop<NO;outer_loop++){
    jmp .L0
    .L0: jmp .L1
    L1: jmp L2
    ....
}

И результаты:

Для "больших" размеров петли (уже для NI>10^4) Я измеряю 4,2 нс /jmp-инструкция (приравнивается к 42 байтам, загруженным из ОЗУ или около 12 тактов на моей машине).
Для маленьких размеров петли (NI<10^3) Я измеряю 1 нс /jmp-инструкция (которая составляет около 3 тактов, что звучит правдоподобно - в таблицах Агнера Фога показаны затраты на 2 такта).

Инструкция jmp LX использует 2 байта eb 00 кодирование.

Таким образом, мой вопрос: что может быть объяснением высокой стоимости jmp-инструкция в "больших" петлях?

PS: Если вы хотите попробовать его на своем компьютере, вы можете скачать скрипты отсюда, просто запустите sh jmp_test.sh в папке src.

Редактировать: Экспериментальные результаты, подтверждающие теорию размера Питера BTB.

В следующей таблице показаны циклы на инструкцию для разных ǸI значения (относительно NI=1000):

|oprations/ NI        | 1000 |  2000|  3000|  4000|  5000| 10000|
|---------------------|------|------|------|------|------|------|
|jmp                  |  1.0 |  1.0 |  1.0 |  1.2 |  1.9 |   3.8|
|jmp+xor              |  1.0 |  1.2 |  1.3 |  1.6 |  2.8 |   5.3|
|jmp+cmp+je (jump)    |  1.0 |  1.5 |  4.0 |  4.4 |  5.5 |   5.5|
|jmp+cmp+je (no jump) |  1.0 |  1.2 |  1.3 |  1.5 |  3.8 |   7.6|

Это можно увидеть:

Для jmp инструкции (пока неизвестного) ресурса становится мало, и это приводит к снижению производительности для ǸI больше чем 4000
Этот ресурс не передается с такими инструкциями, как xor - снижение производительности начинает действовать NI около 4000, если jmp а также xor исполняются после друг друга.
Но этот ресурс делится с je если прыжок сделан - для jmp+je друг за другом ресурс становится дефицитным для NI около 2000
Однако если je совсем не прыгает, ресурс снова становится дефицитным для NI около 4000 (4-я строка).

В статьях Мэтта Годболта по обратному проектированию с предсказанием ветвлений указывается, что емкость целевого буфера ветвления составляет 4096 записей. Это очень убедительное доказательство того, что пропуск BTB является причиной наблюдаемой разницы в пропускной способности между малым и большим jmp петли.

12

performance assembly x86 cpu-architecture intel

Источник

user5769463 07 авг '16 в 07:23

1 ответ

Решение

Другие вопросы по тегам performance assembly x86 cpu-architecture intel

user224132 07 авг '16 в 08:23 2016-08-07 08:23 · Accepted Answer · 2016-08-07 08:23

TL:DR: мое текущее предположение исчерпывает записи BTB (целевой буфер ветвления). Увидеть ниже.

Даже если ваш jmp s no-ops, у CPU нет дополнительных транзисторов для обнаружения этого особого случая. Они обрабатываются так же, как и любой другой jmp, что означает необходимость перезапуска выборки команд из нового местоположения, создавая пузырь в конвейере.

Чтобы узнать больше о переходах и их влиянии на конвейерные процессоры, Control Hazards в классическом конвейере RISC должно быть хорошим введением в то, почему ветки трудны для конвейерных процессоров. Руководства Агнера Фога объясняют практические последствия, но я думаю, что предполагают некоторые из таких базовых знаний.

Ваш процессор Intel Broadwell имеет uop-кеш, который кэширует декодированные инструкции (отдельно от I-кеша 32 кБ L1).

Размер кэша мопов составляет 32 набора по 8 способов, по 6 мопов на строку, что в общей сложности составляет 1536 мопов (если каждая строка упакована по 6 моп; идеальная эффективность). 1536 мопов - от 1000 до 10000 тестовых размеров. Перед вашим редактированием я предсказал, что отсечка для медленного на быстрое будет примерно 1536 команд в вашем цикле. Он вообще не замедляется, пока не превысит 1536 инструкций, поэтому я думаю, что мы можем исключить эффекты uop-cache. Это не такой простой вопрос, как я думал.:)

Запуск из uop-кэша (небольшой размер кода) вместо декодеров команд x86 (большие циклы) означает, что перед этапом, который распознает этап, меньше этапов конвейера jmp инструкции. Таким образом, мы можем ожидать, что пузырьки от постоянного потока скачков будут меньше, даже если они предсказаны правильно.

Предполагается, что работа с декодерами дает больший штраф за неверный прогноз ветвления (например, 20 циклов вместо 15), но это не предсказанные ветвления.

Несмотря на то, что ЦПУ не нужно прогнозировать, выбрана ли ветвь или нет, он все равно может использовать ресурсы прогнозирования ветвления, чтобы предсказать, что блок кода содержит взятую ветвь, прежде чем он будет декодирован.

Кэширование того факта, что в определенном блоке кода есть ветвь и ее целевой адрес, позволяет внешнему интерфейсу начинать извлекать код из целевой ветки до jmp rel32 Кодировка фактически декодируется. Помните, что декодирование x86-команд переменной длины сложно: вы не знаете, где начинается одна инструкция, пока не будет декодирована предыдущая. Таким образом, вы не можете просто сопоставить шаблон с потоком инструкций, ища безусловные переходы / вызовы, как только он будет получен.

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

См. Также Какое неверное предсказание ветвления обнаруживает целевой буфер ветвления? который имеет хороший ответ и обсуждение в этой теме Realworldtech.

Один очень важный момент: BTB предсказывает, какой блок следует выбрать следующим, а не точное назначение конкретной ветви в блоке выборки. Таким образом, вместо того, чтобы предсказывать цели для всех ветвей в блоке выборки, ЦП просто нужно прогнозировать адрес следующей выборки.

Да, пропускная способность памяти может быть узким местом при работе с очень высокой пропускной способностью, такой как обнуление xor, но вы сталкиваетесь с другим узким местом с jmp, Процессор успеет извлечь 42B из памяти, но это не то, что он делает. Предварительная выборка может легко выдерживать 2 байта на 3 такта, поэтому должно быть почти нулевое количество пропусков I-кэша L1.

В вашем xor с / без теста REX пропускная способность основной памяти могла бы стать узким местом, если бы вы тестировали с достаточно большим циклом, чтобы он не помещался в кэш L3. Я потребляю 4 * 2B за такт на процессоре ~3 ГГц, что составляет почти максимум 25 ГБ / с DDR3-1600 МГц. Однако даже кэш-память третьего уровня будет достаточно быстрой, чтобы поддерживать скорость 4 * 3B на цикл.

Интересно, что основная память BW является узким местом; Сначала я предполагал, что декодирование (в блоках по 16 байт) будет узким местом для 3-байтовых XOR, но я думаю, что они достаточно малы.

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

Для бенчмаркинга в тактах используйте perf stat ./a.out, Существуют и другие полезные счетчики производительности, которые необходимы для понимания характеристик производительности.

См. X86-64 Относительная производительность jmp для результатов счетчика перфорации для Core2 (8 циклов на джамп) и некоторые неизвестные микроархитектуры, где она составляет ~10c на джамп.

Детали современных характеристик производительности процессора достаточно сложны для понимания даже в более или менее "белых ящиках" (читая руководство по оптимизации Intel и то, что они опубликовали в отношении внутренних компонентов процессора). Вы начнете застревать рано и часто, если будете настаивать на тестировании "черного ящика", когда вы не читаете такие вещи, как статьи о arstechnica о новом дизайне ЦП, или, может быть, некоторые более подробные вещи, такие как обзор микроархива Дэвида Кантера в Haswell, или тому подобное Sandybridge рецензия я связал ранее.

Если вы застряли рано и часто в порядке, и вам весело, то обязательно продолжайте делать то, что делаете. Но людям становится труднее отвечать на ваши вопросы, если вы не знаете этих деталей, как в этом случае.:/ Например, моя первая версия этого ответа предполагала, что вы прочитали достаточно, чтобы узнать, что такое кэш uop.