الگوریتم‌های چندریسمانی

الگوریتم‌های چندریسمانی (به انگلیسی: Multithreaded Algorithms)  الگوریتمهایی هستند که برای انجام کارهای موازی در روی  رایانهای تک‌پردازنده و چندپردازنده استفاده می‌شوند. الگوریتم‌های سریال برای اجرا روی کامپیوترهای تک‌پردازنده‌ای مناسبند که در آن‌ها در هر لحظه فقط یک دستورالعمل اجرا می‌شود؛ اما الگوریتم‌های موازی قابلیت اجرا بر روی کامپیوترهای چندپردازنده را دارند که به آن‌ها قابلیت اجرای چندین دستورالعمل به صورت هم‌زمان را می‌دهد. برنامه‌نویسی چندریسمانه به دو دسته ایستا، وپویا تقسیم‌بندی می‌شود که در ادامه به توضیح هر کدام می‌پردازیم.

برنامه‌نویسی چندریسمانی ایستا

یک روش معمول برای برنامه نویسی کامپیوترهای موازی با حافظه مشترک استفاده از ریسمان‌سازی ایستا (به انگلیسی: Static Threading) است. که یک تجرید نرم‌افزاری از پردازنده‌های مجازی فراهم می‌کند و ریسمان‌ها از یک حافظه مشترک استفاده می‌کنند. در این روش به هر ریسمان شمارنده برنامه (به انگلیسی: Program Counter) اختصاص می‌دهیم  و به همین دلیل است که می‌تواند مستقل از بقیه ریسمان‌ها کد مربوط به خود را اجرا کند. مدیریت این ریسمان‌ها بر عهده سیستم عامل می‌باشد. به این صورت که سیستم عامل می‌تواند در صورت لزوم هر یک از این ریسمان‌ها را روی پردازنده بارگذاری کند یا آن‌ها را از پردازنده خارج سازد تا ریسمان دیگری روی آن پردازنده شروع به اجرا شود. سیستم عامل به برنامه‌نویس این امکان را می‌دهد که ریسمان‌ها را ساخته یا آن‌ها را از بین ببرد. اما انجام این اعمال ب کندی صورت می‌گیرد. به همین دلیل اکثر اوقات ریسمان‌ها در طول اجرای برنامه ثابت باقی می‌مانند و به همین دلیل به آن‌ها ایستا گفته می‌شود.

برنامه‌نویسی چندریسمانی پویا

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

مبانی چندریسمانی پویا

با بررسی مثالی از محاسبه اعداد دنبالهٔ فیبوناتچی به صورت  بازگشتی به توضیح این قسمت می‌پردازیم. دنبالهٔ فیبوناتچی به صورت زیر تعریف می‌شود:
F(0) = ۰F(1) = ۱F(i) = F(i - 1) + F(i - 2)
اگر بخواهیم جمله n ام سری فیبوناتچی را به دست آوریم می‌توانیم از الگوریتم بازگشتی زیر کمک بگیریم:
FIB(n)If n<= ۱Return nElseX = FIB(n - 1)Y = FIB(n - 2)Return X + Y
محاسبه اعداد فیبوناتچی بزرگ به این روش اصلاً کار مناسبی نیست، چرا که در آن محاسبات تکراری زیادی وجود دارد. برای مثال شکل زیر رویه محاسبه برای(F(6 را نشان می‌دهد.
برای فراخوانی (F(6 باید به‌طور بازگشتی (F(5 و (F(4 را فراخوانی کنیم. از طرفی برای محاسبه(F(5 باید (F(4 محاسبه شود. چون این رویه حاصل Fرا ذخیره نمی‌کند، فراخوانی‌های تکراری را انجام می‌دهد. مرتبه اجرای این الگوریتم نمایی است. در حالیکه با روش برنامه نویسی پویا می‌توانیم الگوریتمی برای محاسبه اعداد فیبوناتچی ارائه دهیم که این کار را در (O(n انجام می‌دهد.
حال با اضافه کردن کلمات کلیدی موازی‌سازی spawn , sync  به شبه کد قبلی، آن را گسترش می‌دهیم تا از محاسبات موازی پشتیبانی کند:
P-FIB(n)If n <= ۱Return nElsex = spawn P-FIB(n - 1)y = P-FIB(n - 2syncreturn x + y
اگر کلمات کلیدی spawn , sync  را از P-FIB  حذف کنیم، شبه کد حاصل دقیقاً مشابه FIB خواهد بود. سریال‌سازی یک الگوریتم چند ریسمانی را به صورت الگوریتم سریالی تعریف می‌کنیم که از حذف کلمات چند ریسمانی به دست می‌آید.

ضرب چند ریسمانی ماتریسها

ماتریسها را می‌توان به صورت عادی با سه حلقه تو در تو در هم ضرب کرد که زمان اجرای آن برابر (O(n3 است:
square-matrix-mult(A,B)n= A.rowslet C be a new n*n matrixparalell for i=1 to nparallel for j=1 to ncij=۰for k=1 to nc[ij]=c[ij]+a[ik]*b[kj]return C
اما برای کاهش زمان اجرای آن می‌توان به روش زیر عمل کرد:
برای ضرب دو ماتریس n*n نیاز به ۸ ضرب ماتریسی n/2*n/2 و یک جمع ماتریسی n/2 * n/2 داریم. به کمک شبه کد زیر با استفاده از موازی‌سازی تو در تو این استراتژی را با روش تقسیم و غلبه پیاده‌سازی می‌کنیم:
P-matrix_mult_recursive1n=A.rows2if n==۱3c[11]=a[1,1].b[1,1]4else5let T be a new n*n matrixpartition A, B, C and T ino n/2*n/2 submatricesA11,A12,A21,A22;B11,B12,B21,B22;C11,C12,C21,C22;T11,T12,T21,T22;6spawn P-matrix_mult_recursive(C11,A11,B11)7spawn P-matrix_mult_recursive(C12,A11,B12)8spawn P-matrix_mult_recursive(C21,A21,B11)9spawn P-matrix_mult_recursive(C22,A21,B12)10spawn P-matrix_mult_recursive(T11,A12,B21)11spawn P-matrix_mult_recursive(T21,A12,B22)12spawn P-matrix_mult_recursive(T21,A22,B21)13P-matrix_mult_recursive(T22,A22,B22)14sync15parallel for i=1 to n16parallel for j=1 to n17c[i,j]=c[i,k]+t[i,j]
خط ۳ حالت پایه را بیان می‌کند که شرط خروج از تابع بازگشتی است. حالت بازگشتی در خطوط ۴ تا ۱۷ اداره می‌شود. در خط ۴ یک ماتریس موقتی T در حافظه تخصیص داده می‌شود و خط ۵ هر یک از ماتریس‌های A,B,C,T را به زیر ماتریس‌هایی با اندازه n/2*n/2 تقیسم می‌کند.