بخشی از مقاله
خلاصه
یکی از مسائل مهم در پردازش موازی ، مسیریابی پیام ها از گره مبدا به گره مقصد می باشد که توسط گره های مسیریابی انجام می شود. بن بسسسست در مسیریابی، پدیده مخربی است که در اثر وابستگی بافرها و کانالهای مسیریابی به صورت چرخه وابستگی غیر قابل حل، بوجود می آید. بسیاری از الگوریتم های مسیریابی برای مقابله با بن بست از روش های پیشگیری و اجتناب از بن بست استفاده می کنند که دراین روشها از منابع بصورت بهینه استفاده نخواهد شد زیرا در این روشها محدودیت هایی در عمل مسیریابی و استفاده از منابع، وجود دارد. اما در بسیاری ازالگوریتم های مسیریابی بدلیل اینکه بن بست به ندرت اتفاق می افتد و به جهت استفاده ناکارامد از منابع در روش پیشگیری از بن بست، از روش کشف و رفع بن بست استفاده می شود.
در این مقاله روش کشف بن بست با توجه به میانگین ترافیک هم در کانالهای ورودی و هم در کانال های خروجی در هر گره و با کمک تکنیک های فازی ارائه می شود و سعی بر این بوده که پیام هایی که به اشتباه به عنوان پیام در گیر بن بست گزارش می شوند کاهش پیدا کند و نیز حتی الامکان در هنگام بروز بن بست واقعی پیام های کمتری به عنوان پیام درگیر بن بست برای رفع بن بست معرفی شوند.
.1 مقدمه
پردازش موازی در سیستمهای مالتی کامپیوتر با استفاده از تبادل پیام است. یک روش مسیریابی رایج در مالتی کامپیوترها، مسیریابی wormhole است.[2] [1] در مسیریابی wormhole یک بسته بین گره ها در واحدهایی بنام Flit، منتقل میشود. Flit سرایند یک پیام، شامل اطلاعات مسیریابی است. و بقیهFlit هایی که پشت سر سرآیند هستند حاوی داده هستند. مسیریابی می تواند به صورت معین یا وفقی باشد.در مسیریابی معین مسیر ارتباطی بین هر دوگره مبدأ و مقصد، ثابت است اما انعطاف پذیری آن برای وفق دادن با شرایط شبکه مانند ازدحام یا خرابی کم است.
وفقیت یک ویژگی مهم است که مسیرهای جایگزین را برای بسته هایی که با کانال های مسدود، سخت افزار معیوب و...روبرو می شوند، فراهم می کند. مسیریابی معین از استفاده مؤثر اتصالات فیزیکی شبکه پیشگیری می کند. مسیریابی باقاعده کوتاهترین مسیر، بسته را در امتدادکوتاهترین مسیر هدایت می کند در نتیجه تحمل پذیری خطا کم است. اما در مسیریابی غیر کوتاه، مسیر انتخاب شده ممکن است همیشه کوتاهترین مسیر نباشد در نتیجه تحمل پذیری خطا را بهتر فراهم می کند.
در مسیریابی wormhole ممکن است پدیده بن بست رخ دهد. در واقع بن بست به جهت وابستگی کانالها و بافرها به صورت چرخه وابستگی ظاهر میشود و در این چرخه وابستگی هر کدام از پیامهای درگیر بن بست، برای ادامه مسیریابی منابعی که در اختیار پیام های دیگر چرخه است را تقاضا میکنند و این عملیات منجر به یک چرخه وابستگی غیر قابل حل در مسیریابی میشود.
در روش های پیشگیری و اجتناب از بن بست، از منابع بصورت بهینه استفاده نخواهد شد. در این روش ها مسیریابی بصورت غیر وفقی و تا حدی وفقی انجام میشود و برای پیشگیری از بن بست محدودیت-هایی در شبکه ایجاد میکنند.[4] [3] در روش های کشف و رفع بن بست مسیریابی بصورت وفقی صورت میگیرد و اجازه وقوع بن بست داده میشود .در این روش ها پیامهای درگیر بن بست تشخیص و گزارش داده میشود و سپس چرخه مربوط به بن بست برای رفع بن بست شکسته میشود.
.2 روش فازی کشف بن بست
روش های زیادی برای کشف بن بست در شبکه اتصالات چند پردازنده وجود دارد.[6] یک روش پایه برای کشف بن بست بدین صورت است که اگر یک مسیریاب نتواند پیامی را مسیریابی کند - زمانی که برای مسیریابی پیام، کانالهای خروجی مناسب آزاد نیستند - و اگر تمام کانالهای خروجی مناسب بیش از یک مهلت زمانی مشخص ، مسدود شده باشند آنگاه آن پیام بعنوان یک پیام درگیر بن بست گزارش میشود.
اما انتخاب حد آستانه - مهلت زمانی - مسئله مهمی است بدین صورت اگر برای حد آستانه سطح پایین در نظر گرفته شود ممکن است پیامی که در گیر بن بست نیست به اشتباه به عنوان پیام درگیر بن بست معرفی شود و اگربرای حد آستانه سطح بالا در نظر گرفته شود ممکن است پیام درگیر بن بست دیرتر کشف شود. مهلت زمانی کشف بنبست، نمیتواند یک مقدار ثابت با هر ترافیک و بار شبکه باشد.
در این مقاله سطح آستانه کشف بنبست با توجه به ترافیک شبکه به صورت فازی تعیین میشود. در این مقاله ترافیک هم بر اساس وضعیت کانالهای خروجی و هم وضعیت کانالهای ورودی محاسبه شده برخلاف سایر الگوریتمهای دیگر که ترافیک را فقط بر اساس وضعیت کانالهای خروجی محاسبه می-کنند. دراین مقاله به دلیل اینکه کانالهای مشغول ورودی نیز در هر گره در افزایش ترافیک موثر هستند و به دلیل اینکه اگر بن بست اتفاق بیفتد، واضح است که کانال ورودی نیز جزئی از چرخه وابستگی بن بست هست، وضعیت کانالهای ورودی در محاسبه ترافیک بررسی شده است.
با بیشتر شدن ترافیک شبکه در جهات مختلف، احتمال انسداد کانالها و مسدود شدن بستهها بالا میرود و به همین جهت سطح آستانه باید بالا رود تا از تشخیص بستههای مسدود به جای بسته درگیر بنبست جلوگیری شود و با پایین آمدن ترافیک و کم شدن بستهها و کانالهای مسدود، سطح آستانه پایین آورده میشود، زیرا که، احتمال مسدود شدن بستهها و تشخیص به اشتباه آنها به جای بستههای درگیر بنبست کاهش مییابد.
برای فازی کردن سطح آستانه کشف بنبست، لازم است که حد بالا و حد پایین سطح آستانه تعیین گردد تا مقدار سطح آستانه که با استفاده از روش فازی معین میشود از کنترل خارج نشود. مقدار اولیه برای سطح آستانه در هر گره ابتدا باید معین شود،و باید مقدار آن در بازه حد پایین و بالا تعیین شود تا مقادیر سطح آستانه همیشه در این محدوده قرار گیرند. در هر پالس ساعت سیستم، هم وضعیت کانالهای مجازی خروجی و هم وضعیت کانال های مجازی ورودی بررسی میگردد.
با بررسی کانالهای آزاد و مشغول هم در کانالهای خروجی و هم در کانالهای ورودی میتوانیم تا حدودی ترافیک شبکه را به صورت محلی و تقریبی در هر گره محاسبه کنیم و اگر این عملیات را در یک بازه زمانی انجام دهیم میتوانیم ترافیک را به صورت میانگینی از ترافیک ها در پالسهای آن بازه زمانی محاسبه کنیم. یک متغیر ورودی فازی برای نشان دادن اختلاف مقدار ترافیک حال و گذشته بکاربرده شده که شامل یک سری مقادیر زبانی است و نیز یک متغیرخروجی فازی بنام Offset برای جبران مقدار سطح آستانه در نظر گرفته شده است که باز شامل یک سری مقادیر زبانی است .
برای اینکه نقش گذشته را در هر بازه زمانی از بین نبریم، ترافیک در هر گره را به صورت میانگین ترافیک در این بازه و ترافیک گذشته حساب میکنیم.یک سری قوانین فازی اگر- آنگاه تعریف شده که این قوانین بیانگر تغییرات ترافیک در مقدار سطح آستانه به صورت متغیرهای زبانی میباشند. مثلا، اگر مقدار ترافیک در جهات مختلف زیاد شودآنگاه باید مقدار سطح آستانه یا مهلت زمانی خیلی بیشتر شود تا از تشخیص به اشتباه پیامهای عادی به جای پیامهای بنبست جلوگیری شود به همین جهت Offset باید مقداری مثبت باشد. توابع عضویت فازی خروجی برای پارامتر ورودی فازی به صورت مثلثی تعریف شده. مکانیسم کشف بنبست فازی، در هر t اجرا میشود، این زمان را بر حسب پالس ساعت سیستم بیان میکنیم، در حالی که تعداد کانالهای خروجی و ورودی مشغول و آزاد در هر پالس ساعت حساب میشوند و بعد از هر ترافیک حاصل بر اساس مجموع کانالهای مشغول خروجی و ورودی در بازه زمانی گزارش میشود.
ترافیک شبکه بر اساس میانگین ترافیک گزارش شده در و ترافیک گذشته، حاصل میشود، این عمل تأثیری در تصمیم گیری حال ندارد و برای مشخص کردن ترافیک گذشته در اجرای بعدی مکانیسم کشف فازی در t بعدی مورد استفاده قرار میگیرد. برای نافازیسازی و بدست آوردن Offset مطلوب، از روش نافازیسازی مرکز ثقل،استفاده میکنیم.
در واقع Offset بدست آمده را برای بدست آوردن مقدار سطح آستانه جدید اعمال میکنیم - سطح آستانه جدید= سطح آستانه قبلی - Offset + در روش کشف بن بست به کار برده شده در این مقاله تعداد کمتری پیام در هنگام وقوع بن بست به عنوان پیام درگیر بن بست معرفی می شود زیرا چرخه بن بست با بیرون کشیدن حتی یکی از پیام های درگیر بن بست رفع می شود و لزومی ندارد که در هر گره یک پیام یا چند پیام به عنوان پیام درگیر بن بست معرفی شوند. در واقع به دنبال محل پیدایش بن بست می باشیم و سعی می کنیم با دنبال کردن چرخه وابستگی بن بست ، محل پیدایش چرخه وابستگی معرفی شود. این عمل با انتخاب یک سطح آستانه مناسب برای مدت زمان انسداد کانالها و پیامهای درگیر بن بست عملی است.
.3 الگوی شبکه
در هر گره ، برای رساندن یک بسته به مقصد کوتاهترین مسیر انتخاب می شود. برای مسیریابی از راه گزینی wormhole استفاده می شود. واحد مسیریابی در هر پالس یک بسته را مسیریابی می کند. هر کانال فیزیکی شامل سه کانال مجازی است.
واحد مسیریابی می تواند هر کدام از کانال های مجازی مربوط به کانال فیزیکی را انتخاب کند .سیاست انتخاب کانال مجازی برای استفاده از پهنای باند کانال فیزیکی بصورت نوبت گردشی است. در هر گره برای بسته هایی که منتظر مسیریابی هستند صفی در نظر گرفته می شود که بسته ها در این صف به صورت نوبت گردشی منتظر می مانند.در هر پالس فقط یک بسته مسیریابی می شود .آن بسته ، بسته ابتدای صف است.برای هر کانال مجازی ورودی و هر کانال مجازی خروجی بافری برای ذخیره کردن flit در نظر گرفته شده که ظرفیت این بافرها چهارflit است.سیاست انتخاب بسته برای استفاده از بافرهای ورودی و خروجی fifo است .در هر پالس فقط یک flit از کانال فیزیکی می تواند عبور کند
