(Как) я могу предсказать время выполнения фрагмента кода с помощью LLVM Machine Code Analyzer? - PullRequest
Новая
       52

(Как) я могу предсказать время выполнения фрагмента кода с помощью LLVM Machine Code Analyzer?

0 голосов
/ 09 января 2019

Я использовал llvm-mca для вычисления полных циклов части кода, полагая, что они предсказывают время его выполнения. Однако динамическое измерение времени выполнения практически не выявило корреляции. Итак: Почему суммарные циклы, вычисленные с помощью llvm-mca, не позволяют точно предсказать время выполнения? Можно ли как-нибудь лучше предсказать время выполнения с помощью llvm-mca?

подробности:

Я хотел знать время выполнения следующего кода для различных типов итераторов begin (и end), для startValue, являющихся 0.0 или 0ULL: 

std::accumulate(begin, end, starValue)

Чтобы предсказать время выполнения, я использовал Compiler Explorer (https://godbolt.org/z/5HDzSF) с его плагином LLVM Machine Code Analyzer (llvm-mca), поскольку llvm-mca - это «инструмент анализа производительности, который использует информацию, доступную в LLVM ( например, планирование моделей) для статического измерения производительности ". Я использовал следующий код: 

using vec_t = std::vector<double>;

vec_t generateRandomVector(vec_t::size_type size)
{
    std::random_device rnd_device;
    std::mt19937 mersenne_engine {rnd_device()};
    std::uniform_real_distribution dist{0.0,1.1};
    auto gen = [&dist, &mersenne_engine](){
        return dist(mersenne_engine);
    };
    vec_t result(size);
    std::generate(result.begin(), result.end(), gen);
    return result;
}

double start()
{
    vec_t vec = generateRandomVector(30000000);
    vec_t::iterator vectorBegin = vec.begin();
    vec_t::iterator vectorEnd = vec.end();
    __asm volatile("# LLVM-MCA-BEGIN stopwatchedAccumulate");
    double result = std::accumulate(vectorBegin, vectorEnd, 0.0);
    __asm volatile("# LLVM-MCA-END");    
    return result;
}

Тем не менее, я не вижу никакой корреляции между общим количеством циклов компьютера по llvm-mca и временем настенных часов от запуска соответствующего std :: накопления. Например, в приведенном выше коде общее количество циклов равно 2806, время выполнения равно 14 мс. Когда я переключаюсь на startValue 0ULL, общее количество циклов составляет 2357, но время выполнения составляет 117 мс.

1 Ответ

0 голосов
/ 09 января 2019

TL: DR: LLVM-MCA проанализировала весь кусок кода между этими комментариями, как если бы это было тело цикла, и показала счетчик циклов для 100 итераций всех этих инструкции.

Но, кроме собственно (крошечного) цикла, большинство инструкций - это настройка цикла и горизонтальная сумма SIMD после цикла, который фактически выполняется только один раз. (Вот почему число циклов указывается в тысячах, а не в 400 = 100 при 4-тактной задержке vaddpd на Skylake для версии 0.0 с аккумулятором double.)

Если вы снимите флажок "//" в проводнике компилятора Godbolt или измените операторы asm, добавив nop, например "nop # LLVM-MCA-END", вы сможете найти эти строки в окне asm и посмотреть, что такое LLVM- MCA смотрел как это "петля".

LLVM MCA имитирует указанную последовательность инструкций по сборке и вычисляет количество циклов, которое, по ее оценкам, потребуется для выполнения за итерацию в указанной целевой архитектуре. LLVM MCA делает ряд упрощений, таких как (вне головы): (1) он предполагает, что все условные ветви проваливаются, (2) он предполагает, что все обращения к памяти имеют тип памяти обратной записи, и все попадания в кэш L1, (3) он предполагает, что интерфейс работает оптимально, и (4) call инструкции не выполняются в вызываемой процедуре, и они просто проваливаются. Есть и другие предположения, которые я не могу вспомнить в данный момент.

По сути, LLVM MCA (как и Intel IACA) является точным только для простых циклов с привязкой к внутренним вычислениям. В IACA, хотя большинство инструкций поддерживаются, некоторые инструкции не смоделированы подробно. Например, предполагается, что инструкции предварительной выборки потребляют только микроархитектурные ресурсы, но в основном имеют нулевую задержку и не влияют на состояние иерархии памяти. Однако мне кажется, что MCA полностью игнорирует такие инструкции. Во всяком случае, это не особенно относится к вашему вопросу.

Теперь вернемся к вашему коду. В предоставленной вами ссылке Compiler Explorer вы не передали никаких опций LLVM MCA. Таким образом, целевая архитектура по умолчанию вступает в силу, то есть любая архитектура, на которой работает инструмент. Это случилось с SKX. Общее количество циклов, которое вы упомянули, относится к SKX, но не ясно, запускали ли вы код на SKX или нет. Вы должны использовать опцию -mcpu, чтобы указать архитектуру. Это не зависит от -march, который вы передали в gcc. Также обратите внимание, что сравнение основных циклов с миллисекундами не имеет смысла. Вы можете использовать инструкцию RDTSC для измерения времени выполнения с точки зрения циклов ядра.

Обратите внимание, как компилятор встроил вызов std::accumulate. По-видимому, этот код начинается в строке сборки 405, а последняя инструкция std::accumulate находится в строке 444, всего 38 инструкций. Причина, по которой оценка MCA LLVM не будет соответствовать фактическим показателям, стала ясна сейчас. Инструмент предполагает, что все эти инструкции выполняются в цикле для большого количества итераций. Очевидно, это не тот случай. Из 420-424 есть только одна петля: 

.L75:
        vaddpd  ymm0, ymm0, YMMWORD PTR [rax]
        add     rax, 32
        cmp     rax, rcx
        jne     .L75

Только этот код должен быть вводом в MCA. На уровне исходного кода на самом деле нет способа заставить MCA анализировать только этот код. Вам нужно будет вручную вставить std::accumulate и поместить метки LLVM-MCA-BEGIN и LLVM-MCA-END где-нибудь внутри него.

При передаче 0ULL вместо 0.0 в std::accumulate ввод в MCA LLVM начинается с инструкции по сборке 402 и заканчивается на 441. Обратите внимание, что любые инструкции, не поддерживаемые MCA (например, vcvtsi2sdq), будут быть полностью исключен из анализа. Часть кода, которая на самом деле находится в цикле: 

.L78:
        vxorpd  xmm0, xmm0, xmm0
        vcvtsi2sdq      xmm0, xmm0, rax
        test    rax, rax
        jns     .L75
        mov     rcx, rax
        and     eax, 1
        vxorpd  xmm0, xmm0, xmm0
        shr     rcx
        or      rcx, rax
        vcvtsi2sdq      xmm0, xmm0, rcx
        vaddsd  xmm0, xmm0, xmm0
.L75:
        vaddsd  xmm0, xmm0, QWORD PTR [rdx]
        vcomisd xmm0, xmm1
        vcvttsd2si      rax, xmm0
        jb      .L77
        vsubsd  xmm0, xmm0, xmm1
        vcvttsd2si      rax, xmm0
        xor     rax, rdi
.L77:
        add     rdx, 8
        cmp     rsi, rdx
        jne     .L78

Обратите внимание, что в коде есть условный переход jns, целевой адрес которого находится где-то в блоке. MCA просто предположит, что прыжок провалится. Если этого не произошло при фактическом запуске кода, MCA излишне добавит накладные расходы из 7 инструкций. Есть еще один скачок, jb, но этот, я думаю, не важен для больших векторов и будет падать большую часть времени. Последний переход, jne, также является последней инструкцией, поэтому MCA будет считать, что следующая инструкция снова является верхней. Для достаточно большого количества итераций это допущение совершенно нормально.

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

...