22106

ارائه الگوريتم مسيريابي سلسله مراتبي در شبكه بر تراشه دو بعدي

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

الكترونيك - ديجيتال

1399/2/9

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

برق

همراه با افزايش روزافزون تعداد هسته‌ها در يك تراشه، شبكه برتراشه به عنوان يك استاندارد اتصالات درون تراشه براي غلبه بر مقياس‌پذيري محدود شده زيرساخت‌هاي داخلي سنتي مانند گذرگاه‌ها به كار گماشته شده است. افزايش اندازه شبكه بر تراشه‌ها موجب شده است كه اين شبكه‌هاي ميان ارتباطي با مشكل عدم توزيع بار متعادل مواجه شوند. اين توزيع بار نامتعادل سبب بروز تراكم در شبكه بر تراشه‌ها مي‌شود. به دليل كوتاه‌تر بودن مسير عبور از مركز شبكه، الگوريتم‌هاي مسيريابي ترجيح مي‌دهند كه اين مسير را براي پيمايش بسته از مبدا به مقصد مشخص انتخاب كنند كه اين امر باعث بروز ازدحام در مركز شبكه بر تراشه شده و كارآيي آن را كاهش مي‌دهد. . از اين رو، مسيريابي بسته‌ها در شبكه بر تراشه از اهميت زيادي برخوردار است. در اين پايان‌نامه با استفاده از روش جزبندي، شبكه برتراشه با ابعاد بزرگ را به زيرشبكه‌هاي كوچكتر تقسيم مي‌كنيم تا بتوانيم مسيريابي در شبكه را راحت‌تر مديريت كنيم. براي مسير‌يابي با استفاده از اطلاعات تراكم هر زير شبكه كه به صورت ميانگين محاسبه و در بسته‌هاي داده تعبيه شده است، استفاده مي‌شود. براي اين منظور، فضاي خالي در بسته‌هاي داده به دو بخش تقسيم بندي شده تا هم اطلاعات درون و هم اطلاعات بيرون زيرشبكه‌ها را در خود جاي دهد. الگوريتم مسيريابي ما ابتدا مسير با ازدحام كمتر را از ميان زيرشبكه‌ها تعيين مي‌كند. سپس، با به كار گيري الگوريتم مسيريابي قطعي مانند XY به طرف گره مقصد حركت مي‌كند. در اين الگوريتم مسيريابي، از مزيت‌هاي هر دو نوع مسيريابي انطباقي و قطعي استفاده مي‌شود. علاوه بر اين، ما مفهومي به نام سطح را براي شبكه بر تراشه‌ها تعريف مي‌كنيم كه به ما اين امكان را مي‌دهد تا الگوريتم مسيريابي را براي شبكه بر تراشه‌هايي با هر اندازه به‌كار گيريم. نتايج شبيه‌سازي تحت الگوهاي ترافيكي مختلف مشخص مي‌كند كه روش پيشنهادي در مقايسه با روش‌هاي ديگر، داراي بهبودحداقل 5% و حد اكثر تا 16% در عملكرد و بين 15% تا 65% در تاخير رسيدن بسته به مقصد را دارد. به علاوه روش ذخيره سازي ميانگين اطلاعات ازدحام80% بهبود در سربار را براي يك شبكه شامل 64 مسيرياب را نشان مي‌دهد.

1399/04/24

Propose a hierarchical routing algorithm for two-dimensional Network-on-Chip

4/28/2020 12:00:00 AM

Nowadays Network-on-Chip (NoC) provides remarkable facilities in transmitting data between Chip Multiprocessors (CMPs). Routing algorithms have a key role in Network-on-Chip (NoC) to increase the received packets at the destination routers. Congestion is a known problem that affects performance in Network-on-Chip communication. As deterministic routings do not consider the large-scale network’s status, Congestion-aware routing algorithms have been used for packet transmission but they are faced with hardware overhead for transmitting congestion information. In this thesis, we present and evaluate a novel routing scheme which combines the advantages of both deterministic and adaptive routing for traffic management in a 2D mesh network. For this purpose, we proposed a partitioning model that divides the network into two inter and intra-partition regions. Furthermore, in order to limit hardware overhead, congestion information is propagated in the header flit of the packet which is divided into two separate sections for storing inter and intra values. The purposed method utilizes this congestion information for routing decisions and forward packet toward partitions with lower traffic. Congestion information will be transferred between inter-partition regions to locally evaluate the traffic conditions. Using this evaluation, it is possible to use a deterministic algorithm such as dimension-order routing, which is known as XY to decrease the number of virtual channels. In the proposed algorithm, the congestion deflected from the center of the network and distributed to the entire network and tries to improve the overall system performance. The simulation of the purposed algorithm has been carried out the Noxim simulator. Under different traffic patterns, simulation results show that our routing algorithm improves the saturation throughput and average packet latency in comparison with other algorithms. The results indicate that our algorithm has at least 15% and at most 64% improvement in latency and between 5% and 16% improvement in throughput. In addition, the method that we proposed for having an average in congestion information shows 80% overhead improvement for a network with 64 routers.