17136

17136

ارائه روشي براي مديريت ترافيك در شبكه‌هاي برتراشه سه بعدي

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

الكترونيك

دي 1395

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

برق

مساله¬ ازدحام مهم¬ترين عاملي است كه كارايي يك شبكه برتراشه را محدود مي¬كند. ازدحام باعث افزايش تاخير ارسال يا دريافت بسته¬ها¬، بالارفتن حرارت سطح تراشه و افزايش توان مصرفي مي¬گردد. الگوريتم¬هاي مسيريابي¬ ازدحام-آگاه در سه دسته¬ي الگوريتم¬هاي محلي، ناحيه¬اي و سراسري با اجتناب از مسيرهاي مزدحم، سعي در توزيع بار ترافيكي در سراسر شبكه و كاهش تاخير ارسال بسته¬ها دارند. در اين پايان¬نامه، دو الگوريتم مسيريابي ازدحام-آگاه به منظور توزيع بار ترافيكي در شبكه¬هاي برتراشه سه-بعدي پيشنهاد شده است. الگوريتم اول، يك مسيريابي ازدحام-آگاه سراسري است كه در آن هر مسيرياب از وضعيت ازدحام همه¬ي گره¬هاي يك لايه شبكه آگاه است. اين روش كه G-CARA ناميده مي¬شود، با تعبيه كردن اطلاعات ازدحام در بسته¬هاي داده، اطلاعات ترافيكي را در سراسر شبكه منتشر مي¬كند. پس از انتشار اطلاعات ازدحام، در هر لايه از شبكه برمبناي رويكرد XY مسيريابي ازدحام-آگاه انجام مي¬شود تا بسته-هاي داده با حداقل تاخير به مقصد برسند. الگوريتم پيشنهادي دوم، يك مسيريابي ازدحام-آگاه ناحيه¬اي است كه در آن هر مسيرياب از وضعيت ازدحام گره¬هايي كه در محدوده¬ي i گامي آن قرار گرفته¬اند و يك ناحيه پلكاني تشكيل مي¬دهند، آگاه است. در اين روش كه R-CARA ناميده مي¬شود، براي جمع¬آوري و توزيع اطلاعات ازدحام در ناحيه پلكاني، يك شبكه انتشار ازدحام با تاخير كم پياده¬سازي مي¬گردد. براي مسيريابي بسته¬ها، R-CARA براساس موقعيت مقصد نسبت به مسيرياب فعلي، چهار حالت تعريف مي-كند. الگوريتم پيشنهادي برمبناي اين حالت¬ها ازدحام را در گذرگاه¬هاي قابل¬قبول تخمين مي¬زند و بسته¬ را از گذرگاه كم¬ازدحام¬تر هدايت مي¬كند.¬ نتايج شبيه¬سازي تحت الگوهاي ترافيكي مختلف نشان مي¬دهد كه الگوريتم پيشنهادي اول در مقايسه با الگوريتم¬هاي ديگر به صورت ميانگين 23%-14% اشباع برون¬داد شبـكه را بهبود مي¬بخشـد و 42%-61% تاخير تحويل بسته¬ها را كاهش مي¬دهد. الگوريتم پيشنهادي دوم در مقايسه با روش¬هاي ازدحام-آگاه موجود به صورت ميانگين 17%-5% اشباع برون¬داد را بهبود مي¬بخشد و 51%-18% ميانگين تاخير تحويل بسته¬ها را كاهش مي¬دهد. واژه‌هاي كليدي: شبكه برتراشه سه¬بعدي، مسيريابي وفقي، ازدحام-آگاه، رهايي از بن¬بست.

1396/01/29

1/1/1900 12:00:00 AM

Abstract: Congestion issue is the major factor, which limits improvement of network-on-chip efficiency. It leads to larger transmission latency, higher thermal an​d more power consumption. Congestion-aware routing algorithms, which are classified as local, regional an​d global algorithms, can distribute traffic load over the network an​d reduce packet transmission latency by selecting less congested paths. In this thesis, two congestion-aware routing algorithms are presented to distribute traffic load in 3D NoCs. The first algorithm is a globally congestion-aware routing in which each router is aware about congestion status of all network nodes. This method, which named Globally Congestion Aware Routing Algorithm (G-CARA), propagates congestion data through the network by embedding status information in data packets. After propagation of congestion information, congestion-aware routing is performed in each network layer based on XY, So that data packets reach their destination with the minimum of delay. The second algorithm is a regionally congestion-aware routing in which each router is aware about congestion status of all nods that are located in the stair region. In this method, which named Regional Congestion Aware Routing Algorithm (R-CARA), a low-latency congestion propagation network is implemented for collecting an​d distributing traffic data. For routing packets, R-CARA introduces four situations according to position of current router an​d destination. It estimates the congestion of admissible directions based on these situations an​d forwards packet in less congested direction. Under different traffic patterns, simulation results show that the first algorithm improves the saturation throughput an​d average packet latency in comparison with other algorithms, an improvement of 14.68%-22.95% an​d 42.43%-61.29% respective. The second algorithm improves the saturation throughput an​d average packet latency in comparison with existing congestion-aware schemes, an improvement of 5.04%-17.08% an​d 18.62%-51.21% respective. Keywords: 3D Network-on-Chip (NoC), Adaptive Routing, Congestion-Aware, Deadlock freedom.