برداری‌سازی خودکار

برداری‌سازی خودکار، یک روش بهینه‌سازی کامپایلر است که در آن بهینه‌سازی بر روی آرایه (ساختمان داده‌ها)‌ها صورت می‌گیرد. این روش با موازی‌سازی عملیات بر روی آرایه‌ها باعث می‌شود که سرعت برای حلقه‌های خاصی بسیار بهبود می‌یابد. برای مثال فرض کنید که قرار است دو بردار را با هم جمع کنید. در این حالت حلقه‌ای داریم که پارامترهای متناظر دو بردار را با هم جمع می‌کند. حال از آن‌جا که پارامترهای مختلف هر بردار بر روی هم تأثیری نمی‌گذارند می‌توان تمام این عملیات جمع کردن را با هم انجام داد و آن را از حالت سری که در حلقه وجود دارد می‌توان خارج کرد. برای مثال اگر فضای برداری ما ۴ بعدی باشد عملاً مجموع دو بردار به صورت زیر پیاده‌سازی می‌شود.

${\displaystyle }$

حال اگر همین مثال بالا را بخواهیم برای فضای برداری n بعدی پیاده‌سازی کنیم باید از حلقه استفاده کنیم و می‌توانیم به روشی که در پایین اشاره شده‌است بسنده کنیم.

for (i=0; i<n; i++)
    c[i] = a[i] * b[i];

کامپایلری که در آن برداری‌سازی خودکار انجام شود کد بالا را به صورت سری انجام نمی‌دهد زیرا برای i و j متفاوت دو مجموع عملاً تأثیری بر روی هم ندارند و کامپایلر براساس قدرت پردازشی دستگاه خود می‌تواند به صورت موازی با هم جمع کند.

پیش زمینه

رایانه‌های اولیه تمام عملیات‌های خود را به صورت سری انجام می‌دادند به عبارتی در هر واحد زمانی یک کار انجام می‌دادند. با گذشت زمان رایانه‌ها این قابلیت را پیدا کردند که چند کار را در یک واحد زمانی انجام دهند و از ان زمان مسئله موازی‌سازی مطرح بود. کامپایلرها نیز ازین قاعده مستثنا نبودند و به سمت موازی‌سازی رفته‌اند که یکی از این روش‌ها برداری‌سازی خودکار است.

Intel's MMXو SSEو AVX و AltiVec و ARM's NEON از این نوع خودکارسازی پشتیبانی می‌کنند.

تضمین

مانند هر بهینه‌سازی دیگر اهمیت زیادی دارد که بهینه‌سازی انجام شده باعث به وجود آمدن خطا در پاسخ نشود. روش برداری‌سازی خودکار از حساس‌ترین روش‌ها به این آفت است. در پایین دو مورد از خطاهایی که ممکن است با آن مواجه شویم را آورده‌ایم.

وابستگی داده‌ها

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

دقت داده‌ها

ممکن است متغیرهای موجود در بردارها از نوع متفاوتی باشند و ممکن است در انجام عملیات‌های مجبور باشیم بعضی از آن‌ها را به هم تبدیل کنیم و برای همین موازی‌سازی می‌تواند باعث به وجود آمدن خطا در داده‌ها شود.

وابستگی داده‌ها

همان‌طور که در بخش قبل گفتیم اولین مرحله در روش برداری‌سازی خودکار پیدا کردن وابستگی بین داده هاست. به عبارتی نباید دو دو خط از حلقهٔ مورد نظر که به هم مرتبطند را هم‌زمان انجام دهیم برای مثال:

for (i = 0; i < 128; i++) {
  a[i] = a[i+1];
  a[i] = a[i-1];
}

در مثال بالا همان‌طور که می‌بینیم اگر دو جملهٔ متوالی را بخواهیم به صورت موازی با هم انجام دهیم به نتیجهٔ غلطی می‌رسیم.

پس بنا بر مثالی که در بالاتر دیدیم وابستگی داده‌ها اهمیت زیادی دارد و با ساخت درخت وابستگی و انجام الگوریتم‌های مشخص می‌توانیم این موازی سازی‌ها را انجام دهیم.

زمان اجرا در مقابل زمان کامپایل

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

int a[128];
int b[128];
// initialize b

for (i = 0; i<128; i++)
  a[i] = b[i] + 5;

اما لزوماً همهٔ کدها مانند کد بالا را نمی‌توان در زمان کامپایل برداری‌سازی را بر روی آن انجام داد.

برخی از کدها ممکن است در زمان اجرا به هم مرتبط شوند پس نمی‌توان در همان زمان کامپایل گراف وابستگی آن‌ها را به‌طور کامل انجام داد. برای مثال کد زیر کاملاً مشابه کد بالاست با این تفاوت که دو متغیر در زمان اجرا ساخته می‌شوند و در زمان کامپایل قابل تشخیص نیستند.

int *a = malloc(128*sizeof(int));
int *b = malloc(128*sizeof(int));
// initialize b

for (i = 0; i<128; i++, a++, b++)
  *a = *b + 5;
// ...
// ...
// ...
free(b);
free(a);

تکنیک‌ها

دراین جا به یک مثال ساده برای مفهوم شدن نحوهٔ برداری‌سازی ارائه می‌کنیم. این مثال را در نظر بگیرید:

  for (i = 0; i < 1024; i++)
     C[i] = A[i]*B[i];

بر اساس میزان موازی‌سازی که می‌توانیم انجام دهیم برداری‌سازی انجام می‌شود. مثلاً اینجا می‌خواهیم هر سه جمله را به‌طور موازی با هم ضرب کنیم.

  for (i = 0; i < 1024; i+=4)
     C[i:i+3] = A[i:i+3]*B[i:i+3];