В информатике и особенно в проектировании компиляторов оптимизация гнезд циклов (LNO) — это метод оптимизации, который применяет набор преобразований циклов с целью оптимизации локальности или распараллеливания или другого сокращения накладных расходов цикла в гнездах циклов. ( Вложенные циклы возникают, когда один цикл находится внутри другого цикла.) Одним из классических способов использования является уменьшение задержки доступа к памяти или пропускной способности кэша, необходимой из-за повторного использования кэша для некоторых распространенных алгоритмов линейной алгебры .
Техника, используемая для такой оптимизации, называется мозаикой циклов [1] , также известной как блокировка циклов [2] или «разборка и обмен» .
Мозаичное разделение цикла разделяет пространство итераций цикла на более мелкие фрагменты или блоки, чтобы гарантировать, что данные, используемые в цикле, остаются в кеше до тех пор, пока они не будут повторно использованы. Разделение пространства итераций цикла приводит к разделению большого массива на более мелкие блоки, таким образом вписывая элементы массива, к которым осуществляется доступ, в размер кэша, улучшая повторное использование кэша и устраняя требования к размеру кэша.
Обычная петля
для ( я знак равно 0 ; я < N ; ++ я ) { ... } можно заблокировать блоком размера B, заменив его на
for ( j знак равно 0 ; j < N ; j += B ) { for ( я знак равно j ; я < min ( N , j + B ); ++ я ) { .... } } где min()— функция, возвращающая минимум своих аргументов.
Ниже приведен пример умножения матрицы на вектор. Имеется три массива, каждый по 100 элементов. Код не разбивает массивы на меньшие размеры.
int i , j , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; интервал п = 100 ; для ( я знак равно 0 ; я < п ; я ++ ) { c [ я ] знак равно 0 ; для ( j знак равно 0 ; j < n ; j ++ ) { c [ я ] = c [ я ] + а [ я ] [ j ] * b [ j ]; } } После применения мозаики цикла с использованием блоков 2 * 2 код выглядит следующим образом:
int i , j , x , y , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; интервал п = 100 ; для ( я знак равно 0 ; я < п ; я += 2 ) { c [ я ] знак равно 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), могут пересекать строки кэша, вызывая промахи в кэше.
Не всегда легко решить, какое значение размера тайла является оптимальным для одного цикла, поскольку это требует точной оценки областей массива, к которым осуществляется доступ в цикле, и размера кэша целевой машины. Порядок вложений циклов ( loop interchange ) также играет важную роль в достижении лучшей производительности кэша. Явная блокировка требует выбора размера плитки с учетом этих факторов. Напротив, алгоритмы, не учитывающие кэш, предназначены для эффективного использования кэша без явной блокировки.
Многие крупные математические операции на компьютерах в конечном итоге тратят большую часть времени на умножение матриц . Операция:
где A, B и C — массивы размера N×N. Индексы в следующем описании имеют форму C[row][column].
Основной цикл:
int я , j , k ; для ( я знак равно 0 ; я < N ; ++ я ) { для ( j знак равно 0 ; j < N ; ++ j ) { C [ я ][ j ] = 0 ; для ( k знак равно 0 ; k < N ; ++ k ) C [ i ] [ j ] += A [ i ] [ k ] * B [ k ] [ j ]; } } Есть три проблемы, которые нужно решить:
Исходный цикл вычисляет результат для одной записи в матрице результатов за раз. Вычисляя одновременно небольшой блок записей, следующий цикл повторно использует каждое загруженное значение дважды, так что внутренний цикл имеет четыре загрузки и четыре умножения-сложения, тем самым решая проблему №2. Используя одновременно четыре аккумулятора, этот код может держать один сумматор с плавающей запятой с задержкой 4 почти все время занятым (проблема № 1). Однако код не решает третью проблему. (Он также не касается работы по очистке, необходимой, когда N нечетно. Такие детали будут исключены из дальнейшего обсуждения.)
для ( я знак равно 0 ; я < N ; я += 2 ) { для ( j знак равно 0 ; j < N ; j += 2 ) { Acc00 = Acc01 = Acc10 = Acc11 = 0 ; for ( 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 [ я + 0 ][ j + 0 ] = acc00 ; C [ я + 0 ][ j + 1 ] = acc01 ; C [ я + 1 ][ j + 0 ] = acc10 ; C [ я + 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 ( я = ii ; я < ii + ib ; я += 2 ) { акк00 = акк01 = акк10 = акк11 = 0 ; for ( 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 [ я + 0 ][ j + 0 ] = acc00 ; C [ я + 0 ][ j + 1 ] = acc01 ; C [ я + 1 ][ j + 0 ] = acc10 ; C [ я + 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 раз для передач. Пока
система памяти машины будет поддерживать операции с плавающей запятой, и код будет работать с максимальной производительностью. Кэш-память 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 ( я знак равно ii ; я < ii + ib ; я += 2 ) { if ( kk == 0 ) Acc00 = Acc01 = Acc10 = Acc11 = 0 ; еще { acc00 = C [ я + 0 ] [ j + 0 ]; acc01 = C [ я + 0 ] [ j + 1 ]; acc10 = C [ я + 1 ] [ j + 0 ]; acc11 = C [ я + 1 ] [ j + 1 ]; } for ( 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 [ я + 0 ][ j + 0 ] = acc00 ; C [ я + 0 ][ j + 1 ] = acc01 ; C [ я + 1 ][ j + 0 ] = acc10 ; C [ я + 1 ][ j + 1 ] = acc11 ; } } } } В приведенных выше примерах кода не показаны подробности работы со значениями N, которые не кратны коэффициентам блокировки. Компиляторы, выполняющие оптимизацию гнезда циклов, выдают код для очистки границ вычислений. Например, большинство компиляторов LNO, вероятно, отделили бы итерацию kk == 0 от остальных итераций kk, чтобы удалить оператор if из iцикла. Это одна из ценностей такого компилятора: хотя простые случаи такой оптимизации легко закодировать, сохранение правильности всех деталей при репликации и преобразовании кода является процессом, подверженным ошибкам.
Вышеупомянутый цикл достигнет только 80% пиковых провалов в примере системы при блокировке размера кэша L1 16 КБ. В системах с еще более несбалансированной памятью ситуация будет хуже. К счастью, Pentium 4 имеет 256 КБ (или больше, в зависимости от модели) кэш-памяти второго уровня с высокой пропускной способностью, а также кэш-память первого уровня. Есть выбор:
Вместо того, чтобы специально настраивать один конкретный размер кэша, как в первом примере, алгоритм, не учитывающий кэш , предназначен для использования любого доступного кэша, независимо от его размера. При этом автоматически используются преимущества двух или более уровней иерархии памяти, если они доступны. Известны независящие от кэша алгоритмы умножения матриц .
укладка плитки.