Здравствуйте, уважаемые читатели.

В мае мы выпустили 2-е издание (на русском языке - первое) фундаментальной книги Дениса Бахвалова "Оптимизация производительности современных процессоров". Денис Бахвалов, легендарный в узких кругах разработчик процессоров из компании "Intel", ведёт классный англоязычный блог Easyperf, в котором рассуждает на разнообразные темы, связанные с профилированием процессоров, поиском узких мест, машинным кодом, а также со своей книгой. Сегодня предлагаем вам перевод одной из самых глубоких и стратегически важных статей этого блога, многие аспекты которой подробнее раскрыты в книге. Далее - от автора

Существует множество способов анализировать производительность приложения, выполняемого на современном процессоре. В этой статье я рассмотрю эту проблему в ещё одном ракурсе. Разобранную здесь концепцию важно усвоить для того, чтобы составить общее впечатление о тех ограничениях, с которыми сталкивается современная индустрия вычислений на ЦП. Кроме того, предложенная здесь ментальная модель поможет вам лучше понимать, насколько производителен ваш код. Во второй части статьи я разверну все четыре категории, расскажу о программных и аппаратных решениях, дам ссылки на исследовательские статьи и скажу несколько слов о перспективах развития.

Переходим прямо к делу. На уровне центрального процессора (ЦП) производительность любого приложения ограничивается четырьмя факторами:

• Предсказуемость кода

• Предсказуемость данных

• Пропускная способность при выполнении

• Задержка при выполнении

Вот как это можно представить. Во-первых, современные процессоры всегда пытаются спрогнозировать, какой код будет выполняться далее (это и есть «предсказуемость кода»). В этом смысле код ЦП всегда немного опережает события, заглядывая в будущее. Корректные прогнозы значительно способствуют правильному выполнению, поскольку позволяют ЦП продвигаться с работой быстрее, чем поступают в распоряжение результаты уже выполненных инструкций. Но, если с этим не угадывать, то зачастую приходится дорого расплачиваться за ошибки из-за падения производительности.

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

В-третьих (речь о “предсказуемости данных”), некоторые инструкции обращаются к памяти. В настоящее время это одно из самых серьёзных узких мест, поскольку продолжает расти разрыв в производительности между ЦП и памятью. Надеюсь, уже все знают, что обращаться за данными в кэш получается быстро, а обращения к DRAM могут проходить в 100 раз медленнее. Именно поэтому существуют инструменты аппаратной предвыборки, цель которых — спрогнозировать, к каким данным программа обратится в ближайшем будущем и заранее подтянуть эти данные. Таким образом, к тому моменту, как программе потребуется двигаться дальше, нужные значения уже будут лежать в кэшах. К этой категории относятся проблемы, возникающие из-за не самой хорошей компоновки инструкций в пространстве и времени, так как кэш пытается учитывать и первое, и второе. Кроме того, в эту категорию я включаю проблемы, связанные с буфером ассоциативной трансляции (TLB).

В-четвёртых, поговорим о «задержке при выполнении». В абсолютном большинстве приложений во множестве встречаются цепочки зависимостей, при которых, чтобы приступить к действию B, нужно сначала выполнить действие A. Соответственно, в этой последней категории рассматривается, насколько хорошо ЦП может выполнить последовательность зависимых инструкций. Для полноты картины отмечу, что существуют чрезвычайно параллельные (massively parallel) приложения, в которых небольшие последовательные участки сменяются большими параллельными. Задачи такого рода ограничиваются лишь пропускной способностью при выполнении, но не задержкой.

Внимательный читатель может правомерно провести здесь параллели с нисходящей методологией анализа производительности, и это верно. Ниже я приведу TMA-метрики, соответствующие каждой из 4 категорий.

• Предсказуемость кода (неправильные допущения)

• Пропускная способность при выполнении (ограничено фронтендом, ограничено бэкендом, устаревание)

• Предсказуемость данных (ограничено памятью)

• Задержка при выполнении (ограничено бэкендом)

Давайте подробнее разберём каждую из этих категорий.

Предсказуемость кода

• Определение: насколько качественно ЦП способен предсказывать поток управления в программе (прогнозирование ветвлений).

• В идеале: результат выполнения каждой ветки правильно предсказывается в 100% случаев сразу после того, как программа свернула на данную ветку.

• Хуже всего: алгоритмы с высокой энтропией, дающие поток управления, в котором не прослеживается явного паттерна — например, получаются случайные числа.

• Современное состояние: сегодня наиболее совершенными среди предикторов считаются TAGE‑подобные [Seznec] или основанные на перцептронах [Jimenez]. Рассмотренные здесь предикторы ветвлений ошибаются не более 3 раз на 1000 инструкций. Современные ЦП, как правило, достигают свыше 95% точности прогнозирования на большинстве рабочих нагрузок.

• Улучшения на уровне программы: пользуйтесь неветвящимися алгоритмами (таблицы поиска, предикация, так далее), заменяя ими те ветвления, которые часто прогнозируются неверно. Уменьшите общее количество веток.

• В будущем: в большинстве программ повышение качества прогнозирования едва ли серьёзно улучшит ситуацию, так как прогнозирование уже сейчас довольно качественное. В программах, содержащих сложно прогнозируемые ветвления, можно кое‑что сделать. Во‑первых, программное прогнозирование ветвлений, как в [Whisper], можно в определённых случаях перенести на аппаратный уровень. Во‑вторых, возможен гибридный подход, при котором наряду со стандартным предиктором используется отдельный движок (обучается оффлайн), обрабатывающий лишь те ветвления, которые плохо поддаются прогнозированию [BranchNet].

Пропускная способность при выполнении

• Определение: насколько хорошо инструкции продвигаются по конвейеру ЦП. Здесь учитываются такие операции как выборка, обнаружение независимых инструкций (также называемое «извлечение параллелизма»), а также распараллеливание выдачи и выполнения инструкций. От ширины конвейера ЦП зависит, сколько независимых инструкций процессор может выполнить на одном такте.

• В идеале: с аппаратной точки зрения в идеале нужно иметь бесконечно широкую микроархитектуру с неограниченной возможностью неупорядоченного выполнения и бесконечным количеством блоков выполнения. С программной точки зрения в идеале нужно добиваться, чтобы приложение достигало максимальной теоретически возможной пропускной способности («потолка») на данной машине.

• Хуже всего: алгоритмы с очень низким показателем параллелизма на уровне инструкций (ILP), недоиспользующие вычислительные возможности данной машины.

• Современное состояние: часто наблюдаются пробуксовки из‑за нехватки ресурсов для выполнения программ. Очень сложно спрогнозировать, какой именно ресурс в конвейере ЦП окажется узким местом для конкретного приложения. Пролить на это немного света можно, изучив информацию с разных счётчиков, но более универсальный подход — использовать нисходящий анализ. Машины с функцией неупорядоченного выполнения (OOO) очень хорошо извлекают параллелизм, хотя, и у них есть слепые пятна. Они легко схыватывают «локальный» параллелизм, наблюдаемый посреди цикла или функции, но не находят глобального параллелизма, например:

foo(); // большая невстроенная функцтя
bar(); // bar не зависит от foo

Если процессор будет перемежать выполнение foo и bar, то программа существенно ускорится, но в настоящее время ЦП выполняют такой код последовательно. Некоторое пересечение при выполнении возможно, когда foo заканчивает работу, а bar только начинает. Честно говоря, можно было бы распараллелить выполнение  foo и bar, если, например, порождать новый поток для bar.

Ширина современных архитектур варьируется от 4 до 8. Увеличить ширину машины очень дорого, поскольку придётся одновременно расширять все звенья конвейера ЦП — только так машина останется сбалансированной. В настоящее время всё сложнее проектировать расширенные таким образом архитектуры, поэтому на практике создать такую расширенную систему почти невозможно.

• Улучшения на уровне программы: чтобы достичь потолка производительности на конкретной машине, нужно убедиться, что ЦП легко обнаруживает параллелизм в вашей программе. В настоящее время компиляторы справляются с большинством простых случаев самостоятельно, поэтому обычно не приходится переставлять строки кода, чтобы добиться более качественного планирования инструкций. Есть и более сложные случаи. Например, если (как показано выше) выполнение функций foo и bar частично перекрывается, то придётся вручную размотать обе функции и организовать их выполнение бок о бок. Но в таком случае вы можете израсходовать все доступные регистры, что повлечёт опорожнение и повторное заполнение ячеек памяти (это плохо скажется на производительности, но в некоторых случаях всё‑таки бывает оправдано).

• В будущем: ещё пару лет ширина современных процессоров будет расширяться, но, в конце концов, будет достигнут предел. На то есть три основные причины. Во‑первых, среди всех программ очень мало чрезвычайно параллельных, поэтому бессмысленно делать сверхширокий конвейер. Действует эмпирическое правило: в типичном коде средний показатель ILP равен 2, то есть, в любой конкретный момент можно параллельно выполнять 2 инструкции. Вторая причина связана с управлением сложностью и поддержанием машины в том сбалансированном состоянии, которое мы обсуждали выше. В‑третьих, уже есть хорошие решения для работы с чрезвычайно параллельным софтом: это видеокарты (GPU) и другие ускорители.

Предсказуемость данных

• Определение: насколько хорошо ЦП может скрывать задержку при обращениях к памяти, заранее предвыбирая нужные данные.

• В идеале: последовательные обращения к памяти.

• Хуже всего: произвольный доступ к памяти (например, обращения к хеш‑картам, гистограммам), с вытеснением тех данных, которые будут переиспользоваться позже (например, перебор большого датасета). А также ситуация, когда ядра ЦП конкурируют за пространство кэшей L2/L3, вызывая пробуксовку кэшей друг друга.

• В настоящее время: задержка в кэшах L1, L2 и L3 не снижается, но их размеры растут. Но большой кэш не решает всех программ. Да, он помогает не вытеснять те данные, которые можно будет использовать позднее, но против произвольных обращений к памяти он бессилен.

• Улучшения на уровне программы: преобразовывать компоновку данных, преобразовывать циклы (блокирование, чередование, так далее), упаковка данных, избегание пробуксовок кэша, прогрев кэша, так далее

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

Существует революционная идея PIM (обработка в оперативной памяти), в соответствии с которой некоторые вычисления (например, memset, memcpy) переносятся ближе к фактическому местоположению данных. Идеи в этой области варьируются от применения специализированных ускорителей до вычислений непосредственно в DRAM. Основная преграда здесь заключается в том, что при принятии новой модели программирования для таких устройств придётся переписывать код приложений. [PIM]

Кроме того, есть несколько идей о том, как умнее организовать предвыборку на аппаратном уровне. Например, [Pythia] при помощи обучения с подкреплением ищет паттерны в сохранившейся в памяти истории запросов к различным адресам, чтобы на основе этой информации генерировать запросы на предвыборку. [Hermes] пытается спрогнозировать, какие обращения к памяти приведут к промахам в кэше и поэтому заранее инициирует обращения к DRAM.

Цепочки зависимостей в данных

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

• В идеале: идеального случая здесь нет, поскольку в общем случае невозможно ускорить обработку данных, полноценно зависящих друг от друга. С программной точки зрения чрезвычайно параллельные приложения, в которых зависимостей мало (и они короткие) — это практически идеал.

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

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

• Улучшения на уровне программы: иногда удаётся разбить на части избыточные цепочки зависимостей в данных или перемежать выполнение разных цепочек. Если это не получается сделать, то лучше всего будет устранить любые вычисления, которые могут помешать ЦП при выполнении длинной цепочки зависимостей.

• В будущем: сложно сказать, следует ли в будущем ожидать серьёзного увеличения тактовой частоты процессора, несмотря на исчерпание закона масштабирования Деннарда. По этому поводу ведутся жаркие дискуссии, а я не инженер‑электронщик, чтобы иметь обоснованное мнение на этот счёт. Есть одна интересная идея по поводу ускорения цепочек зависимостей данных, которую я называю «прогнозирование значения». Речь о том, чтобы предсказывать результаты выполнения определённых инструкций примерно таким же образом, как мы предсказываем ветвления. Если некая инструкция много раз подряд возвращает одно и то же значение, то с высокой степенью уверенности можно предположить, что и в следующий раз мы получим такое же значение. Такое допущение позволит разорвать цепочку зависимостей и начать выполнение с середины. Нельзя подобным образом предугадать результат выполнения каждой инструкции, поэтому здесь, конечно же, нужно действовать очень разборчиво. Кроме того, для воплощения такой идеи потребуется серьёзно изменить движок неупорядоченного выполнения, из‑за чего разработчики аппаратной части не горят желанием реализовывать эти функции на реальном железе. [Perais] [Seznec].

Заключительные мысли

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

Цепочки зависимостей данных — это наиболее труднопреодолимое узкое место. С архитектурной точки зрения современные ЦП мало что могут с этим сделать. Движки для неупорядоченного выполнения инструкций, используемые в большинстве современных процессоров, бесполезны при наличии длинной цепочки зависимостей — например, когда мы обходим связный список, это ещё называется «погоней за указателем». Притом, что можно повлиять на другие категории задержек (улучшить прогнозирование ветвлений, реализовать более умные аппаратные механизмы предвыборки, расширить конвейер инструкций), пока в современных архитектурах не удаётся как следует справляться с ситуациями «сначала запись, потом чтение» (так называемые «истинные» зависимости данных).  

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

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