New logic architectures for round robin arbitration and their automatic RTL generation

Abstract

İşlem isteklerinin sıraya konulması (iş-düzenleme), bilgisayar ve iletişim sistemlerinin önemli problemlerinden birisidir. İş-düzenleme işleminin en çok kullanıldığı alanlardan birisi bilgisayar ağlarıdır. Gigabit ve terabit yönlendirici tasarımının önemli uğraşlarından biri, hızlı, maliyeti düşük ve adil iş-düzenleyici donanımları tasarlayarak paket yönlendirme işlemini hızlandırmaktır. Bu konu, yüksek kaliteli, gelecek nesil, çoklu-ortam servislerinin desteklenmesi için son derece kritiktir.Bu tezde, hızlı ve alan açısından verimli iş-düzenleyici mimarilerine ve bunların Yazmaç Transfer Seviyesi (YTS) tasarım üreteçlerine odaklanılmıştır. Bu alanda en çok dikkate değer çalışma Stanford Üniversitesi'nden Pankaj Gupta ve Nick McKeown'un çalışmasıdır. Biz bu çalışmaya STA_RRA adını verdik. Daha sonraları STA_RRA üzerinde iyileştirme çalışmaları yapılmasına rağmen, hala hız ve alan açısından ilerleme kaydedilebileceğini gördük.Bu tezde, STA_RRA ve değişik türevlerinden hız ve alan açışından daha iyi iki yeni iş-düzenleyici mimarisi önerilmektedir. Önerilen iş-düzenleyici tasarımlarından birisi minimum alan sonuçlarına odaklanırken, diğeri hız için tasarlanmıştır. Bu tasarımlardaki yenilik, termometre kodlamasında ve öncelik kodlamasında Paralel Prefiks Ağaç yordamlarının kullanılmasıdır. Önerilen ve rakip iş-düzenleyiciler, 8 bit'ten 256 bit'e kadar sentezlenmiştir. Yapılan karşılaştırma çalışmalarında, bizim iş-düzenleyicilerimizin rakip iş-düzenleyicilere göre hız açısından 42% ve alan açısından 22% oranla daha iyi sonuç verdiği görülmüştür.Anahtar Kelimeler: Değişmez Zaman Paylaşımlı İş-düzenleyiciler, YTS Üretimi, Paralel Prefiks Ağaç Yordamları

Resource arbitration is a major problem in communications and computer systems. One of the most prevalent usage areas of arbitration is in computer networks. In gigabit and terabit routers, the challenge is to design ultra high speed, cost effective, and fair arbitration hardware to speed up packet forwarding. This issue is highly important for supporting high quality multimedia services in next generation networks.This thesis is focused on architectures for fast and area efficient round robin arbiters (RRA) and their Register Transfer Level (RTL) design generation. One of the most notable works in this area is the work of Pankaj Gupta and Nick McKeown at Stanford University ? which we call Stanford Round Robin Arbiter (STA_RRA). Although there have been further enhancements on top of STA_RRA, we have seen that there is still room for improvement in both speed and area departments.This thesis work proposes two new RRA logic architectures with better speed or area metrics than STA_RRA and its variants. One of the proposed RRA designs is focused on achieving minimum area results, and the other one is designed for speed. The novelty of these designs is in their use of parallel prefix tree (PPT) algorithms for thermometer encoding and priority encoding operations. Synthesis of proposed arbiters and their rivals were carried out from 8 bits to 256 bits. Benchmarks of 256 bits arbiters show that our proposed architectures perform better than their rivals by a factor of 42% in speed and 22% in area.Keywords: Round Robin Arbiters, RTL Generation, Parallel Prefix Tree Algorithms