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

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

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];