بخشی از مقاله
چکیده
در اکثرکامپیوترهای امروزی معمولاٌیک واحد پردازشی که توان انجام یک دستورالعمل را دارد وجود دارد. همین امرباعث شده تا مسئله ای به نام همزمانی انجام امور مستقل، دردنیای کامپیوتر مطرح شود. و روزبه روزاین مسئله پررنگتر شود به طوری که امروزه اکثر زبانهای برنامه نویسی به سمت برنامه نویسی موازی و پردازش موازی درحال حرکت باشند. درهمین راستا چندین توپولوژی برای انجام کار موازی معرفی شدند . یکی ازمهمترین این توپولوژی ها، شبکه پروانه می باشد که یک ارتباط بین پردازنده ها و دیگر منابع سیستم مانندحافظه ایجادمی کند. دراین مقاله قصدداریم این شبکه رابازبان برنامه نویسی سی شارپ شبیه سازی کنیم ونحوه مسیریابی آن را نشان دهیم.
کلمات کلیدی: پردازش موازی، شبکه پروانه ، مسیریابی ، توپولوژی
-1 مقدمه
سرعت در کامپیوتر ها همیشه برای انسانها درزندگی مطرح بوده و هست. طبق قانون مور برای پیاده سازی وحدس برای بهبود ترانسیستور ها در یک بازه معین بایستی سرعت آنان نیزافزایش یابد. اما آیا نیاز به ابداع یا تقویت روش نیست ؟ تحقیقات عملی و تئوری در زمینه طراحی شبکه های درون ارتباطی بین پردازنده - حافظه برای مالتی پروسسورها ارائه شده است. هر ماژول حافظه می تواند در یک لحظه تنها به یک درخواست سرویس دهد. بنابراین درخواست های همزمان به یک حافظه توسط چندین پردازنده منجر به ازدحام حافظه خواهد شد.لذا به معرفی چند توپولوژی می پردازیم
-2توپولوژی خطی
همانطور که در شکل 1 نشان داده شده است، در توپولوژی خطی، کامپیوترها یکی پس از دیگری در یک خط به ترتیب به یکدیگر متصل شدهاند. در حالت کلی قطر یک توپولوژی خطی با n پردازنده برابر با n − 1 و درجه اتصال کامپیوترها به استثنای اولی و آخری برابر با 2 است. فاصله بین هر دو پردازنده j و i نیز همواره برابر با |i − j| است و این مقدار زمانی به حداکثر مقدار خود میرسد که پردازنده ابتدایی و انتهایی شبکه بخواهند با هم تبادل داده کنند.
-3توپولوژی حلقه
قابلیت اجرایی یک توپولوژی خطی میتواند به سادگی بدون افزایش هزینه با اضافه کردن یک پیوند ارتباطی از نخستین کامپیوتر به آخرین کامپیوتر تا حد زیادی اصلاح شود که نتیجه این کار توپولوژی حلقوی نامیده میشود. وجود همین یک پیوند ارتباطی اضافه موجب میشود که متوسط مسافت بین پردازندهها با ضریب 2 کاهش یافته و قطر توپولوژی از n − 1 به 2 کاهش بیابد. در این توپولوژی یک پیام با پیمودن حداکثر نصف طول حلقه از یک کامپیوتر به کامپیوتر دیگر خواهد رسید. درحالی که در توپولوژی خطی ممکن است یک پیام برای رسیدن به مقصد ناچار شود که از تمامی پیوندهای ارتباطی عبور کند. همانطور که در شکل 2 مشاهده میکنید، درجه اتصال تمام کامپیوترها در توپولوژی حلقوی برابر با 2 است.
-3توری دوبعدی
اگر تعداد پیوندهای ارتباطی متصل به هر کامپیوتر را افزایش دهیم، این امکان وجود دارد که قطر و متوسط تأخیر ارتباطی شبکه را کاهش دهیم. یکی از این توپولوژیها که آرایش آنها مانند یک آرایه دو بعدی یا ماتریس است، توری دو بعدی است که در شکل 3 نشان داده شده است. همانطور که مشاهده میکنید هر پردازنده به پردازندههای بالا، پایین، چپ و راست خود متصل بوده و درجه اتصال هر کامپیوتر در آن حداقل 2 و حداکثر 4 است. ساختار ماتریسی این توپولوژی موجب میشود که قطر آن بسیار کمتر از تعداد کامپیوترهای موجود در شبکه باشد. در حالت کلی در یک توری با ابعاد i × j قطر توپولوژی برابر با i + j − 2 است که در واقع حداقل فاصله بین دو پردازنده واقع در دو گوشه مخالف توری است. بنابراین یک توری دو بعدی با 2 پردازنده قطری برابر − 12 خواهد داشت. گاهی توپولوژی خطی به توری یک بعدی تعبیر میشود.
-4چنبره دوبعدی
با پیوند دادن ارتباطی بین پردازنده ابتدایی و انتهایی آن را به فرم حلقه در خواهدآمد با حلقوی کردن تمام سطرها و ستونهای یک توری به توپولوژی دیگری به نام چنبره خواهیم رسیدکه قابلیت اجرایی آن از توری بیشتر است. در این توپولوژی، درجه اتصال تمام پردازندهها برابر 4 است و در چنبرهای با ابعاد i × j با ij کامپیوتر، قطر توپولوژی برابر با 2 - i+j - خواهد بود، بنابراین یک چنبره دو بعدی با پردازنده قطری برابر 2 خواهد داشت. با تغییرات صورت گرفته، دیگر بیشترین فاصله بین دو پردازنده در دو گوشه مخالف نخواهد بود و فاصله آن دو، به 2 کاهش مییابد. درچنبره بیشترین فاصله بین پردازنده های گوشه و مرکز چنبره خواهد بود که اندازه قطر را تعیین خواهند کرد. گاهی توپولوژی حلقهای به چنبره یک بعدی تعبیر میشود. در شکل 4 یک چنبره 4×4 رامشاهده میکنید.
