Academic Commons

Articles

FIFO Sizing for High-Performance Pipelines

Soviani, Cristian; Edwards, Stephen A.

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.

Subjects

Files

Also Published In

Title
Proceedings of the 16th International Workshop on Logic and Synthesis, May 30 - June 1, 2007, San Diego, CA

More About This Work

Academic Units
Computer Science
Published Here
March 7, 2012