Description
In this report, we present a theoretical model for VLSI computation, with assumptions updated for modern technology, and a number of asymptotic lower bounds in this model. Among other facts, we show unconditionally that all n-input computations of a single output require time Ω(n1/3), that dense matrix multiplication requires time Ω(n) for n x n matrices, and that sparse-matrix-times-dense-vector multiplication (SpMV) requires time Ω(n/logn)1/2for some matrices. We also show that implementation of the Bellman-Ford shortest paths algorithm requires time Ω(n4/3)for some graphs.
Additionally, we develop bounds on placement quality for FPGA designs, and algorithms for applying them. We present comparisons between our bounds and the quality of an actual placement for several benchmark designs.