17409

17409

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

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

سخت افزار - معماري

دي ماه 1395

دكتراحمد پاطوقي

كامپيوتر

چكيده مطابق با پيش¬بيني¬هاي ITRS،¬ به كارگيري شبكه¬هاي برتراشه¬ي سه¬بعدي براي اتصال عناصر پردازشي، ماجول¬هاي حافظه¬¬ و ماجول¬هاي ورودي/ خروجي بر روي تراشه با تكنولوژي¬هاي كوچكتر از 65 نانومتر يكي از بهترين راه حل¬ها مي¬باشد. در ساخت مدارات مجتمع سه‌بعدي، استفاده از كانال‌هاي درون‌سيليكون هزينه¬ي ساخت تراشه¬هاي سه¬بعدي را به شدت بالا مي¬برد؛ به طوري¬كه ساخت يك شبكه¬ي سه‌بعدي با تعداد كامل كانال‌هاي عمودي از لحاظ هزينه و پيچيدگي ساخت، مقرون به¬صرفه نمي¬باشد. ازسوي ديگر ناكامل بودن كانال‌هاي درون‌سيليكون، مسأله¬ي مسيريابي اطلاعات در شبكه‌هاي روي تراشه‌ي سه‌بعدي را متفاوت از مسيريابي در شبكه‌هاي دوبعدي كرده است. در اين پايان¬نامه يك الگوريتم مسيريابي نيمه¬تطبيقي براي شبكه¬هاي روي تراشه¬ي سه¬بعدي با كانال عمودي ناكامل ارائه شده است. الگوريتم پيشنهادي با تقسيم بندي لايه¬هاي يك تراشه به گروه¬هاي چهارتايي، براي هر لايه از اين گروه¬ها يك مسيريابي ارائه مي¬كند. همچنين سطرها و ستون¬ها در هر لايه به دو گروه زوج و فرد تقسيم مي¬شوند و مسيريابي با توجه به موقعيت بسته در سطرها و ستون¬هاي زوج/فرد انجام مي¬شود. اين الگوريتم تنها با استفاده از دو كانال مجازي مسأله¬ي بن¬بست و چرخه¬ي زنده را مرتفع كرده است. ارزيابي الگوريتم پيشنهادي با استفاده از شبيه¬¬ساز Accessnoxim انجام شده و طي آن، روش پيشنهادي با الگوريتم شناخته شده¬ي¬ اول_آسانسور مقايسه شده است. نتايج بررسي¬ها نشان مي¬دهد كه ميانگين بهبود تأخير تحويل بسته¬ها در الگوريتم پيشنهادي نسبت ¬به الگوريتم اول_آسانسور حداكثر 54% و به¬طور ميانگين 8/32% بهتر است، همچنين گذردهي شبكه تحت الگوريتم پيشنهادي نسبت ¬به الگوريتم اول_آسانسور بيشتر است. ارزيابي¬هاي انجام شده نشان مي¬دهد كه بهترين چينش ازنظر ميانگين بهبود تأخير، قرارگرفتن كانال‌هاي درون‌سيليكون به¬صورت قطري مي¬باشد. كلمات كليدي: بن¬بست، شبكه¬ روي تراشه¬ سه‌بعدي، مسيريابي وفق¬پذيرنيمه¬كامل، كانال¬عمودي نيمه-كامل، كانال¬مجازي.

1396/03/19

1/1/1900 12:00:00 AM

Abstract: According to ITRS, using Three-Dimensional Chips for connecting processing elements, memory and I/O modules on chips that made with less than 65 nm technologies is One of the best solutions in construction of three-dimensional integrated circuits using of through-silicon-via (TSVs) strongly increase the Manufacturing cost of Three-Dimensional chips, so that the fabricating of a three dimensional network on chip with the total number of vertical links is not efficient because of cost and complexity of this process. On the other hand, the problem of routing information in 3D NOCs in comparison with 2D NOCs is because of incompleteness of TSV channels. In this thesis, we propose a partially adaptive routing algorithm for vertically partially connected TSV links for three-dimensional network on chips. The proposed algorithm is divided network layers into four groups and for each layer of these groups, provided a routing strategy. Also rows and columns in each layer can be divided into two Odd and Even groups and routing strategies in rows and columns are different from each other. The proposed routing algorithm using two virtual channels in each layer is deadlock and livelock free and is eva​luated using Access Noxim simulator, in which the proposed method is compared with the well-known Elevator_First algorithm. Our experimental results reveal that the average improvement of packet delivery latency of our algorithm significantly outperforms the Elevator_First algorithm with maximum of 54% and the average of 32.8%. Also network throughput in the proposed algorithm is better than Elevator_First. Moreover, eva​luations show that diagonally placement of TSVs in layers in terms of improving average latency is the best scenario. Keywords: Deadlock, 3D NOC, Partially Adaptive Routing, Partially Connected TSVs, Virtual Channel