انتشار (broadcast) - موازی

در پست قبل گفتیم که:

راهنمایی حل سوال:

فرض کنید می خواهیم از host داده ای را برای همه ی پردازنده ها broadcast کنیم. با یک bfs از host روی گراف (فعلا یالهای را بدون جهت در نظر می گیریم) می زنیم و یال با وزن 0 اضافه می کنیم. از آنجایی که گراف اولیه systolic بوده است و درخت (bfs) دور ندارد، پس دور با وزن 0 نداریم و گراف جدید semi-systolic است و با روش گفته شده می توانیم آن را systolic کنیم.

ثابت می کنیم که با 2 برابر کردن وزن یالها حتما می توانیم این گراف را systolic کنیم. برای این کار کافی است نشان دهیم که حداکثر نصف یالهای هر دور وزن 0 دارند. = حداکثر نصف یالهای هر دور از درخت bfs آمده اند. هر یال bfs عمق را یکی زیاد می کند و هر یال غیر bfs عمق را حداکثر یکی کم می کند. چون یک دور است باید از همان راسی که شروع کرده به همان برگردد پس تعداد یالهای bfs از غیر bfs کمتر مساوی است.

(تا آخر 1.4.5)