7899

7899

مسيريابي تحمل پذير نقص شبكه بر تراشه توسط الگوريتم ژنتيك

كارشناسي ارشد

مهندسي برق گرايش الكترونيك

١٣٨٩

١٣٨٩

پروفسوركريم محمدي

دكترهادي شهريار شاهحسيني

چكيده افزايش پيچيدگي طراحي مدارات مجتمع از يك سو و نياز به جداسازي فعاليت قسمت هاي محاسباتي و ارتباطي در تراشههاي امروزي از سويي ديگر، مسير طراحي را به سوي سامانه هاي مبتني بر شبكه روي تراشه سوق دادهاست . امروزه داشتن قابليت اعتماد بالا در برابر عوامل ناخواسته محيطي يكي از اهداف مهم طراحي سامانههاي محاسباتي محسوب ميگردد؛ عواملي كه آسيبپذيري مدارها در برابر آنها با كاهش روزافزون اندازهها در فناوريهاي ساخت تراشه روزبروز افزايش مييابد. در اين ميان شبكههاي روي تراشه به عنوان زيربناي ارتباطي مقياس پذير در سامانههاي روي تراشه، بايستي از اين ويژگي برخوردار باشند. در اين پاياننامه، شبكههاي روي تراشه از نظر ساختار داخلي، انواع همبندي ها، انواع خرابي ها بررسي شده است و آشنايي با انواع الگوريتمهاي مسيريابي و الگوريتمهاي مسيريابي تحملپذير در برابر اشكالهاي دائمي، صورت گرفته است. در ادامه، طراحي دو نوع الگوريتم مسيريابي تحملپذير اشكال اتصالها ارائه شده، كه يكي از نوع قطعي و ديگري از نوع تطبيقي است. در نوع اول از حداقل تعداد كانالهاي مجازي استفاده شده است. نوع دوم نيازي به كانال مجازي ندارد و الگوريتمي توزيع شده بوده و به خاطر عدم استفاده از جدولهاي مسيريابي از خاصيت مقياسپذيري بهره ميبرد. طراحي اين نوع الگوريتمها به نحوي صورت گرفتهاست كه قابليت اطميناني قابل توجه اما با هزينه و زمان تأخير ناچيز و كارآيي بالا بدست آيد. در الگوريتم نوع اول، كه هدف اصلي اين پايان نامه است، با بهره گيري از الگوريتم ژن تيك در الگوريتم مسيريابي تحملپذير اشكال، براي يافتن امنترين، كم تأخيرترين مسير و در عين حال مسيري فاقد بنبست و چرخهي زنده، از تكنيكي ابتكاري استفاده شدهاست. الگوريتم دوم، الگوريتم مسيريابي تحملپذير اشكالي است كه به منظور بالانس شدن تراكم در نقاطي كه اشكال رخداد دادهاست، پارامتر تراكم را در حين مسيريابي در نظر ميگيرد. به منظور بررسي ميزان كارآيي و قابليت اطمينان الگوريتمهاي پيشنهادي، نتايج شبيه سازي با الگوريتمهاي كارآ و بروز مقايسه شدهاند. واژه هاي كليدي: شبكه بر تراشه، الگوريتم مسيريابي تحمل پذي ر اشكال، قابليت اطمينان، الگوريتم ژنتيك، پارامتر تراكم.