FIFO Sizing for High-Performance Pipelines

Performance-critical pipelines—such as a packet processing pipeline in a network device—are built from a sequence of simple processing modules, connected by FIFOs. Due to their complex sequential behavior, the worst case throughput, as well as the size of the interconnecting FIFOs, are currently designed using very rough heuristics. Such systems are usually validated by simulation, or worse, field testing. In this paper, we propose a methodology that address these two issues. First, we propose a fast technique for computing the maximum possible throughput assuming unbounded FIFOs. Then, we describe two algorithms, one exact, one heuristic, that compute minimum FIFO sizes that can achieve this throughput (i.e., FIFOs that do not introduce bottlenecks). Experimental results suggest our algorithm is applicable to pipelines of at least five modules with runtimes generally in minutes. Since such a computation is only needed a few times for any design, we consider our technique practical