В информатике и, в частности, при проектировании компиляторов оптимизация вложений циклов (LNO) - это метод оптимизации, который применяет набор преобразований циклов с целью оптимизации местоположения или распараллеливания или другого сокращения накладных расходов цикла для гнезд циклов. ( Вложенные циклы возникают, когда один цикл находится внутри другого цикла.) Один из классических способов использования - уменьшить задержку доступа к памяти или полосу пропускания кэша, необходимую из-за повторного использования кеша для некоторых распространенных алгоритмов линейной алгебры .
Методика , используемая для получения такой оптимизации называется цикл плиточные , [1] , также известный как петли блокирующего [2] или Разрез и обмена .
Обзор
Мозаика цикла разбивает пространство итерации цикла на более мелкие фрагменты или блоки, чтобы гарантировать, что данные, используемые в цикле, останутся в кэше до тех пор, пока они не будут повторно использованы. Разделение пространства итераций цикла приводит к разбиению большого массива на более мелкие блоки, таким образом подгоняя элементы массива, к которым осуществляется доступ, к размеру кеша, улучшая повторное использование кеша и устраняя требования к размеру кеша.
Обычная петля
for ( i = 0 ; i < N ; ++ i ) { ... }
можно заблокировать размером блока B, заменив его на
for ( j = 0 ; j < N ; j + = B ) { for ( i = j ; i < min ( N , j + B ); ++ i ) { .... } }
где min()
- функция, возвращающая минимум своих аргументов.
Пример: умножение матрицы на вектор
Ниже приведен пример умножения матрицы на вектор. Есть три массива, каждый по 100 элементов. Код не разбивает массивы на меньшие размеры.
int i , j , a [ 100 ] [ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; для ( я = 0 ; я < п ; я ++ ) { с [ я ] = 0 ; для ( j = 0 ; j < n ; j ++ ) { c [ i ] = c [ i ] + a [ i ] [ j ] * b [ j ]; } }
После применения мозаики цикла с использованием блоков 2 * 2 код выглядит так:
int i , j , x , y , a [ 100 ] [ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; для ( я = 0 ; я < п ; я + = 2 ) { с [ я ] = 0 ; с [ я + 1 ] = 0 ; for ( j = 0 ; j < n ; j + = 2 ) { for ( x = i ; x < min ( i + 2 , n ); x ++ ) { for ( y = j ; y < min ( j + 2 , n ); y ++ ) { c [ x ] = c [ x ] + a [ x ] [ y ] * b [ y ]; } } } }
Исходное пространство итераций цикла - n на n . Доступный фрагмент массива a [i, j] также равен n на n . Когда n слишком велико, а размер кэша машины слишком мал, элементы массива, к которым осуществляется доступ за одну итерацию цикла (например i = 1
, j = 1 to n
), могут пересекать строки кэша, вызывая пропуски кеша.
Размер плитки
Не всегда легко решить, какое значение размера плитки является оптимальным для одного цикла, потому что это требует точной оценки областей массива, к которым осуществляется доступ в цикле, и размера кэша целевой машины. Порядок вложений циклов ( чередование циклов ) также играет важную роль в достижении лучшей производительности кеша. Явная блокировка требует выбора размера плитки на основе этих факторов. Напротив, алгоритмы без учета кеша разработаны для эффективного использования кеша без явной блокировки.
Пример: умножение матриц
Многие большие математические операции на компьютерах в конечном итоге тратят большую часть своего времени на умножение матриц . Операция:
- С = А × В
где A, B и C - массивы N × N. Нижние индексы для следующего описания даны в форме C[row][column]
.
Базовый цикл:
int i , j , k ;for ( i = 0 ; i < N ; ++ i ) { for ( j = 0 ; j < N ; ++ j ) { C [ i ] [ j ] = 0 ; для ( k = 0 ; k < N ; ++ k ) C [ i ] [ j ] + = A [ i ] [ k ] * B [ k ] [ j ]; } }
Необходимо решить три проблемы:
- Для завершения добавления с плавающей запятой требуется некоторое количество циклов. Чтобы сумматор с задержкой в несколько циклов оставался занятым, код должен обновлять несколько аккумуляторов параллельно.
- Обычно машины могут выполнять только одну операцию с памятью на умножение-сложение , поэтому загруженные значения необходимо повторно использовать как минимум дважды.
- Типичные системы памяти ПК могут поддерживать только одно 8-байтовое двойное слово на 10–30 операций умножения с двойной точностью, поэтому значения, загруженные в кэш, должны использоваться многократно.
Исходный цикл вычисляет результат для одной записи в матрице результатов за раз. При одновременном вычислении небольшого блока записей следующий цикл повторно использует каждое загруженное значение дважды, так что внутренний цикл имеет четыре загрузки и четыре операции умножения-сложения, таким образом решая проблему № 2. Имея одновременно четыре аккумулятора, этот код может почти все время держать один сумматор с плавающей запятой с задержкой 4 занятым (проблема №1). Однако код не решает третью проблему. (Он также не касается работы по очистке, необходимой, когда N нечетно. Такие детали не будут включены в последующее обсуждение.)
for ( i = 0 ; i < N ; i + = 2 ) { for ( j = 0 ; j < N ; j + = 2 ) { acc00 = acc01 = acc10 = acc11 = 0 ; для ( k = 0 ; k < N ; k ++ ) { acc00 + = B [ k ] [ j + 0 ] * A [ i + 0 ] [ k ]; acc01 + = B [ k ] [ j + 1 ] * A [ i + 0 ] [ k ]; acc10 + = B [ k ] [ j + 0 ] * A [ i + 1 ] [ k ]; acc11 + = B [ k ] [ j + 1 ] * A [ i + 1 ] [ k ]; } C [ i + 0 ] [ j + 0 ] = acc00 ; C [ i + 0 ] [ j + 1 ] = acc01 ; C [ i + 1 ] [ j + 0 ] = acc10 ; C [ i + 1 ] [ j + 1 ] = acc11 ; } }
В этом коде итерации i
и j
итерации были заблокированы в два раза, и оба результирующих двухитерационных внутренних цикла были полностью развернуты.
Этот код вполне приемлемо работал бы на Cray Y-MP (построенном в начале 1980-х), который может поддерживать 0,8 умножения – сложения на операцию с основной памятью. Такая машина, как Pentium 4 с тактовой частотой 2,8 ГГц, построенная в 2003 году, имеет немного меньшую пропускную способность памяти и значительно лучшую систему с плавающей запятой, так что она может выдерживать 16,5 операций умножения-сложения на операцию с памятью. В результате приведенный выше код будет работать медленнее на Pentium 4 2,8 ГГц, чем на Y-MP 166 МГц!
Машине с большей задержкой добавления чисел с плавающей запятой или с несколькими сумматорами потребуется больше аккумуляторов для параллельной работы. Вышеупомянутый цикл легко изменить, чтобы вычислить блок 3x3 вместо блока 2x2, но результирующий код не всегда быстрее. Цикл требует, чтобы регистры содержали как аккумуляторы, так и загруженные и повторно используемые значения A и B. Блок 2x2 требует 7 регистров. Для блока 3x3 требуется 13, что не будет работать на машине с 8 регистрами с плавающей запятой в ISA . Если у ЦП недостаточно регистров, компилятор будет планировать дополнительные загрузки и сохранения, чтобы разлить регистры в слоты стека, что заставит цикл работать медленнее, чем блокированный цикл меньшего размера.
Умножение матриц похоже на многие другие коды в том смысле, что оно может быть ограничено пропускной способностью памяти, и что большее количество регистров может помочь компилятору и программисту уменьшить потребность в пропускной способности памяти. Это давление регистров является причиной того, почему производители процессоров RISC , которые намеревались строить машины более параллельно, чем процессоры общего назначения x86 и 68000 , приняли файлы регистров с плавающей запятой на 32 элемента .
Приведенный выше код не очень хорошо использует кеш. Во время вычисления горизонтальной полосы результатов C загружается одна горизонтальная полоса A и загружается вся матрица B. Для всего расчета C сохраняется один раз (это хорошо), A загружается в кеш один раз (при условии, что полоса A помещается в кеш с полосой B), но B загружается N / ib раз, где ib - размер полосы в матрице C, всего N 3 / ib двойных слов загружается из основной памяти. В приведенном выше коде ib равно 2.
Следующий шаг по уменьшению трафика памяти - сделать ib как можно больше. Оно должно быть больше, чем число «баланса», сообщаемое потоками. В случае одной конкретной системы Pentium 4 с частотой 2,8 ГГц, используемой в этом примере, значение баланса равно 16,5. Второй пример кода выше не может быть расширен напрямую, так как для этого потребуется гораздо больше регистров-накопителей. Вместо этого цикл блокируется по i. (Технически это на самом деле второй раз, когда i заблокирован, поскольку в первый раз был коэффициент 2.)
for ( ii = 0 ; ii < N ; ii + = ib ) { for ( j = 0 ; j < N ; j + = 2 ) { for ( i = ii ; i < ii + ib ; i + = 2 ) { acc00 = acc01 = acc10 = acc11 = 0 ; для ( k = 0 ; k < N ; k ++ ) { acc00 + = B [ k ] [ j + 0 ] * A [ i + 0 ] [ k ]; acc01 + = B [ k ] [ j + 1 ] * A [ i + 0 ] [ k ]; acc10 + = B [ k ] [ j + 0 ] * A [ i + 1 ] [ k ]; acc11 + = B [ k ] [ j + 1 ] * A [ i + 1 ] [ k ]; } C [ i + 0 ] [ j + 0 ] = acc00 ; C [ i + 0 ] [ j + 1 ] = acc01 ; C [ i + 1 ] [ j + 0 ] = acc10 ; C [ i + 1 ] [ j + 1 ] = acc11 ; } } }
С помощью этого кода для ib можно установить любой желаемый параметр, и количество загрузок матрицы B будет уменьшено на этот коэффициент. За эту свободу приходится платить: N × ib срезов матрицы A хранятся в кэше. Пока это подходит, этот код не будет ограничен системой памяти.
Так какой размер матрицы подходит? В примере системы Pentium 4 с тактовой частотой 2,8 ГГц имеет 16 КБ первичного кэша данных. При ib = 20 срез матрицы A в этом коде будет больше, чем первичный кеш, когда N> 100. Для задач большего размера требуется другой трюк.
Этот трюк заключается в уменьшении размера полосы B-матрицы путем блокировки цикла k, чтобы размер полосы был ib × kb. Блокировка цикла k означает, что массив C будет загружен и сохранен N / kb раз, в общей сложностипередача памяти. B все еще передается N / ib раз, дляпереводы. Пока
- 2 * N / kb + N / ib
система памяти машины будет не отставать от блока с плавающей запятой, и код будет работать с максимальной производительностью. Кэш-память Pentium 4 размером 16 КБ недостаточно велика: если бы вместо этого было выбрано ib = 24 и kb = 64, было бы использовано 12 КБ кеш-памяти, чтобы избежать его полного заполнения, что желательно, поэтому для массивов C и B некоторая комната для протекания. Эти числа находятся в пределах 20% от пиковой скорости процессора с плавающей запятой.
Вот код с k
заблокированным циклом .
for ( ii = 0 ; ii < N ; ii + = ib ) { for ( kk = 0 ; kk < N ; kk + = kb ) { for ( j = 0 ; j < N ; j + = 2 ) { for ( i = ii ; i < ii + ib ; i + = 2 ) { если ( kk == 0 ) acc00 = acc01 = acc10 = acc11 = 0 ; иначе { acc00 = C [ я + 0 ] [ j + 0 ]; acc01 = C [ i + 0 ] [ j + 1 ]; acc10 = C [ i + 1 ] [ j + 0 ]; acc11 = C [ i + 1 ] [ j + 1 ]; } для ( k = kk ; k < kk + kb ; k ++ ) { acc00 + = B [ k ] [ j + 0 ] * A [ i + 0 ] [ k ]; acc01 + = B [ k ] [ j + 1 ] * A [ i + 0 ] [ k ]; acc10 + = B [ k ] [ j + 0 ] * A [ i + 1 ] [ k ]; acc11 + = B [ k ] [ j + 1 ] * A [ i + 1 ] [ k ]; } C [ i + 0 ] [ j + 0 ] = acc00 ; C [ i + 0 ] [ j + 1 ] = acc01 ; C [ i + 1 ] [ j + 0 ] = acc10 ; C [ i + 1 ] [ j + 1 ] = acc11 ; } } } }
В приведенных выше примерах кода не показаны подробности работы со значениями N, которые не кратны блокирующим факторам. Компиляторы, которые выполняют оптимизацию вложенности циклов, генерируют код для очистки границ вычислений. Например, большинство компиляторов ЛНО, вероятно , разделить на кк == 0 итерацию отключения от остальных kk
итераций, чтобы удалить , если заявление от i
цикла. Это одно из достоинств такого компилятора: несмотря на то, что кодировать простые случаи этой оптимизации несложно, сохранение всех деталей в правильном виде при репликации и преобразовании кода - это процесс, подверженный ошибкам.
Вышеупомянутый цикл будет достигать только 80% пиковых ошибок на примере системы при блокировке для размера кэша L1 16 КБ. Он будет хуже работать в системах с еще более несбалансированной памятью. К счастью, Pentium 4 имеет 256 КБ (или больше, в зависимости от модели) кэш-память уровня 2 с высокой пропускной способностью, а также кэш уровня 1. Есть выбор:
- Отрегулируйте размеры блоков для кэша уровня 2. Это подчеркнет способность процессора поддерживать множество инструкций в полете одновременно, и есть большая вероятность, что он не сможет получить полную пропускную способность из кэша уровня 2.
- Снова заблокируйте циклы, снова для размеров кэша 2-го уровня. При наличии трех уровней блокировки (для регистрового файла, для кэша L1 и кеша L2) код минимизирует требуемую полосу пропускания на каждом уровне иерархии памяти . К сожалению, дополнительные уровни блокировки повлекут за собой еще большие накладные расходы на цикл, что для некоторых размеров проблем на некотором оборудовании может потребовать больше времени, чем любые недостатки в способности оборудования передавать данные из кэша L2.
Вместо того, чтобы специально настраиваться на один конкретный размер кеша, как в первом примере, алгоритм без учета кеша предназначен для использования преимуществ любого доступного кеша, независимо от его размера. Это автоматически использует преимущества двух или более уровней иерархии памяти, если они доступны. Известны алгоритмы умножения матриц без учета кеша .
Смотрите также
Рекомендации
- ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Реализация расширенного дизайна компилятора . Морган Кауфманн. ISBN 978-1-55860-320-2.
черепица.
- ^ Жоао МП Кардозу; Педро К. Динис (2 апреля 2011 г.). Методы компиляции реконфигурируемых архитектур . Springer Science & Business Media. ISBN 978-0-387-09671-1.
дальнейшее чтение
- Вулф М. Мор Итерационная мозаика пространства . Supercomputing'89, страницы 655–664, 1989.
- Вольф, М. Е. и Лам, М. Алгоритм оптимизации локальности данных . PLDI '91, страницы 30–44, 1991.
- Иригоин, Ф. и Триоле, Р. Разбиение надузлов . POPL '88, страницы 319–329, 1988.
- Сюэ, Дж. Замощение петель для параллелизма . Kluwer Academic Publishers. 2000 г.
- М. С. Лам, Э. Ротберг и М. Е. Вольф. Производительность кеша и оптимизация заблокированных алгоритмов . В материалах 4-й Международной конференции по архитектурной поддержке языков программирования и операционных систем, страницы 63–74, апрель 1991 г.
Внешние ссылки
- Потоковая передача результатов тестов , показывающих общий баланс между операциями с плавающей запятой и операциями с памятью для множества разных компьютеров.
- «CHiLL: составная структура преобразования контура высокого уровня» [ постоянная мертвая ссылка ]