اطلاعیه

**mojtaba_led** · 2012-10-10T22:43:52

پاسخ : پردازش موازی

سلام مجدد

دوستان ما دو ماتریس n*n داریم ، اگه این دو ماتریس رو در هم ضرب کنیم جواب میشه یه ماتریس n*n یعنی n^2 تا درایه داره؛

خوب ما اگه برای حل این ماتریس از الگوریتم های ترتیبی استفاده کنیم نیاز به پیچیدگی زمانی با order های مختلفی که با الگوریتم های مختلفی رسیدن ،داریم ؛مثلا ( O( n^2 یعنی اگه مثلا سطر رو ستون برابر با 4 باشه با الگوریتم مورد نظر 16 time step نیاز داریم تا تمام درایه های ماتریس حاصلضرب بدست بیان .
این برای زمانی بود که ما یه پرسسور داشته باشیم که مجبور بودیم از الگوریتم های ترتیبی استفاده کنیم .

حالا ما اگه بخواهیم به صورت موازی تمام درایه ها رو محاسبه کنیم تو ساده ترین حالت داریم :

1.خوب ماتریس حاصلضرب n^2 درایه داره
2. برای محاسبه هر درایه ما باید دو تا کار بکنبم : 1- حاصلضرب درایه های سطر در ستون رو محاسبه کنیم (به تعداد n تا) و بعد اینها رو با هم جمع کنیم با یه حساب سرانگشتی میفهیمیم که اولا ما برای محاسبه هر درایه دو عمل رو باید به صورت ترتیب انجام بدیم یعنی اول حاصل ضرب ها رو بدست بیاریم و بعد حاصل جمع ، اما حاصل ضرب ها میتونن موازی انجام بشن پس برای n جفت درایه با n پرسسور میتونیم توی یک time step حاصل ضرب ها رو بدست بیاریم ، و برای محاسبه جمع هم میتونیم با n/2 پرسسور توی log n واحد زمانی حاصل جمع ، ضرب ها رو بدست بیاریم ، پس در کل برای محاسبه هر درایه توی log n +1 واحد زمانی (تو این الگوریتم) حداقل نیاز به n پرسسور داریم .

از طرفی ما میتونیم تمام درایه ها رو به صورت موازی با هم بدست بیاریم (با صرف نظر از تداخل در خوندن مقادیر درایه ها از حافظه توسط چند پرسسور به صورت هم زمان) ،خوب ما n^2 تا درایه داریم ، هر درایه برای محاسبه به n پرسسور نیاز داشت پس برای محاسبه کل درایه ها به صورت موازی برای حل ماتریس توی log n+1 واحد زمانی نیاز به n^3 پرسسور داریم !

خوب حالا سوال من اینه که چکار کنیم ، چه الگوریتمی استفاده کنیم تا این n^3 پرسسور به n^3/log n تقلیل پیدا کنه ، بدون این که پیچیدگی زمانی زیاد بشه ، یعنی محاسبه کل ماتریس تو همون log n واحد زمانی انجام بشه ؟

اطلاعیه

پردازش موازی

پردازش موازی

دیدگاه