Throughput of Long Self-Timed Pipelines

Abstract:

We explore the practical limits on throughput imposed by timing in a long, self-timed, circulating pipeline (ring). We first consider the case when computation, communication, and storage are combined in a single operation, and the time for this operation is random with an exponential distribution. This
pipeline is amenable to queuing theory analysis, and we show that the asymptotic processor utilization is independent of the length of the pipeline, but is at most 25%. This suggests a design where computation and communication are separated from storage. We analyze this pipeline with various distributions of processing time, and show that linear speedup can again be achieved, but in this case with utilization approaching 100%.