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

در علوم رایانه، شکافت حلقه (توزیع حلقه) یک بهینه‌سازی کامپایلر است که در آن یک حلقه به چندین حلقه در همان محدوده شکسته می‌شود و هر یک از حلقه‌ها تنها بخشی از بدنهٔ حلقهٔ اصلی را در شامل می‌شود.^[۱][۲] هدف از تجزیه‌کردن یک حلقهٔ بزرگ به چندین حلقهٔ کوچک‌تر، دستیابی به استفادهٔ بهتر از مکان مرجع است. این بهینه‌سازی، در پردازنده‌های چند هسته‌ای بسیار کارآمد است به این صورت که می‌تواند یک کار را به چندین کار برای پردازنده‌ها تقسیم کند.

در عوض، ادغام حلقه (متراکم کردن حلقه) یک بهینه‌سازی کامپایلر و دگرگونی حلقه است که چندین حلقه را با یک حلقه جایگزین می‌کند.^[۲][۳] این امکان وجود دارد که دو حلقه در یک محدوده تکرار شوند و هر یک داده‌های دیگری را ارجاع ندهند. ادغام حلقه همیشه سرعت زمان اجرا (run-time) را بهبود نمی‌بخشد. در بعضی از معماری‌ها، ممکن است دو حلقه بهتر از یک حلقه عمل کنند زیرا، برای مثال، در هر حلقه مکان داده افزایش یافته‌است.

شکافت یا توزیع حلقه، جدا کردن دستورات یک حلقه است که دستورات جدا شده از یکدیگر مستقل هستند.

شکافت حلقه

فرم کلی شکافت حلقه در زبان 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 اجرا نمی‌شود.

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

منابع

1. CRC Press (۳ اکتبر ۲۰۱۸). «The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition».
2. Optimizing Compilers for Modern Architectures: A Dependence-based Approach.
3. Morgan Kaufmann (۱۵ اوت ۱۹۹۷). «Advanced Compiler Design Implementation».
4. «3.7.2 Loop Fusion (Sun Studio 12: C User's Guide)». docs.oracle.com. دریافت‌شده در ۲۰۲۰-۰۲-۰۱.
5. «Loop Fusion». compileroptimizations.com. دریافت‌شده در ۲۰۲۰-۰۲-۰۱.