نمونه ترجمه تخصصی رشته ریاضی - ترجمه آنلاین

جبر خطی با عملکرد بالا

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

عملیات مختلف جبر خطی، از جمله روش های تکراری، و رفتار آنها در حضور شبکه­ای با پهنای باند محدود و امکان ارتباط محدود را تجزیه تحلیل می کنیم. این فصل را با نکات کوتاهی درباره پیچیدگی­های الگوریتم­ها که ناشی از اجرای موازی است، به پایان می بریم.

 

سفارش ترجمه تخصصی تمامی رشته ها

 

 

6.1. عملیات جمعی

عملیات جمعی نقش مهمی در عملیات جبر خطی دارند. در واقع، مقیاس­پذیری عملیات به هزینه این گروه­ها بستگی دارد که در ادامه خواهیم دید. در اینجا بررسی کوتاهی داریم درباره نظریه­های  اساسی؛ برای جزئیات بیشتر رجوع کنید به [21].

در محاسبه هزینه عمل جمعی، سه ثابت ساختاری برای بدست آوردن مرزهای پایین کافی است: α، ارسال یک پیام، β معکوس داده ا رسالی (رجوع کنید به بخش 1.3.2)، و γ معکوس زمان برای اجرای عمل حساب. ارسال n آیتم داده به α + βn زمان نیاز دارد. بعلاوه فرض می کنیم که هر بار فقط یک پیام را می توان ارسال کرد. درباره امکان ارتباط پردازشگرها فرضی صورت نگرفته است؛ بنابراین مرزهای پایین حاصل برای دامنه وسیعی از ساختارها صدق می­کند.

دلالت اصلی مدل ساختاری بالا این است که تعداد پردازشگر اکتیو در هر مرحله از الگوریتم فقط می­تواند دو برابر شود. برای مثال، برای انجام پخش گسترده، پردازشگر اول 0 به پردازشگر 1 ارسال می کند، سپس 0 و 1 می توانند به 2 و 3 ارسال کند، سپس 3-0 به 4-7 ارسال می کنند و همین طور ادامه می یابد. این ترتیب ا رسال پیام، درخت پوشا با حداقل پوشش شبکه پردازشگر نامیده می شود، و هر الگوریتم حداقل α log₂p هزینه در رابطه با مجموع نهفتگی دارد.

 

دیکشنری تخصصی ریاضی آنلاین

 

6.1.1. پخش گسترده

در عمل پخش گسترده، یک پردازشگر دارا n عنصر داده است که باید به بقیه ارسال شود: پردازشگرهای دیگر به کپی کامل همه n عنصر نیاز دارند. براساس توضیح بالا، می توان نتیجه گرفت که پخش گسترده به p پردازشگر حداقل [log₂p] مرحله زمان می­برد و با مجموع نهفتگی (تاخیر) [log₂p] α خواهد بود. چون n عنصر ارسال می شود، nβ به همه عناصر ارسالی از پردازشگر افزوده می شود و حد پایین هزینه عبارت است از

 

می توان متد درخت پوشا (زیرگرافی از یک درخت) را به شکل زیر نشان داد:

 

(در t = 1، p₀ به p₁ ارسال می­کند؛ در t = 2، p₀, p₁ به p₂p₃ ارسال می کند.) این الگوریتم عبارت درست log₂p.α را دارد اما پردازشگر 0 به صورت مکرر کل بردار را ارسال می کند، در نتیجه هزینه پهنای باند log₂p . nβ است. اگر n کوچک باشد، هزینه نهفتگی غالب است، بنابراین  می­توان این رابطه به صورت عملیات جمعی بردار کوتاه عنوان کرد.

الگوریتم زیر پخش گسترده را به صورت ترکیبی از الگوریتم پراکندن و پخش یکنواخت (bucket brigade) اجرا می­کند:  

 

حالا پیچیدگی عبارت  است از

 

که در نهفتگی (latency) مطلوب نیست، اما اگر n بزرگ باشد الگوریتم بهتر خواهد بود و آن را  به عمل جمعی بردار بلند تبدیل می­کند.

6.1.2. کاهش

در عمل کاهش، هر پردازشگر n عنصر داده دارد، و یک پردازشگر باید آنها را عنصر به عنصر ترکیب کند، مثلا با محاسبه n جمع یا ضرب.

با اجرای پخش گسترده روبه عقب در طول زمان، می توان دید که عمل کاهش همان مرز پایین در ارتباط [log₂p]  α + nβ را دارد. هم چنین عمل کاهش محاسبه­ای را نیز دربرمی گیرد که به مجموع زمان (p – 1) γn به صورت ترتیبی نیاز دارد: هر n آیتم در n پردازشگر کاهش می­یابد. از آنجا که این عملیات می­تواند موازی شود، مرز پایین در محاسبات عبارت است ازγn  p-1p ، و این مجموع حاصل می شود:

 

الگوریتم درخت پوشا با استفاده از علامت x^(j)_i برای آیتم داده i نشان داده شده است که در اصل در پردازشگر j بود، و x_i^(j:k) را برای مجموعه آیتم­های i پردازشگر j . . . k بکار می­بریم.

 

در زمان t = 1، پردازشگر p₀, p₂ از p₁, p₃ دریافت می کند و در زمان t = 2، p₀ از p₂ دریافت می کند.

در مورد پخش گسترده بالا، این الگوریتم به مرز پایین نمی­رسد؛ بلکه پیچیدگی آن عبارت است از

 

برای بردارهای کوتاه عبارت α غالب است بنابراین این الگوریتم کافی است. برای بردارهای بلند می توان همانند بالا الگوریتم­های دیگری بکار برد [21].

6.1.3. Allreduce

عمل allreduce همان کاهش جزء به جزء n عنصر را در هر پردازشگر محاسبه می کند، اما نتیجه را به جای اینکه فقط در ریشه درخت پوشا قرار دهد، در هر پردازشگر قرار می دهد. این عمل را می­توان به صورت کاهش و سپس پخش گسترده اجرا کرد اما الگوریتم­های موثرتری نیز وجود دارد.

مرز پایین در هزینه allreduce تقریبا با عمل کاهش ساده برابر است: چون در کاهش همه پردازشگرها همزمان فعال نیستند، فرض می کنیم که کار بیشتری را می توان تقسیم کرد. این یعنی مرز پایین در نهفتگی و محاسبه یکسان می ماند. برای پهنای باند، توجیه ما به این است: برای اینکه برقراری ارتباط کاملا موازی شود،n  p-ip  آیتم باید به هر پردازشگر برسد و آن را ترک کند. بنابراین مجموع زمان عبارت است از

 

6.1.4. Allgather

در عمل allgather روی n عنصر، هر پردازشگر n/p عنصر دارد، و یک پردازشگر همه آنها را گردآوری می کند، بدون اینکه آنها را همانند کاهش ترکیب کند. allgather همانند gather (گردآوری) محاسبه می کند اما نتیجه را در هر پردازشگر قرار می­دهد.

بازهم فرض می کنیم که گردآوری­ها (gatherها) با چند هدف همزمان فعال هستند. چون هر پردازشگر از درخت پوشای حداقل منشعب می شود، نهفتگی log₂pα را داریم. مجموع هزینه ساخت بردار به طول n با allgather عبارت است از

 

سفارش ترجمه تخصصی تمامی رشته ها

 

که به اینصورت نشان داده شده است:

 

در زمان t = 1، مبادله یبن همسایه p₀, p₁ و همینطور p₂, p₃ برقرار است؛ در زمان t = 2 مبادله در فاصله دو بین p₀, p₁ و همینطور p₁, p₃  است.

6.1.5. کاهش – پراکنش

در عمل کاهش – پراکنش (reduce-scatter)، هر پردازشگر n عنصر دارد، و کاهش n طرفه روی آنها انجام می­گیرد. برخلاف کاهش یاا allreduce، نتیجه تقسیم می شود، و همانند عمل پراکنش (scatter) توزیع می شود.

پردازشگر i آیتم x⁽ⁱ⁾_i ر ا دارد و به ∑_jx_i^(j) نیاز دارد. می توان این عمل را با کاهش اندازه p، با گردآوری بردار (∑_ix₀⁽ⁱ⁾, ∑_ix_i⁽ⁱ⁾, . . .) در یک پردازشگر، و پراکنش (پخش) نتایج انجام داد. با این حال، می توان این عملیات را در الگوریتم تبادل دوطرفه معروف تلفیق کرد:

 

کاهش – پراکنش را می توان اجرای معکوس allgather در نظر گرفت که با افزایش حساب همراه است، بنابراین هزینه عبارت است از:

 

6.2. ضرب برداری ماتریس موازی متراکم 

در این بخش به تفصیل به عملکرد ضرب برداری ماتریس موازی متراکم، بویژه مقیاس پذیری می­پردازیم. ابتدا مورد ساده­ای را بررسی می کنیم، و جنبه­های موازی سازی را تا انداز­ه­ای بحث می کنیم.

6.2.1. پیاده­سازی بلوک – ردیف

در طراحی نسخه موازی الگوریتم، معمولا داده­های اهداف مربوطه تجزیه می شود. در مورد عملیات ماتریس-بردار مثل ضرب y = Ax، می توان با تجزیه بردار شروع کرد، و انشعابات آن را در تجزیه ماتریس بررسی کرد، یا با ماتریس شروع کرد و تجزیه بردار را از روی آن بدست آورد. در این مورد، به نظر می رسد که شروع با تجزیه ماتریس بهتر از بردار باشد، زیرا به احتمال زیاد اهمیت محاسباتی بیشتری خواهد داشت. حالا دو گزینه داریم.

1. تجزیه تک بعدی روی ماتریس انجام می دهیم و آن را به ردیف­های بلوک یا ستون­های بلوک تقسیم می کنیم و هر یک از اینها را به یک پردازشگر اختصاص می دهیم.
2. یا می توان تجزیه د.وبعدی انجام داد و به هر پردازشگر زیرماتریس بیشتری اختصاص داد.

با تجزیه ردیف­های بلوک شروع می کنیم. پردارشگر p و مجموعه I_p  اندیس­ها یا ردیف­های خودش را در نظر می­گیریم،I_p  i ϵ را ردیفی بگیرید که برای این پردازشگر تعیین شده است. عناصر در ردیف i در عمل زیر بکار می رود:

 

حالا توجیه مسئله:

 

زبان تخصصی ریاضی+pdf

 

• اگر پردازشگر p همه مقادیر x_j را داشته باشد، ضرب بردار – ماتریس را می توان به راحتی اجرا کرد، و در پایان اجرا، پردارشگر مقادیر درست y_j برای j ϵ I_p خواهد داشت.
• این یعنی هر پردازشگر باید یک کپی از x را داشته باشد، که کاری بی­فایده. هم چنین مسئله انسجام داده­ها مطرح می شود: باید مطمئن شوید که پردازشگر مقدار درست x را دارد.
• در ایجاد اپلیکیشن­های عملی (مثلا متدهای تکراری که قبلا دیدید)، حاصل ضرب بردار- ماتریس، مستقیما یا غیرمستقیم، ورودی ضرب بردار – ماتریس بعدی است. مطمئناً این وضعیت برای متد توان است که x, Ax, A²x, . . . را محاسبه می کند. چون عمل ما با کل x برای هر پردازشگر شروع شد، اما در پایان x فقط عنوان قسمت محلی Ax بود، اشتباه کرده­ایم (خطا داریم).
• شاید بهتر باشد فرض کنیم که هر پردازشگر، در شروع عمل، فقط قسمت محلی x را دارد، یعنی x_i، که i ϵ I_p است، تا حالت شروع و پایان الگوریتم یکسان باشد. یعنی باید الگوریتم را تغییر دهیم تا ارتباطی را شامل شود که هر پردازشگر بتواند مقادیر x_i را با i ∉ I_p  را بدست آورد.

تمرین 6.1. توجیه مشابهی را درباره موردی ارائه دهید که ماتریس به ستون­های بلوک تجزیه می شود. الگوریتم موازی را به تفصیل همانند بالا اما بدون شبه کد توضیح دهید.

حالا ارتباط را با جزئیات بررسی می کنیم: پردازشگر ثابت p، عملیاتی که انجام می دهد و ارتباطی را که لازم دارد، در نظر می­گیریم. طبق تحلیل بالا، در اجرای عبارت y_i = ∑_j a_jx_j باید بدانیم که مقادیر j به کدام پردازشگر تعلق دارد. برای این منظور، داریم

 

ورودی: تعداد پردازشگر p، عناصر x_i با i ϵ I_p؛ عناصر ماتریس A_ij با i ϵ I_p.

خروجی: عناصر y_i با i ϵ I_p

برای i ϵ I_p

s←0 را انجام دهید؛

برای j ϵ I_p

s←s + a_ijx_j را انجام دهید.

برای j ∉I_p

X_i را از پردازشگری که در آن قرار دارد به پردازشگر فعلی (جاری) ارسال کنید، سپس؛

s←s + a_ijx_j

y_i ←s

روش MVP موازی (a, x_local, y_local, p)

شکل 6.1: ضرب بردار-ماتریس موازی کدگذاری شده ساده

اگر j ϵ I_p باشد، در اینصورت y_i ← y_i + a_ijx_j فقط مقادیری را دربرمی­گیرد که از قبل نسبت به پردازشگر محلی است. بنابراین روی مورد  j ∉I_p  تمرکز می کنیم. بهتر است فقط عبارت زیر را بنویسیم

 

و لایه پایین­تر به صورت خودکار x (j) از هر پردازشگری که در آن ذخیره شده باشد به رجیستر محلی منتقل می­شود. (زبان­های PGAS بخش 2.6.5 برای این منظور هستند اما راندمان تضمین نشده است.) پیاده­سازی براساس این دیدگاه خوش بینانه در مورد موازی­سازی در شکل 6.1. آمده است.

مسئله چنین روش محلی این است که ارتباط خیلی زیا است.

• اگر ماتریس A متراکم باشد، عنصر x_j برای هر ردیف ضروری است، و در نتیجه عنصری است که به هر ردیف i ϵ I_p آورده می شود.
• برای هر پردازشگر q ≠p ، تعداد زیادی عنصر x_i با i ϵ I_p وجود خواهد داشت که باید از پردازشگر q به p منتقل شوند. انجام اینکار در پیام­های جداگانه، به جای انتقال یکجا، اتلاف زیادی دارد.

این مسائل در مود حافظه مشترک چندان مطرح نیست، اما در مورد حافظه توزیع شده بهتر است از روش بافرینگ استفاده شود.

 

سفارش ترجمه تخصصی تمامی رشته ها

به جای ارتباط عناصر x به صورت تک تک، ما از بافر محلی B_pq برای هر پردازشگر  q ≠p  استفاده می­کنیم و عناصر لازم را برای انجام ضرب در p از q گردآوری می کنیم. (رجوع کنید به شکل 6.2). الگوریتم موازی در شکل 6.3 نشان داده شده است.

با این روش، علاوه بر اینکه از آوردن هر عنصر بیش از یکبار جلوگیری می شود، پیام­های کوچک زیادی در یک پیام بزرگ ادغام می شود که معمولاً موثرتر است؛ بحث پهنای باند نهفتگی در بخش 2.7.8 را به خاطر آورید.

تمرین 6.2. شبه کدی برای ضرب بردار – ماتریس با استفاده از عملیات غیر بلوک ­بندی ایجاد کنید (رجوع کنید به بخش 2.6.3.6).

 

شکل 6.2. ضرب بردار – ماتریس موازی با توزیع ردیف بلوک.

ورودی: تعداد پردازشگر p، عناصر x_i با i ϵ I_p؛ عناصر ماتریس A_ij با i ϵ I_p.

خروجی: عناصر y_i با i ϵ I_p

برای q ≠p

عناصر x را از پردازشگر q به p ارسال کنید، به صورت بافر B_pq دریافت کنید.

y_local←Ax_local

برای q ≠p

y_local ← y_local + A_pqB_pq

روش MVP موازی (A, x_local, y_local, p)

شکل 6.3. پیاده­سازی ضرب بردار – ماتریس موازی با بافر (میانگیر)

در بالا گفتیم که داشتن کپی کل x در هر پردازشگر اتلاف فضا است. بحث ضمنی در اینجا این است که به طور کل نمی­خواهیم ذخیره­سازی محلی تابعی از تعداد پردازشگر باشد: معمولا باید تابعی از داده­های محلی باشد. (این با مقیاس­پذیری ضعیف مرتبط است؛ بخش 2.2.4.)

می بینید که به خاطر ملاحظات ارتباطی به این نتیجه رسیدیم که ذخیره کل بردار ورودی هر پردازشگر اجتناب­ناپذیر است یا حداقل بهتر است انجام گیرد. چنین موازنه­ای بین زمان و فضا در برنامه نویسی موازی کاملا متداول است. برای ضرب بردار – ماتریس متراکم می توان از این سربار  دفاع کرد، زیرا ذخیره­ بردار مرتبه پایین­تری از ذخیره ماتریس دارد، بنابراین تخصیص ما چندان هم بیش از حد لازم نیست. در ادامه (بخش 6.5) خواهیم دید که برای ضرب بردار – ماتریس اسپارس (کم پشت) ممکن است سربار بسیار کمتر باشد.

به راحتی می توان دید که ضرب بردار – ماتریس متراکم، به طوریکه در صورت صرفنظر از زمان ارتباط، افزایش سرعت خیلی خوبی دارد. در بخش­های بعدی خواهید دید که پیاده­سازی ردیف بلوک بالا با در نظر گرفتن ارتباط، مطلوب نخواهد بود. برای مقیاس­پذیر بودن به تجزیه دو بعُدی نیاز داریم. با بررسی مشترک­ها شروع می کنیم.

6.2.2 مقیاس­پذیری ضرب بردار – ماتریس متراکم

در این بخش تحلیل کاملی داریم درباره محاسبه موازی  y ← A_x که x, y ∈ Rⁿ  است و A ∈ R^{n ×n}  است. فرض می کنیم که p گره بکار می رود، اما فرضی درباره امکان اتصال آنها نداریم. خواهیم دید که چگونه ماتریس توزیع شده تفاوت زیادی در مقیاس گذاری الگوریتم ایجاد می کند؛ برای جستجوی اصلی رجوع کنید به [83, 144, 150]، و بخش 2.24 برای تعریف اشکال مختلف مقیاس گذاری.

6.2.2.1. ضرب بردار – ماتریس، تقسیم براساس ردیف

تقسیم­بندی

 

که در آن A ∈ R^{mi ×n}  و∈ R^n-m   ∑^p-1_i=0 m_in   x_iy_i  و m_i ≈ n/p است. با این فرض شروع می­کنیم که A_i , x_i , y_i در اصل به P_i اختصاص یافته­اند.

در این محاسبه هر پردازشگر به کل بردار x نیاز دارد، اما فقط کسر n/p از آن را داراست. بنابراین allgather را برای x اجرا می کنیم. سپس پردازشگر می تواند ضرب محلی y_i ← A_ix را انجام دهد؛ ارتباط دیگری پس از آن لازم نیست.

الگوریتمی با هزینه ارتباط برای y = Ax در صورتی موازی است که

مرحله	هزینه (مرز پایین)
xi را allgather کنید به طوریکه x در همه گره­ها موجود باشد yi  = Ax را به صورت محلی محاسبه کنید

 

تحلیل هزینه: مجموع هزینه الگوریتم به طور تقریبی عبارت است از،

 

چون هزینه ترتیبی T₁(n) = 2n²γ است، افزایش سرعت عبارت است از

 

و راندمان عبارت است از

 

نگاهی خوش­بینانه: حالا اگر p را معین و n را بزرگ بگیریم،

 

بنابراین اگر بتوانیم مسئله را به اندازه کافی بزرگ بسازیم، راندمان موازی تقریبا عالی خواهد بود. اما چنین راندمانی با فرض حافظه نامحدود بدست می­آید، پس این تحلیل عملی نیست.

نگاهی بدبینانه: در تحلیل مقیاس­پذیری قوی، n را ثابت و p را بزرگ می­گیریم تا داشته باشیم،

 

بنابراین، در نهایت راندمان موازی تقریبا وجود ندارد.

نگاهی واقع­بینانه: در نگاهی واقع­بینانه تعداد پردازشگر را با افزایش میزان داده افزایش می­دهیم. اینکار مقیاس­پذیری نامیده می شود، و موجب می­شود میزان حافظه موجود برای ذخیره مسئله به صورت خطی با p افزایش یابد.

M را برابر با تعداد اعداد با ممیز شناور بگیرید که می­توان در حافظه یک گره ذخیره کرد. در اینصورت حافظه جمعی با Mp بدست می­آید. n_max(p) را برابر با بزرگترین مسئله بگیرید که می­توان در حافظه جمعی p گره ذخیره کرد. در اینصورت اگر بتوان از کل حافظه برای ماتریس استفاده کرد،

 

حالا این پرسش مطرح می شود که با چه راندمان موازی می­توان بزرگترین مسئله را در p گره ذخیره کرد:

 

حالا اگر آنچه را که با افزایش تعداد گره اتفاق می­افتد، تحلیل کنیم، درمی­یابیم که

 

بنابراین، این الگوریتم موازی برای ضرب بردار – ماتریس مقیاس­پذیر نیست.

اگر این عبارت راندمان را با دقت بیشتری بررسی کنید، می بینید که مسئله اصلی قسمت 1/p  است. این جملات فاکتوری از β را دربرمی­گیرند و اگر مشتق معکوس را دنبال کنید خواهید دید که از زمان ارسال داده بین پردازشگرها پدید می­آید. در واقع بدون توجه به تعداد پردازشگر، اندازه پیام ثابت n است.

فرد واقع­بین می­داند که زمان محدود، T_max، برای انجام محاسبه وجود دارد. تحت بهترین شرایط، یعنی با سربار ارتباط صفر، بزرگترین مسئله­ای که می­توانیم در زمان T_max حل کنیم، عبارت است از

 

 

بنابراین

 

راندمان موازی که با بزرگترین مسئله قابل حل در زمان T_max می­توان برای الگوریتم بدست آورد، عبارت است از

 

و راندمان موازی با افزایش تعداد گره­ها عبارت است از

 

بازهم با افزایش تعداد پردازشگرها و محدودیت زمان نمی­توان راندمان را حفظ کرد.

 

 6.2.2.2. ضرب بردار – ماتریس، تقسیم­بندی براساس ستون

تقسیم­بندی

 

که در آن A_j∈ R^{n  n×}  وx_iy_i ∈ Rⁿ  با ∑^p-1_i=0 n_j = n و n_j ≈ n/p است.

با این فرض شروع می­کنیم که  A_j, x_i و y_i در اصل به P_j اختصاص داده شده اند (اما حالا A_i بلوک ستون­هاست). در این الگوریتم براساس ستون، پردازشگر i می­تواند طول بردار A_ix_i را بدون ارتباط قبلی محاسبه کند. بنابراین این نتایج نسبی باید درعمل کاهش - پراکنش باهم جمع شود:

 

هر پردازشگر i قسمت (A_ix_i)   نتیجه خود را به پردازشگر j پخش می­کند. سپس پردازشگرهای دریافت کننده عمل کاهش را انجام می­دهند، و همه این قسمت­ها را به هم اضافه می­کنند:

 

الگوریتم با هزینه­ها عبارت است از:

 

مرحله	هزینه (مرز پایین)
به صورت محلی y(j) = Ajxj روی y(j) کاهش- پراکنش انجام دهید به طوریکه yi= j=0(p-1)yi(j)  باشد.

 

تحلیل هزینه: مجموع هزینه الگوریتم به صورت تقریبی عبارت است از،

 

توجه داشته باشید که این تحلیل همانند هزینه T^1D-row (n) است، به جز اینکه (β + γ) جایگزین β شده است. به راحتی می­توان دید که نتیجه­گیری­ها د رباره مقیاس­پذیری همان است.

6.2.2.3. تقسیم­بندی دو بُعدی

سپس تقسیم­بندی زیر انجام دهید

 

که در آن     A_ij ∈ R^{n_i ×n_j} و x_iy_i ∈ R^n_i  با ∑^p-1_i=0 n_j = N و   n_i≈N /p است.

گره­ها را به صورت شبکه c × r خواهیم دید، با P = rc، و اندیس آنها  به صورت p_ij با I = 0, . . ., r-1 و j=0, . . . , c-1 است. شکل 6.4 برای ماتریس 12 × 12 در شبکه پردازشگر 4 × 3، تخصیص داده­ها به گره­ها را نشان می­دهد که در آن سلول i, j عناصر ماتریس و بردار را برای p_ij نشان می­دهد.

 

شکل 4. توزیع عناصر ماتریس و بردار برای مسئله­ای با اندازه 12 و در شبکه پردازشگر 3 × 4.

به عبارت دیگر، p_ij بلوک ماتریس A_ij و قسمت x و y را دارد. بر این اساس، الگوریتم زیر حاصل می­شود:

• چون x_j در ستون jام توزیع شده است، الگوریتم با گردآوری x_i در هر پردازشگر p_ij بوسیله allgather درون ستون­های پردازشگر شروع می­شود.
• هر پردازشگر p_ij، y_ij = A_ijx_j را محاسبه می­کند. اینکار به ارتباط بیشتری نیاز ندارد.
• سپس نتیجه y_i با گردآوری تکه­های y_ij در هر ردیف پردازشگر جمع­آوری می­شود تا y_i شکل گیرد، و سپس در ردیف پردازشگر توزیع می­شود (پخش می­شود). در واقع این دو عمل برای تشکیل کاهش- پراکنش (reduce – scatter) تلفیق می­شود.
• اگر r = c باشد، می­توانیم داده­های y را در پردازشگرها جابجا کنیم، تا بتواند به عنوان ورودی برای ضرب بردار – ماتریس بعدی باشد. اما اگر A^tAx را محاسبه می­کنیم، y به درستی برای ضرب A^t توزیع شده است.

الگوریتم: الگوریتم با تحلیل هزینه عبارت است از

مرحله	هزینه (مرز پایین)
xi را درون ستون­ها allgather کنید ضرب بردار – ماتریس محلی را انجام دهید yi را درون ردیف­ها کاهش- پراکنش دهید

 

تحلیل هزینه: مجموع هزینه الگوریتم به صورت تقریبی عبارت است از

 

حالا ساده کردن را  انجام می­دهیم تا r=c= p  شود.

 

چون هزینه ترتیبی T₁(n) = 2n²γ است، افزایش سرعت عبارت است از

 

و راندمان موازی عبارت است از

 

سفارش ترجمه تخصصی تمامی رشته ها

 

بازهم این پرسش را می­پرسیم که راندمان موازی برای بزرگترین مسئله­ای که می­توان در p گره ذخیره کرد، چیست.

 

به طوریکه هنوز داریم

 

با این حال، log₂p خیلی آهسته با p رشد می­کند و در نتیجه با همان عملکرد خواهد بود. در این مورد  E_p^p×p (n_maxp) خیلی آهسته کاهش می­یابد و الگوریتم برای اهداف عملی مقیاس­پذیر محسوب می­شود.

توجه داشته باشید که وقتی r = p است، الگوریتم 2 بُعدی به الگوریتم "تقسیم­بندی با ردیف" تبدیل می­شود و وقتی c = p است به الگوریتم "تقسیم­بندی با ستون" تبدیل می شود. به راحتی می­توان نشان داد که الگوریتم دو بعدی براساس تحلیل بالا وقتی r = c است تا زمانیکه r/c ثابت بماند، مقیاس­پذیر است.

6.3. فاکتورگیری LU به صورت موازی

موازی سازی ماتریس – بردار و ضرب ماتریس – بردار از یک نظر آسان است. همه عناصر خروجی به صورت جداگانه با هر ترتیبی قابل محاسبه هستند، بنابراین درجه رهایش بالایی در الگوریتم موازی­سازی داریم. این امر در مورد محاسبه فاکتورگیری LU یا حل کردن سیستم خطی با ماتریس فاکتورگیری شده نیز صدق می­کند.

6.3.1. حل سیستم مثلثی

حل سیستم مثلثی y = L^-1_x ( L مثلثی پایین است) عمل ماتریس-بردار است، بنابراین پیچیدگی O(N²) با ضرب ماتریس – بردار مشترک است. با این حال، برخلاف عمل ضرب، این فرآیند حل رابطه رکورانس (بازگشتی) بین عناصر خروجی دارد:

 

این به این معنی است که موازی­سازی ناچیز نیست. در مورد ماتریس اسپارس استراتژی­های خاصی امکان­پذیر است؛ رجوع کنید به بخش 6.11. در اینجا نکته کلی درباره مورد متراکم عنوان می­کنیم.

برای سادگی فرض کنید ارتباط زمان نمی­برد، و همه عملیات ریاضی به زمان یکسان نیاز دارند. ابتدا توزیع ماتریس براساس ردیف را در نظر می­گیریم، یعنی پردازشگر p عناصر l_p*  را ذخیره می­کند. با  این فرض می­توانیم راه حل مثلثی را به ترتیب زیر پیاده کنیم:

• پردازشگر 1،  y₁= l₁₁^-1x₁  را حل می­کند و مقدار آن را به پردازشگر بعدی می­فرستد.
• به طور کل، پردازشگر p مقادیر y₁, . . ., y_p-1 را از پردازشگر p - 1 می­گیرد و y_p را  محاسبه می­کند؛
• سپس هر پردازشگر p، y₁, . . ., y_p را به p + 1 می­فرستد.

تمرین 6.3. نشان دهید که این الگوریتم 2N² زمان می­برد، درست مثل الگوریتم ترتیبی (متوالی).

در این الگوریتم هر پردازشگر همه مقادیر محاسبه شده را به شیوه خاصی به جانشین­اش منتقل می کند. با این حال، اینکار به این معنی است که پردازشگر p فقط در آخرین لحظه y₁ را دریافت می­کند، در صورتیکه این مقدار قبلا در مرحله اول محاسبه شده است. این الگوریتم حل را می­توان به گونه­ای تنظیم کرد که عناصر محاسبه شده بالافاصله در دسترس قرار گیرند:

• پردازشگر 1، y₁ را حل می­کند و به همه پردازشگرهای بعدی می فرستد.
• به طور کل، پردازشگر p منتظر پیام­های فردی با مقادیر y_p برای q < p می­ماند.
• سپس پردازشگر p، y_p را محاسبه می­کند و آن را به پردازشگرهای q با q > p ارسال می­کند.

تحت  این فرض که زمان ارتباط قابل صرفنظر است، این الگوریتم می­تواند بسیاری سریع­تر باشد. برای مثال، همه پردازشگرهای p > 1 همزمان y₁ را دریافت می­کنند و می­توانند همزمان  l_p1y₁ را محاسبه کنند.

تمرین 6.4. نشان دهید که طول زمان این الگوریتم O(N) است.

تمرین 6.5. حالا توزیع ماتریس براساس ستون را در نظر بگیرید: پردازشگر p، l_*p را ذخیره می­کند. الگوریتم حل مثلثی را با این توزیع طرح کنید و نشان دهید که زمان حل موازی O(N) است.

6.3.2. فاکتورگیری

تحلیل کامل مقیاس­پذیری فاکتورگیری LU متراکم بسیار پیچیده است، بنابراین بدون اثبات بیشتر می­گوییم که همانند مورد ماتریس – بردار، توزیع دوبُعدی لازم است. با این حال، می­توان پیچیدگی دیگری نیز مشخص کرد. چون فاکتورگیری از هر نوع در ماتریس پیش می­رود، پردازشگرها برای مدتی غیرفعال خواهند بود.

تمرین 6.6. حذف گاوسی رو به راست معمولی را در نظر بگیرید

 

زمان اجرا، افزایش سرعت، و راندمان را به صورت تابعی از N تحلیل کنید، فرض کنید توزیع تک بُعدی است و پردازشگر کافی برای ذخیره یک ستون به ازای هر پردازشگر وجود دارد. نشان دهید که افزایش سرعت محدود است.

این تحلیل را برای تجزیه دوبُعدی نیز انجام دهید که در آن هر پردازشگر یک عنصر را ذخیره می کند.

 

به همین دلیل، تجزیه زیاد بکار رفته است، که در آن ماتریس به بلوک­های بیشتری از تعداد پردازشگر تقسیم می­شود، و هر پردازشگر چندین زیرماتریس غیرمجاور را ذخیره می­کند. این فرآیند در شکل 6.5 نشان داده شده است.

 

شکل 6.5. توزیع چرخه­ای تک بُعدی: تخصیص چهار ستون ماتریس به دو پردازشگر، و ترسیم ذخیره­سازی حاصل بر ستون­های ماتریس.

که در آن چهار ستون مارتریس با به دو پردازشگر تقسیم می­کنیم: هر پردازشگر در ستون مجاور حافظه دو ستون ماتریس غیرمجاور ذخیره می­کند.

 در شکل 6.6 نشان می­دهیم که ضرب ماتریس – بردار با چنین ماتریسی را می­توان بدون آگاهی از اینکه پردازشگرها قسمت­های غیرمجاور ماتریس را ذخیره ­می­کنند، حل کرد. تنها چیزی که لازم است این است که بردار ورودی نیز به صورت چرخه­ای توزیع شود.

 

شکل 6.6. ضرب ماتریس - بردار با ماتریس توزیع شده چرخه­ای.

تمرین 6.7. حالا ماتریس 4 × 4 و شبکه پردارشگر 2 × 2 در نظر بگیرید. ماتریس را به صورت چرخه­ای هم براساس ردیف و هم با ستون توزیع کنید. نشان دهید تا زمانی که ورودی درست توزیع شود، ضرب ماتریس – بردار را می­توان با استفاده از ذخیره­سازی مجاور ماتریس انجام داد. خروجی چگونه توزیع می­شود؟ نشان دهید که ارتباط بیشتری نسبت به کاهش مثال تک بُعدی نیاز است.

بویژه، با P < N پردارشگر، و با فرض ساده بودن N = cP، پردازشگر 0 را با ذخیره ردیف 0, c, 2c, 3c, … در نظر بگیرید؛ پردازشگر 1 ردیف 1, c + 1, 2c + 1, . . ., را ذخیره می­کند و غیره. اگر N = c₁P₁ = c₂P₂ و P = P₁P₂ باشد، این طرح را می­توان به دو توزیع دو بُعدی تعمیم دارد. اینکار توزیع چرخه­ای 2 بُعدی نامیده می­شود. این طرح را می­توان با در نظر گرفتن ردیف­ها و ستون­های بلوک، و با تخصیص ردیف­ 0, c, 2c, … بلوک به پردازشگر 0 بیشتر بسط داد.

 

الگوریتم 1: a ← x^ty را محاسبه کنید که در آن x, y بردارهای توزیع شده است

کاهش و پخش گسترده (که می­تواند در Allreduce تلفیق شود) داده­ها در همه پردازشگرها را تلفیق می­کند، بنابراین زمان  ارتباطی آنها با افزایش تعداد پردازشگر افزایش می­یابد. این امر باعث می شود ضرب داخلی عمل گسترده­ای باشد، و راههایی برای کاهش تاثیر آنها بر عملکرد متدهای تکراری پیشنهاد شده است.

برخی از روش­های اتخاذ شده به ترتیب زیر است.

• ممکن است محاسبه ضرب داخلی بر محاسبات موازی دیگر منبطق باشد [34].
• در متد GMERS، استفاده از متد کلاسیک Gram-Schmidt (GS) ضرب داخلی غیروابسته بسیار کمتری از متد تعدیل شده GS دارد، اما ثبات کمتری دارد. برخی استراتژی­هایی برای تصمیم­گیری در استفاده از متد کلاسیک GS بررسی کرده­اند [110].

از آنجا که حساب کامپیوتری شرکت­پذیر نیست، ضرب­های  داخلی منبع اصلی نتایجی هستند که با اجرای یک محاسبه یکسان برای دو پیکربندی متفاوت پردازشگر فرق می­کنند. در بخش 3.3.6 این راه حل را شرح داده­ایم.

6.7.2. ساختار ماتریس المان محدود

موضوع بسیار مهم این است که المان ماتریس a_ij مجموع محاسبات، بویژه انتگرال­های معین، در همه المان­هایی است که هر دو متغیر i و j را دارند:

 

 

شکل 6.9. دامنه المان محدود، موازی­سازی ساختار ماتریس، و موازی­سازی ذخیره­سازی المان.

محاسبات در هر المان قسمت­های مشترک زیادی دارند، بنابراین طبیعی است که هر المان e به صورت منحصر برای پردازشگر P_e تخصیص یابد، که همه a_ij^(e) را محاسبه می­کند. در شکل 6.9 المان 2 برای پردازشگر 0 تعیین شده و المان 4 برای پردازشگر 1 تخصیص یافته است.

 

6.8. پیش­شرط ­سازهای موازی

در بالا (بخش 5.5.5 و بویژه 5.5.5.1) چند گزینه مختلف از K دیدیم. در این بخش با بررسی استراتژی­های موازی­سازی شروع می­کنیم. این بحث و بررسی ه تفصیل در بخش­ها بعدی ادامه خواهد د اشت.

6.8.1. پیش­شرط­ سازی ژاکوبی

6.8.2. مشکل با IUL موازی

در بالا دیدیم که از نظر شمارش فلاپ، بکارگیری پیش­شرط­ساز ILU (بخش 5.5.5.1) به اندازه انجام ضرب بردار- ماتریس پرهزینه است. اگر متدهای تکراری را در کامپیوتر موازی بکار گیریم، این افزایش هزینه دیگر وجود نخواهد داشت.

در نگاه اول عملیات شبیه هم هست. ضرب بردار – ماتریس y = Ax به این شکل است

 

در حالت موازی به این شکل خواهد بود

 

فرض کنید پردازشگر کپی محلی همه المان­های لازم A و x را دارد و این عمل کاملاً موازی است: همه پردازشگرها می­تواند بلافاصله کار را شروع کند، و اگر بار کار تقریبا برابر باشد، پردازشگر­ها کار را همزمان تمام می­کنند. در اینصورت مجموع زمان ضرب بردار – ماتریس بر تعداد پردازشگر تقسیم می­شود، و افزایش سرعت کمابیش تمام و کمال خواهد بود.

حالا حل روبه جلو Lx = y را در نظر بگیرید، برای مثال در مورد پیش­شرط ساز ILU:

 

می­توان به راحتی کد موازی را نوشت:

 

 اما حالا یک مسئله وجود دارد. دیگر نمی­توانیم بگوییم "فرض کنید پردازشگری کپی محلی همه چیز در سمت راست خود را دارد"، زیرا بردار x هم در سمت چپ هست و هم در سمت راست. با اینکه ضرب بردار – ماتریس در اصل در ردیف­های ماتریس کاملا موازی است، اما این کد حل مثلثی بازگشتی و در نتیجه ترتیبی است.

در بخش­های بعد استراتژی­های مختلفی برای یافتن پیش­شرط­ساز­ها خواهیم دید که در حالت موازی عملکرد متفاوتی دارند.

6.8.3. متدهای ژاکوبی بلوکی

روش­های مختلفی برای اصلاح ترتیبی بودن حل مثلثی پیشنهاد شده است. برای مثال، می­توان گفت که پردازشگرها از اجزای x که باید از پردازشگرهای د یگر بیاید، صرفنظر کنند:

 

 

 

سفارش ترجمه تخصصی تمامی رشته ها

این کار رنگ­آمیزی ما را به کجا می­برد؟ حل هنوز هم ترتیبی است . . . درست است که حلقه بیرونی بالای رنگ­ها ترتیبی است، اما همه نقاط همرنگ مستقل از همدیگر هستند، بنابراین می­توان همه آنها را همزمان حل کرد. پس اگر از تقسیم­بندی دامنه عادی استفاده کنیم و آن را با چند رنگ ترکیب کنیم (رجوع کنید به شکل 6.11)، همه پردازشگرها در طی همه مراحل رنگی فعال خواهند بود، رجوع کنید به شکل 6.12. اگر نگاهی به شکل بیاندازید می­بینید که یک پردازشگر در آخرین رنگ فعال نیست. با  تعداد زیاد گره برای هر پردازشگر این اتفاق نمی­افتد، اما ممکن است عدم تعادل بار بوجود آید.