broadcasting on hypercube

روشهای ارسال یک پیام به همه‌ی پردازنده‌ها در مدل ابرمکعب (هر پردازنده یک عدد q بیتی دارد و هر بیت آن را عوض کنیم به یک پردازنده‌ی همسایه‌ی آن می‌رسیم.)

۱- روش درخت دوجمله‌ای: در این روش یک پردازنده (مثلاً صفر) اطلاعات را به ترتیب به همسایه بعد آخر تا اول خود می‌فرستد. این پردازنده ها هم به همین ترتیب برای پردازنده‌های زیرمجموعه خود می‌فرستند.

زمان این کار به اندازه‌ی طول پیام * تعداد بیت‌های پردازنده‌ها (لگاریتم تعداد پردازنده‌ها) می‌شود.

۲- الگوریتم خط لوله درخت دوجمله‌ای (pipelined binomial tree)

در این روش به جای اینکه کل پیام را هر بار بفرستیم یک بیت پیام را می‌فرستیم و در مرحله‌ی بعد بیت بعدی و ادامه می‌دهیم تا کل پیام ارسال شود. زمان این کار به اندازه‌ی طول پیام به اضافه‌ی تعداد بیت‌های پردازنده‌ها (لگاریتم تعداد پردازنده‌ها) می‌شود.

۳- الگوریتم جانسون و هو (Johnsson & Ho)

هر بیت پیام را به پردازنده‌ی یک بعد می‌فرستد و هر کدام همین کار را ادامه می‌دهند. اگر تعداد بیت‌های پیام و تعداد بیت‌های پردازنده‌ها برابر باشد زمان این الگوریتم به اندازه‌ی تعداد بیت‌ها خواهد بود.