مرکز منطقه ای اطلاع رسانی علوم و فناوری فصلنامه مهندسی برق و مهندسی کامپيوتر ايران 16823745 15 3 2017 11 28 An Efficient Routing Algorithm for Three-Dimensional Networks On-Chip with Partially Vertical Links الگوریتم مسیریابی کارا برای شبکه روی تراشه سه‌بعدی با کانال‌های عمودی نیمه‌کامل 211 222 fa فاطمه وحدت‌پناه احمد پاطوقی 2017 11 29 Three-Dimensional Chips are made of stacking silicon layers which communicate with each other by Through-Silicon-Via (TSV) links. Manufacturing cost of Three-Dimensional chips is a function of the number of TSVs because the fabricating of a three-dimensional chip with fully vertical links is of high cost and high fabrication complexity. The packet routing strategies in the 3D NoCs with partially TSVs is more complex than that in the 2D NoCs. In this paper, we proposed a routing algorithm for the 3D NoCs with partial TSVs, which provides a dynamic routing with maximum adaptivity for packets by dividing the network into three groups of layers, rows and columns. This algorithm is independent of vertical channel's position but related to layer number of the current packet and based on the layer number, odd or even, uses a special turn strategy to route packets on rows and columns with odd or even numbers. The proposed routing algorithm mitigates deadlock and livelock with only two virtual. The experiments show that average packet latency in proposed algorithm is 32.8% smaller than that in Elevator_First which is a well-known algorithm for packet routing in 3D chips. Also, this improvement on average packet latency and network throughput will be more with increasing on network size and reduction on TSV number. تراشه‌های سه‌بعدی از قرارگرفتن لایه‌های سیلیکون به صورت پشته ساخته می‌شوند و ارتباط بین این لایه‌ها توسط کانال‌های درون‌سیلیکون برقرار می‌شود. هزینه ساخت این تراشه‌ها تابعی از تعداد کانال‌های عمودی است و ساخت آنها با تعداد کامل کانال‌ها از لحاظ هزینه و پیچیدگی ساخت، مقرون به صرفه نیست. ناکامل بودن کانال‌های درون‌سیلیکون، مسأله مسیریابی اطلاعات را در شبکه‌های روی تراشه سه‌بعدی، پیچیده‌تر از شبکه‌های دوبعدی کرده است. در این مقاله یک الگوریتم مسیریابی برای شبکه‌های روی تراشه سه‌بعدی با کانال‌های عمودی ناکامل ارائه شده است که با تقسیم‌بندی لایه‌ای، سطری و ستونی شبکه، یک مسیریابی پویا را با حداکثر تطبیق‌پذیری در اختیار بسته‌ها قرار می‌دهد. این الگوریتم مستقل از مکان قرارگرفتن کانال‌های عمودی است و با در نظر گرفتن شماره لایه‌ای که بسته در آن قرار دارد و زوج یا فرد بودن آن، مدل چرخش خاصی در سطرها و یا ستون‌های زوج یا فرد به کار می‌گیرد. این الگوریتم تنها با استفاده از دو کانال مجازی مسأله بن‌بست و چرخه زنده را مرتفع کرده است. نتایج شبیه‌سازی و مقایسه الگوریتم پیشنهادی با الگوریتم اول- آسانسور نشان می‌دهد که در الگوریتم پیشنهادی، میانگین تأخیر تحویل بسته 8/32% نسبت به الگوریتم اول- آسانسور بهبود داشته است. همچنین قابل ذکر است که بهبود تأخیر و گذردهی با بزرگ‌تر شدن ابعاد شبکه و کاهش تعداد کانال‌های درون‌سیلیکون، افزایش خواهد یافت. http://ijece.org/fa/Article/Download/28274