Tech Report CS-89-18

I/O Overhead and Parallel VLSI Architectures for Lattice Computations

Mark H. Nodine, Daniel P. Lopresti and Jeffrey Scott Vitter

March 1989


In this paper we introduce a complexity measure for inputs and outputs (I/Os) in two-dimensional lattice computations called the I/O overhead \verb+\(*Q+. We show by pebbling arguments that a lower bound for the I/O overhead is proportional to $n ^ {-1}$, when there are $n ^ 2$ processing elements available for the computation. We show that if the results are required to be read at every generation, then the lower bound is the constant 2. We then examine four architectures and show that one of them, the multi-generation sweep architecture, also has I/O overhead proportional to $n ^ {-1}$ and we derive and compare the constants of proportionality. Finally, we prove a closed form for the discrete minimization equation giving the optimal number of generations to compute for the multi-generation sweep architecture.

(complete text in pdf)