Hardware efficient two step iterative matching algorithms for VOQ switches

Virtual output queued (VOQ) crossbar switches have been demonstrating advantages as high speed interconnects. They eliminate the Head of Line (HOL) blocking, which limits the maximum throughput of single input queued switches, and do not require switching fabrics with speedup capability, which prevents output queued switches from being cheaply implementable. Existing practical VOQ scheduling algorithms work in an iterative manner, and each iteration usually includes three steps: request, grant and accept. By incorporating arbitration into the request step, the accept step can be eliminated, and two step iterative matching can be achieved. While two step algorithms achieve almost identical performance as three step algorithms, they have extra advantages, such as simpler hardware implementation, shorter scheduling time, and less data exchange. As examples of two step iterative matching algorithms, we present Two Step Parallel Iterative Matching (PIM2) and Two Step iSLIP (iSLIP2), and theoretically analyze the convergence property of PIM2. Furthermore, because the request step and grant step perform similar operations, and the two steps always progress in a sequential manner, we propose a hardware efficient implementation for two step iterative matching algorithms which requires only one set of arbitration logic. We conduct extensive simulations, and the results demonstrate that our analytical result on the average convergence iterations, In N + e/(e -1), is more accurate than the classical result, log₂ N + 4/3, and that two step algorithms and three step algorithms have almost identical performance.