Nathaniel Young

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2022-108

May 13, 2022

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-108.pdf

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 $\Omega(\sqrt[3]{n})$, that dense matrix multiplication requires time $\Omega(n)$ for $n \times n$ matrices, and that sparse-matrix-times-dense-vector multiplication (SpMV) requires time $\Omega(\sqrt{n / \log n})$ for some matrices. We also show that implementation of the Bellman-Ford shortest paths algorithm requires time $\Omega(n^{4/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.

Advisors: John Wawrzynek

---

BibTeX citation:

@mastersthesis{Young:EECS-2022-108,
    Author= {Young, Nathaniel},
    Title= {An Updated Model of Computation for VLSI and Applications to FPGA Implementation},
    School= {EECS Department, University of California, Berkeley},
    Year= {2022},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-108.html},
    Number= {UCB/EECS-2022-108},
    Abstract= {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 $\Omega(\sqrt[3]{n})$, that dense matrix multiplication requires time $\Omega(n)$ for $n \times n$ matrices, and that sparse-matrix-times-dense-vector multiplication (SpMV) requires time $\Omega(\sqrt{n / \log n})$ for some matrices. We also show that implementation of the Bellman-Ford shortest paths algorithm requires time $\Omega(n^{4/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.},
}

EndNote citation:

%0 Thesis
%A Young, Nathaniel 
%T An Updated Model of Computation for VLSI and Applications to FPGA Implementation
%I EECS Department, University of California, Berkeley
%D 2022
%8 May 13
%@ UCB/EECS-2022-108
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-108.html
%F Young:EECS-2022-108