Слияние циклов

Слияние циклов (объединение циклов, англ. loop fusion, англ. loop jamming) — оптимизация компилятора, выполняющая объединение нескольких циклов, смежных в дереве циклов, в один. Преобразование возможно, если циклы имеют одинаковое количество итераций и не зависят друг от друга по данным. Слияние циклов может повысить локальность данных[1] [2], что повышает эффективность работы кэша.

Слияние циклов не всегда сокращает время исполнения программы. На некоторых архитектурах может оказаться более выгодным исполнить два цикла вместо одного объединённого, так как, например, локальность данных в таком случае может оказаться выше. В таких случаях, может применяться обратная оптимизация, разложение циклов, которая расщепляет один цикл на несколько.

Примеры

 
int i, a[100], b[100];
for (i = 0; i < 100; i++)
	a[i] = 1;                     
for (i = 0; i < 100; i++)
	b[i] = 2;

эквивалентно:

int i, a[100], b[100];
for (i = 0; i < 100; i++)
{
	a[i] = 1; 
	b[i] = 2;
}

Примечания
  1. Manjikian, N., Abdelrahman, T.S. Fusion of loops for parallelism and locality
  2. Штейнберг Б.Я., Штейнберг О.Б., Василенко А.А. Слияние циклов для локализации данных

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.