В информатике и, в частности, в проектировании компиляторов , оптимизация вложенных циклов (LNO) — это метод оптимизации, который применяет набор преобразований циклов с целью оптимизации локальности или распараллеливания или другого сокращения накладных расходов циклов вложенных циклов. ( Вложенные циклы возникают, когда один цикл находится внутри другого цикла.) Одним из классических способов использования является уменьшение задержки доступа к памяти или пропускной способности кэша, необходимой из-за повторного использования кэша для некоторых распространенных алгоритмов линейной алгебры .
Метод, используемый для выполнения этой оптимизации , называется циклической мозаикой [1], также известной как блокировка циклов [2] или метод полосовой шахты и обмена .
Циклическая мозаика разделяет пространство итерации цикла на более мелкие фрагменты или блоки, чтобы гарантировать, что данные, используемые в цикле, остаются в кэше до тех пор, пока они не будут использованы повторно. Разделение пространства итерации цикла приводит к разделению большого массива на более мелкие блоки, тем самым подгоняя элементы массива, к которым осуществляется доступ, под размер кэша, улучшая повторное использование кэша и устраняя требования к размеру кэша.
Обычная петля
для ( i = 0 ; i < N ; ++ i ) { ... } можно заблокировать размером блока B, заменив его на
для ( j = 0 ; j < N ; j += B ) { для ( i = j ; i < min ( N , j + B ); ++ i ) { .... } } где min()— функция, возвращающая минимум своих аргументов.
Ниже приведен пример умножения матрицы на вектор. Есть три массива, каждый из которых содержит 100 элементов. Код не разбивает массивы на меньшие размеры.
int i , j , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; для ( i = 0 ; i < n ; i ++ ) { c [ i ] = 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 ; для ( i = 0 ; i < n ; i += 2 ) { c [ i ] = 0 ; c [ i + 1 ] = 0 ; для ( j = 0 ; j < n ; j += 2 ) { для ( x = i ; x < min ( i + 2 , n ); x ++ ) { для ( 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 ; для ( i = 0 ; i < N ; ++ i ) { для ( j = 0 ; j < N ; ++ j ) { C [ i ][ j ] = 0 ; для ( k = 0 ; k < N ; ++ k ) C [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ]; } } Необходимо решить три проблемы:
Исходный цикл вычисляет результат для одной записи в матрице результатов за раз. Вычисляя небольшой блок записей одновременно, следующий цикл повторно использует каждое загруженное значение дважды, так что внутренний цикл имеет четыре загрузки и четыре умножения-сложения, тем самым решая проблему № 2. Перенося четыре аккумулятора одновременно, этот код может держать один сумматор с плавающей точкой с задержкой 4 занятым почти все время (проблема № 1). Однако код не решает третью проблему. (Он также не решает работу по очистке, необходимую, когда N нечетное. Такие детали будут опущены в последующем обсуждении.)
для ( i = 0 ; i < N ; i += 2 ) { для ( 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 умножений-сложений на одну операцию памяти в основной памяти. Машина вроде 2,8 ГГц Pentium 4, выпущенная в 2003 году, имеет немного меньшую пропускную способность памяти и значительно лучшую плавающую запятую, так что она может поддерживать 16,5 умножений-сложений на одну операцию памяти. В результате, код выше будет работать медленнее на 2,8 ГГц Pentium 4, чем на 166 МГц Y-MP!
Машина с более длительной задержкой сложения с плавающей точкой или с несколькими сумматорами потребует больше аккумуляторов для параллельной работы. Легко изменить цикл выше, чтобы вычислять блок 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.)
для ( ii = 0 ; ii < N ; ii += ib ) { для ( j = 0 ; j < N ; j += 2 ) { для ( 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 раз, для передач. Пока
система памяти машины будет поддерживать блок с плавающей точкой, и код будет работать с максимальной производительностью. 16 КБ кэша Pentium 4 недостаточно: если бы вместо этого были выбраны ib=24 и kb=64, то было бы использовано 12 КБ кэша, избегая его полного заполнения, что желательно, поэтому массивы C и B должны иметь некоторое пространство для прохождения. Эти числа находятся в пределах 20% от пиковой скорости процессора с плавающей точкой.
Вот код с kзаблокированным циклом.
для ( ii = 0 ; ii < N ; ii += ib ) { для ( kk = 0 ; kk < N ; kk += kb ) { для ( j = 0 ; j < N ; j += 2 ) { для ( i = ii ; i < ii + ib ; i += 2 ) { если ( kk == 0 ) acc00 = acc01 = acc10 = acc11 = 0 ; иначе { acc00 = C [ i + 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, которые не являются кратными блокирующим факторам. Компиляторы, которые выполняют оптимизацию вложенности циклов, выдают код для очистки краев вычислений. Например, большинство компиляторов LNO, вероятно, отделили бы итерацию kk == 0 от остальных итераций kk, чтобы удалить оператор if из iцикла. Это одно из преимуществ такого компилятора: хотя кодировать простые случаи этой оптимизации просто, сохранение всех деталей корректными по мере репликации и преобразования кода является подверженным ошибкам процессом.
Вышеуказанный цикл достигнет только 80% пиковых флопов в системе-примере при блокировке для размера кэша L1 16 КБ. Он будет работать хуже в системах с еще более несбалансированными системами памяти. К счастью, Pentium 4 имеет 256 КБ (или больше, в зависимости от модели) кэша уровня 2 с высокой пропускной способностью, а также кэш уровня 1. Есть выбор:
Вместо того, чтобы специально настраиваться на один конкретный размер кэша, как в первом примере, алгоритм, игнорирующий кэш , разработан для использования любого доступного кэша, независимо от его размера. Это автоматически использует преимущества двух или более уровней иерархии памяти, если они доступны. Известны алгоритмы, игнорирующие кэш, для умножения матриц .
плитка.