19195

۱۹۱۹۵

ارائه يك الگوريتم مسيريابي وفق پذير جزئي با كارايي بالا براي شبكه بر تراشه سه‌بعدي

ﮐﺎرﺷﻨﺎﺳﯽ ارﺷﺪ

معماري سيستم هاي كامپيوتري

ارديبهشت ماه ۱۳۹۷

دكتر مرتضي آنالويي

كامپيوتر

چكيده شبكه بر تراشه سه‌بعدي به‌ عنوان بهترين راه‌حل براي برقراري ارتباط بين واحدهاي پردازشي مختلف در تراشه‌هاي سه‌بعدي شناخته مي¬شود. استفاده از كانال¬هاي درون سيليكون يكي از رايج¬ترين روش¬ها در ساخت تراشه‌هاي سه‌بعدي است اما به دليل پيچيدگي در فرآيند ساخت اين كانال‌ها و سربار مساحت بالايي كه به تراشه تحميل مي‌كند، ساخت تراشه¬هايي با تعداد محدودي از كانال درون سيليكون پيشنهاد شد. در تراشه¬هايي با اتصالات عمودي ناكامل به دليل كاهش پهناي باند عمودي، ميزان ترافيك روي هر كانال افزايش مي¬يابد؛ بنابراين در چنين شبكه¬هايي مديريت ترافيك براي بهبود كارايي شبكه بسيار حياتي است. براي اين منظور در اين پايان‌نامه با ارائه‌ي يك الگوريتم مسيريابي ازدحام آگاه و توزيع مناسب ترافيك در كانال‌هاي درون سيليكون، كارايي شبكه بهبود مي¬يابد. در الگوريتم مسيريابي پيشنهادي اطلاعات ازدحام كانال‌هاي درون سيليكون به‌وسيله‌ي شبكه‌ي سيمي و فضاي خالي موجود در سرآيند بسته‌ها در شبكه منتشر مي‌شود. از شبكه¬ي سيمي در بين صفحه‌هاي مختلف و از سرآيند بسته در هر صفحه استفاده شده است به‌اين‌ترتيب همه‌ي مسيرياب‌هاي شبكه، از وضعيت ازدحام كانال‌هاي عمودي مطلع هستند و بر اساس اين اطلاعات براي بسته¬هايي كه مقصدشان در لايه‌ي ديگري قرار دارد، يك مسيرياب داراي كانال عمودي، به ‌عنوان مقصد موقت انتخاب مي‌كنند. بسته‌ها از مبدأ تا مقصد موقت و از مقصد موقت تا مقصد اصلي را بر اساس الگوريتم مسيريابي غرب-اول مسيريابي مي‌شوند. براي جلوگيري از بن‌بست، از دو زير شبكه¬¬¬ي بالارونده و پايين‌رونده و دو كانال مجازي در بعد X و Y استفاده شده است. مسيريابي پيشنهادي حتي باوجود يك كانال عمودي در هر نقطه‌اي از شبكه، به‌درستي كار مي¬كند. نتايج شبيه¬سازي¬هاي انجام شده، به‌وسيله‌ي شبيه‌ساز Access Noxim و تحت الگوهاي ترافيكي مختلف نشان مي‌دهد الگوريتم مسيريابي پيشنهادي در مقايسه با الگوريتم مسيريابي شرق-سپس غرب، تأخير تحويل بسته‌ها را به‌طور ميانگين 51.4% بهبود مي¬دهد. همچنين گذردهي شبكه در مسيريابي پيشنهادي، بهتر از مسيريابي شرق-سپس غرب مي¬باشد. واژه‌هاي كليدي: شبكه بر تراشه سه‌بعدي، كانال عمودي نيمه‌كامل، كارايي، الگوريتم مسيريابي ازدحام آگاه.

1397/04/24

Providing a high performance partially adaptive routing algorithm for 3D network on chip

7/15/2018 12:00:00 AM

Abstract: Three dimensional network on chip is known as the best solution for connecting among different processing elements in 3D chips. Using through-silicon-via is one of the common approach in construction of 3D chips. But due to complexity in manufacturing process and high area overhead that imposed to chip, it suggests chips with limited number of through-silicon-via. In chips with partially vertical links due to decreased vertical bandwidth, the traffic increases over every channel. So traffic management is important in such networks. For this purpose in this thesis we propose a congestion aware routing algorithm and proper traffic distribution in through-silicon-via, so that network performance improves. In proposed routing algorithm congestion of through-silicon-via propagate with wired network and packet header in network. It has been used the wired network among the different layers and packet header in every layer. Thus all routers of network know the congestion situation of vertical channel and according to this information select a router with vertical channel for packets that their destination is in another layer as temp destination. Packets are routing from source to temp destination and from temp destination to main destination with west-first routing algorithm. For deadlock avoidance, two upward and downward sub network and two virtual channel in X and Y dimensions are used. The proposed routing algorithm works correctly even with one vertical channel in every point of network. Simulation results are performed by Access Noxim and under different traffic patterns which shows our proposed routing algorithm in comparison with east-then-west routing, improves packet delivery latency 51.4% in average. Also network throughput in the proposed routing is better than east-then-west. Keywords: Three dimensional network on chip, partionally vertical channels, performance, congestion aware routing algorithm.