Fault tolerant routing algorithm in networks on chip using ant colony algorithm

Ghahremani, Rahman and Javidan, Javad and Jamali, Shahram (2015) Fault tolerant routing algorithm in networks on chip using ant colony algorithm. Masters thesis, University of Mohaghegh Ardabili.

[img] Text (مسیریابی تحمل‌پذیر نقص در شبکه روی تراشه با استفاده از الگوریتم کلونی مورچگان)
Rahman Ghahremani.pdf

Download (613kB)
Official URL: http://www.uma.ac.ir

Abstract

: Increasing of design complexity of integrated circuits on one hand and need to segregate activities of computation and communication sections in today's IC chips on the other hand, has directed design path towards systems based on network- on-chip. Nowadays, having high reliability in face of unwanted environmental factors is an important goal in the designing of computational systems; factors against which the vulnerabilities of circuits are ever more increasing as the sizes continually diminish in the areas of chip manufacturing technologies. In this respect, the networks-on-chip, as a scalable communication substructure in systems-on-chip, should possess this characteristic. In this thesis, the networks-on-chip have been examined with respect to their internal structure and various types of connections and breakdowns, and also different routing algorithms and fault-tolerant routing algorithms against permanent faults and problems have been introduced and presented. Then, the designs of two types of routing algorithms tolerant of connection faults, have been presented, that in first method we use ant colony algorithm and how ants can skip the obstacles when searching for food sources. In this method packets was considered as ants and obstacles as a failures. to further explore a second method is proposed. This algorithm is based on DyXY algorithm that tolerance permanent link failures and also the algorithm is aware of the congestion. The simulation results show that the proposed algorithm has better performance in all evaluation parameters such as delay and reliability than planar adapt routing algorithm.

Item Type: Thesis (Masters)
Persian Title: مسیریابی تحمل‌پذیر نقص در شبکه روی تراشه با استفاده از الگوریتم کلونی مورچگان
Persian Abstract: افزایش پیچیدگی مدارات مجتمع و عدم مقياس¬پذيری گذرگاه¬های سنتی و روش نقطه به نقطه برای ارتباط بین اجزای داخل تراشه از یک سو و نیاز به جداسازی فعالیت قسمت‌های محاسباتی و ارتباطی در تراشه‌های امروزی از سویی دیگر، مسیر طراحی قسمت ارتباطی را به سمت شبکه بر تراشه سوق داده است. يکي از چالش¬های اساسی برای چنين سيستم¬های پيچيده، امکان وقوع نقص¬های دائمی در اثر عيب¬های زمان ساخت يا نقص¬های طول عمر در طول زمان عمر مفيد آن‌هاست. همچنين نقص¬های گذرا که علت¬هاي تصادفی و غيرقابل پيش¬بينی دارند و می-توانند عملکرد سيستم را به شدت تحت تاثير قرار دهند. بنابراين نياز به نوعي از طراحي به‌وجود آمد که اين گونه سيستم¬ها در برابر نقص¬هاي گوناگون دچار خرابی نشده و به کار خود ادامه دهند. اين گونه طراحي¬ها علاوه بر بالا بردن کارآيي سيستم بايد قابليت پياده‌سازي با هزينه¬اي منطقي را نيز داشته باشند. از آنجا که کارايي شبکه‌هاي بر تراشه نيز همانند هر شبکه ميان ارتباطي ديگر، به طور گسترده‌اي وابسته به روش‌هاي مسيريابي بکار رفته در آن‌ها مي‌باشد، در تراشه¬های مبتنی برشبکه بر تراشه، طراحی الگوريتم¬های مسيريابی با قابليت تحمل¬پذيری نقص روشی کارآمد برای افزايش قابليت اطمينان در برابر نقص¬های دائمی و گذرا می¬باشد. در این پایان‌نامه پس از مرور مفاهیم مربوط به شبکه بر تراشه به بررسی الگوریتم‌های مسیریابی تحمل‌پذیر نقص در برابر اشکال‌های دائمی پرداخته‌ایم و دو الگوریتم مسیریابی برای تحمل‌پذیری نقص‌های دائمی ارائه شده است که در روش اول از الگوریتم‌ کلونی مورچگان و نحوه‌ی عملکرد آن‌ها در برخورد با موانع استفاده شده است که در آن بسته بعنوان مورچه و خرابی‌ها بعنوان مانع در نظر گرفته شده‌اند. در ادامه برای بررسی بیشتر روش دومی نیز پیشنهاد شده است. این الگوریتم بر مبنای الگوریتم DyXY بوده که قابلیت تحمل‌پذیری نقص‌های دائمی لینک‌ها به آن اضافه شده و همچنین الگوریتمی آگاه از ازدحام می‌باشد. نتایج شبیه‌سازی نشان می‌دهد الگوریتم‌های پیشنهادی عملکرد بهتری در همه پارامترهای ارزیابی همچون تاخیر و قابلیت اعتماد نسبت به الگوریتم صفحه‌ای دارند.
Supervisor:
SupervisorE-mail
Javidan, JavadUNSPECIFIED
Advisor:
AdvisorE-mail
Jamali, ShahramUNSPECIFIED
Subjects: Faculty of Engineering > Department of Electrical & Computer Engineering
Divisions > Faculty of Engineering > Department of Electrical & Computer Engineering
Divisions: Subjects > Faculty of Engineering > Department of Electrical & Computer Engineering
Faculty of Engineering > Department of Electrical & Computer Engineering
Date Deposited: 10 Nov 2018 18:26
Last Modified: 10 Nov 2018 18:26
URI: http://repository.uma.ac.ir/id/eprint/1710

Actions (login required)

View Item View Item