Оптимизация гнезда петель - Loop nest optimization

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

Метод, используемый для этой оптимизации, называется замощение петли,[1] также известный как блокировка петли[2] или же вскрыть шахту и развязку.

Обзор

Мозаика цикла разделяет пространство итераций цикла на более мелкие фрагменты или блоки, чтобы гарантировать, что данные, используемые в цикле, остаются в тайник пока он не будет использован повторно. Разделение пространства итераций цикла приводит к разбиению большого массива на более мелкие блоки, таким образом подгоняя элементы массива, к которым осуществляется доступ, к размеру кеша, улучшая повторное использование кеша и устраняя требования к размеру кеша.

Обычная петля

за (я=0; я<N; ++я) {  ...}

можно заблокировать размером блока B, заменив его на 

за (j=0; j<N; j+=B) {  за (я=j; я<мин(N, j+B); ++я) {    ....  }}

куда мин () - функция, возвращающая минимум своих аргументов.

Пример: умножение матрицы на вектор

Ниже приводится пример умножения матрицы на вектор. Есть три массива, каждый по 100 элементов. Код не разбивает массивы на меньшие размеры.

  int я, j, а[100][100], б[100], c[100];  int п = 100;  за (я = 0; я < п; я++) {    c[я] = 0;    за (j = 0; j < п; j++) {      c[я] = c[я] + а[я][j] * б[j];    }  }

После того, как мы применим мозаику цикла с использованием блоков 2 * 2, наш код будет выглядеть так:

  int я, j, Икс, у, а[100][100], б[100], c[100];  int п = 100;  за (я = 0; я < п; я += 2) {    c[я] = 0;    c[я + 1] = 0;    за (j = 0; j < п; j += 2) {      за (Икс = я; Икс < мин(я + 2, п); Икс++) {        за (у = j; у < мин(j + 2, п); у++) {          c[Икс] = c[Икс] + а[Икс][у] * б[у];        }      }    }  }

Исходное пространство итераций цикла: п к п. Доступный фрагмент массива a [i, j] также п к п. Когда п слишком велик, а размер кеша машины слишком мал, элементы массива, к которым осуществляется доступ, за одну итерацию цикла (например, я = 1, j = от 1 до n) может пересекать строки кэша, вызывая промахи кеша.

Размер плитки

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

Пример: умножение матриц

Многие большие математические операции на компьютерах тратят много времени на выполнение матричное умножение. Операция:

С = А × В

где A, B и C - массивы размером N × N. Нижние индексы для следующего описания имеют форму C [строка] [столбец].

Базовый цикл:

int я, j, k;за (я = 0; я < N; ++я){    за (j = 0; j < N; ++j)    {        C[я][j] = 0;        за (k = 0; k < N; ++k)            C[я][j] += А[я][k] * B[k][j];    }}

Необходимо решить три проблемы:

  • Для завершения добавления с плавающей запятой требуется некоторое количество циклов. Чтобы сохранить сумматор с задержкой нескольких циклов код должен обновить несколько аккумуляторы в параллели.
  • Машины обычно могут выполнять только одну операцию с памятью за умножить-сложить, поэтому загруженные значения необходимо использовать повторно как минимум дважды.
  • Типичная система памяти ПК может выдерживать только одно 8-байтовое двойное слово на 10–30 операций умножения с двойной точностью, поэтому значения, загруженные в кэш, должны использоваться многократно.

Исходный цикл вычисляет результат для одной записи в матрице результатов за раз. При одновременном вычислении небольшого блока записей следующий цикл повторно использует каждое загруженное значение дважды, так что внутренний цикл имеет четыре загрузки и четыре операции умножения-сложения, таким образом решая проблему № 2. Перенося четыре аккумулятора одновременно, этот код может держать один сумматор с плавающей запятой с задержкой 4 занятым почти все время (проблема №1). Однако код не решает третью проблему. (Он также не касается работы по очистке, необходимой, когда N нечетно. Такие детали будут опущены в последующее обсуждение.)

за (я = 0; я < N; я += 2){    за (j = 0; j < N; j += 2)    {        acc00 = acc01 = acc10 = acc11 = 0;        за (k = 0; k < N; k++)        {            acc00 += B[k][j + 0] * А[я + 0][k];            acc01 += B[k][j + 1] * А[я + 0][k];            acc10 += B[k][j + 0] * А[я + 1][k];            acc11 += B[k][j + 1] * А[я + 1][k];        }        C[я + 0][j + 0] = acc00;        C[я + 0][j + 1] = acc01;        C[я + 1][j + 0] = acc10;        C[я + 1][j + 1] = acc11;    }}

В этом коде были я и 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 регистрами с плавающей запятой в ЭТО. Если у ЦП недостаточно регистров, компилятор будет планировать дополнительные загрузки и сохранения, чтобы разлить регистры в слоты стека, что заставит цикл работать медленнее, чем блокированный цикл меньшего размера.

Умножение матриц похоже на многие другие коды в том смысле, что оно может быть ограничено пропускной способностью памяти, и что большее количество регистров может помочь компилятору и программисту снизить потребность в пропускной способности памяти. Этот регистрировать давление вот почему поставщики RISC ЦП, которые намеревались строить машины более параллельные, чем общего назначения x86 и 68000 ЦП, принятая 32-х позиционная с плавающей запятой зарегистрировать файлы.

Приведенный выше код не очень хорошо использует кеш. Во время вычисления горизонтальной полосы результатов C загружается одна горизонтальная полоса A и загружается вся матрица B. Для всего расчета C сохраняется один раз (это хорошо), A загружается в кеш один раз (при условии, что полоса A помещается в кеш с полосой B), но B загружается N / ib раз, где ib - размер полосы в матрице C, всего N3/ 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)    {        за (я = ii; я < ii + ib; я += 2)        {            acc00 = acc01 = acc10 = acc11 = 0;            за (k = 0; k < N; k++)            {                acc00 += B[k][j + 0] * А[я + 0][k];                acc01 += B[k][j + 1] * А[я + 0][k];                acc10 += B[k][j + 0] * А[я + 1][k];                acc11 += B[k][j + 1] * А[я + 1][k];            }            C[я + 0][j + 0] = acc00;            C[я + 0][j + 1] = acc01;            C[я + 1][j + 0] = acc10;            C[я + 1][j + 1] = acc11;        }    }}

С помощью этого кода мы можем установить для ib все, что захотим, и количество загрузок матрицы B будет уменьшено на этот коэффициент. За эту свободу приходится платить: теперь мы храним в кэше кусочки матрицы A размером N × ib. Пока это подходит, этот код не будет ограничен системой памяти.

Так какой размер матрицы подходит? В нашем примере система 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

система памяти машины будет не отставать от блока с плавающей запятой, и код будет работать с максимальной производительностью. Кэш-память Pentium4 16 КБ недостаточно велика: мы могли бы выбрать ib = 24 и kb = 64, таким образом, используя 12 КБ кеш-памяти - мы не хотим заполнять его полностью, поскольку для массивов C и B должно быть какое-то место. протекать. Эти числа находятся в пределах 20% от пиковой скорости процессора с плавающей запятой.

Вот код с циклом k заблокирован.

за (ii = 0; ii < N; ii += ib){    за (кк = 0; кк < N; кк += kb)    {        за (j=0; j < N; j += 2)        {            за (я = ii; я < ii + ib; я += 2)            {                если (кк == 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];                }                за (k = кк; k < кк + kb; k++)                {                    acc00 += B[k][j + 0] * А[я + 0][k];	                acc01 += B[k][j + 1] * А[я + 0][k];	                acc10 += B[k][j + 0] * А[я + 1][k];	                acc11 += B[k][j + 1] * А[я + 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 итерация отключена от остальной части кк итераций, чтобы удалить оператор if из я петля. Это одно из достоинств такого компилятора: несмотря на то, что кодировать простые случаи этой оптимизации несложно, сохранение всех деталей в правильном состоянии при репликации и преобразовании кода - это процесс, подверженный ошибкам.

Вышеупомянутый цикл будет достигать только 80% пиковых ошибок в примере системы при блокировке для размера кэша L1 16 КБ. Он будет хуже работать в системах с еще более несбалансированной памятью. К счастью, Pentium 4 имеет 256 КБ (или больше, в зависимости от модели) кэш-памяти уровня 2 с высокой пропускной способностью, а также кеш-память уровня 1. Нам предоставляется выбор:

  • Мы можем настроить размеры блоков для кеша второго уровня. Это подчеркнет способность процессора поддерживать в действии множество инструкций одновременно, и есть большая вероятность, что он не сможет получить полную пропускную способность из кэша уровня 2.
  • Мы можем снова заблокировать циклы, опять же для размеров кэша второго уровня. При наличии трех уровней блокировки (для регистрового файла, для кэша L1 и кеша L2) код минимизирует требуемую полосу пропускания на каждом уровне иерархия памяти. К сожалению, дополнительные уровни блокировки повлекут за собой еще большие накладные расходы на цикл, что для некоторых размеров проблем на некотором оборудовании может потребовать больше времени, чем любые недостатки в способности оборудования передавать данные из кэша L2.

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

Смотрите также

Рекомендации

  1. ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Расширенная реализация проекта компилятора. Морган Кауфманн. ISBN  978-1-55860-320-2. черепица.
  2. ^ Жуан М.П. Кардосо; Педро К. Динис (2 апреля 2011 г.). Методы компиляции реконфигурируемых архитектур. Springer Science & Business Media. ISBN  978-0-387-09671-1.

дальнейшее чтение

  1. Вулф, М. Больше мозаики пространства итераций. Supercomputing'89, страницы 655–664, 1989.
  2. Вольф, М. Э. и Лам, М. Алгоритм оптимизации локальности данных. PLDI '91, страницы 30–44, 1991.
  3. Иригоин Ф. и Триоле Р. Разделение надузлов. POPL '88, страницы 319–329, 1988.
  4. Сюэ, Дж. Замощение петель для параллелизма. Kluwer Academic Publishers. 2000 г.
  5. М. С. Лам, Э. Э. Ротберг и М. Э. Вольф. Производительность кеша и оптимизация заблокированных алгоритмов. В материалах 4-й Международной конференции по архитектурной поддержке языков программирования и операционных систем, страницы 63–74, апрель 1991 г.

внешняя ссылка