الگوریتم های بهینه انتشار برای همبندی های مبتنی بر Mesh

چكیده

حل مسایل به صورت موازی بر روی شبکه‏ای از پردازنده‏ها به منظور افزایش سرعت اجرای الگوریتم‏ها، پژوهشگران را با چالش چگونگی برقراری ارتباط بین پردازنده‏ها روبرو می‏کند. از اینرو در سیستم‏هایی که از ارسال پیغام برای ارتباط استفاده می‏نمایند، هزینه زمانی ارسال پیغام بین پردازندها بر کارایی الگوریتم اثر می‏گذارد و بنابراین ضروری است که این هزینه حداقل باشد. در این پژوهش، مساله ارتباط بین پردازنده‏ها در همبندی‏های مبتنی بر Mesh بررسی می‏شود. ابتدا بررسی بر روی کارهای انجام شده و الگوریتم‏های ارایه شده برای انتشار پیغام در این شبکه‏ها و مقایسه آن‏ها صورت می‏گیرد و پس از آن تلاش می‏شود تا الگوریتم‏های بهینه معرفی شوند. الگوریتم‏هایی که هدف آنها کاهش زمان و منابع با حداقل کردن تعداد بسته‏های ارسالی و پیدا کردن بهترین راه ارسال می‏باشد. لذا در این مقاله یك الگوریتم ساده برای مسئله‌ی كوتاهترین مسیر تك-منبع در یك گراف مسطح با یالهای با وزن غیر‌منفی ارائه خواهیم داد.