تست ب.م.م

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

شرح

آزمون بزرگ‌ترین مخرج مشترک (GCD) آزمایشی است که در تئوری تدوینگر علوم کامپیوتر برای مطالعه بهینه‌سازی حلقه و تجزیه و تحلیل وابستگی حلقه برای آزمایش وابستگی بین عبارات حلقه استفاده می‌شود.

کاربرد

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

بنیاد و پایه

قضیه

یک معادله خطی دیوفانتین

a1 * x1 + a2 * x2 + … + an * xn = c

دارای یک جواب صحیح x1 , x2 , … ,xn می‌باشد اگر بزرگ‌ترین مخرج مشترک (a1,a2,... ,an) بر c تقسیم پذیر باشد.

به عنوان مثال

۲ * x1 -2 * x2 = ۱

GCD (2 ،۲) = ۲ و۱ نمی‌تواند بر ۲ تقسیم شود؛ بنابراین، برای معادله فوق هیچ راه حل عددی وجود ندارد.

تحلیل وابستگی

تجزیه و تحلیل منابع آرایه در زمان کامپایل برای تعیین وابستگی به داده‌ها (اعم از اینکه به یک آدرس نشان دهند یا نه) دشوار است. یک آزمون ساده و کافی برای عدم وجود وابستگی، آزمون بزرگترین مخرج مشترک (GCD) است. این مبتنی بر مشاهده است که اگر یک حلقه حمل شده وابستگی بین [X [a * i + b و [X [c * i + d وجود داشته باشد (جایی که X آرایه است ، a , b ، c و d عدد صحیح هستند ، و i متغیر حلقه است) ، سپس ب.م.م a و c باید بر (d - b) تقسیم شود. فرض این است که حلقه باید نرمال سازی شود - طوری نوشته شود که شاخص / متغیر حلقه از ۱ شروع شود و در هر تکرار ۱ واحد افزایش یابد. به عنوان مثال، در حلقه زیر، a = ۲، b = ۳، c = ۲، d = ۰ و GCD (a، c) = ۲ و (d-b) می‌شود -۳. از آنجا که ۲ بر -۳ تقسیم پذیر نیست، هیچ وابستگی امکان‌پذیر نیست.

for (i=1; i<=100; i++)
{
  X[2*i+3] = X[2*i] + 50;
}

روند

کد حلقه به‌طور کلی:

(++for (int i=0; i<n; i
 }
 ;... = [s1   a[x*i+k
  [s2   ... = a[y*i+m              
                      {

برای تصمیم‌گیری در مورد اینکه آیا وابستگی حلقه ای وجود دارد (دو منبع آرایه به همان مکان حافظه دسترسی دارند و یکی از آنها یک عمل نوشتن است) بین [x * i + k] و [y * i + m]، یکی معمولاً باید معادله را حل کند ^]

x*i1 +k = y*i2+m (Or x*i1 -y*i2 = m -k)

Where 0<=i1, i2 <n and i1 != i2.

اگر (GCD (x، y بر (mk) تقسیم شود، در آن صورت ممکن است وابستگی خاصی در دستور حلقه s1 و s2 وجود داشته باشد. اگر (GCD (x، y بر (mk) تقسیم پذیر نباشد، هر دو عبارت مستقل هستند و می‌توانند به صورت موازی اجرا شوند. به طور مشابه این آزمون برای تمام عبارات موجود در یک حلقه داده شده انجام می‌شود.

یک مثال کد منبع به طور مثال در C به صورت زیر ظاهر می‌شود:

for (int i=0; i<100; i++)
{
  s1 a[2*i] = b[i];
  s2 c[i] = a[4*i+1];
}

GCD (2،۴) می‌شود ۲ و تقسیم شونده ۱ است. از آنجا که ۲ نمی‌تواند ۱ را کامل تقسیم کند (باقی مانده ناصفر)، هیچ وابستگی بین s1 و s2 وجود ندارد و روشهای مختلف تبدیل حلقه دیگر نیز قابل استفاده است.

جستارهای وابسته

منابع

طراحی و اجرای پیشرفته کامپایلر توسط استیون اس موچنیک