دنیای موازی: جهانی پر از پردازش‌های موازی!

به قلم نوید نصیری، ورودی 1402 ارشد مهندسی کامپیوتر صنعتی اصفهان
بازنگری‌شده توسط مهدی قاسمی، ورودی 99 کارشناسی مهندسی کامپیوتر صنعتی اصفهان

مقدمه

دنیا، دنیای پردازشه! پردازش‌ها هم روز به‌ روز دارن سنگین‌تر میشن! پردازش سنگین یعنی زمان‌بر شدن. زمان‌بر شدن یعنی صبر و حوصله برای انسان عجول و بی‌حوصله امروزی تا بتونه یه پردازش‌ رو انجام بده و نتیجش رو ببینه. اما انسان امروزی، دست رو دست نمیذاره و میره سراغ بالا بردن سرعت پردازش به کمک هر روشی!

بله درسته به هر روشی. اول که یه هسته پردازنده داشته، شروع میکنه به بالا بردن سرعت کلاک و طراحی الگوریتم‌هایی در سطح معماری و مدار منطقی (مثل الگوریتم Carry Look Ahead که سرعت جمع دو عدد رو بسیار افزایش داد) که بتونه محاسبات و پردازش خودش رو سریع‌تر انجام بده. بعد می‌بینه فایده نداره، میاد چند تا هسته پردازشی میذاره کنار هم تا باهم کار کنند و پردازش انجام بدن. ولی به همینجا ختم نمیشه و هنوز سرعت بالاتر میخواد. کامپیوتر‌های چند هسته‌ای رو کنار هم میذاره و با تشکیل کلاستر، بر روی چندین پردازنده قوی روی چندین کامپیوتر، پردازش خودش رو انجام میده! اینجاست که اهمیت پردازش موازی مشخص میشه.

مگه میشه حرف از پردازش موازی بشه و سخنی از gpu نیاد وسط! اگر الان روی یه لپ‌تاپ که گرافیک RTX داشته باشه دارین این متن رو میخونین، احتمالا حدود ۶۰۰۰ تا هسته پردازشی روی گرافیکتون هست که دارن همشون باهم صفحه نمایش و گرافیک لپ‌تاپتون رو پردازش می‌کنن!

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

چیا موازی میشن؟

خب دیگه مقدمه بسه!

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

هسته‌ها چطور با هم حرف می‌زنند؟

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

الف) حافظه مشترک‌ (Shared Memory)

توی این حالت بین اون تعداد از پردازنده‌ها که میخوان با هم ارتباط داشته باشن، یه متغیر مشترک در یک حافظه مشترک تعریف میشه که با استفاده از اون، با هم داده رد و بدل می‌کنند.

فهمیدیم که برای موازی اجرا کردن، نیاز هست که موازی کد زده بشه! یعنی یه طوری کد زده بشه که هم سیستم‌عامل و هم سخت‌افزار متوجه اون بشه! خب برای این کار یک‌سری ابزار‌ها و کتابخونه‌هایی هستند که بهمون کمک می‌کنند. یکی از کتابخونه‌ها که اتفاقا به روش Shared Memory ارتباط بین هسته‌ها رو فراهم می‌کنه، OpenMP هست. با این کتابخونه می‌تونین تجربه کد زدن موازی به این روش رو توی زبان‌های C و C++ پیدا کنین.

ب) ارسال پیام (Message Passing)

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

برای این حالت از کد‌نویسی موازی هم کتابخونه‌هایی توی C و C++ هست که استفاده می‌شن. یکی از معروف‌ترینشون کتابخونه MPI هست. با این کتابخونه میشه از یک هسته پردازشی به هسته دیگه پیام مورد نظر رو انتقال داد. به این صورت که هر زمان که پردازنده دریافت‌کننده نیاز به گرفتن داده از یک پردازنده دیگه داره، منتظر گرفتن داده از پردازنده مورد نظر می‌مونه و بعد از دریافت پیام، به کار خودش ادامه میده و از اون داده استفاده می‌کنه. البته این کتابخونه توی همین داد و ستد ساده پیام، کلی قابلیت جالب بهمون میده که می‌تونین توی مستنداتش بخونین.

چقدر سریع‌تره؟

و اما زمانی که میایم سراغ پردازش‌های موازی،‌ نیاز هست که علاوه‌بر مواردی که تا الان گفته شد، الگوریتمی‌ که میخوایم ازش استفاده کنیم هم قابل موازی شدن باشه. بعضی از الگوریتم‌ها ماهیتا متوالی هستند و قابل موازی شدن نیستند چون انجام هر بخش از اون نیازمند انجام کامل بخش قبلش هست، پس نمیشه به صورت موازی اجراش کرد. الگوریتم‌های موازی با استفاده‌ از روش‌های خلاقانه، قابلیت موازی‌سازی برنامه‌ رو ایجاد می‌کنه و سعی می‌کنه تا جایی که ممکنه، برنامه به صورت موازی انجام بشه. این قسمت‌ها معمولا وابستگی کمی به هم دارند و یا اصلا وابستگی ندارند اما در صورت وجود وابستگی، داده‌ها بین پردازنده‌ها قابل انتقال هست. کارایی الگوریتم‌ها معمولا با زمان اجرا و منابع پردازشی مورد استفاده‌شون سنجیده می‌شن. یکی از الگوریتم‌هایی که توی پردازش موازی کاربرد داره و احتمالا باهاش آشنا هستین، الگوریتم تقسیم و غلبه ( Divide and Conquer ) هست. این الگوریتم برای راحت‌تر شدن مسئله، اون رو به بخش‌های کوچیک‌تر تقسیم می‌کنه و بر روی اون‌ قسمت‌ها، عملیات مورد نظرش رو انجام می‌ده و در نهایت قسمت‌های کوچیک‌ رو با هم ادغام می‌کنه. یک مثال خیلی ساده بخوام بزنم، اگر n عدد رو به صورت متوالی بخوایم جمع بزنیم، پیچیدگی زمانی n داره. درحالی که اگر با الگوریتم تقسیم و غلبه و به صورت موازی بخوایم این کار رو انجام بدیم، می‌تونیم توی زمان log n این کار رو انجام بدیم. (چرا؟ :)) همچنین می‌تونین برای مسائل Binary Sort, Quick Sort, Merge Sort, Integer Multiplication, Matrix Inversion, Matrix Multiplication هم الگوریتم‌های موازی رو بررسی کنین.

اما سرعت بالا هزینه داره! :(

به قول یه استادی، هیچ چیزی مجانی نیست…:)

تونستیم با هسته‌های بیشتر سرعت بعضی‌ کار‌ها رو خیلی خیلی ببریم بالا ولی به چه قیمتی؟ خب اولیش که بدیهیه برامون هزینس. هزینه استفاده از چند پردازنده زیاده. اما کار به همینجا ختم نمیشه و تازه چالش‌های پردازش‌های موازی خودشون رو نشون میدن. اینجا چند مورد از چالش‌ها رو صرفا اشاره می‌کنم که توی بازدهی پردازش موازی تاثیر زیادی دارن و هنوز هم به عنوان زمینه‌های تحقیقاتی و مقاله، بازار داغی دارن :)

استفاده از Cache توی پردازنده‌ها می‌تونه در ارتباط بین هسته‌ها موثر باشه؟
زمان پردازنده‌ها چطور با هم هماهنگ باشه؟
ارتباط بین پردازنده‌ها به چه صورتی باشه تا بازدهی بالاتری داشته‌باشن؟
پردازنده‌ها چه زمانی نیاز دارن که با هم در ارتباط باشند و چه زمانی نیاز ندارن؟
هسته‌ها چطور به صورت همزمان عمل کنن؟
چطور از محاسبه‌های تکراری توسط هسته‌ها جلوگیری بشه؟
بار پردازشی چطور به بهترین صورت بین پردازنده‌ها تقسیم بشه؟
و در کل چه راه‌هایی هست که بالاترین بازدهی رو بتونیم با کمترین هزینه، از این موازی‌سازی داشته باشیم؟
و …

یکم کد بزنیم!؟

یکی از کتابخونه‌هایی که بالا‌تر هم معرفی شد و میشه باهاش برنامه نویسی موازی رو تجربه کرد، OpenMP هست. این کتابخونه رو می‌تونین با یه سرچ ساده نصبش کنین و توی زبان C و C++ خیلی راحت استفاده کنین. با این کتابخونه میتونیم مشخص کنیم که کدوم بخش کدمون با چند تا پردازنده به صورت موازی اجرا بشه. مثلا توی نمونه کد پایین، بخش داخل حلقه، با دو تا ترد اجرا میشه. خروجی کد چیه؟ و چرا خروجی کد اینطوریه؟

 #include <stdio.h>
 #include <mpi.h>
 #include <omp.h>
 int main()
 {
         int th_id, num;
         omp_set_num_threads(2);
         #pragma omp parallel for
         for (int i=0; i < 10 ; i++)
         {
                 num = omp_get_num_threads(); 
                 th_id = omp_get_thread_num(); 
                 printf(&quotthread Id : %d/%d Threads, Assigned Loop Index: %d\n&quot, th_id, num, i);
 }
 return 0;
 }

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

 #include <stdio.h>
 #include <mpi.h>
 int main( int argc, char **argv )
 {
 int rank, buf;
 int val = 0;
 MPI_Status status;
 MPI_Init(&argv, &argc);
 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
 /* Process 0 sends and Process 1 receives */
 if ( rank == 0 )
 {
         buf = 123456;
         MPI_Send(&buf, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
         MPI_Recv(&val, 1, MPI_INT, 1, 1, MPI_COMM_WORLD, &status);
         if ( buf * 9 + 7 == val )
         {
                 printf(&quotCalculation is correct :)))\n&quot);
         }
         else
         {
                 printf(&quotCalculation is not correct :(((\n&quot);
         }
         printf(&quot\nRecieved Number from Id 1 is : %d\n&quot, val);
  }
 else if ( rank == 1 )
 {
         MPI_Recv(&buf, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
         printf(&quotReceived number from rank 0 : %d\n&quot, buf);
         val = buf * 9 + 7;
         MPI_Send(&val, 1, MPI_INT, 0, 1, MPI_COMM_WORLD);
 }
 MPI_Finalize();
 return 0;
 }

کلام آخر:)

و در آخر برای اینکه این سرنخ‌هایی که دادم رو ادامه بدین، میتونین یه نگاه به مستندات این کتابخونه‌ها بندازین و با هم مقایسشون کنین و چند تا کد جذاب دیگه هم بزنین. همچنین حیفه درباره CUDA که برای برنامه‌نویسی گرافیک‌های Nvidia استفاده میشه نخونین. و در آخر چند تا کتاب در این زمینه معرفی میکنم که خواستین بخونین و جواب سوالایی که ایجاد شد براتون رو توش پیدا کنین:).