(۲۹ اردیبهشت ۱۳۹۵ ۰۵:۴۶ ب.ظ)irpersian20 نوشته شده توسط:  با درود
دوستان این به صورت سریال و نه حدی یعنی چی؟ یا نفصل الگوریتم های چند ریسمانی کورمن هست
ممنون ضمیمه شد

سلام.
میگه که spawn کردن بازگشتی، یعنی اینکه یک حلقه رو دو قسمت کنیم و هر کدوم از اون دو قسمت دوباره به صورت بازگشتی دو قسمت بشند و ... باعث میشه که یک سربار در مقایسه با حالت اجرای سریالی اضافه بشه. یعنی در اجرای سریال، حلقه روی اعداد ۱ تا N یک کاری میکنه، اما در موازیسازی، علاوه بر اینکه اون کارها رو باید بکنه، یک سربار عملیاتی دیگه هم برای بخش کردن حلقه به دو قسمت ۱ تا N/2 و از N/2 تا N اعمال میشه.
اون not asymptotically ربطی به serialization نداره. منظورش این هست که سرباری که اضافه میشه، مجانب یا حد خود عملیات نیست. پایینش ادامه داده. میگه هر کدوم از حلقههایی که ایجاد میشه هر کدوم حداقل یک کار ثابتی انجام میدن (یعنی حداقل O(1) که در این مثال از مرتبهی O(n) هست)، و در کل اگه K حلقه ایجاد بشه، K منهای یک عملیات بخش کردن حلقه صورت گرفته (اگر حلقههای ایجاد شده رو به صورت برگهای یک درخت دو دویی کامل در نظر بگیرید، عملیات بخش کردن همون یالهای اون درخت هستند که هر حلقه رو به دو زیر حلقهی کوچکتر تقسیم کرده، پس برای K حلقه به تعداد K-1 یال داخلی خواهیم داشت). خب K حلقه داریم که هر کدوم از مرتبهی O(n) هستند و K-1 عملیات بخش کردن که کار ثابتی انجام میدند و میشه به صورت O(1) گرفت. پس سرباری که ایجاد میشه هر چند باعث میشه نسبت به حالت اجرای سریالی یک سرباری داشته باشیم، ولی این سربار حدش کمتر از کاری هست که توسط حلقهها صورت میگیره.
پینوشت: توجه شود که این سربار نسبت به حالت اجرای سریالی، این معنی رو نمیده که سریالی سریعتر هست، بلکه به این معنی هست که وقتی مثلا آخرش ۸ قسمت میشه، سرعتی که بدست میاریم ۸ برابر نیست و مقداری هم بابت عملیات تقسیم صرف میشه. که این صرف شدن کمتر از کاری هست که توسط خود حلقهها انجام میشه. یعنی سرعت ۸ برابر نمیشه، اما ۴ برابر هم نمیشه و بیشتر از این مقدار خواهد بود (چنانچه عملیات تقسیم حلقهها به اندازه خود حلقه ها طول میکشید اون موقع ۴ برابر سرعت زیاد میشد ولی این متن خواسته این رو توضیح بده که تقسیم سربارش کم هست).