Кэш и TLB

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

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

• Компонентов исполняемых программ
• Данных, с которыми работают исполняемые программы
• TLB

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

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

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

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

Например, если напрямую запрограммировать операции с матрицами (в частности, умножение матриц), то у них будет очень низкий уровень компактности ссылок. В таких операциях почти всегда требуется перебрать все элементы матрицы по порядку. У каждого компилятора есть свои правила размещения матриц в памяти. Компилятор FORTRAN размещает матрицы по столбцам (то есть, сначала все элементы первого столбца, затем - второго и т.д.). В то же время компилятор C размещает матрицы по строкам. Для матриц небольшого размера все строки и столбцы умещаются в кэше одновременно, так что процессор и математический сопроцессор могут работать с полной скоростью. Однако по мере увеличения размера матрицы компактность ссылок для операций над строками и столбцами снижается, и, в конце концов, хранить данные в кэше становится невозможно. Происходит следующее: если строка матрицы длиннее строки кэша, то в ходе операции над строкой (например, умножения строки на столбец) уже помещенные в кэш элементы строки выбрасываются, а затем снова считываются, но уже с другой позиции. Таким образом, одни и те же данные помещаются в кэш несколько раз.

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

Перед специалистами по численным методам была поставлена задача - создать программы на основе алгоритмов работы с матрицами, использующие технику поблочной выборки и другие способы оптимизации. В результате скорость умножения матриц повысилась в 30 раз. Эти оптимизированные процедуры входят в библиотеку основных функций линейной алгебры (BLAS), /usr/lib/libblas.a. Большое количество оптимизированных процедур содержится в лицензионной программе Engineering and Scientific Subroutine Library (ESSL).

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

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