В этой статье я расскажу о том, как загруженность шины данных влияет на масштабируемость (scalability) приложений. Под масштабируемостью мы будем понимать не только способность многопоточного приложения сокращать свое время выполнения по мере увеличения числа потоков. Мы также добавим сюда и способность однопоточного приложения, запущенного одновременно в несколько копий (instances), выполняться за тот же самый промежуток времени, что и одна копия. Хотя последний пример было бы правильнее охарактеризовать таким свойством как пропускная способность (throughput), так как он относится к «серверному» режиму запуска приложений. Т.е. это такой режим, при котором на сервере запускается однопоточное приложение, каждый раз когда к нему подключается новый клиент. Главная задача при разработке таких приложений — это снижение их зависимости от общих ресурсов, одним из которых может являться шина данных.
Ниже приведена картинка, на которой показано положение шины памяти в системе. Слева изображена схема для «допотопной» архитектуры Core 2, справа для менее старой — Nehalem. Все последующие архитектуры Intel имеют схожую схему с Nehalem (за исключением Intel MIC).
Итак, зачем же нам знать состояние шины во время выполнения приложения? А вот зачем. Иногда бывает так, что программа вроде бы и написана в соответствии с канонами параллельного программирования: и процент однопоточного кода незначителен, и потоки загружены равномерно, и синхронизации почти нет, и прочее, но что-то все равно мешает ей линейно масштабироваться с увеличением числа потоков. В таких случаях специалисты анализируют производительность приложения на архитектурном уровне. На этом уровне можно найти проблемы, характерные для конкретной модели процессора или конфигурации системы. Именно к таким проблемам относится загруженность шины данных.
Давайте, посмотрим, как влияет загруженность шины на масштабируемость. Для этого напишем простую программу, которая в цикле будет читать и писать элементы одномерного массива.
Будем запускать эту программу с разным количеством потоков и разным параметром STEP. Параметр STEP соответствует утилизации КЭШ-линии. Мы помним, что процессор обменивается с памятью порциями по 64 байта, которые называются КЭШ-линиями. Если нам нужно прочитать всего лишь один байт, процессор все равно скачает из памяти 64 байта. Такой обмен данными происходит из-за принципа пространственной локальности. Это первый принцип, который лежит в основе КЭШ. Процессор как бы предполагает, что если мы считали какое-то значение массива из памяти, то на следующем шаге нам понадобиться считать следующее значение из того же массива. Поэтому важно размещать данные как можно ближе друг к другу, чтобы снизить нагрузку на шину. Таким образом, при STEP = 1, утилизация КЭШ-линии составляет 100%, при STEP = 4, утилизация – 25%, STEP = 8, утилизация – 12,5% и при STEP = 64, утилизация – 1,56%. Фактически, последний параметр означает закачивание новой КЭШ-линии на каждой итерации внутреннего цикла.
Еще одно замечание: тестовая программа была собрана компилятором Intel с опцией –no-vec, чтобы получить скалярный код вместо векторного. Это было сделано с целью получения «красивых данных» для облегчения понимания теории.
На этом графике отображено время выполнения нашего приложения в зависимости от тестируемых параметров. Мы видим, что по мере того, как ухудшается утилизации КЭШ-линии (параметр STEP), масштабируемость, т.е. отношение времени для меньшего числа потоков ко времени для большего числа потоков, тоже становится хуже.
Теперь посмотрим, как меняется нагрузка на шину данных в зависимости от тестируемых параметров. Нагрузку мы будем измерять с помощью VTune Amplifer, используя анализ «Bandwidth».
Мы видим, что одновременно с ухудшением масштабируемости нагрузка на шину возрастает. Объяснение здесь простое – потокам всё больше требуется КЭШ линий и в силу ограниченности шины им приходится всё дольше и дольше простаивать в ожидании данных. Это и является причиной ухудшения масштабируемости. Также важно отметить, что значение нагрузки с какого-то момента перестает существенно изменяться и постепенно приближается к некоторому значению, которое называется пиковая нагрузка. В нашем случае пиковая нагрузка равна 19 Гб/сек.
Теперь рассмотрим что такое принцип временной локальности. Это еще один принцип, который лежит в основе КЭШ и говорит он следующее: если мы считали какой-то элемент из памяти, то, скорее всего, мы обратимся к этому элементу еще раз через какое-то время. Для демонстрации этого принципа возьмем самый плохой случай, где утилизация КЭШ-линии составляет 1,56%. Применим для этого случая обход цикла по блокам, не нарушая целостности данных и сохраняя семантику программы.
Такая оптимизация позволяет нам обработать требуемое количество раз данные, которые находятся в КЭШ в текущий момент. После того как данные обработаны, мы сдвигаемся к следующей порции, закачивая их по шине, и повторяем суммирование. Важно отметить, что объем порции соответствует объему КЭШ второго уровня.
Такой подход не только сократил время выполнения приложения, но и что самое важное для нас, существенно улучшил масштабируемость. Эта оптимизация позволила снизить зависимость потоков от общего ресурса, т.е. от шины данных, и переключить их на КЭШ второго уровня, который является собственным ресурсом для каждого ядра, да и к тому же более быстрым. Мы также видим, что загрузка шины стала мизерной.
Итак, для того чтобы улучшить масштабируемость нашего приложения, мы должны использовать один из принципов локальности. А если мы хотим еще и значительно сократить время выполнения, то мы должны использовать оба принципа.
Кто-то скажет, что не рассмотрен случай использования инструкций типа movnti, предназначенных для разгрузки шины, но я отмечу, что об этом мы поговорим в следующей статье.
Теперь давайте ответим на главный вопрос этой статьи: «А как понять, что слабая масштабируемость приложения вызвана именно высокой загрузкой шины данных?».
Для ответа на этот вопрос мы должны проделать следующие шаги используя VTune Amplifer:
- Измерить пиковую нагрузку для шины данных в нашей системе
- Выяснить, как меняется загрузка шины в зависимости от увеличения числа потоков нашего приложения
- Если мы видим, что при увеличении числа потоков, нагрузка на шину быстро достигает пиковых значений (измеренных в п.1), то в этом и кроется причина наших бед (плохой масштабируемости). При этом мы должны понимать, что есть еще другие причины (например false-sharing), которые мы уже проверили.
Для определения пиковой нагрузки возьмем тестовую программу из первого примера с параметром STEP = 64.
На всякий случай рекомендую собирать эту программу без опции межпроцедурного анализа. Ее достаточно будет скомпилировать просто с опцией –O2. Здесь нужно учесть, что размер массивов не должен превышать размер оперативной памяти, иначе на измерения может оказать влияние paging операционной системы. Количество потоков должно быть не меньше количества ядер, а если включен Hyper-Threading, то оно должно быть не больше числа hardware потоков. Число повторений (REPEAT) может быть любым, главное, чтобы тест выполнялся существенное время и VTune выдавал одинаковое значение пропускной способности от запуска к запуску.
А теперь рассмотрим пример из реальной жизни. Возьмем приложение 410.lbm из пакета SPEC CPU2006. Это одна из версий известного метода для решения задач гидродинамики (полное название Lattice Boltzmann Method). Данная версия написана таким образом, чтобы сместить баланс нагрузки с процессора на шину памяти. Запустим приложение на двухсокетном сервере на базе Nehalem и посмотрим на масштабируемость.
Мы видим, что уже на четырех потоках масштабирование ухудшается, а нагрузка на шину существенно возрастает и на восьми потоках она достигает пикового значения. При этом я уже выполнил проверки на другие причины плохой масштабируемости, и они не подтвердились, поэтому я делаю вывод, что именно такая загрузка шины и есть главная причина.
Теперь взглянем на горячий цикл этого приложения.
Мы видим, что в нем нарушен принцип «пространственной локальности», т.е. в 19 массивов записываются модифицированные элементы из массива srcGrid (запись в массив dstGrid с большими смещениями для процессора всё равно, что запись в разные массивы). Самая главная проблема этого приложения – непоследовательная запись с шагом 20 элементов. Такая сложная запись обусловлена специфической структурой данных. Дело в том, что в процессе выполнения приложения один куб трансформируется в другой, и каждый элемент этого куба является структурой из 20 элементов типа double. Т.е. фактически мы имеем дело с массивом структур, хотя явно они не объявлены.
Для того, чтобы сделать запись линейной, нужно применить классическую оптимизацию, которая называется «трансформация массива структур в структуру массивов». О том, как применять эту оптимизацию можно почитать в статье «Optimization Study for Multicores. Muneeb Anwar Khan». После применения оптимизации и разбивки записи на блоки (для улучшения работы hardware prefetcher’ов) мы имеем следующий цикл:
И результат:
Мы видим, что масштабируемость улучшилась благодаря уменьшению нагрузки на шину. Хотя нужно признать что время выполнения приложения в один поток немного увеличилось. Это связано с тем, что при трансформации данных нам пришлось добавить еще 19 массивов для srcGrid, а это увеличило нагрузку на hardware prefetcher. Интересный результат получается при запуске однопоточной версии этого приложения в восемь копий, т.е. в «серверном» режиме. (Приложение было собрано без опций распараллеливания.)
Одновременное выполнение восьми однопоточных копий на восьми ядрах занимает 252 секунды, что меньше чем восемь последовательных запусков многопоточной версии, которые выполняются 8 * 37 = 296 секунды. Это говорит о том, что в многопоточной версии существуют какие-то алгоритмические проблемы, связанные с распараллеливанием. Но это уже другая история.
Автор: nikolai_serdyuk
