موضوع مقاله: الگوریتم‌های چندریسمانی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم‌های چندریسمانی | مقدمه: الگوریتم‌های چندریسمانی الگوریتمهایی هستند که برای انجام کارهای موازی در روی رایانهای تک‌پردازنده و چندپردازنده استفاده می‌شوند. | ## بخش 1: الگوریتم‌های چندریسمانی | الگوریتم‌های سریال برای اجرا روی کامپیوترهای تک‌پردازنده‌ای مناسبند که در آن‌ها در هر لحظه فقط یک دستورالعمل اجرا می‌شود؛ اما الگوریتم‌های موازی قابلیت اجرا بر روی کامپیوترهای چندپردازنده را دارند که به آن‌ها قابلیت اجرای چندین دستورالعمل به صورت هم‌زمان را می‌دهد. برنامه‌نویسی چندریسمانه به دو دسته ایستا، وپویا تقسیم‌بندی می‌شود که در ادامه به توضیح هر کدام می‌پردازیم. برنامه‌نویسی چندریسمانی ایستا یک روش معمول برای برنامه نویسی کامپیوترهای موازی با حافظه مشترک استفاده از ریسمان‌سازی ایستادهقان طرزه، مقدمه‌ای بر الگوریتم‌ها، ۷۸6. که یک تجرید نرم‌افزاری از پردازنده‌های مجازی فراهم می‌کند و ریسمان‌ها از یک حافظه مشترک استفاده می‌کنند. در این روش به هر ریسمان شمارنده برنامه اختصاص می‌دهیم و به همین دلیل است که می‌تواند مستقل از بقیه ریسمان‌ها کد مربوط به خود را اجرا کند. به این صورت که سیستم عامل می‌تواند در صورت لزوم هر یک از این ریسمان‌ها را روی پردازنده بارگذاری کند یا آن‌ها را از پردازنده خارج سازد تا ریسمان دیگری روی آن پردازنده شروع به اجرا شود. سیستم عامل به برنامه‌نویس این امکان را می‌دهد که ریسمان‌ها را ساخته یا آن‌ها را از بین ببرد. به همین دلیل اکثر اوقات ریسمان‌ها در طول اجرای برنامه ثابت باقی می‌مانند و به همین دلیل به آن‌ها ایستا گفته می‌شود. برنامه‌نویسی چندریسمانی پویا برنامه‌نویسی چندریسمانی پویا به برنامه‌نویس اجازه می‌دهد در کاربردها از موازی‌سازی استفاده کند. با آن‌که کارایی محیط‌های چندریسمانی پویا هنوز در حال تکامل است، اما تقریباً تمام آن‌ها از دو ویژگی پشتیبانی می‌کنند: موازی‌سازی تودرتو و حلقه‌های موازی. موازی‌سازی تودرتو به زیرروال‌ها اجازه می‌دهد که تکثیر شوند که این به معنی ادامهٔ اجرای تابع فراخوانی‌کننده‌است در حالی که زیرروال فراخوانی‌شده هم‌زمان در حال محاسبهٔ نتیجهٔ خود است. یک حلقهٔ موازی، مشابه یک حلقهٔ دستور for معمولی است غیر از این‌که تکرارهای حلقه می‌توانند به‌صورت هم‌زمان اجرا شوند. | ## بخش 2: الگوریتم‌های چندریسمانی | [=صفحات کتاب] برنامه‌نویسی چندریسمانی پویا دارای چندین مزیت مهم به شرح زیر است: این مدل یک گسترش ساده از مدل برنامه‌نویسی سریالی است. تعداد زیادی از چارچوب‌های همزمانی از یکی از نسخه‌های چندریسمانی پویا پشتیبانی می‌کنند. بسیاری از الگوریتم‌های چندریسمانی حاوی موازی‌سازی‌های تودرتو، به‌صورت طبیعی از رویکرد تقسیم و غلبه ناشی می‌شوند. در ضمن، درست همان‌طور که الگوریتم‌های تقسیم و پیش‌روی سریال را می‌توان با استفاده از حل رابطه‌های بازگشتی تحلیل کرد، الگوریتم‌های چندریسمانی نیز به همین‌گونه‌اند. مبانی چندریسمانی پویا با بررسی مثالی از محاسبه اعداد دنبالهٔ فیبوناتچی به صورت بازگشتی به توضیح این قسمت می‌پردازیم. در حالیکه با روش برنامه نویسی پویا می‌توانیم الگوریتمی برای محاسبه اعداد فیبوناتچی ارائه دهیم که این کار را در (O(n انجام می‌دهد. سریال‌سازی یک الگوریتم چند ریسمانی را به صورت الگوریتم سریالی تعریف می‌کنیم که از حذف کلمات چند ریسمانی به دست می‌آید. موقعیت‌های چالش‌آمیز یک الگوریتم چند ریسمانی، قطعی است اگر همیشه برای یک ورودی خاص، خروجی یکسان تولید کند(مستقل از اینکه دستورالعمل‌ها چگونه روی پردازنده‌ها برنامه‌ریزی می‌شوند) و غیرقطعی است اگر رفتار آن‌ها در اجراهای مختلف با هم تفاوت داشته باشد. خیلی مواقع یک الگوریتم چند ریسمانی که باید قطعی باشد نمی‌تواند به این هدف دست یابد، چون حاوی یک چالش قطعیت است. چند خطای معروف ناشی از این موقعیت‌ها عبارتند از دستگاه تابشی therac-25 که باعث مرگ سه نفر و مجروح شدن چندین نفر دیگر شد و قطع برق امریکای شمالی در سال ۲۰۰۳ که بیش از ۵۰ میلیون نفر از آن رنج بردند. ممکن است روزهای متوالی در آزمایشگاه برنامه خود را بدون هیچ مشکلی تست کنید، ولی در نهایت هنگام عمل به خطاهای عجیب و نادر بر بخورید.. یک چالش قطعیت زمانی رخ می‌دهد که دو دستورالعمل منقطا موازی به یک خانه از حافظه دسترسی داشته باشند و حداقل یکی از آن‌ها در آن خانه حافظه بازنویسی انجام دهد. | ## بخش 3: الگوریتم‌های چندریسمانی | با این که به نظر می‌رسد RACE همیشه باشد مقدار ۲ را چاپ کند (نسخه سریال آن قطعاً همین کار را می‌کند) ممکن است مقدار ۱ را چاپ کند. وقتی یک پردازنده مقدار x را افزایش می‌دهد این عملیات غیرقابل تقسیم است و لی خود از چند دستورالعمل تشکیل می‌شود: 1. نوشتن مقدار ثبات در حافظه مربوط به x شکل زیر یک Dag محاسباتی است که اجرای رویه RACE را نشان می‌دهد که در آن ریسمان‌ها به دستورالعمل‌های تکی شکسته می‌شوند. پردازنده ۲ مقدار x را از حافظه خوانده و در ثبات r2 می‌ریزد و آن را افزایش می‌دهد که مقدار ۱ را برای r1 تولید می‌کند و سپس مقدار حاصل را در x می‌ریزد. اکنون پردازنده ۱ با مرحله ۷ بازمی‌گردد که ذخیره مقدار ۱ مربوط به r1 در x است که در واقع x را تغییر نمی‌دهد. بنابراین در مرحله ۸ مقدار ۱ در خروجی چاپ می‌شود برعکس حالت سریال که در آن مقدار ۲ را در خروجی خواهیم داشت. مثلاً اگر ترتیب اجرا به صورت <۱,۲,۳,۴,۵,۶,۷,۸> باشد به نتیجه صحیح دست پیدا می‌کنیم. ممکن است روزها برنامه خود را تست کرده و هیچ خطایی نیابید ولی در عمل زمانی که خروجی برنامه حیاتی است، با توقف ناگهانی روبرو شوید. با اینکه می‌توان از طرق مختلف مثلاً انحصار متقابل این چالش را برطرف کرد ولی در اینجا به سادگی اطمینان حاصل می‌کنیم که ریسمانهایی که به‌طور موازی کار می‌کنند مستقل هستند. بین spawn ,sync متناظر کر فرزند تشکیل شده باید مستقل از کد پدر باشد که شامل کر فرزندان تکثیر یا فراخوانی شده اضافی هم می‌شود. | ## جمع‌بندی | در خط ۴ یک ماتریس موقتی T در حافظه تخصیص داده می‌شود و خط ۵ هر یک از ماتریس‌های A,B,C,T را به زیر ماتریس‌هایی با اندازه n/2*n/2 تقیسم می‌کند.