Оптимизация гнезда циклов
 | Эта статья нуждается в дополнительных цитатах для проверки . ( январь 2021 г. ) |
В информатике и особенно в компиляторов проектировании оптимизация гнезд циклов (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;
for (i = 0; i < n; i++) {
c[i] = 0;
for (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;
for (i = 0; i < n; i += 2) {
c[i] = 0;
c[i + 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 i, j, k;
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
C[i][j] = 0;
for (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;
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[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;
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[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 < N/баланс
система памяти машины будет поддерживать операции с плавающей запятой, и код будет работать с максимальной производительностью. Кэш-память 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)
{
if (kk == 0)
acc00 = acc01 = acc10 = acc11 = 0;
else
{
acc00 = C[i + 0][j + 0];
acc01 = C[i + 0][j + 1];
acc10 = C[i + 1][j + 0];
acc11 = C[i + 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[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. Это повысит способность процессора одновременно выполнять множество инструкций, и есть большая вероятность, что он не сможет обеспечить полную пропускную способность кэша уровня 2.
- Снова заблокируйте циклы, снова для размеров кэша уровня 2. Имея в общей сложности три уровня блокировки (для файла регистра, для кэша L1 и кэша L2), код минимизирует требуемую пропускную способность на каждом уровне иерархии памяти . К сожалению, дополнительные уровни блокировки повлекут за собой еще больше накладных расходов на циклы, что для некоторых размеров проблем на определенном оборудовании может занять больше времени, чем любые недостатки в способности оборудования передавать потоковые данные из кэша L2.
Вместо того, чтобы специально настраивать один конкретный размер кэша, как в первом примере, алгоритм, не учитывающий кэш, предназначен для использования любого доступного кэша, независимо от его размера. При этом автоматически используются преимущества двух или более уровней иерархии памяти, если они доступны. независящие от кэша алгоритмы умножения матриц Известны .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Стивен Мучник; Мучник и партнеры (15 августа 1997 г.). Расширенная реализация проекта компилятора . Морган Кауфманн. ISBN 978-1-55860-320-2 .
укладка плитки.
- ^ Жоао член парламента Кардозу; Педро К. Динис (2 апреля 2011 г.). Методы компиляции для реконфигурируемых архитектур . Springer Science & Business Media. ISBN 978-0-387-09671-1 .
Дальнейшее чтение
[ редактировать ]- Вульф, М. Дополнительные сведения о мозаике итерационного пространства . Суперкомпьютеры'89, страницы 655–664, 1989.
- Вольф М.Э. и Лам М. Алгоритм оптимизации локальности данных . PLDI '91, страницы 30–44, 1991.
- Иригоин Ф. и Триоле Р. Разделение суперузлов . POPL '88, страницы 319–329, 1988.
- Сюэ, Дж. Разбиение циклов для параллелизма . Академическое издательство Клювер. 2000.
- М. С. Лам, Э. Э. Ротберг и М. Е. Вольф. Производительность кэша и оптимизация заблокированных алгоритмов . В материалах 4-й Международной конференции по архитектурной поддержке языков программирования и операционных систем, страницы 63–74, апрель 1991 г.
Внешние ссылки
[ редактировать ]- Результаты тестов потоков , показывающие общий баланс между операциями с плавающей запятой и операциями с памятью для множества разных компьютеров.
- «CHiLL: составная структура преобразования цикла высокого уровня» [ постоянная мертвая ссылка ]
| Базы данных органов управления : Национальные |
|---|
