آزمون بانرجی

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

این بدان معنی است که تنها چیزی که آزمون می تواند تضمین کند عدم وجود وابستگی است.

	ضد وابستگی شکسته شده است	وابستگی واقعی شکسته شده است
درست	وجود ندارد ضد وابستگی ها	وجود ندارد وابستگی های واقعی
نادرست	ممکن است وجود داشته باشد یا نباشد ضد وابستگی ها	ممکن است وجود داشته باشد یا نباشد وابستگی های واقعی

فرم کلی

برای یک حلقه از فرم:

    for(i=0; i<n; i++) {
        c[f(i)] = a[i] + b[i]; /* عبارت s1 */
        d[i] = c[g(i)] + e[i];    /* عبارت s2 */
    }

یک وابستگی واقعی بین عبارت s1 و عبارت s2 وجود دارد اگر و فقط اگر :

$\exists i,j\in \left[0,n-1\right]:i\leq j\quad and\quad f\left(i\right)=g\left(j\right)\!$

یک ضد وابستگی بین عبارت s1 و عبارت s2 وجود دارد اگر و فقط اگر :

$\exists i,j\in \left[0,n-1\right]:i>j\quad and\quad f\left(i\right)=g\left(j\right)\!$

برای یک حلقه از فرم:

   for(i=0; i<n; i++) {
        c[i] = a[g(i)] + b[i]; /* عبارت s1 */
        a[f(i)] = d[i] + e[i];    /* عبارت s2 */
    }

یک وابستگی واقعی بین عبارت s1 و عبارت s2 وجود دارد اگر و فقط اگر :

$\exists i,j\in \left[0,n-1\right]:i<j\quad and\quad f\left(i\right)=g\left(j\right)\!$

مثال

نمونه تست بانرجی.

حلقه ای که برای وابستگی آزموده میشود  :

    for(i=0; i<10; i++)  {
        c[i+9] = a[i] + b[i]; /*عبارت s1*/
        d[i] = c[i] + e[i];    /*عبارت s2*/
    }

${Let\ }f(i)=i+9\!$

${Let\ }g(j)=j+0\!$

بنابراین،

${\begin{array}{lcr}a_{0}=9\ ,\ a_{1}=1,\\b_{0}=0\ ,\ b_{1}=1\!\end{array}}$

و

$b_{0}-a_{0}=-9\!$

آزمایش برای ضد وابستگی

$U_{max}=max\left\{a_{1}\times i-b_{1}\times j\right\}{}$ بطوریکه $0\leq j<i<n$

$U_{max}=max\left\{a_{1}\times i-b_{1}\times j\right\}{}$ بطوریکه $0\leq i\leq j<n$

که می دهد:

$U_{max}=9-9=0\!$

$L_{min}=1-0=1\!$

پس، محدودیت ها بر $b_{0}-a_{0}$ هستند :

$1\leq -9\leq 9\!$

واضح است که -9 خارج از کران است ، بنابراین ضد وابستگی شکسته می شود.

تست درستی وابستگی

$L_{min}=min\left\{a_{1}\times i-b_{1}\times j\right\}{}$ بطوریکه $0\leq i\leq j<n$

آنگاه داریم :

$L_{min}=0-9=-9\!$

در حال حاضر، محدودیت ها روی $b_{0}-a_{0}$ هستند :

$-9\leq -9\leq 0\!$

واضح است که -9 داخل کران بدست آمده است ، بنابراین وابستگی واقعی شکسته نمی شود.

نتیجه

از آنجا که ضد وابستگی شکسته شد، می‌توان ادعا کرد که ضد وابستگی بین گزاره‌ها وجود ندارد.

وقتی وابستگی درست (واقعی) نقض نشده است ، نمی دانیم که آیا وابستگی واقعی بین گزاره ها وجود دارد یا خیر.

بنابراین، حلقه قابل موازی سازی است، اما عبارات باید به ترتیب وابستگی واقعی (بالقوه) آنها اجرا شوند.

همچنین ببینید

• تست GCD

منابع

• رندی آلن و کن کندی بهینه سازی کامپایلرها برای معماری های مدرن: رویکردی مبتنی بر وابستگی

• لاستوتسکی، الکس. محاسبات موازی در شبکه های ناهمگن