شکافت و ادغام حلقه

فرم کلی شکافت حلقه در زبان C

    for (i = 0; i <100; i++)
    {
        //code 1
        //code 2
    }

برابر است با:

    for (i = 0; i <100; i++) {
        //code 1
    }

    for (i = 0; i <100; i++) {
        //code 2
    }

یکی از دلایل انجام شکافت حلقه، بهبود دسترسی به حافظه (memory locality یا locality of reference) است. برای مثال در کد زیر، برای بهبود دسترسی به حافظه، دستورهایی که مستقل از هم بوده‌اند، در حلقه‌های متفاوت گذاشته شده‌اند.

مثالی از بهبود دسترسی به حافظه

    for (i = 1 ; i <n ; i++){
a[i] = a[i] + b[i - 1];
b[i] = c[i -1] * x + y;
c[i] = 1 / b[i];
d[i] = sqrt(c[i]);
}

برابر است با:

for (i = 0 ; i <n - 1 ; i++){
b[i + 1] = c[i] * x + y;
c[i + 1] = 1 / b[i + 1];
}
for (i = 0 ; i <n - 1 ; i++)
a[i + 1] = a[i + 1] + b[i];
for (i = 0 ; i <n - 1 ; i++)
d[i + 1] = sqrt(c[i + 1]);

i = n + 1;

اگر دانه‌دانه بودن یک حلقه یا کارهایی که توسط یک حلقه انجام می‌شود، اندک باشد؛ ممکن است افزایش عملکرد از توزیع حلقه (شکافتن حلقه) ناچیز باشد؛ زیرا سربار راه اندازی حلقه موازی در مقایسه با حجم کار حلقه بسیار بیشتر است. در چنین شرایطی، کامپایلر از ادغام حلقه برای ترکیب چندین حلقه به یک حلقه موازی منفرد استفاده می‌کند تا سربار حلقه کاهش یابد و عملکرد زمان اجرا بهبود یابد و در نتیجه دانه‌بندی حلقه را افزایش می‌دهد. زمانی که حلقه‌هایی با تعداد گردش‌های یکسان در مجاورت یکدیگر قرار دارند، ادغام حلقه آسان و ایمن است. مثال زیر را در نظر بگیرید.

/* حلقهٔ موازی کوتاه اول */
for (i=0; i <100; i++) {
    a[i] = a[i] + b[i];
}

/* حلقهٔ موازی کوتاه دوم */
for (i=0; i <100; i++) {
    b[i] = a[i] * d[i];
}

دو حلقهٔ موازی کوتاه در کنار یکدیگر قرار دارند و با خیال راحت می‌توان آن دو را به صورت زیر ترکیب کرد:

/* حلقهٔ موازی بزرگ */
for (i=0; i <100; i++) {
    a[i] = a[i] + b[i];
    b[i] = a[i] * d[i];
}

حلقه جدید نیمی از اجرای موازی حلقه سربار را تولید می‌کند. ادغام حلقه همچنین می‌تواند از روش‌های دیگر کمک کند. به عنوان مثال، اگر همان داده‌ها در دو حلقه ارجاع داده شده باشند، ترکیب آنها می‌تواند باعث بهبود مکان مرجع شود. با این حال، ادغام حلقه همیشه بی خطر نیست. اگر ادغام حلقه وابستگی داده‌ای که قبلاً وجود نداشته باشد را ایجاد کند؛ ممکن است ادغام منجر به اجرای نادرست شود. مثال زیر را در نظر بگیرید:

/* حلقهٔ موازی کوتاه */
for (i=0; i <100; i++) {
    a[i] = a[i] + b[i];
}

/* حلقه کوتاه با وابستگی داده‌ای */
for (i=0; i <100; i++) {
    a[i+1] = a[i] * d[i];
}

مثالی از زبان C

for (i = 0; i <300; i++) {
  a[i] = a[i] + 3;
}

for (i = 0; i <300; i++) {
  b[i] = b[i] + 4;
}

برابر است با:

for (i = 0; i <300; i++)
{
  a[i] = a[i] + 3;
  b[i] = b[i] + 4;
}

ادغام حلقه معمولاً توسط کامپایلرهای زبان C اجرا نمی‌شود.

گرچه ادغام حلقه‌ها باعث کاهش سربار حلقه می‌شود، اما همیشه عملکرد زمان اجرا را بهبود نمی‌بخشد و ممکن است عملکرد زمان اجرا را کاهش دهد. برای مثال، اگر دو آرایه در حلقه‌های مجزا بجای اینکه هر دو به صورت همزمان در یک حلقه مقداردهی شوند، ممکن است کارایی بهتری داشته باشد.