مقاله ترجمه شده رشته ریاضی - ترجمه تخصصی

استراتژی­های مر تب­سازی و موازی­سازی

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

 

برای ثبت سفارش ترجمه تخصصی، کلیک کنید

 

شکل 6.12. حل ILU چند رنگ موازی در چهار مرحله.

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

6.9.1. تشریح تو در تو

چند مثال از مرتب کردن متغیرها در دامنه علاوه بر مرتب کردن واژگانی را در بالا دیدید. در این بخش مرتب کردن با تشریح تو در تو بررسی می­شود که در ابتدا به عنوان راهی برای کاهش شرح دادن ایجاد شد. اما این روش در زمینه محاسبه موازی نیز مفید است.

 

شکل 6.13. تشریح دامنه به دو زیردامنه تو در تو غیرمتصل و یک جدا کننده.

تشریح تو در تو (Nested dissection) فرآیندی بازگشتی برای تعیین ترتیب مجهول­ها در دامنه است. در مرحله اول، دامنه محاسبه به دو قسمت تقسیم می­شود، و نوار تقسیم بین این دو قرار می­گیرد؛ رجوع کنید به شکل 6.13). برای اینکه دقیق باشد، جدا کننده  به اندازه کافی عریض است تا ارتباطی بین زیردامنه چپ و راست وجود نداشته باشد. ماتریس حاصل A^DD ساختار 3 × 3  دارد، که معادل با سه قسمت دامنه است. چون زیر دامنه Ω₁ و Ω₂ به هم وصل نیستند، زیرماتریس A₁₂^DD و A₂₁^DD صفر است.

 

این فرآیند تقسیم دامنه بوسیله جدا کننده تجزیه دامنه یا زیرساخت دامنه نامیده می­شود، اگرچه این نام با تحلیل ریاضی ماتریس­های حاصل نیز مرتبط است [10]. در این مثال دامنه چهارگوش، یافتن جداکننده اهمیتی ندارد. با این حال، برای نوع معادلاتی که از BVPها بدست آمد همیشه می­توان جدا کننده را به طور موثری برای هر دامنه­ای یافت [115]؛ رجوع کنید به بخش 20.5.1.

حالا فاکتورگیری LU از این ماتریس را در نظر بگیرید. اگر برحسب ساختار بلوک 3 × 3 از آن فاکتورگیری کنیم، داریم

 

که در آن

S₃₃ = A₃₃ – A₃₁A₁₁^-1A₁₃ – A₃₂A₂₂^-1A₂₃

در اینجا واقعیت مهم این است که

• سهم   A₃₁A₁₁^-1A₁ و  A₃₂A₂₂^-1A₂₃ را می­توان همزمان محاسبه کرد، بنابراین فاکتورگیری تا حد زیادی موازی است؛ و
•  درحل رو به جلو و حل رو به عقب، مولفه 1 و 2 حل را می­توان همزمان محاسبه کرد، بنابراین فرآیند حل نیز تا حد زیادی موازی است.

ممکن است کار با بلوک سوم به صورت موازی ساده نباشد، بنابراین این امر مولفه ترتیبی به الگوریتم اضافه می­کند. هم چنین باید ساختار S₃₃ را به دقت بررسی کنیم.

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

نتیجه این است که با حذف همه متغیرها در بلوک 1 و 2، ماتریس S₃₃ کاملا متراکم در اندازه n × n برجای می­ماند.

افزودن جدا کننده منجر به فاکتورگیری می­شود که موازی دوطرفه است. حالا این فرآیند را تکرار می­کنیم: جدا کننده­ای داخل بلوک 1 و 2 قرار می­دهیم (شکل 6.14)، که ساختار ماتریس زیر بدست می­اید:

 

شکل 6.14: تجزیه دامنه چهارطرفه.

 

(به شباهت­های بین ماتریس "فلش" در بخش 5.4.3.4 توجه کنید و این امر را که منجر به پر کردن کمتری می­شود، به خاطر آورید.) فاکتورگیری LU این عبارت است از:

برای ثبت سفارش ترجمه تخصصی، کلیک کنید

که در آن

 

حالا ساخت فاکتورگیری به ترتیب زیر است:

• بلوک­های A_ii به صورت موازی برای i = 1, 2, 3, 4 فاکتورگیری می­شود؛ همین­طور سهم A_5i, A_ii^-1A_i7 برای i = 1, 2، A_ii^-1A_i6 برای i = 3, 4، و A_7iA_ii^-1A_i7 برای i = 1, 2, 3, 4 می­توان به صورت موازی ساخت.
• ماتریس­های مکمل Schur، S₅, S₆ شکل می­گیرد و سپس به صورت موازی فاکتورگیری می­شود و سهم A_7iA_i^-1 برای i = 5,6 به صورت موازی ساخته می­شود.

همانند توجیه بالا می­توان نتیجه گرفت که بعد از حذف بلوک 1, 2, 3, 4 ماتریس به روز شده S₅, S₆ متراکم و با اندازه n/2 است، و بعد از حذف بلوک 5,6 ماتریس مکمل Schur، S₇ ماتریس متراکم در اندازه n است.

تمرین 6.25. نشان دهد که حل سیستمی با A^DD موازی سازی شبیه به ساخت فاکتورگیری دارد که در بالا توضیح داده شد.

برای ارجاع بیشتر، مجموعه 1 و 2 را خواهر برادر می­نامیم، و 3 و 4 را نیز همین­طور. مجموعه 5 والد 1 و 2 است، 6 والد 3 و 4 است؛ 5 و 6 خواهر و برادر هستند و 7 والد 5 و 6 است.

6.9.1.1. تجزیه دامنه

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

• پردازش موازی زیردامنه­ها، هم در فاکتورگیری  و م در حل L, U، و
• سیستمی برای حل در ساختار جدا کننده.  

 

شکل 6.15. تجزیه یکطرفه دامنه

تمرین 6.26. ماتریس حاصل از BVP دو بُعدی ساختار بلوکی سه قطری خواهد داشت. دامنه را به چهار نوار تقسیم کنید، یعنی با استفاده از سه جدا کننده (رجوع کنید به شکل 6.15). توجه داشته باشید که جدا کننده­ها در ماتریس اصلی به هم وصل نیستند.

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

6.9.1.2 پیچیدگی

متد تشریح تو در تو فرآیند بالا را تکرار می کند تا زیردامنه ها خیلی کوچک شوند. برای تحلیل نظری، تقسیم را ادامه می­دهیم تا اندازه زیر دامنه­ها 1 × 1 شود، اما در عمل می­توان در اندازه­های مثل 32 توقف کرد، و حل کننده متراکم موثری برای فاکتورگیری و وارونه کردن بلوک­ها بکار برد.

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

• یک ماتریس متراکم در جدا کننده در اندازه n، به اضافه
• دو ماتریس متراکم در جدا کننده­ها در اندازه n/2،
• فضای 3/2n² و زمان 5/12n³؛
• دو جمله بالا در چهار زیر دامنه در اندازه (n / 2) × (n / 2) تکرار می­شود؛

با مشاهده اینکه n= N  است، داریم

 

ظاهراً حالا فاکتورگیری داریم که تا حد زیادی موازی است، و در O(N log N) به جای O(N^3/2) انجام می­گیرد (رجوع کنید به بخش 5.4.3.3). زمان فاکتورگیری نیز از O(N²) به O(N^3/2) کاهش می­یابد.

متاسفانه این صرفه­جویی در فضا فقط در دو بُعد روی می­دهد: در سه بعد موارد زیر لازم است:

• یک جدا کننده در اندازه n × n، با فضای (n × n)² = N^4/3 و زمان 1/3 . (n × n) = 1/3.N²،
• دو جدا کننده در اندازه n/2 ×  n، با فضای N^3/2/2 و زمان 1/3 . N²/4،
• که بالغ بر 7/4N^3/2 فضا و 21 / 16N² /3 زمان می­شود؛
• در سطح بعدی 8 زیردامنه وجود دارد که با n → n/2 به این جملات کمک می­کند و در نتیجه N→N/8.

در نتیجه مجموع فضا عبارت است از

 

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

 

حالا دیگر صرفه­جویی بسیار بالای مورد دو بعدی را داریم. تحلیل پیچیده­تر نشان می­دهد که بهبودی مرتبه در مسائل کلی در دوبُعد حاصل می­شود. و به طور کل سه بُعدی پیچیدگی بالاتری دارد [114].

6.9.1.3. موازی­سازی

متد تشریح تو در تو به وضوح موازی­سازی زیادی را ایجاد می­کند و ما می­توانیم آن را کار موازی­سازی عنوان کنیم (بخش 2.5.3): در رابطه با هر جدا کننده کار فاکتورگیری ماتریس­های آن وجود دارد، و فاکتورگیری با حل سیستم خطی بر اساس متغیرهای آن است. با این حال، این کارها مستقل از هم نیستند: در شکل 6.14 فاکتورگیری در دامنه 7 باید منتظر 5 و 6 بماند و آنها نیز باید منتظر 1, 2, 3, 4 باشند. بنابراین کارهای مرتبط به هم به شکل درختی وجود دارد: هر ماتریس جداکننده فقط زمانی قبل فاکتورگیری است که فرزندان آن فاکتورگیری شده باشد.

برای ثبت سفارش ترجمه تخصصی، کلیک کنید

ترسیم این کارها در پردازشگر ساده نیست. اولاً اگر با حافظه مشترک سر و کار داریم می­توانیم از صف داده­ها (داده رج یا داده هایی که به نوبت پردازش می شوند) ساده کار استفاده کنیم:

Queue ←{}

برای همه زیردامنه­های سطح کف d

d را به Queue اضافه کنید

در حالیکه Queue خالی نیست

اگر پردازشگر بیکار است، در اینصورت

کار قرار گرفته در صف داده را را آن اختصاص دهید

اگر کار پایان یافت و خواهر و بردارش پس از آن پایان یافت

آن را به والدش در صف داده اضافه کنید

 

مسئله اصلی در اینجا این است که در نقطه­ای تعداد پردازشگر بیشتر از کار می­شود، در نتیجه عدم تعادل بار پیش می­آید. این مسئله با این واقعیت تشدید می­شود که کارهای آخر مهم ترین کار نیز هستند، زیرا اندازه جدا کننده­ها از سطحی به سطح دیگر دو برابر می­شود. (به خاطر داشته باشید که کار فاکتورگیری ماتیس متراکم با توان سوم اندازه پیش می­رود!) بنابراین برای جدا کننده­های بزرگتر باید از موازی­سازی کار به موازی­سازی حد متوسط تغییر دهیم، که در آن پردازشگرها در فاکتورگیری بلوک همکاری می­کنند.

حالا با حافظه توزیع شده، می­توان مسئله موازی­سازی را با صف داده کار ساده انجام داد، زیرا جابجایی مقادیر زیاد داده را دربرمی­گیرد. (اما به خاطر داشته باشید که کار توان بالاتری از اندازه ماتریس است، که اینبار به نفع ما عمل می­کند، و ارتباط را نسبتاً ارزان می­سازد.) بنابراین راه حل استفاده از شکلی از تجزیه دامنه است. در شکل 6.14 می­توانیم چهار پردازشگر داشته باشیم که با بلوک 1,2,3,4 مرتبط هستند. پردازشگر 1 و2 باهم گفتگو می­کنند که یکی بلوک 5 را فاکتورگیری کند (و همین طور پردازشگر 3 و 4 و بلوک 6)، یا هر دو اینکار را به صورت زائد انجام می­دهند.  

6.9.1.4. پیش­شرط سازی

همانند همه فاکتورگیری­ها، می­توان متد تشریح تو در تو را با فاکتورگیری ناقص به پیش­شرط سازی تبدیل کرد. (برای نظریه اصلی درباره فاکتورگیری، رجوع کنید به بخش 5.5.5.1). با این حال، در اینجا فاکتورگیری کاملاً برحسب ماتریس­های بلوکی تنظیم می­شود، و تقسیم براساس المان محوری به حل معکوس یا سیستم با ماتریس بلوکی محوری تبدیل می­شود. بیش از این به جزیئات نمی­پردازیم و برای جزئیات بیشتر می­توانید رجوع کنید به [4, 50, 125].

6.9.2. ثبت و رنگ آمیزی متغیر: مجموعه­های غیروابسته

جایشگت دیگر متغیرهای مسئله براساس رنگ­امیزی گراف است (بخش 20.3). اینجا هدف اصلی حداکثرسازی موازی­سازی موجود است.

مثال ساده ای را در نظر بگیرید که در آن A ماتریس سه قطری است. معادله Ax = b به شکل زیر است:

 

 

شکل 6.16. ترتیب قرمز – سیاه نقاط روی خط

مشاهده می­کنیم که x_i مستقیماً به x_i-1 و x_i+1 وابسته است، اما به x_i-2 یا x_i+1 وابسته نیست. بنابراین بررسی می­کنیم که اگر اندیس­ها را برای دسته­بندی مولفه­ها به صورت یک درمیان جایگشت کنیم، چا اتفاقی می­افتد.

نقاط 1, . . ., n را در نظر می­گیرم و آنها را قرمز و سیاه رنگ می­کنیم (شکل 6.6)، سپس آنها را جایگشت می­کنیم تا ابتدا نقاط قرمز و سپس همه نقاط سیاه را بدست آوریم. ماتریس جایشگتی معادل به شکل زیر خواهد بود:

 

با این ماتریس جایگشتی A، ماتریس گاوس-Seidel، D_A + L_A به این شکل خواهد بود:

 

این چه معنایی برای ما دارد؟ حل سیستم Lx = y را اینگونه می­توان بیان کرد.

برای i = 1, 3, 5, . . .

x_i ← y_i / a_{ii ر}ا حل کنید

برای i = 2, 4, 6, . . .

t = a_{ii – 1}x_{i – 1} + a_{ii + 1} x_{i + 1} را محاسبه کنید

(x_i ← y_i / - t) / a_ii را حل کنید

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

 

شکل 6.17: راه حل قرمز – سیاه در دامنه تک بعدی

 

شکل 6.18. حل قرمز-سیاه موازی در دامنه تک بعدی

 

ترتیب قرمز – سیاه را می­توان برای مسائل دوبعدی نیز بکار برد. حالا ترتیب قرمز – سیاه را برای نقاط (i, j) بکار می­بریم که 1 ≤ i, j ≤ n است. در اینجا ابتدا شماره­گذاری متوالی برای نقاط فرد در سطر اول بکار می­بریم یعنی، (1, 1), (3, 1), (5, 1), . . .,، سپس نقاط زوج سطر دوم (2, 2), (4, 2), (6, 2), . . .، نقاط فرد در سطح سوم؛ و غیره. بنابراین با شماره­گذاری نصف نقاط در دامنه، با نقاط زوج در سطر اول، نقاط فرد در سطر دوم و غیره ادامه می­دهیم. به طوریکه در شکل 6.19 می­بینید، حالا نقاط قرمز فقط به نقاط سیاه متصل هستند. از لحاظ تئوری، رنگ­امیزی (رجوع کنید به ضمیمه 20 برای تعریف این مفهوم) گراف ماتریس با دو رنگ را بدست آورده­اید.

تمرین 6.27. ترتیب قرمز – سیاه را برای BVP دو بعدی بکار برید. ساختار ماتریس حاصل را رسم کنید.

ترتیب قرمز-سیاه مثالی ساده از رنگ­آمیزی گراف است (گاهی چند رنگی نامیده می­شود). در موارد ساده­ای مثل دامنه مربع واحد که در بخش 4.2.3 بررسی کردیم، یا مدل 3 بعدی آن، تعداد رنگ گراف مجاورت به راحتی تعیین می­شود.

تمرین 6.28. دیدید که ترتیب قرمز – سیاه مجهول­ها همراه با استنسیل (شابلون) ستاره پنج نقطه­ای معمولی دو زیرمجموعه از متغیرها می­دهد که به هم متصل نیستند، یعنی دو رنگ گراف ماتریس را شکل می­دهند. اگر گره­ها با استنسیل دوم در شکل 4.3 به هم  وصل شوند، آیا می­توانید رنگ­آمیزی را پیدا کنید؟.برای ثبت سفارش ترجمه تخصصی، کلیک کنید

 

شکل 6.19. ترتیب قرمز – سیاه متغیرها در دامنه دو بعدی

برای تعداد رنگ­های لازم برای گراف ماتریس اسپارس محدودیت ساده­ای وجود دارد: تعداد رنگ­ها d + 1 است که d درجه گراف است. برای اینکه ببینید می­توان گراف را با درجه d با استفاده از d + 1 رنگ، رنگ­آمیزی کرد، گرهی با درجه d را در نظر بگیرید. مهم نیست همسایه­های آن چه رنگی هستند، همیشه رنگ استفاده شده در میان d + 1 رنگ وجود دارد.

تمرین 6.29. ماتریس اسپارس در نظر بگیرید که در آن می­توان گراف را باا d رنگ رنگ­آمیزی کرد. ماتریس را با شماره­ گذاری مجهول­های رنگ اول، سپس رنگ دوم و به همین ترتیب، جایگشت کنید. درباره الگوری اسپارسی ماتریس جایگشتی حاصل چه می­توان گفت؟

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

6.10. تسهیم عملگر

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

 

بدون اثبات، می­گوییم که مسئله وابسته زمان را نیز می­توان با

 

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

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

تمرین 6.30. مزایای نسبی این روش­ها را با توجه به تعداد عمل  تحلیل کنید. موردی را در نظر بگیرید که α به t وابسته است و موردی که وابسته نیست. هم چنین سرعت مورد انتظار عملیات مختلف را بررسی کنید.

مزیت دیگر زمانی است که حل موازی (6.3) را در نظر می­گیرید. توجه داشته باشید که مجموعه دو بعدی از متغیرهای u_ij داریم، اما عملگر I + d²u/dx² فقط u_ij, u_ij-1, u_ij+1 را مرتبط می­کند. یعنی هر لینک معادل با مقدار i به صورت مستقل قابل پردازش است. بنابراین هر دو عملگر را می­توان با استفاده از تقسیم تک بعدی در دامنه به صورت موازی حل کرد. از سوی د یگر حل سیستم در (6.2) موازی­سازی محدود دارد.

متاسفانه، پیچیدگی جدی وجود دارد: عملگر در جهت x به تقسیم دامنه در آن جهت نیاز دارد، و عملگر در جهت y به تقسیم دامنه در جهت دیگر نیاز دارد. راه حلی که معمولاً انتخاب می­شود ترانهادن ماتریس مقدار u_ij در بین دو حل است، تا تجزیه یک پردازشگر از عهده هر دو برآید. این ترانهش (جابجاسازی) ممکن است میزان زیادی از زمان پردازش را در هر مرحله بگیرد.

تمرین 6.3.1. مزایا و مسائل تجزیه دو بعدی دامنه را با  استفاده از شبکه پردازشگر P = p × p بحث کنید. می­توانید راهی برای رفع این مسائل پیشنهاد کنید؟

یکی از راههای افزایش سرعت این محاسبات این است که عمل صریح جایگزین حل ضمنی شود؛ رجوع کنید به بخش 6.11.3.

 

 

 

 

 

6.11. موازی­سازی و عملیات ضمنی

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

تمرین 6.32. A را ماتریس

بگیرید. نشان  دهید که ضرب بردار ماتریس y ← Ax و حل x ← A^-1y، که با حل سیستم مثلثی ax = y بدست آمد، نه با معکوس کردن A، تعداد عمل برابر دارند.

شکل 6.20. استنسیل تفاوت فاکتور L ماتریس BNP دو بعدی

حالا موازی­سازی ضرب y ← Ax را در نظر بگیرید. فرض کنید n پردازشگر داریم، و هر پردازشگر i ردیف iام A را ذخیره می­کند. نشان دهید که ضرب Ax را می­توان بدون زمان بیکاری در هیچ یک از پردازشگرها به جز اولی محاسبه کرد.

آیا می­توان همان روش را برای حل سیستم مثلثی Ax = y بکار برد؟ نشان دهید که در اجرای مستقیم هر پردازشگر برای (n – 1) / n زمان محاسبه بیکار است.

حالا برخی روش­های پرداختن به این مولفه ذاتاً ترتیبی را بررسی می­کنیم.

6.11.1. جبهه موج

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

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

دوباره به شکل 4.1 نگاه کنید که استنسیل اختلاف BVP دو بعدی را توصیف می­کند. تصویر معادل برای فاکتور مثلث پایین در شکل 6.20 است. این شکل ترتیبی بودن فرآیند حل مثلث پایین را توصیف می­کند x←L^-1y:

 x_k= y_k- l_k-1- x_k-1l_k,k-nx_k-n

به عبارت دیگر، مقدار در نقطه k را می­توان در صورتی یافت که همسایه­های سمت چپ (یعنی متغیر k – 1) و زیر (متغیر k – n) معلوم باشد.

می توان دید که اگر x₁ معلوم باشد، علاوه بر x₂، می­توان x_n+1 را نیز یافت. در مرحله بعد می­توان x₃, x_n+2 و x_2n+1 را  تعیین کرد. با ادامه این فرآیند می­توان x را با جبهه­های موج حل کرد: مقادیر x در هر جبهه موج مستقل از هم است، بنابراین می­توان آنها را به صورت موازی در مرحله ترتیبی یکسان حل کرد.

تمرین 6.34. این استدلال را تمام کنید. حداکثر تعداد پردازشگری که می توان بکار بست، چند تاست، و تعداد مراحل ترتیبی چندتاست؟ راندمان حاصل چقدر است؟

در بخش 5.4.3.5 مرتب­سازی Cuthill-McKee برای کاهش پر کردن ماتریس را دیدید. می توان این الگوریتم را تعدیل کرد تا جبهه­های موج بدست آید:

1. یک گره دلخواه انتخاب کنید و "سطح صفر" را فرا بخوانید.
2. برای سطح n + 1، نقاط متصل به سطح n را پیدا کنید که خودشان متصل نیستند.
3. برای "مرتب­سازی معکوس Cuthill –McKee" معروف، شماره­گذاری سطوح را معکوس کنید.

تمرین 6.35. این الگوریتم اصلا درست نیست. مسئله چیست؛ چگونه می­توان آن را اصلاح کرد؟ نشان دهید که ماتریس جایگشتی حاصل دیگر سه قطری نیست، اما ممکن است هنوز ساختار نواری را داشته باشد.

6.11.2. دو برابر سازی بازگشتی

یکی از استراتژی­ها برای پرداختن به بازگشتی بودن، دو برابر سازی بازگشتی است، که در تمرین 1.4 دیدید. در اینجا این استراتژی را به صورت سیستماتیک­تر بررسی می­کنیم. ابتدا ماتریس (6.4) را در نظر بگیرید کنید و آن را مقیاس­گذاری کنید تا به شکل

باشد که به صورت A = I + B می­نویسیم.

تمرین 6.36. حل سیستم (I + B)x = y چه کمکی به Ax = y می­کند؟ تعداد عمل حل کردن سیستم به دو روش متفاوت چندتاست؟

کاری که حالا انجام می­دهیم شبیه به حذف گاوسی است، به جز اینکه با ردیف اول شروع نمی­کنیم، بلکه با ردیف دوم شروع می کنیم. (اگر حذف گاوسی انجام می­دادید یا تجزیه LU در ماتریس I + B انجام می­دادید، چه اتفاقی می افتاد؟) از ردیف دوم برای حذف b₃₂ استفاده می کنیم:

که به صورت L⁽²⁾A = A⁽²⁾ می­نویسیم. هم چنین L⁽²⁾ y = y⁽²⁾ را محاسبه می­کنیم به طوریکه A⁽²⁾ x = y⁽²⁾ همان جواب Ax = y را داشته باشد. حل سیستم تبدیل شده اندکی برای مفید است: بعد از محاسبه x₁, x₂ و x₃ را می­توان به صورت موازی محاسبه کرد.

حالا این فرآیند حذف را با استفاده از ردیف چهارم برای حذف b₅₄، ردیف ششم برای حذف b₇₆، و غیره، تکرار می­کنیم. نتیجه نهایی جمع همه ماتریس­های L⁽ⁱ⁾ است:

که به صورت L(I + B) = C می نویسیم، و با حل (I + B)x = y  داریم Cx = L^-1y.

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

• اولاً محاسبه y’ = L^-1y ساده است. (جزئیات را کار کنید. چه میزان موازی­سازی وجود دارد؟)
• حل Cx = y’ هنوز ترتیبی است، اما دیگر n مرحله طول نمی­کشد: از روی x₁ می­توان x₃ را بدست آورد، از روی آن x₅ را بدست می­آوریم، و همین طور ادامه می یابد. به عبارت دیگر، فقط رابطه ترتیبی بین مولفه­های x با شماره فرد وجود دارد.
• مولفه­های x با شماره زوج به همدیگر وابسته نیستند، بلکه فقط به مولفه­های فرد وابسته­اند: x₂ از روی x₁ بدست می­آید، x₄ از روی x₃ بدست می­آید و غیره. وقتی مولفه­های فرد محاسبه شد، مسلماً به صورت ترتیبی، این مرحله کاملا موازی است.

می­توان حل ترتیبی مولفه­های فرد را اینگونه توصیف کرد:

که در آن c _i+1i = - b_2n+1,2nb_2n,2n-1. به عبارت دیگر، اندازه مسئله ترتیبی در اندازه n را به مسئله ترتیبی در نوع اندازه و مسئله موازی کاهش دادیم که اندازه هر دو n / 2 است. حالا می­توان این فرآیند را به صورت بازگشتی تکرار داد، که مسئله اصلی را به عملیات موازی ترتیبی کاهش می­دهد، و  هر یک نصف اندازه قبلی است.

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

6.11.3. تقریب عملیات ضمنی با صریح، بسط سری

به دلایل متعددی گاهی می­توان عملیات ضمنی را، که در بالا دیدید و ممکن است در عمل مشکل­ساز باشد، با عملیات ضمنی متفاوتی جایگزین کرد که عملاً مفیدتر است.

• بکارگیری متدی صریح برای معادله گرما (بخش 4.3) به جای معادله ضمنی با رعایت محدودیت­های اندازه مرحله در متد صریح درست است.
• ایجاد تغییر و سرهمبندی با پیش شرط ساز (بخش 5.5.7) در متد تکراری مجاز است، زیرا فقط سرعت همگرایی را تحت تاثیر قرار می­دهد، نه حلی که متد به آن همگراست. قبلا مثال این نظر کلی را در متد ژاکوبی بلوک دیدید؛ بخش 6.8.3. در ادامه این بخش خواهیم دید که می­توان بازگشتی­ها (رکورانس) در پیش شرط ساز را، که عملیات ضمنی است، با عملیات صریح جایگزین کرد که مزایای محاسباتی مختلفی فراهم می­کند.
• حل سیستم خطی مثال خوبی از عمل ضمنی است و چون در ادامه برای حل دو مسئیه مثلثی بکار می­رود، بهتر است راههای یافتن جایگزین محاسباتی برای حل سیستم مثلث پایین بررسی کنیم. اگر U مثلث بالا و منفرد است، D را قطر U می­گیریم، و می­نویسیم U = D(I – B) که در آن B ماتریس مثلث بالا با قطر صفر است، که ماتریس دقیقاً مثلث بالا نامیده می­شود؛ می­گویی I – B ماتریس مثلث منفرد بالا است.

تمرین 6.37. A = LU را فاکتورگیری LU بگیرید که در آن L در قطر یک هایی دارد. نشان دهید که چگونه می­توان سیستم Ax = b حل کرد.   

حال عمل مورد نظر ما حل سیستم (I – B)x = y است. مشاهده می­کنیم که

 (I-B)^-1=I+B+ B²+ . . .                           (6.5)

 و Bⁿ = 0 است که n اندازه ماتریس است (این را بررسی کنید!)، بنابراین می­توان (I – b)x = y را دقیقاً با  رابطه زیر حل کرد:

البته می­خواهیم از محاسبه توان­های B^k به صورت صریح اجتناب کنیم، بنابراین مشاهده می­کنیم که

الگوریتم حاصل برای ارزیابی  _k=0^n-1B^ky  قانون هورنر (Horner) نامیده می شود، و می­بینید که از محاسبه توان­های ماتریس B^k اجتناب می­کند.

تمرین 6.38. فرض کنید I – B دو قطری است. نشان دهید که محاسبات بالا n(n + 1) عمل طول دربرمی­گیرد. تعداد عمل محاسبه (I – B)x = y با حل مثلثی چندتاست؟

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

تمرین 6.39. A را ماتریس سه قطری

BVP  تک بعدی در بخش 4.2.2 بگیرید.

1. تعریف ماتریس با قطر غالب را در بخش 5.3.4 به خاطر آورید. آیا این ماتریس با قطر غالب است؟
2. نشان د هید که محورها در فاکتورگیری این ماتریس (بدون محورگیری) با بازگشت مطابقت د ارد. راهنمایی: نشان دهید که بعد از n مرحله حذف (n ≥ 0) ماتریس باقیمانده به این شکل خواهد بود،

و رابطه بین d_n+1 و d_n را پیدا کنید.

3. نشان دهید که ترتیب n → d_n صعودی است، و مقدار حد را بدست آورید.
4. فاکتور L و U را برحسب محورهایd_n  بنویسید.
5. آیا فاکتور L و U غالب قطری هستند؟

تمرین بالا بر این دلالت دارد (توجه داشته باشید که آن را اثبات نکردیم) برای ماتریس­های حاصل از BVPها دریافتیم که B^k↓ 0 از نظر اندازه المان و هنجار. یعنی می­توان تقریب حل (I – B)x = y با مثلا با x= (I +B) y یا x = (I + B + B²)y بدست آرود. انجام اینکار تعداد عمل بیشتری از حل مثلثی مستقیم دارد، اما از نظر محاسباتی حداقل به دو جهت مفید است:

• الگوریتم صریح رفتار خط لوله بهتری دارد.
• الگوریتم ضمنی در موازی مسائلی دارد، که دیدید؛ الگوریتم صریح به راحتی موازی­سازی می شود.

البته این ممکن است این تقریب دلالت­های دیگری هم برای پایایی کل الگوریتم عددی داشته باشد.

تمرین 6.40. جنبه­های موازی سازی قانون هورنر را توضیح دهید؛ معادله (6.6).

6.12. آپدیت­های شبکه

یکی از نتیجه­گیری­های فصل 4 این بود که متدهای صریح برای مسائل وابسته زمان از نظر محاسباتی راحت­تر از متدهای ضمنی هستند. برای مثال، معمولا بیشتر ضرب بردار – ماتریس را در برمی­گیرند تا حل سیستم، و موازی­سازی عملیات صریح کاملا ساده است: هر مقدار نتیجه ضرب بردار – ماتریس را می­توان جداگانه محاسبه کرد. این به این معنی نیست که جنبه­های دیگر قابل توجه نیست.

چون ما ماتریس­های اسپارس را بررسی می­کنیم، که از استنسیل محاسباتی ریشه می­گیرند، دیدگاه اپراتور را اتخاذ می­کنیم. در شکل 6.7 و 6.8 دیدید که بکارگیری استنسیل در هر نقطه از دامنه موجب روابط معینی بین پردازشگرهای می­شود: برای ارزیابی ضرب بردار – ماتریس y ← Ax در پردازشگر، آن پردازشگر باید مقادیر x منطقه روح خود را بدست آورد. با فرض­های توجیه پذیر درباره تقسیم بندی دامنه برای پردازشگرها، تعداد پیام­ها کاملا پایین خواهد بود.

تمرین 6.41. توجیه کنید که در FEM یا FDM، تعداد پیام­ها O(1) با h ↓ 0 است.

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

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

و فرض کنید که مجموعه {x_i⁽ⁿ⁾}_i خیلی بزرگ است و در حافظه نهانی جا نمی­گیرد. برای مثال، این مدلی برای طرح صریج گرما در یک بُعد فضاست؛ رجوع کنید به بخش 4.3.1.1. به صورت شماتیک داریم:

در محاسبه معمولی، که ابتدا کل x_i^{(n + 2)} را محاسبه می­کنیم، مقادیر میانی در سطح n + 1 بعد از اینکه ایجاد شدند از حافطه نهانی خارج می­شوند و سپس به عنوان ورودی برای مقادیر سطح n + 2 دوباره به حافظه نهانی بازگردانده می­شوند.

با این حال، اگر به جای یک تکرار دو  تکرار را محاسبه کنیم، ممکن است مقادیر میانی در حافظه نهانی بمانند. x₀⁽ⁿ⁺²⁾ را در نظر بگیرید: به x₀⁽ⁿ⁺¹⁾, x₁⁽ⁿ⁺¹⁾ نیاز دارد که آن هم به x₀⁽ⁿ⁾, . . ., x₂⁽ⁿ⁾ نیاز د ارد.

حالا فرض کنید نتایج میانی مورد نظر ما نیست بلکه فقط تکرار نهایی مد نظر ماست. شگل 6.21 مثالی ساده را نشان می­هد. پردزشگر اول 4 نقطه را در سطح n + 2 محاسبه می کند. برای اینکار به 5 نقطه از سطح n + 1 نیاز  دارد، و اینها نیز باید از روش 6 نقطه در سطح n محاسبه شوند. می توان دید که پردازشگر باید منطقه روح به عرض دو را باید گردآوری کند، برخلاف عرض یک برای به روزسازی تک مرحله­ای معمولی. یکی از نقاطی که توسط پردازشگر اول محاسبه می­شود x₃^{(n + 2)} است که به x₄^{(n +1)} نیاز د ارد. این نقطه برای محاسبه x₄⁽ⁿ⁺²⁾ نیز لازم است، که به پردازشگر دوم تعلق دارد.

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

تمرین 6.42. آیا می­توان به مواردی فکر کرد که با بیش از دو پردازشگر به صورت تکراری محاسبه می­شوند؟

درباره این طرح محاسبه چند مرحله آپدیت براساس بلوک چند تفسیر می­توان ارائه کرد.

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

تمرین 6.43. استفاده از این استراتژی را برای محاسبه چند هسته­ای بحث کنید. در چه مواردی صرفه­جویی شده است؟ موانع پتانسیل کدامند؟

6.12.1. تحلیل

در اینجا الگوریتمی را که طرح کردیم تجزیه و تحلیل می­کنیم. همانند معادله (6.7) محدود به مجموعه تک بعدی از نقاط و تابعی از سه نقطه خواهیم بود. پارامترهای مسئله عبارتند از:

• N تعداد نقاطی است که به آپدیت (به رزو) می­شود، و M تعداد مراحل آپدیت را نشان می­دهد. بنابراین ارزیابی های تابع MN را انجام می دهیم.
• α، β، γ پارامترهای معمول هستند که نهفتگی، زمان انتقال یک نقطه و زمان عمل را توصیف می­کنند (در اینجا ارزیابی f گرفته شده است).
• B تعداد مراحلی است که گردهم می­آوریم.

هر ارتباط هاله­ای شامل b نقطه است، و ما این  N/b را بارها انجام می­دهیم. کاری که انجام می­گیرد شامل آپدیت­های محلی MN/p، به اضافه کار تکراری به خاطر هاله است. جمله آخر شامل b²/2 عمل است، که هم در سمت و هم در سمت راست دامنه پردازشگر انجام می­گیرد.

با جمع زدن همه این عبارت، هزینه را پیدا می­کنیم،

مشاهده می­کنیم که سربار  αM/b+γM/b غیروابسته به p است،

تمرین 6.44. مقدار مطلوب b را محاسبه کنید و تاکید داشته باشید که فقط به پارامترهای ریاضی α, β, γ وابسته است نه به پارامترهای مسئله.

6.12.2. استراتژی حداقل سازی ارتباط و کار

با اشتراک (همپوشی) محاسبه با ارتباط می توان این الگوریتم را کارآمدتر ساخت. به طوریکه در شکل 6.22 نشان داده شده است، هر پردازشگر با برقراری ارتباط با هاله خود، و هم­پوشی این ارتباط با قسمت ارتباطی که به صورت محلی امکان پذیر است، شروع می کند. مقادیری که به هاله وابسته هستند در آخر محاسبه می شوند.

شکل 6.22: محاسبه بلوک­های نقاط شبکه در چند تکرار

 

تمرین 5.45. مشکل بزرگ در سازماندهی کد (با تاکید بر "کد"!) به این شیوه چیست؟

برای ثبت سفارش ترجمه تخصصی، کلیک کنید

اگر تعداد نقاط به ازای هر پردازشگر به اندازه کافی زیاد باشد، میزان ارتباط نسبت به محاسبه پایین است، و می­توانید b را نسبتاً بزرگ بگیرید. با این حال، این آپدیت­های شبکه اغلب در متدهای تکراری مثل متد CG بکار می­روند (بخش 5.5.10)، و در این صورت ملاحظات گردکردن مانع از این می­شود که b را خیلی بزرگ بگیرید [27].

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

اصلاح بیشتر الگوریتم بالا امکان­پذیر است. شکل 6.23 نشان می دهد که می­توان از منطقه هاله استفاده کرد که از نقاط مختلف از مراحل زمانی مختلف استفاده می کند. این الگوریتم (رجوع کنید به [35]) میزان محاسبه تکراری را کاهش می دهد. با این حال، حال مقادیر هاله که در ابتدا منتقل می شوند باید محاسبه شوند، بنابراین تقسیم ارتباط محلی به دو مرحله لازم است.

شکل 6.23: محاسبه بلوک­های نقاط شبکه در چندتکرار

6.13. الگوریتم­های بلوکی در ساختارهای چند هسته­ای

در بخش 5.3.7 دیدید که الگوریتم­های خطی معینی را می­توان برحسب زیرماتریس طرح کرد. این دیدگاه می­توان برای اجرای موثر عملیات جبر خطی در ساختارهای حافظه مشترک مثل پردازشگرهای چند هسته­ای مفید باشد.

برای مثال، فاکتورگیری چولسکی (Cholesky) را در نظر بگیرید، که A = LL^t را برای ماتریس قطعی مثبت متقارن A محاسبه می­کند؛ هم چنین رجوع کنید به 5.3.2. می­توان الگوریتم را به صورت بازگشتی اینگونه توصیف کرد:

و در آن Ã₂₁ = A₂₁:₁₁^-t, A₁₁ = L₁₁L₁₁^t.

در عمل، پیاده­سازی بلوکی برای تقسیم بندی بکار می­رود

که در آن k اندیس ردیف بلوک جاری است، و فاکتورگیری برای همه اندیس­های k > پایان می­یابد. فاکتورگیری با استفاده از ا سامی Blas برای عملیات به صورت زیر نوشته می­شود:

برای k = 1، بلوک n:

کلید عملکرد موازی تقسیم­بندی اندیس­های k > است و نوشتن الگوریتم برحسب این بلوک­هاست:

 

 

حالا الگوریتم سطح دیگری از حلقه­های داخلی را می­گیرد:

حالا روشن است که الگوریتم به میزان زیادی موازی­سازی دارد: تکرارها در هر حلقه-l به صورت جداگانه قابل پردازش است. با این حال، این حلقه­ها در هر تکرار حلقه بیرونی k کوتاهتر می­شوند، بنابراین معلوم نیست که چند پردازشگر را می­توان بکار برد.بعلاوه، لزومی ندار ترتیب عملیات الگوریتم بالا حفظ شود. برای مثال، بعد از

فاکتورگیری L₂L^t₂ می­تواند شروع شود، حتی اگر بقیه k = 1 تکرار هنوز تمام نشده باشد. بنابراین احتمالاً موازی­سازی بیشتری از آنچه که می­توان با موازی­سازی حلقه داخلی بدست آورد، وجود دارد.

بهترین راه برای موازی­سازی در این مورد تغییر دیدگاه از جریان کنترل الگوریتم، که در آن ترتیب عملیات حف­ظ می­شود، به دیدگاه جریان داده است.در این حالت فقط وابستگی داده ها نشان داده می شود، و هر ترتیب عملیات که مطابق با این وابستگی­ها باشد مجاز است. (معمولا از ترتیب کارهای برنامه صرفنظر می­کنیم و ترتیب نسبی را جایگزین آن می­کنیم.) بهترین راه نشان دادن جریان داده الگوریتم با ساخت گراف غیرچرخه­ای جهت­دار کارها (Directed Acyclic Graph) (DAG) است (رجوع کنید به بخش 20 برای خلاصه­ای از گراف­ها) . اگر  کار j از خروجی کار i استفاده کند لبه (i, j) را به گراف اضافه می­کنیم.

تمرین 6.47. در بخش 2.6.1.7 مفهوم انسجام ترتیبی را یاد گرفتید: برنامه کد موازی پیچ­دار باید با اجرای موازی همان نتایج اجرای ترتیبی را دهد. ما فقط گفتیم که الگوریتم­های مبتنی بر DAG آزادند کارها را به هر ترتیبی که با ترتیب نسبی گره­های گراف مطابقت داشته باشد، انجام دهند. بحث کنید که آیا انسجام ترتیبی در این زمینه مسئله است یا نه.

ما در مثال خود DAG را با راس قرار دادن کار برای هر تکرار داخلی ساختیم. شکل 6.24 DAG همه کارهای ماتریس 4 × 4 بلوک را نشان می­دهد.

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

تمرین 6.49. فرض کنید T کار وجود دارد که همگی به زمان اجرای واحد نیاز دارد، و فرض کنید p پردازشگر داریم. حداقل زمان تئوری برای اجرای الگوریتم چیست؟ حالا در این فرمول مسیر بحرانی را در نظر بگیرید، طول آن را C بنامید.

در اجرای کارهای DAGف چندین مشاهده وجود دارد.

• اگر قرار است بیش از یک آپدیت در بلوک صورت گیرد، شاید بهتر باشد این آپدیت­ها با یک فرآیند محاسبه شود. اینکار حفظ انسجام حافظه نهانی را ساده می­کند.
• اگر داده­ها بکار می رود و سپس تعدیل می­شود، باید قبل از شروع تعدیل، استفاده پایان یابد. حتی اگر دو کار در پردازشگرهای متفاوتی صورت گیرد بازهم ممکن است این امر درست باشد، زیرا زیرسیستم حافظه معمولا انسجام حافظه نهانی را حفظ می کند، بنابراین تعدیل­ها می­تواند فرآیند خواندن داده­ها تحت تاثیر قرار دهد. این مورد را می­توان با داشتن یک کپی از داده در حافظه اصلی اصلاح کرد، که فرآیند خواندن داده­ای را می­دهد که ذخیره شده است (رجوع کنید به بخش 1.4.1).