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

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

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

مزایا

برنامه‌نویسی چندریسمانی پویا دارای چندین مزیت مهم به شرح زیر است:

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

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

با بررسی مثالی از محاسبه اعداد دنبالهٔ فیبوناتچی به صورت بازگشتی به توضیح این قسمت می‌پردازیم. دنبالهٔ فیبوناتچی به صورت زیر تعریف می‌شود:

F(0) = ۰
F(1) = ۱
F(i) = F(i - 1) + F(i - 2)

اگر بخواهیم جمله n ام سری فیبوناتچی را به دست آوریم می‌توانیم از الگوریتم بازگشتی زیر کمک بگیریم:

FIB(n)
If n<= ۱
	Return n
Else
	X = 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 n
Else
x = spawn P-FIB(n - 1)
y = P-FIB(n - 2
sync
return x + y

اگر کلمات کلیدی spawn , sync را از P-FIB حذف کنیم، شبه کد حاصل دقیقاً مشابه FIB خواهد بود. سریال‌سازی یک الگوریتم چند ریسمانی را به صورت الگوریتم سریالی تعریف می‌کنیم که از حذف کلمات چند ریسمانی به دست می‌آید.

یک الگوریتم چند ریسمانی، قطعی (به انگلیسی: Deterministic) است اگر همیشه برای یک ورودی خاص، خروجی یکسان تولید کند(مستقل از اینکه دستورالعمل‌ها چگونه روی پردازنده‌ها برنامه‌ریزی می‌شوند) و غیرقطعی (به انگلیسی: Nondeterministic) است اگر رفتار آن‌ها در اجراهای مختلف با هم تفاوت داشته باشد. خیلی مواقع یک الگوریتم چند ریسمانی که باید قطعی باشد نمی‌تواند به این هدف دست یابد، چون حاوی یک چالش قطعیت است. موقعیت‌های چالش‌آمیز، مخرب همزمان سازی هستند. چند خطای معروف ناشی از این موقعیت‌ها عبارتند از دستگاه تابشی therac-25 که باعث مرگ سه نفر و مجروح شدن چندین نفر دیگر شد و قطع برق امریکای شمالی در سال ۲۰۰۳ که بیش از ۵۰ میلیون نفر از آن رنج بردند. یافتن این اشکالات مهلک بسیار دشوار است. ممکن است روزهای متوالی در آزمایشگاه برنامه خود را بدون هیچ مشکلی تست کنید، ولی در نهایت هنگام عمل به خطاهای عجیب و نادر بر بخورید.. یک چالش قطعیت زمانی رخ می‌دهد که دو دستورالعمل منقطا موازی به یک خانه از حافظه دسترسی داشته باشند و حداقل یکی از آن‌ها در آن خانه حافظه بازنویسی انجام دهد. رویه زیر حالت چالش‌آمیز را نشان می‌دهد:

RACE()
X = ۰
Parallel for i = 1 to 2
X = x + 1
Print x

پس از مقدار دهی اولیه x با ۰ در خط ۱، رویه RACE دو ریسمان موازی می‌سازد که هر دوی آن‌ها x را در خط ۳ افزایش می‌دهند. با این که به نظر می‌رسد RACE همیشه باشد مقدار ۲ را چاپ کند (نسخه سریال آن قطعاً همین کار را می‌کند) ممکن است مقدار ۱ را چاپ کند. اما این ناسازگاری چه گونه به وجود می‌آید؟ وقتی یک پردازنده مقدار x را افزایش می‌دهد این عملیات غیرقابل تقسیم است و لی خود از چند دستورالعمل تشکیل می‌شود: 1. خواندن x از حافظه و نوشتن آن روی یکی از ثباتهای پردازنده ۲. افزایش مقدار ثبات 3. نوشتن مقدار ثبات در حافظه مربوط به x شکل زیر یک Dag محاسباتی است که اجرای رویه RACE را نشان می‌دهد که در آن ریسمان‌ها به دستورالعمل‌های تکی شکسته می‌شوند.

در جدول زیر نیز مقادیر را برای اجرایی نشان می‌دهد که در آن ناهنجاری بروز کرده‌است.

مقدار x در حافظه ذخیره شده‌است و r1, r2 ثباتهای(به انگلیسی: Register) پردازنده هستند. در مرحله ۱ یکی از پردازنده‌ها x را برابر ۰ قرار می‌دهد. در مراحل ۲ و ۳ پردازنده ۱ مقدار x را از حافظه خوانده و در ثبات r1 قرار می‌دهد. در این مرحله پردازنده ۲ وارد عمل می‌شود ودستورالعمل‌های ۶ تا ۴ را انجام می‌دهد. پردازنده ۲ مقدار x را از حافظه خوانده و در ثبات r2 می‌ریزد و آن را افزایش می‌دهد که مقدار ۱ را برای r1 تولید می‌کند و سپس مقدار حاصل را در x می‌ریزد. اکنون پردازنده ۱ با مرحله ۷ بازمی‌گردد که ذخیره مقدار ۱ مربوط به r1 در x است که در واقع x را تغییر نمی‌دهد. بنابراین در مرحله ۸ مقدار ۱ در خروجی چاپ می‌شود برعکس حالت سریال که در آن مقدار ۲ را در خروجی خواهیم داشت. در واقع بسیاری از اجراها باعث این رخداد نمی‌شوند. مثلاً اگر ترتیب اجرا به صورت <۱,۲,۳,۴,۵,۶,۷,۸> باشد به نتیجه صحیح دست پیدا می‌کنیم. این مشکل چالش‌های قطعیت است. معمولاً اکثر ترتیب‌ها نتیجه درستی را تولید می‌کنند. در نتیجه انجام تست برای تشخیص این چالش‌ها دشوار است. ممکن است روزها برنامه خود را تست کرده و هیچ خطایی نیابید ولی در عمل زمانی که خروجی برنامه حیاتی است، با توقف ناگهانی روبرو شوید. با اینکه می‌توان از طرق مختلف مثلاً انحصار متقابل (به انگلیسی: Mutual Exclusion) این چالش را برطرف کرد ولی در اینجا به سادگی اطمینان حاصل می‌کنیم که ریسمانهایی که به‌طور موازی کار می‌کنند مستقل هستند. یعنی هیچ چالشی نسبت به یکدیگر ندارند. بنابراین در یک ساختار parallel forتمام تکرارها باید مستقل از یکدیگر باشند. بین spawn ,sync متناظر کر فرزند تشکیل شده باید مستقل از کد پدر باشد که شامل کر فرزندان تکثیر یا فراخوانی شده اضافی هم می‌شود.

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

ماتریسها را می‌توان به صورت عادی با سه حلقه تو در تو در هم ضرب کرد که زمان اجرای آن برابر (O(n3 است:

square-matrix-mult(A,B)
n= A.rows
let C be a new n*n matrix
paralell for i=1 to n
	parallel for j=1 to n
	cij=۰
		for k=1 to n
			c[ij]=c[ij]+a[ik]*b[kj]
return C

اما برای کاهش زمان اجرای آن می‌توان به روش زیر عمل کرد: برای ضرب دو ماتریس n*n نیاز به ۸ ضرب ماتریسی n/2*n/2 و یک جمع ماتریسی n/2 * n/2 داریم. به کمک شبه کد زیر با استفاده از موازی‌سازی تو در تو این استراتژی را با روش تقسیم و غلبه پیاده‌سازی می‌کنیم:

P-matrix_mult_recursive
1	n=A.rows
2	if n==۱
3		c[11]=a[1,1].b[1,1]
4	else
5		let T be a new n*n matrix
	partition A, B, C and T ino n/2*n/2 submatrices
	A11,A12,A21,A22;
	B11,B12,B21,B22;
	C11,C12,C21,C22;
	T11,T12,T21,T22;
6	spawn P-matrix_mult_recursive(C11,A11,B11)
7	spawn P-matrix_mult_recursive(C12,A11,B12)
8	spawn P-matrix_mult_recursive(C21,A21,B11)
9	spawn P-matrix_mult_recursive(C22,A21,B12)
10	spawn P-matrix_mult_recursive(T11,A12,B21)
11	spawn P-matrix_mult_recursive(T21,A12,B22)
12	spawn P-matrix_mult_recursive(T21,A22,B21)
13	P-matrix_mult_recursive(T22,A22,B22)
14	sync
15	parallel for i=1 to n
16		parallel for j=1 to n
17			c[i,j]=c[i,k]+t[i,j]

خط ۳ حالت پایه را بیان می‌کند که شرط خروج از تابع بازگشتی است. حالت بازگشتی در خطوط ۴ تا ۱۷ اداره می‌شود. در خط ۴ یک ماتریس موقتی T در حافظه تخصیص داده می‌شود و خط ۵ هر یک از ماتریس‌های A,B,C,T را به زیر ماتریس‌هایی با اندازه n/2*n/2 تقیسم می‌کند.

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

• مقدمه‌ای بر طراحی الگوریتم - دهقان طرزه
• کتاب طراحی الگوریتم - جعفر نژاد قمی
• کتاب ارشد طراحی الگوریتم - هادی یوسفی
• درس و کنکور طراحی الگوریتم - نوشته مهندس حمید رضا مقسمی - انتشارات گسترش علوم پایه