четверг, 26 мая 2016 г.

Профиль программы и его предсказание

Сегодня хотел бы рассказать про то как в компиляторе представлена профильная информация и как она предсказывается. Студентам и просто людям часто выносит мозг тот факт что компилятор статически (т.е. без реального исполнения) может предсказывать такие вещи как количество итераций у цикла или просто вероятности переходов, поэтому расскажу об этом по подробнее.
Для начала опишу проблему. В некоторых процессорах с прямым порядком исполнения команд (in-order) нужно уметь хорошо планировать код. Более того ситуация становится совсем плохой если в процессоре отсутствует предсказатель переходов. Т.о. компилятору становится необходимо брать все эти функции на себя. Необходимо понять по какой ветке и с какой вероятностью пойдёт исполнение, какой цикл является горячим и стоит ли его раскручивать/конвейеризовывать, какая функция является горячей и стоит ли её инлайнить. (Кстати, из интеловских лекций следует что они также используют предсказатель и для x86 процессоров).

Чтобы уметь делать всё выше перечисленное, мы приходим к понятию профиля. Внутри компилятора он представляет из себя немного не то к чему привыкли пользователи gprof/perf/etc. Надеюсь что читатель уже знает что такое cfg, поэтому перейдём к описанию. Профилем программы является информация о количестве проходов по узлам cfg и вероятность перехода по каждой дуге. Чтобы было понятно, можно посмотреть на рисунок:

На нём видно, что каждая дуга (исходящая, но к входящим это тоже относится) имеет 2 цифры. Первая - это счётчик. Он говорит сколько раз мы прошли по данной дуге. Вторая - это вероятность. Она говорит с какой вероятностью мы переходим на данную дугу из исходного узла. Эти две цифры вазимозаменяемы и должны постоянно поддерживаться в согласованном состоянии. Для узла вероятность смысла не имеет (на самом деле имеет, но не в данном контексте), поэтому у него есть только счётчик.

Откуда берётся данная информация? Есть два способа её получить. Первый, и довольно очевидный - исполнить программу и посмотреть. Но такой метод имеет много минусов, и к сожалению используется редко (а ведь он может значительно ускорить программа на Эльбрусах, да и не только).

Второй метод - предсказать. Предсказание проходит по следующему принципу: мы полагаем что стартовый узел имеет счётчик 1. Далее для всех исходящих дуг мы вычисляем счётчики по формуле:
$$
C(E_{\text{out}}) = C(N) C(P_{\text{out}})
$$
Далее для каждого узла мы вычисляем счётчик по формуле:
$$
C(N) = \sum\limits_{i = 1}^K C(E^{in}_i)
$$
Таким образом проходим по всей процедуре и предсказываем профиль. Возникает логичный вопрос: откуда взять вероятности? Их берём с полка выставляем исходя из данных, известных во время компиляции или некоторых эвристик. Например если мы можем статически прикинуть результат условного оператора, то вероятность вычислить легко. Если нет, то компилятор имеет определённую статистику по вероятностям переходов при определённой структуре cfg.

Теперь вопрос: что делать если у нас встретилась обратная дуга? Т.е. имеем cfg следующего вида:

Если будем действовать по описанному выше алгоритму, то зациклимся и будем постоянно наращивать счётчик. Решается это поиском вероятности выйти из цикла (т.е. без учёта обратной дуги) и проставления счётчиков в соответствии с этой вероятностью. Формула для этого на удивление простая, а реализация её вычисления на удивление сложное:
$$
I = \frac1{P_{loop\_out}(E^{out}_i)}
$$
Самая большая хитрость в том чтобы её посчитать. Не буду описывать здесь как это делается (это долго и скучно), скажу только что сложность алгоритма немного возрастает если идёт гнездо циклов, и сильно возрастает если цикл несводимый.

Касательно точности такого предсказания могу сказать что никогда не делал исследования этого вопроса, но попытки отключения профиля или неаккуратная его корректировка могут просаживать производительность в разы.

2 комментария:

  1. Анонимный29 мая 2016 г., 20:10

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

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

    ОтветитьУдалить
    Ответы
    1. > Хм, так а аппаратный то наверно точно так же и работает, по тем же алгоритмам?

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

      > Я кстати про предсказывание путем самого обычного подбора через исполнение и сравнение сразу же подумал, а вот аппаратный предсказатель так уже не сможет.

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

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

      Мне было очевидно что Интел прибегает к этому для Итаниумов, но что они и для x86 тоже предсказатель используют я не был уверен, поэтому немного удивился. Фишка в том что на этапе компиляции у нас нет входных данных. Т.е. да, нам известна структура программы, но без входных данных мы не можем ничего точно предполагать. И это значительно снижает точность предсказания. Даже динамический профиль не всегда помогает, потому что в SPEC'ах, например есть задачи с плохой обучающией выборкой и применение динамического профилирования только замедляет задачу.

      > А про внеочередное исполнение расскажете?

      Ну большинство современных процессоров работают по OoO схеме. Если в двух словах, то в процессоре есть очередь инструкций на исполнение, и как только становятся известны аргументы какой-либо, он посылает её на исполнение независимо от изначального порядка подачи в буфер.

      > Я так понимаю это единственная такого рода проблема которая не ложится на машину без суперскалярных йобушек, или оно вообще не нужно становится?

      Я бы сказал что скорее его отсутствие приводит к значительному усложнению компилятора. Т.е. если в OoO процессор получает очередь инструкций

      SUB F2, F4 -> F0
      ADD F0, F8 -> F10
      DIV F8, F14 -> F12

      то он может самостоятельно понять что ADD зависит от SUB, а DIV - нет, и забросить DIV наверх, или распределить их на разные исполняющие устройства. В случае с In-Order это приходится делать компилятору. И если в данном примере это довольно просто, то когда начинается работа с LOAD/STORE, то приходится писать сложные анализы указателей для определния независимости операций. А потом приходится ещё и сложный планировщик инструкций делать. Поэтому для VLIW процессоров хороший компилятор просто жизненно необходим. Ну и важно ещё писать хороший код чтобы компилятор мог лучше его понимать и оптимизировать.

      Удалить