Pipelined Architecture for Multi-String Matching

Abstract

This letter presents a new oblivious routing algorithm for 3D mesh networks called randomized partially-minimal (RPM) routing that provably achieves optimal worst- case throughput for 3D meshes when the network radix fc is even and within a factor of 1/k <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> of optimal when k is odd. Although this optimality result has been achieved with the minimal routing algorithm OITURN for the 2D case, the worst-case throughput of OITURN degrades tremendously in higher dimensions. Other existing routing algorithms suffer from either poor worst-case throughput (DOR, ROMM) or poor latency (VAL). RPM on the other hand achieves near optimal worst-case and good average-case throughput as well as good latency performance.